Add precomputed constants for common cases.

There are now 2 features that control the amount of precomputed
constants. They can either be 0, 12, or 256. Most users will likely want
to go with the 12, so this is the default feature.

6 files changed, 106 insertions, 12 deletions

diff --git a/src/lib.rs b/src/lib.rs
index 2548c46..955daf8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -18,6 +18,20 @@
 //! [`PasswordMaker`] is the main part of this crate. You give it settings similar to those of a PasswordMaker Pro profile,
 //! and it gives you a password that's hopfully the same you'd get from PasswordMaker Pro for the same input.
 //! 
+//! # Features
+//! The library comes with a set of precomputed powers to (slightly) speed up computation in common use cases. By default, constants
+//! for the lengths of the pre-defined character sets of PasswordMaker Pro are included (10, 16, 32, 52, 62, 94), amounting to a total
+//! of 360 bytes on a 32bit machine, and 408 bytes on a 64bit machine (and some instructions to read them). For all other character
+//! set lengths the values are computed at runtime when needed. Those values are in the (default-enabled)
+//! `precomputed_common_max_powers` feature.
+//! 
+//! If you prefer simpler code and want to save a couple of bytes in the binary, you can disable `default-features` to use runtime
+//! computation for all values, at the cost of a slight performance impact.
+//! 
+//! On the other hand, if binary size is not of concern, you might want to enable the `precomputed_max_powers` feature.
+//! This feature enables precomputed powers for all bases in the range 2..130. It therefore needs 7680 bytes on a 32bit machine, and
+//! 8704 bytes on a 64bit machine (plus some extra instructions).
+//! 
 //! # Warning
 //! This library has NOT been tested on 16bit machines. It might work, but probably does not.
 
diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs
index e88f379..438ef20 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion.rs
@@ -21,7 +21,7 @@ pub(crate) struct IterativeBaseConversion<V,B>{
 
 impl<V,B> IterativeBaseConversion<V,B> 
     where V: for<'a> From<&'a B> +                          //could be replaced by num::traits::identities::One.
-             ConstantMaxPowerCache<B>,
+             PrecomputedMaxPowers<B>,
           for<'a> &'a V : Mul<&'a B, Output = Option<V>> +  //used to get the first current_base_power.
                           Mul<&'a V, Output = Option<V>>
 {
@@ -96,7 +96,7 @@ pub(crate) trait RemAssignWithQuotient{
     fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self;
 }
 
-pub(crate) trait ConstantMaxPowerCache<B> where Self : Sized{
+pub(crate) trait PrecomputedMaxPowers<B> where Self : Sized{
     fn lookup(_base : &B) -> Option<(Self, usize)> { None }
 }
 
@@ -150,7 +150,7 @@ mod iterative_conversion_tests{
         }
     }
 
-    impl ConstantMaxPowerCache<u64> for MyU128{}
+    impl PrecomputedMaxPowers<u64> for MyU128{}
 
     #[test]
     fn test_simple_u128_to_hex_conversion(){
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
index ae4aeca..5397f03 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
@@ -4,8 +4,10 @@
 
 //let's start with the simple case: u128
 //we do need a NewType here, because actual u128 already has a Mul<&usize> implementation that does not match the version we want.
-
+#[cfg(feature="precomputed_max_powers")]
 mod precomputed_constants;
+#[cfg(all(not(feature="precomputed_max_powers"),feature="precomputed_common_max_powers"))]
+mod precomputed_common_constants;
 
 use std::ops::{DivAssign, Mul};
 use std::convert::{TryFrom, TryInto};
@@ -13,7 +15,7 @@ use std::fmt::Display;
 use std::error::Error;
 use std::iter::once;
 
-use super::iterative_conversion::{RemAssignWithQuotient, ConstantMaxPowerCache};
+use super::iterative_conversion::{RemAssignWithQuotient, PrecomputedMaxPowers};
 
 //Type to be used as V, with usize as B.
 pub(crate) struct SixteenBytes(u128);
@@ -68,7 +70,7 @@ impl Mul<&SixteenBytes> for &SixteenBytes{
     }
 }
 
-impl ConstantMaxPowerCache<usize> for SixteenBytes{}
+impl PrecomputedMaxPowers<usize> for SixteenBytes{}
 
 //--------------------------------------------------------------------------------------------------------------------------------------
 //and now the hard part: The same for [u32;N].
@@ -77,6 +79,11 @@ impl ConstantMaxPowerCache<usize> for SixteenBytes{}
 #[derive(PartialEq, PartialOrd, Ord, Eq, Clone, Debug)]
 pub(crate) struct ArbitraryBytes<const N : usize>([u32;N]);
 
+#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))]
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{}
+#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))]
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{}
+
 const fn from_usize<const N : usize>(x : &usize) -> ArbitraryBytes<N> {
     let mut result = [0;N]; //from Godbolt it looks like the compiler is smart enough to skip the unnecessary inits.
     #[cfg(target_pointer_width = "64")]
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs
new file mode 100644
index 0000000..ffea565
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs
@@ -0,0 +1,72 @@
+//! Precomputed max fitting powers and exponents for common password character lits.
+//! 10 is "digits only"
+//! 16 is "hexadecimal"
+//! 32 is "special characters only"
+//! 52 is "letters only"
+//! 62 is "letters and digits"
+//! 94 is "letters, digits and special characters" - the default for PasswordMaker Pro.
+
+use super::super::iterative_conversion::PrecomputedMaxPowers;
+use super::ArbitraryBytes;
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{
+    fn lookup(base : &usize) -> Option<(Self, usize)> { 
+        match base {
+            10 => Some((ArbitraryBytes([0xAF29_8D05, 0x0E43_95D6, 0x9670_B12B, 0x7F41_0000, 0x0000_0000]), 48)),
+            16 => Some((ArbitraryBytes([0x1000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 39)),
+            32 => Some((ArbitraryBytes([0x0800_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 31)),
+            52 => Some((ArbitraryBytes([0xC3AC_AD73, 0xBB2B_01F7, 0x6D5D_11C1, 0xF100_0000, 0x0000_0000]), 28)),
+            62 => Some((ArbitraryBytes([0x0702_2C89, 0x3992_DDB9, 0xC9B6_E9D6, 0x5CE5_4443, 0x0400_0000]), 26)),
+            94 => Some((ArbitraryBytes([0x27AC_9E29, 0x5D2F_DF56, 0x4DA2_58BA, 0x7B1F_542F, 0x8100_0000]), 24)),
+            _ => None
+        }
+    }
+}
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{
+    fn lookup(base : &usize) -> Option<(Self, usize)> { 
+        match base {
+            10 => Some((ArbitraryBytes([0xDD15_FE86, 0xAFFA_D912, 0x49EF_0EB7, 0x13F3_9EBE, 0xAA98_7B6E, 0x6FD2_A000, 0x0000_0000, 0x0000_0000]), 77)),
+            16 => Some((ArbitraryBytes([0x1000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 63)),
+            32 => Some((ArbitraryBytes([0x8000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 51)),
+            52 => Some((ArbitraryBytes([0x070E_F55B, 0x69EB_9498, 0x3F55_F32D, 0x0BB1_D645, 0x1D6E_AA22, 0x3100_0000, 0x0000_0000, 0x0000_0000]), 44)),
+            62 => Some((ArbitraryBytes([0x0437_92AD, 0xB7D6_D494, 0xD37D_50A9, 0xCA83_391F, 0x58DB_8150, 0x3744_EF95, 0x05BB_0400, 0x0000_0000]), 42)),
+            94 => Some((ArbitraryBytes([0xC5F2_400A, 0x64FC_C0E8, 0x33E1_BCF0, 0x9749_C06B, 0xF160_B863, 0x83C3_ACB8, 0xEC85_2780, 0x0000_0000]), 39)),
+            _ => None
+        }
+     }
+}
+
+#[cfg(test)]
+mod precomputed_common_constants_tests{
+    use super::super::super::PrecomputedMaxPowers;
+    use super::super::super::ArbitraryBytes;
+    use super::super::super::iterative_conversion::IterativeBaseConversion;
+
+    #[test]
+    fn highest_fitting_power_consistency_5(){
+        let mut count = 0;
+        for base in 2..200 {
+            if let Some(precomputed) = ArbitraryBytes::<5>::lookup(&base) {
+                let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<5>,usize>::find_highest_fitting_power_non_cached(&base);
+                assert_eq!(non_cached_result.exponent, precomputed.1);
+                assert_eq!(non_cached_result.power, precomputed.0);
+                count += 1;
+            }
+        }
+        assert!(count > 0);
+    }
+    #[test]
+    fn highest_fitting_power_consistency_8(){
+        let mut count = 0;
+        for base in 2..200 {
+            if let Some(precomputed) = ArbitraryBytes::<8>::lookup(&base) {
+                let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<8>,usize>::find_highest_fitting_power_non_cached(&base);
+                assert_eq!(non_cached_result.exponent, precomputed.1);
+                assert_eq!(non_cached_result.power, precomputed.0);
+                count += 1;
+            }
+        }
+        assert!(count > 0);
+    }
+}
\ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
index 86b8c56..e845176 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
@@ -1,13 +1,14 @@
 use super::const_mul_usize;
 use super::ArbitraryBytes;
-use super::super::iterative_conversion::ConstantMaxPowerCache;
+use super::super::iterative_conversion::PrecomputedMaxPowers;
 
-impl ConstantMaxPowerCache<usize> for ArbitraryBytes<5>{
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{
     fn lookup(base : &usize) -> Option<(Self, usize)> { 
         get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_5)
     }
 }
-impl ConstantMaxPowerCache<usize> for ArbitraryBytes<8>{
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{
     fn lookup(base : &usize) -> Option<(Self, usize)> { 
         get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_8)
      }
@@ -38,7 +39,7 @@ const fn const_find_highest_fitting_power<const N : usize>(base : usize) -> ([u3
 //If anyone could tell me how to implement "~const Clone" in stable Rust, I'd be very happy.
 const fn const_clone<const N : usize>(x : &ArbitraryBytes<N>) -> ArbitraryBytes<N>{ArbitraryBytes(x.0)}
 
-pub(crate) const fn gen_const_max_power_cache<const N : usize, const CNT : usize>() -> [([u32;N],usize);CNT]{
+const fn gen_const_max_power_cache<const N : usize, const CNT : usize>() -> [([u32;N],usize);CNT]{
     let mut result = [([0u32;N],0usize);CNT];
     let mut i = 0usize;
     loop {
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index 311f7c5..cab838e 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -3,7 +3,7 @@ use iterative_conversion_impl::PadWithAZero;
 pub(super) use iterative_conversion::IterativeBaseConversion;
 pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes};
 
-use self::iterative_conversion::ConstantMaxPowerCache;
+use self::iterative_conversion::PrecomputedMaxPowers;
 
 mod iterative_conversion;
 mod iterative_conversion_impl;
@@ -16,7 +16,7 @@ pub(super) trait BaseConversion {
 
 impl<T, const N : usize, const M : usize> BaseConversion for T 
     where T : ToArbitraryBytes<Output = ArbitraryBytes<N>>,
-        for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero<Output = ArbitraryBytes<M>> + ConstantMaxPowerCache<usize>,
+        for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero<Output = ArbitraryBytes<M>> + PrecomputedMaxPowers<usize>,
 {
     type Output = IterativeBaseConversion<ArbitraryBytes<N>, usize>;
     fn convert_to_base(self, base : usize) -> Self::Output {