From 9835e2ae736235810b4ea1c162ca5e65c547e770 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 18 May 2024 04:49:50 +0200 Subject: Merging upstream version 1.71.1+dfsg1. Signed-off-by: Daniel Baumann --- vendor/crypto-bigint/src/uint/div.rs | 600 +++++++++++++++++++++++++---------- 1 file changed, 424 insertions(+), 176 deletions(-) (limited to 'vendor/crypto-bigint/src/uint/div.rs') diff --git a/vendor/crypto-bigint/src/uint/div.rs b/vendor/crypto-bigint/src/uint/div.rs index f7d9d6bf3..90741c472 100644 --- a/vendor/crypto-bigint/src/uint/div.rs +++ b/vendor/crypto-bigint/src/uint/div.rs @@ -1,33 +1,68 @@ -//! [`UInt`] division operations. +//! [`Uint`] division operations. -use super::UInt; -use crate::limb::Word; -use crate::{Integer, Limb, NonZero, Wrapping}; +use super::div_limb::{div_rem_limb_with_reciprocal, Reciprocal}; +use crate::{CtChoice, Limb, NonZero, Uint, Word, Wrapping}; use core::ops::{Div, DivAssign, Rem, RemAssign}; -use subtle::{Choice, CtOption}; +use subtle::CtOption; + +impl Uint { + /// Computes `self` / `rhs` using a pre-made reciprocal, + /// returns the quotient (q) and remainder (r). + #[inline(always)] + pub const fn ct_div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) { + div_rem_limb_with_reciprocal(self, reciprocal) + } + + /// Computes `self` / `rhs` using a pre-made reciprocal, + /// returns the quotient (q) and remainder (r). + #[inline(always)] + pub fn div_rem_limb_with_reciprocal( + &self, + reciprocal: &CtOption, + ) -> CtOption<(Self, Limb)> { + reciprocal.map(|r| div_rem_limb_with_reciprocal(self, &r)) + } + + /// Computes `self` / `rhs`, returns the quotient (q) and remainder (r). + /// Returns the truthy value as the third element of the tuple if `rhs != 0`, + /// and the falsy value otherwise. + #[inline(always)] + pub(crate) const fn ct_div_rem_limb(&self, rhs: Limb) -> (Self, Limb, CtChoice) { + let (reciprocal, is_some) = Reciprocal::ct_new(rhs); + let (quo, rem) = div_rem_limb_with_reciprocal(self, &reciprocal); + (quo, rem, is_some) + } + + /// Computes `self` / `rhs`, returns the quotient (q) and remainder (r). + #[inline(always)] + pub fn div_rem_limb(&self, rhs: NonZero) -> (Self, Limb) { + // Guaranteed to succeed since `rhs` is nonzero. + let (quo, rem, _is_some) = self.ct_div_rem_limb(*rhs); + (quo, rem) + } -impl UInt { /// Computes `self` / `rhs`, returns the quotient (q), remainder (r) - /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`]. - /// NOTE: Use only if you need to access const fn. Otherwise use `div_rem` because + /// and the truthy value for is_some or the falsy value for is_none. + /// + /// NOTE: Use only if you need to access const fn. Otherwise use [`Self::div_rem`] because /// the value for is_some needs to be checked before using `q` and `r`. /// /// This is variable only with respect to `rhs`. /// /// When used with a fixed `rhs`, this function is constant-time with respect /// to `self`. - pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, u8) { + pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, CtChoice) { let mb = rhs.bits_vartime(); - let mut bd = (LIMBS * Limb::BIT_SIZE) - mb; + let mut bd = Self::BITS - mb; let mut rem = *self; let mut quo = Self::ZERO; let mut c = rhs.shl_vartime(bd); loop { let (mut r, borrow) = rem.sbb(&c, Limb::ZERO); - rem = Self::ct_select(r, rem, borrow.0); + rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0)); r = quo.bitor(&Self::ONE); - quo = Self::ct_select(r, quo, borrow.0); + quo = Self::ct_select(&r, &quo, CtChoice::from_mask(borrow.0)); if bd == 0 { break; } @@ -36,27 +71,28 @@ impl UInt { quo = quo.shl_vartime(1); } - let is_some = Limb(mb as Word).is_nonzero(); - quo = Self::ct_select(Self::ZERO, quo, is_some); - (quo, rem, (is_some & 1) as u8) + let is_some = Limb(mb as Word).ct_is_nonzero(); + quo = Self::ct_select(&Self::ZERO, &quo, is_some); + (quo, rem, is_some) } /// Computes `self` % `rhs`, returns the remainder and - /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`]. - /// NOTE: Use only if you need to access const fn. Otherwise use `reduce` + /// and the truthy value for is_some or the falsy value for is_none. + /// + /// NOTE: Use only if you need to access const fn. Otherwise use [`Self::rem`]. /// This is variable only with respect to `rhs`. /// /// When used with a fixed `rhs`, this function is constant-time with respect /// to `self`. - pub(crate) const fn ct_reduce(&self, rhs: &Self) -> (Self, u8) { + pub const fn const_rem(&self, rhs: &Self) -> (Self, CtChoice) { let mb = rhs.bits_vartime(); - let mut bd = (LIMBS * Limb::BIT_SIZE) - mb; + let mut bd = Self::BITS - mb; let mut rem = *self; let mut c = rhs.shl_vartime(bd); loop { let (r, borrow) = rem.sbb(&c, Limb::ZERO); - rem = Self::ct_select(r, rem, borrow.0); + rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0)); if bd == 0 { break; } @@ -64,20 +100,55 @@ impl UInt { c = c.shr_vartime(1); } - let is_some = Limb(mb as Word).is_nonzero(); - (rem, (is_some & 1) as u8) + let is_some = Limb(mb as Word).ct_is_nonzero(); + (rem, is_some) + } + + /// Computes `self` % `rhs`, returns the remainder and + /// and the truthy value for is_some or the falsy value for is_none. + /// + /// This is variable only with respect to `rhs`. + /// + /// When used with a fixed `rhs`, this function is constant-time with respect + /// to `self`. + pub const fn const_rem_wide(lower_upper: (Self, Self), rhs: &Self) -> (Self, CtChoice) { + let mb = rhs.bits_vartime(); + + // The number of bits to consider is two sets of limbs * BITS - mb (modulus bitcount) + let mut bd = (2 * Self::BITS) - mb; + + // The wide integer to reduce, split into two halves + let (mut lower, mut upper) = lower_upper; + + // Factor of the modulus, split into two halves + let mut c = Self::shl_vartime_wide((*rhs, Uint::ZERO), bd); + + loop { + let (lower_sub, borrow) = lower.sbb(&c.0, Limb::ZERO); + let (upper_sub, borrow) = upper.sbb(&c.1, borrow); + + lower = Self::ct_select(&lower_sub, &lower, CtChoice::from_mask(borrow.0)); + upper = Self::ct_select(&upper_sub, &upper, CtChoice::from_mask(borrow.0)); + if bd == 0 { + break; + } + bd -= 1; + c = Self::shr_vartime_wide(c, 1); + } + + let is_some = Limb(mb as Word).ct_is_nonzero(); + (lower, is_some) } /// Computes `self` % 2^k. Faster than reduce since its a power of 2. - /// Limited to 2^16-1 since UInt doesn't support higher. - pub const fn reduce2k(&self, k: usize) -> Self { + /// Limited to 2^16-1 since Uint doesn't support higher. + pub const fn rem2k(&self, k: usize) -> Self { let highest = (LIMBS - 1) as u32; - let index = k as u32 / (Limb::BIT_SIZE as u32); - let res = Limb::ct_cmp(Limb::from_u32(index), Limb::from_u32(highest)) - 1; - let le = Limb::is_nonzero(Limb(res as Word)); + let index = k as u32 / (Limb::BITS as u32); + let le = Limb::ct_le(Limb::from_u32(index), Limb::from_u32(highest)); let word = Limb::ct_select(Limb::from_u32(highest), Limb::from_u32(index), le).0 as usize; - let base = k % Limb::BIT_SIZE; + let base = k % Limb::BITS; let mask = (1 << base) - 1; let mut out = *self; @@ -94,266 +165,418 @@ impl UInt { out } - /// Computes self / rhs, returns the quotient, remainder - /// if rhs != 0 - pub fn div_rem(&self, rhs: &Self) -> CtOption<(Self, Self)> { - let (q, r, c) = self.ct_div_rem(rhs); - CtOption::new((q, r), Choice::from(c)) + /// Computes self / rhs, returns the quotient, remainder. + pub fn div_rem(&self, rhs: &NonZero) -> (Self, Self) { + // Since `rhs` is nonzero, this should always hold. + let (q, r, _c) = self.ct_div_rem(rhs); + (q, r) } - /// Computes self % rhs, returns the remainder - /// if rhs != 0 - pub fn reduce(&self, rhs: &Self) -> CtOption { - let (r, c) = self.ct_reduce(rhs); - CtOption::new(r, Choice::from(c)) + /// Computes self % rhs, returns the remainder. + pub fn rem(&self, rhs: &NonZero) -> Self { + // Since `rhs` is nonzero, this should always hold. + let (r, _c) = self.const_rem(rhs); + r } /// Wrapped division is just normal division i.e. `self` / `rhs` /// There’s no way wrapping could ever happen. /// This function exists, so that all operations are accounted for in the wrapping operations. + /// + /// Panics if `rhs == 0`. pub const fn wrapping_div(&self, rhs: &Self) -> Self { let (q, _, c) = self.ct_div_rem(rhs); - assert!(c == 1, "divide by zero"); + assert!(c.is_true_vartime(), "divide by zero"); q } /// Perform checked division, returning a [`CtOption`] which `is_some` /// only if the rhs != 0 pub fn checked_div(&self, rhs: &Self) -> CtOption { - let (q, _, c) = self.ct_div_rem(rhs); - CtOption::new(q, Choice::from(c)) + NonZero::new(*rhs).map(|rhs| { + let (q, _r) = self.div_rem(&rhs); + q + }) } /// Wrapped (modular) remainder calculation is just `self` % `rhs`. /// There’s no way wrapping could ever happen. /// This function exists, so that all operations are accounted for in the wrapping operations. + /// + /// Panics if `rhs == 0`. pub const fn wrapping_rem(&self, rhs: &Self) -> Self { - let (r, c) = self.ct_reduce(rhs); - assert!(c == 1, "modulo zero"); + let (r, c) = self.const_rem(rhs); + assert!(c.is_true_vartime(), "modulo zero"); r } /// Perform checked reduction, returning a [`CtOption`] which `is_some` /// only if the rhs != 0 pub fn checked_rem(&self, rhs: &Self) -> CtOption { - let (r, c) = self.ct_reduce(rhs); - CtOption::new(r, Choice::from(c)) + NonZero::new(*rhs).map(|rhs| self.rem(&rhs)) } } -impl Div<&NonZero>> for &UInt -where - UInt: Integer, -{ - type Output = UInt; +// +// Division by a single limb +// + +impl Div<&NonZero> for &Uint { + type Output = Uint; - fn div(self, rhs: &NonZero>) -> Self::Output { + fn div(self, rhs: &NonZero) -> Self::Output { *self / *rhs } } -impl Div<&NonZero>> for UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Div<&NonZero> for Uint { + type Output = Uint; - fn div(self, rhs: &NonZero>) -> Self::Output { + fn div(self, rhs: &NonZero) -> Self::Output { self / *rhs } } -impl Div>> for &UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Div> for &Uint { + type Output = Uint; - fn div(self, rhs: NonZero>) -> Self::Output { + fn div(self, rhs: NonZero) -> Self::Output { *self / rhs } } -impl Div>> for UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Div> for Uint { + type Output = Uint; - fn div(self, rhs: NonZero>) -> Self::Output { - let (q, _, _) = self.ct_div_rem(&rhs); + fn div(self, rhs: NonZero) -> Self::Output { + let (q, _, _) = self.ct_div_rem_limb(*rhs); q } } -impl DivAssign<&NonZero>> for UInt -where - UInt: Integer, -{ - fn div_assign(&mut self, rhs: &NonZero>) { - let (q, _, _) = self.ct_div_rem(rhs); - *self = q +impl DivAssign<&NonZero> for Uint { + fn div_assign(&mut self, rhs: &NonZero) { + *self /= *rhs; } } -impl DivAssign>> for UInt -where - UInt: Integer, -{ - fn div_assign(&mut self, rhs: NonZero>) { - *self /= &rhs; +impl DivAssign> for Uint { + fn div_assign(&mut self, rhs: NonZero) { + *self = *self / rhs; } } -impl Div>> for Wrapping> { - type Output = Wrapping>; +impl Div> for Wrapping> { + type Output = Wrapping>; - fn div(self, rhs: NonZero>) -> Self::Output { - Wrapping(self.0.wrapping_div(rhs.as_ref())) + fn div(self, rhs: NonZero) -> Self::Output { + Wrapping(self.0 / rhs) } } -impl Div>> for &Wrapping> { - type Output = Wrapping>; +impl Div> for &Wrapping> { + type Output = Wrapping>; - fn div(self, rhs: NonZero>) -> Self::Output { + fn div(self, rhs: NonZero) -> Self::Output { *self / rhs } } -impl Div<&NonZero>> for &Wrapping> { - type Output = Wrapping>; +impl Div<&NonZero> for &Wrapping> { + type Output = Wrapping>; - fn div(self, rhs: &NonZero>) -> Self::Output { + fn div(self, rhs: &NonZero) -> Self::Output { *self / *rhs } } -impl Div<&NonZero>> for Wrapping> { - type Output = Wrapping>; +impl Div<&NonZero> for Wrapping> { + type Output = Wrapping>; - fn div(self, rhs: &NonZero>) -> Self::Output { + fn div(self, rhs: &NonZero) -> Self::Output { self / *rhs } } -impl DivAssign<&NonZero>> for Wrapping> { - fn div_assign(&mut self, rhs: &NonZero>) { - *self = Wrapping(self.0.wrapping_div(rhs.as_ref())) +impl DivAssign<&NonZero> for Wrapping> { + fn div_assign(&mut self, rhs: &NonZero) { + *self = Wrapping(self.0 / rhs) } } -impl DivAssign>> for Wrapping> { - fn div_assign(&mut self, rhs: NonZero>) { +impl DivAssign> for Wrapping> { + fn div_assign(&mut self, rhs: NonZero) { *self /= &rhs; } } -impl Rem<&NonZero>> for &UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Rem<&NonZero> for &Uint { + type Output = Limb; - fn rem(self, rhs: &NonZero>) -> Self::Output { + fn rem(self, rhs: &NonZero) -> Self::Output { *self % *rhs } } -impl Rem<&NonZero>> for UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Rem<&NonZero> for Uint { + type Output = Limb; - fn rem(self, rhs: &NonZero>) -> Self::Output { + fn rem(self, rhs: &NonZero) -> Self::Output { self % *rhs } } -impl Rem>> for &UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Rem> for &Uint { + type Output = Limb; - fn rem(self, rhs: NonZero>) -> Self::Output { + fn rem(self, rhs: NonZero) -> Self::Output { *self % rhs } } -impl Rem>> for UInt -where - UInt: Integer, -{ - type Output = UInt; +impl Rem> for Uint { + type Output = Limb; - fn rem(self, rhs: NonZero>) -> Self::Output { - let (r, _) = self.ct_reduce(&rhs); + fn rem(self, rhs: NonZero) -> Self::Output { + let (_, r, _) = self.ct_div_rem_limb(*rhs); r } } -impl RemAssign<&NonZero>> for UInt -where - UInt: Integer, -{ - fn rem_assign(&mut self, rhs: &NonZero>) { - let (r, _) = self.ct_reduce(rhs); - *self = r +impl RemAssign<&NonZero> for Uint { + fn rem_assign(&mut self, rhs: &NonZero) { + *self = (*self % rhs).into(); } } -impl RemAssign>> for UInt -where - UInt: Integer, -{ - fn rem_assign(&mut self, rhs: NonZero>) { +impl RemAssign> for Uint { + fn rem_assign(&mut self, rhs: NonZero) { *self %= &rhs; } } -impl Rem>> for Wrapping> { - type Output = Wrapping>; +impl Rem> for Wrapping> { + type Output = Wrapping; + + fn rem(self, rhs: NonZero) -> Self::Output { + Wrapping(self.0 % rhs) + } +} + +impl Rem> for &Wrapping> { + type Output = Wrapping; + + fn rem(self, rhs: NonZero) -> Self::Output { + *self % rhs + } +} + +impl Rem<&NonZero> for &Wrapping> { + type Output = Wrapping; + + fn rem(self, rhs: &NonZero) -> Self::Output { + *self % *rhs + } +} + +impl Rem<&NonZero> for Wrapping> { + type Output = Wrapping; + + fn rem(self, rhs: &NonZero) -> Self::Output { + self % *rhs + } +} + +impl RemAssign> for Wrapping> { + fn rem_assign(&mut self, rhs: NonZero) { + *self %= &rhs; + } +} + +impl RemAssign<&NonZero> for Wrapping> { + fn rem_assign(&mut self, rhs: &NonZero) { + *self = Wrapping((self.0 % rhs).into()) + } +} + +// +// Division by an Uint +// + +impl Div<&NonZero>> for &Uint { + type Output = Uint; + + fn div(self, rhs: &NonZero>) -> Self::Output { + *self / *rhs + } +} + +impl Div<&NonZero>> for Uint { + type Output = Uint; + + fn div(self, rhs: &NonZero>) -> Self::Output { + self / *rhs + } +} + +impl Div>> for &Uint { + type Output = Uint; + + fn div(self, rhs: NonZero>) -> Self::Output { + *self / rhs + } +} + +impl Div>> for Uint { + type Output = Uint; + + fn div(self, rhs: NonZero>) -> Self::Output { + let (q, _) = self.div_rem(&rhs); + q + } +} + +impl DivAssign<&NonZero>> for Uint { + fn div_assign(&mut self, rhs: &NonZero>) { + *self /= *rhs + } +} + +impl DivAssign>> for Uint { + fn div_assign(&mut self, rhs: NonZero>) { + *self = *self / rhs; + } +} + +impl Div>> for Wrapping> { + type Output = Wrapping>; + + fn div(self, rhs: NonZero>) -> Self::Output { + Wrapping(self.0 / rhs) + } +} + +impl Div>> for &Wrapping> { + type Output = Wrapping>; - fn rem(self, rhs: NonZero>) -> Self::Output { - Wrapping(self.0.wrapping_rem(rhs.as_ref())) + fn div(self, rhs: NonZero>) -> Self::Output { + *self / rhs + } +} + +impl Div<&NonZero>> for &Wrapping> { + type Output = Wrapping>; + + fn div(self, rhs: &NonZero>) -> Self::Output { + *self / *rhs } } -impl Rem>> for &Wrapping> { - type Output = Wrapping>; +impl Div<&NonZero>> for Wrapping> { + type Output = Wrapping>; + + fn div(self, rhs: &NonZero>) -> Self::Output { + self / *rhs + } +} - fn rem(self, rhs: NonZero>) -> Self::Output { +impl DivAssign<&NonZero>> for Wrapping> { + fn div_assign(&mut self, rhs: &NonZero>) { + *self = Wrapping(self.0 / rhs); + } +} + +impl DivAssign>> for Wrapping> { + fn div_assign(&mut self, rhs: NonZero>) { + *self /= &rhs; + } +} + +impl Rem<&NonZero>> for &Uint { + type Output = Uint; + + fn rem(self, rhs: &NonZero>) -> Self::Output { + *self % *rhs + } +} + +impl Rem<&NonZero>> for Uint { + type Output = Uint; + + fn rem(self, rhs: &NonZero>) -> Self::Output { + self % *rhs + } +} + +impl Rem>> for &Uint { + type Output = Uint; + + fn rem(self, rhs: NonZero>) -> Self::Output { *self % rhs } } -impl Rem<&NonZero>> for &Wrapping> { - type Output = Wrapping>; +impl Rem>> for Uint { + type Output = Uint; + + fn rem(self, rhs: NonZero>) -> Self::Output { + Self::rem(&self, &rhs) + } +} + +impl RemAssign<&NonZero>> for Uint { + fn rem_assign(&mut self, rhs: &NonZero>) { + *self %= *rhs + } +} + +impl RemAssign>> for Uint { + fn rem_assign(&mut self, rhs: NonZero>) { + *self = *self % rhs; + } +} + +impl Rem>> for Wrapping> { + type Output = Wrapping>; - fn rem(self, rhs: &NonZero>) -> Self::Output { + fn rem(self, rhs: NonZero>) -> Self::Output { + Wrapping(self.0 % rhs) + } +} + +impl Rem>> for &Wrapping> { + type Output = Wrapping>; + + fn rem(self, rhs: NonZero>) -> Self::Output { + *self % rhs + } +} + +impl Rem<&NonZero>> for &Wrapping> { + type Output = Wrapping>; + + fn rem(self, rhs: &NonZero>) -> Self::Output { *self % *rhs } } -impl Rem<&NonZero>> for Wrapping> { - type Output = Wrapping>; +impl Rem<&NonZero>> for Wrapping> { + type Output = Wrapping>; - fn rem(self, rhs: &NonZero>) -> Self::Output { + fn rem(self, rhs: &NonZero>) -> Self::Output { self % *rhs } } -impl RemAssign>> for Wrapping> { - fn rem_assign(&mut self, rhs: NonZero>) { +impl RemAssign>> for Wrapping> { + fn rem_assign(&mut self, rhs: NonZero>) { *self %= &rhs; } } -impl RemAssign<&NonZero>> for Wrapping> { - fn rem_assign(&mut self, rhs: &NonZero>) { - *self = Wrapping(self.0.wrapping_rem(rhs.as_ref())) +impl RemAssign<&NonZero>> for Wrapping> { + fn rem_assign(&mut self, rhs: &NonZero>) { + *self = Wrapping(self.0 % rhs) } } @@ -387,7 +610,7 @@ mod tests { let lhs = U256::from(*n); let rhs = U256::from(*d); let (q, r, is_some) = lhs.ct_div_rem(&rhs); - assert_eq!(is_some, 1); + assert!(is_some.is_true_vartime()); assert_eq!(U256::from(*e), q); assert_eq!(U256::from(*ee), r); } @@ -401,9 +624,9 @@ mod tests { let num = U256::random(&mut rng).shr_vartime(128); let den = U256::random(&mut rng).shr_vartime(128); let n = num.checked_mul(&den); - if n.is_some().unwrap_u8() == 1 { + if n.is_some().into() { let (q, _, is_some) = n.unwrap().ct_div_rem(&den); - assert_eq!(is_some, 1); + assert!(is_some.is_true_vartime()); assert_eq!(q, num); } } @@ -415,17 +638,17 @@ mod tests { let mut b = U256::ZERO; b.limbs[b.limbs.len() - 1] = Limb(Word::MAX); let q = a.wrapping_div(&b); - assert_eq!(q, UInt::ZERO); + assert_eq!(q, Uint::ZERO); a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7)); b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7)); let q = a.wrapping_div(&b); - assert_eq!(q, UInt::ZERO); + assert_eq!(q, Uint::ZERO); } #[test] fn div_zero() { let (q, r, is_some) = U256::ONE.ct_div_rem(&U256::ZERO); - assert_eq!(is_some, 0); + assert!(!is_some.is_true_vartime()); assert_eq!(q, U256::ZERO); assert_eq!(r, U256::ONE); } @@ -433,36 +656,49 @@ mod tests { #[test] fn div_one() { let (q, r, is_some) = U256::from(10u8).ct_div_rem(&U256::ONE); - assert_eq!(is_some, 1); + assert!(is_some.is_true_vartime()); assert_eq!(q, U256::from(10u8)); assert_eq!(r, U256::ZERO); } #[test] fn reduce_one() { - let (r, is_some) = U256::from(10u8).ct_reduce(&U256::ONE); - assert_eq!(is_some, 1); + let (r, is_some) = U256::from(10u8).const_rem(&U256::ONE); + assert!(is_some.is_true_vartime()); assert_eq!(r, U256::ZERO); } #[test] fn reduce_zero() { let u = U256::from(10u8); - let (r, is_some) = u.ct_reduce(&U256::ZERO); - assert_eq!(is_some, 0); + let (r, is_some) = u.const_rem(&U256::ZERO); + assert!(!is_some.is_true_vartime()); assert_eq!(r, u); } #[test] fn reduce_tests() { - let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(2u8)); - assert_eq!(is_some, 1); + let (r, is_some) = U256::from(10u8).const_rem(&U256::from(2u8)); + assert!(is_some.is_true_vartime()); assert_eq!(r, U256::ZERO); - let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(3u8)); - assert_eq!(is_some, 1); + let (r, is_some) = U256::from(10u8).const_rem(&U256::from(3u8)); + assert!(is_some.is_true_vartime()); assert_eq!(r, U256::ONE); - let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(7u8)); - assert_eq!(is_some, 1); + let (r, is_some) = U256::from(10u8).const_rem(&U256::from(7u8)); + assert!(is_some.is_true_vartime()); + assert_eq!(r, U256::from(3u8)); + } + + #[test] + fn reduce_tests_wide_zero_padded() { + let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(2u8)); + assert!(is_some.is_true_vartime()); + assert_eq!(r, U256::ZERO); + let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(3u8)); + assert!(is_some.is_true_vartime()); + assert_eq!(r, U256::ONE); + let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(7u8)); + assert!(is_some.is_true_vartime()); assert_eq!(r, U256::from(3u8)); } @@ -472,7 +708,7 @@ mod tests { let mut b = U256::ZERO; b.limbs[b.limbs.len() - 1] = Limb(Word::MAX); let r = a.wrapping_rem(&b); - assert_eq!(r, UInt::ZERO); + assert_eq!(r, Uint::ZERO); a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7)); b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7)); let r = a.wrapping_rem(&b); @@ -481,16 +717,28 @@ mod tests { #[cfg(feature = "rand")] #[test] - fn reduce2krand() { + fn rem2krand() { let mut rng = ChaChaRng::from_seed([7u8; 32]); for _ in 0..25 { let num = U256::random(&mut rng); let k = (rng.next_u32() % 256) as usize; let den = U256::ONE.shl_vartime(k); - let a = num.reduce2k(k); + let a = num.rem2k(k); let e = num.wrapping_rem(&den); assert_eq!(a, e); } } + + #[test] + fn rem_trait() { + let a = U256::from(10u64); + let b = NonZero::new(U256::from(3u64)).unwrap(); + let c = U256::from(1u64); + + assert_eq!(a % b, c); + assert_eq!(a % &b, c); + assert_eq!(&a % b, c); + assert_eq!(&a % &b, c); + } } -- cgit v1.2.3