crypto_bigint/uint/
shr.rs

1//! [`Uint`] bitwise right shift operations.
2
3use crate::{CtOption, Limb, Shr, ShrAssign, ShrVartime, Uint, WrappingShr, primitives::u32_rem};
4
5impl<const LIMBS: usize> Uint<LIMBS> {
6    /// Computes `self >> shift`.
7    ///
8    /// # Panics
9    /// - if `shift >= Self::BITS`.
10    #[inline(never)]
11    #[must_use]
12    #[track_caller]
13    pub const fn shr(&self, shift: u32) -> Self {
14        let mut res = *self;
15        res.as_mut_uint_ref().bounded_shr_assign(shift, Self::BITS);
16        res
17    }
18
19    /// Computes `self >> shift` in variable time.
20    ///
21    /// # Panics
22    /// - if `shift >= Self::BITS`.
23    #[inline(always)]
24    #[must_use]
25    pub const fn shr_vartime(&self, shift: u32) -> Self {
26        self.overflowing_shr_vartime(shift)
27            .expect("`shift` exceeds upper bound")
28    }
29
30    /// Computes `self >> shift`.
31    ///
32    /// Returns `None` if `shift >= Self::BITS`.
33    #[inline(never)]
34    #[must_use]
35    pub const fn overflowing_shr(&self, shift: u32) -> CtOption<Self> {
36        let mut res = *self;
37        let overflow = res.as_mut_uint_ref().overflowing_shr_assign(shift);
38        CtOption::new(res, overflow.not())
39    }
40
41    /// Computes `self >> shift`.
42    ///
43    /// Returns `None` if `shift >= Self::BITS`.
44    ///
45    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
46    ///
47    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
48    #[inline(always)]
49    #[must_use]
50    pub const fn overflowing_shr_vartime(&self, shift: u32) -> Option<Self> {
51        if shift < Self::BITS {
52            Some(self.unbounded_shr_vartime(shift))
53        } else {
54            None
55        }
56    }
57
58    /// Computes a right shift on a wide input as `(lo, hi)`.
59    ///
60    /// Returns `None` if `shift >= Self::BITS`.
61    ///
62    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
63    ///
64    /// When used with a fixed `shift`, this function is constant-time with respect
65    /// to `self`.
66    #[inline(always)]
67    #[must_use]
68    pub const fn overflowing_shr_vartime_wide(
69        lower_upper: (Self, Self),
70        shift: u32,
71    ) -> Option<(Self, Self)> {
72        let (lower, upper) = lower_upper;
73        if shift >= 2 * Self::BITS {
74            None
75        } else if shift >= Self::BITS {
76            let lower = upper.unbounded_shr_vartime(shift - Self::BITS);
77            Some((lower, Self::ZERO))
78        } else {
79            let new_upper = upper.unbounded_shr_vartime(shift);
80            let lower_hi = upper.unbounded_shl_vartime(Self::BITS - shift);
81            let lower_lo = lower.unbounded_shr_vartime(shift);
82            Some((lower_lo.bitor(&lower_hi), new_upper))
83        }
84    }
85
86    /// Computes `self >> shift` where `shift < shift_upper_bound`.
87    ///
88    /// The runtime is determined by `shift_upper_bound` which may be larger or smaller than
89    /// `Self::BITS`.
90    ///
91    /// # Panics
92    /// - if the shift exceeds the upper bound.
93    #[inline(never)]
94    #[must_use]
95    #[track_caller]
96    pub const fn bounded_shr(&self, shift: u32, shift_upper_bound: u32) -> Self {
97        let mut res = *self;
98        res.as_mut_uint_ref()
99            .bounded_shr_assign(shift, shift_upper_bound);
100        res
101    }
102
103    /// Computes `self >> (shift * Limb::BITS)` where `shift < shift_upper_bound`.
104    ///
105    /// The runtime is determined by `shift_upper_bound` which may be larger or smaller than
106    /// `LIMBS`.
107    ///
108    /// # Panics
109    /// - if the shift exceeds the upper bound.
110    #[must_use]
111    #[track_caller]
112    pub(crate) const fn bounded_shr_by_limbs(&self, shift: u32, shift_upper_bound: u32) -> Self {
113        let mut res = *self;
114        res.as_mut_uint_ref()
115            .bounded_shr_by_limbs_assign(shift, shift_upper_bound);
116        res
117    }
118
119    /// Computes `self >> shift` in a panic-free manner, returning zero if the shift exceeds the
120    /// precision.
121    #[inline(never)]
122    #[must_use]
123    pub const fn unbounded_shr(&self, shift: u32) -> Self {
124        let mut res = *self;
125        res.as_mut_uint_ref().unbounded_shr_assign(shift);
126        res
127    }
128
129    /// Computes `self >> shift` in variable time in a panic-free manner, returning zero if the
130    /// shift exceeds the precision.
131    ///
132    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
133    ///
134    /// When used with a fixed `shift`, this function is constant-time with respect
135    /// to `self`.
136    #[inline(always)]
137    #[must_use]
138    pub const fn unbounded_shr_vartime(&self, shift: u32) -> Self {
139        let mut res = Self::ZERO;
140        self.as_uint_ref()
141            .unbounded_shr_vartime(shift, res.as_mut_uint_ref());
142        res
143    }
144
145    /// Computes `self >> (shift * Limb::BITS)` in a panic-free manner, returning zero if the
146    /// shift exceeds the precision.
147    ///
148    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
149    ///
150    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
151    #[inline(always)]
152    #[must_use]
153    pub(crate) const fn unbounded_shr_by_limbs_vartime(&self, shift: u32) -> Self {
154        let mut res = *self;
155        res.as_mut_uint_ref()
156            .unbounded_shr_assign_by_limbs_vartime(shift);
157        res
158    }
159
160    /// Computes `self >> shift` in a panic-free manner, reducing shift modulo the type's width.
161    #[inline(always)]
162    #[must_use]
163    pub const fn wrapping_shr(&self, shift: u32) -> Self {
164        self.shr(u32_rem(shift, Self::BITS))
165    }
166
167    /// Computes `self >> shift` in variable-time in a panic-free manner, reducing shift modulo
168    /// the type's width.
169    ///
170    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
171    ///
172    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
173    #[inline(always)]
174    #[must_use]
175    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
176    pub const fn wrapping_shr_vartime(&self, shift: u32) -> Self {
177        self.unbounded_shr_vartime(shift % Self::BITS)
178    }
179
180    /// Computes `self >> 1` in constant-time.
181    #[inline(always)]
182    #[must_use]
183    pub(crate) const fn shr1(&self) -> Self {
184        let mut res = *self;
185        res.as_mut_uint_ref().shr1_assign();
186        res
187    }
188
189    /// Computes `self >> shift` where `0 <= shift < Limb::BITS`,
190    /// returning the result and the carry.
191    ///
192    /// # Panics
193    /// - if `shift >= Limb::BITS`.
194    #[inline(always)]
195    #[must_use]
196    #[track_caller]
197    pub(crate) const fn shr_limb_with_carry(&self, shift: u32, carry: Limb) -> (Self, Limb) {
198        let mut res = *self;
199        let carry = res
200            .as_mut_uint_ref()
201            .shr_assign_limb_with_carry(shift, carry);
202        (res, carry)
203    }
204}
205
206macro_rules! impl_shr {
207    ($($shift:ty),+) => {
208        $(
209            impl<const LIMBS: usize> Shr<$shift> for Uint<LIMBS> {
210                type Output = Uint<LIMBS>;
211
212                #[inline]
213                fn shr(self, shift: $shift) -> Uint<LIMBS> {
214                    <&Self>::shr(&self, shift)
215                }
216            }
217
218            impl<const LIMBS: usize> Shr<$shift> for &Uint<LIMBS> {
219                type Output = Uint<LIMBS>;
220
221                #[inline]
222                fn shr(self, shift: $shift) -> Uint<LIMBS> {
223                    Uint::<LIMBS>::shr(self, u32::try_from(shift).expect("invalid shift"))
224                }
225            }
226
227            impl<const LIMBS: usize> ShrAssign<$shift> for Uint<LIMBS> {
228                fn shr_assign(&mut self, shift: $shift) {
229                    *self = self.shr(shift)
230                }
231            }
232        )+
233    };
234}
235
236impl_shr!(i32, u32, usize);
237
238impl<const LIMBS: usize> WrappingShr for Uint<LIMBS> {
239    fn wrapping_shr(&self, shift: u32) -> Uint<LIMBS> {
240        self.wrapping_shr(shift)
241    }
242}
243
244impl<const LIMBS: usize> ShrVartime for Uint<LIMBS> {
245    fn overflowing_shr_vartime(&self, shift: u32) -> Option<Self> {
246        self.overflowing_shr_vartime(shift)
247    }
248
249    fn unbounded_shr_vartime(&self, shift: u32) -> Self {
250        self.unbounded_shr_vartime(shift)
251    }
252
253    fn wrapping_shr_vartime(&self, shift: u32) -> Self {
254        self.wrapping_shr_vartime(shift)
255    }
256}
257
258#[cfg(test)]
259mod tests {
260    use crate::{Limb, ShrVartime, U128, U192, Uint, WrappingShr};
261
262    const N: U192 = U192::from_be_hex("FFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
263
264    const N_2: U192 = U192::from_be_hex("7FFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0");
265
266    #[test]
267    fn shr1() {
268        assert_eq!(N.shr1(), N_2);
269        assert_eq!(N >> 1, N_2);
270        assert_eq!(N.bounded_shr(1, 2), N_2);
271        assert_eq!(ShrVartime::overflowing_shr_vartime(&N, 1), Some(N_2));
272        assert_eq!(ShrVartime::wrapping_shr_vartime(&N, 1), N_2);
273    }
274
275    #[test]
276    fn shr_bounds() {
277        assert!(N.overflowing_shr(192).is_none().to_bool_vartime());
278        assert!(N.overflowing_shr_vartime(192).is_none());
279        assert_eq!(N.unbounded_shr(192), Uint::ZERO);
280        assert_eq!(N.unbounded_shr_vartime(192), Uint::ZERO);
281        assert_eq!(N.wrapping_shr(192), N);
282        assert_eq!(N.wrapping_shr_vartime(192), N);
283    }
284
285    #[test]
286    #[should_panic(expected = "`shift` exceeds upper bound")]
287    fn shr_bounds_panic() {
288        let _ = N >> 192;
289    }
290
291    #[test]
292    fn shr_wide_1_1_128() {
293        assert_eq!(
294            Uint::overflowing_shr_vartime_wide((U128::ONE, U128::ONE), 128).unwrap(),
295            (U128::ONE, U128::ZERO)
296        );
297    }
298
299    #[test]
300    fn shr_wide_0_max_1() {
301        assert_eq!(
302            Uint::overflowing_shr_vartime_wide((U128::ZERO, U128::MAX), 1).unwrap(),
303            (U128::ONE << 127, U128::MAX >> 1)
304        );
305    }
306
307    #[test]
308    fn shr_wide_max_max_256() {
309        assert!(Uint::overflowing_shr_vartime_wide((U128::MAX, U128::MAX), 256).is_none());
310    }
311
312    #[test]
313    #[should_panic]
314    fn shr_limb_with_carry_shift_too_large() {
315        let _ = U128::ONE.shr_limb_with_carry(Limb::BITS, Limb::ZERO);
316    }
317
318    #[test]
319    fn shr_limb_with_carry() {
320        let val = U128::from_be_hex("876543210FEDCBA90123456FEDCBA987");
321
322        // Shift by zero
323        let (res, carry) = val.shr_limb_with_carry(0, Limb::ZERO);
324        assert_eq!(res, val);
325        assert_eq!(carry, Limb::ZERO);
326
327        // Shift by one
328        let (res, carry) = val.shr_limb_with_carry(1, Limb::ZERO);
329        assert_eq!(res, val.shr_vartime(1));
330        assert_eq!(carry, val.limbs[0].shl(Limb::BITS - 1));
331
332        // Shift by any
333        let (res, carry) = val.shr_limb_with_carry(13, Limb::ZERO);
334        assert_eq!(res, val.shr_vartime(13));
335        assert_eq!(carry, val.limbs[0].shl(Limb::BITS - 13));
336
337        // Shift by max
338        let (res, carry) = val.shr_limb_with_carry(Limb::BITS - 1, Limb::ZERO);
339        assert_eq!(res, val.shr_vartime(Limb::BITS - 1));
340        assert_eq!(carry, val.limbs[0].shl(1));
341    }
342
343    #[test]
344    fn shr_by_limbs() {
345        let val = Uint::<2>::from_words([1, 99]);
346        assert_eq!(val.bounded_shr_by_limbs(0, 3).as_words(), &[1, 99]);
347        assert_eq!(val.bounded_shr_by_limbs(1, 3).as_words(), &[99, 0]);
348        assert_eq!(val.bounded_shr_by_limbs(2, 3).as_words(), &[0, 0]);
349        assert_eq!(val.unbounded_shr_by_limbs_vartime(0).as_words(), &[1, 99]);
350        assert_eq!(val.unbounded_shr_by_limbs_vartime(1).as_words(), &[99, 0]);
351        assert_eq!(val.unbounded_shr_by_limbs_vartime(2).as_words(), &[0, 0]);
352    }
353
354    #[test]
355    fn overflowing_shr() {
356        assert_eq!(
357            U192::from_u8(16).overflowing_shr(2).into_option(),
358            Some(U192::from_u8(4))
359        );
360        assert_eq!(U192::ONE.overflowing_shr(U192::BITS).into_option(), None);
361        assert_eq!(
362            ShrVartime::overflowing_shr_vartime(&U192::from_u8(16), 2),
363            Some(U192::from_u8(4))
364        );
365        assert_eq!(
366            ShrVartime::overflowing_shr_vartime(&U192::ONE, U192::BITS),
367            None
368        );
369    }
370
371    #[test]
372    fn unbounded_shr() {
373        assert_eq!(U192::from_u8(16).unbounded_shr(2), U192::from_u8(4));
374        assert_eq!(U192::MAX.unbounded_shr(U192::BITS), U192::ZERO);
375        assert_eq!(
376            ShrVartime::unbounded_shr_vartime(&U192::from_u8(16), 2),
377            U192::from_u8(4)
378        );
379        assert_eq!(
380            ShrVartime::unbounded_shr_vartime(&U192::MAX, U192::BITS),
381            U192::ZERO
382        );
383    }
384
385    #[test]
386    fn wrapping_shr() {
387        assert_eq!(
388            WrappingShr::wrapping_shr(&U192::from_u8(16), 2),
389            U192::from_u8(4)
390        );
391        assert_eq!(WrappingShr::wrapping_shr(&U192::ONE, U192::BITS), U192::ONE);
392        assert_eq!(
393            ShrVartime::wrapping_shr_vartime(&U192::from_u8(16), 2),
394            U192::from_u8(4)
395        );
396        assert_eq!(
397            ShrVartime::wrapping_shr_vartime(&U192::ONE, U192::BITS),
398            U192::ONE
399        );
400    }
401}
crypto_bigint/uint/shr.rs

crypto_bigint/uint/
shr.rs
