aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion.rs32
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs (renamed from src/passwordmaker/base_conversion/iterative_conversion_impl.rs)105
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs125
-rw-r--r--src/passwordmaker/base_conversion/mod.rs4
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 {
generated by cgit v1.2.3 (git 2.46.0) at 2025-09-18 21:37:46 +0000