Merging upstream version 1.71.1+dfsg1.

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

1 files changed, 119 insertions, 25 deletions

diff --git a/vendor/crypto-bigint/src/uint/shl.rs b/vendor/crypto-bigint/src/uint/shl.rs
index 9d4669130..eb8c713c9 100644
--- a/vendor/crypto-bigint/src/uint/shl.rs
+++ b/vendor/crypto-bigint/src/uint/shl.rs
@@ -1,9 +1,65 @@
-//! [`UInt`] bitwise left shift operations.
+//! [`Uint`] bitwise left shift operations.
 
-use crate::{Limb, UInt, Word};
+use crate::{limb::HI_BIT, CtChoice, Limb, Uint, Word};
 use core::ops::{Shl, ShlAssign};
 
-impl<const LIMBS: usize> UInt<LIMBS> {
+impl<const LIMBS: usize> Uint<LIMBS> {
+    /// Computes `self << 1` in constant-time, returning the overflowing bit as a `CtChoice`.
+    pub(crate) const fn shl_1(&self) -> (Self, CtChoice) {
+        let mut shifted_bits = [0; LIMBS];
+        let mut i = 0;
+        while i < LIMBS {
+            shifted_bits[i] = self.limbs[i].0 << 1;
+            i += 1;
+        }
+
+        let mut carry_bits = [0; LIMBS];
+        let mut i = 0;
+        while i < LIMBS {
+            carry_bits[i] = self.limbs[i].0 >> HI_BIT;
+            i += 1;
+        }
+
+        let mut limbs = [Limb(0); LIMBS];
+
+        limbs[0] = Limb(shifted_bits[0]);
+        let mut i = 1;
+        while i < LIMBS {
+            limbs[i] = Limb(shifted_bits[i] | carry_bits[i - 1]);
+            i += 1;
+        }
+
+        (Uint::new(limbs), CtChoice::from_lsb(carry_bits[LIMBS - 1]))
+    }
+
+    /// Computes `self << shift` where `0 <= shift < Limb::BITS`,
+    /// returning the result and the carry.
+    #[inline(always)]
+    pub(crate) const fn shl_limb(&self, n: usize) -> (Self, Limb) {
+        let mut limbs = [Limb::ZERO; LIMBS];
+
+        let nz = Limb(n as Word).ct_is_nonzero();
+        let lshift = n as Word;
+        let rshift = Limb::ct_select(Limb::ZERO, Limb((Limb::BITS - n) as Word), nz).0;
+        let carry = Limb::ct_select(
+            Limb::ZERO,
+            Limb(self.limbs[LIMBS - 1].0.wrapping_shr(Word::BITS - n as u32)),
+            nz,
+        );
+
+        let mut i = LIMBS - 1;
+        while i > 0 {
+            let mut limb = self.limbs[i].0 << lshift;
+            let hi = self.limbs[i - 1].0 >> rshift;
+            limb |= nz.if_true(hi);
+            limbs[i] = Limb(limb);
+            i -= 1
+        }
+        limbs[0] = Limb(self.limbs[0].0 << lshift);
+
+        (Uint::<LIMBS>::new(limbs), carry)
+    }
+
     /// Computes `self << shift`.
     ///
     /// NOTE: this operation is variable time with respect to `n` *ONLY*.
@@ -14,55 +70,69 @@ impl<const LIMBS: usize> UInt<LIMBS> {
     pub const fn shl_vartime(&self, n: usize) -> Self {
         let mut limbs = [Limb::ZERO; LIMBS];
 
-        if n >= Limb::BIT_SIZE * LIMBS {
+        if n >= Limb::BITS * LIMBS {
             return Self { limbs };
         }
 
-        let shift_num = n / Limb::BIT_SIZE;
-        let rem = n % Limb::BIT_SIZE;
-        let nz = Limb(rem as Word).is_nonzero();
-        let lshift_rem = rem as Word;
-        let rshift_rem = Limb::ct_select(Limb::ZERO, Limb((Limb::BIT_SIZE - rem) as Word), nz).0;
+        let shift_num = n / Limb::BITS;
+        let rem = n % Limb::BITS;
 
-        let mut i = LIMBS - 1;
+        let mut i = LIMBS;
         while i > shift_num {
-            let mut limb = self.limbs[i - shift_num].0 << lshift_rem;
-            let hi = self.limbs[i - shift_num - 1].0 >> rshift_rem;
-            limb |= hi & nz;
-            limbs[i] = Limb(limb);
-            i -= 1
+            i -= 1;
+            limbs[i] = self.limbs[i - shift_num];
         }
-        limbs[shift_num] = Limb(self.limbs[0].0 << lshift_rem);
 
-        Self { limbs }
+        let (new_lower, _carry) = (Self { limbs }).shl_limb(rem);
+        new_lower
+    }
+
+    /// Computes a left shift on a wide input as `(lo, hi)`.
+    ///
+    /// NOTE: this operation is variable time with respect to `n` *ONLY*.
+    ///
+    /// When used with a fixed `n`, this function is constant-time with respect
+    /// to `self`.
+    #[inline(always)]
+    pub const fn shl_vartime_wide(lower_upper: (Self, Self), n: usize) -> (Self, Self) {
+        let (lower, mut upper) = lower_upper;
+        let new_lower = lower.shl_vartime(n);
+        upper = upper.shl_vartime(n);
+        if n >= Self::BITS {
+            upper = upper.bitor(&lower.shl_vartime(n - Self::BITS));
+        } else {
+            upper = upper.bitor(&lower.shr_vartime(Self::BITS - n));
+        }
+
+        (new_lower, upper)
     }
 }
 
-impl<const LIMBS: usize> Shl<usize> for UInt<LIMBS> {
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Shl<usize> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
 
     /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
     ///
     /// When used with a fixed `rhs`, this function is constant-time with respect
     /// to `self`.
-    fn shl(self, rhs: usize) -> UInt<LIMBS> {
+    fn shl(self, rhs: usize) -> Uint<LIMBS> {
         self.shl_vartime(rhs)
     }
 }
 
-impl<const LIMBS: usize> Shl<usize> for &UInt<LIMBS> {
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Shl<usize> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
 
     /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
     ///
     /// When used with a fixed `rhs`, this function is constant-time with respect
     /// to `self`.
-    fn shl(self, rhs: usize) -> UInt<LIMBS> {
+    fn shl(self, rhs: usize) -> Uint<LIMBS> {
         self.shl_vartime(rhs)
     }
 }
 
-impl<const LIMBS: usize> ShlAssign<usize> for UInt<LIMBS> {
+impl<const LIMBS: usize> ShlAssign<usize> for Uint<LIMBS> {
     /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
     ///
     /// When used with a fixed `rhs`, this function is constant-time with respect
@@ -74,7 +144,7 @@ impl<const LIMBS: usize> ShlAssign<usize> for UInt<LIMBS> {
 
 #[cfg(test)]
 mod tests {
-    use crate::U256;
+    use crate::{Limb, Uint, U128, U256};
 
     const N: U256 =
         U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
@@ -131,4 +201,28 @@ mod tests {
     fn shl64() {
         assert_eq!(N << 64, SIXTY_FOUR);
     }
+
+    #[test]
+    fn shl_wide_1_1_128() {
+        assert_eq!(
+            Uint::shl_vartime_wide((U128::ONE, U128::ONE), 128),
+            (U128::ZERO, U128::ONE)
+        );
+    }
+
+    #[test]
+    fn shl_wide_max_0_1() {
+        assert_eq!(
+            Uint::shl_vartime_wide((U128::MAX, U128::ZERO), 1),
+            (U128::MAX.sbb(&U128::ONE, Limb::ZERO).0, U128::ONE)
+        );
+    }
+
+    #[test]
+    fn shl_wide_max_max_256() {
+        assert_eq!(
+            Uint::shl_vartime_wide((U128::MAX, U128::MAX), 256),
+            (U128::ZERO, U128::ZERO)
+        );
+    }
 }