From b1f4d48e956c6b6599b666248e5aa157b9660dca Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Tue, 18 Oct 2022 07:56:16 +0200 Subject: First draft of (untested) iterative conversion. --- src/passwordmaker/base_conversion/mod.rs | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'src/passwordmaker/base_conversion/mod.rs') diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index 8d217ef..4ae7653 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -1,6 +1,10 @@ use std::convert::TryInto; -use self::remainders::CalcRemainders; +use remainders::CalcRemainders; + +mod division; +mod iterative_conversion; +mod iterative_conversion_impl; mod remainders; mod remainders_impl; -- cgit v1.2.3 From 86851fe70c0ff7ff1da98a82edabeef9c2ad989e Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Tue, 18 Oct 2022 21:18:23 +0200 Subject: Draft of iterative_conversion. --- src/passwordmaker/base_conversion/division.rs | 32 -------- .../base_conversion/iterative_conversion.rs | 9 ++- .../base_conversion/iterative_conversion_impl.rs | 87 ++++++++++++++++------ src/passwordmaker/base_conversion/mod.rs | 51 +++++++------ src/passwordmaker/base_conversion/remainders.rs | 43 ----------- .../base_conversion/remainders_impl.rs | 76 ------------------- src/passwordmaker/mod.rs | 56 +++++++------- 7 files changed, 129 insertions(+), 225 deletions(-) delete mode 100644 src/passwordmaker/base_conversion/division.rs delete mode 100644 src/passwordmaker/base_conversion/remainders.rs delete mode 100644 src/passwordmaker/base_conversion/remainders_impl.rs (limited to 'src/passwordmaker/base_conversion/mod.rs') diff --git a/src/passwordmaker/base_conversion/division.rs b/src/passwordmaker/base_conversion/division.rs deleted file mode 100644 index c6fc911..0000000 --- a/src/passwordmaker/base_conversion/division.rs +++ /dev/null @@ -1,32 +0,0 @@ -/// A trait that combines std::ops::Div and std::ops::Rem, as those can often be computed together. -pub(super) trait Division where Self:Sized { - /// does in-place arbitrary-length division. Returns remainder. - fn divide(self, divisor : &D) -> DivisionResult; - fn is_zero(&self) -> bool; -} - -/// Or mark your type as `UseGenericDivision` to just use `/` and `%` operators for types. Makes only sense for integers. -pub(super) trait UseGenericDivision : Clone - + for <'a> std::ops::Div<&'a Self, Output = Self> - + for <'a> std::ops::Rem<&'a Self, Output = Self> - + Default - + Eq {} - - impl Division for U - where U: UseGenericDivision -{ - fn divide(self, divisor : &Self) -> DivisionResult { - DivisionResult { - result: self.clone().div(divisor), - remainder: self.rem(divisor) - } - } - fn is_zero(&self) -> bool { - *self == Self::default() - } -} - -pub(super) struct DivisionResult { - pub result : T, - pub remainder : U, -} \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index 94d28c0..9b55141 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -12,7 +12,7 @@ use std::convert::TryInto; use std::ops::{Mul, DivAssign}; use std::iter::successors; -pub(super) struct IterativeBaseConversion{ +pub(crate) struct IterativeBaseConversion{ current_value : V, current_base_potency : V, remaining_digits : usize, @@ -141,4 +141,11 @@ mod iterative_conversion_tests{ assert_eq!(i.len(), 32); assert_eq!(i.skip_while(|x| *x == 0_u64).collect::>(), vec![7, 5, 0xA, 0x10, 0xC, 0xC, 3, 0xD, 3, 0xA, 3,8,4,8,3]); } + #[test] + fn test_simple_u128_to_base_39_conversion(){ + let i = IterativeBaseConversion::new(MyU128(1234567890123456789u128), 39u64); + assert_eq!(i.len(), 25); + // 3YPRS4FaC1KU + assert_eq!(i.skip_while(|x| *x == 0_u64).collect::>(), vec![3, 34, 25, 27, 28, 4, 15, 36, 12, 1, 20, 30]); + } } \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index be1d851..3dceb9b 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -15,7 +15,13 @@ use std::{ops::{DivAssign, Mul, SubAssign}, convert::{TryFrom, TryInto}, fmt::Di use super::iterative_conversion::RemAssignWithQuotient; //Type to be used as V, with usize as B. -struct SixteenBytes(u128); +pub(crate) struct SixteenBytes(u128); + +impl SixteenBytes{ + pub(super) fn new(value : u128) -> Self { + SixteenBytes(value) + } +} //just for convenience impl From for SixteenBytes{ @@ -58,7 +64,7 @@ impl Mul<&usize> for &SixteenBytes{ //We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again. #[derive(PartialEq, PartialOrd, Ord, Eq, Clone)] -struct ArbitraryBytes([u32;N]); +pub(crate) struct ArbitraryBytes([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>{ @@ -116,7 +122,7 @@ impl From<&u32> for ArbitraryBytes<8>{ } //workaround for lack of proper const-generic support. -trait PadWithAZero{ +pub(super) trait PadWithAZero{ type Output; fn pad_with_a_zero(&self) -> Self::Output; } @@ -160,7 +166,7 @@ impl DivAssign<&usize> for ArbitraryBytes{ } #[derive(Debug, Clone, Copy)] -struct ArbitraryBytesToUsizeError; +pub(crate) struct ArbitraryBytesToUsizeError; impl Display for ArbitraryBytesToUsizeError{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "conversion from arbitrary sized int-array to usize failed") @@ -203,7 +209,7 @@ impl TryFrom<&ArbitraryBytes> for usize{ } #[derive(Debug, Clone, Copy)] -struct ArbitraryBytesToU32Error; +pub(crate) struct ArbitraryBytesToU32Error; impl Display for ArbitraryBytesToU32Error{ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "conversion from arbitrary sized int-array to u32 failed") @@ -233,7 +239,7 @@ impl Mul<&usize> for &ArbitraryBytes{ //somewhere we need this clone, can just as well be in here... let mut result = self.0.clone(); let carry = result.iter_mut().rev().fold(UsizeAndFour::default(), |carry, digit|{ - assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry always has to fit in usize, otherwise something is terribly wrong. + debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry always has to fit in usize, otherwise something is terribly wrong. let res = (*digit as UsizeAndFour) * (*rhs as UsizeAndFour) + carry; *digit = res as u32; res >> 32 @@ -276,7 +282,7 @@ impl Mul for ArbitraryBytes{ fn mul(mut self, rhs: u32) -> Self::Output { //somewhere we need this clone, can just as well be in here... let carry = self.0.iter_mut().rev().fold(u64::default(), |carry, digit|{ - assert_eq!(carry, carry & (u32::MAX as u64)); //carry always has to fit in usize, otherwise something is terribly wrong. + debug_assert_eq!(carry, carry & (u32::MAX as u64)); //carry always has to fit in usize, otherwise something is terribly wrong. let res = (*digit as u64) * (rhs as u64) + carry; *digit = res as u32; res >> 32 @@ -301,31 +307,35 @@ impl SubAssign<&ArbitraryBytes> for ArbitraryBytes{ 1 } }); - assert_eq!(carry,0); + debug_assert_eq!(carry,0); } } impl ArbitraryBytes{ + pub(super) fn new(data : [u32;N]) -> Self { + ArbitraryBytes(data) + } + /// Replaces self with Quotient and returns Remainder fn div_assign_with_remainder_usize(&mut self, rhs: &usize) -> usize { #[cfg(target_pointer_width = "64")] type UsizeAndFour = u128; #[cfg(not(target_pointer_width = "64"))] type UsizeAndFour = u64; - assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128); + debug_assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128); let divisor : UsizeAndFour = *rhs as UsizeAndFour; let remainder = self.0.iter_mut().fold(0 as UsizeAndFour,|carry, current| { - assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize. + debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize. let carry_shifted = carry << 32; let dividend = (carry_shifted) + (*current as UsizeAndFour); let ratio = dividend / divisor; - assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. *current = (ratio) as u32; dividend - (*current as UsizeAndFour) * divisor }); - assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); + debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); remainder as usize } @@ -333,15 +343,15 @@ impl ArbitraryBytes{ fn div_assign_with_remainder_u32(&mut self, rhs: &u32) -> u32 { let divisor : u64 = *rhs as u64; let remainder = self.0.iter_mut().fold(0 as u64,|carry, current| { - assert_eq!(carry, carry & (u32::MAX as u64)); //carry has to be lower than divisor, and divisor is usize. + debug_assert_eq!(carry, carry & (u32::MAX as u64)); //carry has to be lower than divisor, and divisor is usize. let carry_shifted = carry << 32; let dividend = (carry_shifted) + (*current as u64); let ratio = dividend / divisor; - assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. *current = (ratio) as u32; dividend - (*current as u64) * divisor }); - assert_eq!(remainder, remainder & (u32::MAX as u64)); + debug_assert_eq!(remainder, remainder & (u32::MAX as u64)); remainder as u32 } @@ -355,10 +365,10 @@ impl ArbitraryBytes{ where Self : PadWithAZero> + for<'a> From<&'a usize> { - assert!(M == N+1); + debug_assert!(M == N+1); //first we need to find n (number of digits in divisor) let n_digits_divisor= N - divisor.find_first_nonzero_digit(); - assert!(n_digits_divisor > 1); + debug_assert!(n_digits_divisor > 1); //and same in the non-normalized dividend let m_plus_n_digits_dividend = N - self.find_first_nonzero_digit(); let m_extra_digits_dividend = m_plus_n_digits_dividend - n_digits_divisor; @@ -376,7 +386,7 @@ impl ArbitraryBytes{ let divisor_second_significant_digit = divisor.get_digit_from_right(n_digits_divisor-2) as u64; //step D2, D7: the loop. - for j in m_extra_digits_dividend..=0 { + for j in (0..=m_extra_digits_dividend).rev() { //Step D3: Guess a digit let guess_dividend = ((dividend.get_digit_from_right(j+n_digits_divisor) as u64)<<32) + (dividend.get_digit_from_right(j + n_digits_divisor - 1) as u64); let mut guesstimate = guess_dividend/guess_divisor; @@ -393,7 +403,7 @@ impl ArbitraryBytes{ //I'm too tired to do this by the book. If this thing is gonna blow, we can just as well increase our guesstimate by one and call it a day. //In any case, this does only happen in _very_ rare cases. Soo: //Steps D4-D6. - assert!(guesstimate & (u32::MAX as u64) == guesstimate); //Knuth says this is a one-place number, and I trust him. + debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate); //Knuth says this is a one-place number, and I trust him. let mut guesstimate = guesstimate as u32; let mut s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type."); let will_overflow = @@ -402,7 +412,7 @@ impl ArbitraryBytes{ if will_overflow { guesstimate -= 1; s -= &divisor; - assert!(std::cmp::Ord::cmp(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]) != Ordering::Less) + debug_assert!(std::cmp::Ord::cmp(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]) != Ordering::Less) } slice_sub_assign(&mut dividend.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); quotient.set_digit_from_right(guesstimate, j); @@ -428,7 +438,7 @@ impl ArbitraryBytes{ } fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){ - assert_eq!(lhs.len(), rhs.len()); + debug_assert_eq!(lhs.len(), rhs.len()); let carry = lhs.iter_mut().zip(rhs.iter()).rev().fold(0_u64,|carry,(i,s)| { let s = (*s as u64) + carry; if *i as u64 >= s { @@ -439,5 +449,38 @@ fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){ 1 } }); - assert_eq!(carry,0); + debug_assert_eq!(carry,0); +} + +#[cfg(test)] +mod iterative_conversion_impl_tests{ + use super::*; + + #[test] + fn knuth_add_back_test(){ + let mut dividend = ArbitraryBytes::new([ + //m = 3, n=5 + u32::MAX, + u32::MAX, + u32::MAX-1, + u32::MAX, + u32::MAX, + 0, + 0, + 3 + ]); + let divisor = ArbitraryBytes::new([ + 0, + 0, + 0, + 0, + 0, + u32::MAX, + u32::MAX, + u32::MAX, + ]); + let result = dividend.rem_assign_with_quotient(&divisor); + assert_eq!(dividend.0, [0,0,0,0,0,0,0,2]); + assert_eq!(result.0, [0,0,0,u32::MAX,u32::MAX, u32::MAX, u32::MAX, u32::MAX]); + } } \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index 4ae7653..b1ffedf 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -1,60 +1,63 @@ use std::convert::TryInto; +use iterative_conversion_impl::PadWithAZero; +pub(super) use iterative_conversion::IterativeBaseConversion; +pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes}; -use remainders::CalcRemainders; - -mod division; mod iterative_conversion; mod iterative_conversion_impl; -mod remainders; -mod remainders_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; // 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) -> std::iter::Rev>; + fn convert_to_base(self, base : usize) -> Self::Output; } -impl BaseConversion for T where T : ToI32Array{ - fn convert_to_base(self, base : usize) -> std::iter::Rev> { - self.to_int_array().calc_remainders(base).collect::>().into_iter().rev() +impl BaseConversion for T + where T : ToArbitraryBytes>, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero>, +{ + type Output = IterativeBaseConversion, usize>; + fn convert_to_base(self, base : usize) -> Self::Output { + IterativeBaseConversion::new(self.to_arbitrary_bytes(), base) } } impl BaseConversion for [u8;16]{ - fn convert_to_base(self, base : usize) -> std::iter::Rev> { - u128::from_be_bytes(self).calc_remainders(base as u128).map(|ll| ll as usize).collect::>().into_iter().rev() + type Output = IterativeBaseConversion; + fn convert_to_base(self, base : usize) -> IterativeBaseConversion { + IterativeBaseConversion::new(SixteenBytes::new(u128::from_be_bytes(self)), base) } } // Rust 1.52 only has a very limited support for const generics. This means, we'll have to live with this not-too-constrained solution... -pub(super) trait ToI32Array { +pub(super) trait ToArbitraryBytes { type Output; - fn to_int_array(self) -> Self::Output; + fn to_arbitrary_bytes(self) -> Self::Output; } //this could of course be done in a generic manner, but it's ugly without array_mut, which we don't have in Rust 1.52. //Soo, pedestrian's approach :D -impl ToI32Array for [u8;20] { - type Output = [u32; 5]; - fn to_int_array(self) -> [u32; 5] { - [ +impl ToArbitraryBytes for [u8;20] { + type Output = ArbitraryBytes<5>; + fn to_arbitrary_bytes(self) -> ArbitraryBytes<5> { + ArbitraryBytes::new([ u32::from_be_bytes(self[0..4].try_into().unwrap()), u32::from_be_bytes(self[4..8].try_into().unwrap()), u32::from_be_bytes(self[8..12].try_into().unwrap()), u32::from_be_bytes(self[12..16].try_into().unwrap()), u32::from_be_bytes(self[16..20].try_into().unwrap()), - ] + ]) } } -impl ToI32Array for [u8;32] { - type Output = [u32; 8]; - fn to_int_array(self) -> [u32; 8] { - [ +impl ToArbitraryBytes for [u8;32] { + type Output = ArbitraryBytes<8>; + fn to_arbitrary_bytes(self) -> ArbitraryBytes<8> { + ArbitraryBytes::new([ u32::from_be_bytes(self[0..4].try_into().unwrap()), u32::from_be_bytes(self[4..8].try_into().unwrap()), u32::from_be_bytes(self[8..12].try_into().unwrap()), @@ -63,6 +66,6 @@ impl ToI32Array for [u8;32] { u32::from_be_bytes(self[20..24].try_into().unwrap()), u32::from_be_bytes(self[24..28].try_into().unwrap()), u32::from_be_bytes(self[28..32].try_into().unwrap()), - ] + ]) } } \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs deleted file mode 100644 index 344fab2..0000000 --- a/src/passwordmaker/base_conversion/remainders.rs +++ /dev/null @@ -1,43 +0,0 @@ -use super::division::{Division, DivisionResult}; - -/// Trait used for the old base conversion. -pub(super) trait CalcRemainders{ - fn calc_remainders(self, divisor : D) -> Remainders; -} - -impl CalcRemainders for T - where T:Division -{ - fn calc_remainders(self, divisor : D) -> Remainders { - Remainders::new(self,divisor) - } -} - -pub(super) struct Remainders{ - value : Option, - divisor : U, -} - -impl> Remainders { - fn new(value : T, divisor : U) -> Self { - let value = if value.is_zero() { None } else { Some(value) }; - Remainders { - value, - divisor, - } - } -} - -impl> Iterator for Remainders{ - type Item=U; - - fn next(&mut self) -> Option { - if let Some(v) = self.value.take() { - let DivisionResult{result, remainder} = v.divide(&self.divisor); - self.value = if result.is_zero() { None } else { Some(result) }; - Some(remainder) - } else { - None - } - } -} \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/remainders_impl.rs b/src/passwordmaker/base_conversion/remainders_impl.rs deleted file mode 100644 index c2431bb..0000000 --- a/src/passwordmaker/base_conversion/remainders_impl.rs +++ /dev/null @@ -1,76 +0,0 @@ -use super::division::{Division, UseGenericDivision, DivisionResult}; - -impl UseGenericDivision for u128{} //for Md4, Md5 - -impl Division for [u32;N] { - #[allow(clippy::cast_possible_truncation)] - fn divide(mut self, divisor : &usize) -> DivisionResult { - #[cfg(target_pointer_width = "64")] - type UsizeAndFour = u128; - #[cfg(not(target_pointer_width = "64"))] - type UsizeAndFour = u64; - assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128); - - //uses mutation, because why not? self is owned after all :D - let divisor : UsizeAndFour = *divisor as UsizeAndFour; - let remainder = self.iter_mut().fold(0 as UsizeAndFour,|carry, current| { - assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize. - let carry_shifted = carry << 32; - let dividend = (carry_shifted) + (*current as UsizeAndFour); - let ratio = dividend / divisor; - assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. - *current = (ratio) as u32; - dividend - (*current as UsizeAndFour) * divisor - }); - assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); - let remainder = remainder as usize; - DivisionResult{ - result: self, - remainder, - } - } - - fn is_zero(&self) -> bool { - self.iter().all(|x| *x == 0) - } -} - -#[cfg(test)] -mod remainders_tests{ - use super::super::remainders::CalcRemainders; - - use super::*; - #[test] - fn test_generic_division(){ - let v = 50u128; - let d = 7u128; - let DivisionResult{result, remainder}=v.divide(&d); - assert_eq!(7, result); - assert_eq!(1, remainder); - } - - #[test] - fn test_remainders() { - //relies on generic division. - let v = 141u128; - let d = 3u128; - let results : Vec = v.calc_remainders(d).collect(); - assert_eq!(results, vec![0u128,2u128,0u128,2u128,1u128]) - } - - #[test] - fn test_array_divide() { - let dividend_int = 0xe7f1ec3a5f35af805407a8a531eefb79u128; - let dividend = [(dividend_int >> 96) as u32, ((dividend_int >> 64) & 0xffffffff) as u32, ((dividend_int >> 32) & 0xffffffff) as u32, (dividend_int & 0xffffffff) as u32]; - #[cfg(target_pointer_width = "64")] - let divisor = 1531534813576487; - #[cfg(not(target_pointer_width = "64"))] - let divisor = 1531534813; - let result_int = dividend_int / (divisor as u128); - let remainder_int = dividend_int % (divisor as u128); - let result = dividend.divide(&divisor); - assert_eq!(result.result, [(result_int >> 96) as u32, ((result_int >> 64) & 0xffffffff) as u32, ((result_int >> 32) & 0xffffffff) as u32, (result_int & 0xffffffff) as u32]); - assert_eq!(remainder_int, result.remainder as u128); - } - -} \ No newline at end of file diff --git a/src/passwordmaker/mod.rs b/src/passwordmaker/mod.rs index a96698d..5e51ee9 100644 --- a/src/passwordmaker/mod.rs +++ b/src/passwordmaker/mod.rs @@ -1,10 +1,13 @@ -use std::iter::repeat; +use std::iter::SkipWhile; + use unicode_segmentation::UnicodeSegmentation; use leet::LeetReplacementTable; use grapheme::Grapheme; use base_conversion::BaseConversion; +use self::base_conversion::{IterativeBaseConversion, SixteenBytes, ArbitraryBytes}; + use super::Hasher; mod base_conversion; @@ -94,7 +97,6 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let message = yeet_upper_bytes(&message).collect::>(); let hash = H::MD5::hash(&message); let grapheme_indices = hash.convert_to_base(characters.len()); - let grapheme_indices = yoink_additional_graphemes_for_06_if_needed(grapheme_indices); GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::V06(grapheme_indices)} } @@ -112,7 +114,6 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let data = yeet_upper_bytes(data); let hash = hmac::hmac::(key, data); let grapheme_indices = hash.convert_to_base(characters.len()); - let grapheme_indices = yoink_additional_graphemes_for_06_if_needed(grapheme_indices); GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::V06(grapheme_indices)} } @@ -128,17 +129,17 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let data = leetified_data.as_deref().unwrap_or(data); let grapheme_indices = match algo { Algorithm::Md4 => - modern_hmac_to_grapheme_indices::(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern16(modern_hmac_to_grapheme_indices::(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Md5 => - modern_hmac_to_grapheme_indices::(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern16(modern_hmac_to_grapheme_indices::(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Sha1 => - modern_hmac_to_grapheme_indices::(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern20(modern_hmac_to_grapheme_indices::(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Sha256 => - modern_hmac_to_grapheme_indices::(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern32(modern_hmac_to_grapheme_indices::(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Ripemd160 => - modern_hmac_to_grapheme_indices::(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern20(modern_hmac_to_grapheme_indices::(&key, data, characters.len()).skip_while(is_zero)), }; - GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::Modern(grapheme_indices)} + GetGraphemesIterator { graphemes : characters, inner: grapheme_indices} } fn generate_password_part_modern<'a>( @@ -152,17 +153,17 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let message = pre_leet_level.as_ref().map(|l| l.leetify(&message)).unwrap_or(message); let grapheme_indices = match algo { Algorithm::Md4 => - modern_message_to_grapheme_indices::(&message, characters.len()), + GetGraphemesIteratorInner::Modern16(modern_message_to_grapheme_indices::(&message, characters.len()).skip_while(is_zero)), Algorithm::Md5 => - modern_message_to_grapheme_indices::(&message,characters.len()), + GetGraphemesIteratorInner::Modern16(modern_message_to_grapheme_indices::(&message,characters.len()).skip_while(is_zero)), Algorithm::Sha1 => - modern_message_to_grapheme_indices::(&message,characters.len()), + GetGraphemesIteratorInner::Modern20(modern_message_to_grapheme_indices::(&message,characters.len()).skip_while(is_zero)), Algorithm::Sha256 => - modern_message_to_grapheme_indices::(&message,characters.len()), + GetGraphemesIteratorInner::Modern32(modern_message_to_grapheme_indices::(&message,characters.len()).skip_while(is_zero)), Algorithm::Ripemd160 => - modern_message_to_grapheme_indices::(&message,characters.len()), + GetGraphemesIteratorInner::Modern20(modern_message_to_grapheme_indices::(&message,characters.len()).skip_while(is_zero)), }; - GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::Modern(grapheme_indices)} + GetGraphemesIterator { graphemes : characters, inner: grapheme_indices} } } @@ -195,9 +196,15 @@ fn combine_prefix_password_suffix<'a, T : Iterator>>(password: .collect() } +fn is_zero(i : &usize) -> bool { + *i == 0 +} + enum GetGraphemesIteratorInner { - Modern(std::iter::Rev>), - V06(std::iter::Chain>, std::iter::Rev>>) + Modern16(SkipWhile,fn(&usize)->bool>), + Modern20(SkipWhile,usize>,fn(&usize)->bool>), + Modern32(SkipWhile,usize>,fn(&usize)->bool>), + V06(IterativeBaseConversion) } struct GetGraphemesIterator<'a> { graphemes : &'a Vec>, @@ -212,21 +219,23 @@ impl<'a> Iterator for GetGraphemesIterator<'a> { fn next(&mut self) -> Option { let idx = match &mut self.inner { - GetGraphemesIteratorInner::Modern(i) => i.next(), + GetGraphemesIteratorInner::Modern16(i) => i.next(), + GetGraphemesIteratorInner::Modern20(i) => i.next(), + GetGraphemesIteratorInner::Modern32(i) => i.next(), GetGraphemesIteratorInner::V06(i) => i.next(), }; idx.and_then(|idx| self.graphemes.get(idx).cloned()) } } -fn modern_hmac_to_grapheme_indices(key : &str, data: &str, divisor : usize) -> std::iter::Rev> +fn modern_hmac_to_grapheme_indices(key : &str, data: &str, divisor : usize) -> <::Output as BaseConversion>::Output where T:Hasher, ::Output: BaseConversion + AsRef<[u8]> { hmac::hmac::(key.bytes(), data.bytes()).convert_to_base(divisor) } -fn modern_message_to_grapheme_indices(data: &str, divisor : usize) -> std::iter::Rev> +fn modern_message_to_grapheme_indices(data: &str, divisor : usize) -> <::Output as BaseConversion>::Output where T:Hasher, ::Output: BaseConversion { @@ -307,11 +316,4 @@ impl AlgoSelection { #[allow(clippy::cast_possible_truncation)] //clippy, stop complaining. Truncating is the very purpose of this function... fn yeet_upper_bytes(input : &str) -> impl Iterator + Clone + '_ { input.encode_utf16().map(|wide_char| wide_char as u8) -} - -//signature subject to change, but need named types... -fn yoink_additional_graphemes_for_06_if_needed(input : std::iter::Rev>) - -> std::iter::Chain>, std::iter::Rev>> -{ - repeat(0_usize).take(32-input.len()).chain(input) } \ No newline at end of file -- cgit v1.2.3 From f8b8a1f5804057bf150e60a757d86b984099a631 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 21 Oct 2022 19:08:23 +0200 Subject: Exponential search for largest potency. Speeds up the 20 and 32 byte cases. Has slightly negative impact for 16 byte case. --- .../base_conversion/iterative_conversion.rs | 23 ++++-- .../base_conversion/iterative_conversion_impl.rs | 93 ++++++++++++++++++++++ src/passwordmaker/base_conversion/mod.rs | 2 - 3 files changed, 110 insertions(+), 8 deletions(-) (limited to 'src/passwordmaker/base_conversion/mod.rs') 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{ impl IterativeBaseConversion where V: for<'a> From<&'a B>, //could be replaced by num::traits::identities::One. - for<'a> &'a V : Mul<&'a B, Output = Option> //used to get the first current_base_potency. + for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_potency. + Mul<&'a V, Output = Option> { 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 IterativeBaseConversion } fn find_highest_fitting_potency(base : &B) -> PotencyAndExponent { - //If we also required B: Mul 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) 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; + 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; + + 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 Mul<&usize> for &ArbitraryBytes{ } } +impl Mul<&ArbitraryBytes> for &ArbitraryBytes where ArbitraryBytes : for<'a> From<&'a usize> { + type Output = Option>; + ///School method for now. Just to see if this is any fast. + fn mul(self, rhs: &ArbitraryBytes) -> Self::Output { + let mut result : ArbitraryBytes = (&0_usize).into(); + let no_overflow = rhs.0.iter().enumerate().filter(|(_,b)| **b != 0).try_for_each(|(i,b)|{ + let p : Option> = 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 RemAssignWithQuotient for ArbitraryBytes where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero> { @@ -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; - // 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; } -- cgit v1.2.3 From d5b30baf4dd8ff8dbc4c0bd22b9178c914cbe973 Mon Sep 17 00:00:00 2001 From: Andreas Grois 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 +- .../base_conversion/iterative_conversion_impl.rs | 898 --------------------- .../iterative_conversion_impl/mod.rs | 875 ++++++++++++++++++++ .../precomputed_constants.rs | 125 +++ src/passwordmaker/base_conversion/mod.rs | 4 +- 5 files changed, 1025 insertions(+), 909 deletions(-) delete mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl.rs create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs (limited to 'src/passwordmaker/base_conversion/mod.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{ } impl IterativeBaseConversion - 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, for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_potency. Mul<&'a V, Output = Option> { 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 { - let base_v = base.into(); + fn find_highest_fitting_power(base : &B) -> PotencyAndExponent { + 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 { + 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) 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 std::iter::ExactSizeIterator for IterativeBaseConversion where IterativeBaseConversion : Iterator {} -struct PotencyAndExponent{ - potency : V, - count : usize, +pub(super) struct PotencyAndExponent{ + 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 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 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.rs deleted file mode 100644 index 76fd32e..0000000 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ /dev/null @@ -1,898 +0,0 @@ -//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N]. -//! Beware that all functions in this module are optimized for the use cases of passwordmaker-rs. They may or may not -//! be suitable for anything else. - -//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. - -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; - -//Type to be used as V, with usize as B. -pub(crate) struct SixteenBytes(u128); - -impl SixteenBytes{ - pub(super) fn new(value : u128) -> Self { - SixteenBytes(value) - } -} - -//just for convenience -impl From for SixteenBytes{ - fn from(x: u128) -> Self { - SixteenBytes(x) - } -} -impl From<&usize> for SixteenBytes{ - fn from(x: &usize) -> Self { - SixteenBytes(*x as u128) - } -} -impl DivAssign<&usize> for SixteenBytes{ - fn div_assign(&mut self, rhs: &usize) { - self.0 /= *rhs as u128 - } -} -impl RemAssignWithQuotient for SixteenBytes{ - fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self { - let quotient = self.0 / divisor.0; - self.0 %= divisor.0; - Self(quotient) - } -} -impl TryFrom for usize{ - type Error = std::num::TryFromIntError; - fn try_from(value: SixteenBytes) -> Result { - value.0.try_into() - } -} -impl Mul<&usize> for &SixteenBytes{ - type Output = Option; - fn mul(self, rhs: &usize) -> Self::Output { - self.0.checked_mul(*rhs as u128).map(Into::into) - } -} - -impl Mul<&SixteenBytes> for &SixteenBytes{ - type Output = Option; - - 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. - -#[derive(PartialEq, PartialOrd, Ord, Eq, Clone)] -pub(crate) struct ArbitraryBytes([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, - ]) - } -} - -impl From<&usize> for ArbitraryBytes<8>{ - 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, - ]) - } -} - -impl From<&u32> for ArbitraryBytes<8>{ - fn from(x: &u32) -> Self { - Self([ - 0, - 0, - 0, - 0, - 0, - 0, - 0, - *x, - ]) - } -} - -//workaround for lack of proper const-generic support. -pub(crate) trait PadWithAZero{ - type Output; - fn pad_with_a_zero(&self) -> Self::Output; -} - -impl PadWithAZero for ArbitraryBytes<5>{ - type Output = ArbitraryBytes<6>; - fn pad_with_a_zero(&self) -> Self::Output { - ArbitraryBytes::<6>([ - 0, - self.0[0], - self.0[1], - self.0[2], - self.0[3], - self.0[4], - ]) - } -} - -impl PadWithAZero for ArbitraryBytes<8>{ - type Output = ArbitraryBytes<9>; - fn pad_with_a_zero(&self) -> Self::Output { - ArbitraryBytes::<9>([ - 0, - self.0[0], - self.0[1], - self.0[2], - self.0[3], - self.0[4], - self.0[5], - self.0[6], - self.0[7], - ]) - } -} - -impl DivAssign<&usize> for ArbitraryBytes{ - //just do long division. - fn div_assign(&mut self, rhs: &usize) { - self.div_assign_with_remainder_usize(rhs); - } -} - -#[derive(Debug, Clone, Copy)] -pub(crate) struct ArbitraryBytesToUsizeError; -impl Display for ArbitraryBytesToUsizeError{ - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - write!(f, "conversion from arbitrary sized int-array to usize failed") - } -} -impl Error for ArbitraryBytesToUsizeError{} - -impl TryFrom> for usize{ - type Error = ArbitraryBytesToUsizeError; - - fn try_from(value: ArbitraryBytes) -> Result { - usize::try_from(&value) - } -} - -impl TryFrom<&ArbitraryBytes> for usize{ - type Error = ArbitraryBytesToUsizeError; - #[cfg(target_pointer_width = "64")] - fn try_from(value: &ArbitraryBytes) -> Result { - //64 bits. - if value.0[0..N.saturating_sub(2)].iter().any(|x| *x != 0) { - Err(ArbitraryBytesToUsizeError) - } else { - //failing to get last_bit is an actual error. - let last_bit = value.0.get(N-1).ok_or(ArbitraryBytesToUsizeError).copied(); - //second-last is not an error though. - let second_last_bit = value.0.get(N-2).copied().unwrap_or_default(); - last_bit.map(|last_bit| u64_from_u32s(second_last_bit, last_bit) as usize) - } - } - #[cfg(not(target_pointer_width = "64"))] - fn try_from(value: &ArbitraryBytes) -> Result { - //16 or 32 bits. - if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { - Err(ArbitraryBytesToUsizeError) - } else { - value.0.get(N-1).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToUsizeError) - } - } -} - -#[derive(Debug, Clone, Copy)] -pub(crate) struct ArbitraryBytesToU32Error; -impl Display for ArbitraryBytesToU32Error{ - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - write!(f, "conversion from arbitrary sized int-array to u32 failed") - } -} -impl Error for ArbitraryBytesToU32Error{} - -impl TryFrom<&ArbitraryBytes> for u32{ - type Error = ArbitraryBytesToU32Error; - - fn try_from(value: &ArbitraryBytes) -> Result { - if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { - Err(ArbitraryBytesToU32Error) - } else { - value.0.get(N-1).copied().ok_or(ArbitraryBytesToU32Error) - } - } -} - -macro_rules! make_mul { - ($t:ty, $long_t:ty) => { - impl Mul<$t> for ArbitraryBytes{ - type Output = Option>; - 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) - } - } - } - }; -} -make_mul!(u32,u64); -#[cfg(target_pointer_width = "64")] -make_mul!(usize, u128); -#[cfg(not(target_pointer_width = "64"))] -make_mul!(usize, u64); - -impl Mul<&usize> for &ArbitraryBytes{ - type Output = Option>; - fn mul(self, rhs: &usize) -> Self::Output { - (*self).clone() * (*rhs) - } -} - -impl Mul<&ArbitraryBytes> for &ArbitraryBytes where ArbitraryBytes : for<'a> From<&'a usize> { - type Output = Option>; - ///School method. I haven't tried Karatsuba, but rule of thumb is that it only gets faster at about 32 digits. We have 8 digits max. - fn mul(self, rhs: &ArbitraryBytes) -> Self::Output { - let mut result : ArbitraryBytes = (&0_usize).into(); - let no_overflow = rhs.0.iter().enumerate().filter(|(_,b)| **b != 0).try_for_each(|(i,b)|{ - let p : Option> = 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. - slice_overflowing_add_assign(&mut result.0[0..(i+1)], &p.0[(N-1-i)..]) - }); - carry.filter(|x| !x).map(|_|()) - }); - no_overflow.map(|_| result) - } -} - -impl RemAssignWithQuotient for ArbitraryBytes - where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero> -{ - fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self{ - - //This is based on Knuth, TAOCP vol 2 section 4.3, algorithm D. - //First, check if we can get away without doing a division. - match Ord::cmp(self, divisor){ - std::cmp::Ordering::Less => Self::from(&0_usize), //leave self unchanged, it's the remainder. - std::cmp::Ordering::Equal => { *self = Self::from(&0_usize); Self::from(&1_usize) }, - std::cmp::Ordering::Greater => { - //If a single digit division suffices, do a single digit division. - if let Ok(divisor_as_u32) = divisor.try_into() { - self.rem_assign_with_quotient_u32(&divisor_as_u32) - } else { - self.rem_assign_with_quotient_knuth(divisor) - } - }, - } - } -} - -macro_rules! make_div_assign_with_remainder { - ($name:ident, $t_divisor:ty, $t_long:ty) => { - /// Replaces self with Quotient and returns Remainder - fn $name(&mut self, rhs: &$t_divisor) -> $t_divisor { - debug_assert!((<$t_long>::MAX >> 32) as u128 >= <$t_divisor>::MAX as u128); - - let divisor = *rhs as $t_long; - let remainder = self.0.iter_mut().fold(0 as $t_long,|carry, current| { - debug_assert_eq!(carry, carry & (<$t_divisor>::MAX as $t_long)); //carry has to be lower than divisor, and divisor is $t_divisor. - let carry_shifted = carry << 32; - let dividend = (carry_shifted) | (*current as $t_long); - let remainder = dividend % divisor; - let ratio = dividend / divisor; - debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. - *current = (ratio) as u32; - remainder - }); - debug_assert_eq!(remainder, remainder & (<$t_divisor>::MAX as $t_long)); - remainder as $t_divisor - } - }; -} - -impl ArbitraryBytes{ - pub(super) fn new(data : [u32;N]) -> Self { - ArbitraryBytes(data) - } - - #[cfg(target_pointer_width = "64")] - make_div_assign_with_remainder!(div_assign_with_remainder_usize, usize, u128); - - #[cfg(not(target_pointer_width = "64"))] - make_div_assign_with_remainder!(div_assign_with_remainder_usize, usize, u64); - - make_div_assign_with_remainder!(div_assign_with_remainder_u32, u32, u64); - - fn rem_assign_with_quotient_u32(&mut self, divisor: &u32) -> Self where Self : for<'a> From<&'a u32> { - let remainder = self.div_assign_with_remainder_u32(divisor); - std::mem::replace(self, Self::from(&remainder)) - } - - //This is Knuth, The Art of Computer Programming Volume 2, Section 4.3, Algorithm D. - fn rem_assign_with_quotient_knuth(&mut self, divisor : &Self) -> Self - where Self : PadWithAZero> + - for<'a> From<&'a usize> - { - debug_assert!(M == N+1); - //first we need to find n (number of digits in divisor) - let n_digits_divisor= N - divisor.find_first_nonzero_digit(); - debug_assert!(n_digits_divisor > 1); - //and same in the non-normalized dividend - let m_plus_n_digits_dividend = N - self.find_first_nonzero_digit(); - let m_extra_digits_dividend = m_plus_n_digits_dividend - n_digits_divisor; - - //step D1: Normalize. This brings the maximum error for each digit down to no more than 2. - let normalize_shift = divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros() as usize; - //again, missing const generics ruin all the fun. - let mut dividend = self.shift_left(normalize_shift); - let divisor = divisor.shift_left(normalize_shift); - debug_assert_eq!(divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros(),0); - - let mut quotient : Self = (&0_usize).into(); - - //needed for Step D3, but is the same for all iterations -> factored out. - let guess_divisor = divisor.get_digit_from_right(n_digits_divisor - 1) as u64; - let divisor_second_significant_digit = divisor.get_digit_from_right(n_digits_divisor-2) as u64; - - //step D2, D7: the loop. - for j in (0..=m_extra_digits_dividend).rev() { - //Step D3: Guess a digit - let guess_dividend = u64_from_u32s(dividend.get_digit_from_right(j+n_digits_divisor), dividend.get_digit_from_right(j + n_digits_divisor - 1)); - let mut guesstimate = guess_dividend/guess_divisor; - let mut guess_reminder = guess_dividend % guess_divisor; - //refine our guesstimate (still step D3). Ensures that error of guesstimate is either 0 or +1. - while guess_reminder <= u32::MAX as u64 - && (guesstimate > u32::MAX as u64 - || divisor_second_significant_digit * guesstimate - > (guess_reminder << 32) | (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64) - ) { - guesstimate -= 1; - guess_reminder += guess_divisor; - } - //Step D4: Pretend the guess was correct and subtract guesstimate * divisor from dividend. - debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate, "The while above should have made guesstimate a one-digit number. Debug!"); - let mut guesstimate = guesstimate as u32; - let s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type."); - let s_range = (M - 1 - n_digits_divisor)..M; - let d_range = (s_range.start - j)..(s_range.end - j); - let did_overflow = slice_overflowing_sub_assign(&mut dividend.0[d_range.clone()], &s.0[s_range.clone()]); - //Step D5: If guesstimate was incorrect, the subtraction has overflown. The result is wrapped in such a case. - if did_overflow { - //Step D6: We have to correct our guesstimate. It was too large by one. We also have to fix the overflow that has occured. - guesstimate -= 1; - //The addition must overflow again. The two overflows cancel out, and since we are using wrapping arithmetics, the result becomes correct again. - let did_overflow = slice_overflowing_add_assign(&mut dividend.0[d_range.clone()], &divisor.0[s_range.clone()]); - debug_assert!(did_overflow, "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.") - } - quotient.set_digit_from_right(guesstimate, j); - } - - //Steop D8: Compute Remainder. - self.0 = dividend.shift_right(normalize_shift).0[1..].try_into() - .expect("Conversion of what should have been an N-element slice into an N-element array failed."); - quotient - - } - - fn find_first_nonzero_digit(&self) -> usize{ - self.0.iter().enumerate().skip_while(|(_,v)| **v == 0).next().map(|(x,_)| x).unwrap_or(N) - } - - fn get_digit_from_right(&self, i : usize) -> u32{ - self.0[N-i-1] - } - fn set_digit_from_right(&mut self, val: u32, i : usize){ - self.0[N-i-1] = val; - } - - fn shift_left(&self, s : usize) -> ::Output - where Self : PadWithAZero> - { - debug_assert!(s < 32); - let mut res = self.pad_with_a_zero(); - if s != 0{ - res.0.iter_mut().zip(self.0.iter().chain(once(&0))).for_each(|(current, next)| *current = (*current << s) | (*next >> (32-s))); - } - res - } - - fn shift_right(mut self, s : usize) -> Self { - debug_assert!(s < 32); - if s != 0 { - let _ = self.0.iter_mut().fold(0u32, |carry, val| { - let c = *val << (32-s); - *val >>= s; - debug_assert!(*val & carry == 0); - *val |= carry; - c - }); - } - self - } -} - -fn slice_overflowing_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ - debug_assert_eq!(lhs.len(), rhs.len()); - lhs.iter_mut().zip(rhs.iter()).rev().fold(false,|carry,(a,b)| { - let r = b.overflowing_add(carry as u32); - let s = a.overflowing_sub(r.0); - *a = s.0; - r.1 || s.1 - }) -} - -fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool { - debug_assert_eq!(lhs.len(), rhs.len()); - lhs.iter_mut().zip(rhs.iter()).rev().fold(false, |carry, (a, b)| { - let r = b.overflowing_add(carry as u32); - let s = a.overflowing_add(r.0); - *a = s.0; - r.1 || s.1 - }) -} - -fn u64_from_u32s(msb : u32, lsb : u32) -> u64{ - let msb = msb as u64; - let lsb = lsb as u64; - (msb << 32) | lsb -} - -#[cfg(test)] -mod arbitrary_bytes_tests{ - use super::*; - use rand::RngCore; - use rand_xoshiro::rand_core::SeedableRng; - use rand_xoshiro::Xoshiro256Plus; - - /// Tests specifically the case that will_overflow is true. - #[test] - fn knuth_add_back_test(){ - let mut dividend = ArbitraryBytes::new([ - //m = 3, n=5 - u32::MAX, - u32::MAX, - u32::MAX-1, - u32::MAX, - u32::MAX, - 0, - 0, - 3 - ]); - let divisor = ArbitraryBytes::new([ - 0, - 0, - 0, - 0, - 0, - u32::MAX, - u32::MAX, - u32::MAX, - ]); - let result = dividend.rem_assign_with_quotient(&divisor); - assert_eq!(dividend.0, [0,0,0,0,0,0,0,2]); - assert_eq!(result.0, [0,0,0,u32::MAX,u32::MAX, u32::MAX, u32::MAX, u32::MAX]); - } - - - fn prepare_many_numbers(max_dividend_digits : u32, min_dividend_digits : u32, max_divisor_digits : u32, min_divisor_digits : u32) -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ - assert!(max_dividend_digits < 5); - assert!(min_dividend_digits <= max_dividend_digits); - assert!(max_divisor_digits < 5); - assert!(min_divisor_digits <= max_divisor_digits); - let mut rng = Xoshiro256Plus::seed_from_u64(0); - let mut res = Vec::new(); - for _i in 0..1000000 { - let dx = rng.next_u32() % (max_dividend_digits + 1 - min_dividend_digits) + min_dividend_digits; - let dy = rng.next_u32() % (max_divisor_digits + 1 - min_divisor_digits) + min_divisor_digits; - let ds = dx.min(dy); - let dl = dx.max(dy); - let dividendx = [ - 0, - if dl >= 4 { rng.next_u32() } else { 0 }, - if dl >= 3 { rng.next_u32() } else { 0 }, - if dl >= 2 { rng.next_u32() } else { 0 }, - if dl >= 1 { rng.next_u32() } else { 0 }, - ]; - let divisorx = [ - 0, - if ds >= 4 { rng.next_u32() } else { 0 }, - if ds >= 3 { rng.next_u32() } else { 0 }, - if ds >= 2 { rng.next_u32() } else { 0 }, - if ds >= 1 { rng.next_u32() } else { 0 }, - ]; - let needs_swap = ds == dl && dividendx[5-ds as usize] < divisorx[5-ds as usize]; - let dividend = ArbitraryBytes::new(if needs_swap {divisorx} else {dividendx}); - let divisor = ArbitraryBytes::new(if needs_swap {dividendx} else {divisorx}); - assert!(dividend.ge(&divisor)); - - let td = - ((dividend.0[1] as u128)<<96) - + ((dividend.0[2] as u128)<<64) - + ((dividend.0[3] as u128)<<32) - + (dividend.0[4] as u128); - let tn = - ((divisor.0[1] as u128)<<96) - + ((divisor.0[2] as u128)<<64) - + ((divisor.0[3] as u128)<<32) - + (divisor.0[4] as u128); - - - res.push((dividend, divisor, td/tn, td%tn)); - } - res - } - - /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.) - #[test] - fn rem_assign_with_quotient_knuth_many_numbers_test() { - let input = prepare_many_numbers(4,2, 4, 2); - for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { - let quotient = dividend.rem_assign_with_quotient_knuth(&divisor); - let remainder = dividend; - let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); - let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); - assert_eq!(quotient, expected_quotient); - assert_eq!(remainder, expexted_remainder); - } - } - /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.) - #[test] - fn rem_assign_with_quotient_many_numbers_test() { - let input = prepare_many_numbers(4,1, 4, 1); - for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { - let quotient = dividend.rem_assign_with_quotient(&divisor); - let remainder = dividend; - let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); - let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); - assert_eq!(quotient, expected_quotient); - assert_eq!(remainder, expexted_remainder); - } - } - - #[test] - fn rem_assign_with_quotient_u32_many_numbers_test() { - let input = prepare_many_numbers(4,1, 1, 1); - for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { - let quotient = dividend.rem_assign_with_quotient_u32(&divisor.0.last().unwrap()); - let remainder = dividend; - let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); - let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); - assert_eq!(quotient, expected_quotient); - assert_eq!(remainder, expexted_remainder); - } - } - - #[test] - fn rem_assign_with_quotient_u32_test(){ - let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let quotient = a.rem_assign_with_quotient_u32(&0x12345); - assert_eq!(quotient.0, [0x9A10,0xB282B7BA,0xE4948E98,0x2AE63D74,0xE6FDFF4A]); - assert_eq!(a.0, [0,0,0,0,0x6882]); - } - - #[test] - fn rem_assign_with_quotient_u32_test2(){ - let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]); - let quotient = a.rem_assign_with_quotient_u32(&0x12345); - assert_eq!(quotient.0, [0,0,0,0,0]); - assert_eq!(a.0, [0,0,0,0,0x1234]); - } - - #[test] - fn div_assign_with_remainder_usize_test(){ - let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let remainder = a.div_assign_with_remainder_usize(&0x1234_usize); - assert_eq!(a.0, [0x9A135,0x79AA8650,0xD251DC7A,0x9AA8C1F2,0x8B9729EF]); - assert_eq!(remainder, 0x2E8); - } - - #[test] - fn div_assign_with_remainder_usize_test2(){ - let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]); - let remainder = a.div_assign_with_remainder_usize(&0x1235_usize); - assert_eq!(a.0, [0,0,0,0,0]); - assert_eq!(remainder, 0x1234); - } - - #[cfg(target_pointer_width = "64")] - #[test] - fn div_assign_with_remainder_usize_test3(){ - let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let remainder = a.div_assign_with_remainder_usize(&0x123456789ab_usize); - assert_eq!(a.0, [0,0x9A107B,0xBEC8B35A,0xEC9D3B43,0x056F803A]); - assert_eq!(remainder, 0xD7537A4B6); - } - - #[test] - fn sub_assign_test() { - let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let b = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let carry = slice_overflowing_sub_assign(&mut a.0,&b.0); - assert!(!carry); - assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]); - } - - #[test] - fn sub_assign_test2() { - let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let carry = slice_overflowing_sub_assign(&mut a.0,&b.0); - assert!(carry); - assert_eq!(a.0, [0x935D3D98,0x4BEB08CB,0x4CF2240D,0xCA49E363,0xB0268A9E]); - } - - #[test] - fn add_assign_test() { - let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let carry = slice_overflowing_add_assign(&mut a.0,&b.0); - assert!(!carry); - assert_eq!(a.0, [0xF1F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]); - } - #[test] - fn add_assign_test2() { - let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = ArbitraryBytes::new([0xbf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); - let carry = slice_overflowing_add_assign(&mut a.0,&b.0); - assert!(carry); - assert_eq!(a.0, [0x01F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]); - } - - #[test] - fn shift_left_test() { - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = a.shift_left(7); - assert_eq!(b.0,[0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]); - } - - #[test] - fn shift_right_test() { - let a = ArbitraryBytes::new([0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]); - let b = a.shift_right(7); - assert_eq!(b.0,[0, 0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - } - - #[test] - fn get_digit_from_right_test(){ - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - assert_eq!(a.get_digit_from_right(3), 0xffffffff); - } - - #[test] - fn set_digit_from_right_test(){ - let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - a.set_digit_from_right(0xdeadbeef, 4); - assert_eq!(a.0[0], 0xdeadbeef); - } - - #[test] - fn find_first_nonzero_digit_test() { - let a = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]); - assert_eq!(a.find_first_nonzero_digit(),3); - } - - #[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()) - } - - #[test] - fn mul_with_u32_test(){ - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = 3u32; - let product = a*b; - assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036]) - } - #[test] - fn mul_with_u32_test2(){ - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = 4u32; - let product = a*b; - assert!(product.is_none()) - } - #[test] - fn mul_with_usize_test_working(){ - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = 3usize; - let product = a*b; - assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036]) - } - #[test] - fn mul_with_usize_test_overflow(){ - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = 4usize; - let product = a*b; - assert!(product.is_none()) - } - #[cfg(target_pointer_width = "64")] - #[test] - fn mul_with_usize_test_64bit_works(){ - let a = ArbitraryBytes::new([0,0,0xc7138bd5,0x12345678,0xabcde012]); - let b = 0x123456789ausize; - let product = a*b; - assert_eq!(product.unwrap().0, [0xE,0x28130BBC,0x7442D257,0x1FEDDF10,0xC8ED3AD4]) - } - #[cfg(target_pointer_width = "64")] - #[test] - fn mul_with_usize_test_64bit_overflow(){ - let a = ArbitraryBytes::new([0,0x1,0xc7138bd5,0x12345678,0xabcde012]); - let b = usize::MAX; - let product = a*b; - assert!(product.is_none()) - } - #[test] - fn try_into_u32_test(){ - let a = ArbitraryBytes::new([0,0,0,0,0xabcde012]); - let b : u32 = (&a).try_into().unwrap(); - assert_eq!(b, 0xabcde012); - } - #[test] - fn try_into_u32_test_overflows(){ - let a = ArbitraryBytes::new([0,0,0,0x1,0xabcde012]); - let b : Result = (&a).try_into(); - assert!(b.is_err()) - } - #[test] - fn try_into_usize_test(){ - let a = ArbitraryBytes::new([0,0,0,0,0xe012]); - let b : usize = (&a).try_into().unwrap(); - assert_eq!(b, 0xe012); - } - #[test] - fn try_into_usize_test_overflows(){ - let a = ArbitraryBytes::new([0,0,0x1,0,0xabcde012]); - let b : Result = (&a).try_into(); - assert!(b.is_err()) - } - #[cfg(target_pointer_width = "64")] - #[test] - fn try_into_usize_test_on_64_bits(){ - let a = ArbitraryBytes::new([0,0,0,0x54a,0xabcde012]); - let b : usize= (&a).try_into().unwrap(); - assert_eq!(b, 0x54aabcde012); - } - #[cfg(target_pointer_width = "32")] - #[test] - fn try_into_usize_test_on_64_bits(){ - let a = ArbitraryBytes::new([0,0,0,0x54a,0xabcde012]); - let b : Result = (&a).try_into(); - assert!(b.is_err()) - } - #[test] - fn pad_with_a_zero_5(){ - let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = a.pad_with_a_zero(); - assert_eq!(*b.0.first().unwrap(),0); - assert_eq!(b.0[1..], a.0); - } - #[test] - fn pad_with_a_zero_8(){ - let a = ArbitraryBytes::new([0x4631abcd,0x35a40be4,0x074c4d0a,0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = a.pad_with_a_zero(); - assert_eq!(*b.0.first().unwrap(),0); - assert_eq!(b.0[1..], a.0); - } - #[cfg(target_pointer_width = "64")] - #[test] - fn from_usize_5_large(){ - let a : ArbitraryBytes<5> = (&0x7246abcd705aef_usize).into(); - assert_eq!(a.0[4], 0xcd705aef); - assert_eq!(a.0[3], 0x007246ab); - assert!(a.0[..3].iter().all(|x| *x==0)); - } - #[test] - fn from_usize_5(){ - let a : ArbitraryBytes<5> = (&0xcd705aef_usize).into(); - assert_eq!(a.0[4], 0xcd705aef); - assert!(a.0[..4].iter().all(|x| *x==0)); - } - #[cfg(target_pointer_width = "64")] - #[test] - fn from_usize_8_large(){ - let a : ArbitraryBytes<8> = (&0x7246abcd705aef_usize).into(); - assert_eq!(a.0[7], 0xcd705aef); - assert_eq!(a.0[6], 0x007246ab); - assert!(a.0[..6].iter().all(|x| *x==0)); - } - #[test] - fn from_usize_8(){ - let a : ArbitraryBytes<8> = (&0xcd705aef_usize).into(); - assert_eq!(a.0[7], 0xcd705aef); - assert!(a.0[..7].iter().all(|x| *x==0)); - } -} \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs new file mode 100644 index 0000000..7ab9171 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -0,0 +1,875 @@ +//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N]. +//! Beware that all functions in this module are optimized for the use cases of passwordmaker-rs. They may or may not +//! be suitable for anything else. + +//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, ConstantMaxPotencyCache}; + +//Type to be used as V, with usize as B. +pub(crate) struct SixteenBytes(u128); + +impl SixteenBytes{ + pub(super) fn new(value : u128) -> Self { + SixteenBytes(value) + } +} + +//just for convenience +impl From for SixteenBytes{ + fn from(x: u128) -> Self { + SixteenBytes(x) + } +} +impl From<&usize> for SixteenBytes{ + fn from(x: &usize) -> Self { + SixteenBytes(*x as u128) + } +} +impl DivAssign<&usize> for SixteenBytes{ + fn div_assign(&mut self, rhs: &usize) { + self.0 /= *rhs as u128 + } +} +impl RemAssignWithQuotient for SixteenBytes{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self { + let quotient = self.0 / divisor.0; + self.0 %= divisor.0; + Self(quotient) + } +} +impl TryFrom for usize{ + type Error = std::num::TryFromIntError; + fn try_from(value: SixteenBytes) -> Result { + value.0.try_into() + } +} +impl Mul<&usize> for &SixteenBytes{ + type Output = Option; + fn mul(self, rhs: &usize) -> Self::Output { + self.0.checked_mul(*rhs as u128).map(Into::into) + } +} + +impl Mul<&SixteenBytes> for &SixteenBytes{ + type Output = Option; + + fn mul(self, rhs: &SixteenBytes) -> Self::Output { + self.0.checked_mul(rhs.0).map(Into::into) + } +} + +impl ConstantMaxPotencyCache 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, Debug)] +pub(crate) struct ArbitraryBytes([u32;N]); + +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")] + 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{ + fn from(x: &usize) -> Self { + from_usize(x) + } +} +impl From<&u32> for ArbitraryBytes{ + fn from(x: &u32) -> Self { + let mut result = [0;N]; + if let Some(l) = result.last_mut() { *l = *x }; + ArbitraryBytes(result) + } +} + +//workaround for lack of proper const-generic support. +pub(crate) trait PadWithAZero{ + type Output; + fn pad_with_a_zero(&self) -> Self::Output; +} + +impl PadWithAZero for ArbitraryBytes<5>{ + type Output = ArbitraryBytes<6>; + fn pad_with_a_zero(&self) -> Self::Output { + ArbitraryBytes::<6>([ + 0, + self.0[0], + self.0[1], + self.0[2], + self.0[3], + self.0[4], + ]) + } +} + +impl PadWithAZero for ArbitraryBytes<8>{ + type Output = ArbitraryBytes<9>; + fn pad_with_a_zero(&self) -> Self::Output { + ArbitraryBytes::<9>([ + 0, + self.0[0], + self.0[1], + self.0[2], + self.0[3], + self.0[4], + self.0[5], + self.0[6], + self.0[7], + ]) + } +} + +impl DivAssign<&usize> for ArbitraryBytes{ + //just do long division. + fn div_assign(&mut self, rhs: &usize) { + self.div_assign_with_remainder_usize(rhs); + } +} + +#[derive(Debug, Clone, Copy)] +pub(crate) struct ArbitraryBytesToUsizeError; +impl Display for ArbitraryBytesToUsizeError{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "conversion from arbitrary sized int-array to usize failed") + } +} +impl Error for ArbitraryBytesToUsizeError{} + +impl TryFrom> for usize{ + type Error = ArbitraryBytesToUsizeError; + + fn try_from(value: ArbitraryBytes) -> Result { + usize::try_from(&value) + } +} + +impl TryFrom<&ArbitraryBytes> for usize{ + type Error = ArbitraryBytesToUsizeError; + #[cfg(target_pointer_width = "64")] + fn try_from(value: &ArbitraryBytes) -> Result { + //64 bits. + if value.0[0..N.saturating_sub(2)].iter().any(|x| *x != 0) { + Err(ArbitraryBytesToUsizeError) + } else { + //failing to get last_bit is an actual error. + let last_bit = value.0.get(N-1).ok_or(ArbitraryBytesToUsizeError).copied(); + //second-last is not an error though. + let second_last_bit = value.0.get(N-2).copied().unwrap_or_default(); + last_bit.map(|last_bit| u64_from_u32s(second_last_bit, last_bit) as usize) + } + } + #[cfg(not(target_pointer_width = "64"))] + fn try_from(value: &ArbitraryBytes) -> Result { + //16 or 32 bits. + if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { + Err(ArbitraryBytesToUsizeError) + } else { + value.0.get(N-1).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToUsizeError) + } + } +} + +#[derive(Debug, Clone, Copy)] +pub(crate) struct ArbitraryBytesToU32Error; +impl Display for ArbitraryBytesToU32Error{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "conversion from arbitrary sized int-array to u32 failed") + } +} +impl Error for ArbitraryBytesToU32Error{} + +impl TryFrom<&ArbitraryBytes> for u32{ + type Error = ArbitraryBytesToU32Error; + + fn try_from(value: &ArbitraryBytes) -> Result { + if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { + Err(ArbitraryBytesToU32Error) + } else { + value.0.get(N-1).copied().ok_or(ArbitraryBytesToU32Error) + } + } +} + +macro_rules! make_mul { + ($cfn:ident, $t:ty, $long_t:ty) => { + impl Mul<$t> for ArbitraryBytes{ + type Output = Option>; + fn mul(self, rhs: $t) -> Self::Output { + $cfn(self, rhs) + } + } + const fn $cfn(mut lhs : ArbitraryBytes, rhs: $t) -> Option> { + //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!(const_mul_u32, u32,u64); +#[cfg(target_pointer_width = "64")] +make_mul!(const_mul_usize, usize, u128); +#[cfg(not(target_pointer_width = "64"))] +make_mul!(const_mul_usize, usize, u64); + +impl Mul<&usize> for &ArbitraryBytes{ + type Output = Option>; + fn mul(self, rhs: &usize) -> Self::Output { + (*self).clone() * (*rhs) + } +} + +impl Mul<&ArbitraryBytes> for &ArbitraryBytes where ArbitraryBytes : for<'a> From<&'a usize> { + type Output = Option>; + ///School method. I haven't tried Karatsuba, but rule of thumb is that it only gets faster at about 32 digits. We have 8 digits max. + fn mul(self, rhs: &ArbitraryBytes) -> Self::Output { + let mut result : ArbitraryBytes = (&0_usize).into(); + let no_overflow = rhs.0.iter().enumerate().filter(|(_,b)| **b != 0).try_for_each(|(i,b)|{ + let p : Option> = 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. + slice_overflowing_add_assign(&mut result.0[0..(i+1)], &p.0[(N-1-i)..]) + }); + carry.filter(|x| !x).map(|_|()) + }); + no_overflow.map(|_| result) + } +} + +impl RemAssignWithQuotient for ArbitraryBytes + where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero> +{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self{ + + //This is based on Knuth, TAOCP vol 2 section 4.3, algorithm D. + //First, check if we can get away without doing a division. + match Ord::cmp(self, divisor){ + std::cmp::Ordering::Less => Self::from(&0_usize), //leave self unchanged, it's the remainder. + std::cmp::Ordering::Equal => { *self = Self::from(&0_usize); Self::from(&1_usize) }, + std::cmp::Ordering::Greater => { + //If a single digit division suffices, do a single digit division. + if let Ok(divisor_as_u32) = divisor.try_into() { + self.rem_assign_with_quotient_u32(&divisor_as_u32) + } else { + self.rem_assign_with_quotient_knuth(divisor) + } + }, + } + } +} + +macro_rules! make_div_assign_with_remainder { + ($name:ident, $t_divisor:ty, $t_long:ty) => { + /// Replaces self with Quotient and returns Remainder + fn $name(&mut self, rhs: &$t_divisor) -> $t_divisor { + debug_assert!((<$t_long>::MAX >> 32) as u128 >= <$t_divisor>::MAX as u128); + + let divisor = *rhs as $t_long; + let remainder = self.0.iter_mut().fold(0 as $t_long,|carry, current| { + debug_assert_eq!(carry, carry & (<$t_divisor>::MAX as $t_long)); //carry has to be lower than divisor, and divisor is $t_divisor. + let carry_shifted = carry << 32; + let dividend = (carry_shifted) | (*current as $t_long); + let remainder = dividend % divisor; + let ratio = dividend / divisor; + debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + *current = (ratio) as u32; + remainder + }); + debug_assert_eq!(remainder, remainder & (<$t_divisor>::MAX as $t_long)); + remainder as $t_divisor + } + }; +} + +impl ArbitraryBytes{ + pub(super) fn new(data : [u32;N]) -> Self { + ArbitraryBytes(data) + } + + #[cfg(target_pointer_width = "64")] + make_div_assign_with_remainder!(div_assign_with_remainder_usize, usize, u128); + + #[cfg(not(target_pointer_width = "64"))] + make_div_assign_with_remainder!(div_assign_with_remainder_usize, usize, u64); + + make_div_assign_with_remainder!(div_assign_with_remainder_u32, u32, u64); + + fn rem_assign_with_quotient_u32(&mut self, divisor: &u32) -> Self where Self : for<'a> From<&'a u32> { + let remainder = self.div_assign_with_remainder_u32(divisor); + std::mem::replace(self, Self::from(&remainder)) + } + + //This is Knuth, The Art of Computer Programming Volume 2, Section 4.3, Algorithm D. + fn rem_assign_with_quotient_knuth(&mut self, divisor : &Self) -> Self + where Self : PadWithAZero> + + for<'a> From<&'a usize> + { + debug_assert!(M == N+1); + //first we need to find n (number of digits in divisor) + let n_digits_divisor= N - divisor.find_first_nonzero_digit(); + debug_assert!(n_digits_divisor > 1); + //and same in the non-normalized dividend + let m_plus_n_digits_dividend = N - self.find_first_nonzero_digit(); + let m_extra_digits_dividend = m_plus_n_digits_dividend - n_digits_divisor; + + //step D1: Normalize. This brings the maximum error for each digit down to no more than 2. + let normalize_shift = divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros() as usize; + //again, missing const generics ruin all the fun. + let mut dividend = self.shift_left(normalize_shift); + let divisor = divisor.shift_left(normalize_shift); + debug_assert_eq!(divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros(),0); + + let mut quotient : Self = (&0_usize).into(); + + //needed for Step D3, but is the same for all iterations -> factored out. + let guess_divisor = divisor.get_digit_from_right(n_digits_divisor - 1) as u64; + let divisor_second_significant_digit = divisor.get_digit_from_right(n_digits_divisor-2) as u64; + + //step D2, D7: the loop. + for j in (0..=m_extra_digits_dividend).rev() { + //Step D3: Guess a digit + let guess_dividend = u64_from_u32s(dividend.get_digit_from_right(j+n_digits_divisor), dividend.get_digit_from_right(j + n_digits_divisor - 1)); + let mut guesstimate = guess_dividend/guess_divisor; + let mut guess_reminder = guess_dividend % guess_divisor; + //refine our guesstimate (still step D3). Ensures that error of guesstimate is either 0 or +1. + while guess_reminder <= u32::MAX as u64 + && (guesstimate > u32::MAX as u64 + || divisor_second_significant_digit * guesstimate + > (guess_reminder << 32) | (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64) + ) { + guesstimate -= 1; + guess_reminder += guess_divisor; + } + //Step D4: Pretend the guess was correct and subtract guesstimate * divisor from dividend. + debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate, "The while above should have made guesstimate a one-digit number. Debug!"); + let mut guesstimate = guesstimate as u32; + let s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type."); + let s_range = (M - 1 - n_digits_divisor)..M; + let d_range = (s_range.start - j)..(s_range.end - j); + let did_overflow = slice_overflowing_sub_assign(&mut dividend.0[d_range.clone()], &s.0[s_range.clone()]); + //Step D5: If guesstimate was incorrect, the subtraction has overflown. The result is wrapped in such a case. + if did_overflow { + //Step D6: We have to correct our guesstimate. It was too large by one. We also have to fix the overflow that has occured. + guesstimate -= 1; + //The addition must overflow again. The two overflows cancel out, and since we are using wrapping arithmetics, the result becomes correct again. + let did_overflow = slice_overflowing_add_assign(&mut dividend.0[d_range.clone()], &divisor.0[s_range.clone()]); + debug_assert!(did_overflow, "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.") + } + quotient.set_digit_from_right(guesstimate, j); + } + + //Steop D8: Compute Remainder. + self.0 = dividend.shift_right(normalize_shift).0[1..].try_into() + .expect("Conversion of what should have been an N-element slice into an N-element array failed."); + quotient + + } + + fn find_first_nonzero_digit(&self) -> usize{ + self.0.iter().enumerate().skip_while(|(_,v)| **v == 0).next().map(|(x,_)| x).unwrap_or(N) + } + + fn get_digit_from_right(&self, i : usize) -> u32{ + self.0[N-i-1] + } + fn set_digit_from_right(&mut self, val: u32, i : usize){ + self.0[N-i-1] = val; + } + + fn shift_left(&self, s : usize) -> ::Output + where Self : PadWithAZero> + { + debug_assert!(s < 32); + let mut res = self.pad_with_a_zero(); + if s != 0{ + res.0.iter_mut().zip(self.0.iter().chain(once(&0))).for_each(|(current, next)| *current = (*current << s) | (*next >> (32-s))); + } + res + } + + fn shift_right(mut self, s : usize) -> Self { + debug_assert!(s < 32); + if s != 0 { + let _ = self.0.iter_mut().fold(0u32, |carry, val| { + let c = *val << (32-s); + *val >>= s; + debug_assert!(*val & carry == 0); + *val |= carry; + c + }); + } + self + } +} + +fn slice_overflowing_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ + debug_assert_eq!(lhs.len(), rhs.len()); + lhs.iter_mut().zip(rhs.iter()).rev().fold(false,|carry,(a,b)| { + let r = b.overflowing_add(carry as u32); + let s = a.overflowing_sub(r.0); + *a = s.0; + r.1 || s.1 + }) +} + +fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool { + debug_assert_eq!(lhs.len(), rhs.len()); + lhs.iter_mut().zip(rhs.iter()).rev().fold(false, |carry, (a, b)| { + let r = b.overflowing_add(carry as u32); + let s = a.overflowing_add(r.0); + *a = s.0; + r.1 || s.1 + }) +} + +fn u64_from_u32s(msb : u32, lsb : u32) -> u64{ + let msb = msb as u64; + let lsb = lsb as u64; + (msb << 32) | lsb +} + +#[cfg(test)] +mod arbitrary_bytes_tests{ + use super::*; + use rand::RngCore; + use rand_xoshiro::rand_core::SeedableRng; + use rand_xoshiro::Xoshiro256Plus; + + /// Tests specifically the case that will_overflow is true. + #[test] + fn knuth_add_back_test(){ + let mut dividend = ArbitraryBytes::new([ + //m = 3, n=5 + u32::MAX, + u32::MAX, + u32::MAX-1, + u32::MAX, + u32::MAX, + 0, + 0, + 3 + ]); + let divisor = ArbitraryBytes::new([ + 0, + 0, + 0, + 0, + 0, + u32::MAX, + u32::MAX, + u32::MAX, + ]); + let result = dividend.rem_assign_with_quotient(&divisor); + assert_eq!(dividend.0, [0,0,0,0,0,0,0,2]); + assert_eq!(result.0, [0,0,0,u32::MAX,u32::MAX, u32::MAX, u32::MAX, u32::MAX]); + } + + + fn prepare_many_numbers(max_dividend_digits : u32, min_dividend_digits : u32, max_divisor_digits : u32, min_divisor_digits : u32) -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ + assert!(max_dividend_digits < 5); + assert!(min_dividend_digits <= max_dividend_digits); + assert!(max_divisor_digits < 5); + assert!(min_divisor_digits <= max_divisor_digits); + let mut rng = Xoshiro256Plus::seed_from_u64(0); + let mut res = Vec::new(); + for _i in 0..1000000 { + let dx = rng.next_u32() % (max_dividend_digits + 1 - min_dividend_digits) + min_dividend_digits; + let dy = rng.next_u32() % (max_divisor_digits + 1 - min_divisor_digits) + min_divisor_digits; + let ds = dx.min(dy); + let dl = dx.max(dy); + let dividendx = [ + 0, + if dl >= 4 { rng.next_u32() } else { 0 }, + if dl >= 3 { rng.next_u32() } else { 0 }, + if dl >= 2 { rng.next_u32() } else { 0 }, + if dl >= 1 { rng.next_u32() } else { 0 }, + ]; + let divisorx = [ + 0, + if ds >= 4 { rng.next_u32() } else { 0 }, + if ds >= 3 { rng.next_u32() } else { 0 }, + if ds >= 2 { rng.next_u32() } else { 0 }, + if ds >= 1 { rng.next_u32() } else { 0 }, + ]; + let needs_swap = ds == dl && dividendx[5-ds as usize] < divisorx[5-ds as usize]; + let dividend = ArbitraryBytes::new(if needs_swap {divisorx} else {dividendx}); + let divisor = ArbitraryBytes::new(if needs_swap {dividendx} else {divisorx}); + assert!(dividend.ge(&divisor)); + + let td = + ((dividend.0[1] as u128)<<96) + + ((dividend.0[2] as u128)<<64) + + ((dividend.0[3] as u128)<<32) + + (dividend.0[4] as u128); + let tn = + ((divisor.0[1] as u128)<<96) + + ((divisor.0[2] as u128)<<64) + + ((divisor.0[3] as u128)<<32) + + (divisor.0[4] as u128); + + + res.push((dividend, divisor, td/tn, td%tn)); + } + res + } + + /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.) + #[test] + fn rem_assign_with_quotient_knuth_many_numbers_test() { + let input = prepare_many_numbers(4,2, 4, 2); + for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { + let quotient = dividend.rem_assign_with_quotient_knuth(&divisor); + let remainder = dividend; + let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); + let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); + assert_eq!(quotient, expected_quotient); + assert_eq!(remainder, expexted_remainder); + } + } + /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.) + #[test] + fn rem_assign_with_quotient_many_numbers_test() { + let input = prepare_many_numbers(4,1, 4, 1); + for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { + let quotient = dividend.rem_assign_with_quotient(&divisor); + let remainder = dividend; + let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); + let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); + assert_eq!(quotient, expected_quotient); + assert_eq!(remainder, expexted_remainder); + } + } + + #[test] + fn rem_assign_with_quotient_u32_many_numbers_test() { + let input = prepare_many_numbers(4,1, 1, 1); + for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { + let quotient = dividend.rem_assign_with_quotient_u32(&divisor.0.last().unwrap()); + let remainder = dividend; + let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); + let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); + assert_eq!(quotient, expected_quotient); + assert_eq!(remainder, expexted_remainder); + } + } + + #[test] + fn rem_assign_with_quotient_u32_test(){ + let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let quotient = a.rem_assign_with_quotient_u32(&0x12345); + assert_eq!(quotient.0, [0x9A10,0xB282B7BA,0xE4948E98,0x2AE63D74,0xE6FDFF4A]); + assert_eq!(a.0, [0,0,0,0,0x6882]); + } + + #[test] + fn rem_assign_with_quotient_u32_test2(){ + let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]); + let quotient = a.rem_assign_with_quotient_u32(&0x12345); + assert_eq!(quotient.0, [0,0,0,0,0]); + assert_eq!(a.0, [0,0,0,0,0x1234]); + } + + #[test] + fn div_assign_with_remainder_usize_test(){ + let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let remainder = a.div_assign_with_remainder_usize(&0x1234_usize); + assert_eq!(a.0, [0x9A135,0x79AA8650,0xD251DC7A,0x9AA8C1F2,0x8B9729EF]); + assert_eq!(remainder, 0x2E8); + } + + #[test] + fn div_assign_with_remainder_usize_test2(){ + let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]); + let remainder = a.div_assign_with_remainder_usize(&0x1235_usize); + assert_eq!(a.0, [0,0,0,0,0]); + assert_eq!(remainder, 0x1234); + } + + #[cfg(target_pointer_width = "64")] + #[test] + fn div_assign_with_remainder_usize_test3(){ + let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let remainder = a.div_assign_with_remainder_usize(&0x123456789ab_usize); + assert_eq!(a.0, [0,0x9A107B,0xBEC8B35A,0xEC9D3B43,0x056F803A]); + assert_eq!(remainder, 0xD7537A4B6); + } + + #[test] + fn sub_assign_test() { + let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let b = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let carry = slice_overflowing_sub_assign(&mut a.0,&b.0); + assert!(!carry); + assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]); + } + + #[test] + fn sub_assign_test2() { + let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let carry = slice_overflowing_sub_assign(&mut a.0,&b.0); + assert!(carry); + assert_eq!(a.0, [0x935D3D98,0x4BEB08CB,0x4CF2240D,0xCA49E363,0xB0268A9E]); + } + + #[test] + fn add_assign_test() { + let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let carry = slice_overflowing_add_assign(&mut a.0,&b.0); + assert!(!carry); + assert_eq!(a.0, [0xF1F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]); + } + #[test] + fn add_assign_test2() { + let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = ArbitraryBytes::new([0xbf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let carry = slice_overflowing_add_assign(&mut a.0,&b.0); + assert!(carry); + assert_eq!(a.0, [0x01F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]); + } + + #[test] + fn shift_left_test() { + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = a.shift_left(7); + assert_eq!(b.0,[0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]); + } + + #[test] + fn shift_right_test() { + let a = ArbitraryBytes::new([0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]); + let b = a.shift_right(7); + assert_eq!(b.0,[0, 0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + } + + #[test] + fn get_digit_from_right_test(){ + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + assert_eq!(a.get_digit_from_right(3), 0xffffffff); + } + + #[test] + fn set_digit_from_right_test(){ + let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + a.set_digit_from_right(0xdeadbeef, 4); + assert_eq!(a.0[0], 0xdeadbeef); + } + + #[test] + fn find_first_nonzero_digit_test() { + let a = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]); + assert_eq!(a.find_first_nonzero_digit(),3); + } + + #[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()) + } + + #[test] + fn mul_with_u32_test(){ + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = 3u32; + let product = a*b; + assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036]) + } + #[test] + fn mul_with_u32_test2(){ + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = 4u32; + let product = a*b; + assert!(product.is_none()) + } + #[test] + fn mul_with_usize_test_working(){ + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = 3usize; + let product = a*b; + assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036]) + } + #[test] + fn mul_with_usize_test_overflow(){ + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = 4usize; + let product = a*b; + assert!(product.is_none()) + } + #[cfg(target_pointer_width = "64")] + #[test] + fn mul_with_usize_test_64bit_works(){ + let a = ArbitraryBytes::new([0,0,0xc7138bd5,0x12345678,0xabcde012]); + let b = 0x123456789ausize; + let product = a*b; + assert_eq!(product.unwrap().0, [0xE,0x28130BBC,0x7442D257,0x1FEDDF10,0xC8ED3AD4]) + } + #[cfg(target_pointer_width = "64")] + #[test] + fn mul_with_usize_test_64bit_overflow(){ + let a = ArbitraryBytes::new([0,0x1,0xc7138bd5,0x12345678,0xabcde012]); + let b = usize::MAX; + let product = a*b; + assert!(product.is_none()) + } + #[test] + fn try_into_u32_test(){ + let a = ArbitraryBytes::new([0,0,0,0,0xabcde012]); + let b : u32 = (&a).try_into().unwrap(); + assert_eq!(b, 0xabcde012); + } + #[test] + fn try_into_u32_test_overflows(){ + let a = ArbitraryBytes::new([0,0,0,0x1,0xabcde012]); + let b : Result = (&a).try_into(); + assert!(b.is_err()) + } + #[test] + fn try_into_usize_test(){ + let a = ArbitraryBytes::new([0,0,0,0,0xe012]); + let b : usize = (&a).try_into().unwrap(); + assert_eq!(b, 0xe012); + } + #[test] + fn try_into_usize_test_overflows(){ + let a = ArbitraryBytes::new([0,0,0x1,0,0xabcde012]); + let b : Result = (&a).try_into(); + assert!(b.is_err()) + } + #[cfg(target_pointer_width = "64")] + #[test] + fn try_into_usize_test_on_64_bits(){ + let a = ArbitraryBytes::new([0,0,0,0x54a,0xabcde012]); + let b : usize= (&a).try_into().unwrap(); + assert_eq!(b, 0x54aabcde012); + } + #[cfg(target_pointer_width = "32")] + #[test] + fn try_into_usize_test_on_64_bits(){ + let a = ArbitraryBytes::new([0,0,0,0x54a,0xabcde012]); + let b : Result = (&a).try_into(); + assert!(b.is_err()) + } + #[test] + fn pad_with_a_zero_5(){ + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = a.pad_with_a_zero(); + assert_eq!(*b.0.first().unwrap(),0); + assert_eq!(b.0[1..], a.0); + } + #[test] + fn pad_with_a_zero_8(){ + let a = ArbitraryBytes::new([0x4631abcd,0x35a40be4,0x074c4d0a,0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = a.pad_with_a_zero(); + assert_eq!(*b.0.first().unwrap(),0); + assert_eq!(b.0[1..], a.0); + } + #[cfg(target_pointer_width = "64")] + #[test] + fn from_usize_5_large(){ + let a : ArbitraryBytes<5> = (&0x7246abcd705aef_usize).into(); + assert_eq!(a.0[4], 0xcd705aef); + assert_eq!(a.0[3], 0x007246ab); + assert!(a.0[..3].iter().all(|x| *x==0)); + } + #[test] + fn from_usize_5(){ + let a : ArbitraryBytes<5> = (&0xcd705aef_usize).into(); + assert_eq!(a.0[4], 0xcd705aef); + assert!(a.0[..4].iter().all(|x| *x==0)); + } + #[cfg(target_pointer_width = "64")] + #[test] + fn from_usize_8_large(){ + let a : ArbitraryBytes<8> = (&0x7246abcd705aef_usize).into(); + assert_eq!(a.0[7], 0xcd705aef); + assert_eq!(a.0[6], 0x007246ab); + assert!(a.0[..6].iter().all(|x| *x==0)); + } + #[test] + fn from_usize_8(){ + let a : ArbitraryBytes<8> = (&0xcd705aef_usize).into(); + assert_eq!(a.0[7], 0xcd705aef); + assert!(a.0[..7].iter().all(|x| *x==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 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 for ArbitraryBytes<5>{ + fn lookup(base : &usize) -> Option<(Self, usize)> { + get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_5) + } +} +impl ConstantMaxPotencyCache for ArbitraryBytes<8>{ + fn lookup(base : &usize) -> Option<(Self, usize)> { + get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_8) + } +} + +fn get_from_cache(base : &usize, cache : &[([u32;N], usize)]) -> Option<(ArbitraryBytes, 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(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(x : &ArbitraryBytes) -> ArbitraryBytes{ArbitraryBytes(x.0)} + +pub(crate) const fn gen_const_max_potency_cache() -> [([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::,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::,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 BaseConversion for T where T : ToArbitraryBytes>, - for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero>, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero> + ConstantMaxPotencyCache, { type Output = IterativeBaseConversion, usize>; fn convert_to_base(self, base : usize) -> Self::Output { -- cgit v1.2.3 From 53fff5d2f7fc007476e4c4850bd4f974f488b13e Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sun, 23 Oct 2022 15:22:20 +0200 Subject: Rename "potency" to "power", the English term. It seems English doesn't use the word potency in this context, but rather uses power. --- .../base_conversion/iterative_conversion.rs | 32 +++++------ .../iterative_conversion_impl/mod.rs | 4 +- .../precomputed_constants.rs | 62 +++++++++++----------- src/passwordmaker/base_conversion/mod.rs | 4 +- 4 files changed, 51 insertions(+), 51 deletions(-) (limited to 'src/passwordmaker/base_conversion/mod.rs') diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index f5db0f7..e88f379 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -14,34 +14,34 @@ use std::iter::successors; pub(crate) struct IterativeBaseConversion{ current_value : V, - current_base_potency : V, + current_base_power : V, remaining_digits : usize, base : B, } impl IterativeBaseConversion where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. - ConstantMaxPotencyCache, - for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_potency. + ConstantMaxPowerCache, + for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_power. Mul<&'a V, Output = Option> { pub(super) fn new(value : V, base : B) -> Self{ - let PotencyAndExponent{power : current_base_potency, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base); + let PowerAndExponent{power : current_base_power, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base); Self{ current_value : value, - current_base_potency, + current_base_power, 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_power(base : &B) -> PotencyAndExponent { - V::lookup(base).map(|(potency,count)| PotencyAndExponent{ power: potency, exponent: count }) + fn find_highest_fitting_power(base : &B) -> PowerAndExponent { + V::lookup(base).map(|(power,count)| PowerAndExponent{ power, 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 { + pub(super) fn find_highest_fitting_power_non_cached(base : &B) -> PowerAndExponent { let base_v = base.into(); let exp_result = successors(Some((base_v, 1)), |(p, e)| { @@ -49,15 +49,15 @@ impl IterativeBaseConversion }).last(); - let result = successors(exp_result, |(potency, count)| (potency * base).map(|v| (v, count + 1))) + let result = successors(exp_result, |(power, count)| (power * base).map(|v| (v, count + 1))) .last() .expect("Cannot fail, first entry is Some (required V : From) and there's no filtering."); - PotencyAndExponent{ power : result.0, exponent : result.1 } + PowerAndExponent{ power : result.0, exponent : result.1 } } } impl std::iter::Iterator for IterativeBaseConversion - where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency + where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_power RemAssignWithQuotient+ //used to get the result of each step. TryInto //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. { @@ -67,9 +67,9 @@ impl std::iter::Iterator for IterativeBaseConversion if self.remaining_digits == 0 { None } else { - let result = self.current_value.rem_assign_with_quotient(&self.current_base_potency); + let result = self.current_value.rem_assign_with_quotient(&self.current_base_power); - self.current_base_potency /= &self.base; + self.current_base_power /= &self.base; self.remaining_digits = self.remaining_digits - 1; //this cannot ever yield None. @@ -86,7 +86,7 @@ impl std::iter::ExactSizeIterator for IterativeBaseConversion where IterativeBaseConversion : Iterator {} -pub(super) struct PotencyAndExponent{ +pub(super) struct PowerAndExponent{ pub(super) power : V, pub(super) exponent : usize, } @@ -96,7 +96,7 @@ pub(crate) trait RemAssignWithQuotient{ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; } -pub(crate) trait ConstantMaxPotencyCache where Self : Sized{ +pub(crate) trait ConstantMaxPowerCache where Self : Sized{ fn lookup(_base : &B) -> Option<(Self, usize)> { None } } @@ -150,7 +150,7 @@ mod iterative_conversion_tests{ } } - impl ConstantMaxPotencyCache for MyU128{} + impl ConstantMaxPowerCache 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 7ab9171..ae4aeca 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -13,7 +13,7 @@ use std::fmt::Display; use std::error::Error; use std::iter::once; -use super::iterative_conversion::{RemAssignWithQuotient, ConstantMaxPotencyCache}; +use super::iterative_conversion::{RemAssignWithQuotient, ConstantMaxPowerCache}; //Type to be used as V, with usize as B. pub(crate) struct SixteenBytes(u128); @@ -68,7 +68,7 @@ impl Mul<&SixteenBytes> for &SixteenBytes{ } } -impl ConstantMaxPotencyCache for SixteenBytes{} +impl ConstantMaxPowerCache for SixteenBytes{} //-------------------------------------------------------------------------------------------------------------------------------------- //and now the hard part: The same for [u32;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 index c5a1809..86b8c56 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs @@ -1,15 +1,15 @@ use super::const_mul_usize; use super::ArbitraryBytes; -use super::super::iterative_conversion::ConstantMaxPotencyCache; +use super::super::iterative_conversion::ConstantMaxPowerCache; -impl ConstantMaxPotencyCache for ArbitraryBytes<5>{ +impl ConstantMaxPowerCache for ArbitraryBytes<5>{ fn lookup(base : &usize) -> Option<(Self, usize)> { - get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_5) + get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_5) } } -impl ConstantMaxPotencyCache for ArbitraryBytes<8>{ +impl ConstantMaxPowerCache for ArbitraryBytes<8>{ fn lookup(base : &usize) -> Option<(Self, usize)> { - get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_8) + get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_8) } } @@ -18,12 +18,12 @@ fn get_from_cache(base : &usize, cache : &[([u32;N], usize)]) - .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(); +const CONSTANT_MAX_POWER_CACHE_5 : [([u32;5],usize);128] = gen_const_max_power_cache(); +const CONSTANT_MAX_POWER_CACHE_8 : [([u32;8],usize);128] = gen_const_max_power_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. +/// This version of find_highest_fitting_power 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(base : usize) -> ([u32;N],usize){ let start = super::from_usize(&base); @@ -38,7 +38,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_potency_cache() -> [([u32;N],usize);CNT]{ +pub(crate) const fn gen_const_max_power_cache() -> [([u32;N],usize);CNT]{ let mut result = [([0u32;N],0usize);CNT]; let mut i = 0usize; loop { @@ -57,69 +57,69 @@ mod iterative_conversion_constants_tests{ #[test] fn test_overlows_8() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, _exponent) in entries { - assert!((potency * base).is_none()) + for (base, power, _exponent) in entries { + assert!((power * base).is_none()) } } #[test] fn test_overlows_5() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, _exponent) in entries { - assert!((potency * base).is_none()) + for (base, power, _exponent) in entries { + assert!((power * base).is_none()) } } #[test] fn test_exponent_8() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, mut potency, exponent) in entries { + for (base, mut power, 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); + let remainder = power.div_assign_with_remainder_usize(&base); assert_eq!(remainder, 0); } - assert_eq!(potency, (&1usize).into()); + assert_eq!(power, (&1usize).into()); } } #[test] fn test_exponent_5() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, mut potency, exponent) in entries { + for (base, mut power, 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); + let remainder = power.div_assign_with_remainder_usize(&base); assert_eq!(remainder, 0); } - assert_eq!(potency, (&1usize).into()); + assert_eq!(power, (&1usize).into()); } } #[test] - fn highest_fitting_potency_consistency_5(){ + fn highest_fitting_power_consistency_5(){ use super::super::super::iterative_conversion::IterativeBaseConversion; - let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, exponent) in entries { + for (base, power, exponent) in entries { let non_cached_result = IterativeBaseConversion::,usize>::find_highest_fitting_power_non_cached(&base); assert_eq!(non_cached_result.exponent,exponent); - assert_eq!(non_cached_result.power, potency); + assert_eq!(non_cached_result.power, power); } } #[test] - fn highest_fitting_potency_consistency_8(){ + fn highest_fitting_power_consistency_8(){ use super::super::super::iterative_conversion::IterativeBaseConversion; - let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, exponent) in entries { + for (base, power, exponent) in entries { let non_cached_result = IterativeBaseConversion::,usize>::find_highest_fitting_power_non_cached(&base); assert_eq!(non_cached_result.exponent,exponent); - assert_eq!(non_cached_result.power, potency); + assert_eq!(non_cached_result.power, power); } } } \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index bb3fbd6..311f7c5 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::ConstantMaxPotencyCache; +use self::iterative_conversion::ConstantMaxPowerCache; 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> + ConstantMaxPotencyCache, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero> + ConstantMaxPowerCache, { type Output = IterativeBaseConversion, usize>; fn convert_to_base(self, base : usize) -> Self::Output { -- cgit v1.2.3 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. --- Cargo.toml | 5 ++ src/lib.rs | 14 +++++ .../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 +- tests/password_generation.rs | 19 ++++++ 8 files changed, 130 insertions(+), 12 deletions(-) create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs (limited to 'src/passwordmaker/base_conversion/mod.rs') diff --git a/Cargo.toml b/Cargo.toml index 24363ab..46e3713 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -11,6 +11,11 @@ license = "LGPL-3.0-or-later" keywords = ["password", "crypto", "password-generator", "security"] categories = ["cryptography"] +[features] +default = ["precomputed_common_max_powers"] +precomputed_max_powers = ["precomputed_common_max_powers"] +precomputed_common_max_powers = [] + [dependencies] unicode-segmentation = "1.10.0" diff --git a/src/lib.rs b/src/lib.rs index 2548c46..955daf8 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -18,6 +18,20 @@ //! [`PasswordMaker`] is the main part of this crate. You give it settings similar to those of a PasswordMaker Pro profile, //! and it gives you a password that's hopfully the same you'd get from PasswordMaker Pro for the same input. //! +//! # Features +//! The library comes with a set of precomputed powers to (slightly) speed up computation in common use cases. By default, constants +//! for the lengths of the pre-defined character sets of PasswordMaker Pro are included (10, 16, 32, 52, 62, 94), amounting to a total +//! of 360 bytes on a 32bit machine, and 408 bytes on a 64bit machine (and some instructions to read them). For all other character +//! set lengths the values are computed at runtime when needed. Those values are in the (default-enabled) +//! `precomputed_common_max_powers` feature. +//! +//! If you prefer simpler code and want to save a couple of bytes in the binary, you can disable `default-features` to use runtime +//! computation for all values, at the cost of a slight performance impact. +//! +//! On the other hand, if binary size is not of concern, you might want to enable the `precomputed_max_powers` feature. +//! This feature enables precomputed powers for all bases in the range 2..130. It therefore needs 7680 bytes on a 32bit machine, and +//! 8704 bytes on a 64bit machine (plus some extra instructions). +//! //! # Warning //! This library has NOT been tested on 16bit machines. It might work, but probably does not. 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 { diff --git a/tests/password_generation.rs b/tests/password_generation.rs index e559ea5..41874fa 100644 --- a/tests/password_generation.rs +++ b/tests/password_generation.rs @@ -421,4 +421,23 @@ fn test_suffix_with_insufficient_length_with_post_leet(){ ".0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789öä@€Whatever".to_owned(), "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789".to_owned()).unwrap(); assert_eq!(result, "suffi"); +} + +/// This test exists primarily to test base conversion manual max power search. If certain features are enabled, some values are hard-coded for shorter charsets. +#[test] +fn test_very_large_character_set(){ + let pwm = Pwm::new( + HashAlgorithm::Md5, + passwordmaker_rs::UseLeetWhenGenerating::NotAtAll, + r#"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!§$%&/()=?`+*~#'öäüÖÄÜ-_.:,;|<>@€[]}{¬½¼³²¹¡⅛£¤⅜⅝⅞™±°¿˛¯˘—÷×″^°ſ¶®ŧŦ←¥↓↑→ıøØþÞæÆſẞðÐđªŋŊħĦĸłŁ¢©„‚“‘”’µº"#, + "max_mustermann", + "modification", + 64, + "pre", + "suf" + ).unwrap(); + let result = pwm.generate( + ".0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789öä@€Whatever".to_owned(), + "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789".to_owned()).unwrap(); + assert_eq!(result, r#"preF.º„ĸsj®³5⅜±←|ö←U1Fh~`€ſµ½ẞ5öi6:¯—#öŁ#Oö—ſkª“/[§Ŋ↓½`'Bu:″¯suf"#); } \ No newline at end of file -- cgit v1.2.3 From 6ee6a65b30bdbd4956b18518009f25a0b7db0979 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Thu, 27 Oct 2022 08:56:51 +0200 Subject: Base Conv: Combine shifting and padding. Having one function that does both seems to be measurably faster, though I would have expected the compiler to inline and generate comparable assembly. Well, seems it didn't. --- .../iterative_conversion_impl/mod.rs | 81 +++++++++++++++++----- src/passwordmaker/base_conversion/mod.rs | 4 +- 2 files changed, 64 insertions(+), 21 deletions(-) (limited to 'src/passwordmaker/base_conversion/mod.rs') diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index 71fb3d7..0a03192 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -13,7 +13,6 @@ use std::ops::{DivAssign, Mul, MulAssign}; use std::convert::{TryFrom, TryInto}; use std::fmt::Display; use std::error::Error; -use std::iter::once; use super::iterative_conversion::{RemAssignWithQuotient, PrecomputedMaxPowers}; @@ -112,11 +111,16 @@ impl From<&u32> for ArbitraryBytes{ } //workaround for lack of proper const-generic support. -pub(crate) trait PadWithAZero{ +trait PadWithAZero{ type Output; fn pad_with_a_zero(&self) -> Self::Output; } +pub(crate) trait PaddedShiftLeft{ + type Output; + fn padded_shift_left(&self, shift : u32) -> Self::Output; +} + impl PadWithAZero for ArbitraryBytes<5>{ type Output = ArbitraryBytes<6>; fn pad_with_a_zero(&self) -> Self::Output { @@ -148,6 +152,49 @@ impl PadWithAZero for ArbitraryBytes<8>{ } } +impl PaddedShiftLeft for ArbitraryBytes<5>{ + type Output = ArbitraryBytes::<6>; + + fn padded_shift_left(&self, shift : u32) -> Self::Output { + debug_assert!(shift < 32); + if shift == 0 { + self.pad_with_a_zero() + } else { + ArbitraryBytes([ + self.0[0] >> (32-shift), + (self.0[0] << shift) | (self.0[1] >> (32-shift)), + (self.0[1] << shift) | (self.0[2] >> (32-shift)), + (self.0[2] << shift) | (self.0[3] >> (32-shift)), + (self.0[3] << shift) | (self.0[4] >> (32-shift)), + self.0[4] << shift + ]) + } + } +} + +impl PaddedShiftLeft for ArbitraryBytes<8>{ + type Output = ArbitraryBytes::<9>; + + fn padded_shift_left(&self, shift : u32) -> Self::Output { + debug_assert!(shift < 32); + if shift == 0 { + self.pad_with_a_zero() + } else { + ArbitraryBytes([ + self.0[0] >> (32-shift), + (self.0[0] << shift) | (self.0[1] >> (32-shift)), + (self.0[1] << shift) | (self.0[2] >> (32-shift)), + (self.0[2] << shift) | (self.0[3] >> (32-shift)), + (self.0[3] << shift) | (self.0[4] >> (32-shift)), + (self.0[4] << shift) | (self.0[5] >> (32-shift)), + (self.0[5] << shift) | (self.0[6] >> (32-shift)), + (self.0[6] << shift) | (self.0[7] >> (32-shift)), + self.0[7] << shift + ]) + } + } +} + impl DivAssign<&usize> for ArbitraryBytes{ //just do long division. fn div_assign(&mut self, rhs: &usize) { @@ -295,7 +342,7 @@ impl Mul<&ArbitraryBytes> for &ArbitraryBytes where Arbit } impl RemAssignWithQuotient for ArbitraryBytes - where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero> + where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PaddedShiftLeft> { fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self{ @@ -359,7 +406,7 @@ impl ArbitraryBytes{ //This is Knuth, The Art of Computer Programming Volume 2, Section 4.3, Algorithm D. fn rem_assign_with_quotient_knuth(&mut self, divisor : &Self) -> Self - where Self : PadWithAZero> + + where Self : PaddedShiftLeft> + for<'a> From<&'a usize> { debug_assert!(M == N+1); @@ -373,8 +420,8 @@ impl ArbitraryBytes{ //step D1: Normalize. This brings the maximum error for each digit down to no more than 2. let normalize_shift = divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros(); //again, missing const generics ruin all the fun. - let mut dividend = self.shift_left(normalize_shift); - let divisor = divisor.shift_left(normalize_shift); + let mut dividend = self.padded_shift_left(normalize_shift); + let divisor = divisor.padded_shift_left(normalize_shift); debug_assert_eq!(divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros(),0); let mut quotient : Self = (&0_usize).into(); @@ -434,17 +481,6 @@ impl ArbitraryBytes{ self.0[N-i-1] = val; } - fn shift_left(&self, s : u32) -> ::Output - where Self : PadWithAZero> - { - debug_assert!(s < 32); - let mut res = self.pad_with_a_zero(); - if s != 0{ - res.0.iter_mut().zip(self.0.iter().chain(once(&0))).for_each(|(current, next)| *current = (*current << s) | (*next >> (32-s))); - } - res - } - fn shift_right(mut self, s : u32) -> Self { debug_assert!(s < 32); if s != 0 { @@ -688,11 +724,18 @@ mod arbitrary_bytes_tests{ } #[test] - fn shift_left_test() { + fn shift_left_test_5() { let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - let b = a.shift_left(7); + let b = a.padded_shift_left(7); assert_eq!(b.0,[0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]); } + + #[test] + fn shift_left_test_8() { + let a = ArbitraryBytes::new([0x4631abcd,0x35a40be4,0x074c4d0a,0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = a.padded_shift_left(7); + assert_eq!(b.0,[0x23, 0x18D5_E69A, 0xD205_F203, 0xA626_8521, 0x53DF_817F, 0xFFFF_FFE3, 0x89C5_EA89, 0x1A2B_3C55, 0xE6F0_0900]); + } #[test] fn shift_right_test() { diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index cab838e..6640880 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -1,5 +1,5 @@ use std::convert::TryInto; -use iterative_conversion_impl::PadWithAZero; +use iterative_conversion_impl::PaddedShiftLeft; pub(super) use iterative_conversion::IterativeBaseConversion; pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes}; @@ -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> + PrecomputedMaxPowers, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PaddedShiftLeft> + PrecomputedMaxPowers, { type Output = IterativeBaseConversion, usize>; fn convert_to_base(self, base : usize) -> Self::Output { -- cgit v1.2.3 From 36b7ec5ea805196749c7f10f1d8e03ae03564f2b Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 4 Nov 2022 20:51:12 +0100 Subject: More Clippy lints. Now Clippy is happy. --- .../base_conversion/iterative_conversion_impl/mod.rs | 10 +++++----- .../iterative_conversion_impl/precomputed_constants.rs | 14 +++++++------- src/passwordmaker/base_conversion/mod.rs | 1 + src/passwordmaker/mod.rs | 18 ++++++++++++++---- 4 files changed, 27 insertions(+), 16 deletions(-) (limited to 'src/passwordmaker/base_conversion/mod.rs') diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index 3d5351a..b805272 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -476,7 +476,7 @@ impl ArbitraryBytes{ } fn find_first_nonzero_digit(&self) -> usize{ - self.0.iter().enumerate().skip_while(|(_,v)| **v == 0).next().map(|(x,_)| x).unwrap_or(N) + self.0.iter().enumerate().find(|(_,v)| **v != 0).map_or(N,|(x,_)| x) } fn get_digit_from_right(&self, i : usize) -> u32{ @@ -504,7 +504,7 @@ impl ArbitraryBytes{ fn slice_overflowing_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ debug_assert_eq!(lhs.len(), rhs.len()); lhs.iter_mut().zip(rhs.iter()).rev().fold(false,|carry,(a,b)| { - let r = b.overflowing_add(carry as u32); + let r = b.overflowing_add(u32::from(carry)); let s = a.overflowing_sub(r.0); *a = s.0; r.1 || s.1 @@ -514,7 +514,7 @@ fn slice_overflowing_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool { debug_assert_eq!(lhs.len(), rhs.len()); lhs.iter_mut().zip(rhs.iter()).rev().fold(false, |carry, (a, b)| { - let r = b.overflowing_add(carry as u32); + let r = b.overflowing_add(u32::from(carry)); let s = a.overflowing_add(r.0); *a = s.0; r.1 || s.1 @@ -522,8 +522,8 @@ fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool { } fn u64_from_u32s(m : u32, l : u32) -> u64{ - let m = m as u64; - let l = l as u64; + let m = u64::from(m); + let l = u64::from(l); (m << 32) | l } 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 e845176..1127692 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs @@ -4,17 +4,17 @@ use super::super::iterative_conversion::PrecomputedMaxPowers; impl PrecomputedMaxPowers for ArbitraryBytes<5>{ fn lookup(base : &usize) -> Option<(Self, usize)> { - get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_5) + get_from_cache(*base, &CONSTANT_MAX_POWER_CACHE_5) } } impl PrecomputedMaxPowers for ArbitraryBytes<8>{ fn lookup(base : &usize) -> Option<(Self, usize)> { - get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_8) + get_from_cache(*base, &CONSTANT_MAX_POWER_CACHE_8) } } -fn get_from_cache(base : &usize, cache : &[([u32;N], usize)]) -> Option<(ArbitraryBytes, usize)>{ +fn get_from_cache(base : usize, cache : &[([u32;N], usize)]) -> Option<(ArbitraryBytes, usize)>{ base.checked_sub(2).and_then(|idx|cache.get(idx)) .map(|c| (ArbitraryBytes(c.0), c.1)) } @@ -24,9 +24,9 @@ const CONSTANT_MAX_POWER_CACHE_8 : [([u32;8],usize);128] = gen_const_max_power_c //----------------------------------------------------------------------------------------- -/// This version of find_highest_fitting_power is not optimized. But it can run in const contexts. Only use it there, use the normal one everywhere else. +/// This version of `find_highest_fitting_power` 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(base : usize) -> ([u32;N],usize){ - let start = super::from_usize(&base); + let start = super::from_usize(base); let mut x = (start, 1); while let Some(next) = const_mul_usize(const_clone(&x.0),base) { @@ -81,7 +81,7 @@ mod iterative_conversion_constants_tests{ for (base, mut power, 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 = power.div_assign_with_remainder_usize(&base); + let remainder = power.div_assign_with_remainder_usize(base); assert_eq!(remainder, 0); } assert_eq!(power, (&1usize).into()); @@ -95,7 +95,7 @@ mod iterative_conversion_constants_tests{ for (base, mut power, 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 = power.div_assign_with_remainder_usize(&base); + let remainder = power.div_assign_with_remainder_usize(base); assert_eq!(remainder, 0); } assert_eq!(power, (&1usize).into()); diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index 6640880..6415904 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -14,6 +14,7 @@ pub(super) trait BaseConversion { fn convert_to_base(self, base : usize) -> Self::Output; } +#[allow(clippy::trait_duplication_in_bounds)] //False positive in clippy. usize != u32. impl BaseConversion for T where T : ToArbitraryBytes>, for<'a> T::Output: From<&'a usize> + From<&'a u32> + PaddedShiftLeft> + PrecomputedMaxPowers, diff --git a/src/passwordmaker/mod.rs b/src/passwordmaker/mod.rs index 61a0a95..c9ec1e3 100644 --- a/src/passwordmaker/mod.rs +++ b/src/passwordmaker/mod.rs @@ -201,15 +201,25 @@ fn combine_prefix_password_suffix<'a, T : Iterator>>(password: result } +#[allow(clippy::trivially_copy_pass_by_ref)] //signature is actually determined by Iterator::skip_while(). There's simply no choice. fn is_zero(i : &usize) -> bool { *i == 0 } +type BaseConversion16 = IterativeBaseConversion; +type BaseConversion16Modern = SkipWhilebool>; + +type BaseConversion20 = IterativeBaseConversion,usize>; +type BaseConversion20Modern = SkipWhilebool>; + +type BaseConversion32 = IterativeBaseConversion,usize>; +type BaseConversion32Modern = SkipWhilebool>; + enum GetGraphemesIteratorInner { - Modern16(SkipWhile,fn(&usize)->bool>), - Modern20(SkipWhile,usize>,fn(&usize)->bool>), - Modern32(SkipWhile,usize>,fn(&usize)->bool>), - V06(IterativeBaseConversion) + Modern16(BaseConversion16Modern), + Modern20(BaseConversion20Modern), + Modern32(BaseConversion32Modern), + V06(BaseConversion16) } struct GetGraphemesIterator<'a> { graphemes : &'a Vec>, -- cgit v1.2.3