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    #[inline]
111    #[must_use]
112    #[track_caller]
113    pub(crate) const fn bounded_shr_by_limbs(&self, shift: u32, shift_upper_bound: u32) -> Self {
114        let mut res = *self;
115        res.as_mut_uint_ref()
116            .bounded_shr_by_limbs_assign(shift, shift_upper_bound);
117        res
118    }
119
120    /// Computes `self >> shift` in a panic-free manner, returning zero if the shift exceeds the
121    /// precision.
122    #[inline(never)]
123    #[must_use]
124    pub const fn unbounded_shr(&self, shift: u32) -> Self {
125        let mut res = *self;
126        res.as_mut_uint_ref().unbounded_shr_assign(shift);
127        res
128    }
129
130    /// Computes `self >> shift` in variable time in a panic-free manner, returning zero if the
131    /// shift exceeds the precision.
132    ///
133    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
134    ///
135    /// When used with a fixed `shift`, this function is constant-time with respect
136    /// to `self`.
137    #[inline(always)]
138    #[must_use]
139    pub const fn unbounded_shr_vartime(&self, shift: u32) -> Self {
140        let mut res = Self::ZERO;
141        self.as_uint_ref()
142            .unbounded_shr_vartime(shift, res.as_mut_uint_ref());
143        res
144    }
145
146    /// Computes `self >> (shift * Limb::BITS)` in a panic-free manner, returning zero if the
147    /// shift exceeds the precision.
148    ///
149    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
150    ///
151    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
152    #[inline(always)]
153    #[must_use]
154    pub(crate) const fn unbounded_shr_by_limbs_vartime(&self, shift: u32) -> Self {
155        let mut res = *self;
156        res.as_mut_uint_ref()
157            .unbounded_shr_assign_by_limbs_vartime(shift);
158        res
159    }
160
161    /// Computes `self >> shift` in a panic-free manner, reducing shift modulo the type's width.
162    #[inline(always)]
163    #[must_use]
164    pub const fn wrapping_shr(&self, shift: u32) -> Self {
165        self.shr(u32_rem(shift, Self::BITS))
166    }
167
168    /// Computes `self >> shift` in variable-time in a panic-free manner, reducing shift modulo
169    /// the type's width.
170    ///
171    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
172    ///
173    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
174    #[inline(always)]
175    #[must_use]
176    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
177    pub const fn wrapping_shr_vartime(&self, shift: u32) -> Self {
178        self.unbounded_shr_vartime(shift % Self::BITS)
179    }
180
181    /// Computes `self >> 1` in constant-time.
182    #[inline(always)]
183    #[must_use]
184    pub(crate) const fn shr1(&self) -> Self {
185        let mut res = *self;
186        res.as_mut_uint_ref().shr1_assign();
187        res
188    }
189
190    /// Computes `self >> shift` where `0 <= shift < Limb::BITS`,
191    /// returning the result and the carry.
192    ///
193    /// # Panics
194    /// - if `shift >= Limb::BITS`.
195    #[inline(always)]
196    #[must_use]
197    #[track_caller]
198    pub(crate) const fn shr_limb_with_carry(&self, shift: u32, carry: Limb) -> (Self, Limb) {
199        let mut res = *self;
200        let carry = res
201            .as_mut_uint_ref()
202            .shr_assign_limb_with_carry(shift, carry);
203        (res, carry)
204    }
205}
206
207macro_rules! impl_shr {
208    ($($shift:ty),+) => {
209        $(
210            impl<const LIMBS: usize> Shr<$shift> for Uint<LIMBS> {
211                type Output = Uint<LIMBS>;
212
213                #[inline]
214                fn shr(self, shift: $shift) -> Uint<LIMBS> {
215                    <&Self>::shr(&self, shift)
216                }
217            }
218
219            impl<const LIMBS: usize> Shr<$shift> for &Uint<LIMBS> {
220                type Output = Uint<LIMBS>;
221
222                #[inline]
223                fn shr(self, shift: $shift) -> Uint<LIMBS> {
224                    Uint::<LIMBS>::shr(self, u32::try_from(shift).expect("invalid shift"))
225                }
226            }
227
228            impl<const LIMBS: usize> ShrAssign<$shift> for Uint<LIMBS> {
229                fn shr_assign(&mut self, shift: $shift) {
230                    *self = self.shr(shift)
231                }
232            }
233        )+
234    };
235}
236
237impl_shr!(i32, u32, usize);
238
239impl<const LIMBS: usize> WrappingShr for Uint<LIMBS> {
240    fn wrapping_shr(&self, shift: u32) -> Uint<LIMBS> {
241        self.wrapping_shr(shift)
242    }
243}
244
245impl<const LIMBS: usize> ShrVartime for Uint<LIMBS> {
246    fn overflowing_shr_vartime(&self, shift: u32) -> Option<Self> {
247        self.overflowing_shr_vartime(shift)
248    }
249
250    fn unbounded_shr_vartime(&self, shift: u32) -> Self {
251        self.unbounded_shr_vartime(shift)
252    }
253
254    fn wrapping_shr_vartime(&self, shift: u32) -> Self {
255        self.wrapping_shr_vartime(shift)
256    }
257}
258
259#[cfg(test)]
260mod tests {
261    use crate::{Limb, ShrVartime, U128, U192, Uint, WrappingShr};
262
263    const N: U192 = U192::from_be_hex("FFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
264
265    const N_2: U192 = U192::from_be_hex("7FFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0");
266
267    #[test]
268    fn shr1() {
269        assert_eq!(N.shr1(), N_2);
270        assert_eq!(N >> 1, N_2);
271        assert_eq!(N.bounded_shr(1, 2), N_2);
272        assert_eq!(ShrVartime::overflowing_shr_vartime(&N, 1), Some(N_2));
273        assert_eq!(ShrVartime::wrapping_shr_vartime(&N, 1), N_2);
274    }
275
276    #[test]
277    fn shr_bounds() {
278        assert!(N.overflowing_shr(192).is_none().to_bool_vartime());
279        assert!(N.overflowing_shr_vartime(192).is_none());
280        assert_eq!(N.unbounded_shr(192), Uint::ZERO);
281        assert_eq!(N.unbounded_shr_vartime(192), Uint::ZERO);
282        assert_eq!(N.wrapping_shr(192), N);
283        assert_eq!(N.wrapping_shr_vartime(192), N);
284    }
285
286    #[test]
287    #[should_panic(expected = "`shift` exceeds upper bound")]
288    fn shr_bounds_panic() {
289        let _ = N >> 192;
290    }
291
292    #[test]
293    fn shr_wide_1_1_128() {
294        assert_eq!(
295            Uint::overflowing_shr_vartime_wide((U128::ONE, U128::ONE), 128).unwrap(),
296            (U128::ONE, U128::ZERO)
297        );
298    }
299
300    #[test]
301    fn shr_wide_0_max_1() {
302        assert_eq!(
303            Uint::overflowing_shr_vartime_wide((U128::ZERO, U128::MAX), 1).unwrap(),
304            (U128::ONE << 127, U128::MAX >> 1)
305        );
306    }
307
308    #[test]
309    fn shr_wide_max_max_256() {
310        assert!(Uint::overflowing_shr_vartime_wide((U128::MAX, U128::MAX), 256).is_none());
311    }
312
313    #[test]
314    #[should_panic]
315    fn shr_limb_with_carry_shift_too_large() {
316        let _ = U128::ONE.shr_limb_with_carry(Limb::BITS, Limb::ZERO);
317    }
318
319    #[test]
320    fn shr_limb_with_carry() {
321        let val = U128::from_be_hex("876543210FEDCBA90123456FEDCBA987");
322
323        // Shift by zero
324        let (res, carry) = val.shr_limb_with_carry(0, Limb::ZERO);
325        assert_eq!(res, val);
326        assert_eq!(carry, Limb::ZERO);
327
328        // Shift by one
329        let (res, carry) = val.shr_limb_with_carry(1, Limb::ZERO);
330        assert_eq!(res, val.shr_vartime(1));
331        assert_eq!(carry, val.limbs[0].shl(Limb::BITS - 1));
332
333        // Shift by any
334        let (res, carry) = val.shr_limb_with_carry(13, Limb::ZERO);
335        assert_eq!(res, val.shr_vartime(13));
336        assert_eq!(carry, val.limbs[0].shl(Limb::BITS - 13));
337
338        // Shift by max
339        let (res, carry) = val.shr_limb_with_carry(Limb::BITS - 1, Limb::ZERO);
340        assert_eq!(res, val.shr_vartime(Limb::BITS - 1));
341        assert_eq!(carry, val.limbs[0].shl(1));
342    }
343
344    #[test]
345    fn shr_by_limbs() {
346        let val = Uint::<2>::from_words([1, 99]);
347        assert_eq!(val.bounded_shr_by_limbs(0, 3).as_words(), &[1, 99]);
348        assert_eq!(val.bounded_shr_by_limbs(1, 3).as_words(), &[99, 0]);
349        assert_eq!(val.bounded_shr_by_limbs(2, 3).as_words(), &[0, 0]);
350        assert_eq!(val.unbounded_shr_by_limbs_vartime(0).as_words(), &[1, 99]);
351        assert_eq!(val.unbounded_shr_by_limbs_vartime(1).as_words(), &[99, 0]);
352        assert_eq!(val.unbounded_shr_by_limbs_vartime(2).as_words(), &[0, 0]);
353    }
354
355    #[test]
356    fn overflowing_shr() {
357        assert_eq!(
358            U192::from_u8(16).overflowing_shr(2).into_option(),
359            Some(U192::from_u8(4))
360        );
361        assert_eq!(U192::ONE.overflowing_shr(U192::BITS).into_option(), None);
362        assert_eq!(
363            ShrVartime::overflowing_shr_vartime(&U192::from_u8(16), 2),
364            Some(U192::from_u8(4))
365        );
366        assert_eq!(
367            ShrVartime::overflowing_shr_vartime(&U192::ONE, U192::BITS),
368            None
369        );
370    }
371
372    #[test]
373    fn unbounded_shr() {
374        assert_eq!(U192::from_u8(16).unbounded_shr(2), U192::from_u8(4));
375        assert_eq!(U192::MAX.unbounded_shr(U192::BITS), U192::ZERO);
376        assert_eq!(
377            ShrVartime::unbounded_shr_vartime(&U192::from_u8(16), 2),
378            U192::from_u8(4)
379        );
380        assert_eq!(
381            ShrVartime::unbounded_shr_vartime(&U192::MAX, U192::BITS),
382            U192::ZERO
383        );
384    }
385
386    #[test]
387    fn wrapping_shr() {
388        assert_eq!(
389            WrappingShr::wrapping_shr(&U192::from_u8(16), 2),
390            U192::from_u8(4)
391        );
392        assert_eq!(WrappingShr::wrapping_shr(&U192::ONE, U192::BITS), U192::ONE);
393        assert_eq!(
394            ShrVartime::wrapping_shr_vartime(&U192::from_u8(16), 2),
395            U192::from_u8(4)
396        );
397        assert_eq!(
398            ShrVartime::wrapping_shr_vartime(&U192::ONE, U192::BITS),
399            U192::ONE
400        );
401    }
402}
crypto_bigint/uint/shr.rs

crypto_bigint/uint/
shr.rs
