#[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};
pub(crate) struct SixteenBytes(u128);
impl SixteenBytes{
pub(super) fn new(value : u128) -> Self {
SixteenBytes(value)
}
}
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{}
#[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]; #[cfg(target_pointer_width = "64")]
if N > 1 { result[N-2] = (x >> 32) as u32;}
if N > 0 { result[N-1] = x as u32;} 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)
}
}
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>{
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> {
if value.0[0..N.saturating_sub(2)].iter().any(|x| *x != 0) {
Err(ArbitraryBytesToUsizeError)
} else {
let last_bit = value.0.get(N-1).copied().ok_or(ArbitraryBytesToUsizeError);
let second_last_bit = value.0.get(N-2).copied().unwrap_or_default();
#[allow(clippy::cast_possible_truncation)] 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> {
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>> {
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 { 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)
}
}
impl<const N : usize> MulAssign<&usize> for ArbitraryBytes<N>{
#[allow(clippy::cast_possible_truncation)] 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>>;
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|{
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)] 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{
match Ord::cmp(self, divisor){
std::cmp::Ordering::Less => Self::from(&0_usize), std::cmp::Ordering::Equal => { *self = Self::from(&0_usize); Self::from(&1_usize) },
std::cmp::Ordering::Greater => {
if let Ok(divisor_as_u32) = divisor.try_into() {
self.rem_assign_with_quotient_u32(divisor_as_u32)
} else {
self.rem_assign_with_quotient_knuth(divisor)
}
},
}
}
}
macro_rules! make_div_assign_with_remainder {
($name:ident, $t_divisor:ty, $t_long:ty) => {
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)); 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); *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))
}
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);
let n_digits_divisor= N - divisor.find_first_nonzero_digit();
debug_assert!(n_digits_divisor > 1);
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;
let normalize_shift = divisor.get_digit_from_right(n_digits_divisor - 1).leading_zeros();
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();
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));
for j in (0..=m_extra_digits_dividend).rev() {
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;
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;
}
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()]);
if did_overflow {
guesstimate -= 1;
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);
}
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;
#[test]
fn knuth_add_back_test(){
let mut dividend = ArbitraryBytes::new([
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
}
#[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);
}
}
#[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));
}
}
}