Precompute power+exponent for iterative conversion

The maximum power of the base that can fit into a given data type is
constant. There's no point in computing it at runtime, if we can just
store it in a compile-time constants array.

The code isn't the most beautiful, but that's mostly because Rust const
functions are still a bit limited.
One function was duplicated, because it was easy to get a slow version
to compile in const context, and const context doesn't really care...

4 files changed, 191 insertions, 75 deletions

diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs
index 6716228..f5db0f7 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion.rs
@@ -20,32 +20,39 @@ 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.
+    where V: for<'a> From<&'a B> +                          //could be replaced by num::traits::identities::One.
+             ConstantMaxPotencyCache<B>,
           for<'a> &'a V : Mul<&'a B, Output = Option<V>> +  //used to get the first current_base_potency.
                           Mul<&'a V, Output = Option<V>>
 {
     pub(super) fn new(value : V, base : B) -> Self{
-        let PotencyAndExponent{potency : current_base_potency, count : remaining_digits} = Self::find_highest_fitting_potency(&base);
+        let PotencyAndExponent{power : current_base_potency, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base);
         Self{
             current_value : value,
             current_base_potency,
-            remaining_digits,
+            remaining_digits: highest_fitting_exponent + 1, //to the power of 0 is a digit too. Soo, if base^n is the largest fitting exponent, n+1 digits.
             base,
         }
     }
 
-    fn find_highest_fitting_potency(base : &B) -> PotencyAndExponent<V> {
-        let base_v = base.into();
+    fn find_highest_fitting_power(base : &B) -> PotencyAndExponent<V> {
+        V::lookup(base).map(|(potency,count)| PotencyAndExponent{ power: potency, exponent: count })
+            .unwrap_or_else(|| Self::find_highest_fitting_power_non_cached(base))
+    }
 
+    //public for unit tests in cache, which is not a sub-module of this.
+    pub(super) fn find_highest_fitting_power_non_cached(base : &B) -> PotencyAndExponent<V> {
+        let base_v = base.into();
+    
         let exp_result = successors(Some((base_v, 1)), |(p, e)| {
             Some(((p*p)?, 2*e))
         }).last();
 
 
-        let result = successors(exp_result, |(potency, count)| (potency * base).map(|v| (v, count +1)))
+        let result = successors(exp_result, |(potency, count)| (potency * base).map(|v| (v, count + 1)))
             .last()
             .expect("Cannot fail, first entry is Some (required V : From<B>) and there's no filtering.");
-        PotencyAndExponent{ potency : result.0, count : result.1 + 1 }
+        PotencyAndExponent{ power : result.0, exponent : result.1 }
     }
 }
 
@@ -79,9 +86,9 @@ impl<V,B> std::iter::ExactSizeIterator for IterativeBaseConversion<V,B>
     where IterativeBaseConversion<V,B> : Iterator
 {}
 
-struct PotencyAndExponent<V>{
-    potency : V,
-    count : usize,
+pub(super) struct PotencyAndExponent<V>{
+    pub(super) power : V,
+    pub(super) exponent : usize,
 }
 
 pub(crate) trait RemAssignWithQuotient{
@@ -89,6 +96,10 @@ pub(crate) trait RemAssignWithQuotient{
     fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self;
 }
 
+pub(crate) trait ConstantMaxPotencyCache<B> where Self : Sized{
+    fn lookup(_base : &B) -> Option<(Self, usize)> { None }
+}
+
 //tests general behaviour, using primitive types.
 #[cfg(test)]
 mod iterative_conversion_tests{
@@ -139,6 +150,7 @@ mod iterative_conversion_tests{
         }
     }
 
+    impl ConstantMaxPotencyCache<u64> for MyU128{}
 
     #[test]
     fn test_simple_u128_to_hex_conversion(){
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
index 76fd32e..7ab9171 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
@@ -5,13 +5,15 @@
 //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.
 
+mod precomputed_constants;
+
 use std::ops::{DivAssign, Mul};
 use std::convert::{TryFrom, TryInto};
 use std::fmt::Display;
 use std::error::Error;
 use std::iter::once;
 
-use super::iterative_conversion::RemAssignWithQuotient;
+use super::iterative_conversion::{RemAssignWithQuotient, ConstantMaxPotencyCache};
 
 //Type to be used as V, with usize as B.
 pub(crate) struct SixteenBytes(u128);
@@ -66,65 +68,33 @@ impl Mul<&SixteenBytes> for &SixteenBytes{
     }
 }
 
+impl ConstantMaxPotencyCache<usize> for SixteenBytes{}
+
 //--------------------------------------------------------------------------------------------------------------------------------------
 //and now the hard part: The same for [u32;N].
 //We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again.
 
-#[derive(PartialEq, PartialOrd, Ord, Eq, Clone)]
+#[derive(PartialEq, PartialOrd, Ord, Eq, Clone, Debug)]
 pub(crate) struct ArbitraryBytes<const N : usize>([u32;N]);
 
-//Const generics are still a bit limited -> let's just implement From for the exact types we need.
-impl From<&usize> for ArbitraryBytes<5>{
-    fn from(x: &usize) -> Self {
-        Self([
-            0,//(*x >> 32*4) as u32, //zero on all target platforms
-            0,//(*x >> 32*3) as u32, //zero on all target platforms
-            0,//(*x >> 32*2) as u32, //zero on all target platforms
-            x.checked_shr(32).map(|x| x as u32).unwrap_or_default(),
-            *x as u32,
-        ])
-    }
+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")]
+    if N > 1 { result[N-2] = (*x >> 32) as u32;}
+    if N > 0 { result[N-1] = *x as u32;} //Compiler should hopefully be smart enough to yeet the condition.
+    ArbitraryBytes(result)
 }
 
-impl From<&usize> for ArbitraryBytes<8>{
+impl<const N : usize> From<&usize> for ArbitraryBytes<N>{
     fn from(x: &usize) -> Self {
-        Self([
-            0,//(*x >> 32*7) as u32, //zero on all target platforms
-            0,//(*x >> 32*6) as u32, //zero on all target platforms
-            0,//(*x >> 32*5) as u32, //zero on all target platforms
-            0,//(*x >> 32*4) as u32, //zero on all target platforms
-            0,//(*x >> 32*3) as u32, //zero on all target platforms
-            0,//(*x >> 32*2) as u32, //zero on all target platforms
-            x.checked_shr(32).map(|x| x as u32).unwrap_or_default(),
-            *x as u32,
-        ])
-    }
-}
-
-impl From<&u32> for ArbitraryBytes<5>{
-    fn from(x: &u32) -> Self {
-        Self([
-            0,
-            0,
-            0,
-            0,
-            *x,
-        ])
+        from_usize(x)
     }
 }
-
-impl From<&u32> for ArbitraryBytes<8>{
+impl<const N : usize> From<&u32> for ArbitraryBytes<N>{
     fn from(x: &u32) -> Self {
-        Self([
-            0,
-            0,
-            0,
-            0,
-            0,
-            0,
-            0,
-            *x,
-        ])
+        let mut result = [0;N];
+        if let Some(l) = result.last_mut() { *l = *x };
+        ArbitraryBytes(result)
     }
 }
 
@@ -237,30 +207,37 @@ impl<const N : usize> TryFrom<&ArbitraryBytes<N>> for u32{
 }
 
 macro_rules! make_mul {
-    ($t:ty, $long_t:ty) => {
+    ($cfn:ident, $t:ty, $long_t:ty) => {
         impl<const N : usize> Mul<$t> for ArbitraryBytes<N>{
             type Output = Option<ArbitraryBytes<N>>;
-            fn mul(mut self, rhs: $t) -> Self::Output {
-                let carry = self.0.iter_mut().rev().fold(<$long_t>::default(), |carry, digit|{
-                    debug_assert_eq!(carry, carry & (<$t>::MAX as $long_t)); //carry always has to fit in usize, otherwise something is terribly wrong.
-                    let res = (*digit as $long_t) * (rhs as $long_t) + carry;
-                    *digit = res as u32;
-                    res >> 32
-                });
-                if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously.
-                    None
-                } else {
-                    Some(self)
-                }
+            fn mul(self, rhs: $t) -> Self::Output {
+                $cfn(self, rhs)
+            }
+        }
+        const fn $cfn<const N : usize>(mut lhs : ArbitraryBytes<N>, rhs: $t) -> Option<ArbitraryBytes<N>> {
+            //sorry for this fugly non-idiomatic syntax, but Rust const functions seem to be severely limited right now :-(
+            let mut carry = 0 as $long_t;
+            let mut idx = N;
+            let rhs = rhs as $long_t;
+            while idx != 0 {
+                idx -= 1;
+                let res = (lhs.0[idx] as $long_t) * rhs + carry;
+                lhs.0[idx] = res as u32;
+                carry = res >> 32;
+            }
+            if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously.
+                None
+            } else {
+                Some(lhs)
             }
         }
     };
 }
-make_mul!(u32,u64);
+make_mul!(const_mul_u32, u32,u64);
 #[cfg(target_pointer_width = "64")]
-make_mul!(usize, u128);
+make_mul!(const_mul_usize, usize, u128);
 #[cfg(not(target_pointer_width = "64"))]
-make_mul!(usize, u64);
+make_mul!(const_mul_usize, usize, u64);
 
 impl<const N : usize> Mul<&usize> for &ArbitraryBytes<N>{
     type Output = Option<ArbitraryBytes<N>>;
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
new file mode 100644
index 0000000..c5a1809
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
@@ -0,0 +1,125 @@
+use super::const_mul_usize;
+use super::ArbitraryBytes;
+use super::super::iterative_conversion::ConstantMaxPotencyCache;
+
+impl ConstantMaxPotencyCache<usize> for ArbitraryBytes<5>{
+    fn lookup(base : &usize) -> Option<(Self, usize)> { 
+        get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_5)
+    }
+}
+impl ConstantMaxPotencyCache<usize> for ArbitraryBytes<8>{
+    fn lookup(base : &usize) -> Option<(Self, usize)> { 
+        get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_8)
+     }
+}
+
+fn get_from_cache<const N : usize>(base : &usize, cache : &[([u32;N], usize)]) -> Option<(ArbitraryBytes<N>, usize)>{
+    base.checked_sub(2).and_then(|idx|cache.get(idx))
+        .map(|c| (ArbitraryBytes(c.0), c.1))
+}
+
+const CONSTANT_MAX_POTENCY_CACHE_5 : [([u32;5],usize);128] = gen_const_max_potency_cache();
+const CONSTANT_MAX_POTENCY_CACHE_8 : [([u32;8],usize);128] = gen_const_max_potency_cache();
+
+//-----------------------------------------------------------------------------------------
+
+/// This version of find_highest_fitting_potency is not optimized. But it can run in const contexts. Only use it there, use the normal one everywhere else.
+const fn const_find_highest_fitting_power<const N : usize>(base : usize) -> ([u32;N],usize){
+    let start = super::from_usize(&base);
+
+    let mut x = (start, 1);
+    while let Some(next) = const_mul_usize(const_clone(&x.0),base) {
+        x.0 = next;
+        x.1 +=1;
+    }
+    (x.0.0, x.1)
+}
+
+//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_potency_cache<const N : usize, const CNT : usize>() -> [([u32;N],usize);CNT]{
+    let mut result = [([0u32;N],0usize);CNT];
+    let mut i = 0usize;
+    loop {
+        let highest = const_find_highest_fitting_power(i + 2);
+        result[i] = (highest.0, highest.1);
+        i +=1;
+        if i == CNT { break; }
+    }
+    result
+}
+
+#[cfg(test)]
+mod iterative_conversion_constants_tests{
+    use super::ArbitraryBytes;
+
+    #[test]
+    fn test_overlows_8()
+    {
+        let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate()
+            .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+        for (base, potency, _exponent) in entries {
+            assert!((potency * base).is_none())
+        }
+    }
+    #[test]
+    fn test_overlows_5()
+    {
+        let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate()
+            .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+        for (base, potency, _exponent) in entries {
+            assert!((potency * base).is_none())
+        }
+    }
+    #[test]
+    fn test_exponent_8()
+    {
+        let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate()
+            .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+        for (base, mut potency, exponent) in entries {
+            //exponent is the largest fitting exponent. Soo, if we divide exponent times, we should end up with 1.
+            for _i in 0..exponent  {
+                let remainder = potency.div_assign_with_remainder_usize(&base);
+                assert_eq!(remainder, 0);
+            }
+            assert_eq!(potency, (&1usize).into());
+        }
+    }
+    #[test]
+    fn test_exponent_5()
+    {
+        let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate()
+            .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+        for (base, mut potency, exponent) in entries {
+            //exponent is the largest fitting exponent. Soo, if we divide exponent times, we should end up with 1.
+            for _i in 0..exponent  {
+                let remainder = potency.div_assign_with_remainder_usize(&base);
+                assert_eq!(remainder, 0);
+            }
+            assert_eq!(potency, (&1usize).into());
+        }
+    }
+    #[test]
+    fn highest_fitting_potency_consistency_5(){
+        use super::super::super::iterative_conversion::IterativeBaseConversion;
+        let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate()
+            .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+        for (base, potency, exponent) in entries {
+            let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<5>,usize>::find_highest_fitting_power_non_cached(&base);
+            assert_eq!(non_cached_result.exponent,exponent);
+            assert_eq!(non_cached_result.power, potency);
+        }
+    }
+    #[test]
+    fn highest_fitting_potency_consistency_8(){
+        use super::super::super::iterative_conversion::IterativeBaseConversion;
+        let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate()
+            .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+        for (base, potency, exponent) in entries {
+            let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<8>,usize>::find_highest_fitting_power_non_cached(&base);
+            assert_eq!(non_cached_result.exponent,exponent);
+            assert_eq!(non_cached_result.power, potency);
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index dc98c92..bb3fbd6 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -3,6 +3,8 @@ use iterative_conversion_impl::PadWithAZero;
 pub(super) use iterative_conversion::IterativeBaseConversion;
 pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes};
 
+use self::iterative_conversion::ConstantMaxPotencyCache;
+
 mod iterative_conversion;
 mod iterative_conversion_impl;
 
@@ -14,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>>,
+        for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero<Output = ArbitraryBytes<M>> + ConstantMaxPotencyCache<usize>,
 {
     type Output = IterativeBaseConversion<ArbitraryBytes<N>, usize>;
     fn convert_to_base(self, base : usize) -> Self::Output {