diff options
| -rw-r--r-- | Cargo.toml | 2 | ||||
| -rw-r--r-- | src/lib.rs | 3 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/iterative_conversion.rs | 151 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/iterative_conversion_impl.rs | 573 | ||||
| -rw-r--r-- | src/passwordmaker/base_conversion/mod.rs | 51 | ||||
| -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 | 56 |
8 files changed, 787 insertions, 199 deletions
@@ -24,6 +24,8 @@ sha-1 = "0.10.0" sha2 = "0.10.6" ripemd = "0.1.3" criterion = "0.4.0" +rand = "0.8.5" +rand_xoshiro = "0.6.0" [[bench]] name = "hashrate_32" @@ -17,6 +17,9 @@ //! //! [`PasswordMaker`] is the main part of this crate. You give it settings similar to those of a PasswordMaker Pro profile, //! and it gives you a password that's hopfully the same you'd get from PasswordMaker Pro for the same input. +//! +//! # Warning +//! This library has NOT been tested on 16bit machines. It might work, but probably does not. mod passwordmaker; diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs new file mode 100644 index 0000000..9b55141 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -0,0 +1,151 @@ +//! This module aims to provide iterative computation of the base-converted result, starting at the +//! most significant digit. +//! +//! # Warning +//! This is optimized for passwordmaker-rs domain specific number ranges. If you want to use this +//! somewhere else, make sure to adapt some maths. For instance you might want to early-out for leading zeros. +//! +//! The maths is not great, sorry. It's way easier to start at the least significant digit... +//! If you have any great idea how to improve it: Make a merge request! + +use std::convert::TryInto; +use std::ops::{Mul, DivAssign}; +use std::iter::successors; + +pub(crate) struct IterativeBaseConversion<V,B>{ + current_value : V, + current_base_potency : V, + remaining_digits : usize, + base : B, +} + +impl<V,B> IterativeBaseConversion<V,B> + where V: for<'a> From<&'a B>, //could be replaced by num::traits::identities::One. + for<'a> &'a V : Mul<&'a B, Output = Option<V>> //used to get the first current_base_potency. +{ + pub(super) fn new(value : V, base : B) -> Self{ + let PotencyAndExponent{potency : current_base_potency, count : remaining_digits} = Self::find_highest_fitting_potency(&base); + Self{ + current_value : value, + current_base_potency, + remaining_digits, + base, + } + } + + fn find_highest_fitting_potency(base : &B) -> PotencyAndExponent<V> { + //If we also required B: Mul<V> the new() function could be made a bit faster by going base^2 -> base^4 -> base^8 -> and so on. + //However, for realistic inputs, we have just about 100 multiplications, so, gut feeling says: simple === faster. + let base_v = base.into(); + let result = successors(Some(base_v), |potency| potency * base) + .enumerate() + .last() + .expect("Cannot fail, first entry is Some (required V : From<B>) and there's no filtering."); + PotencyAndExponent{ potency : result.1, count : result.0 + 2 } + } +} + +impl<V,B> std::iter::Iterator for IterativeBaseConversion<V,B> + where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency + RemAssignWithQuotient+ //used to get the result of each step. + TryInto<B> //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. +{ + type Item = B; + + fn next(&mut self) -> Option<Self::Item> { + if self.remaining_digits == 0 { + None + } else { + let result = self.current_value.rem_assign_with_quotient(&self.current_base_potency); + + self.current_base_potency /= &self.base; + self.remaining_digits = self.remaining_digits - 1; + + //this cannot ever yield None. + result.try_into().ok() + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.remaining_digits, Some(self.remaining_digits)) + } +} + +impl<V,B> std::iter::ExactSizeIterator for IterativeBaseConversion<V,B> + where IterativeBaseConversion<V,B> : Iterator +{} + +struct PotencyAndExponent<V>{ + potency : V, + count : usize, +} + +pub(super) trait RemAssignWithQuotient{ + /// Replaces self with remainder of division, and returns quotient. + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self; +} + +//tests general behaviour, using primitive types. +#[cfg(test)] +mod iterative_conversion_tests{ + use std::{ops::Mul, convert::{From, TryFrom}}; + + use super::*; + + #[derive(Debug,Clone)] + struct MyU128(u128); + impl Mul<&u64> for &MyU128 { + type Output = Option<MyU128>; + fn mul(self, rhs: &u64) -> Self::Output { + self.0.checked_mul(*rhs as u128).map(|s| MyU128(s)) + } + } + + impl RemAssignWithQuotient for MyU128{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self { + let quotient = self.0 / divisor.0; + self.0 %= divisor.0; + Self(quotient) + } + } + impl From<&u64> for MyU128{ + fn from(v: &u64) -> Self { + MyU128(v.clone() as u128) + } + } + + impl DivAssign<&u64> for MyU128{ + fn div_assign(&mut self, rhs: &u64) { + self.0 = self.0 / (*rhs as u128); + } + } + + impl TryFrom<MyU128> for u64{ + type Error = std::num::TryFromIntError; + + fn try_from(value: MyU128) -> Result<Self, Self::Error> { + value.0.try_into() + } + } + + + #[test] + fn test_simple_u128_to_hex_conversion(){ + let i = IterativeBaseConversion::new(MyU128(12345678u128), 16u64); + assert_eq!(i.len(), 32); + assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), 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]); + } +}
\ No newline at end of file diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs new file mode 100644 index 0000000..94c8b8b --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -0,0 +1,573 @@ +//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N]. + +//Reminder for myself: The traits needed are: +// where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. +// for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency +// RemAssignWithQuotient+ //used to get the result of each step. +// TryInto<B>, //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<V>> //used to get the first current_base_potency. + +//let's start with the simple case: u128 +//we do need a NewType here, because actual u128 already has a Mul<&usize> implementation that does not match the version we want. + +use std::{ops::{DivAssign, Mul, SubAssign}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering, iter::once}; + +use super::iterative_conversion::RemAssignWithQuotient; + +//Type to be used as V, with usize as B. +pub(crate) struct SixteenBytes(u128); + +impl SixteenBytes{ + pub(super) fn new(value : u128) -> Self { + SixteenBytes(value) + } +} + +//just for convenience +impl From<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) + } +} + +//-------------------------------------------------------------------------------------------------------------------------------------- +//and now the hard part: The same for [u32;N]. +//We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again. + +#[derive(PartialEq, PartialOrd, Ord, Eq, Clone)] +pub(crate) struct ArbitraryBytes<const N : usize>([u32;N]); + +//Const generics are still a bit limited -> let's just implement From for the exact types we need. +impl From<&usize> for ArbitraryBytes<5>{ + fn from(x: &usize) -> Self { + Self([ + 0,//(*x >> 32*4) as u32, //zero on all target platforms + 0,//(*x >> 32*3) as u32, //zero on all target platforms + 0,//(*x >> 32*2) as u32, //zero on all target platforms + x.checked_shr(32).map(|x| x as u32).unwrap_or_default(), + *x as u32, + ]) + } +} + +impl From<&usize> for ArbitraryBytes<8>{ + fn from(x: &usize) -> Self { + Self([ + 0,//(*x >> 32*7) as u32, //zero on all target platforms + 0,//(*x >> 32*6) as u32, //zero on all target platforms + 0,//(*x >> 32*5) as u32, //zero on all target platforms + 0,//(*x >> 32*4) as u32, //zero on all target platforms + 0,//(*x >> 32*3) as u32, //zero on all target platforms + 0,//(*x >> 32*2) as u32, //zero on all target platforms + x.checked_shr(32).map(|x| x as u32).unwrap_or_default(), + *x as u32, + ]) + } +} + +impl From<&u32> for ArbitraryBytes<5>{ + fn from(x: &u32) -> Self { + Self([ + 0, + 0, + 0, + 0, + *x, + ]) + } +} + +impl From<&u32> for ArbitraryBytes<8>{ + fn from(x: &u32) -> Self { + Self([ + 0, + 0, + 0, + 0, + 0, + 0, + 0, + *x, + ]) + } +} + +//workaround for lack of proper const-generic support. +pub(super) 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<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).map(|x| *x as usize); + //second-last is not an error though. + let second_last_bit = value.0.get(N-2).map(|u| (*u as usize) << 32).unwrap_or_default(); + last_bit.map(|last_bit| last_bit + second_last_bit) + } + } + #[cfg(not(target_pointer_width = "64"))] + fn try_from(value: &ArbitraryBytes<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).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToU32Error) + } + } +} + +impl<const N : usize> Mul<&usize> for &ArbitraryBytes<N>{ + type Output = Option<ArbitraryBytes<N>>; + fn mul(self, rhs: &usize) -> Self::Output { + #[cfg(target_pointer_width = "64")] + type UsizeAndFour = u128; + #[cfg(not(target_pointer_width = "64"))] + type UsizeAndFour = u64; + //somewhere we need this clone, can just as well be in here... + let mut result = self.0.clone(); + let carry = result.iter_mut().rev().fold(UsizeAndFour::default(), |carry, digit|{ + debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry always has to fit in usize, otherwise something is terribly wrong. + let res = (*digit as UsizeAndFour) * (*rhs as UsizeAndFour) + carry; + *digit = res as u32; + res >> 32 + }); + if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. + None + } else { + Some(ArbitraryBytes(result)) + } + } +} + +impl<const N : usize, const M : usize> RemAssignWithQuotient for ArbitraryBytes<N> + where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero<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. However, at least for now, a + //non-performing restoring version of the algorithm is used, because I'm too tired right now + //to properly implement the performing one (which would with near certainty be faster a bit). + + //well, nearly without trying to be smart. + match Ord::cmp(self, divisor){ + std::cmp::Ordering::Less => Self::from(&0_usize), //leave self unchanged, it's the remainder. + std::cmp::Ordering::Equal => { *self = Self::from(&0_usize); Self::from(&1_usize) }, + std::cmp::Ordering::Greater => { + if let Ok(divisor_as_u32) = divisor.try_into() { + self.rem_assign_with_quotient_u32(&divisor_as_u32) + } else { + self.rem_assign_with_quotient_knuth(divisor) + } + }, + } + } +} + +/// Needed by rem_assign_with_quotient_knuth +impl<const N : usize> Mul<u32> for ArbitraryBytes<N>{ + type Output = Option<ArbitraryBytes<N>>; + fn mul(mut self, rhs: u32) -> Self::Output { + let carry = self.0.iter_mut().rev().fold(u64::default(), |carry, digit|{ + debug_assert_eq!(carry, carry & (u32::MAX as u64)); //carry always has to fit in usize, otherwise something is terribly wrong. + let res = (*digit as u64) * (rhs as u64) + carry; + *digit = res as u32; + res >> 32 + }); + if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. + None + } else { + Some(self) + } + } +} + +impl<const N : usize> SubAssign<&ArbitraryBytes<N>> for ArbitraryBytes<N>{ + fn sub_assign(&mut self, rhs: &ArbitraryBytes<N>) { + let carry = self.0.iter_mut().zip(rhs.0.iter()).rev().fold(0_u64,|carry,(i,s)| { + let s = (*s as u64) + carry; + if *i as u64 >= s { + *i -= s as u32; + 0 + } else { + *i = (((*i as u64) + (1_u64<<32)) - s) as u32; + 1 + } + }); + debug_assert_eq!(carry,0); + } +} + + +impl<const N : usize> ArbitraryBytes<N>{ + pub(super) fn new(data : [u32;N]) -> Self { + ArbitraryBytes(data) + } + + /// Replaces self with Quotient and returns Remainder + fn div_assign_with_remainder_usize(&mut self, rhs: &usize) -> usize { + #[cfg(target_pointer_width = "64")] + type UsizeAndFour = u128; + #[cfg(not(target_pointer_width = "64"))] + type UsizeAndFour = u64; + debug_assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128); + + let divisor : UsizeAndFour = *rhs as UsizeAndFour; + let remainder = self.0.iter_mut().fold(0 as UsizeAndFour,|carry, current| { + debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize. + let carry_shifted = carry << 32; + let dividend = (carry_shifted) + (*current as UsizeAndFour); + let ratio = dividend / divisor; + debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + *current = (ratio) as u32; + dividend - ratio * divisor + }); + debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); + remainder as usize + } + + /// Used in rem_assign_with_quotient_knuth. The normalization factor is u32, and u32 might be larger than usize. + fn div_assign_with_remainder_u32(&mut self, rhs: &u32) -> u32 { + let divisor : u64 = *rhs as u64; + let remainder = self.0.iter_mut().fold(0_u64,|carry, current| { + debug_assert_eq!(carry, carry & (u32::MAX as u64)); //carry has to be lower than divisor, and divisor is usize. + let carry_shifted = carry << 32; + let dividend = (carry_shifted) + (*current as u64); + let ratio = dividend / divisor; + debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + *current = (ratio) as u32; + dividend - ratio * divisor + }); + debug_assert_eq!(remainder, remainder & (u32::MAX as u64)); + remainder as u32 + } + + fn rem_assign_with_quotient_u32(&mut self, divisor: &u32) -> Self where Self : for<'a> From<&'a u32> { + let remainder = self.div_assign_with_remainder_u32(divisor); + std::mem::replace(self, Self::from(&remainder)) + } + + + fn rem_assign_with_quotient_knuth<const M : usize>(&mut self, divisor : &Self) -> Self + where Self : PadWithAZero<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() 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. + let guess_divisor = divisor.get_digit_from_right(n_digits_divisor - 1) as u64; + let divisor_second_significant_digit = divisor.get_digit_from_right(n_digits_divisor-2) as u64; + + //step D2, D7: the loop. + for j in (0..=m_extra_digits_dividend).rev() { + //Step D3: Guess a digit + let guess_dividend = ((dividend.get_digit_from_right(j+n_digits_divisor) as u64)<<32) + (dividend.get_digit_from_right(j + n_digits_divisor - 1) as u64); + let mut guesstimate = guess_dividend/guess_divisor; + let mut guess_reminder = guess_dividend % guess_divisor; + //refine this result (still step D3) + while guess_reminder <= u32::MAX as u64 + && (guesstimate > u32::MAX as u64 + || divisor_second_significant_digit * guesstimate + > (guess_reminder << 32) + (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64) + ) { + guesstimate -= 1; + guess_reminder += guess_divisor; + } + //I'm too tired to do this by the book. If this thing is gonna blow, we can just as well increase our guesstimate by one and call it a day. + //In any case, this does only happen in _very_ rare cases. Soo: + //Steps D4-D6. + debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate); //Knuth says this is a one-place number, and I trust him. + let mut guesstimate = guesstimate as u32; + let mut s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type."); + let will_overflow = + std::cmp::PartialOrd::lt(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); + if will_overflow { + guesstimate -= 1; + s -= &divisor; + debug_assert!(std::cmp::Ord::cmp(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]) != Ordering::Less) + } + slice_sub_assign(&mut dividend.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); + quotient.set_digit_from_right(guesstimate, j); + } + + //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<const M : usize>(&self, s : usize) -> <Self as PadWithAZero>::Output + where Self : PadWithAZero<Output = ArbitraryBytes<M>> + { + 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_sub_assign(lhs : &mut [u32], rhs: &[u32]){ + debug_assert_eq!(lhs.len(), rhs.len()); + let carry = lhs.iter_mut().zip(rhs.iter()).rev().fold(0_u64,|carry,(i,s)| { + let s = (*s as u64) + carry; + if *i as u64 >= s { + *i -= s as u32; + 0 + } else { + *i = (((*i as u64) + (1_u64<<32)) - s) as u32; + 1 + } + }); + debug_assert_eq!(carry,0); +} + +#[cfg(test)] +mod iterative_conversion_impl_tests{ + use super::*; + use rand::RngCore; + use rand_xoshiro::rand_core::SeedableRng; + use rand_xoshiro::Xoshiro256Plus; + + /// Tests specifically the case that will_overflow is true. + #[test] + fn knuth_add_back_test(){ + let mut dividend = ArbitraryBytes::new([ + //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() -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{ + let mut rng = Xoshiro256Plus::seed_from_u64(0); + let mut res = Vec::new(); + for _i in 0..1000000 { + let dx = rng.next_u32() % 3 + 2; //at least 2 digits, at max 4 (u128) + let dy = rng.next_u32() % 3 + 2; + let ds = dx.min(dy); + let dl = dx.max(dy); + let dividendx = [ + 0, + if dl == 4 { rng.next_u32() } else { 0 }, + if dl >=3 { rng.next_u32() } else {0}, + rng.next_u32(), + rng.next_u32(), + ]; + let divisorx = [ + 0, + if ds == 4 { rng.next_u32() } else { 0 }, + if ds >=3 { rng.next_u32() } else {0}, + rng.next_u32(), + rng.next_u32(), + ]; + let needs_swap = ds == dl && dividendx[5-ds as usize] < divisorx[5-ds as usize]; + let dividend = ArbitraryBytes::new(if needs_swap { divisorx } else {dividendx}); + let divisor = ArbitraryBytes::new(if needs_swap {dividendx} else {divisorx}); + assert!(dividend.ge(&divisor)); + + let td = + ((dividend.0[1] as u128)<<96) + + ((dividend.0[2] as u128)<<64) + + ((dividend.0[3] as u128)<<32) + + (dividend.0[4] as u128); + let tn = + ((divisor.0[1] as u128)<<96) + + ((divisor.0[2] as u128)<<64) + + ((divisor.0[3] as u128)<<32) + + (divisor.0[4] as u128); + + + res.push((dividend, divisor, td/tn, td%tn)); + } + res + } + + /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.) + #[test] + fn knuth_many_numbers_test() { + let input = prepare_many_numbers(); + for (mut dividend, divisor, expected_quotient, expexted_remainder) in input { + let quotient = dividend.rem_assign_with_quotient_knuth(&divisor); + let remainder = dividend; + let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128); + let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128); + assert_eq!(quotient, expected_quotient); + assert_eq!(remainder, expexted_remainder); + } + } +}
\ No newline at end of file diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs index 8d217ef..b1ffedf 100644 --- a/src/passwordmaker/base_conversion/mod.rs +++ b/src/passwordmaker/base_conversion/mod.rs @@ -1,56 +1,63 @@ use std::convert::TryInto; +use iterative_conversion_impl::PadWithAZero; +pub(super) use iterative_conversion::IterativeBaseConversion; +pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes}; -use self::remainders::CalcRemainders; - -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 { + type Output : ExactSizeIterator<Item=usize>; // 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>>; + 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() +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> + PadWithAZero<Output = ArbitraryBytes<M>>, +{ + 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 +66,6 @@ impl ToI32Array for [u8;32] { u32::from_be_bytes(self[20..24].try_into().unwrap()), u32::from_be_bytes(self[24..28].try_into().unwrap()), u32::from_be_bytes(self[28..32].try_into().unwrap()), - ] + ]) } }
\ No newline at end of file diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs deleted file mode 100644 index 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 7bc6c0e..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().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 a96698d..5e51ee9 100644 --- a/src/passwordmaker/mod.rs +++ b/src/passwordmaker/mod.rs @@ -1,10 +1,13 @@ -use std::iter::repeat; +use std::iter::SkipWhile; + use unicode_segmentation::UnicodeSegmentation; use leet::LeetReplacementTable; use grapheme::Grapheme; use base_conversion::BaseConversion; +use self::base_conversion::{IterativeBaseConversion, SixteenBytes, ArbitraryBytes}; + use super::Hasher; mod base_conversion; @@ -94,7 +97,6 @@ impl<'y, H : super::HasherList> super::PasswordMaker<'y, H>{ let message = yeet_upper_bytes(&message).collect::<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} } } @@ -195,9 +196,15 @@ fn combine_prefix_password_suffix<'a, T : Iterator<Item=Grapheme<'a>>>(password: .collect() } +fn is_zero(i : &usize) -> bool { + *i == 0 +} + 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(SkipWhile<IterativeBaseConversion<SixteenBytes,usize>,fn(&usize)->bool>), + Modern20(SkipWhile<IterativeBaseConversion<ArbitraryBytes<5>,usize>,fn(&usize)->bool>), + Modern32(SkipWhile<IterativeBaseConversion<ArbitraryBytes<8>,usize>,fn(&usize)->bool>), + V06(IterativeBaseConversion<SixteenBytes,usize>) } struct GetGraphemesIterator<'a> { graphemes : &'a Vec<Grapheme<'a>>, @@ -212,21 +219,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 { @@ -307,11 +316,4 @@ impl AlgoSelection { #[allow(clippy::cast_possible_truncation)] //clippy, stop complaining. Truncating is the very purpose of this function... fn yeet_upper_bytes(input : &str) -> impl Iterator<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 |