Merging upstream version 1.71.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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));
+    }
 }