Exponential search for largest potency.

Speeds up the 20 and 32 byte cases. Has slightly negative impact for 16
byte case.

3 files changed, 110 insertions, 8 deletions

diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs
index 9b55141..95d9fa3 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion.rs
@@ -21,7 +21,8 @@ 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.
-          for<'a> &'a V : Mul<&'a B, Output = Option<V>>    //used to get the first current_base_potency.
+          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);
@@ -34,14 +35,17 @@ impl<V,B> IterativeBaseConversion<V,B>
     }
 
     fn find_highest_fitting_potency(base : &B) -> PotencyAndExponent<V> {
-        //If we also required B: Mul<V> the new() function could be made a bit faster by going base^2 -> base^4 -> base^8 -> and so on.
-        //However, for realistic inputs, we have just about 100 multiplications, so, gut feeling says: simple === faster.
         let base_v = base.into();
-        let result = successors(Some(base_v), |potency| potency * base)
-            .enumerate()
+
+        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)))
             .last()
             .expect("Cannot fail, first entry is Some (required V : From<B>) and there's no filtering.");
-        PotencyAndExponent{ potency : result.1, count : result.0 + 2 }
+        PotencyAndExponent{ potency : result.0, count : result.1 + 1 }
     }
 }
 
@@ -101,6 +105,13 @@ mod iterative_conversion_tests{
         }
     }
 
+    impl Mul<&MyU128> for &MyU128 {
+        type Output = Option<MyU128>;
+        fn mul(self, rhs: &MyU128) -> Self::Output {
+            self.0.checked_mul(rhs.0).map(|s| MyU128(s))
+     }
+    }
+
     impl RemAssignWithQuotient for MyU128{
         fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self {
             let quotient = self.0 / divisor.0;
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
index c402b20..752dfa3 100644
--- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
@@ -59,6 +59,14 @@ impl Mul<&usize> for &SixteenBytes{
     }
 }
 
+impl Mul<&SixteenBytes> for &SixteenBytes{
+    type Output = Option<SixteenBytes>;
+
+    fn mul(self, rhs: &SixteenBytes) -> Self::Output {
+        self.0.checked_mul(rhs.0).map(Into::into)
+    }
+}
+
 //--------------------------------------------------------------------------------------------------------------------------------------
 //and now the hard part: The same for [u32;N].
 //We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again.
@@ -252,6 +260,33 @@ impl<const N : usize> Mul<&usize> for &ArbitraryBytes<N>{
     }
 }
 
+impl<const N : usize> Mul<&ArbitraryBytes<N>> for &ArbitraryBytes<N> where ArbitraryBytes<N> : for<'a> From<&'a usize> {
+    type Output = Option<ArbitraryBytes<N>>;
+    ///School method for now. Just to see if this is any fast.
+    fn mul(self, rhs: &ArbitraryBytes<N>) -> Self::Output {
+        let mut result : ArbitraryBytes<N> = (&0_usize).into();
+        let no_overflow = rhs.0.iter().enumerate().filter(|(_,b)| **b != 0).try_for_each(|(i,b)|{
+            let p : Option<ArbitraryBytes<N>> = self.clone() * *b;
+            let p = p.filter(|p| p.0[0..(N-1-i)].iter().all(|&i| i == 0));
+            let carry = p.map(|p|{
+                //for some reason it's faster to use slices than iterators here.
+                add_assign_slice(&mut result.0[0..(i+1)], &p.0[(N-1-i)..])
+            });
+            carry.filter(|x| *x == 0).map(|_|())
+        });
+        no_overflow.map(|_| result)
+    }
+}
+
+fn add_assign_slice(lhs : &mut [u32], rhs : &[u32]) -> u32 {
+    debug_assert_eq!(lhs.len(), rhs.len());
+    lhs.iter_mut().zip(rhs.iter()).rev().fold(0, |carry, (a, b)| {
+        let s = (*a as u64) + (*b as u64) + carry;
+        *a = s as u32;
+        s >> 32
+    }) as u32
+}
+
 impl<const N : usize, const M : usize> RemAssignWithQuotient for ArbitraryBytes<N> 
     where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero<Output = ArbitraryBytes<M>>
 {
@@ -570,4 +605,62 @@ mod iterative_conversion_impl_tests{
         a.sub_assign(&b);
         assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]);
     }
+
+    #[test]
+    fn mul_arbitrary_test(){
+        let a = ArbitraryBytes::new([0,0,0,0x47ea7314,0xfba75574]);
+        let b = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]);
+        let a_big = (0x47ea7314_u128 << 32) | 0xfba75574u128;
+        let b_big = (0x12345678_u128 << 32) | 0xabcde012u128;
+        let c_big = a_big*b_big;
+        let c = (&a * &b).unwrap();
+        assert_eq!(c_big & 0xffff_ffff, c.0[4] as u128 );
+        assert_eq!((c_big >> 32 ) & 0xffff_ffff, c.0[3] as u128);
+        assert_eq!((c_big >> 64 ) & 0xffff_ffff, c.0[2] as u128);
+        assert_eq!((c_big >> 96 ) & 0xffff_ffff, c.0[1] as u128);
+        assert_eq!(0, c.0[0]);
+    }
+    #[test]
+    fn mul_arbitrary_test_2(){
+        let a = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+        let b = ArbitraryBytes::new([0,0,0,0,2]);
+        let c = (&a * &b).unwrap();
+        assert_eq!(0x4EC7593F, c.0[0]);
+        assert_eq!(0xA35C3E70, c.0[1]);
+        assert_eq!(2*0x1753a5c7, c.0[2]);
+        assert_eq!(0x8fd4e629, c.0[3]);
+        assert_eq!(0xf74eaae8, c.0[4]);
+    }
+    #[test]
+    fn mul_arbitrary_test_3(){
+        let a = ArbitraryBytes::new([0,0,0,0,2]);
+        let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+        let c = (&a * &b).unwrap();
+        assert_eq!(0x4EC7593F, c.0[0]);
+        assert_eq!(0xA35C3E70, c.0[1]);
+        assert_eq!(2*0x1753a5c7, c.0[2]);
+        assert_eq!(0x8fd4e629, c.0[3]);
+        assert_eq!(0xf74eaae8, c.0[4]);
+    }
+    #[test]
+    fn mul_arbitrary_test_4(){
+        let a = ArbitraryBytes::new([0,0,0,0,8]);
+        let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+        let c = &a * &b;
+        assert!(c.is_none())
+    }
+    #[test]
+    fn mul_arbitrary_test_5(){
+        let a = ArbitraryBytes::new([0,0,0,1,0]);
+        let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+        let c = &a * &b;
+        assert!(c.is_none())
+    }
+    #[test]
+    fn mul_arbitrary_test_6(){
+        let a = ArbitraryBytes::new([0,0,0,1,1]);
+        let b = ArbitraryBytes::new([0,0xffffffff,0x1753a5c7,0x47ea7314,0xfba75574]);
+        let c = &a * &b;
+        assert!(c.is_none())
+    }
 }
\ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index b1ffedf..dc98c92 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -9,8 +9,6 @@ mod iterative_conversion_impl;
 /// Converts an input to a different base (which fits in usize). Returns the digits starting at the most significant one.
 pub(super) trait BaseConversion {
     type Output : ExactSizeIterator<Item=usize>;
-    // return type is subject to change. Hopefully soon the math will be rewritten, so we can skip the Vec and IntoIter.
-    // will have to remain an ExactSizeIterator though.
     fn convert_to_base(self, base : usize) -> Self::Output;
 }