crypto_bigint/int/
shr.rs

1//! [`Int`] bitwise right shift operations.
2
3use crate::{Choice, CtOption, Int, ShrVartime, Uint, WrappingShr, primitives::u32_rem};
4use core::ops::{Shr, ShrAssign};
5
6impl<const LIMBS: usize> Int<LIMBS> {
7    /// Computes `self >> shift`.
8    ///
9    /// Note, this is _signed_ shift right, i.e., the value shifted in on the left is equal to
10    /// the most significant bit.
11    ///
12    /// # Panics
13    /// - if `shift >= Self::BITS`.
14    #[inline(always)]
15    #[must_use]
16    pub const fn shr(&self, shift: u32) -> Self {
17        let sign_bits = Self::select(&Self::ZERO, &Self::MINUS_ONE, self.is_negative());
18        let res = Uint::shr(&self.0, shift);
19        Self::from_bits(res.bitor(&sign_bits.0.unbounded_shl(Self::BITS - shift)))
20    }
21
22    /// Computes `self >> shift` in variable time.
23    ///
24    /// Note, this is _signed_ shift right, i.e., the value shifted in on the left is equal to
25    /// the most significant bit.
26    ///
27    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
28    ///
29    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
30    ///
31    /// # Panics
32    /// - if `shift >= Self::BITS`.
33    #[inline(always)]
34    #[must_use]
35    #[track_caller]
36    pub const fn shr_vartime(&self, shift: u32) -> Self {
37        self.overflowing_shr_vartime(shift)
38            .expect("`shift` within the bit size of the integer")
39    }
40
41    /// Computes `self >> shift`.
42    ///
43    /// Note, this is _signed_ shift right, i.e., the value shifted in on the left is equal to
44    /// the most significant bit.
45    ///
46    /// Returns `None` if `shift >= Self::BITS`.
47    #[inline(always)]
48    #[must_use]
49    #[allow(clippy::integer_division_remainder_used, reason = "needs triage")]
50    pub const fn overflowing_shr(&self, shift: u32) -> CtOption<Self> {
51        let in_range = Choice::from_u32_lt(shift, Self::BITS);
52        let adj_shift = in_range.select_u32(0, shift);
53        CtOption::new(self.shr(adj_shift), in_range)
54    }
55
56    /// Computes `self >> shift`.
57    ///
58    /// NOTE: this is _signed_ shift right, i.e., the value shifted in on the left is equal to
59    /// the most significant bit.
60    ///
61    /// Returns `None` if `shift >= Self::BITS`.
62    ///
63    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
64    ///
65    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
66    #[inline(always)]
67    #[must_use]
68    pub const fn overflowing_shr_vartime(&self, shift: u32) -> Option<Self> {
69        if shift < Self::BITS {
70            Some(self.unbounded_shr_vartime(shift))
71        } else {
72            None
73        }
74    }
75
76    /// Computes `self >> shift` in a panic-free manner.
77    ///
78    /// If the shift exceeds the precision, returns
79    /// - `0` when `self` is non-negative, and
80    /// - `-1` when `self` is negative.
81    #[inline(always)]
82    #[must_use]
83    pub const fn unbounded_shr(&self, shift: u32) -> Self {
84        let default = Self::select(&Self::ZERO, &Self::MINUS_ONE, self.is_negative());
85        ctutils::unwrap_or!(self.overflowing_shr(shift), default, Self::select)
86    }
87
88    /// Computes `self >> shift` in variable-time in a panic-free manner.
89    ///
90    /// If the shift exceeds the precision, returns
91    /// - `0` when `self` is non-negative, and
92    /// - `-1` when `self` is negative.
93    ///
94    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
95    ///
96    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
97    #[inline(always)]
98    #[must_use]
99    pub const fn unbounded_shr_vartime(&self, shift: u32) -> Self {
100        let sign_bits = Self::select(&Self::ZERO, &Self::MINUS_ONE, self.is_negative());
101        if let Some(res) = self.0.overflowing_shr_vartime(shift) {
102            Self::from_bits(res.bitor(&sign_bits.0.unbounded_shl(Self::BITS - shift)))
103        } else {
104            sign_bits
105        }
106    }
107
108    /// Computes `self >> shift` in a panic-free manner.
109    ///
110    /// If the shift exceeds the precision, returns
111    /// - `0` when `self` is non-negative, and
112    /// - `-1` when `self` is negative.
113    #[must_use]
114    pub const fn wrapping_shr(&self, shift: u32) -> Self {
115        self.shr(u32_rem(shift, Self::BITS))
116    }
117
118    /// Computes `self >> shift` in variable-time in a panic-free manner.
119    ///
120    /// If the shift exceeds the precision, returns
121    /// - `0` when `self` is non-negative, and
122    /// - `-1` when `self` is negative.
123    ///
124    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
125    ///
126    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
127    #[must_use]
128    #[allow(clippy::integer_division_remainder_used, reason = "needs triage")]
129    pub const fn wrapping_shr_vartime(&self, shift: u32) -> Self {
130        self.unbounded_shr_vartime(shift % Self::BITS)
131    }
132}
133
134macro_rules! impl_shr {
135    ($($shift:ty),+) => {
136        $(
137            impl<const LIMBS: usize> Shr<$shift> for Int<LIMBS> {
138                type Output = Int<LIMBS>;
139
140                #[inline]
141                fn shr(self, shift: $shift) -> Int<LIMBS> {
142                    <&Self>::shr(&self, shift)
143                }
144            }
145
146            impl<const LIMBS: usize> Shr<$shift> for &Int<LIMBS> {
147                type Output = Int<LIMBS>;
148
149                #[inline]
150                fn shr(self, shift: $shift) -> Int<LIMBS> {
151                    Int::<LIMBS>::shr(self, u32::try_from(shift).expect("invalid shift"))
152                }
153            }
154
155            impl<const LIMBS: usize> ShrAssign<$shift> for Int<LIMBS> {
156                fn shr_assign(&mut self, shift: $shift) {
157                    *self = self.shr(shift)
158                }
159            }
160        )+
161    };
162}
163
164impl_shr!(i32, u32, usize);
165
166impl<const LIMBS: usize> WrappingShr for Int<LIMBS> {
167    fn wrapping_shr(&self, shift: u32) -> Int<LIMBS> {
168        self.wrapping_shr(shift)
169    }
170}
171
172impl<const LIMBS: usize> ShrVartime for Int<LIMBS> {
173    fn overflowing_shr_vartime(&self, shift: u32) -> Option<Self> {
174        self.overflowing_shr_vartime(shift)
175    }
176
177    fn unbounded_shr_vartime(&self, shift: u32) -> Self {
178        self.unbounded_shr_vartime(shift)
179    }
180
181    fn wrapping_shr_vartime(&self, shift: u32) -> Self {
182        self.wrapping_shr_vartime(shift)
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use core::ops::Div;
189
190    use crate::{I256, ShrVartime};
191
192    const N: I256 =
193        I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
194
195    const N_2: I256 =
196        I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0");
197
198    #[test]
199    fn shr0() {
200        assert_eq!(I256::MAX >> 0, I256::MAX);
201        assert_eq!(I256::MIN >> 0, I256::MIN);
202    }
203
204    #[test]
205    fn shr1() {
206        assert_eq!(N >> 1, N_2);
207        assert_eq!(ShrVartime::overflowing_shr_vartime(&N, 1), Some(N_2));
208        assert_eq!(ShrVartime::wrapping_shr_vartime(&N, 1), N_2);
209    }
210
211    #[test]
212    fn shr5() {
213        assert_eq!(
214            I256::MAX >> 5,
215            I256::MAX.div(I256::from(32).to_nz().unwrap()).unwrap()
216        );
217        assert_eq!(
218            I256::MIN >> 5,
219            I256::MIN.div(I256::from(32).to_nz().unwrap()).unwrap()
220        );
221    }
222
223    #[test]
224    fn shr7_vartime() {
225        assert_eq!(
226            I256::MAX.shr_vartime(7),
227            I256::MAX.div(I256::from(128).to_nz().unwrap()).unwrap()
228        );
229        assert_eq!(
230            I256::MIN.shr_vartime(7),
231            I256::MIN.div(I256::from(128).to_nz().unwrap()).unwrap()
232        );
233    }
234
235    #[test]
236    fn shr256_const() {
237        assert!(N.overflowing_shr(256).is_none().to_bool_vartime());
238        assert!(ShrVartime::overflowing_shr_vartime(&N, 256).is_none());
239    }
240
241    #[test]
242    #[should_panic(expected = "`shift` exceeds upper bound")]
243    fn shr_bounds_panic() {
244        let _ = N >> 256;
245    }
246
247    #[test]
248    fn unbounded_shr_vartime_zero_shift() {
249        assert_eq!(I256::MAX.unbounded_shr_vartime(0), I256::MAX);
250        assert_eq!(I256::MIN.unbounded_shr_vartime(0), I256::MIN);
251        assert_eq!(I256::ONE.unbounded_shr_vartime(0), I256::ONE);
252        assert_eq!(I256::MINUS_ONE.unbounded_shr_vartime(0), I256::MINUS_ONE);
253        assert_eq!(I256::ZERO.unbounded_shr_vartime(0), I256::ZERO);
254    }
255
256    #[test]
257    fn overflowing_shr_vartime_zero_shift() {
258        let values = [I256::MAX, I256::MIN, I256::ONE, I256::MINUS_ONE, I256::ZERO];
259        for &val in &values {
260            assert_eq!(val.overflowing_shr_vartime(0), Some(val));
261        }
262    }
263
264    #[test]
265    fn shr_vartime_zero_shift() {
266        let values = [I256::MAX, I256::MIN, I256::ONE, I256::MINUS_ONE, I256::ZERO];
267        for &val in &values {
268            assert_eq!(val.shr_vartime(0), val);
269        }
270    }
271
272    #[test]
273    fn wrapping_shr_vartime_multiple_of_bits_is_identity() {
274        let values = [I256::MAX, I256::MIN, I256::ONE, I256::MINUS_ONE, I256::ZERO];
275        for &val in &values {
276            // Shift by 0 and multiples of the bit size should be identity.
277            for i in 0..4 {
278                assert_eq!(val.wrapping_shr_vartime(i * I256::BITS), val);
279            }
280        }
281    }
282
283    #[test]
284    fn unbounded_shr() {
285        assert_eq!(I256::MAX.unbounded_shr(257), I256::ZERO);
286        assert_eq!(I256::MIN.unbounded_shr(257), I256::MINUS_ONE);
287        assert_eq!(
288            ShrVartime::unbounded_shr_vartime(&I256::MAX, 257),
289            I256::ZERO
290        );
291        assert_eq!(
292            ShrVartime::unbounded_shr_vartime(&I256::MIN, 257),
293            I256::MINUS_ONE
294        );
295    }
296
297    #[test]
298    fn wrapping_shr() {
299        assert_eq!(I256::MAX.wrapping_shr(257), I256::MAX.shr(1));
300        assert_eq!(I256::MIN.wrapping_shr(257), I256::MIN.shr(1));
301        assert_eq!(
302            ShrVartime::wrapping_shr_vartime(&I256::MAX, 257),
303            I256::MAX.shr(1)
304        );
305        assert_eq!(
306            ShrVartime::wrapping_shr_vartime(&I256::MIN, 257),
307            I256::MIN.shr(1)
308        );
309    }
310}
crypto_bigint/int/shr.rs

crypto_bigint/int/
shr.rs
