From d5b30baf4dd8ff8dbc4c0bd22b9178c914cbe973 Mon Sep 17 00:00:00 2001
From: Andreas Grois <andi@grois.info>
Date: Sun, 23 Oct 2022 15:09:23 +0200
Subject: 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...
---
 .../base_conversion/iterative_conversion.rs        | 32 +++++++++++++++-------
 1 file changed, 22 insertions(+), 10 deletions(-)

(limited to 'src/passwordmaker/base_conversion/iterative_conversion.rs')

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(){
-- 
cgit v1.2.3