From 61669cc48f3b460cab05b9b51f87a0cd08d51302 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Tue, 18 Oct 2022 07:55:48 +0200 Subject: Minor: Add warning that 16bit might not work --- src/lib.rs | 3 +++ 1 file changed, 3 insertions(+) diff --git a/src/lib.rs b/src/lib.rs index a005e43..2548c46 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -17,6 +17,9 @@ //! //! [`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. +//! +//! # Warning +//! This library has NOT been tested on 16bit machines. It might work, but probably does not. mod passwordmaker; -- cgit v1.2.3 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/division.rs | 32 ++ .../base_conversion/iterative_conversion.rs | 144 +++++++ .../base_conversion/iterative_conversion_impl.rs | 443 +++++++++++++++++++++ src/passwordmaker/base_conversion/mod.rs | 6 +- src/passwordmaker/base_conversion/remainders.rs | 37 +- .../base_conversion/remainders_impl.rs | 2 +- 6 files changed, 628 insertions(+), 36 deletions(-) create mode 100644 src/passwordmaker/base_conversion/division.rs create mode 100644 src/passwordmaker/base_conversion/iterative_conversion.rs create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl.rs diff --git a/src/passwordmaker/base_conversion/division.rs b/src/passwordmaker/base_conversion/division.rs new file mode 100644 index 0000000..c6fc911 --- /dev/null +++ b/src/passwordmaker/base_conversion/division.rs @@ -0,0 +1,32 @@ +/// 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 new file mode 100644 index 0000000..94d28c0 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -0,0 +1,144 @@ +//! This module aims to provide iterative computation of the base-converted result, starting at the +//! most significant digit. +//! +//! # Warning +//! This is optimized for passwordmaker-rs domain specific number ranges. If you want to use this +//! somewhere else, make sure to adapt some maths. For instance you might want to early-out for leading zeros. +//! +//! The maths is not great, sorry. It's way easier to start at the least significant digit... +//! If you have any great idea how to improve it: Make a merge request! + +use std::convert::TryInto; +use std::ops::{Mul, DivAssign}; +use std::iter::successors; + +pub(super) struct IterativeBaseConversion{ + current_value : V, + current_base_potency : V, + remaining_digits : usize, + base : B, +} + +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. +{ + pub(super) fn new(value : V, base : B) -> Self{ + let PotencyAndExponent{potency : current_base_potency, count : remaining_digits} = Self::find_highest_fitting_potency(&base); + Self{ + current_value : value, + current_base_potency, + remaining_digits, + base, + } + } + + 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() + .last() + .expect("Cannot fail, first entry is Some (required V : From) and there's no filtering."); + PotencyAndExponent{ potency : result.1, count : result.0 + 2 } + } +} + +impl std::iter::Iterator for IterativeBaseConversion + where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency + 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. +{ + type Item = B; + + fn next(&mut self) -> Option { + if self.remaining_digits == 0 { + None + } else { + let result = self.current_value.rem_assign_with_quotient(&self.current_base_potency); + + self.current_base_potency /= &self.base; + self.remaining_digits = self.remaining_digits - 1; + + //this cannot ever yield None. + result.try_into().ok() + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.remaining_digits, Some(self.remaining_digits)) + } +} + +impl std::iter::ExactSizeIterator for IterativeBaseConversion + where IterativeBaseConversion : Iterator +{} + +struct PotencyAndExponent{ + potency : V, + count : usize, +} + +pub(super) trait RemAssignWithQuotient{ + /// Replaces self with remainder of division, and returns quotient. + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; +} + +//tests general behaviour, using primitive types. +#[cfg(test)] +mod iterative_conversion_tests{ + use std::{ops::Mul, convert::{From, TryFrom}}; + + use super::*; + + #[derive(Debug,Clone)] + struct MyU128(u128); + impl Mul<&u64> for &MyU128 { + type Output = Option; + fn mul(self, rhs: &u64) -> Self::Output { + self.0.checked_mul(*rhs as u128).map(|s| MyU128(s)) + } + } + + impl RemAssignWithQuotient for MyU128{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self { + let quotient = self.0 / divisor.0; + self.0 %= divisor.0; + Self(quotient) + } + } + impl From<&u64> for MyU128{ + fn from(v: &u64) -> Self { + MyU128(v.clone() as u128) + } + } + + impl DivAssign<&u64> for MyU128{ + fn div_assign(&mut self, rhs: &u64) { + self.0 = self.0 / (*rhs as u128); + } + } + + impl TryFrom for u64{ + type Error = std::num::TryFromIntError; + + fn try_from(value: MyU128) -> Result { + value.0.try_into() + } + } + + + #[test] + fn test_simple_u128_to_hex_conversion(){ + let i = IterativeBaseConversion::new(MyU128(12345678u128), 16u64); + assert_eq!(i.len(), 32); + assert_eq!(i.skip_while(|x| *x == 0_u64).collect::>(), vec![0xB, 0xC, 0x6, 0x1, 0x4, 0xE]); + } + #[test] + fn test_simple_u128_to_base_17_conversion(){ + let i = IterativeBaseConversion::new(MyU128(1234567890123456789u128), 17u64); + 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]); + } +} \ 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 new file mode 100644 index 0000000..be1d851 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -0,0 +1,443 @@ +//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N]. + +//Reminder for myself: The traits needed are: +// where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. +// for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency +// 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. +// for<'a> &'a V : Mul<&'a B, Output = Option> //used to get the first current_base_potency. + +//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, SubAssign}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering}; + +use super::iterative_conversion::RemAssignWithQuotient; + +//Type to be used as V, with usize as B. +struct SixteenBytes(u128); + +//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) + } +} + +//-------------------------------------------------------------------------------------------------------------------------------------- +//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)] +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. +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)] +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).map(|x| *x as usize); + //second-last is not an error though. + let second_last_bit = value.0.get(N-2).map(|u| (*u as usize) << 32).unwrap_or_default(); + last_bit.map(|last_bit| last_bit + second_last_bit) + } + } + #[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)] +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).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToU32Error) + } + } +} + +impl Mul<&usize> for &ArbitraryBytes{ + type Output = Option>; + fn mul(self, rhs: &usize) -> Self::Output { + #[cfg(target_pointer_width = "64")] + type UsizeAndFour = u128; + #[cfg(not(target_pointer_width = "64"))] + type UsizeAndFour = u64; + //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. + let res = (*digit as UsizeAndFour) * (*rhs as UsizeAndFour) + 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(ArbitraryBytes(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. However, at least for now, a + //non-performing restoring version of the algorithm is used, because I'm too tired right now + //to properly implement the performing one (which would with near certainty be faster a bit). + + //well, nearly without trying to be smart. + 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 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) + } + }, + } + } +} + +/// Needed by rem_assign_with_quotient_knuth +impl Mul for ArbitraryBytes{ + type Output = Option>; + 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. + let res = (*digit as u64) * (rhs as u64) + 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) + } + } +} + +impl SubAssign<&ArbitraryBytes> for ArbitraryBytes{ + fn sub_assign(&mut self, rhs: &ArbitraryBytes) { + let carry = self.0.iter_mut().zip(rhs.0.iter()).rev().fold(0_u64,|carry,(i,s)| { + let s = (*s as u64) + carry; + if *i as u64 >= s { + *i -= s as u32; + 0 + } else { + *i = (((*i as u64) + (1_u64<<32)) - s) as u32; + 1 + } + }); + assert_eq!(carry,0); + } +} + + +impl ArbitraryBytes{ + /// 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); + + 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. + 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)); + remainder as usize + } + + /// Used in rem_assign_with_quotient_knuth. The normalization factor is u32, and u32 might be larger than usize. + 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. + 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. + *current = (ratio) as u32; + dividend - (*current as u64) * divisor + }); + assert_eq!(remainder, remainder & (u32::MAX as u64)); + remainder as u32 + } + + 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)) + } + + + fn rem_assign_with_quotient_knuth(&mut self, divisor : &Self) -> Self + where Self : PadWithAZero> + + for<'a> From<&'a usize> + { + 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); + //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 d = ((1u64 << 32) / (1u64 + (divisor.get_digit_from_right(n_digits_divisor - 1) as u64))) as u32; + //again, missing const generics ruin all the fun. + let mut dividend = (self.pad_with_a_zero() * d).expect("Normalizing dividend failed due to overflow. Mathematically impossible."); + let divisor = (divisor.pad_with_a_zero() * d).expect("Normalizing divisor failed due to overflow. Mathematically impossible."); + + let mut quotient : Self = (&0_usize).into(); + + //needed for Step D3. + 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 m_extra_digits_dividend..=0 { + //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; + let mut guess_reminder = guess_dividend % guess_divisor; + //refine this result (still step D3) + 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; + } + //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. + 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 = + 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; + 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) + } + 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); + } + + //Steop D8: Compute Remainder. + dividend.div_assign_with_remainder_u32(&d); + self.0 = dividend.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 slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){ + 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 { + *i -= s as u32; + 0 + } else { + *i = (((*i as u64) + (1_u64<<32)) - s) as u32; + 1 + } + }); + assert_eq!(carry,0); +} \ No newline at end of file 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; diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs index 93570a1..344fab2 100644 --- a/src/passwordmaker/base_conversion/remainders.rs +++ b/src/passwordmaker/base_conversion/remainders.rs @@ -1,22 +1,10 @@ -/// Adds `calc_remainders(divisor)` method to types that have some implementation of the Division trait. +use super::division::{Division, DivisionResult}; + +/// Trait used for the old base conversion. pub(super) trait CalcRemainders{ fn calc_remainders(self, divisor : D) -> Remainders; } -/// Implement `Division` to enable the `calc_remainders()` method for your type. -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 CalcRemainders for T where T:Division { @@ -52,23 +40,4 @@ impl> Iterator for Remainders{ None } } -} - -pub(super) struct DivisionResult, U> { - pub result : T, - pub remainder : U, -} - -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() - } } \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/remainders_impl.rs b/src/passwordmaker/base_conversion/remainders_impl.rs index 7de2189..c2431bb 100644 --- a/src/passwordmaker/base_conversion/remainders_impl.rs +++ b/src/passwordmaker/base_conversion/remainders_impl.rs @@ -1,4 +1,4 @@ -use super::remainders::{Division, UseGenericDivision, DivisionResult}; +use super::division::{Division, UseGenericDivision, DivisionResult}; impl UseGenericDivision for u128{} //for Md4, Md5 -- 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 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 c9345e9a24f7a8fa802c63574d88ea7a3609570b Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 19 Oct 2022 20:39:20 +0200 Subject: Add many-numbers test for long division. --- Cargo.toml | 2 + .../base_conversion/iterative_conversion_impl.rs | 73 ++++++++++++++++++++-- 2 files changed, 69 insertions(+), 6 deletions(-) diff --git a/Cargo.toml b/Cargo.toml index 7980cd5..62fd7be 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -24,6 +24,8 @@ sha-1 = "0.10.0" sha2 = "0.10.6" ripemd = "0.1.3" criterion = "0.4.0" +rand = "0.8.5" +rand_xoshiro = "0.6.0" [[bench]] name = "hashrate" diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 3dceb9b..4dc3901 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -280,7 +280,6 @@ impl RemAssignWithQuotient for ArbitraryBytes< impl Mul for ArbitraryBytes{ type Output = Option>; 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|{ 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; @@ -333,7 +332,7 @@ impl ArbitraryBytes{ 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; - dividend - (*current as UsizeAndFour) * divisor + dividend - ratio * divisor }); debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); remainder as usize @@ -342,14 +341,14 @@ impl ArbitraryBytes{ /// Used in rem_assign_with_quotient_knuth. The normalization factor is u32, and u32 might be larger than usize. 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| { + let remainder = self.0.iter_mut().fold(0_u64,|carry, current| { 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; 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 + dividend - ratio * divisor }); debug_assert_eq!(remainder, remainder & (u32::MAX as u64)); remainder as u32 @@ -407,8 +406,7 @@ impl ArbitraryBytes{ 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 = - 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; + std::cmp::PartialOrd::lt(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); if will_overflow { guesstimate -= 1; s -= &divisor; @@ -455,7 +453,11 @@ fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){ #[cfg(test)] mod iterative_conversion_impl_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([ @@ -483,4 +485,63 @@ mod iterative_conversion_impl_tests{ 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() -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ + let mut rng = Xoshiro256Plus::seed_from_u64(0); + let mut res = Vec::new(); + for _i in 0..1000000 { + let dx = rng.next_u32() % 3 + 2; //at least 2 digits, at max 4 (u128) + let dy = rng.next_u32() % 3 + 2; + 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}, + rng.next_u32(), + rng.next_u32(), + ]; + let divisorx = [ + 0, + if ds == 4 { rng.next_u32() } else { 0 }, + if ds >=3 { rng.next_u32() } else {0}, + rng.next_u32(), + rng.next_u32(), + ]; + 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 knuth_many_numbers_test() { + let input = prepare_many_numbers(); + 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); + } + } } \ No newline at end of file -- cgit v1.2.3 From de3959ad0ad76b7fbbcb02a704ae770a7cfb5be4 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 19 Oct 2022 21:21:23 +0200 Subject: Change normalization of Knuth division to shift. That's a lot faster than division. --- .../base_conversion/iterative_conversion_impl.rs | 44 +++++++++++++++++++--- 1 file changed, 38 insertions(+), 6 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 4dc3901..4e6747b 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -373,10 +373,11 @@ impl ArbitraryBytes{ 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 d = ((1u64 << 32) / (1u64 + (divisor.get_digit_from_right(n_digits_divisor - 1) as u64))) as u32; + 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.pad_with_a_zero() * d).expect("Normalizing dividend failed due to overflow. Mathematically impossible."); - let divisor = (divisor.pad_with_a_zero() * d).expect("Normalizing divisor failed due to overflow. Mathematically impossible."); + 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(); @@ -417,8 +418,8 @@ impl ArbitraryBytes{ } //Steop D8: Compute Remainder. - dividend.div_assign_with_remainder_u32(&d); - self.0 = dividend.0[1..].try_into().expect("Conversion of what should have been an N-element slice into an N-element array failed."); + 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 } @@ -433,6 +434,37 @@ impl ArbitraryBytes{ 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{ + let _ = res.0.iter_mut().rev().fold(0u32,|carry, val| { + let c = *val >> (32 - s); + *val <<= s; + debug_assert!(*val & carry == 0); + *val += carry; + c + }); + } + 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_sub_assign(lhs : &mut [u32], rhs: &[u32]){ @@ -490,7 +522,7 @@ mod iterative_conversion_impl_tests{ fn prepare_many_numbers() -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ let mut rng = Xoshiro256Plus::seed_from_u64(0); let mut res = Vec::new(); - for _i in 0..1000000 { + for _i in 0..10000000 { let dx = rng.next_u32() % 3 + 2; //at least 2 digits, at max 4 (u128) let dy = rng.next_u32() % 3 + 2; let ds = dx.min(dy); -- cgit v1.2.3 From be766f81b6985b9df3da39d78fb19ec4383075c7 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Thu, 20 Oct 2022 20:17:03 +0200 Subject: Minor: Shift Operation optimization. --- .../base_conversion/iterative_conversion_impl.rs | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 4e6747b..94c8b8b 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -10,7 +10,7 @@ //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, SubAssign}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering}; +use std::{ops::{DivAssign, Mul, SubAssign}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering, iter::once}; use super::iterative_conversion::RemAssignWithQuotient; @@ -441,13 +441,7 @@ impl ArbitraryBytes{ debug_assert!(s < 32); let mut res = self.pad_with_a_zero(); if s != 0{ - let _ = res.0.iter_mut().rev().fold(0u32,|carry, val| { - let c = *val >> (32 - s); - *val <<= s; - debug_assert!(*val & carry == 0); - *val += carry; - c - }); + res.0.iter_mut().zip(self.0.iter().chain(once(&0))).for_each(|(current, next)| *current = (*current << s) | (*next >> (32-s))); } res } @@ -459,7 +453,7 @@ impl ArbitraryBytes{ let c = *val << (32-s); *val >>= s; debug_assert!(*val & carry == 0); - *val += carry; + *val |= carry; c }); } @@ -522,7 +516,7 @@ mod iterative_conversion_impl_tests{ fn prepare_many_numbers() -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ let mut rng = Xoshiro256Plus::seed_from_u64(0); let mut res = Vec::new(); - for _i in 0..10000000 { + for _i in 0..1000000 { let dx = rng.next_u32() % 3 + 2; //at least 2 digits, at max 4 (u128) let dy = rng.next_u32() % 3 + 2; let ds = dx.min(dy); -- cgit v1.2.3 From 8da1c8a10dedb66a21f90957cbbb33c0e0ceece5 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Thu, 20 Oct 2022 23:28:08 +0200 Subject: Macro for single-digit-division. Just to remove code duplication. --- .../base_conversion/iterative_conversion_impl.rs | 74 +++++++++++----------- 1 file changed, 37 insertions(+), 37 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 94c8b8b..c402b20 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -310,49 +310,41 @@ impl SubAssign<&ArbitraryBytes> for ArbitraryBytes{ } } +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) } - /// 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; - 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| { - 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; - 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 - ratio * divisor - }); - debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); - remainder as usize - } - - /// Used in rem_assign_with_quotient_knuth. The normalization factor is u32, and u32 might be larger than usize. - 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_u64,|carry, current| { - 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; - 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 - ratio * divisor - }); - debug_assert_eq!(remainder, remainder & (u32::MAX as u64)); - remainder as u32 - } + #[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); @@ -570,4 +562,12 @@ mod iterative_conversion_impl_tests{ assert_eq!(remainder, expexted_remainder); } } + + #[test] + fn sub_assign_test() { + let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); + let b = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + a.sub_assign(&b); + assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]); + } } \ 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(-) 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 f4e89d21f8edb80d637cce16c00e94ff5aff6864 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 21 Oct 2022 20:24:55 +0200 Subject: Fix trait visibility. --- src/passwordmaker/base_conversion/iterative_conversion.rs | 2 +- src/passwordmaker/base_conversion/iterative_conversion_impl.rs | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index 95d9fa3..6716228 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -84,7 +84,7 @@ struct PotencyAndExponent{ count : usize, } -pub(super) trait RemAssignWithQuotient{ +pub(crate) trait RemAssignWithQuotient{ /// Replaces self with remainder of division, and returns quotient. fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; } diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 752dfa3..0c17d68 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -130,7 +130,7 @@ impl From<&u32> for ArbitraryBytes<8>{ } //workaround for lack of proper const-generic support. -pub(super) trait PadWithAZero{ +pub(crate) trait PadWithAZero{ type Output; fn pad_with_a_zero(&self) -> Self::Output; } -- cgit v1.2.3 From 85d5415445f3cc2294b9ff5055d02a658e873fdb Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sat, 22 Oct 2022 00:02:43 +0200 Subject: Code cleanup and addition of unit tests. --- .../base_conversion/iterative_conversion_impl.rs | 202 +++++++++++++-------- 1 file changed, 124 insertions(+), 78 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 0c17d68..ea67dd1 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -10,7 +10,7 @@ //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, SubAssign}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering, iter::once}; +use std::{ops::{DivAssign, Mul}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering, iter::once}; use super::iterative_conversion::RemAssignWithQuotient; @@ -202,7 +202,7 @@ impl TryFrom<&ArbitraryBytes> for usize{ let last_bit = value.0.get(N-1).ok_or(ArbitraryBytesToUsizeError).map(|x| *x as usize); //second-last is not an error though. let second_last_bit = value.0.get(N-2).map(|u| (*u as usize) << 32).unwrap_or_default(); - last_bit.map(|last_bit| last_bit + second_last_bit) + last_bit.map(|last_bit| last_bit | second_last_bit) } } #[cfg(not(target_pointer_width = "64"))] @@ -232,37 +232,47 @@ impl TryFrom<&ArbitraryBytes> for u32{ if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { Err(ArbitraryBytesToU32Error) } else { - value.0.get(N-1).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToU32Error) + 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 { - #[cfg(target_pointer_width = "64")] - type UsizeAndFour = u128; - #[cfg(not(target_pointer_width = "64"))] - type UsizeAndFour = u64; - //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|{ - 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 - }); - if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. - None - } else { - Some(ArbitraryBytes(result)) - } + (*self).clone() * (*rhs) } } 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. + ///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)|{ @@ -270,23 +280,14 @@ impl Mul<&ArbitraryBytes> for &ArbitraryBytes where Arbit 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)..]) + slice_add_assign(&mut result.0[0..(i+1)], &p.0[(N-1-i)..]) }); - carry.filter(|x| *x == 0).map(|_|()) + carry.filter(|x| !x).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> { @@ -296,11 +297,12 @@ impl RemAssignWithQuotient for ArbitraryBytes< //non-performing restoring version of the algorithm is used, because I'm too tired right now //to properly implement the performing one (which would with near certainty be faster a bit). - //well, nearly without trying to be smart. + //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 { @@ -311,40 +313,6 @@ impl RemAssignWithQuotient for ArbitraryBytes< } } -/// Needed by rem_assign_with_quotient_knuth -impl Mul for ArbitraryBytes{ - type Output = Option>; - fn mul(mut self, rhs: u32) -> Self::Output { - let carry = self.0.iter_mut().rev().fold(u64::default(), |carry, digit|{ - 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 - }); - if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. - None - } else { - Some(self) - } - } -} - -impl SubAssign<&ArbitraryBytes> for ArbitraryBytes{ - fn sub_assign(&mut self, rhs: &ArbitraryBytes) { - let carry = self.0.iter_mut().zip(rhs.0.iter()).rev().fold(0_u64,|carry,(i,s)| { - let s = (*s as u64) + carry; - if *i as u64 >= s { - *i -= s as u32; - 0 - } else { - *i = (((*i as u64) + (1_u64<<32)) - s) as u32; - 1 - } - }); - debug_assert_eq!(carry,0); - } -} - macro_rules! make_div_assign_with_remainder { ($name:ident, $t_divisor:ty, $t_long:ty) => { /// Replaces self with Quotient and returns Remainder @@ -437,7 +405,7 @@ impl ArbitraryBytes{ std::cmp::PartialOrd::lt(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); if will_overflow { guesstimate -= 1; - s -= &divisor; + slice_sub_assign(&mut s.0, &divisor.0); 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)]); @@ -488,19 +456,29 @@ impl ArbitraryBytes{ } } -fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){ +fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ 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 { + lhs.iter_mut().zip(rhs.iter()).rev().fold(false,|carry,(i,s)| { + //don't ask me why, but this branching monstrosity seems faster than checked_add(), overflowing_sub()... + let (s, overflow) = s.overflowing_add(carry as u32); + if !overflow && *i >= s { *i -= s as u32; - 0 + false } else { - *i = (((*i as u64) + (1_u64<<32)) - s) as u32; - 1 + *i = i.wrapping_sub(s as u32); + true } - }); - debug_assert_eq!(carry,0); + }) +} + +fn slice_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 = a.overflowing_add(*b); + let s = r.0.overflowing_add(carry as u32); + *a = s.0; + r.1 || s.1 + }) } #[cfg(test)] @@ -598,14 +576,82 @@ mod iterative_conversion_impl_tests{ } } + #[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 sub_assign_test() { let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]); let b = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); - a.sub_assign(&b); + let carry = slice_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_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_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_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]); -- cgit v1.2.3 From 7432260a8c001edd9721fe4a9598150d7d079bf5 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sat, 22 Oct 2022 13:16:19 +0200 Subject: Minor code cleanup. No performance impact. --- .../base_conversion/iterative_conversion_impl.rs | 65 ++++++++++++---------- 1 file changed, 37 insertions(+), 28 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index ea67dd1..7cc2509 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -10,7 +10,11 @@ //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}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering, iter::once}; +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; @@ -199,10 +203,10 @@ impl TryFrom<&ArbitraryBytes> for usize{ Err(ArbitraryBytesToUsizeError) } else { //failing to get last_bit is an actual error. - let last_bit = value.0.get(N-1).ok_or(ArbitraryBytesToUsizeError).map(|x| *x as usize); + 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).map(|u| (*u as usize) << 32).unwrap_or_default(); - last_bit.map(|last_bit| last_bit | second_last_bit) + 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"))] @@ -376,39 +380,43 @@ impl ArbitraryBytes{ let mut quotient : Self = (&0_usize).into(); - //needed for Step D3. + //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 = ((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 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 this result (still step D3) + //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) + > (guess_reminder << 32) | (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64) ) { guesstimate -= 1; guess_reminder += guess_divisor; } - //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. - debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate); //Knuth says this is a one-place number, and I trust him. + //The (performing) version of this from the book requires more brain-power to understand than a non-performing implementation. + //Since the probability of guesstimate still being off by one is really low (~2^(-32)), the performance impact of non-performaing vs performing + //is absolutely negligible. I'd say that readability of the code is more important than such an edge-case performance gain. + debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate, "The while above should have made guesstimate a one-digit number. Debug!"); + //Step D5: 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 = - std::cmp::PartialOrd::lt(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); + let s_range = (M - 1 - n_digits_divisor)..M; + let d_range = (s_range.start - j)..(s_range.end - j); + let will_overflow = PartialOrd::lt(÷nd.0[d_range.clone()], &s.0[s_range.clone()]); + //Step D6: if will_overflow { guesstimate -= 1; slice_sub_assign(&mut s.0, &divisor.0); - 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) + debug_assert!(!PartialOrd::lt(÷nd.0[d_range.clone()], &s.0[s_range.clone()]), "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.") } - slice_sub_assign(&mut dividend.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); + //Step D4: + slice_sub_assign(&mut dividend.0[d_range], &s.0[s_range]); quotient.set_digit_from_right(guesstimate, j); } @@ -458,29 +466,30 @@ impl ArbitraryBytes{ fn slice_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,(i,s)| { - //don't ask me why, but this branching monstrosity seems faster than checked_add(), overflowing_sub()... - let (s, overflow) = s.overflowing_add(carry as u32); - if !overflow && *i >= s { - *i -= s as u32; - false - } else { - *i = i.wrapping_sub(s as u32); - true - } + 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_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 = a.overflowing_add(*b); - let s = r.0.overflowing_add(carry as u32); + 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 iterative_conversion_impl_tests{ use super::*; -- cgit v1.2.3 From f19f726435b362bd995cac5b0f47abc581550ae4 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sat, 22 Oct 2022 13:31:38 +0200 Subject: Make n-digit division performing. The handling of overflows was non-performing before. Now it's performing and correcting. This lets us skip a less-than check for N-digit numbers, causing a slight performance improvement. --- .../base_conversion/iterative_conversion_impl.rs | 42 ++++++++++------------ 1 file changed, 18 insertions(+), 24 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index 7cc2509..e6074fa 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -284,7 +284,7 @@ impl Mul<&ArbitraryBytes> for &ArbitraryBytes where Arbit 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_add_assign(&mut result.0[0..(i+1)], &p.0[(N-1-i)..]) + slice_overflowing_add_assign(&mut result.0[0..(i+1)], &p.0[(N-1-i)..]) }); carry.filter(|x| !x).map(|_|()) }); @@ -297,10 +297,7 @@ impl RemAssignWithQuotient for ArbitraryBytes< { fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self{ - //This is based on Knuth, TAOCP vol 2 section 4.3, algorithm D. However, at least for now, a - //non-performing restoring version of the algorithm is used, because I'm too tired right now - //to properly implement the performing one (which would with near certainty be faster a bit). - + //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. @@ -358,7 +355,7 @@ impl ArbitraryBytes{ 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> @@ -399,24 +396,21 @@ impl ArbitraryBytes{ guesstimate -= 1; guess_reminder += guess_divisor; } - //The (performing) version of this from the book requires more brain-power to understand than a non-performing implementation. - //Since the probability of guesstimate still being off by one is really low (~2^(-32)), the performance impact of non-performaing vs performing - //is absolutely negligible. I'd say that readability of the code is more important than such an edge-case performance gain. + //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!"); - //Step D5: let mut guesstimate = guesstimate as u32; - let mut s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type."); + 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 will_overflow = PartialOrd::lt(÷nd.0[d_range.clone()], &s.0[s_range.clone()]); - //Step D6: - if will_overflow { + 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; - slice_sub_assign(&mut s.0, &divisor.0); - debug_assert!(!PartialOrd::lt(÷nd.0[d_range.clone()], &s.0[s_range.clone()]), "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.") + //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.") } - //Step D4: - slice_sub_assign(&mut dividend.0[d_range], &s.0[s_range]); quotient.set_digit_from_right(guesstimate, j); } @@ -464,7 +458,7 @@ impl ArbitraryBytes{ } } -fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ +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); @@ -474,7 +468,7 @@ fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{ }) } -fn slice_add_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); @@ -597,7 +591,7 @@ mod iterative_conversion_impl_tests{ 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_sub_assign(&mut a.0,&b.0); + let carry = slice_overflowing_sub_assign(&mut a.0,&b.0); assert!(!carry); assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]); } @@ -606,7 +600,7 @@ mod iterative_conversion_impl_tests{ 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_sub_assign(&mut a.0,&b.0); + let carry = slice_overflowing_sub_assign(&mut a.0,&b.0); assert!(carry); assert_eq!(a.0, [0x935D3D98,0x4BEB08CB,0x4CF2240D,0xCA49E363,0xB0268A9E]); } @@ -615,7 +609,7 @@ mod iterative_conversion_impl_tests{ 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_add_assign(&mut a.0,&b.0); + let carry = slice_overflowing_add_assign(&mut a.0,&b.0); assert!(!carry); assert_eq!(a.0, [0xF1F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]); } @@ -623,7 +617,7 @@ mod iterative_conversion_impl_tests{ 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_add_assign(&mut a.0,&b.0); + let carry = slice_overflowing_add_assign(&mut a.0,&b.0); assert!(carry); assert_eq!(a.0, [0x01F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]); } -- cgit v1.2.3 From 5af07c9df8cde3543a64b2f17f86a48825acf82a Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sat, 22 Oct 2022 15:06:53 +0200 Subject: Add more unit tests to iterative_conversion. --- .../base_conversion/iterative_conversion_impl.rs | 229 ++++++++++++++++++--- 1 file changed, 206 insertions(+), 23 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs index e6074fa..76fd32e 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -1,11 +1,6 @@ //! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N]. - -//Reminder for myself: The traits needed are: -// where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. -// for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency -// 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. -// for<'a> &'a V : Mul<&'a B, Output = Option> //used to get the first current_base_potency. +//! 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. @@ -485,7 +480,7 @@ fn u64_from_u32s(msb : u32, lsb : u32) -> u64{ } #[cfg(test)] -mod iterative_conversion_impl_tests{ +mod arbitrary_bytes_tests{ use super::*; use rand::RngCore; use rand_xoshiro::rand_core::SeedableRng; @@ -521,31 +516,35 @@ mod iterative_conversion_impl_tests{ } - fn prepare_many_numbers() -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ + 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() % 3 + 2; //at least 2 digits, at max 4 (u128) - let dy = rng.next_u32() % 3 + 2; + 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}, - rng.next_u32(), - rng.next_u32(), + 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}, - rng.next_u32(), - rng.next_u32(), + 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}); + 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 = @@ -567,8 +566,8 @@ mod iterative_conversion_impl_tests{ /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.) #[test] - fn knuth_many_numbers_test() { - let input = prepare_many_numbers(); + 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; @@ -578,6 +577,32 @@ mod iterative_conversion_impl_tests{ 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(){ @@ -587,6 +612,39 @@ mod iterative_conversion_impl_tests{ 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]); @@ -712,4 +770,129 @@ mod iterative_conversion_impl_tests{ 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 -- 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 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(-) 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 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 c43c86380e00b018d37dc9b8dbed275c7b6d264d Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Tue, 25 Oct 2022 21:27:47 +0200 Subject: Base Conv: Mul dividend instead of div divisor. As it turns out, the speed gained by lowering the number of digits in divisor using repeated division is much less than the speed gained by using multiplication of the dividend instead of division of divisor. --- .../base_conversion/iterative_conversion.rs | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index 438ef20..7d52e9b 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -17,6 +17,7 @@ pub(crate) struct IterativeBaseConversion{ current_base_power : V, remaining_digits : usize, base : B, + switch_to_multiplication : bool, //count the number of divisions. After 1, current_value is smaller than max_base_power. After 2, it's safe to mutliply current_value by base. } impl IterativeBaseConversion @@ -32,6 +33,7 @@ impl IterativeBaseConversion 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, + switch_to_multiplication: false } } @@ -59,7 +61,8 @@ impl IterativeBaseConversion impl std::iter::Iterator for IterativeBaseConversion 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. + TryInto, //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. + for<'a> &'a V : Mul<&'a B, Output = Option> { type Item = B; @@ -69,7 +72,12 @@ impl std::iter::Iterator for IterativeBaseConversion } else { let result = self.current_value.rem_assign_with_quotient(&self.current_base_power); - self.current_base_power /= &self.base; + if self.switch_to_multiplication { + self.current_value = (&self.current_value * &self.base).expect("Cannot overflow."); + } else { + self.current_base_power /= &self.base; + self.switch_to_multiplication = true; + } self.remaining_digits = self.remaining_digits - 1; //this cannot ever yield None. @@ -171,4 +179,11 @@ mod iterative_conversion_tests{ // 3YPRS4FaC1KU assert_eq!(i.skip_while(|x| *x == 0_u64).collect::>(), vec![3, 34, 25, 27, 28, 4, 15, 36, 12, 1, 20, 30]); } + #[test] + fn test_overflow_in_switch_to_multiplication(){ + //This should simply not overflow ever. + let i = IterativeBaseConversion::new(MyU128(u128::MAX), 40); + let result = i.skip_while(|x| *x == 0_u64).collect::>(); + assert_eq!(result, vec![1, 8, 14, 11, 10, 3, 37, 5, 26, 17, 14, 0, 23, 37, 35, 24, 3, 11, 27, 20, 34, 18, 12, 6, 15]); + } } \ No newline at end of file -- cgit v1.2.3 From 3ed6afab610907a29bb2b9fac0516d918bec333e Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 26 Oct 2022 17:58:30 +0200 Subject: Increment version to 0.2.0 --- Cargo.toml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Cargo.toml b/Cargo.toml index d6166e5..1f1d5c4 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "passwordmaker-rs" -version = "0.1.0" +version = "0.2.0" edition = "2018" authors = ["Andreas Grois"] rust-version = "1.52" -- cgit v1.2.3 From 839e1096dde8e1e934a82d1cf0c4d3a43dc69f38 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 26 Oct 2022 17:59:27 +0200 Subject: Use MulAssign in BaseConversion. Benchmarks show that MulAssign is quite a bit faster than Mul, especially since in this case it's mathematically proven that the multiplication cannot overflow. Also, removed skipping of leading zeros in long division. With the switch to multiplication after the first iteration, the chance that there actually are any leading zeros is on the order of 2^-26. I think at least. In any case, it's small. --- .../base_conversion/iterative_conversion.rs | 20 +++++++++---- .../iterative_conversion_impl/mod.rs | 34 ++++++++++++++++++++-- 2 files changed, 46 insertions(+), 8 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index 7d52e9b..710903e 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -9,7 +9,7 @@ //! If you have any great idea how to improve it: Make a merge request! use std::convert::TryInto; -use std::ops::{Mul, DivAssign}; +use std::ops::{Mul, DivAssign, MulAssign}; use std::iter::successors; pub(crate) struct IterativeBaseConversion{ @@ -59,10 +59,10 @@ impl IterativeBaseConversion } impl std::iter::Iterator for IterativeBaseConversion - where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_power + where V : for<'a> DivAssign<&'a B> + //used in the first iteration to ensure that MulAssign cannot overflow. 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. - for<'a> &'a V : Mul<&'a B, Output = Option> + TryInto+ //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. + for<'a> MulAssign<&'a B> //used instead of DivAssign after one iteration. it's faster to mul the dividend than div the divisor. { type Item = B; @@ -73,7 +73,9 @@ impl std::iter::Iterator for IterativeBaseConversion let result = self.current_value.rem_assign_with_quotient(&self.current_base_power); if self.switch_to_multiplication { - self.current_value = (&self.current_value * &self.base).expect("Cannot overflow."); + //mul_assign is in principle dangerous. + //Since we do two rem_assign_with_quotient calls first, we can be sure that the result is always smaller than base^max_power though. + self.current_value *= &self.base } else { self.current_base_power /= &self.base; self.switch_to_multiplication = true; @@ -128,7 +130,13 @@ mod iterative_conversion_tests{ type Output = Option; fn mul(self, rhs: &MyU128) -> Self::Output { self.0.checked_mul(rhs.0).map(|s| MyU128(s)) - } + } + } + + impl MulAssign<&u64> for MyU128 { + fn mul_assign(&mut self, rhs: &u64) { + self.0.mul_assign(*rhs as u128); + } } impl RemAssignWithQuotient for MyU128{ diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index 96ca497..d3e0045 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -9,7 +9,7 @@ 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::ops::{DivAssign, Mul, MulAssign}; use std::convert::{TryFrom, TryInto}; use std::fmt::Display; use std::error::Error; @@ -70,6 +70,12 @@ impl Mul<&SixteenBytes> for &SixteenBytes{ } } +impl MulAssign<&usize> for SixteenBytes { + fn mul_assign(&mut self, rhs: &usize) { + self.0 *= *rhs as u128; + } +} + impl PrecomputedMaxPowers for SixteenBytes{} //-------------------------------------------------------------------------------------------------------------------------------------- @@ -253,6 +259,23 @@ impl Mul<&usize> for &ArbitraryBytes{ } } +//Done separately, because "mut references not allowed in const contexts" +impl MulAssign<&usize> for ArbitraryBytes{ + fn mul_assign(&mut self, rhs: &usize) { + #[cfg(target_pointer_width = "64")] + type Long = u128; + #[cfg(not(target_pointer_width = "64"))] + type Long = u64; + let rhs = *rhs as Long; + let carry = self.0.iter_mut().rev().fold(0 as Long, |carry, current| { + let res = (*current as Long) * rhs + carry; + *current = res as u32; + res >> 32 + }); + debug_assert_eq!(carry, 0); + } +} + 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. @@ -300,7 +323,7 @@ macro_rules! make_div_assign_with_remainder { 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().skip_while(|x| **x == 0).fold(0 as $t_long,|carry, current| { + 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); @@ -800,6 +823,13 @@ mod arbitrary_bytes_tests{ assert!(product.is_none()) } #[test] + fn mul_assign_usize(){ + let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + let b = 3usize; + a *= &b; + assert_eq!(a.0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036]) + } + #[test] fn try_into_u32_test(){ let a = ArbitraryBytes::new([0,0,0,0,0xabcde012]); let b : u32 = (&a).try_into().unwrap(); -- cgit v1.2.3 From 09d9c9e7d8d30c7f718837a44cabc90142f85b3e Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 26 Oct 2022 21:39:52 +0200 Subject: Minor, remove a pointless type conversion. Seems not to have any performance impact, but still, cleaner this way. --- src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index d3e0045..cee5418 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -371,7 +371,7 @@ impl ArbitraryBytes{ 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; + 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); @@ -434,7 +434,7 @@ impl ArbitraryBytes{ self.0[N-i-1] = val; } - fn shift_left(&self, s : usize) -> ::Output + fn shift_left(&self, s : u32) -> ::Output where Self : PadWithAZero> { debug_assert!(s < 32); @@ -445,7 +445,7 @@ impl ArbitraryBytes{ res } - fn shift_right(mut self, s : usize) -> Self { + fn shift_right(mut self, s : u32) -> Self { debug_assert!(s < 32); if s != 0 { let _ = self.0.iter_mut().fold(0u32, |carry, val| { -- cgit v1.2.3 From 37d19e9e9171c819d92afe395e30359aa059ee15 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 26 Oct 2022 23:47:18 +0200 Subject: Minor: Remove an unnecessary clone. --- src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index cee5418..71fb3d7 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -410,7 +410,7 @@ impl ArbitraryBytes{ //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()]); + let did_overflow = slice_overflowing_add_assign(&mut dividend.0[d_range], &divisor.0[s_range]); 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); -- 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(-) 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 db2e6ce5b648fa513009863e81a13f0e64281a78 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Thu, 3 Nov 2022 22:05:24 +0100 Subject: Test that compare iterative conversion with div. These tests compare the code for iterative base conversion with the alternative formula that spits out digits in reverse order. --- .../iterative_conversion_impl/mod.rs | 53 +++++++++++++++++++++- 1 file changed, 52 insertions(+), 1 deletion(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index 0a03192..6c6193d 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -524,6 +524,8 @@ fn u64_from_u32s(msb : u32, lsb : u32) -> u64{ #[cfg(test)] mod arbitrary_bytes_tests{ + use std::iter::successors; + use super::*; use rand::RngCore; use rand_xoshiro::rand_core::SeedableRng; @@ -566,7 +568,7 @@ mod arbitrary_bytes_tests{ 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 { + for _i in 0..100000 { 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); @@ -952,4 +954,53 @@ mod arbitrary_bytes_tests{ assert_eq!(a.0[7], 0xcd705aef); assert!(a.0[..7].iter().all(|x| *x==0)); } + + fn convert_by_division(value : ArbitraryBytes, base : usize) -> impl Iterator{ + successors(Some((value, 0)),|(v, _)| { + if *v == (&0usize).into() { + None + } else { + let mut v = v.clone(); + let remainder = v.div_assign_with_remainder_usize(&base); + Some((v, remainder)) + } + }).skip(1).map(|(_,b)| b).collect::>().into_iter().rev() + } + #[test] + fn compare_conversion_by_division_randoms_8(){ + let mut rng = Xoshiro256Plus::seed_from_u64(0); + for _ in 0..10000 { + let v = ArbitraryBytes::new([ + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + ]); + let b = rng.next_u32() as usize; + let i1 = super::super::IterativeBaseConversion::new(v.clone(),b).skip_while(|v| *v == 0); + let i2 = convert_by_division(v,b); + assert!(i1.eq(i2)); + } + } + #[test] + fn compare_conversion_by_division_randoms_5(){ + let mut rng = Xoshiro256Plus::seed_from_u64(0); + for _ in 0..10000 { + let v = ArbitraryBytes::new([ + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + rng.next_u32(), + ]); + let b = rng.next_u32() as usize; + let i1 = super::super::IterativeBaseConversion::new(v.clone(),b).skip_while(|v| *v == 0); + let i2 = convert_by_division(v,b); + assert!(i1.eq(i2)); + } + } } \ No newline at end of file -- cgit v1.2.3 From 344264e03d7635b9bd2688390100d3b9f623c58a Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 4 Nov 2022 00:12:14 +0100 Subject: Some clippy lints. Some were fixed, some were ignored because they seem to make a (negative) performance impact. --- .../base_conversion/iterative_conversion.rs | 5 +- .../iterative_conversion_impl/mod.rs | 69 ++++++++++++---------- 2 files changed, 41 insertions(+), 33 deletions(-) diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index 710903e..c8c121c 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -20,6 +20,7 @@ pub(crate) struct IterativeBaseConversion{ switch_to_multiplication : bool, //count the number of divisions. After 1, current_value is smaller than max_base_power. After 2, it's safe to mutliply current_value by base. } +#[allow(clippy::trait_duplication_in_bounds)] //That's obviously a false-positive in clippy... impl IterativeBaseConversion where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. PrecomputedMaxPowers, @@ -37,6 +38,7 @@ impl IterativeBaseConversion } } + #[allow(clippy::map_unwrap_or)] //current code seems to be measurably faster. 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)) @@ -66,6 +68,7 @@ impl std::iter::Iterator for IterativeBaseConversion { type Item = B; + #[allow(clippy::assign_op_pattern)] //measurable performance difference. No, this doesn't make sense. fn next(&mut self) -> Option { if self.remaining_digits == 0 { None @@ -75,7 +78,7 @@ impl std::iter::Iterator for IterativeBaseConversion if self.switch_to_multiplication { //mul_assign is in principle dangerous. //Since we do two rem_assign_with_quotient calls first, we can be sure that the result is always smaller than base^max_power though. - self.current_value *= &self.base + self.current_value *= &self.base; } else { self.current_base_power /= &self.base; self.switch_to_multiplication = true; diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index 6c6193d..3d5351a 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -38,7 +38,7 @@ impl From<&usize> for SixteenBytes{ } impl DivAssign<&usize> for SixteenBytes{ fn div_assign(&mut self, rhs: &usize) { - self.0 /= *rhs as u128 + self.0 /= *rhs as u128; } } impl RemAssignWithQuotient for SixteenBytes{ @@ -89,17 +89,18 @@ 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 { +#[allow(clippy::cast_possible_truncation)] +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. + 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) + from_usize(*x) } } impl From<&u32> for ArbitraryBytes{ @@ -198,7 +199,7 @@ impl PaddedShiftLeft for ArbitraryBytes<8>{ impl DivAssign<&usize> for ArbitraryBytes{ //just do long division. fn div_assign(&mut self, rhs: &usize) { - self.div_assign_with_remainder_usize(rhs); + self.div_assign_with_remainder_usize(*rhs); } } @@ -231,6 +232,7 @@ impl TryFrom<&ArbitraryBytes> for usize{ 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(); + #[allow(clippy::cast_possible_truncation)] //false positive. This function is only compiled on 64bit systems. last_bit.map(|last_bit| u64_from_u32s(second_last_bit, last_bit) as usize) } } @@ -308,6 +310,7 @@ impl Mul<&usize> for &ArbitraryBytes{ //Done separately, because "mut references not allowed in const contexts" impl MulAssign<&usize> for ArbitraryBytes{ + #[allow(clippy::cast_possible_truncation)] //truncation is intentional here. fn mul_assign(&mut self, rhs: &usize) { #[cfg(target_pointer_width = "64")] type Long = u128; @@ -315,9 +318,9 @@ impl MulAssign<&usize> for ArbitraryBytes{ type Long = u64; let rhs = *rhs as Long; let carry = self.0.iter_mut().rev().fold(0 as Long, |carry, current| { - let res = (*current as Long) * rhs + carry; - *current = res as u32; - res >> 32 + let result = (*current as Long) * rhs + carry; + *current = result as u32; + result >> 32 }); debug_assert_eq!(carry, 0); } @@ -333,7 +336,7 @@ impl Mul<&ArbitraryBytes> for &ArbitraryBytes where Arbit 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)..]) + slice_overflowing_add_assign(&mut result.0[0..=i], &p.0[(N-1-i)..]) }); carry.filter(|x| !x).map(|_|()) }); @@ -341,6 +344,7 @@ impl Mul<&ArbitraryBytes> for &ArbitraryBytes where Arbit } } +#[allow(clippy::trait_duplication_in_bounds)] //obvious false positive. u32 and usize aren't the same. impl RemAssignWithQuotient for ArbitraryBytes where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PaddedShiftLeft> { @@ -354,7 +358,7 @@ impl RemAssignWithQuotient for ArbitraryBytes< 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) + self.rem_assign_with_quotient_u32(divisor_as_u32) } else { self.rem_assign_with_quotient_knuth(divisor) } @@ -366,10 +370,10 @@ impl RemAssignWithQuotient for ArbitraryBytes< 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 { + 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 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; @@ -399,7 +403,7 @@ impl ArbitraryBytes{ 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> { + 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)) } @@ -427,8 +431,8 @@ impl ArbitraryBytes{ 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; + let guess_divisor = u64::from(divisor.get_digit_from_right(n_digits_divisor - 1)); + let divisor_second_significant_digit = u64::from(divisor.get_digit_from_right(n_digits_divisor-2)); //step D2, D7: the loop. for j in (0..=m_extra_digits_dividend).rev() { @@ -437,16 +441,17 @@ impl ArbitraryBytes{ 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 + while u32::try_from(guess_reminder).is_ok() + && (guesstimate > u64::from(u32::MAX) || divisor_second_significant_digit * guesstimate - > (guess_reminder << 32) | (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64) + > (guess_reminder << 32) | u64::from(dividend.get_digit_from_right(j + n_digits_divisor - 2)) ) { 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!"); + debug_assert!(guesstimate & u64::from(u32::MAX) == guesstimate, "The while above should have made guesstimate a one-digit number. Debug!"); + #[allow(clippy::cast_possible_truncation)] 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; @@ -458,7 +463,7 @@ impl ArbitraryBytes{ 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], &divisor.0[s_range]); - debug_assert!(did_overflow, "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.") + 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); } @@ -516,10 +521,10 @@ fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool { }) } -fn u64_from_u32s(msb : u32, lsb : u32) -> u64{ - let msb = msb as u64; - let lsb = lsb as u64; - (msb << 32) | lsb +fn u64_from_u32s(m : u32, l : u32) -> u64{ + let m = m as u64; + let l = l as u64; + (m << 32) | l } #[cfg(test)] @@ -640,7 +645,7 @@ mod arbitrary_bytes_tests{ 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 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); @@ -652,7 +657,7 @@ mod arbitrary_bytes_tests{ #[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); + 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]); } @@ -660,7 +665,7 @@ mod arbitrary_bytes_tests{ #[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); + 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]); } @@ -668,7 +673,7 @@ mod arbitrary_bytes_tests{ #[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); + let remainder = a.div_assign_with_remainder_usize(0x1234_usize); assert_eq!(a.0, [0x9A135,0x79AA8650,0xD251DC7A,0x9AA8C1F2,0x8B9729EF]); assert_eq!(remainder, 0x2E8); } @@ -676,7 +681,7 @@ mod arbitrary_bytes_tests{ #[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); + let remainder = a.div_assign_with_remainder_usize(0x1235_usize); assert_eq!(a.0, [0,0,0,0,0]); assert_eq!(remainder, 0x1234); } @@ -685,7 +690,7 @@ mod arbitrary_bytes_tests{ #[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); + let remainder = a.div_assign_with_remainder_usize(0x123456789ab_usize); assert_eq!(a.0, [0,0x9A107B,0xBEC8B35A,0xEC9D3B43,0x056F803A]); assert_eq!(remainder, 0xD7537A4B6); } @@ -961,7 +966,7 @@ mod arbitrary_bytes_tests{ None } else { let mut v = v.clone(); - let remainder = v.div_assign_with_remainder_usize(&base); + let remainder = v.div_assign_with_remainder_usize(base); Some((v, remainder)) } }).skip(1).map(|(_,b)| b).collect::>().into_iter().rev() -- 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(-) 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 From c385c90148178ad38b17491d45f5dcc2cbe06c9c Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 4 Nov 2022 21:31:36 +0100 Subject: Remove obsolete comment about base conversion. It's done, so no point in keeping the TODO around :D --- src/passwordmaker/mod.rs | 3 --- 1 file changed, 3 deletions(-) diff --git a/src/passwordmaker/mod.rs b/src/passwordmaker/mod.rs index c9ec1e3..405d469 100644 --- a/src/passwordmaker/mod.rs +++ b/src/passwordmaker/mod.rs @@ -224,9 +224,6 @@ enum GetGraphemesIteratorInner { struct GetGraphemesIterator<'a> { graphemes : &'a Vec>, inner : GetGraphemesIteratorInner - //There really should be a better solution than storing those values. If we had arbitrary-length multiplication and subtraction maybe? - //like, finding the highest potence of divisor that still is smaller than the dividend, and dividing by that one to get the left-most digit, - //dividing the remainder of this operation by the next-lower potence of divisor to get the second digit, and so on? } impl<'a> Iterator for GetGraphemesIterator<'a> { -- cgit v1.2.3