From 1f57846664b97f0cb630bf5fee13dfbc66f7c77a Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sun, 23 Oct 2022 20:26:23 +0200 Subject: 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. --- .../base_conversion/iterative_conversion.rs | 6 +- .../iterative_conversion_impl/mod.rs | 13 +++- .../precomputed_common_constants.rs | 72 ++++++++++++++++++++++ .../precomputed_constants.rs | 9 +-- src/passwordmaker/base_conversion/mod.rs | 4 +- 5 files changed, 92 insertions(+), 12 deletions(-) create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs (limited to 'src/passwordmaker/base_conversion') 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{ impl IterativeBaseConversion where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. - ConstantMaxPowerCache, + PrecomputedMaxPowers, for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_power. Mul<&'a V, Output = Option> { @@ -96,7 +96,7 @@ pub(crate) trait RemAssignWithQuotient{ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; } -pub(crate) trait ConstantMaxPowerCache where Self : Sized{ +pub(crate) trait PrecomputedMaxPowers where Self : Sized{ fn lookup(_base : &B) -> Option<(Self, usize)> { None } } @@ -150,7 +150,7 @@ mod iterative_conversion_tests{ } } - impl ConstantMaxPowerCache for MyU128{} + impl PrecomputedMaxPowers 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 for SixteenBytes{} +impl PrecomputedMaxPowers for SixteenBytes{} //-------------------------------------------------------------------------------------------------------------------------------------- //and now the hard part: The same for [u32;N]. @@ -77,6 +79,11 @@ impl ConstantMaxPowerCache for SixteenBytes{} #[derive(PartialEq, PartialOrd, Ord, Eq, Clone, Debug)] pub(crate) struct ArbitraryBytes([u32;N]); +#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))] +impl PrecomputedMaxPowers for ArbitraryBytes<5>{} +#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))] +impl PrecomputedMaxPowers for ArbitraryBytes<8>{} + const fn from_usize(x : &usize) -> ArbitraryBytes { 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 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 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::,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::,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 for ArbitraryBytes<5>{ +impl PrecomputedMaxPowers for ArbitraryBytes<5>{ fn lookup(base : &usize) -> Option<(Self, usize)> { get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_5) } } -impl ConstantMaxPowerCache for ArbitraryBytes<8>{ + +impl PrecomputedMaxPowers 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(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(x : &ArbitraryBytes) -> ArbitraryBytes{ArbitraryBytes(x.0)} -pub(crate) const fn gen_const_max_power_cache() -> [([u32;N],usize);CNT]{ +const fn gen_const_max_power_cache() -> [([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 BaseConversion for T where T : ToArbitraryBytes>, - for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero> + ConstantMaxPowerCache, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero> + PrecomputedMaxPowers, { type Output = IterativeBaseConversion, usize>; fn convert_to_base(self, base : usize) -> Self::Output { -- cgit v1.2.3