From b1f4d48e956c6b6599b666248e5aa157b9660dca Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Tue, 18 Oct 2022 07:56:16 +0200 Subject: First draft of (untested) iterative conversion. --- .../base_conversion/iterative_conversion_impl.rs | 443 +++++++++++++++++++++ 1 file changed, 443 insertions(+) create mode 100644 src/passwordmaker/base_conversion/iterative_conversion_impl.rs (limited to 'src/passwordmaker/base_conversion/iterative_conversion_impl.rs') diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs new file mode 100644 index 0000000..be1d851 --- /dev/null +++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs @@ -0,0 +1,443 @@ +//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N]. + +//Reminder for myself: The traits needed are: +// where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One. +// for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency +// RemAssignWithQuotient+ //used to get the result of each step. +// TryInto, //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. +// for<'a> &'a V : Mul<&'a B, Output = Option> //used to get the first current_base_potency. + +//let's start with the simple case: u128 +//we do need a NewType here, because actual u128 already has a Mul<&usize> implementation that does not match the version we want. + +use std::{ops::{DivAssign, Mul, SubAssign}, convert::{TryFrom, TryInto}, fmt::Display, error::Error, cmp::Ordering}; + +use super::iterative_conversion::RemAssignWithQuotient; + +//Type to be used as V, with usize as B. +struct SixteenBytes(u128); + +//just for convenience +impl From for SixteenBytes{ + fn from(x: u128) -> Self { + SixteenBytes(x) + } +} +impl From<&usize> for SixteenBytes{ + fn from(x: &usize) -> Self { + SixteenBytes(*x as u128) + } +} +impl DivAssign<&usize> for SixteenBytes{ + fn div_assign(&mut self, rhs: &usize) { + self.0 /= *rhs as u128 + } +} +impl RemAssignWithQuotient for SixteenBytes{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self { + let quotient = self.0 / divisor.0; + self.0 %= divisor.0; + Self(quotient) + } +} +impl TryFrom for usize{ + type Error = std::num::TryFromIntError; + fn try_from(value: SixteenBytes) -> Result { + value.0.try_into() + } +} +impl Mul<&usize> for &SixteenBytes{ + type Output = Option; + fn mul(self, rhs: &usize) -> Self::Output { + self.0.checked_mul(*rhs as u128).map(Into::into) + } +} + +//-------------------------------------------------------------------------------------------------------------------------------------- +//and now the hard part: The same for [u32;N]. +//We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again. + +#[derive(PartialEq, PartialOrd, Ord, Eq, Clone)] +struct ArbitraryBytes([u32;N]); + +//Const generics are still a bit limited -> let's just implement From for the exact types we need. +impl From<&usize> for ArbitraryBytes<5>{ + fn from(x: &usize) -> Self { + Self([ + 0,//(*x >> 32*4) as u32, //zero on all target platforms + 0,//(*x >> 32*3) as u32, //zero on all target platforms + 0,//(*x >> 32*2) as u32, //zero on all target platforms + x.checked_shr(32).map(|x| x as u32).unwrap_or_default(), + *x as u32, + ]) + } +} + +impl From<&usize> for ArbitraryBytes<8>{ + fn from(x: &usize) -> Self { + Self([ + 0,//(*x >> 32*7) as u32, //zero on all target platforms + 0,//(*x >> 32*6) as u32, //zero on all target platforms + 0,//(*x >> 32*5) as u32, //zero on all target platforms + 0,//(*x >> 32*4) as u32, //zero on all target platforms + 0,//(*x >> 32*3) as u32, //zero on all target platforms + 0,//(*x >> 32*2) as u32, //zero on all target platforms + x.checked_shr(32).map(|x| x as u32).unwrap_or_default(), + *x as u32, + ]) + } +} + +impl From<&u32> for ArbitraryBytes<5>{ + fn from(x: &u32) -> Self { + Self([ + 0, + 0, + 0, + 0, + *x, + ]) + } +} + +impl From<&u32> for ArbitraryBytes<8>{ + fn from(x: &u32) -> Self { + Self([ + 0, + 0, + 0, + 0, + 0, + 0, + 0, + *x, + ]) + } +} + +//workaround for lack of proper const-generic support. +trait PadWithAZero{ + type Output; + fn pad_with_a_zero(&self) -> Self::Output; +} + +impl PadWithAZero for ArbitraryBytes<5>{ + type Output = ArbitraryBytes<6>; + fn pad_with_a_zero(&self) -> Self::Output { + ArbitraryBytes::<6>([ + 0, + self.0[0], + self.0[1], + self.0[2], + self.0[3], + self.0[4], + ]) + } +} + +impl PadWithAZero for ArbitraryBytes<8>{ + type Output = ArbitraryBytes<9>; + fn pad_with_a_zero(&self) -> Self::Output { + ArbitraryBytes::<9>([ + 0, + self.0[0], + self.0[1], + self.0[2], + self.0[3], + self.0[4], + self.0[5], + self.0[6], + self.0[7], + ]) + } +} + +impl DivAssign<&usize> for ArbitraryBytes{ + //just do long division. + fn div_assign(&mut self, rhs: &usize) { + self.div_assign_with_remainder_usize(rhs); + } +} + +#[derive(Debug, Clone, Copy)] +struct ArbitraryBytesToUsizeError; +impl Display for ArbitraryBytesToUsizeError{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "conversion from arbitrary sized int-array to usize failed") + } +} +impl Error for ArbitraryBytesToUsizeError{} + +impl TryFrom> for usize{ + type Error = ArbitraryBytesToUsizeError; + + fn try_from(value: ArbitraryBytes) -> Result { + usize::try_from(&value) + } +} + +impl TryFrom<&ArbitraryBytes> for usize{ + type Error = ArbitraryBytesToUsizeError; + #[cfg(target_pointer_width = "64")] + fn try_from(value: &ArbitraryBytes) -> Result { + //64 bits. + if value.0[0..N.saturating_sub(2)].iter().any(|x| *x != 0) { + Err(ArbitraryBytesToUsizeError) + } else { + //failing to get last_bit is an actual error. + let last_bit = value.0.get(N-1).ok_or(ArbitraryBytesToUsizeError).map(|x| *x as usize); + //second-last is not an error though. + let second_last_bit = value.0.get(N-2).map(|u| (*u as usize) << 32).unwrap_or_default(); + last_bit.map(|last_bit| last_bit + second_last_bit) + } + } + #[cfg(not(target_pointer_width = "64"))] + fn try_from(value: &ArbitraryBytes) -> Result { + //16 or 32 bits. + if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { + Err(ArbitraryBytesToUsizeError) + } else { + value.0.get(N-1).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToUsizeError) + } + } +} + +#[derive(Debug, Clone, Copy)] +struct ArbitraryBytesToU32Error; +impl Display for ArbitraryBytesToU32Error{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "conversion from arbitrary sized int-array to u32 failed") + } +} +impl Error for ArbitraryBytesToU32Error{} + +impl TryFrom<&ArbitraryBytes> for u32{ + type Error = ArbitraryBytesToU32Error; + + fn try_from(value: &ArbitraryBytes) -> Result { + if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) { + Err(ArbitraryBytesToU32Error) + } else { + value.0.get(N-1).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToU32Error) + } + } +} + +impl Mul<&usize> for &ArbitraryBytes{ + type Output = Option>; + fn mul(self, rhs: &usize) -> Self::Output { + #[cfg(target_pointer_width = "64")] + type UsizeAndFour = u128; + #[cfg(not(target_pointer_width = "64"))] + type UsizeAndFour = u64; + //somewhere we need this clone, can just as well be in here... + let mut result = self.0.clone(); + let carry = result.iter_mut().rev().fold(UsizeAndFour::default(), |carry, digit|{ + assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry always has to fit in usize, otherwise something is terribly wrong. + let res = (*digit as UsizeAndFour) * (*rhs as UsizeAndFour) + carry; + *digit = res as u32; + res >> 32 + }); + if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. + None + } else { + Some(ArbitraryBytes(result)) + } + } +} + +impl RemAssignWithQuotient for ArbitraryBytes + where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PadWithAZero> +{ + fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self{ + + //This is based on Knuth, TAOCP vol 2 section 4.3, algorithm D. However, at least for now, a + //non-performing restoring version of the algorithm is used, because I'm too tired right now + //to properly implement the performing one (which would with near certainty be faster a bit). + + //well, nearly without trying to be smart. + match Ord::cmp(self, divisor){ + std::cmp::Ordering::Less => Self::from(&0_usize), //leave self unchanged, it's the remainder. + std::cmp::Ordering::Equal => { *self = Self::from(&0_usize); Self::from(&1_usize) }, + std::cmp::Ordering::Greater => { + if let Ok(divisor_as_u32) = divisor.try_into() { + self.rem_assign_with_quotient_u32(&divisor_as_u32) + } else { + self.rem_assign_with_quotient_knuth(divisor) + } + }, + } + } +} + +/// Needed by rem_assign_with_quotient_knuth +impl Mul for ArbitraryBytes{ + type Output = Option>; + fn mul(mut self, rhs: u32) -> Self::Output { + //somewhere we need this clone, can just as well be in here... + let carry = self.0.iter_mut().rev().fold(u64::default(), |carry, digit|{ + assert_eq!(carry, carry & (u32::MAX as u64)); //carry always has to fit in usize, otherwise something is terribly wrong. + let res = (*digit as u64) * (rhs as u64) + carry; + *digit = res as u32; + res >> 32 + }); + if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously. + None + } else { + Some(self) + } + } +} + +impl SubAssign<&ArbitraryBytes> for ArbitraryBytes{ + fn sub_assign(&mut self, rhs: &ArbitraryBytes) { + let carry = self.0.iter_mut().zip(rhs.0.iter()).rev().fold(0_u64,|carry,(i,s)| { + let s = (*s as u64) + carry; + if *i as u64 >= s { + *i -= s as u32; + 0 + } else { + *i = (((*i as u64) + (1_u64<<32)) - s) as u32; + 1 + } + }); + assert_eq!(carry,0); + } +} + + +impl ArbitraryBytes{ + /// Replaces self with Quotient and returns Remainder + fn div_assign_with_remainder_usize(&mut self, rhs: &usize) -> usize { + #[cfg(target_pointer_width = "64")] + type UsizeAndFour = u128; + #[cfg(not(target_pointer_width = "64"))] + type UsizeAndFour = u64; + assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128); + + let divisor : UsizeAndFour = *rhs as UsizeAndFour; + let remainder = self.0.iter_mut().fold(0 as UsizeAndFour,|carry, current| { + assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize. + let carry_shifted = carry << 32; + let dividend = (carry_shifted) + (*current as UsizeAndFour); + let ratio = dividend / divisor; + assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + *current = (ratio) as u32; + dividend - (*current as UsizeAndFour) * divisor + }); + assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour)); + remainder as usize + } + + /// Used in rem_assign_with_quotient_knuth. The normalization factor is u32, and u32 might be larger than usize. + fn div_assign_with_remainder_u32(&mut self, rhs: &u32) -> u32 { + let divisor : u64 = *rhs as u64; + let remainder = self.0.iter_mut().fold(0 as u64,|carry, current| { + assert_eq!(carry, carry & (u32::MAX as u64)); //carry has to be lower than divisor, and divisor is usize. + let carry_shifted = carry << 32; + let dividend = (carry_shifted) + (*current as u64); + let ratio = dividend / divisor; + assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero. + *current = (ratio) as u32; + dividend - (*current as u64) * divisor + }); + assert_eq!(remainder, remainder & (u32::MAX as u64)); + remainder as u32 + } + + fn rem_assign_with_quotient_u32(&mut self, divisor: &u32) -> Self where Self : for<'a> From<&'a u32> { + let remainder = self.div_assign_with_remainder_u32(divisor); + std::mem::replace(self, Self::from(&remainder)) + } + + + fn rem_assign_with_quotient_knuth(&mut self, divisor : &Self) -> Self + where Self : PadWithAZero> + + for<'a> From<&'a usize> + { + assert!(M == N+1); + //first we need to find n (number of digits in divisor) + let n_digits_divisor= N - divisor.find_first_nonzero_digit(); + assert!(n_digits_divisor > 1); + //and same in the non-normalized dividend + let m_plus_n_digits_dividend = N - self.find_first_nonzero_digit(); + let m_extra_digits_dividend = m_plus_n_digits_dividend - n_digits_divisor; + + //step D1: Normalize. This brings the maximum error for each digit down to no more than 2. + let d = ((1u64 << 32) / (1u64 + (divisor.get_digit_from_right(n_digits_divisor - 1) as u64))) as u32; + //again, missing const generics ruin all the fun. + let mut dividend = (self.pad_with_a_zero() * d).expect("Normalizing dividend failed due to overflow. Mathematically impossible."); + let divisor = (divisor.pad_with_a_zero() * d).expect("Normalizing divisor failed due to overflow. Mathematically impossible."); + + let mut quotient : Self = (&0_usize).into(); + + //needed for Step D3. + let guess_divisor = divisor.get_digit_from_right(n_digits_divisor - 1) as u64; + let divisor_second_significant_digit = divisor.get_digit_from_right(n_digits_divisor-2) as u64; + + //step D2, D7: the loop. + for j in m_extra_digits_dividend..=0 { + //Step D3: Guess a digit + let guess_dividend = ((dividend.get_digit_from_right(j+n_digits_divisor) as u64)<<32) + (dividend.get_digit_from_right(j + n_digits_divisor - 1) as u64); + let mut guesstimate = guess_dividend/guess_divisor; + let mut guess_reminder = guess_dividend % guess_divisor; + //refine this result (still step D3) + while guess_reminder <= u32::MAX as u64 + && (guesstimate > u32::MAX as u64 + || divisor_second_significant_digit * guesstimate + > (guess_reminder << 32) + (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64) + ) { + guesstimate -= 1; + guess_reminder += guess_divisor; + } + //I'm too tired to do this by the book. If this thing is gonna blow, we can just as well increase our guesstimate by one and call it a day. + //In any case, this does only happen in _very_ rare cases. Soo: + //Steps D4-D6. + assert!(guesstimate & (u32::MAX as u64) == guesstimate); //Knuth says this is a one-place number, and I trust him. + let mut guesstimate = guesstimate as u32; + let mut s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type."); + let will_overflow = + std::cmp::Ord::cmp(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]) + == Ordering::Less; + if will_overflow { + guesstimate -= 1; + s -= &divisor; + assert!(std::cmp::Ord::cmp(÷nd.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]) != Ordering::Less) + } + slice_sub_assign(&mut dividend.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]); + quotient.set_digit_from_right(guesstimate, j); + } + + //Steop D8: Compute Remainder. + dividend.div_assign_with_remainder_u32(&d); + self.0 = dividend.0[1..].try_into().expect("Conversion of what should have been an N-element slice into an N-element array failed."); + quotient + + } + + fn find_first_nonzero_digit(&self) -> usize{ + self.0.iter().enumerate().skip_while(|(_,v)| **v == 0).next().map(|(x,_)| x).unwrap_or(N) + } + + fn get_digit_from_right(&self, i : usize) -> u32{ + self.0[N-i-1] + } + fn set_digit_from_right(&mut self, val: u32, i : usize){ + self.0[N-i-1] = val; + } +} + +fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){ + assert_eq!(lhs.len(), rhs.len()); + let carry = lhs.iter_mut().zip(rhs.iter()).rev().fold(0_u64,|carry,(i,s)| { + let s = (*s as u64) + carry; + if *i as u64 >= s { + *i -= s as u32; + 0 + } else { + *i = (((*i as u64) + (1_u64<<32)) - s) as u32; + 1 + } + }); + assert_eq!(carry,0); +} \ No newline at end of file -- cgit v1.2.3