diff options
| -rw-r--r-- | Cargo.toml | 9 | ||||
| -rw-r--r-- | src/lib.rs | 17 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/iterative_conversion.rs | 200 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs | 1011 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs | 72 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs | 126 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/mod.rs | 54 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/remainders.rs | 74 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/remainders_impl.rs | 76 | ||||
| -rw-r--r-- | src/passwordmaker/mod.rs | 69 | ||||
| -rw-r--r-- | tests/password_generation.rs | 19 |
11 files changed, 1523 insertions, 204 deletions
@@ -1,6 +1,6 @@ [package] name = "passwordmaker-rs" -version = "0.1.0" +version = "0.2.0" edition = "2018" authors = ["Andreas Grois"] rust-version = "1.52" @@ -12,6 +12,11 @@ keywords = ["password", "crypto", "password-generator", "security"] categories = ["cryptography"] readme = "README.md" +[features] +default = ["precomputed_common_max_powers"] +precomputed_max_powers = ["precomputed_common_max_powers"] +precomputed_common_max_powers = [] + [dependencies] unicode-segmentation = "1.10.0" @@ -25,6 +30,8 @@ sha-1 = "0.10.0" sha2 = "0.10.6" ripemd = "0.1.3" criterion = "0.4.0" +rand = "0.8.5" +rand_xoshiro = "0.6.0" [[bench]] name = "hashrate_32" @@ -17,6 +17,23 @@ //! //! [`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. mod passwordmaker; diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs new file mode 100644 index 0000000..c8c121c --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -0,0 +1,200 @@ +//! This module aims to provide iterative computation of the base-converted result, starting at the +//! most significant digit. +//! +//! # Warning +//! This is optimized for passwordmaker-rs domain specific number ranges. If you want to use this +//! somewhere else, make sure to adapt some maths. For instance you might want to early-out for leading zeros. +//! +//! The maths is not great, sorry. It's way easier to start at the least significant digit... +//! If you have any great idea how to improve it: Make a merge request! + +use std::convert::TryInto; +use std::ops::{Mul, DivAssign, MulAssign}; +use std::iter::successors; + +pub(crate) struct IterativeBaseConversion<V,B>{ + current_value : V, + current_base_power : V, + remaining_digits : usize, + base : B, + switch_to_multiplication : bool, //count the number of divisions. After 1, current_value is smaller than max_base_power. After 2, it's safe to mutliply current_value by base. +} + +#[allow(clippy::trait_duplication_in_bounds)] //That's obviously a false-positive in clippy... +impl<V,B> IterativeBaseConversion<V,B> + where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. + PrecomputedMaxPowers<B>, + for<'a> &'a V : Mul<&'a B, Output = Option<V>> + //used to get the first current_base_power. + Mul<&'a V, Output = Option<V>> +{ + pub(super) fn new(value : V, base : B) -> Self{ + let PowerAndExponent{power : current_base_power, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base); + Self{ + current_value : value, + current_base_power, + remaining_digits: highest_fitting_exponent + 1, //to the power of 0 is a digit too. Soo, if base^n is the largest fitting exponent, n+1 digits. + base, + switch_to_multiplication: false + } + } + + #[allow(clippy::map_unwrap_or)] //current code seems to be measurably faster. + fn find_highest_fitting_power(base : &B) -> PowerAndExponent<V> { + 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) -> PowerAndExponent<V> { + let base_v = base.into(); + + let exp_result = successors(Some((base_v, 1)), |(p, e)| { + Some(((p*p)?, 2*e)) + }).last(); + + + let result = successors(exp_result, |(power, count)| (power * base).map(|v| (v, count + 1))) + .last() + .expect("Cannot fail, first entry is Some (required V : From<B>) and there's no filtering."); + PowerAndExponent{ power : result.0, exponent : result.1 } + } +} + +impl<V,B> std::iter::Iterator for IterativeBaseConversion<V,B> + 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<B>+ //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; + + #[allow(clippy::assign_op_pattern)] //measurable performance difference. No, this doesn't make sense. + fn next(&mut self) -> Option<Self::Item> { + if self.remaining_digits == 0 { + None + } else { + let result = self.current_value.rem_assign_with_quotient(&self.current_base_power); + + 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; + } else { + self.current_base_power /= &self.base; + self.switch_to_multiplication = true; + } + self.remaining_digits = self.remaining_digits - 1; + + //this cannot ever yield None. + result.try_into().ok() + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.remaining_digits, Some(self.remaining_digits)) + } +} + +impl<V,B> std::iter::ExactSizeIterator for IterativeBaseConversion<V,B> + where IterativeBaseConversion<V,B> : Iterator +{} + +pub(super) struct PowerAndExponent<V>{ + pub(super) power : V, + pub(super) exponent : usize, +} + +pub(crate) trait RemAssignWithQuotient{ + /// Replaces self with remainder of division, and returns quotient. + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; +} + +pub(crate) trait PrecomputedMaxPowers<B> where Self : Sized{ + fn lookup(_base : &B) -> Option<(Self, usize)> { None } +} + +//tests general behaviour, using primitive types. +#[cfg(test)] +mod iterative_conversion_tests{ + use std::{ops::Mul, convert::{From, TryFrom}}; + + use super::*; + + #[derive(Debug,Clone)] + struct MyU128(u128); + impl Mul<&u64> for &MyU128 { + type Output = Option<MyU128>; + fn mul(self, rhs: &u64) -> Self::Output { + self.0.checked_mul(*rhs as u128).map(|s| MyU128(s)) + } + } + + impl Mul<&MyU128> for &MyU128 { + type Output = Option<MyU128>; + 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{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self { + let quotient = self.0 / divisor.0; + self.0 %= divisor.0; + Self(quotient) + } + } + impl From<&u64> for MyU128{ + fn from(v: &u64) -> Self { + MyU128(v.clone() as u128) + } + } + + impl DivAssign<&u64> for MyU128{ + fn div_assign(&mut self, rhs: &u64) { + self.0 = self.0 / (*rhs as u128); + } + } + + impl TryFrom<MyU128> for u64{ + type Error = std::num::TryFromIntError; + + fn try_from(value: MyU128) -> Result<Self, Self::Error> { + value.0.try_into() + } + } + + impl PrecomputedMaxPowers<u64> for MyU128{} + + #[test] + fn test_simple_u128_to_hex_conversion(){ + let i = IterativeBaseConversion::new(MyU128(12345678u128), 16u64); + assert_eq!(i.len(), 32); + assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), vec![0xB, 0xC, 0x6, 0x1, 0x4, 0xE]); + } + #[test] + fn test_simple_u128_to_base_17_conversion(){ + let i = IterativeBaseConversion::new(MyU128(1234567890123456789u128), 17u64); + assert_eq!(i.len(), 32); + assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), vec![7, 5, 0xA, 0x10, 0xC, 0xC, 3, 0xD, 3, 0xA, 3,8,4,8,3]); + } + #[test] + fn test_simple_u128_to_base_39_conversion(){ + let i = IterativeBaseConversion::new(MyU128(1234567890123456789u128), 39u64); + assert_eq!(i.len(), 25); + // 3YPRS4FaC1KU + assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), vec![3, 34, 25, 27, 28, 4, 15, 36, 12, 1, 20, 30]); + } + #[test] + fn test_overflow_in_switch_to_multiplication(){ + //This should simply not overflow ever. + let i = IterativeBaseConversion::new(MyU128(u128::MAX), 40); + let result = i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(); + assert_eq!(result, vec![1, 8, 14, 11, 10, 3, 37, 5, 26, 17, 14, 0, 23, 37, 35, 24, 3, 11, 27, 20, 34, 18, 12, 6, 15]); + } +}
\ No newline at end of file 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..b805272 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs @@ -0,0 +1,1011 @@ +//! 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. +#[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, MulAssign}; +use std::convert::{TryFrom, TryInto}; +use std::fmt::Display; +use std::error::Error; + +use super::iterative_conversion::{RemAssignWithQuotient, PrecomputedMaxPowers}; + +//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<u128> 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<SixteenBytes> for usize{ + type Error = std::num::TryFromIntError; + fn try_from(value: SixteenBytes) -> Result<Self, Self::Error> { + value.0.try_into() + } +} +impl Mul<&usize> for &SixteenBytes{ + type Output = Option<SixteenBytes>; + 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<SixteenBytes>; + + fn mul(self, rhs: &SixteenBytes) -> Self::Output { + self.0.checked_mul(rhs.0).map(Into::into) + } +} + +impl MulAssign<&usize> for SixteenBytes { + fn mul_assign(&mut self, rhs: &usize) { + self.0 *= *rhs as u128; + } +} + +impl PrecomputedMaxPowers<usize> for SixteenBytes{} + +//-------------------------------------------------------------------------------------------------------------------------------------- +//and now the hard part: The same for [u32;N]. +//We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again. + +#[derive(PartialEq, PartialOrd, Ord, Eq, Clone, Debug)] +pub(crate) struct ArbitraryBytes<const N : usize>([u32;N]); + +#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))] +impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{} +#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))] +impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{} + +#[allow(clippy::cast_possible_truncation)] +const fn from_usize<const N : usize>(x : usize) -> ArbitraryBytes<N> { + let mut result = [0;N]; //from Godbolt it looks like the compiler is smart enough to skip the unnecessary inits. + #[cfg(target_pointer_width = "64")] + if N > 1 { result[N-2] = (x >> 32) as u32;} + if N > 0 { result[N-1] = x as u32;} //Compiler should hopefully be smart enough to yeet the condition. + ArbitraryBytes(result) +} + +impl<const N : usize> From<&usize> for ArbitraryBytes<N>{ + fn from(x: &usize) -> Self { + from_usize(*x) + } +} +impl<const N : usize> From<&u32> for ArbitraryBytes<N>{ + 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. +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 { + 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 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<const N : usize> DivAssign<&usize> for ArbitraryBytes<N>{ + //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<const N : usize> TryFrom<ArbitraryBytes<N>> for usize{ + type Error = ArbitraryBytesToUsizeError; + + fn try_from(value: ArbitraryBytes<N>) -> Result<Self, Self::Error> { + usize::try_from(&value) + } +} + +impl<const N : usize> TryFrom<&ArbitraryBytes<N>> for usize{ + type Error = ArbitraryBytesToUsizeError; + #[cfg(target_pointer_width = "64")] + fn try_from(value: &ArbitraryBytes<N>) -> Result<Self, Self::Error> { + //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(); + #[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) + } + } + #[cfg(not(target_pointer_width = "64"))] + fn try_from(value: &ArbitraryBytes<N>) -> Result<Self, Self::Error> { + //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<const N : usize> TryFrom<&ArbitraryBytes<N>> for u32{ + type Error = ArbitraryBytesToU32Error; + + fn try_from(value: &ArbitraryBytes<N>) -> Result<Self, Self::Error> { + 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<const N : usize> Mul<$t> for ArbitraryBytes<N>{ + type Output = Option<ArbitraryBytes<N>>; + fn mul(self, rhs: $t) -> Self::Output { + $cfn(self, rhs) + } + } + const fn $cfn<const N : usize>(mut lhs : ArbitraryBytes<N>, rhs: $t) -> Option<ArbitraryBytes<N>> { + //sorry for this fugly non-idiomatic syntax, but Rust const functions seem to be severely limited right now :-( + let mut carry = 0 as $long_t; + let mut idx = N; + let rhs = rhs as $long_t; + while idx != 0 { + idx -= 1; + let res = (lhs.0[idx] as $long_t) * rhs + carry; + lhs.0[idx] = res as u32; + carry = res >> 32; + } + if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. + None + } else { + Some(lhs) + } + } + }; +} +make_mul!(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<const N : usize> Mul<&usize> for &ArbitraryBytes<N>{ + type Output = Option<ArbitraryBytes<N>>; + fn mul(self, rhs: &usize) -> Self::Output { + (*self).clone() * (*rhs) + } +} + +//Done separately, because "mut references not allowed in const contexts" +impl<const N : usize> MulAssign<&usize> for ArbitraryBytes<N>{ + #[allow(clippy::cast_possible_truncation)] //truncation is intentional here. + 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 result = (*current as Long) * rhs + carry; + *current = result as u32; + result >> 32 + }); + debug_assert_eq!(carry, 0); + } +} + +impl<const N : usize> Mul<&ArbitraryBytes<N>> for &ArbitraryBytes<N> where ArbitraryBytes<N> : for<'a> From<&'a usize> { + type Output = Option<ArbitraryBytes<N>>; + ///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<N>) -> Self::Output { + let mut result : ArbitraryBytes<N> = (&0_usize).into(); + let no_overflow = rhs.0.iter().enumerate().filter(|(_,b)| **b != 0).try_for_each(|(i,b)|{ + let p : Option<ArbitraryBytes<N>> = 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], &p.0[(N-1-i)..]) + }); + carry.filter(|x| !x).map(|_|()) + }); + no_overflow.map(|_| result) + } +} + +#[allow(clippy::trait_duplication_in_bounds)] //obvious false positive. u32 and usize aren't the same. +impl<const N : usize, const M : usize> RemAssignWithQuotient for ArbitraryBytes<N> + where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PaddedShiftLeft<Output = ArbitraryBytes<M>> +{ + 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<const N : usize> ArbitraryBytes<N>{ + 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<const M : usize>(&mut self, divisor : &Self) -> Self + where Self : PaddedShiftLeft<Output = ArbitraryBytes<M>> + + 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(); + //again, missing const generics ruin all the fun. + 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(); + + //needed for Step D3, but is the same for all iterations -> factored out. + 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() { + //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 u32::try_from(guess_reminder).is_ok() + && (guesstimate > u64::from(u32::MAX) + || divisor_second_significant_digit * guesstimate + > (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 & 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; + 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], &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); + } + + //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().find(|(_,v)| **v != 0).map_or(N,|(x,_)| x) + } + + 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_right(mut self, s : u32) -> 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(u32::from(carry)); + 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(u32::from(carry)); + let s = a.overflowing_add(r.0); + *a = s.0; + r.1 || s.1 + }) +} + +fn u64_from_u32s(m : u32, l : u32) -> u64{ + let m = u64::from(m); + let l = u64::from(l); + (m << 32) | l +} + +#[cfg(test)] +mod arbitrary_bytes_tests{ + use std::iter::successors; + + 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..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); + 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_5() { + let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]); + 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() { + 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 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(); + assert_eq!(b, 0xabcde012); + } + #[test] + fn try_into_u32_test_overflows(){ + let a = ArbitraryBytes::new([0,0,0,0x1,0xabcde012]); + let b : Result<u32,_> = (&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<usize,_> = (&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<usize,_> = (&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)); + } + + fn convert_by_division<const N : usize>(value : ArbitraryBytes<N>, base : usize) -> impl Iterator<Item = usize>{ + 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::<Vec<_>>().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 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<usize> 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<usize> 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::<ArbitraryBytes<5>,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::<ArbitraryBytes<8>,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 new file mode 100644 index 0000000..1127692 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs @@ -0,0 +1,126 @@ +use super::const_mul_usize; +use super::ArbitraryBytes; +use super::super::iterative_conversion::PrecomputedMaxPowers; + +impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{ + fn lookup(base : &usize) -> Option<(Self, usize)> { + get_from_cache(*base, &CONSTANT_MAX_POWER_CACHE_5) + } +} + +impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{ + fn lookup(base : &usize) -> Option<(Self, usize)> { + get_from_cache(*base, &CONSTANT_MAX_POWER_CACHE_8) + } +} + +fn get_from_cache<const N : usize>(base : usize, cache : &[([u32;N], usize)]) -> Option<(ArbitraryBytes<N>, usize)>{ + base.checked_sub(2).and_then(|idx|cache.get(idx)) + .map(|c| (ArbitraryBytes(c.0), c.1)) +} + +const CONSTANT_MAX_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_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<const N : usize>(base : usize) -> ([u32;N],usize){ + let start = super::from_usize(base); + + let mut x = (start, 1); + while let Some(next) = const_mul_usize(const_clone(&x.0),base) { + x.0 = next; + x.1 +=1; + } + (x.0.0, x.1) +} + +//If anyone could tell me how to implement "~const Clone" in stable Rust, I'd be very happy. +const fn const_clone<const N : usize>(x : &ArbitraryBytes<N>) -> ArbitraryBytes<N>{ArbitraryBytes(x.0)} + +const fn gen_const_max_power_cache<const N : usize, const CNT : usize>() -> [([u32;N],usize);CNT]{ + let mut result = [([0u32;N],0usize);CNT]; + let mut i = 0usize; + loop { + let highest = const_find_highest_fitting_power(i + 2); + result[i] = (highest.0, highest.1); + i +=1; + if i == CNT { break; } + } + result +} + +#[cfg(test)] +mod iterative_conversion_constants_tests{ + use super::ArbitraryBytes; + + #[test] + fn test_overlows_8() + { + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() + .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); + for (base, power, _exponent) in entries { + assert!((power * base).is_none()) + } + } + #[test] + fn test_overlows_5() + { + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() + .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); + for (base, power, _exponent) in entries { + assert!((power * base).is_none()) + } + } + #[test] + fn test_exponent_8() + { + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() + .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); + 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); + assert_eq!(remainder, 0); + } + assert_eq!(power, (&1usize).into()); + } + } + #[test] + fn test_exponent_5() + { + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() + .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); + 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); + assert_eq!(remainder, 0); + } + assert_eq!(power, (&1usize).into()); + } + } + #[test] + fn highest_fitting_power_consistency_5(){ + use super::super::super::iterative_conversion::IterativeBaseConversion; + let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate() + .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); + for (base, power, exponent) in entries { + let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<5>,usize>::find_highest_fitting_power_non_cached(&base); + assert_eq!(non_cached_result.exponent,exponent); + assert_eq!(non_cached_result.power, power); + } + } + #[test] + fn highest_fitting_power_consistency_8(){ + use super::super::super::iterative_conversion::IterativeBaseConversion; + let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate() + .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e)); + for (base, power, exponent) in entries { + let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<8>,usize>::find_highest_fitting_power_non_cached(&base); + assert_eq!(non_cached_result.exponent,exponent); + assert_eq!(non_cached_result.power, power); + } + } +}
\ No newline at end of file diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index 8d217ef..6415904 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -1,56 +1,64 @@ use std::convert::TryInto; +use iterative_conversion_impl::PaddedShiftLeft; +pub(super) use iterative_conversion::IterativeBaseConversion; +pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes}; -use self::remainders::CalcRemainders; +use self::iterative_conversion::PrecomputedMaxPowers; -mod remainders; -mod remainders_impl; +mod iterative_conversion; +mod iterative_conversion_impl; /// Converts an input to a different base (which fits in usize). Returns the digits starting at the most significant one. pub(super) trait BaseConversion { - // return type is subject to change. Hopefully soon the math will be rewritten, so we can skip the Vec and IntoIter. - // will have to remain an ExactSizeIterator though. - fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>>; + type Output : ExactSizeIterator<Item=usize>; + fn convert_to_base(self, base : usize) -> Self::Output; } -impl<T, const N : usize> BaseConversion for T where T : ToI32Array<Output = [u32;N]>{ - fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> { - self.to_int_array().calc_remainders(base).collect::<Vec<_>>().into_iter().rev() +#[allow(clippy::trait_duplication_in_bounds)] //False positive in clippy. usize != u32. +impl<T, const N : usize, const M : usize> BaseConversion for T + where T : ToArbitraryBytes<Output = ArbitraryBytes<N>>, + for<'a> T::Output: From<&'a usize> + From<&'a u32> + PaddedShiftLeft<Output = ArbitraryBytes<M>> + PrecomputedMaxPowers<usize>, +{ + type Output = IterativeBaseConversion<ArbitraryBytes<N>, usize>; + fn convert_to_base(self, base : usize) -> Self::Output { + IterativeBaseConversion::new(self.to_arbitrary_bytes(), base) } } impl BaseConversion for [u8;16]{ - fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> { - u128::from_be_bytes(self).calc_remainders(base as u128).map(|ll| ll as usize).collect::<Vec<_>>().into_iter().rev() + type Output = IterativeBaseConversion<SixteenBytes,usize>; + fn convert_to_base(self, base : usize) -> IterativeBaseConversion<SixteenBytes,usize> { + IterativeBaseConversion::new(SixteenBytes::new(u128::from_be_bytes(self)), base) } } // Rust 1.52 only has a very limited support for const generics. This means, we'll have to live with this not-too-constrained solution... -pub(super) trait ToI32Array { +pub(super) trait ToArbitraryBytes { type Output; - fn to_int_array(self) -> Self::Output; + fn to_arbitrary_bytes(self) -> Self::Output; } //this could of course be done in a generic manner, but it's ugly without array_mut, which we don't have in Rust 1.52. //Soo, pedestrian's approach :D -impl ToI32Array for [u8;20] { - type Output = [u32; 5]; - fn to_int_array(self) -> [u32; 5] { - [ +impl ToArbitraryBytes for [u8;20] { + type Output = ArbitraryBytes<5>; + fn to_arbitrary_bytes(self) -> ArbitraryBytes<5> { + ArbitraryBytes::new([ u32::from_be_bytes(self[0..4].try_into().unwrap()), u32::from_be_bytes(self[4..8].try_into().unwrap()), u32::from_be_bytes(self[8..12].try_into().unwrap()), u32::from_be_bytes(self[12..16].try_into().unwrap()), u32::from_be_bytes(self[16..20].try_into().unwrap()), - ] + ]) } } -impl ToI32Array for [u8;32] { - type Output = [u32; 8]; - fn to_int_array(self) -> [u32; 8] { - [ +impl ToArbitraryBytes for [u8;32] { + type Output = ArbitraryBytes<8>; + fn to_arbitrary_bytes(self) -> ArbitraryBytes<8> { + ArbitraryBytes::new([ u32::from_be_bytes(self[0..4].try_into().unwrap()), u32::from_be_bytes(self[4..8].try_into().unwrap()), u32::from_be_bytes(self[8..12].try_into().unwrap()), @@ -59,6 +67,6 @@ impl ToI32Array for [u8;32] { u32::from_be_bytes(self[20..24].try_into().unwrap()), u32::from_be_bytes(self[24..28].try_into().unwrap()), u32::from_be_bytes(self[28..32].try_into().unwrap()), - ] + ]) } }
\ No newline at end of file diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs deleted file mode 100644 index 93570a1..0000000 --- a/src/passwordmaker/base_conversion/remainders.rs +++ /dev/null @@ -1,74 +0,0 @@ -/// Adds `calc_remainders(divisor)` method to types that have some implementation of the Division trait. -pub(super) trait CalcRemainders<T, D>{ - fn calc_remainders(self, divisor : D) -> Remainders<T,D>; -} - -/// Implement `Division` to enable the `calc_remainders()` method for your type. -pub(super) trait Division<D> where Self:Sized { - /// does in-place arbitrary-length division. Returns remainder. - fn divide(self, divisor : &D) -> DivisionResult<Self, D>; - fn is_zero(&self) -> bool; -} - -/// Or mark your type as `UseGenericDivision` to just use `/` and `%` operators for types. Makes only sense for integers. -pub(super) trait UseGenericDivision : Clone - + for <'a> std::ops::Div<&'a Self, Output = Self> - + for <'a> std::ops::Rem<&'a Self, Output = Self> - + Default - + Eq {} - -impl<T, D> CalcRemainders<T, D> for T - where T:Division<D> -{ - fn calc_remainders(self, divisor : D) -> Remainders<T, D> { - Remainders::new(self,divisor) - } -} - -pub(super) struct Remainders<T, U>{ - value : Option<T>, - divisor : U, -} - -impl<U, T:Division<U>> Remainders<T, U> { - fn new(value : T, divisor : U) -> Self { - let value = if value.is_zero() { None } else { Some(value) }; - Remainders { - value, - divisor, - } - } -} - -impl<U, T:Division<U>> Iterator for Remainders<T,U>{ - type Item=U; - - fn next(&mut self) -> Option<Self::Item> { - if let Some(v) = self.value.take() { - let DivisionResult{result, remainder} = v.divide(&self.divisor); - self.value = if result.is_zero() { None } else { Some(result) }; - Some(remainder) - } else { - None - } - } -} - -pub(super) struct DivisionResult<T:Division<U>, U> { - pub result : T, - pub remainder : U, -} - -impl<U> Division<U> for U - where U: UseGenericDivision -{ - fn divide(self, divisor : &Self) -> DivisionResult<Self, Self> { - DivisionResult { - result: self.clone().div(divisor), - remainder: self.rem(divisor) - } - } - fn is_zero(&self) -> bool { - *self == Self::default() - } -}
\ No newline at end of file diff --git a/src/passwordmaker/base_conversion/remainders_impl.rs b/src/passwordmaker/base_conversion/remainders_impl.rs deleted file mode 100644 index 8f0a7f9..0000000 --- a/src/passwordmaker/base_conversion/remainders_impl.rs +++ /dev/null @@ -1,76 +0,0 @@ -use super::remainders::{Division, UseGenericDivision, DivisionResult}; - -impl UseGenericDivision for u128{} //for Md4, Md5 - -impl<const N : usize> Division<usize> for [u32;N] { - #[allow(clippy::cast_possible_truncation)] - fn divide(mut self, divisor : &usize) -> DivisionResult<Self, usize> { - #[cfg(target_pointer_width = "64")] - type UsizeAndFour = u128; - #[cfg(not(target_pointer_width = "64"))] - type UsizeAndFour = u64; - debug_assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128); - - //uses mutation, because why not? self is owned after all :D - let divisor : UsizeAndFour = *divisor as UsizeAndFour; - let remainder = self.iter_mut().skip_while(|x| **x == 0).fold(0 as UsizeAndFour,|carry, current| { - debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize. - let carry_shifted = carry << 32; - let dividend = (carry_shifted) + (*current as UsizeAndFour); - let ratio = dividend / divisor; - debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. - *current = (ratio) as u32; - dividend - (*current as UsizeAndFour) * divisor - }); - debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); - let remainder = remainder as usize; - DivisionResult{ - result: self, - remainder, - } - } - - fn is_zero(&self) -> bool { - self.iter().all(|x| *x == 0) - } -} - -#[cfg(test)] -mod remainders_tests{ - use super::super::remainders::CalcRemainders; - - use super::*; - #[test] - fn test_generic_division(){ - let v = 50u128; - let d = 7u128; - let DivisionResult{result, remainder}=v.divide(&d); - assert_eq!(7, result); - assert_eq!(1, remainder); - } - - #[test] - fn test_remainders() { - //relies on generic division. - let v = 141u128; - let d = 3u128; - let results : Vec<u128> = v.calc_remainders(d).collect(); - assert_eq!(results, vec![0u128,2u128,0u128,2u128,1u128]) - } - - #[test] - fn test_array_divide() { - let dividend_int = 0xe7f1ec3a5f35af805407a8a531eefb79u128; - let dividend = [(dividend_int >> 96) as u32, ((dividend_int >> 64) & 0xffffffff) as u32, ((dividend_int >> 32) & 0xffffffff) as u32, (dividend_int & 0xffffffff) as u32]; - #[cfg(target_pointer_width = "64")] - let divisor = 1531534813576487; - #[cfg(not(target_pointer_width = "64"))] - let divisor = 1531534813; - let result_int = dividend_int / (divisor as u128); - let remainder_int = dividend_int % (divisor as u128); - let result = dividend.divide(&divisor); - assert_eq!(result.result, [(result_int >> 96) as u32, ((result_int >> 64) & 0xffffffff) as u32, ((result_int >> 32) & 0xffffffff) as u32, (result_int & 0xffffffff) as u32]); - assert_eq!(remainder_int, result.remainder as u128); - } - -}
\ No newline at end of file diff --git a/src/passwordmaker/mod.rs b/src/passwordmaker/mod.rs index 390836a..405d469 100644 --- a/src/passwordmaker/mod.rs +++ b/src/passwordmaker/mod.rs @@ -1,10 +1,13 @@ -use std::iter::repeat; +use std::iter::SkipWhile; + use unicode_segmentation::UnicodeSegmentation; use leet::LeetReplacementTable; use grapheme::Grapheme; use base_conversion::BaseConversion; +use self::base_conversion::{IterativeBaseConversion, SixteenBytes, ArbitraryBytes}; + use super::Hasher; mod base_conversion; @@ -94,7 +97,6 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let message = yeet_upper_bytes(&message).collect::<Vec<u8>>(); let hash = H::MD5::hash(&message); let grapheme_indices = hash.convert_to_base(characters.len()); - let grapheme_indices = yoink_additional_graphemes_for_06_if_needed(grapheme_indices); GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::V06(grapheme_indices)} } @@ -112,7 +114,6 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let data = yeet_upper_bytes(data); let hash = hmac::hmac::<H::MD5,_,_>(key, data); let grapheme_indices = hash.convert_to_base(characters.len()); - let grapheme_indices = yoink_additional_graphemes_for_06_if_needed(grapheme_indices); GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::V06(grapheme_indices)} } @@ -128,17 +129,17 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let data = leetified_data.as_deref().unwrap_or(data); let grapheme_indices = match algo { Algorithm::Md4 => - modern_hmac_to_grapheme_indices::<H::MD4>(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern16(modern_hmac_to_grapheme_indices::<H::MD4>(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Md5 => - modern_hmac_to_grapheme_indices::<H::MD5>(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern16(modern_hmac_to_grapheme_indices::<H::MD5>(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Sha1 => - modern_hmac_to_grapheme_indices::<H::SHA1>(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern20(modern_hmac_to_grapheme_indices::<H::SHA1>(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Sha256 => - modern_hmac_to_grapheme_indices::<H::SHA256>(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern32(modern_hmac_to_grapheme_indices::<H::SHA256>(&key, data, characters.len()).skip_while(is_zero)), Algorithm::Ripemd160 => - modern_hmac_to_grapheme_indices::<H::RIPEMD160>(&key, data, characters.len()), + GetGraphemesIteratorInner::Modern20(modern_hmac_to_grapheme_indices::<H::RIPEMD160>(&key, data, characters.len()).skip_while(is_zero)), }; - GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::Modern(grapheme_indices)} + GetGraphemesIterator { graphemes : characters, inner: grapheme_indices} } fn generate_password_part_modern<'a>( @@ -152,17 +153,17 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let message = pre_leet_level.as_ref().map(|l| l.leetify(&message)).unwrap_or(message); let grapheme_indices = match algo { Algorithm::Md4 => - modern_message_to_grapheme_indices::<H::MD4>(&message, characters.len()), + GetGraphemesIteratorInner::Modern16(modern_message_to_grapheme_indices::<H::MD4>(&message, characters.len()).skip_while(is_zero)), Algorithm::Md5 => - modern_message_to_grapheme_indices::<H::MD5>(&message,characters.len()), + GetGraphemesIteratorInner::Modern16(modern_message_to_grapheme_indices::<H::MD5>(&message,characters.len()).skip_while(is_zero)), Algorithm::Sha1 => - modern_message_to_grapheme_indices::<H::SHA1>(&message,characters.len()), + GetGraphemesIteratorInner::Modern20(modern_message_to_grapheme_indices::<H::SHA1>(&message,characters.len()).skip_while(is_zero)), Algorithm::Sha256 => - modern_message_to_grapheme_indices::<H::SHA256>(&message,characters.len()), + GetGraphemesIteratorInner::Modern32(modern_message_to_grapheme_indices::<H::SHA256>(&message,characters.len()).skip_while(is_zero)), Algorithm::Ripemd160 => - modern_message_to_grapheme_indices::<H::RIPEMD160>(&message,characters.len()), + GetGraphemesIteratorInner::Modern20(modern_message_to_grapheme_indices::<H::RIPEMD160>(&message,characters.len()).skip_while(is_zero)), }; - GetGraphemesIterator { graphemes : characters, inner: GetGraphemesIteratorInner::Modern(grapheme_indices)} + GetGraphemesIterator { graphemes : characters, inner: grapheme_indices} } } @@ -200,16 +201,29 @@ fn combine_prefix_password_suffix<'a, T : Iterator<Item=Grapheme<'a>>>(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<SixteenBytes,usize>; +type BaseConversion16Modern = SkipWhile<BaseConversion16,fn(&usize)->bool>; + +type BaseConversion20 = IterativeBaseConversion<ArbitraryBytes<5>,usize>; +type BaseConversion20Modern = SkipWhile<BaseConversion20,fn(&usize)->bool>; + +type BaseConversion32 = IterativeBaseConversion<ArbitraryBytes<8>,usize>; +type BaseConversion32Modern = SkipWhile<BaseConversion32,fn(&usize)->bool>; + enum GetGraphemesIteratorInner { - Modern(std::iter::Rev<std::vec::IntoIter<usize>>), - V06(std::iter::Chain<std::iter::Take<std::iter::Repeat<usize>>, std::iter::Rev<std::vec::IntoIter<usize>>>) + Modern16(BaseConversion16Modern), + Modern20(BaseConversion20Modern), + Modern32(BaseConversion32Modern), + V06(BaseConversion16) } struct GetGraphemesIterator<'a> { graphemes : &'a Vec<Grapheme<'a>>, inner : GetGraphemesIteratorInner - //There really should be a better solution than storing those values. If we had arbitrary-length multiplication and subtraction maybe? - //like, finding the highest potence of divisor that still is smaller than the dividend, and dividing by that one to get the left-most digit, - //dividing the remainder of this operation by the next-lower potence of divisor to get the second digit, and so on? } impl<'a> Iterator for GetGraphemesIterator<'a> { @@ -217,21 +231,23 @@ impl<'a> Iterator for GetGraphemesIterator<'a> { fn next(&mut self) -> Option<Self::Item> { let idx = match &mut self.inner { - GetGraphemesIteratorInner::Modern(i) => i.next(), + GetGraphemesIteratorInner::Modern16(i) => i.next(), + GetGraphemesIteratorInner::Modern20(i) => i.next(), + GetGraphemesIteratorInner::Modern32(i) => i.next(), GetGraphemesIteratorInner::V06(i) => i.next(), }; idx.and_then(|idx| self.graphemes.get(idx).cloned()) } } -fn modern_hmac_to_grapheme_indices<T>(key : &str, data: &str, divisor : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> +fn modern_hmac_to_grapheme_indices<T>(key : &str, data: &str, divisor : usize) -> <<T as Hasher>::Output as BaseConversion>::Output where T:Hasher, <T as Hasher>::Output: BaseConversion + AsRef<[u8]> { hmac::hmac::<T,_,_>(key.bytes(), data.bytes()).convert_to_base(divisor) } -fn modern_message_to_grapheme_indices<T>(data: &str, divisor : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> +fn modern_message_to_grapheme_indices<T>(data: &str, divisor : usize) -> <<T as Hasher>::Output as BaseConversion>::Output where T:Hasher, <T as Hasher>::Output: BaseConversion { @@ -312,11 +328,4 @@ impl AlgoSelection { #[allow(clippy::cast_possible_truncation)] //clippy, stop complaining. Truncating is the very purpose of this function... fn yeet_upper_bytes(input : &str) -> impl Iterator<Item=u8> + Clone + '_ { input.encode_utf16().map(|wide_char| wide_char as u8) -} - -//signature subject to change, but need named types... -fn yoink_additional_graphemes_for_06_if_needed(input : std::iter::Rev<std::vec::IntoIter<usize>>) - -> std::iter::Chain<std::iter::Take<std::iter::Repeat<usize>>, std::iter::Rev<std::vec::IntoIter<usize>>> -{ - repeat(0_usize).take(32-input.len()).chain(input) }
\ No newline at end of file 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 |