crypto_bigint/uint/
shr.rs

Help
1//! [`Uint`] bitwise right shift operations.
2
3use super::Uint;
4use crate::{limb::HI_BIT, CtChoice, Limb, Word};
5use core::ops::{Shr, ShrAssign};
6
7impl<const LIMBS: usize> Uint<LIMBS> {
8    /// Computes `self >> 1` in constant-time, returning [`CtChoice::TRUE`] if the overflowing bit
9    /// was set, and [`CtChoice::FALSE`] otherwise.
10    pub(crate) const fn shr_1(&self) -> (Self, CtChoice) {
11        let mut shifted_bits = [0; LIMBS];
12        let mut i = 0;
13        while i < LIMBS {
14            shifted_bits[i] = self.limbs[i].0 >> 1;
15            i += 1;
16        }
17
18        let mut carry_bits = [0; LIMBS];
19        let mut i = 0;
20        while i < LIMBS {
21            carry_bits[i] = self.limbs[i].0 << HI_BIT;
22            i += 1;
23        }
24
25        let mut limbs = [Limb(0); LIMBS];
26
27        let mut i = 0;
28        while i < (LIMBS - 1) {
29            limbs[i] = Limb(shifted_bits[i] | carry_bits[i + 1]);
30            i += 1;
31        }
32        limbs[LIMBS - 1] = Limb(shifted_bits[LIMBS - 1]);
33
34        debug_assert!(carry_bits[LIMBS - 1] == 0 || carry_bits[LIMBS - 1] == (1 << HI_BIT));
35        (
36            Uint::new(limbs),
37            CtChoice::from_lsb(carry_bits[0] >> HI_BIT),
38        )
39    }
40
41    /// Computes `self >> n`.
42    ///
43    /// NOTE: this operation is variable time with respect to `n` *ONLY*.
44    ///
45    /// When used with a fixed `n`, this function is constant-time with respect
46    /// to `self`.
47    #[inline(always)]
48    pub const fn shr_vartime(&self, shift: usize) -> Self {
49        let full_shifts = shift / Limb::BITS;
50        let small_shift = shift & (Limb::BITS - 1);
51        let mut limbs = [Limb::ZERO; LIMBS];
52
53        if shift > Limb::BITS * LIMBS {
54            return Self { limbs };
55        }
56
57        let n = LIMBS - full_shifts;
58        let mut i = 0;
59
60        if small_shift == 0 {
61            while i < n {
62                limbs[i] = Limb(self.limbs[i + full_shifts].0);
63                i += 1;
64            }
65        } else {
66            while i < n {
67                let mut lo = self.limbs[i + full_shifts].0 >> small_shift;
68
69                if i < (LIMBS - 1) - full_shifts {
70                    lo |= self.limbs[i + full_shifts + 1].0 << (Limb::BITS - small_shift);
71                }
72
73                limbs[i] = Limb(lo);
74                i += 1;
75            }
76        }
77
78        Self { limbs }
79    }
80
81    /// Computes a right shift on a wide input as `(lo, hi)`.
82    ///
83    /// NOTE: this operation is variable time with respect to `n` *ONLY*.
84    ///
85    /// When used with a fixed `n`, this function is constant-time with respect
86    /// to `self`.
87    #[inline(always)]
88    pub const fn shr_vartime_wide(lower_upper: (Self, Self), n: usize) -> (Self, Self) {
89        let (mut lower, upper) = lower_upper;
90        let new_upper = upper.shr_vartime(n);
91        lower = lower.shr_vartime(n);
92        if n >= Self::BITS {
93            lower = lower.bitor(&upper.shr_vartime(n - Self::BITS));
94        } else {
95            lower = lower.bitor(&upper.shl_vartime(Self::BITS - n));
96        }
97
98        (lower, new_upper)
99    }
100
101    /// Computes `self << n`.
102    /// Returns zero if `n >= Self::BITS`.
103    pub const fn shr(&self, shift: usize) -> Self {
104        let overflow = CtChoice::from_usize_lt(shift, Self::BITS).not();
105        let shift = shift % Self::BITS;
106        let mut result = *self;
107        let mut i = 0;
108        while i < Self::LOG2_BITS {
109            let bit = CtChoice::from_lsb((shift as Word >> i) & 1);
110            result = Uint::ct_select(&result, &result.shr_vartime(1 << i), bit);
111            i += 1;
112        }
113
114        Uint::ct_select(&result, &Self::ZERO, overflow)
115    }
116}
117
118impl<const LIMBS: usize> Shr<usize> for Uint<LIMBS> {
119    type Output = Uint<LIMBS>;
120
121    /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
122    ///
123    /// When used with a fixed `rhs`, this function is constant-time with respect
124    /// to `self`.
125    fn shr(self, rhs: usize) -> Uint<LIMBS> {
126        Uint::<LIMBS>::shr(&self, rhs)
127    }
128}
129
130impl<const LIMBS: usize> Shr<usize> for &Uint<LIMBS> {
131    type Output = Uint<LIMBS>;
132
133    /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
134    ///
135    /// When used with a fixed `rhs`, this function is constant-time with respect
136    /// to `self`.
137    fn shr(self, rhs: usize) -> Uint<LIMBS> {
138        self.shr(rhs)
139    }
140}
141
142impl<const LIMBS: usize> ShrAssign<usize> for Uint<LIMBS> {
143    fn shr_assign(&mut self, rhs: usize) {
144        *self = self.shr(rhs);
145    }
146}
147
148#[cfg(test)]
149mod tests {
150    use crate::{Uint, U128, U256};
151
152    const N: U256 =
153        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
154
155    const N_2: U256 =
156        U256::from_be_hex("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0");
157
158    #[test]
159    fn shr1() {
160        assert_eq!(N >> 1, N_2);
161    }
162
163    #[test]
164    fn shr_wide_1_1_128() {
165        assert_eq!(
166            Uint::shr_vartime_wide((U128::ONE, U128::ONE), 128),
167            (U128::ONE, U128::ZERO)
168        );
169    }
170
171    #[test]
172    fn shr_wide_0_max_1() {
173        assert_eq!(
174            Uint::shr_vartime_wide((U128::ZERO, U128::MAX), 1),
175            (U128::ONE << 127, U128::MAX >> 1)
176        );
177    }
178
179    #[test]
180    fn shr_wide_max_max_256() {
181        assert_eq!(
182            Uint::shr_vartime_wide((U128::MAX, U128::MAX), 256),
183            (U128::ZERO, U128::ZERO)
184        );
185    }
186}
crypto_bigint/uint/shr.rs

crypto_bigint/uint/
shr.rs
