diff options
Diffstat (limited to 'vendor/crypto-bigint/src/uint/shl.rs')
-rw-r--r-- | vendor/crypto-bigint/src/uint/shl.rs | 144 |
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) + ); + } } |