aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Cargo.toml2
-rw-r--r--src/lib.rs3
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion.rs162
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl.rs898
-rw-r--r--src/passwordmaker/base_conversion/mod.rs53
-rw-r--r--src/passwordmaker/base_conversion/remainders.rs74
-rw-r--r--src/passwordmaker/base_conversion/remainders_impl.rs76
-rw-r--r--src/passwordmaker/mod.rs56
8 files changed, 1123 insertions, 201 deletions
diff --git a/Cargo.toml b/Cargo.toml
index ac0ea6f..24363ab 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -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"
diff --git a/src/lib.rs b/src/lib.rs
index a005e43..2548c46 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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..6716228
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion.rs
@@ -0,0 +1,162 @@
+//! 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.
+ Mul<&'a V, Output = Option<V>>
+{
+ 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> {
+ 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, |(potency, count)| (potency * base).map(|v| (v, count +1)))
+ .last()
+ .expect("Cannot fail, first entry is Some (required V : From<B>) and there's no filtering.");
+ PotencyAndExponent{ potency : result.0, count : result.1 + 1 }
+ }
+}
+
+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(crate) 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 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 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..76fd32e
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl.rs
@@ -0,0 +1,898 @@
+//! 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.
+
+use std::ops::{DivAssign, Mul};
+use std::convert::{TryFrom, TryInto};
+use std::fmt::Display;
+use std::error::Error;
+use std::iter::once;
+
+use super::iterative_conversion::RemAssignWithQuotient;
+
+//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)
+ }
+}
+
+//--------------------------------------------------------------------------------------------------------------------------------------
+//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(crate) trait PadWithAZero{
+ type Output;
+ fn pad_with_a_zero(&self) -> Self::Output;
+}
+
+impl PadWithAZero for ArbitraryBytes<5>{
+ type Output = ArbitraryBytes<6>;
+ fn pad_with_a_zero(&self) -> Self::Output {
+ ArbitraryBytes::<6>([
+ 0,
+ self.0[0],
+ self.0[1],
+ self.0[2],
+ self.0[3],
+ self.0[4],
+ ])
+ }
+}
+
+impl PadWithAZero for ArbitraryBytes<8>{
+ type Output = ArbitraryBytes<9>;
+ fn pad_with_a_zero(&self) -> Self::Output {
+ ArbitraryBytes::<9>([
+ 0,
+ self.0[0],
+ self.0[1],
+ self.0[2],
+ self.0[3],
+ self.0[4],
+ self.0[5],
+ self.0[6],
+ self.0[7],
+ ])
+ }
+}
+
+impl<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();
+ 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 {
+ ($t:ty, $long_t:ty) => {
+ impl<const N : usize> Mul<$t> for ArbitraryBytes<N>{
+ type Output = Option<ArbitraryBytes<N>>;
+ fn mul(mut self, rhs: $t) -> Self::Output {
+ let carry = self.0.iter_mut().rev().fold(<$long_t>::default(), |carry, digit|{
+ debug_assert_eq!(carry, carry & (<$t>::MAX as $long_t)); //carry always has to fit in usize, otherwise something is terribly wrong.
+ let res = (*digit as $long_t) * (rhs as $long_t) + 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)
+ }
+ }
+ }
+ };
+}
+make_mul!(u32,u64);
+#[cfg(target_pointer_width = "64")]
+make_mul!(usize, u128);
+#[cfg(not(target_pointer_width = "64"))]
+make_mul!(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)
+ }
+}
+
+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+1)], &p.0[(N-1-i)..])
+ });
+ carry.filter(|x| !x).map(|_|())
+ });
+ no_overflow.map(|_| 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.
+ //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 : 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, but is the same for all iterations -> factored out.
+ let guess_divisor = divisor.get_digit_from_right(n_digits_divisor - 1) as u64;
+ let divisor_second_significant_digit = divisor.get_digit_from_right(n_digits_divisor-2) as u64;
+
+ //step D2, D7: the loop.
+ for j in (0..=m_extra_digits_dividend).rev() {
+ //Step D3: Guess a digit
+ let guess_dividend = u64_from_u32s(dividend.get_digit_from_right(j+n_digits_divisor), dividend.get_digit_from_right(j + n_digits_divisor - 1));
+ let mut guesstimate = guess_dividend/guess_divisor;
+ let mut guess_reminder = guess_dividend % guess_divisor;
+ //refine our guesstimate (still step D3). Ensures that error of guesstimate is either 0 or +1.
+ while guess_reminder <= u32::MAX as u64
+ && (guesstimate > u32::MAX as u64
+ || divisor_second_significant_digit * guesstimate
+ > (guess_reminder << 32) | (dividend.get_digit_from_right(j + n_digits_divisor - 2) as u64)
+ ) {
+ guesstimate -= 1;
+ guess_reminder += guess_divisor;
+ }
+ //Step D4: Pretend the guess was correct and subtract guesstimate * divisor from dividend.
+ debug_assert!(guesstimate & (u32::MAX as u64) == guesstimate, "The while above should have made guesstimate a one-digit number. Debug!");
+ let mut guesstimate = guesstimate as u32;
+ let s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type.");
+ let s_range = (M - 1 - n_digits_divisor)..M;
+ let d_range = (s_range.start - j)..(s_range.end - j);
+ let did_overflow = slice_overflowing_sub_assign(&mut dividend.0[d_range.clone()], &s.0[s_range.clone()]);
+ //Step D5: If guesstimate was incorrect, the subtraction has overflown. The result is wrapped in such a case.
+ if did_overflow {
+ //Step D6: We have to correct our guesstimate. It was too large by one. We also have to fix the overflow that has occured.
+ guesstimate -= 1;
+ //The addition must overflow again. The two overflows cancel out, and since we are using wrapping arithmetics, the result becomes correct again.
+ let did_overflow = slice_overflowing_add_assign(&mut dividend.0[d_range.clone()], &divisor.0[s_range.clone()]);
+ debug_assert!(did_overflow, "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.")
+ }
+ quotient.set_digit_from_right(guesstimate, j);
+ }
+
+ //Steop D8: Compute Remainder.
+ self.0 = dividend.shift_right(normalize_shift).0[1..].try_into()
+ .expect("Conversion of what should have been an N-element slice into an N-element array failed.");
+ quotient
+
+ }
+
+ fn find_first_nonzero_digit(&self) -> usize{
+ self.0.iter().enumerate().skip_while(|(_,v)| **v == 0).next().map(|(x,_)| x).unwrap_or(N)
+ }
+
+ fn get_digit_from_right(&self, i : usize) -> u32{
+ self.0[N-i-1]
+ }
+ fn set_digit_from_right(&mut self, val: u32, i : usize){
+ self.0[N-i-1] = val;
+ }
+
+ fn shift_left<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_overflowing_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{
+ debug_assert_eq!(lhs.len(), rhs.len());
+ lhs.iter_mut().zip(rhs.iter()).rev().fold(false,|carry,(a,b)| {
+ let r = b.overflowing_add(carry as u32);
+ let s = a.overflowing_sub(r.0);
+ *a = s.0;
+ r.1 || s.1
+ })
+}
+
+fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool {
+ debug_assert_eq!(lhs.len(), rhs.len());
+ lhs.iter_mut().zip(rhs.iter()).rev().fold(false, |carry, (a, b)| {
+ let r = b.overflowing_add(carry as u32);
+ let s = a.overflowing_add(r.0);
+ *a = s.0;
+ r.1 || s.1
+ })
+}
+
+fn u64_from_u32s(msb : u32, lsb : u32) -> u64{
+ let msb = msb as u64;
+ let lsb = lsb as u64;
+ (msb << 32) | lsb
+}
+
+#[cfg(test)]
+mod arbitrary_bytes_tests{
+ use super::*;
+ use rand::RngCore;
+ use rand_xoshiro::rand_core::SeedableRng;
+ use rand_xoshiro::Xoshiro256Plus;
+
+ /// Tests specifically the case that will_overflow is true.
+ #[test]
+ fn knuth_add_back_test(){
+ let mut dividend = ArbitraryBytes::new([
+ //m = 3, n=5
+ u32::MAX,
+ u32::MAX,
+ u32::MAX-1,
+ u32::MAX,
+ u32::MAX,
+ 0,
+ 0,
+ 3
+ ]);
+ let divisor = ArbitraryBytes::new([
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ u32::MAX,
+ u32::MAX,
+ u32::MAX,
+ ]);
+ let result = dividend.rem_assign_with_quotient(&divisor);
+ assert_eq!(dividend.0, [0,0,0,0,0,0,0,2]);
+ assert_eq!(result.0, [0,0,0,u32::MAX,u32::MAX, u32::MAX, u32::MAX, u32::MAX]);
+ }
+
+
+ fn prepare_many_numbers(max_dividend_digits : u32, min_dividend_digits : u32, max_divisor_digits : u32, min_divisor_digits : u32) -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{
+ assert!(max_dividend_digits < 5);
+ assert!(min_dividend_digits <= max_dividend_digits);
+ assert!(max_divisor_digits < 5);
+ assert!(min_divisor_digits <= max_divisor_digits);
+ let mut rng = Xoshiro256Plus::seed_from_u64(0);
+ let mut res = Vec::new();
+ for _i in 0..1000000 {
+ let dx = rng.next_u32() % (max_dividend_digits + 1 - min_dividend_digits) + min_dividend_digits;
+ let dy = rng.next_u32() % (max_divisor_digits + 1 - min_divisor_digits) + min_divisor_digits;
+ let ds = dx.min(dy);
+ let dl = dx.max(dy);
+ let dividendx = [
+ 0,
+ if dl >= 4 { rng.next_u32() } else { 0 },
+ if dl >= 3 { rng.next_u32() } else { 0 },
+ if dl >= 2 { rng.next_u32() } else { 0 },
+ if dl >= 1 { rng.next_u32() } else { 0 },
+ ];
+ let divisorx = [
+ 0,
+ if ds >= 4 { rng.next_u32() } else { 0 },
+ if ds >= 3 { rng.next_u32() } else { 0 },
+ if ds >= 2 { rng.next_u32() } else { 0 },
+ if ds >= 1 { rng.next_u32() } else { 0 },
+ ];
+ let needs_swap = ds == dl && dividendx[5-ds as usize] < divisorx[5-ds as usize];
+ let dividend = ArbitraryBytes::new(if needs_swap {divisorx} else {dividendx});
+ let divisor = ArbitraryBytes::new(if needs_swap {dividendx} else {divisorx});
+ assert!(dividend.ge(&divisor));
+
+ let td =
+ ((dividend.0[1] as u128)<<96)
+ + ((dividend.0[2] as u128)<<64)
+ + ((dividend.0[3] as u128)<<32)
+ + (dividend.0[4] as u128);
+ let tn =
+ ((divisor.0[1] as u128)<<96)
+ + ((divisor.0[2] as u128)<<64)
+ + ((divisor.0[3] as u128)<<32)
+ + (divisor.0[4] as u128);
+
+
+ res.push((dividend, divisor, td/tn, td%tn));
+ }
+ res
+ }
+
+ /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.)
+ #[test]
+ fn rem_assign_with_quotient_knuth_many_numbers_test() {
+ let input = prepare_many_numbers(4,2, 4, 2);
+ for (mut dividend, divisor, expected_quotient, expexted_remainder) in input {
+ let quotient = dividend.rem_assign_with_quotient_knuth(&divisor);
+ let remainder = dividend;
+ let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128);
+ let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128);
+ assert_eq!(quotient, expected_quotient);
+ assert_eq!(remainder, expexted_remainder);
+ }
+ }
+ /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.)
+ #[test]
+ fn rem_assign_with_quotient_many_numbers_test() {
+ let input = prepare_many_numbers(4,1, 4, 1);
+ for (mut dividend, divisor, expected_quotient, expexted_remainder) in input {
+ let quotient = dividend.rem_assign_with_quotient(&divisor);
+ let remainder = dividend;
+ let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128);
+ let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128);
+ assert_eq!(quotient, expected_quotient);
+ assert_eq!(remainder, expexted_remainder);
+ }
+ }
+
+ #[test]
+ fn rem_assign_with_quotient_u32_many_numbers_test() {
+ let input = prepare_many_numbers(4,1, 1, 1);
+ for (mut dividend, divisor, expected_quotient, expexted_remainder) in input {
+ let quotient = dividend.rem_assign_with_quotient_u32(&divisor.0.last().unwrap());
+ let remainder = dividend;
+ let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128);
+ let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128);
+ assert_eq!(quotient, expected_quotient);
+ assert_eq!(remainder, expexted_remainder);
+ }
+ }
+
+ #[test]
+ fn rem_assign_with_quotient_u32_test(){
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let quotient = a.rem_assign_with_quotient_u32(&0x12345);
+ assert_eq!(quotient.0, [0x9A10,0xB282B7BA,0xE4948E98,0x2AE63D74,0xE6FDFF4A]);
+ assert_eq!(a.0, [0,0,0,0,0x6882]);
+ }
+
+ #[test]
+ fn rem_assign_with_quotient_u32_test2(){
+ let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]);
+ let quotient = a.rem_assign_with_quotient_u32(&0x12345);
+ assert_eq!(quotient.0, [0,0,0,0,0]);
+ assert_eq!(a.0, [0,0,0,0,0x1234]);
+ }
+
+ #[test]
+ fn div_assign_with_remainder_usize_test(){
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let remainder = a.div_assign_with_remainder_usize(&0x1234_usize);
+ assert_eq!(a.0, [0x9A135,0x79AA8650,0xD251DC7A,0x9AA8C1F2,0x8B9729EF]);
+ assert_eq!(remainder, 0x2E8);
+ }
+
+ #[test]
+ fn div_assign_with_remainder_usize_test2(){
+ let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]);
+ let remainder = a.div_assign_with_remainder_usize(&0x1235_usize);
+ assert_eq!(a.0, [0,0,0,0,0]);
+ assert_eq!(remainder, 0x1234);
+ }
+
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn div_assign_with_remainder_usize_test3(){
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let remainder = a.div_assign_with_remainder_usize(&0x123456789ab_usize);
+ assert_eq!(a.0, [0,0x9A107B,0xBEC8B35A,0xEC9D3B43,0x056F803A]);
+ assert_eq!(remainder, 0xD7537A4B6);
+ }
+
+ #[test]
+ fn sub_assign_test() {
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let b = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let carry = slice_overflowing_sub_assign(&mut a.0,&b.0);
+ assert!(!carry);
+ assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]);
+ }
+
+ #[test]
+ fn sub_assign_test2() {
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let carry = slice_overflowing_sub_assign(&mut a.0,&b.0);
+ assert!(carry);
+ assert_eq!(a.0, [0x935D3D98,0x4BEB08CB,0x4CF2240D,0xCA49E363,0xB0268A9E]);
+ }
+
+ #[test]
+ fn add_assign_test() {
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let carry = slice_overflowing_add_assign(&mut a.0,&b.0);
+ assert!(!carry);
+ assert_eq!(a.0, [0xF1F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]);
+ }
+ #[test]
+ fn add_assign_test2() {
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = ArbitraryBytes::new([0xbf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let carry = slice_overflowing_add_assign(&mut a.0,&b.0);
+ assert!(carry);
+ assert_eq!(a.0, [0x01F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]);
+ }
+
+ #[test]
+ fn shift_left_test() {
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = a.shift_left(7);
+ assert_eq!(b.0,[0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]);
+ }
+
+ #[test]
+ fn shift_right_test() {
+ let a = ArbitraryBytes::new([0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]);
+ let b = a.shift_right(7);
+ assert_eq!(b.0,[0, 0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ }
+
+ #[test]
+ fn get_digit_from_right_test(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ assert_eq!(a.get_digit_from_right(3), 0xffffffff);
+ }
+
+ #[test]
+ fn set_digit_from_right_test(){
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ a.set_digit_from_right(0xdeadbeef, 4);
+ assert_eq!(a.0[0], 0xdeadbeef);
+ }
+
+ #[test]
+ fn find_first_nonzero_digit_test() {
+ let a = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]);
+ assert_eq!(a.find_first_nonzero_digit(),3);
+ }
+
+ #[test]
+ fn mul_arbitrary_test(){
+ let a = ArbitraryBytes::new([0,0,0,0x47ea7314,0xfba75574]);
+ let b = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]);
+ let a_big = (0x47ea7314_u128 << 32) | 0xfba75574u128;
+ let b_big = (0x12345678_u128 << 32) | 0xabcde012u128;
+ let c_big = a_big*b_big;
+ let c = (&a * &b).unwrap();
+ assert_eq!(c_big & 0xffff_ffff, c.0[4] as u128 );
+ assert_eq!((c_big >> 32 ) & 0xffff_ffff, c.0[3] as u128);
+ assert_eq!((c_big >> 64 ) & 0xffff_ffff, c.0[2] as u128);
+ assert_eq!((c_big >> 96 ) & 0xffff_ffff, c.0[1] as u128);
+ assert_eq!(0, c.0[0]);
+ }
+ #[test]
+ fn mul_arbitrary_test_2(){
+ let a = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let b = ArbitraryBytes::new([0,0,0,0,2]);
+ let c = (&a * &b).unwrap();
+ assert_eq!(0x4EC7593F, c.0[0]);
+ assert_eq!(0xA35C3E70, c.0[1]);
+ assert_eq!(2*0x1753a5c7, c.0[2]);
+ assert_eq!(0x8fd4e629, c.0[3]);
+ assert_eq!(0xf74eaae8, c.0[4]);
+ }
+ #[test]
+ fn mul_arbitrary_test_3(){
+ let a = ArbitraryBytes::new([0,0,0,0,2]);
+ let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = (&a * &b).unwrap();
+ assert_eq!(0x4EC7593F, c.0[0]);
+ assert_eq!(0xA35C3E70, c.0[1]);
+ assert_eq!(2*0x1753a5c7, c.0[2]);
+ assert_eq!(0x8fd4e629, c.0[3]);
+ assert_eq!(0xf74eaae8, c.0[4]);
+ }
+ #[test]
+ fn mul_arbitrary_test_4(){
+ let a = ArbitraryBytes::new([0,0,0,0,8]);
+ let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = &a * &b;
+ assert!(c.is_none())
+ }
+ #[test]
+ fn mul_arbitrary_test_5(){
+ let a = ArbitraryBytes::new([0,0,0,1,0]);
+ let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = &a * &b;
+ assert!(c.is_none())
+ }
+ #[test]
+ fn mul_arbitrary_test_6(){
+ let a = ArbitraryBytes::new([0,0,0,1,1]);
+ let b = ArbitraryBytes::new([0,0xffffffff,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = &a * &b;
+ assert!(c.is_none())
+ }
+
+ #[test]
+ fn mul_with_u32_test(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 3u32;
+ let product = a*b;
+ assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036])
+ }
+ #[test]
+ fn mul_with_u32_test2(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 4u32;
+ let product = a*b;
+ assert!(product.is_none())
+ }
+ #[test]
+ fn mul_with_usize_test_working(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 3usize;
+ let product = a*b;
+ assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036])
+ }
+ #[test]
+ fn mul_with_usize_test_overflow(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 4usize;
+ let product = a*b;
+ assert!(product.is_none())
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn mul_with_usize_test_64bit_works(){
+ let a = ArbitraryBytes::new([0,0,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 0x123456789ausize;
+ let product = a*b;
+ assert_eq!(product.unwrap().0, [0xE,0x28130BBC,0x7442D257,0x1FEDDF10,0xC8ED3AD4])
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn mul_with_usize_test_64bit_overflow(){
+ let a = ArbitraryBytes::new([0,0x1,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = usize::MAX;
+ let product = a*b;
+ assert!(product.is_none())
+ }
+ #[test]
+ fn try_into_u32_test(){
+ let a = ArbitraryBytes::new([0,0,0,0,0xabcde012]);
+ let b : u32 = (&a).try_into().unwrap();
+ assert_eq!(b, 0xabcde012);
+ }
+ #[test]
+ fn try_into_u32_test_overflows(){
+ let a = ArbitraryBytes::new([0,0,0,0x1,0xabcde012]);
+ let b : Result<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));
+ }
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index 8d217ef..dc98c92 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -1,56 +1,61 @@
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 {
- // 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()
+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 +64,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 390836a..61a0a95 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,9 +201,15 @@ fn combine_prefix_password_suffix<'a, T : Iterator<Item=Grapheme<'a>>>(password:
result
}
+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>>,
@@ -217,21 +224,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 +321,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
generated by cgit v1.2.3 (git 2.46.0) at 2025-09-18 22:46:53 +0000