aboutsummaryrefslogtreecommitdiff
path: root/src/passwordmaker/base_conversion
diff options
context:
space:
mode:
Diffstat (limited to 'src/passwordmaker/base_conversion')
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion.rs200
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs1011
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs72
-rw-r--r--src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs126
-rw-r--r--src/passwordmaker/base_conversion/mod.rs54
-rw-r--r--src/passwordmaker/base_conversion/remainders.rs74
-rw-r--r--src/passwordmaker/base_conversion/remainders_impl.rs76
7 files changed, 1440 insertions, 173 deletions
diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs
new file mode 100644
index 0000000..c8c121c
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion.rs
@@ -0,0 +1,200 @@
+//! This module aims to provide iterative computation of the base-converted result, starting at the
+//! most significant digit.
+//!
+//! # Warning
+//! This is optimized for passwordmaker-rs domain specific number ranges. If you want to use this
+//! somewhere else, make sure to adapt some maths. For instance you might want to early-out for leading zeros.
+//!
+//! The maths is not great, sorry. It's way easier to start at the least significant digit...
+//! If you have any great idea how to improve it: Make a merge request!
+
+use std::convert::TryInto;
+use std::ops::{Mul, DivAssign, MulAssign};
+use std::iter::successors;
+
+pub(crate) struct IterativeBaseConversion<V,B>{
+ current_value : V,
+ current_base_power : V,
+ remaining_digits : usize,
+ base : B,
+ switch_to_multiplication : bool, //count the number of divisions. After 1, current_value is smaller than max_base_power. After 2, it's safe to mutliply current_value by base.
+}
+
+#[allow(clippy::trait_duplication_in_bounds)] //That's obviously a false-positive in clippy...
+impl<V,B> IterativeBaseConversion<V,B>
+ where V: for<'a> From<&'a B> + //could be replaced by num::traits::identities::One.
+ PrecomputedMaxPowers<B>,
+ for<'a> &'a V : Mul<&'a B, Output = Option<V>> + //used to get the first current_base_power.
+ Mul<&'a V, Output = Option<V>>
+{
+ pub(super) fn new(value : V, base : B) -> Self{
+ let PowerAndExponent{power : current_base_power, exponent : highest_fitting_exponent} = Self::find_highest_fitting_power(&base);
+ Self{
+ current_value : value,
+ current_base_power,
+ remaining_digits: highest_fitting_exponent + 1, //to the power of 0 is a digit too. Soo, if base^n is the largest fitting exponent, n+1 digits.
+ base,
+ switch_to_multiplication: false
+ }
+ }
+
+ #[allow(clippy::map_unwrap_or)] //current code seems to be measurably faster.
+ fn find_highest_fitting_power(base : &B) -> PowerAndExponent<V> {
+ V::lookup(base).map(|(power,count)| PowerAndExponent{ power, exponent: count })
+ .unwrap_or_else(|| Self::find_highest_fitting_power_non_cached(base))
+ }
+
+ //public for unit tests in cache, which is not a sub-module of this.
+ pub(super) fn find_highest_fitting_power_non_cached(base : &B) -> PowerAndExponent<V> {
+ let base_v = base.into();
+
+ let exp_result = successors(Some((base_v, 1)), |(p, e)| {
+ Some(((p*p)?, 2*e))
+ }).last();
+
+
+ let result = successors(exp_result, |(power, count)| (power * base).map(|v| (v, count + 1)))
+ .last()
+ .expect("Cannot fail, first entry is Some (required V : From<B>) and there's no filtering.");
+ PowerAndExponent{ power : result.0, exponent : result.1 }
+ }
+}
+
+impl<V,B> std::iter::Iterator for IterativeBaseConversion<V,B>
+ where V : for<'a> DivAssign<&'a B> + //used in the first iteration to ensure that MulAssign cannot overflow.
+ RemAssignWithQuotient+ //used to get the result of each step.
+ TryInto<B>+ //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong.
+ for<'a> MulAssign<&'a B> //used instead of DivAssign after one iteration. it's faster to mul the dividend than div the divisor.
+{
+ type Item = B;
+
+ #[allow(clippy::assign_op_pattern)] //measurable performance difference. No, this doesn't make sense.
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.remaining_digits == 0 {
+ None
+ } else {
+ let result = self.current_value.rem_assign_with_quotient(&self.current_base_power);
+
+ if self.switch_to_multiplication {
+ //mul_assign is in principle dangerous.
+ //Since we do two rem_assign_with_quotient calls first, we can be sure that the result is always smaller than base^max_power though.
+ self.current_value *= &self.base;
+ } else {
+ self.current_base_power /= &self.base;
+ self.switch_to_multiplication = true;
+ }
+ self.remaining_digits = self.remaining_digits - 1;
+
+ //this cannot ever yield None.
+ result.try_into().ok()
+ }
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (self.remaining_digits, Some(self.remaining_digits))
+ }
+}
+
+impl<V,B> std::iter::ExactSizeIterator for IterativeBaseConversion<V,B>
+ where IterativeBaseConversion<V,B> : Iterator
+{}
+
+pub(super) struct PowerAndExponent<V>{
+ pub(super) power : V,
+ pub(super) exponent : usize,
+}
+
+pub(crate) trait RemAssignWithQuotient{
+ /// Replaces self with remainder of division, and returns quotient.
+ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self;
+}
+
+pub(crate) trait PrecomputedMaxPowers<B> where Self : Sized{
+ fn lookup(_base : &B) -> Option<(Self, usize)> { None }
+}
+
+//tests general behaviour, using primitive types.
+#[cfg(test)]
+mod iterative_conversion_tests{
+ use std::{ops::Mul, convert::{From, TryFrom}};
+
+ use super::*;
+
+ #[derive(Debug,Clone)]
+ struct MyU128(u128);
+ impl Mul<&u64> for &MyU128 {
+ type Output = Option<MyU128>;
+ fn mul(self, rhs: &u64) -> Self::Output {
+ self.0.checked_mul(*rhs as u128).map(|s| MyU128(s))
+ }
+ }
+
+ impl Mul<&MyU128> for &MyU128 {
+ type Output = Option<MyU128>;
+ fn mul(self, rhs: &MyU128) -> Self::Output {
+ self.0.checked_mul(rhs.0).map(|s| MyU128(s))
+ }
+ }
+
+ impl MulAssign<&u64> for MyU128 {
+ fn mul_assign(&mut self, rhs: &u64) {
+ self.0.mul_assign(*rhs as u128);
+ }
+ }
+
+ impl RemAssignWithQuotient for MyU128{
+ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self {
+ let quotient = self.0 / divisor.0;
+ self.0 %= divisor.0;
+ Self(quotient)
+ }
+ }
+ impl From<&u64> for MyU128{
+ fn from(v: &u64) -> Self {
+ MyU128(v.clone() as u128)
+ }
+ }
+
+ impl DivAssign<&u64> for MyU128{
+ fn div_assign(&mut self, rhs: &u64) {
+ self.0 = self.0 / (*rhs as u128);
+ }
+ }
+
+ impl TryFrom<MyU128> for u64{
+ type Error = std::num::TryFromIntError;
+
+ fn try_from(value: MyU128) -> Result<Self, Self::Error> {
+ value.0.try_into()
+ }
+ }
+
+ impl PrecomputedMaxPowers<u64> for MyU128{}
+
+ #[test]
+ fn test_simple_u128_to_hex_conversion(){
+ let i = IterativeBaseConversion::new(MyU128(12345678u128), 16u64);
+ assert_eq!(i.len(), 32);
+ assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), vec![0xB, 0xC, 0x6, 0x1, 0x4, 0xE]);
+ }
+ #[test]
+ fn test_simple_u128_to_base_17_conversion(){
+ let i = IterativeBaseConversion::new(MyU128(1234567890123456789u128), 17u64);
+ assert_eq!(i.len(), 32);
+ assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), vec![7, 5, 0xA, 0x10, 0xC, 0xC, 3, 0xD, 3, 0xA, 3,8,4,8,3]);
+ }
+ #[test]
+ fn test_simple_u128_to_base_39_conversion(){
+ let i = IterativeBaseConversion::new(MyU128(1234567890123456789u128), 39u64);
+ assert_eq!(i.len(), 25);
+ // 3YPRS4FaC1KU
+ assert_eq!(i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>(), vec![3, 34, 25, 27, 28, 4, 15, 36, 12, 1, 20, 30]);
+ }
+ #[test]
+ fn test_overflow_in_switch_to_multiplication(){
+ //This should simply not overflow ever.
+ let i = IterativeBaseConversion::new(MyU128(u128::MAX), 40);
+ let result = i.skip_while(|x| *x == 0_u64).collect::<Vec<_>>();
+ assert_eq!(result, vec![1, 8, 14, 11, 10, 3, 37, 5, 26, 17, 14, 0, 23, 37, 35, 24, 3, 11, 27, 20, 34, 18, 12, 6, 15]);
+ }
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
new file mode 100644
index 0000000..b805272
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/mod.rs
@@ -0,0 +1,1011 @@
+//! Implementation of iterative conversion support for the types we need it for: u128 and [u32;N].
+//! Beware that all functions in this module are optimized for the use cases of passwordmaker-rs. They may or may not
+//! be suitable for anything else.
+
+//let's start with the simple case: u128
+//we do need a NewType here, because actual u128 already has a Mul<&usize> implementation that does not match the version we want.
+#[cfg(feature="precomputed_max_powers")]
+mod precomputed_constants;
+#[cfg(all(not(feature="precomputed_max_powers"),feature="precomputed_common_max_powers"))]
+mod precomputed_common_constants;
+
+use std::ops::{DivAssign, Mul, MulAssign};
+use std::convert::{TryFrom, TryInto};
+use std::fmt::Display;
+use std::error::Error;
+
+use super::iterative_conversion::{RemAssignWithQuotient, PrecomputedMaxPowers};
+
+//Type to be used as V, with usize as B.
+pub(crate) struct SixteenBytes(u128);
+
+impl SixteenBytes{
+ pub(super) fn new(value : u128) -> Self {
+ SixteenBytes(value)
+ }
+}
+
+//just for convenience
+impl From<u128> for SixteenBytes{
+ fn from(x: u128) -> Self {
+ SixteenBytes(x)
+ }
+}
+impl From<&usize> for SixteenBytes{
+ fn from(x: &usize) -> Self {
+ SixteenBytes(*x as u128)
+ }
+}
+impl DivAssign<&usize> for SixteenBytes{
+ fn div_assign(&mut self, rhs: &usize) {
+ self.0 /= *rhs as u128;
+ }
+}
+impl RemAssignWithQuotient for SixteenBytes{
+ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self {
+ let quotient = self.0 / divisor.0;
+ self.0 %= divisor.0;
+ Self(quotient)
+ }
+}
+impl TryFrom<SixteenBytes> for usize{
+ type Error = std::num::TryFromIntError;
+ fn try_from(value: SixteenBytes) -> Result<Self, Self::Error> {
+ value.0.try_into()
+ }
+}
+impl Mul<&usize> for &SixteenBytes{
+ type Output = Option<SixteenBytes>;
+ fn mul(self, rhs: &usize) -> Self::Output {
+ self.0.checked_mul(*rhs as u128).map(Into::into)
+ }
+}
+
+impl Mul<&SixteenBytes> for &SixteenBytes{
+ type Output = Option<SixteenBytes>;
+
+ fn mul(self, rhs: &SixteenBytes) -> Self::Output {
+ self.0.checked_mul(rhs.0).map(Into::into)
+ }
+}
+
+impl MulAssign<&usize> for SixteenBytes {
+ fn mul_assign(&mut self, rhs: &usize) {
+ self.0 *= *rhs as u128;
+ }
+}
+
+impl PrecomputedMaxPowers<usize> for SixteenBytes{}
+
+//--------------------------------------------------------------------------------------------------------------------------------------
+//and now the hard part: The same for [u32;N].
+//We cannot directly implement all the Foreign traits on arrays directly. So, newtypes again.
+
+#[derive(PartialEq, PartialOrd, Ord, Eq, Clone, Debug)]
+pub(crate) struct ArbitraryBytes<const N : usize>([u32;N]);
+
+#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))]
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{}
+#[cfg(not(any(feature="precomputed_max_powers", feature="precomputed_common_max_powers")))]
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{}
+
+#[allow(clippy::cast_possible_truncation)]
+const fn from_usize<const N : usize>(x : usize) -> ArbitraryBytes<N> {
+ let mut result = [0;N]; //from Godbolt it looks like the compiler is smart enough to skip the unnecessary inits.
+ #[cfg(target_pointer_width = "64")]
+ if N > 1 { result[N-2] = (x >> 32) as u32;}
+ if N > 0 { result[N-1] = x as u32;} //Compiler should hopefully be smart enough to yeet the condition.
+ ArbitraryBytes(result)
+}
+
+impl<const N : usize> From<&usize> for ArbitraryBytes<N>{
+ fn from(x: &usize) -> Self {
+ from_usize(*x)
+ }
+}
+impl<const N : usize> From<&u32> for ArbitraryBytes<N>{
+ fn from(x: &u32) -> Self {
+ let mut result = [0;N];
+ if let Some(l) = result.last_mut() { *l = *x };
+ ArbitraryBytes(result)
+ }
+}
+
+//workaround for lack of proper const-generic support.
+trait PadWithAZero{
+ type Output;
+ fn pad_with_a_zero(&self) -> Self::Output;
+}
+
+pub(crate) trait PaddedShiftLeft{
+ type Output;
+ fn padded_shift_left(&self, shift : u32) -> Self::Output;
+}
+
+impl PadWithAZero for ArbitraryBytes<5>{
+ type Output = ArbitraryBytes<6>;
+ fn pad_with_a_zero(&self) -> Self::Output {
+ ArbitraryBytes::<6>([
+ 0,
+ self.0[0],
+ self.0[1],
+ self.0[2],
+ self.0[3],
+ self.0[4],
+ ])
+ }
+}
+
+impl PadWithAZero for ArbitraryBytes<8>{
+ type Output = ArbitraryBytes<9>;
+ fn pad_with_a_zero(&self) -> Self::Output {
+ ArbitraryBytes::<9>([
+ 0,
+ self.0[0],
+ self.0[1],
+ self.0[2],
+ self.0[3],
+ self.0[4],
+ self.0[5],
+ self.0[6],
+ self.0[7],
+ ])
+ }
+}
+
+impl PaddedShiftLeft for ArbitraryBytes<5>{
+ type Output = ArbitraryBytes::<6>;
+
+ fn padded_shift_left(&self, shift : u32) -> Self::Output {
+ debug_assert!(shift < 32);
+ if shift == 0 {
+ self.pad_with_a_zero()
+ } else {
+ ArbitraryBytes([
+ self.0[0] >> (32-shift),
+ (self.0[0] << shift) | (self.0[1] >> (32-shift)),
+ (self.0[1] << shift) | (self.0[2] >> (32-shift)),
+ (self.0[2] << shift) | (self.0[3] >> (32-shift)),
+ (self.0[3] << shift) | (self.0[4] >> (32-shift)),
+ self.0[4] << shift
+ ])
+ }
+ }
+}
+
+impl PaddedShiftLeft for ArbitraryBytes<8>{
+ type Output = ArbitraryBytes::<9>;
+
+ fn padded_shift_left(&self, shift : u32) -> Self::Output {
+ debug_assert!(shift < 32);
+ if shift == 0 {
+ self.pad_with_a_zero()
+ } else {
+ ArbitraryBytes([
+ self.0[0] >> (32-shift),
+ (self.0[0] << shift) | (self.0[1] >> (32-shift)),
+ (self.0[1] << shift) | (self.0[2] >> (32-shift)),
+ (self.0[2] << shift) | (self.0[3] >> (32-shift)),
+ (self.0[3] << shift) | (self.0[4] >> (32-shift)),
+ (self.0[4] << shift) | (self.0[5] >> (32-shift)),
+ (self.0[5] << shift) | (self.0[6] >> (32-shift)),
+ (self.0[6] << shift) | (self.0[7] >> (32-shift)),
+ self.0[7] << shift
+ ])
+ }
+ }
+}
+
+impl<const N : usize> DivAssign<&usize> for ArbitraryBytes<N>{
+ //just do long division.
+ fn div_assign(&mut self, rhs: &usize) {
+ self.div_assign_with_remainder_usize(*rhs);
+ }
+}
+
+#[derive(Debug, Clone, Copy)]
+pub(crate) struct ArbitraryBytesToUsizeError;
+impl Display for ArbitraryBytesToUsizeError{
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "conversion from arbitrary sized int-array to usize failed")
+ }
+}
+impl Error for ArbitraryBytesToUsizeError{}
+
+impl<const N : usize> TryFrom<ArbitraryBytes<N>> for usize{
+ type Error = ArbitraryBytesToUsizeError;
+
+ fn try_from(value: ArbitraryBytes<N>) -> Result<Self, Self::Error> {
+ usize::try_from(&value)
+ }
+}
+
+impl<const N : usize> TryFrom<&ArbitraryBytes<N>> for usize{
+ type Error = ArbitraryBytesToUsizeError;
+ #[cfg(target_pointer_width = "64")]
+ fn try_from(value: &ArbitraryBytes<N>) -> Result<Self, Self::Error> {
+ //64 bits.
+ if value.0[0..N.saturating_sub(2)].iter().any(|x| *x != 0) {
+ Err(ArbitraryBytesToUsizeError)
+ } else {
+ //failing to get last_bit is an actual error.
+ let last_bit = value.0.get(N-1).ok_or(ArbitraryBytesToUsizeError).copied();
+ //second-last is not an error though.
+ let second_last_bit = value.0.get(N-2).copied().unwrap_or_default();
+ #[allow(clippy::cast_possible_truncation)] //false positive. This function is only compiled on 64bit systems.
+ last_bit.map(|last_bit| u64_from_u32s(second_last_bit, last_bit) as usize)
+ }
+ }
+ #[cfg(not(target_pointer_width = "64"))]
+ fn try_from(value: &ArbitraryBytes<N>) -> Result<Self, Self::Error> {
+ //16 or 32 bits.
+ if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) {
+ Err(ArbitraryBytesToUsizeError)
+ } else {
+ value.0.get(N-1).and_then(|x| (*x).try_into().ok()).ok_or(ArbitraryBytesToUsizeError)
+ }
+ }
+}
+
+#[derive(Debug, Clone, Copy)]
+pub(crate) struct ArbitraryBytesToU32Error;
+impl Display for ArbitraryBytesToU32Error{
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "conversion from arbitrary sized int-array to u32 failed")
+ }
+}
+impl Error for ArbitraryBytesToU32Error{}
+
+impl<const N : usize> TryFrom<&ArbitraryBytes<N>> for u32{
+ type Error = ArbitraryBytesToU32Error;
+
+ fn try_from(value: &ArbitraryBytes<N>) -> Result<Self, Self::Error> {
+ if value.0[0..N.saturating_sub(1)].iter().any(|x| *x != 0) {
+ Err(ArbitraryBytesToU32Error)
+ } else {
+ value.0.get(N-1).copied().ok_or(ArbitraryBytesToU32Error)
+ }
+ }
+}
+
+macro_rules! make_mul {
+ ($cfn:ident, $t:ty, $long_t:ty) => {
+ impl<const N : usize> Mul<$t> for ArbitraryBytes<N>{
+ type Output = Option<ArbitraryBytes<N>>;
+ fn mul(self, rhs: $t) -> Self::Output {
+ $cfn(self, rhs)
+ }
+ }
+ const fn $cfn<const N : usize>(mut lhs : ArbitraryBytes<N>, rhs: $t) -> Option<ArbitraryBytes<N>> {
+ //sorry for this fugly non-idiomatic syntax, but Rust const functions seem to be severely limited right now :-(
+ let mut carry = 0 as $long_t;
+ let mut idx = N;
+ let rhs = rhs as $long_t;
+ while idx != 0 {
+ idx -= 1;
+ let res = (lhs.0[idx] as $long_t) * rhs + carry;
+ lhs.0[idx] = res as u32;
+ carry = res >> 32;
+ }
+ if carry != 0 { //if there's still carry after we hit the last digit, well, didn't fit obviously.
+ None
+ } else {
+ Some(lhs)
+ }
+ }
+ };
+}
+make_mul!(const_mul_u32, u32,u64);
+#[cfg(target_pointer_width = "64")]
+make_mul!(const_mul_usize, usize, u128);
+#[cfg(not(target_pointer_width = "64"))]
+make_mul!(const_mul_usize, usize, u64);
+
+impl<const N : usize> Mul<&usize> for &ArbitraryBytes<N>{
+ type Output = Option<ArbitraryBytes<N>>;
+ fn mul(self, rhs: &usize) -> Self::Output {
+ (*self).clone() * (*rhs)
+ }
+}
+
+//Done separately, because "mut references not allowed in const contexts"
+impl<const N : usize> MulAssign<&usize> for ArbitraryBytes<N>{
+ #[allow(clippy::cast_possible_truncation)] //truncation is intentional here.
+ fn mul_assign(&mut self, rhs: &usize) {
+ #[cfg(target_pointer_width = "64")]
+ type Long = u128;
+ #[cfg(not(target_pointer_width = "64"))]
+ type Long = u64;
+ let rhs = *rhs as Long;
+ let carry = self.0.iter_mut().rev().fold(0 as Long, |carry, current| {
+ let result = (*current as Long) * rhs + carry;
+ *current = result as u32;
+ result >> 32
+ });
+ debug_assert_eq!(carry, 0);
+ }
+}
+
+impl<const N : usize> Mul<&ArbitraryBytes<N>> for &ArbitraryBytes<N> where ArbitraryBytes<N> : for<'a> From<&'a usize> {
+ type Output = Option<ArbitraryBytes<N>>;
+ ///School method. I haven't tried Karatsuba, but rule of thumb is that it only gets faster at about 32 digits. We have 8 digits max.
+ fn mul(self, rhs: &ArbitraryBytes<N>) -> Self::Output {
+ let mut result : ArbitraryBytes<N> = (&0_usize).into();
+ let no_overflow = rhs.0.iter().enumerate().filter(|(_,b)| **b != 0).try_for_each(|(i,b)|{
+ let p : Option<ArbitraryBytes<N>> = self.clone() * *b;
+ let p = p.filter(|p| p.0[0..(N-1-i)].iter().all(|&i| i == 0));
+ let carry = p.map(|p|{
+ //for some reason it's faster to use slices than iterators here.
+ slice_overflowing_add_assign(&mut result.0[0..=i], &p.0[(N-1-i)..])
+ });
+ carry.filter(|x| !x).map(|_|())
+ });
+ no_overflow.map(|_| result)
+ }
+}
+
+#[allow(clippy::trait_duplication_in_bounds)] //obvious false positive. u32 and usize aren't the same.
+impl<const N : usize, const M : usize> RemAssignWithQuotient for ArbitraryBytes<N>
+ where Self : for<'a> From<&'a usize> + for<'a> From<&'a u32> + PaddedShiftLeft<Output = ArbitraryBytes<M>>
+{
+ fn rem_assign_with_quotient(&mut self, divisor : &Self) -> Self{
+
+ //This is based on Knuth, TAOCP vol 2 section 4.3, algorithm D.
+ //First, check if we can get away without doing a division.
+ match Ord::cmp(self, divisor){
+ std::cmp::Ordering::Less => Self::from(&0_usize), //leave self unchanged, it's the remainder.
+ std::cmp::Ordering::Equal => { *self = Self::from(&0_usize); Self::from(&1_usize) },
+ std::cmp::Ordering::Greater => {
+ //If a single digit division suffices, do a single digit division.
+ if let Ok(divisor_as_u32) = divisor.try_into() {
+ self.rem_assign_with_quotient_u32(divisor_as_u32)
+ } else {
+ self.rem_assign_with_quotient_knuth(divisor)
+ }
+ },
+ }
+ }
+}
+
+macro_rules! make_div_assign_with_remainder {
+ ($name:ident, $t_divisor:ty, $t_long:ty) => {
+ /// Replaces self with Quotient and returns Remainder
+ fn $name(&mut self, rhs: $t_divisor) -> $t_divisor {
+ debug_assert!((<$t_long>::MAX >> 32) as u128 >= <$t_divisor>::MAX as u128);
+
+ let divisor = rhs as $t_long;
+ let remainder = self.0.iter_mut().fold(0 as $t_long,|carry, current| {
+ debug_assert_eq!(carry, carry & (<$t_divisor>::MAX as $t_long)); //carry has to be lower than divisor, and divisor is $t_divisor.
+ let carry_shifted = carry << 32;
+ let dividend = (carry_shifted) | (*current as $t_long);
+ let remainder = dividend % divisor;
+ let ratio = dividend / divisor;
+ debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero.
+ *current = (ratio) as u32;
+ remainder
+ });
+ debug_assert_eq!(remainder, remainder & (<$t_divisor>::MAX as $t_long));
+ remainder as $t_divisor
+ }
+ };
+}
+
+impl<const N : usize> ArbitraryBytes<N>{
+ pub(super) fn new(data : [u32;N]) -> Self {
+ ArbitraryBytes(data)
+ }
+
+ #[cfg(target_pointer_width = "64")]
+ make_div_assign_with_remainder!(div_assign_with_remainder_usize, usize, u128);
+
+ #[cfg(not(target_pointer_width = "64"))]
+ make_div_assign_with_remainder!(div_assign_with_remainder_usize, usize, u64);
+
+ make_div_assign_with_remainder!(div_assign_with_remainder_u32, u32, u64);
+
+ fn rem_assign_with_quotient_u32(&mut self, divisor: u32) -> Self where Self : for<'a> From<&'a u32> {
+ let remainder = self.div_assign_with_remainder_u32(divisor);
+ std::mem::replace(self, Self::from(&remainder))
+ }
+
+ //This is Knuth, The Art of Computer Programming Volume 2, Section 4.3, Algorithm D.
+ fn rem_assign_with_quotient_knuth<const M : usize>(&mut self, divisor : &Self) -> Self
+ where Self : PaddedShiftLeft<Output = ArbitraryBytes<M>> +
+ for<'a> From<&'a usize>
+ {
+ debug_assert!(M == N+1);
+ //first we need to find n (number of digits in divisor)
+ let n_digits_divisor= N - divisor.find_first_nonzero_digit();
+ debug_assert!(n_digits_divisor > 1);
+ //and same in the non-normalized dividend
+ let m_plus_n_digits_dividend = N - self.find_first_nonzero_digit();
+ let m_extra_digits_dividend = m_plus_n_digits_dividend - n_digits_divisor;
+
+ //step D1: Normalize. This brings the maximum error for each digit down to no more than 2.
+ let normalize_shift = divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros();
+ //again, missing const generics ruin all the fun.
+ let mut dividend = self.padded_shift_left(normalize_shift);
+ let divisor = divisor.padded_shift_left(normalize_shift);
+ debug_assert_eq!(divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros(),0);
+
+ let mut quotient : Self = (&0_usize).into();
+
+ //needed for Step D3, but is the same for all iterations -> factored out.
+ let guess_divisor = u64::from(divisor.get_digit_from_right(n_digits_divisor - 1));
+ let divisor_second_significant_digit = u64::from(divisor.get_digit_from_right(n_digits_divisor-2));
+
+ //step D2, D7: the loop.
+ for j in (0..=m_extra_digits_dividend).rev() {
+ //Step D3: Guess a digit
+ let guess_dividend = u64_from_u32s(dividend.get_digit_from_right(j+n_digits_divisor), dividend.get_digit_from_right(j + n_digits_divisor - 1));
+ let mut guesstimate = guess_dividend/guess_divisor;
+ let mut guess_reminder = guess_dividend % guess_divisor;
+ //refine our guesstimate (still step D3). Ensures that error of guesstimate is either 0 or +1.
+ while u32::try_from(guess_reminder).is_ok()
+ && (guesstimate > u64::from(u32::MAX)
+ || divisor_second_significant_digit * guesstimate
+ > (guess_reminder << 32) | u64::from(dividend.get_digit_from_right(j + n_digits_divisor - 2))
+ ) {
+ guesstimate -= 1;
+ guess_reminder += guess_divisor;
+ }
+ //Step D4: Pretend the guess was correct and subtract guesstimate * divisor from dividend.
+ debug_assert!(guesstimate & u64::from(u32::MAX) == guesstimate, "The while above should have made guesstimate a one-digit number. Debug!");
+ #[allow(clippy::cast_possible_truncation)]
+ let mut guesstimate = guesstimate as u32;
+ let s = (divisor.clone() * guesstimate).expect("Multipliation by a digit cannot overflow for a padded type.");
+ let s_range = (M - 1 - n_digits_divisor)..M;
+ let d_range = (s_range.start - j)..(s_range.end - j);
+ let did_overflow = slice_overflowing_sub_assign(&mut dividend.0[d_range.clone()], &s.0[s_range.clone()]);
+ //Step D5: If guesstimate was incorrect, the subtraction has overflown. The result is wrapped in such a case.
+ if did_overflow {
+ //Step D6: We have to correct our guesstimate. It was too large by one. We also have to fix the overflow that has occured.
+ guesstimate -= 1;
+ //The addition must overflow again. The two overflows cancel out, and since we are using wrapping arithmetics, the result becomes correct again.
+ let did_overflow = slice_overflowing_add_assign(&mut dividend.0[d_range], &divisor.0[s_range]);
+ debug_assert!(did_overflow, "Knuth, TAOCP Vol 2, Chap 4.3.1 exercise 21 says: if this fails, the while above is wrong. Debug.");
+ }
+ quotient.set_digit_from_right(guesstimate, j);
+ }
+
+ //Steop D8: Compute Remainder.
+ self.0 = dividend.shift_right(normalize_shift).0[1..].try_into()
+ .expect("Conversion of what should have been an N-element slice into an N-element array failed.");
+ quotient
+
+ }
+
+ fn find_first_nonzero_digit(&self) -> usize{
+ self.0.iter().enumerate().find(|(_,v)| **v != 0).map_or(N,|(x,_)| x)
+ }
+
+ fn get_digit_from_right(&self, i : usize) -> u32{
+ self.0[N-i-1]
+ }
+ fn set_digit_from_right(&mut self, val: u32, i : usize){
+ self.0[N-i-1] = val;
+ }
+
+ fn shift_right(mut self, s : u32) -> Self {
+ debug_assert!(s < 32);
+ if s != 0 {
+ let _ = self.0.iter_mut().fold(0u32, |carry, val| {
+ let c = *val << (32-s);
+ *val >>= s;
+ debug_assert!(*val & carry == 0);
+ *val |= carry;
+ c
+ });
+ }
+ self
+ }
+}
+
+fn slice_overflowing_sub_assign(lhs : &mut [u32], rhs: &[u32]) -> bool{
+ debug_assert_eq!(lhs.len(), rhs.len());
+ lhs.iter_mut().zip(rhs.iter()).rev().fold(false,|carry,(a,b)| {
+ let r = b.overflowing_add(u32::from(carry));
+ let s = a.overflowing_sub(r.0);
+ *a = s.0;
+ r.1 || s.1
+ })
+}
+
+fn slice_overflowing_add_assign(lhs : &mut [u32], rhs : &[u32]) -> bool {
+ debug_assert_eq!(lhs.len(), rhs.len());
+ lhs.iter_mut().zip(rhs.iter()).rev().fold(false, |carry, (a, b)| {
+ let r = b.overflowing_add(u32::from(carry));
+ let s = a.overflowing_add(r.0);
+ *a = s.0;
+ r.1 || s.1
+ })
+}
+
+fn u64_from_u32s(m : u32, l : u32) -> u64{
+ let m = u64::from(m);
+ let l = u64::from(l);
+ (m << 32) | l
+}
+
+#[cfg(test)]
+mod arbitrary_bytes_tests{
+ use std::iter::successors;
+
+ use super::*;
+ use rand::RngCore;
+ use rand_xoshiro::rand_core::SeedableRng;
+ use rand_xoshiro::Xoshiro256Plus;
+
+ /// Tests specifically the case that will_overflow is true.
+ #[test]
+ fn knuth_add_back_test(){
+ let mut dividend = ArbitraryBytes::new([
+ //m = 3, n=5
+ u32::MAX,
+ u32::MAX,
+ u32::MAX-1,
+ u32::MAX,
+ u32::MAX,
+ 0,
+ 0,
+ 3
+ ]);
+ let divisor = ArbitraryBytes::new([
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ u32::MAX,
+ u32::MAX,
+ u32::MAX,
+ ]);
+ let result = dividend.rem_assign_with_quotient(&divisor);
+ assert_eq!(dividend.0, [0,0,0,0,0,0,0,2]);
+ assert_eq!(result.0, [0,0,0,u32::MAX,u32::MAX, u32::MAX, u32::MAX, u32::MAX]);
+ }
+
+
+ fn prepare_many_numbers(max_dividend_digits : u32, min_dividend_digits : u32, max_divisor_digits : u32, min_divisor_digits : u32) -> Vec<(ArbitraryBytes<5>,ArbitraryBytes<5>, u128, u128)>{
+ assert!(max_dividend_digits < 5);
+ assert!(min_dividend_digits <= max_dividend_digits);
+ assert!(max_divisor_digits < 5);
+ assert!(min_divisor_digits <= max_divisor_digits);
+ let mut rng = Xoshiro256Plus::seed_from_u64(0);
+ let mut res = Vec::new();
+ for _i in 0..100000 {
+ let dx = rng.next_u32() % (max_dividend_digits + 1 - min_dividend_digits) + min_dividend_digits;
+ let dy = rng.next_u32() % (max_divisor_digits + 1 - min_divisor_digits) + min_divisor_digits;
+ let ds = dx.min(dy);
+ let dl = dx.max(dy);
+ let dividendx = [
+ 0,
+ if dl >= 4 { rng.next_u32() } else { 0 },
+ if dl >= 3 { rng.next_u32() } else { 0 },
+ if dl >= 2 { rng.next_u32() } else { 0 },
+ if dl >= 1 { rng.next_u32() } else { 0 },
+ ];
+ let divisorx = [
+ 0,
+ if ds >= 4 { rng.next_u32() } else { 0 },
+ if ds >= 3 { rng.next_u32() } else { 0 },
+ if ds >= 2 { rng.next_u32() } else { 0 },
+ if ds >= 1 { rng.next_u32() } else { 0 },
+ ];
+ let needs_swap = ds == dl && dividendx[5-ds as usize] < divisorx[5-ds as usize];
+ let dividend = ArbitraryBytes::new(if needs_swap {divisorx} else {dividendx});
+ let divisor = ArbitraryBytes::new(if needs_swap {dividendx} else {divisorx});
+ assert!(dividend.ge(&divisor));
+
+ let td =
+ ((dividend.0[1] as u128)<<96)
+ + ((dividend.0[2] as u128)<<64)
+ + ((dividend.0[3] as u128)<<32)
+ + (dividend.0[4] as u128);
+ let tn =
+ ((divisor.0[1] as u128)<<96)
+ + ((divisor.0[2] as u128)<<64)
+ + ((divisor.0[3] as u128)<<32)
+ + (divisor.0[4] as u128);
+
+
+ res.push((dividend, divisor, td/tn, td%tn));
+ }
+ res
+ }
+
+ /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.)
+ #[test]
+ fn rem_assign_with_quotient_knuth_many_numbers_test() {
+ let input = prepare_many_numbers(4,2, 4, 2);
+ for (mut dividend, divisor, expected_quotient, expexted_remainder) in input {
+ let quotient = dividend.rem_assign_with_quotient_knuth(&divisor);
+ let remainder = dividend;
+ let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128);
+ let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128);
+ assert_eq!(quotient, expected_quotient);
+ assert_eq!(remainder, expexted_remainder);
+ }
+ }
+ /// Just tests a bunch of procedurally generated numbers (all within u128 for easy comparison.)
+ #[test]
+ fn rem_assign_with_quotient_many_numbers_test() {
+ let input = prepare_many_numbers(4,1, 4, 1);
+ for (mut dividend, divisor, expected_quotient, expexted_remainder) in input {
+ let quotient = dividend.rem_assign_with_quotient(&divisor);
+ let remainder = dividend;
+ let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128);
+ let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128);
+ assert_eq!(quotient, expected_quotient);
+ assert_eq!(remainder, expexted_remainder);
+ }
+ }
+
+ #[test]
+ fn rem_assign_with_quotient_u32_many_numbers_test() {
+ let input = prepare_many_numbers(4,1, 1, 1);
+ for (mut dividend, divisor, expected_quotient, expexted_remainder) in input {
+ let quotient = dividend.rem_assign_with_quotient_u32(*divisor.0.last().unwrap());
+ let remainder = dividend;
+ let quotient = ((quotient.0[1] as u128)<<(96)) + ((quotient.0[2] as u128)<<64) + ((quotient.0[3] as u128)<<32) + (quotient.0[4] as u128);
+ let remainder = ((remainder.0[1] as u128)<<(96)) + ((remainder.0[2] as u128)<<64) + ((remainder.0[3] as u128)<<32) + (remainder.0[4] as u128);
+ assert_eq!(quotient, expected_quotient);
+ assert_eq!(remainder, expexted_remainder);
+ }
+ }
+
+ #[test]
+ fn rem_assign_with_quotient_u32_test(){
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let quotient = a.rem_assign_with_quotient_u32(0x12345);
+ assert_eq!(quotient.0, [0x9A10,0xB282B7BA,0xE4948E98,0x2AE63D74,0xE6FDFF4A]);
+ assert_eq!(a.0, [0,0,0,0,0x6882]);
+ }
+
+ #[test]
+ fn rem_assign_with_quotient_u32_test2(){
+ let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]);
+ let quotient = a.rem_assign_with_quotient_u32(0x12345);
+ assert_eq!(quotient.0, [0,0,0,0,0]);
+ assert_eq!(a.0, [0,0,0,0,0x1234]);
+ }
+
+ #[test]
+ fn div_assign_with_remainder_usize_test(){
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let remainder = a.div_assign_with_remainder_usize(0x1234_usize);
+ assert_eq!(a.0, [0x9A135,0x79AA8650,0xD251DC7A,0x9AA8C1F2,0x8B9729EF]);
+ assert_eq!(remainder, 0x2E8);
+ }
+
+ #[test]
+ fn div_assign_with_remainder_usize_test2(){
+ let mut a = ArbitraryBytes::new([0,0,0,0,0x1234]);
+ let remainder = a.div_assign_with_remainder_usize(0x1235_usize);
+ assert_eq!(a.0, [0,0,0,0,0]);
+ assert_eq!(remainder, 0x1234);
+ }
+
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn div_assign_with_remainder_usize_test3(){
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let remainder = a.div_assign_with_remainder_usize(0x123456789ab_usize);
+ assert_eq!(a.0, [0,0x9A107B,0xBEC8B35A,0xEC9D3B43,0x056F803A]);
+ assert_eq!(remainder, 0xD7537A4B6);
+ }
+
+ #[test]
+ fn sub_assign_test() {
+ let mut a = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let b = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let carry = slice_overflowing_sub_assign(&mut a.0,&b.0);
+ assert!(!carry);
+ assert_eq!(a.0, [0x6CA2C267,0xb414f734,0xb30ddbf2,0x35b61c9c,0x4fd97562]);
+ }
+
+ #[test]
+ fn sub_assign_test2() {
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let carry = slice_overflowing_sub_assign(&mut a.0,&b.0);
+ assert!(carry);
+ assert_eq!(a.0, [0x935D3D98,0x4BEB08CB,0x4CF2240D,0xCA49E363,0xB0268A9E]);
+ }
+
+ #[test]
+ fn add_assign_test() {
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = ArbitraryBytes::new([0xaf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let carry = slice_overflowing_add_assign(&mut a.0,&b.0);
+ assert!(!carry);
+ assert_eq!(a.0, [0xF1F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]);
+ }
+ #[test]
+ fn add_assign_test2() {
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = ArbitraryBytes::new([0xbf4a816a,0xb414f734,0x7a2167c7,0x47ea7314,0xfba75574]);
+ let carry = slice_overflowing_add_assign(&mut a.0,&b.0);
+ assert!(carry);
+ assert_eq!(a.0, [0x01F2406D,0xB414F734,0x4134F39C,0x5A1EC98D,0xA7753586]);
+ }
+
+ #[test]
+ fn shift_left_test_5() {
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = a.padded_shift_left(7);
+ assert_eq!(b.0,[0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]);
+ }
+
+ #[test]
+ fn shift_left_test_8() {
+ let a = ArbitraryBytes::new([0x4631abcd,0x35a40be4,0x074c4d0a,0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = a.padded_shift_left(7);
+ assert_eq!(b.0,[0x23, 0x18D5_E69A, 0xD205_F203, 0xA626_8521, 0x53DF_817F, 0xFFFF_FFE3, 0x89C5_EA89, 0x1A2B_3C55, 0xE6F0_0900]);
+ }
+
+ #[test]
+ fn shift_right_test() {
+ let a = ArbitraryBytes::new([0x21, 0x53DF817F,0xFFFFFFE3, 0x89C5EA89, 0x1A2B3C55, 0xE6F00900]);
+ let b = a.shift_right(7);
+ assert_eq!(b.0,[0, 0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ }
+
+ #[test]
+ fn get_digit_from_right_test(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ assert_eq!(a.get_digit_from_right(3), 0xffffffff);
+ }
+
+ #[test]
+ fn set_digit_from_right_test(){
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ a.set_digit_from_right(0xdeadbeef, 4);
+ assert_eq!(a.0[0], 0xdeadbeef);
+ }
+
+ #[test]
+ fn find_first_nonzero_digit_test() {
+ let a = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]);
+ assert_eq!(a.find_first_nonzero_digit(),3);
+ }
+
+ #[test]
+ fn mul_arbitrary_test(){
+ let a = ArbitraryBytes::new([0,0,0,0x47ea7314,0xfba75574]);
+ let b = ArbitraryBytes::new([0,0,0,0x12345678,0xabcde012]);
+ let a_big = (0x47ea7314_u128 << 32) | 0xfba75574u128;
+ let b_big = (0x12345678_u128 << 32) | 0xabcde012u128;
+ let c_big = a_big*b_big;
+ let c = (&a * &b).unwrap();
+ assert_eq!(c_big & 0xffff_ffff, c.0[4] as u128 );
+ assert_eq!((c_big >> 32 ) & 0xffff_ffff, c.0[3] as u128);
+ assert_eq!((c_big >> 64 ) & 0xffff_ffff, c.0[2] as u128);
+ assert_eq!((c_big >> 96 ) & 0xffff_ffff, c.0[1] as u128);
+ assert_eq!(0, c.0[0]);
+ }
+ #[test]
+ fn mul_arbitrary_test_2(){
+ let a = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let b = ArbitraryBytes::new([0,0,0,0,2]);
+ let c = (&a * &b).unwrap();
+ assert_eq!(0x4EC7593F, c.0[0]);
+ assert_eq!(0xA35C3E70, c.0[1]);
+ assert_eq!(2*0x1753a5c7, c.0[2]);
+ assert_eq!(0x8fd4e629, c.0[3]);
+ assert_eq!(0xf74eaae8, c.0[4]);
+ }
+ #[test]
+ fn mul_arbitrary_test_3(){
+ let a = ArbitraryBytes::new([0,0,0,0,2]);
+ let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = (&a * &b).unwrap();
+ assert_eq!(0x4EC7593F, c.0[0]);
+ assert_eq!(0xA35C3E70, c.0[1]);
+ assert_eq!(2*0x1753a5c7, c.0[2]);
+ assert_eq!(0x8fd4e629, c.0[3]);
+ assert_eq!(0xf74eaae8, c.0[4]);
+ }
+ #[test]
+ fn mul_arbitrary_test_4(){
+ let a = ArbitraryBytes::new([0,0,0,0,8]);
+ let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = &a * &b;
+ assert!(c.is_none())
+ }
+ #[test]
+ fn mul_arbitrary_test_5(){
+ let a = ArbitraryBytes::new([0,0,0,1,0]);
+ let b = ArbitraryBytes::new([0x2763ac9f,0xd1ae1f38,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = &a * &b;
+ assert!(c.is_none())
+ }
+ #[test]
+ fn mul_arbitrary_test_6(){
+ let a = ArbitraryBytes::new([0,0,0,1,1]);
+ let b = ArbitraryBytes::new([0,0xffffffff,0x1753a5c7,0x47ea7314,0xfba75574]);
+ let c = &a * &b;
+ assert!(c.is_none())
+ }
+
+ #[test]
+ fn mul_with_u32_test(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 3u32;
+ let product = a*b;
+ assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036])
+ }
+ #[test]
+ fn mul_with_u32_test2(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 4u32;
+ let product = a*b;
+ assert!(product.is_none())
+ }
+ #[test]
+ fn mul_with_usize_test_working(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 3usize;
+ let product = a*b;
+ assert_eq!(product.unwrap().0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036])
+ }
+ #[test]
+ fn mul_with_usize_test_overflow(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 4usize;
+ let product = a*b;
+ assert!(product.is_none())
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn mul_with_usize_test_64bit_works(){
+ let a = ArbitraryBytes::new([0,0,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 0x123456789ausize;
+ let product = a*b;
+ assert_eq!(product.unwrap().0, [0xE,0x28130BBC,0x7442D257,0x1FEDDF10,0xC8ED3AD4])
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn mul_with_usize_test_64bit_overflow(){
+ let a = ArbitraryBytes::new([0,0x1,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = usize::MAX;
+ let product = a*b;
+ assert!(product.is_none())
+ }
+ #[test]
+ fn mul_assign_usize(){
+ let mut a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = 3usize;
+ a *= &b;
+ assert_eq!(a.0, [0xC7F73D08,0xFFFFFFFF,0x553AA37F,0x369D036A,0x0369A036])
+ }
+ #[test]
+ fn try_into_u32_test(){
+ let a = ArbitraryBytes::new([0,0,0,0,0xabcde012]);
+ let b : u32 = (&a).try_into().unwrap();
+ assert_eq!(b, 0xabcde012);
+ }
+ #[test]
+ fn try_into_u32_test_overflows(){
+ let a = ArbitraryBytes::new([0,0,0,0x1,0xabcde012]);
+ let b : Result<u32,_> = (&a).try_into();
+ assert!(b.is_err())
+ }
+ #[test]
+ fn try_into_usize_test(){
+ let a = ArbitraryBytes::new([0,0,0,0,0xe012]);
+ let b : usize = (&a).try_into().unwrap();
+ assert_eq!(b, 0xe012);
+ }
+ #[test]
+ fn try_into_usize_test_overflows(){
+ let a = ArbitraryBytes::new([0,0,0x1,0,0xabcde012]);
+ let b : Result<usize,_> = (&a).try_into();
+ assert!(b.is_err())
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn try_into_usize_test_on_64_bits(){
+ let a = ArbitraryBytes::new([0,0,0,0x54a,0xabcde012]);
+ let b : usize= (&a).try_into().unwrap();
+ assert_eq!(b, 0x54aabcde012);
+ }
+ #[cfg(target_pointer_width = "32")]
+ #[test]
+ fn try_into_usize_test_on_64_bits(){
+ let a = ArbitraryBytes::new([0,0,0,0x54a,0xabcde012]);
+ let b : Result<usize,_> = (&a).try_into();
+ assert!(b.is_err())
+ }
+ #[test]
+ fn pad_with_a_zero_5(){
+ let a = ArbitraryBytes::new([0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = a.pad_with_a_zero();
+ assert_eq!(*b.0.first().unwrap(),0);
+ assert_eq!(b.0[1..], a.0);
+ }
+ #[test]
+ fn pad_with_a_zero_8(){
+ let a = ArbitraryBytes::new([0x4631abcd,0x35a40be4,0x074c4d0a,0x42a7bf02,0xffffffff,0xc7138bd5,0x12345678,0xabcde012]);
+ let b = a.pad_with_a_zero();
+ assert_eq!(*b.0.first().unwrap(),0);
+ assert_eq!(b.0[1..], a.0);
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn from_usize_5_large(){
+ let a : ArbitraryBytes<5> = (&0x7246abcd705aef_usize).into();
+ assert_eq!(a.0[4], 0xcd705aef);
+ assert_eq!(a.0[3], 0x007246ab);
+ assert!(a.0[..3].iter().all(|x| *x==0));
+ }
+ #[test]
+ fn from_usize_5(){
+ let a : ArbitraryBytes<5> = (&0xcd705aef_usize).into();
+ assert_eq!(a.0[4], 0xcd705aef);
+ assert!(a.0[..4].iter().all(|x| *x==0));
+ }
+ #[cfg(target_pointer_width = "64")]
+ #[test]
+ fn from_usize_8_large(){
+ let a : ArbitraryBytes<8> = (&0x7246abcd705aef_usize).into();
+ assert_eq!(a.0[7], 0xcd705aef);
+ assert_eq!(a.0[6], 0x007246ab);
+ assert!(a.0[..6].iter().all(|x| *x==0));
+ }
+ #[test]
+ fn from_usize_8(){
+ let a : ArbitraryBytes<8> = (&0xcd705aef_usize).into();
+ assert_eq!(a.0[7], 0xcd705aef);
+ assert!(a.0[..7].iter().all(|x| *x==0));
+ }
+
+ fn convert_by_division<const N : usize>(value : ArbitraryBytes<N>, base : usize) -> impl Iterator<Item = usize>{
+ successors(Some((value, 0)),|(v, _)| {
+ if *v == (&0usize).into() {
+ None
+ } else {
+ let mut v = v.clone();
+ let remainder = v.div_assign_with_remainder_usize(base);
+ Some((v, remainder))
+ }
+ }).skip(1).map(|(_,b)| b).collect::<Vec<_>>().into_iter().rev()
+ }
+ #[test]
+ fn compare_conversion_by_division_randoms_8(){
+ let mut rng = Xoshiro256Plus::seed_from_u64(0);
+ for _ in 0..10000 {
+ let v = ArbitraryBytes::new([
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ ]);
+ let b = rng.next_u32() as usize;
+ let i1 = super::super::IterativeBaseConversion::new(v.clone(),b).skip_while(|v| *v == 0);
+ let i2 = convert_by_division(v,b);
+ assert!(i1.eq(i2));
+ }
+ }
+ #[test]
+ fn compare_conversion_by_division_randoms_5(){
+ let mut rng = Xoshiro256Plus::seed_from_u64(0);
+ for _ in 0..10000 {
+ let v = ArbitraryBytes::new([
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ rng.next_u32(),
+ ]);
+ let b = rng.next_u32() as usize;
+ let i1 = super::super::IterativeBaseConversion::new(v.clone(),b).skip_while(|v| *v == 0);
+ let i2 = convert_by_division(v,b);
+ assert!(i1.eq(i2));
+ }
+ }
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs
new file mode 100644
index 0000000..ffea565
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_common_constants.rs
@@ -0,0 +1,72 @@
+//! Precomputed max fitting powers and exponents for common password character lits.
+//! 10 is "digits only"
+//! 16 is "hexadecimal"
+//! 32 is "special characters only"
+//! 52 is "letters only"
+//! 62 is "letters and digits"
+//! 94 is "letters, digits and special characters" - the default for PasswordMaker Pro.
+
+use super::super::iterative_conversion::PrecomputedMaxPowers;
+use super::ArbitraryBytes;
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{
+ fn lookup(base : &usize) -> Option<(Self, usize)> {
+ match base {
+ 10 => Some((ArbitraryBytes([0xAF29_8D05, 0x0E43_95D6, 0x9670_B12B, 0x7F41_0000, 0x0000_0000]), 48)),
+ 16 => Some((ArbitraryBytes([0x1000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 39)),
+ 32 => Some((ArbitraryBytes([0x0800_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 31)),
+ 52 => Some((ArbitraryBytes([0xC3AC_AD73, 0xBB2B_01F7, 0x6D5D_11C1, 0xF100_0000, 0x0000_0000]), 28)),
+ 62 => Some((ArbitraryBytes([0x0702_2C89, 0x3992_DDB9, 0xC9B6_E9D6, 0x5CE5_4443, 0x0400_0000]), 26)),
+ 94 => Some((ArbitraryBytes([0x27AC_9E29, 0x5D2F_DF56, 0x4DA2_58BA, 0x7B1F_542F, 0x8100_0000]), 24)),
+ _ => None
+ }
+ }
+}
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{
+ fn lookup(base : &usize) -> Option<(Self, usize)> {
+ match base {
+ 10 => Some((ArbitraryBytes([0xDD15_FE86, 0xAFFA_D912, 0x49EF_0EB7, 0x13F3_9EBE, 0xAA98_7B6E, 0x6FD2_A000, 0x0000_0000, 0x0000_0000]), 77)),
+ 16 => Some((ArbitraryBytes([0x1000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 63)),
+ 32 => Some((ArbitraryBytes([0x8000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000, 0x0000_0000]), 51)),
+ 52 => Some((ArbitraryBytes([0x070E_F55B, 0x69EB_9498, 0x3F55_F32D, 0x0BB1_D645, 0x1D6E_AA22, 0x3100_0000, 0x0000_0000, 0x0000_0000]), 44)),
+ 62 => Some((ArbitraryBytes([0x0437_92AD, 0xB7D6_D494, 0xD37D_50A9, 0xCA83_391F, 0x58DB_8150, 0x3744_EF95, 0x05BB_0400, 0x0000_0000]), 42)),
+ 94 => Some((ArbitraryBytes([0xC5F2_400A, 0x64FC_C0E8, 0x33E1_BCF0, 0x9749_C06B, 0xF160_B863, 0x83C3_ACB8, 0xEC85_2780, 0x0000_0000]), 39)),
+ _ => None
+ }
+ }
+}
+
+#[cfg(test)]
+mod precomputed_common_constants_tests{
+ use super::super::super::PrecomputedMaxPowers;
+ use super::super::super::ArbitraryBytes;
+ use super::super::super::iterative_conversion::IterativeBaseConversion;
+
+ #[test]
+ fn highest_fitting_power_consistency_5(){
+ let mut count = 0;
+ for base in 2..200 {
+ if let Some(precomputed) = ArbitraryBytes::<5>::lookup(&base) {
+ let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<5>,usize>::find_highest_fitting_power_non_cached(&base);
+ assert_eq!(non_cached_result.exponent, precomputed.1);
+ assert_eq!(non_cached_result.power, precomputed.0);
+ count += 1;
+ }
+ }
+ assert!(count > 0);
+ }
+ #[test]
+ fn highest_fitting_power_consistency_8(){
+ let mut count = 0;
+ for base in 2..200 {
+ if let Some(precomputed) = ArbitraryBytes::<8>::lookup(&base) {
+ let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<8>,usize>::find_highest_fitting_power_non_cached(&base);
+ assert_eq!(non_cached_result.exponent, precomputed.1);
+ assert_eq!(non_cached_result.power, precomputed.0);
+ count += 1;
+ }
+ }
+ assert!(count > 0);
+ }
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
new file mode 100644
index 0000000..1127692
--- /dev/null
+++ b/src/passwordmaker/base_conversion/iterative_conversion_impl/precomputed_constants.rs
@@ -0,0 +1,126 @@
+use super::const_mul_usize;
+use super::ArbitraryBytes;
+use super::super::iterative_conversion::PrecomputedMaxPowers;
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<5>{
+ fn lookup(base : &usize) -> Option<(Self, usize)> {
+ get_from_cache(*base, &CONSTANT_MAX_POWER_CACHE_5)
+ }
+}
+
+impl PrecomputedMaxPowers<usize> for ArbitraryBytes<8>{
+ fn lookup(base : &usize) -> Option<(Self, usize)> {
+ get_from_cache(*base, &CONSTANT_MAX_POWER_CACHE_8)
+ }
+}
+
+fn get_from_cache<const N : usize>(base : usize, cache : &[([u32;N], usize)]) -> Option<(ArbitraryBytes<N>, usize)>{
+ base.checked_sub(2).and_then(|idx|cache.get(idx))
+ .map(|c| (ArbitraryBytes(c.0), c.1))
+}
+
+const CONSTANT_MAX_POWER_CACHE_5 : [([u32;5],usize);128] = gen_const_max_power_cache();
+const CONSTANT_MAX_POWER_CACHE_8 : [([u32;8],usize);128] = gen_const_max_power_cache();
+
+//-----------------------------------------------------------------------------------------
+
+/// This version of `find_highest_fitting_power` is not optimized. But it can run in const contexts. Only use it there, use the normal one everywhere else.
+const fn const_find_highest_fitting_power<const N : usize>(base : usize) -> ([u32;N],usize){
+ let start = super::from_usize(base);
+
+ let mut x = (start, 1);
+ while let Some(next) = const_mul_usize(const_clone(&x.0),base) {
+ x.0 = next;
+ x.1 +=1;
+ }
+ (x.0.0, x.1)
+}
+
+//If anyone could tell me how to implement "~const Clone" in stable Rust, I'd be very happy.
+const fn const_clone<const N : usize>(x : &ArbitraryBytes<N>) -> ArbitraryBytes<N>{ArbitraryBytes(x.0)}
+
+const fn gen_const_max_power_cache<const N : usize, const CNT : usize>() -> [([u32;N],usize);CNT]{
+ let mut result = [([0u32;N],0usize);CNT];
+ let mut i = 0usize;
+ loop {
+ let highest = const_find_highest_fitting_power(i + 2);
+ result[i] = (highest.0, highest.1);
+ i +=1;
+ if i == CNT { break; }
+ }
+ result
+}
+
+#[cfg(test)]
+mod iterative_conversion_constants_tests{
+ use super::ArbitraryBytes;
+
+ #[test]
+ fn test_overlows_8()
+ {
+ let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate()
+ .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+ for (base, power, _exponent) in entries {
+ assert!((power * base).is_none())
+ }
+ }
+ #[test]
+ fn test_overlows_5()
+ {
+ let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate()
+ .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+ for (base, power, _exponent) in entries {
+ assert!((power * base).is_none())
+ }
+ }
+ #[test]
+ fn test_exponent_8()
+ {
+ let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate()
+ .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+ for (base, mut power, exponent) in entries {
+ //exponent is the largest fitting exponent. Soo, if we divide exponent times, we should end up with 1.
+ for _i in 0..exponent {
+ let remainder = power.div_assign_with_remainder_usize(base);
+ assert_eq!(remainder, 0);
+ }
+ assert_eq!(power, (&1usize).into());
+ }
+ }
+ #[test]
+ fn test_exponent_5()
+ {
+ let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate()
+ .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+ for (base, mut power, exponent) in entries {
+ //exponent is the largest fitting exponent. Soo, if we divide exponent times, we should end up with 1.
+ for _i in 0..exponent {
+ let remainder = power.div_assign_with_remainder_usize(base);
+ assert_eq!(remainder, 0);
+ }
+ assert_eq!(power, (&1usize).into());
+ }
+ }
+ #[test]
+ fn highest_fitting_power_consistency_5(){
+ use super::super::super::iterative_conversion::IterativeBaseConversion;
+ let entries = super::CONSTANT_MAX_POWER_CACHE_5.iter().enumerate()
+ .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+ for (base, power, exponent) in entries {
+ let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<5>,usize>::find_highest_fitting_power_non_cached(&base);
+ assert_eq!(non_cached_result.exponent,exponent);
+ assert_eq!(non_cached_result.power, power);
+ }
+ }
+ #[test]
+ fn highest_fitting_power_consistency_8(){
+ use super::super::super::iterative_conversion::IterativeBaseConversion;
+ let entries = super::CONSTANT_MAX_POWER_CACHE_8.iter().enumerate()
+ .map(|(i,(p,e))| (i+2, ArbitraryBytes(*p), *e));
+ for (base, power, exponent) in entries {
+ let non_cached_result = IterativeBaseConversion::<ArbitraryBytes<8>,usize>::find_highest_fitting_power_non_cached(&base);
+ assert_eq!(non_cached_result.exponent,exponent);
+ assert_eq!(non_cached_result.power, power);
+ }
+ }
+} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index 8d217ef..6415904 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -1,56 +1,64 @@
use std::convert::TryInto;
+use iterative_conversion_impl::PaddedShiftLeft;
+pub(super) use iterative_conversion::IterativeBaseConversion;
+pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes};
-use self::remainders::CalcRemainders;
+use self::iterative_conversion::PrecomputedMaxPowers;
-mod remainders;
-mod remainders_impl;
+mod iterative_conversion;
+mod iterative_conversion_impl;
/// Converts an input to a different base (which fits in usize). Returns the digits starting at the most significant one.
pub(super) trait BaseConversion {
- // return type is subject to change. Hopefully soon the math will be rewritten, so we can skip the Vec and IntoIter.
- // will have to remain an ExactSizeIterator though.
- fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>>;
+ type Output : ExactSizeIterator<Item=usize>;
+ fn convert_to_base(self, base : usize) -> Self::Output;
}
-impl<T, const N : usize> BaseConversion for T where T : ToI32Array<Output = [u32;N]>{
- fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> {
- self.to_int_array().calc_remainders(base).collect::<Vec<_>>().into_iter().rev()
+#[allow(clippy::trait_duplication_in_bounds)] //False positive in clippy. usize != u32.
+impl<T, const N : usize, const M : usize> BaseConversion for T
+ where T : ToArbitraryBytes<Output = ArbitraryBytes<N>>,
+ for<'a> T::Output: From<&'a usize> + From<&'a u32> + PaddedShiftLeft<Output = ArbitraryBytes<M>> + PrecomputedMaxPowers<usize>,
+{
+ type Output = IterativeBaseConversion<ArbitraryBytes<N>, usize>;
+ fn convert_to_base(self, base : usize) -> Self::Output {
+ IterativeBaseConversion::new(self.to_arbitrary_bytes(), base)
}
}
impl BaseConversion for [u8;16]{
- fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> {
- u128::from_be_bytes(self).calc_remainders(base as u128).map(|ll| ll as usize).collect::<Vec<_>>().into_iter().rev()
+ type Output = IterativeBaseConversion<SixteenBytes,usize>;
+ fn convert_to_base(self, base : usize) -> IterativeBaseConversion<SixteenBytes,usize> {
+ IterativeBaseConversion::new(SixteenBytes::new(u128::from_be_bytes(self)), base)
}
}
// Rust 1.52 only has a very limited support for const generics. This means, we'll have to live with this not-too-constrained solution...
-pub(super) trait ToI32Array {
+pub(super) trait ToArbitraryBytes {
type Output;
- fn to_int_array(self) -> Self::Output;
+ fn to_arbitrary_bytes(self) -> Self::Output;
}
//this could of course be done in a generic manner, but it's ugly without array_mut, which we don't have in Rust 1.52.
//Soo, pedestrian's approach :D
-impl ToI32Array for [u8;20] {
- type Output = [u32; 5];
- fn to_int_array(self) -> [u32; 5] {
- [
+impl ToArbitraryBytes for [u8;20] {
+ type Output = ArbitraryBytes<5>;
+ fn to_arbitrary_bytes(self) -> ArbitraryBytes<5> {
+ ArbitraryBytes::new([
u32::from_be_bytes(self[0..4].try_into().unwrap()),
u32::from_be_bytes(self[4..8].try_into().unwrap()),
u32::from_be_bytes(self[8..12].try_into().unwrap()),
u32::from_be_bytes(self[12..16].try_into().unwrap()),
u32::from_be_bytes(self[16..20].try_into().unwrap()),
- ]
+ ])
}
}
-impl ToI32Array for [u8;32] {
- type Output = [u32; 8];
- fn to_int_array(self) -> [u32; 8] {
- [
+impl ToArbitraryBytes for [u8;32] {
+ type Output = ArbitraryBytes<8>;
+ fn to_arbitrary_bytes(self) -> ArbitraryBytes<8> {
+ ArbitraryBytes::new([
u32::from_be_bytes(self[0..4].try_into().unwrap()),
u32::from_be_bytes(self[4..8].try_into().unwrap()),
u32::from_be_bytes(self[8..12].try_into().unwrap()),
@@ -59,6 +67,6 @@ impl ToI32Array for [u8;32] {
u32::from_be_bytes(self[20..24].try_into().unwrap()),
u32::from_be_bytes(self[24..28].try_into().unwrap()),
u32::from_be_bytes(self[28..32].try_into().unwrap()),
- ]
+ ])
}
} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs
deleted file mode 100644
index 93570a1..0000000
--- a/src/passwordmaker/base_conversion/remainders.rs
+++ /dev/null
@@ -1,74 +0,0 @@
-/// Adds `calc_remainders(divisor)` method to types that have some implementation of the Division trait.
-pub(super) trait CalcRemainders<T, D>{
- fn calc_remainders(self, divisor : D) -> Remainders<T,D>;
-}
-
-/// Implement `Division` to enable the `calc_remainders()` method for your type.
-pub(super) trait Division<D> where Self:Sized {
- /// does in-place arbitrary-length division. Returns remainder.
- fn divide(self, divisor : &D) -> DivisionResult<Self, D>;
- fn is_zero(&self) -> bool;
-}
-
-/// Or mark your type as `UseGenericDivision` to just use `/` and `%` operators for types. Makes only sense for integers.
-pub(super) trait UseGenericDivision : Clone
- + for <'a> std::ops::Div<&'a Self, Output = Self>
- + for <'a> std::ops::Rem<&'a Self, Output = Self>
- + Default
- + Eq {}
-
-impl<T, D> CalcRemainders<T, D> for T
- where T:Division<D>
-{
- fn calc_remainders(self, divisor : D) -> Remainders<T, D> {
- Remainders::new(self,divisor)
- }
-}
-
-pub(super) struct Remainders<T, U>{
- value : Option<T>,
- divisor : U,
-}
-
-impl<U, T:Division<U>> Remainders<T, U> {
- fn new(value : T, divisor : U) -> Self {
- let value = if value.is_zero() { None } else { Some(value) };
- Remainders {
- value,
- divisor,
- }
- }
-}
-
-impl<U, T:Division<U>> Iterator for Remainders<T,U>{
- type Item=U;
-
- fn next(&mut self) -> Option<Self::Item> {
- if let Some(v) = self.value.take() {
- let DivisionResult{result, remainder} = v.divide(&self.divisor);
- self.value = if result.is_zero() { None } else { Some(result) };
- Some(remainder)
- } else {
- None
- }
- }
-}
-
-pub(super) struct DivisionResult<T:Division<U>, U> {
- pub result : T,
- pub remainder : U,
-}
-
-impl<U> Division<U> for U
- where U: UseGenericDivision
-{
- fn divide(self, divisor : &Self) -> DivisionResult<Self, Self> {
- DivisionResult {
- result: self.clone().div(divisor),
- remainder: self.rem(divisor)
- }
- }
- fn is_zero(&self) -> bool {
- *self == Self::default()
- }
-} \ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/remainders_impl.rs b/src/passwordmaker/base_conversion/remainders_impl.rs
deleted file mode 100644
index 8f0a7f9..0000000
--- a/src/passwordmaker/base_conversion/remainders_impl.rs
+++ /dev/null
@@ -1,76 +0,0 @@
-use super::remainders::{Division, UseGenericDivision, DivisionResult};
-
-impl UseGenericDivision for u128{} //for Md4, Md5
-
-impl<const N : usize> Division<usize> for [u32;N] {
- #[allow(clippy::cast_possible_truncation)]
- fn divide(mut self, divisor : &usize) -> DivisionResult<Self, usize> {
- #[cfg(target_pointer_width = "64")]
- type UsizeAndFour = u128;
- #[cfg(not(target_pointer_width = "64"))]
- type UsizeAndFour = u64;
- debug_assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128);
-
- //uses mutation, because why not? self is owned after all :D
- let divisor : UsizeAndFour = *divisor as UsizeAndFour;
- let remainder = self.iter_mut().skip_while(|x| **x == 0).fold(0 as UsizeAndFour,|carry, current| {
- debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize.
- let carry_shifted = carry << 32;
- let dividend = (carry_shifted) + (*current as UsizeAndFour);
- let ratio = dividend / divisor;
- debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero.
- *current = (ratio) as u32;
- dividend - (*current as UsizeAndFour) * divisor
- });
- debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour));
- let remainder = remainder as usize;
- DivisionResult{
- result: self,
- remainder,
- }
- }
-
- fn is_zero(&self) -> bool {
- self.iter().all(|x| *x == 0)
- }
-}
-
-#[cfg(test)]
-mod remainders_tests{
- use super::super::remainders::CalcRemainders;
-
- use super::*;
- #[test]
- fn test_generic_division(){
- let v = 50u128;
- let d = 7u128;
- let DivisionResult{result, remainder}=v.divide(&d);
- assert_eq!(7, result);
- assert_eq!(1, remainder);
- }
-
- #[test]
- fn test_remainders() {
- //relies on generic division.
- let v = 141u128;
- let d = 3u128;
- let results : Vec<u128> = v.calc_remainders(d).collect();
- assert_eq!(results, vec![0u128,2u128,0u128,2u128,1u128])
- }
-
- #[test]
- fn test_array_divide() {
- let dividend_int = 0xe7f1ec3a5f35af805407a8a531eefb79u128;
- let dividend = [(dividend_int >> 96) as u32, ((dividend_int >> 64) & 0xffffffff) as u32, ((dividend_int >> 32) & 0xffffffff) as u32, (dividend_int & 0xffffffff) as u32];
- #[cfg(target_pointer_width = "64")]
- let divisor = 1531534813576487;
- #[cfg(not(target_pointer_width = "64"))]
- let divisor = 1531534813;
- let result_int = dividend_int / (divisor as u128);
- let remainder_int = dividend_int % (divisor as u128);
- let result = dividend.divide(&divisor);
- assert_eq!(result.result, [(result_int >> 96) as u32, ((result_int >> 64) & 0xffffffff) as u32, ((result_int >> 32) & 0xffffffff) as u32, (result_int & 0xffffffff) as u32]);
- assert_eq!(remainder_int, result.remainder as u128);
- }
-
-} \ No newline at end of file
generated by cgit v1.2.3 (git 2.46.0) at 2025-09-18 22:58:14 +0000