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... --- .../iterative_conversion_impl/mod.rs | 875 +++++++++++++++++++++ .../precomputed_constants.rs | 125 +++ 2 files changed, 1000 insertions(+) create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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 -- cgit v1.2.3 From 53fff5d2f7fc007476e4c4850bd4f974f488b13e Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sun, 23 Oct 2022 15:22:20 +0200 Subject: Rename "potency" to "power", the English term. It seems English doesn't use the word potency in this context, but rather uses power. --- .../base_conversion/iterative_conversion.rs | 32 +++++------ .../iterative_conversion_impl/mod.rs | 4 +- .../precomputed_constants.rs | 62 +++++++++++----------- src/passwordmaker/base_conversion/mod.rs | 4 +- 4 files changed, 51 insertions(+), 51 deletions(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index f5db0f7..e88f379 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -14,34 +14,34 @@ use std::iter::successors; pub(crate) struct IterativeBaseConversion{ current_value : V, - current_base_potency : V, + current_base_power : V, remaining_digits : usize, base : B, } impl IterativeBaseConversion where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. - ConstantMaxPotencyCache, - for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_potency. + ConstantMaxPowerCache, + for<'a> &'a V : Mul<&'a B, Output = Option> + //used to get the first current_base_power. Mul<&'a V, Output = Option> { pub(super) fn new(value : V, base : B) -> Self{ - let PotencyAndExponent{power : current_base_potency, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base); + let PowerAndExponent{power : current_base_power, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base); Self{ current_value : value, - current_base_potency, + current_base_power, remaining_digits: highest_fitting_exponent + 1, //to the power of 0 is a digit too. Soo, if base^n is the largest fitting exponent, n+1 digits. base, } } - fn find_highest_fitting_power(base : &B) -> PotencyAndExponent { - V::lookup(base).map(|(potency,count)| PotencyAndExponent{ power: potency, exponent: count }) + fn find_highest_fitting_power(base : &B) -> PowerAndExponent { + V::lookup(base).map(|(power,count)| PowerAndExponent{ power, exponent: count }) .unwrap_or_else(|| Self::find_highest_fitting_power_non_cached(base)) } //public for unit tests in cache, which is not a sub-module of this. - pub(super) fn find_highest_fitting_power_non_cached(base : &B) -> PotencyAndExponent { + pub(super) fn find_highest_fitting_power_non_cached(base : &B) -> PowerAndExponent { let base_v = base.into(); let exp_result = successors(Some((base_v, 1)), |(p, e)| { @@ -49,15 +49,15 @@ impl IterativeBaseConversion }).last(); - let result = successors(exp_result, |(potency, count)| (potency * base).map(|v| (v, count + 1))) + let result = successors(exp_result, |(power, count)| (power * base).map(|v| (v, count + 1))) .last() .expect("Cannot fail, first entry is Some (required V : From) and there's no filtering."); - PotencyAndExponent{ power : result.0, exponent : result.1 } + PowerAndExponent{ power : result.0, exponent : result.1 } } } impl std::iter::Iterator for IterativeBaseConversion - where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency + where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_power RemAssignWithQuotient+ //used to get the result of each step. TryInto //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. { @@ -67,9 +67,9 @@ impl std::iter::Iterator for IterativeBaseConversion if self.remaining_digits == 0 { None } else { - let result = self.current_value.rem_assign_with_quotient(&self.current_base_potency); + let result = self.current_value.rem_assign_with_quotient(&self.current_base_power); - self.current_base_potency /= &self.base; + self.current_base_power /= &self.base; self.remaining_digits = self.remaining_digits - 1; //this cannot ever yield None. @@ -86,7 +86,7 @@ impl std::iter::ExactSizeIterator for IterativeBaseConversion where IterativeBaseConversion : Iterator {} -pub(super) struct PotencyAndExponent{ +pub(super) struct PowerAndExponent{ pub(super) power : V, pub(super) exponent : usize, } @@ -96,7 +96,7 @@ pub(crate) trait RemAssignWithQuotient{ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; } -pub(crate) trait ConstantMaxPotencyCache where Self : Sized{ +pub(crate) trait ConstantMaxPowerCache where Self : Sized{ fn lookup(_base : &B) -> Option<(Self, usize)> { None } } @@ -150,7 +150,7 @@ mod iterative_conversion_tests{ } } - impl ConstantMaxPotencyCache for MyU128{} + impl ConstantMaxPowerCache for MyU128{} #[test] fn test_simple_u128_to_hex_conversion(){ diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs index 7ab9171..ae4aeca 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -13,7 +13,7 @@ use std::fmt::Display; use std::error::Error; use std::iter::once; -use super::iterative_conversion::{RemAssignWithQuotient, ConstantMaxPotencyCache}; +use super::iterative_conversion::{RemAssignWithQuotient, ConstantMaxPowerCache}; //Type to be used as V, with usize as B. pub(crate) struct SixteenBytes(u128); @@ -68,7 +68,7 @@ impl Mul<&SixteenBytes> for &SixteenBytes{ } } -impl ConstantMaxPotencyCache for SixteenBytes{} +impl ConstantMaxPowerCache for SixteenBytes{} //-------------------------------------------------------------------------------------------------------------------------------------- //and now the hard part: The same for [u32;N]. diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs index c5a1809..86b8c56 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs @@ -1,15 +1,15 @@ use super::const_mul_usize; use super::ArbitraryBytes; -use super::super::iterative_conversion::ConstantMaxPotencyCache; +use super::super::iterative_conversion::ConstantMaxPowerCache; -impl ConstantMaxPotencyCache for ArbitraryBytes<5>{ +impl ConstantMaxPowerCache for ArbitraryBytes<5>{ fn lookup(base : &usize) -> Option<(Self, usize)> { - get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_5) + get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_5) } } -impl ConstantMaxPotencyCache for ArbitraryBytes<8>{ +impl ConstantMaxPowerCache for ArbitraryBytes<8>{ fn lookup(base : &usize) -> Option<(Self, usize)> { - get_from_cache(base, &CONSTANT_MAX_POTENCY_CACHE_8) + get_from_cache(base, &CONSTANT_MAX_POWER_CACHE_8) } } @@ -18,12 +18,12 @@ fn get_from_cache(base : &usize, cache : &[([u32;N], usize)]) - .map(|c| (ArbitraryBytes(c.0), c.1)) } -const CONSTANT_MAX_POTENCY_CACHE_5 : [([u32;5],usize);128] = gen_const_max_potency_cache(); -const CONSTANT_MAX_POTENCY_CACHE_8 : [([u32;8],usize);128] = gen_const_max_potency_cache(); +const CONSTANT_MAX_POWER_CACHE_5 : [([u32;5],usize);128] = gen_const_max_power_cache(); +const CONSTANT_MAX_POWER_CACHE_8 : [([u32;8],usize);128] = gen_const_max_power_cache(); //----------------------------------------------------------------------------------------- -/// This version of find_highest_fitting_potency is not optimized. But it can run in const contexts. Only use it there, use the normal one everywhere else. +/// This version of find_highest_fitting_power is not optimized. But it can run in const contexts. Only use it there, use the normal one everywhere else. const fn const_find_highest_fitting_power(base : usize) -> ([u32;N],usize){ let start = super::from_usize(&base); @@ -38,7 +38,7 @@ const fn const_find_highest_fitting_power(base : usize) -> ([u3 //If anyone could tell me how to implement "~const Clone" in stable Rust, I'd be very happy. const fn const_clone(x : &ArbitraryBytes) -> ArbitraryBytes{ArbitraryBytes(x.0)} -pub(crate) const fn gen_const_max_potency_cache() -> [([u32;N],usize);CNT]{ +pub(crate) const fn gen_const_max_power_cache() -> [([u32;N],usize);CNT]{ let mut result = [([0u32;N],0usize);CNT]; let mut i = 0usize; loop { @@ -57,69 +57,69 @@ mod iterative_conversion_constants_tests{ #[test] fn test_overlows_8() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, _exponent) in entries { - assert!((potency * base).is_none()) + for (base, power, _exponent) in entries { + assert!((power * base).is_none()) } } #[test] fn test_overlows_5() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, _exponent) in entries { - assert!((potency * base).is_none()) + for (base, power, _exponent) in entries { + assert!((power * base).is_none()) } } #[test] fn test_exponent_8() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, mut potency, exponent) in entries { + for (base, mut power, exponent) in entries { //exponent is the largest fitting exponent. Soo, if we divide exponent times, we should end up with 1. for _i in 0..exponent { - let remainder = potency.div_assign_with_remainder_usize(&base); + let remainder = power.div_assign_with_remainder_usize(&base); assert_eq!(remainder, 0); } - assert_eq!(potency, (&1usize).into()); + assert_eq!(power, (&1usize).into()); } } #[test] fn test_exponent_5() { - let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, mut potency, exponent) in entries { + for (base, mut power, exponent) in entries { //exponent is the largest fitting exponent. Soo, if we divide exponent times, we should end up with 1. for _i in 0..exponent { - let remainder = potency.div_assign_with_remainder_usize(&base); + let remainder = power.div_assign_with_remainder_usize(&base); assert_eq!(remainder, 0); } - assert_eq!(potency, (&1usize).into()); + assert_eq!(power, (&1usize).into()); } } #[test] - fn highest_fitting_potency_consistency_5(){ + fn highest_fitting_power_consistency_5(){ use super::super::super::iterative_conversion::IterativeBaseConversion; - let entries = super::CONSTANT_MAX_POTENCY_CACHE_5.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, exponent) in entries { + for (base, power, exponent) in entries { let non_cached_result = IterativeBaseConversion::,usize>::find_highest_fitting_power_non_cached(&base); assert_eq!(non_cached_result.exponent,exponent); - assert_eq!(non_cached_result.power, potency); + assert_eq!(non_cached_result.power, power); } } #[test] - fn highest_fitting_potency_consistency_8(){ + fn highest_fitting_power_consistency_8(){ use super::super::super::iterative_conversion::IterativeBaseConversion; - let entries = super::CONSTANT_MAX_POTENCY_CACHE_8.iter().enumerate() + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); - for (base, potency, exponent) in entries { + for (base, power, exponent) in entries { let non_cached_result = IterativeBaseConversion::,usize>::find_highest_fitting_power_non_cached(&base); assert_eq!(non_cached_result.exponent,exponent); - assert_eq!(non_cached_result.power, potency); + assert_eq!(non_cached_result.power, power); } } } \ No newline at end of file diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index bb3fbd6..311f7c5 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -3,7 +3,7 @@ use iterative_conversion_impl::PadWithAZero; pub(super) use iterative_conversion::IterativeBaseConversion; pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes}; -use self::iterative_conversion::ConstantMaxPotencyCache; +use self::iterative_conversion::ConstantMaxPowerCache; mod iterative_conversion; mod iterative_conversion_impl; @@ -16,7 +16,7 @@ pub(super) trait BaseConversion { impl BaseConversion for T where T : ToArbitraryBytes>, - for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero> + ConstantMaxPotencyCache, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PadWithAZero> + ConstantMaxPowerCache, { type Output = IterativeBaseConversion, usize>; fn convert_to_base(self, base : usize) -> Self::Output { -- cgit v1.2.3 From 1f57846664b97f0cb630bf5fee13dfbc66f7c77a Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Sun, 23 Oct 2022 20:26:23 +0200 Subject: Add precomputed constants for common cases. There are now 2 features that control the amount of precomputed constants. They can either be 0, 12, or 256. Most users will likely want to go with the 12, so this is the default feature. --- Cargo.toml | 5 ++ src/lib.rs | 14 +++++ .../base_conversion/iterative_conversion.rs | 6 +- .../iterative_conversion_impl/mod.rs | 13 +++- .../precomputed_common_constants.rs | 72 ++++++++++++++++++++++ .../precomputed_constants.rs | 9 +-- src/passwordmaker/base_conversion/mod.rs | 4 +- tests/password_generation.rs | 19 ++++++ 8 files changed, 130 insertions(+), 12 deletions(-) create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl') 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