diff options
Diffstat (limited to 'vendor/crypto-bigint/src/uint/mul.rs')
-rw-r--r-- | vendor/crypto-bigint/src/uint/mul.rs | 150 |
1 files changed, 116 insertions, 34 deletions
diff --git a/vendor/crypto-bigint/src/uint/mul.rs b/vendor/crypto-bigint/src/uint/mul.rs index ecb32fd10..fcfc756aa 100644 --- a/vendor/crypto-bigint/src/uint/mul.rs +++ b/vendor/crypto-bigint/src/uint/mul.rs @@ -1,10 +1,10 @@ -//! [`UInt`] addition operations. +//! [`Uint`] addition operations. -use crate::{Checked, CheckedMul, Concat, Limb, UInt, Wrapping, Zero}; +use crate::{Checked, CheckedMul, Concat, Limb, Uint, WideWord, Word, Wrapping, Zero}; use core::ops::{Mul, MulAssign}; use subtle::CtOption; -impl<const LIMBS: usize> UInt<LIMBS> { +impl<const LIMBS: usize> Uint<LIMBS> { /// Compute "wide" multiplication, with a product twice the size of the input. /// /// Returns a tuple containing the `(lo, hi)` components of the product. @@ -75,17 +75,91 @@ impl<const LIMBS: usize> UInt<LIMBS> { self.mul_wide(rhs).0 } - /// Square self, returning a "wide" result. + /// Square self, returning a concatenated "wide" result. pub fn square(&self) -> <Self as Concat>::Output where Self: Concat, { - let (lo, hi) = self.mul_wide(self); + let (lo, hi) = self.square_wide(); hi.concat(&lo) } + + /// Square self, returning a "wide" result in two parts as (lo, hi). + pub const fn square_wide(&self) -> (Self, Self) { + // Translated from https://github.com/ucbrise/jedi-pairing/blob/c4bf151/include/core/bigint.hpp#L410 + // + // Permission to relicense the resulting translation as Apache 2.0 + MIT was given + // by the original author Sam Kumar: https://github.com/RustCrypto/crypto-bigint/pull/133#discussion_r1056870411 + let mut lo = Self::ZERO; + let mut hi = Self::ZERO; + + // Schoolbook multiplication, but only considering half of the multiplication grid + let mut i = 1; + while i < LIMBS { + let mut j = 0; + let mut carry = Limb::ZERO; + + while j < i { + let k = i + j; + + if k >= LIMBS { + let (n, c) = hi.limbs[k - LIMBS].mac(self.limbs[i], self.limbs[j], carry); + hi.limbs[k - LIMBS] = n; + carry = c; + } else { + let (n, c) = lo.limbs[k].mac(self.limbs[i], self.limbs[j], carry); + lo.limbs[k] = n; + carry = c; + } + + j += 1; + } + + if (2 * i) < LIMBS { + lo.limbs[2 * i] = carry; + } else { + hi.limbs[2 * i - LIMBS] = carry; + } + + i += 1; + } + + // Double the current result, this accounts for the other half of the multiplication grid. + // TODO: The top word is empty so we can also use a special purpose shl. + (lo, hi) = Self::shl_vartime_wide((lo, hi), 1); + + // Handle the diagonal of the multiplication grid, which finishes the multiplication grid. + let mut carry = Limb::ZERO; + let mut i = 0; + while i < LIMBS { + if (i * 2) < LIMBS { + let (n, c) = lo.limbs[i * 2].mac(self.limbs[i], self.limbs[i], carry); + lo.limbs[i * 2] = n; + carry = c; + } else { + let (n, c) = hi.limbs[i * 2 - LIMBS].mac(self.limbs[i], self.limbs[i], carry); + hi.limbs[i * 2 - LIMBS] = n; + carry = c; + } + + if (i * 2 + 1) < LIMBS { + let n = lo.limbs[i * 2 + 1].0 as WideWord + carry.0 as WideWord; + lo.limbs[i * 2 + 1] = Limb(n as Word); + carry = Limb((n >> Word::BITS) as Word); + } else { + let n = hi.limbs[i * 2 + 1 - LIMBS].0 as WideWord + carry.0 as WideWord; + hi.limbs[i * 2 + 1 - LIMBS] = Limb(n as Word); + carry = Limb((n >> Word::BITS) as Word); + } + + i += 1; + } + + (lo, hi) + } } -impl<const LIMBS: usize> CheckedMul<&UInt<LIMBS>> for UInt<LIMBS> { +impl<const LIMBS: usize> CheckedMul<&Uint<LIMBS>> for Uint<LIMBS> { type Output = Self; fn checked_mul(&self, rhs: &Self) -> CtOption<Self> { @@ -94,89 +168,89 @@ impl<const LIMBS: usize> CheckedMul<&UInt<LIMBS>> for UInt<LIMBS> { } } -impl<const LIMBS: usize> Mul for Wrapping<UInt<LIMBS>> { +impl<const LIMBS: usize> Mul for Wrapping<Uint<LIMBS>> { type Output = Self; - fn mul(self, rhs: Self) -> Wrapping<UInt<LIMBS>> { + fn mul(self, rhs: Self) -> Wrapping<Uint<LIMBS>> { Wrapping(self.0.wrapping_mul(&rhs.0)) } } -impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> { - type Output = Wrapping<UInt<LIMBS>>; +impl<const LIMBS: usize> Mul<&Wrapping<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> { + type Output = Wrapping<Uint<LIMBS>>; - fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> { + fn mul(self, rhs: &Wrapping<Uint<LIMBS>>) -> Wrapping<Uint<LIMBS>> { Wrapping(self.0.wrapping_mul(&rhs.0)) } } -impl<const LIMBS: usize> Mul<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> { - type Output = Wrapping<UInt<LIMBS>>; +impl<const LIMBS: usize> Mul<Wrapping<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> { + type Output = Wrapping<Uint<LIMBS>>; - fn mul(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> { + fn mul(self, rhs: Wrapping<Uint<LIMBS>>) -> Wrapping<Uint<LIMBS>> { Wrapping(self.0.wrapping_mul(&rhs.0)) } } -impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> { - type Output = Wrapping<UInt<LIMBS>>; +impl<const LIMBS: usize> Mul<&Wrapping<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> { + type Output = Wrapping<Uint<LIMBS>>; - fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> { + fn mul(self, rhs: &Wrapping<Uint<LIMBS>>) -> Wrapping<Uint<LIMBS>> { Wrapping(self.0.wrapping_mul(&rhs.0)) } } -impl<const LIMBS: usize> MulAssign for Wrapping<UInt<LIMBS>> { +impl<const LIMBS: usize> MulAssign for Wrapping<Uint<LIMBS>> { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } -impl<const LIMBS: usize> MulAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> { +impl<const LIMBS: usize> MulAssign<&Wrapping<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> { fn mul_assign(&mut self, other: &Self) { *self = *self * other; } } -impl<const LIMBS: usize> Mul for Checked<UInt<LIMBS>> { +impl<const LIMBS: usize> Mul for Checked<Uint<LIMBS>> { type Output = Self; - fn mul(self, rhs: Self) -> Checked<UInt<LIMBS>> { + fn mul(self, rhs: Self) -> Checked<Uint<LIMBS>> { Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b)))) } } -impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> { - type Output = Checked<UInt<LIMBS>>; +impl<const LIMBS: usize> Mul<&Checked<Uint<LIMBS>>> for Checked<Uint<LIMBS>> { + type Output = Checked<Uint<LIMBS>>; - fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> { + fn mul(self, rhs: &Checked<Uint<LIMBS>>) -> Checked<Uint<LIMBS>> { Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b)))) } } -impl<const LIMBS: usize> Mul<Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> { - type Output = Checked<UInt<LIMBS>>; +impl<const LIMBS: usize> Mul<Checked<Uint<LIMBS>>> for &Checked<Uint<LIMBS>> { + type Output = Checked<Uint<LIMBS>>; - fn mul(self, rhs: Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> { + fn mul(self, rhs: Checked<Uint<LIMBS>>) -> Checked<Uint<LIMBS>> { Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b)))) } } -impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> { - type Output = Checked<UInt<LIMBS>>; +impl<const LIMBS: usize> Mul<&Checked<Uint<LIMBS>>> for &Checked<Uint<LIMBS>> { + type Output = Checked<Uint<LIMBS>>; - fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> { + fn mul(self, rhs: &Checked<Uint<LIMBS>>) -> Checked<Uint<LIMBS>> { Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b)))) } } -impl<const LIMBS: usize> MulAssign for Checked<UInt<LIMBS>> { +impl<const LIMBS: usize> MulAssign for Checked<Uint<LIMBS>> { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } -impl<const LIMBS: usize> MulAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> { +impl<const LIMBS: usize> MulAssign<&Checked<Uint<LIMBS>>> for Checked<Uint<LIMBS>> { fn mul_assign(&mut self, other: &Self) { *self = *self * other; } @@ -184,7 +258,7 @@ impl<const LIMBS: usize> MulAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS #[cfg(test)] mod tests { - use crate::{CheckedMul, Zero, U64}; + use crate::{CheckedMul, Zero, U256, U64}; #[test] fn mul_wide_zero_and_one() { @@ -196,7 +270,7 @@ mod tests { #[test] fn mul_wide_lo_only() { - let primes: &[u32] = &[3, 5, 17, 256, 65537]; + let primes: &[u32] = &[3, 5, 17, 257, 65537]; for &a_int in primes { for &b_int in primes { @@ -243,4 +317,12 @@ mod tests { assert_eq!(lo, U64::from_u64(1)); assert_eq!(hi, U64::from_u64(0xffff_ffff_ffff_fffe)); } + + #[test] + fn square_larger() { + let n = U256::MAX; + let (hi, lo) = n.square().split(); + assert_eq!(lo, U256::ONE); + assert_eq!(hi, U256::MAX.wrapping_sub(&U256::ONE)); + } } |