aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/passwordmaker/base_conversion/division.rs32
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion.rs144
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl.rs443
-rw-r--r--src/passwordmaker/base_conversion/mod.rs6
-rw-r--r--src/passwordmaker/base_conversion/remainders.rs37
-rw-r--r--src/passwordmaker/base_conversion/remainders_impl.rs2
6 files changed, 628 insertions, 36 deletions
diff --git a/src/passwordmaker/base_conversion/division.rs b/src/passwordmaker/base_conversion/division.rs
new file mode 100644
index 0000000..c6fc911
--- /dev/null
+++ b/src/passwordmaker/base_conversion/division.rs
@@ -0,0 +1,32 @@
+/// A trait that combines std::ops::Div and std::ops::Rem, as those can often be computed together.
+pub(super) trait Division<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<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()
+ }
+}
+
+pub(super) struct DivisionResult<T, U> {
+ pub result : T,
+ pub remainder : U,
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs
new file mode 100644
index 0000000..94d28c0
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion.rs
@@ -0,0 +1,144 @@
+//! This module aims to provide iterative computation of the base-converted result, starting at the
+//! most significant digit.
+//!
+//! # Warning
+//! This is optimized for passwordmaker-rs domain specific number ranges. If you want to use this
+//! somewhere else, make sure to adapt some maths. For instance you might want to early-out for leading zeros.
+//!
+//! The maths is not great, sorry. It's way easier to start at the least significant digit...
+//! If you have any great idea how to improve it: Make a merge request!
+
+use std::convert::TryInto;
+use std::ops::{Mul, DivAssign};
+use std::iter::successors;
+
+pub(super) struct IterativeBaseConversion<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]);
+ }
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
new file mode 100644
index 0000000..be1d851
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
@@ -0,0 +1,443 @@
+//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N].
+
+//Reminder for myself: The traits needed are:
+// where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One.
+// for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_potency
+// RemAssignWithQuotient+ //used to get the result of each step.
+// TryInto<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};
+
+use super::iterative_conversion::RemAssignWithQuotient;
+
+//Type to be used as V, with usize as B.
+struct SixteenBytes(u128);
+
+//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)]
+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.
+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)]
+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)]
+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|{
+ 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 {
+ //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<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
+ }
+ });
+ assert_eq!(carry,0);
+ }
+}
+
+
+impl<const N : usize> ArbitraryBytes<N>{
+ /// 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<const M : usize>(&mut self, divisor : &Self) -> Self
+ where Self : PadWithAZero<Output = ArbitraryBytes<M>> +
+ 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(&dividend.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(&dividend.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]) != Ordering::Less)
+ }
+ slice_sub_assign(&mut dividend.0[(M - 1 - (j+n_digits_divisor))..=(M - 1 - j)], &s.0[(M - 1 - n_digits_divisor)..=(M - 1)]);
+ quotient.set_digit_from_right(guesstimate, j);
+ }
+
+ //Steop D8: Compute Remainder.
+ dividend.div_assign_with_remainder_u32(&d);
+ self.0 = dividend.0[1..].try_into().expect("Conversion of what should have been an N-element slice into an N-element array failed.");
+ quotient
+
+ }
+
+ fn find_first_nonzero_digit(&self) -> usize{
+ self.0.iter().enumerate().skip_while(|(_,v)| **v == 0).next().map(|(x,_)| x).unwrap_or(N)
+ }
+
+ fn get_digit_from_right(&self, i : usize) -> u32{
+ self.0[N-i-1]
+ }
+ fn set_digit_from_right(&mut self, val: u32, i : usize){
+ self.0[N-i-1] = val;
+ }
+}
+
+fn slice_sub_assign(lhs : &mut [u32], rhs: &[u32]){
+ assert_eq!(lhs.len(), rhs.len());
+ let carry = lhs.iter_mut().zip(rhs.iter()).rev().fold(0_u64,|carry,(i,s)| {
+ let s = (*s as u64) + carry;
+ if *i as u64 >= s {
+ *i -= s as u32;
+ 0
+ } else {
+ *i = (((*i as u64) + (1_u64<<32)) - s) as u32;
+ 1
+ }
+ });
+ assert_eq!(carry,0);
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index 8d217ef..4ae7653 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -1,6 +1,10 @@
use std::convert::TryInto;
-use self::remainders::CalcRemainders;
+use remainders::CalcRemainders;
+
+mod division;
+mod iterative_conversion;
+mod iterative_conversion_impl;
mod remainders;
mod remainders_impl;
diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs
index 93570a1..344fab2 100644
--- a/src/passwordmaker/base_conversion/remainders.rs
+++ b/src/passwordmaker/base_conversion/remainders.rs
@@ -1,22 +1,10 @@
-/// Adds `calc_remainders(divisor)` method to types that have some implementation of the Division trait.
+use super::division::{Division, DivisionResult};
+
+/// Trait used for the old base conversion.
pub(super) trait CalcRemainders<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>
{
@@ -52,23 +40,4 @@ impl<U, T:Division<U>> Iterator for Remainders<T,U>{
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
index 7de2189..c2431bb 100644
--- a/src/passwordmaker/base_conversion/remainders_impl.rs
+++ b/src/passwordmaker/base_conversion/remainders_impl.rs
@@ -1,4 +1,4 @@
-use super::remainders::{Division, UseGenericDivision, DivisionResult};
+use super::division::{Division, UseGenericDivision, DivisionResult};
impl UseGenericDivision for u128{} //for Md4, Md5
generated by cgit v1.2.3 (git 2.46.0) at 2025-09-18 23:23:41 +0000