crypto_bigint/uint/ref_type/
shr.rs

1//! [`UintRef`] bitwise right shift operations.
2
3use core::num::NonZeroU32;
4
5use super::UintRef;
6use crate::{
7    Choice, Limb,
8    primitives::{u32_bits, u32_rem},
9};
10
11impl UintRef {
12    /// Right-shifts by `shift` bits.
13    ///
14    /// # Panics
15    /// - if the shift exceeds the type's width.
16    #[inline(always)]
17    pub const fn shr_assign(&mut self, shift: u32) {
18        self.bounded_shr_assign(shift, self.bits_precision());
19    }
20
21    /// Right-shifts by `shift` bits in constant-time.
22    ///
23    /// Returns truthy `Choice` and leaves `self` unmodified if `shift >= self.bits_precision()`,
24    /// otherwise returns a falsy `Choice` and shifts `self` in place.
25    #[inline(always)]
26    pub const fn overflowing_shr_assign(&mut self, shift: u32) -> Choice {
27        let bits = self.bits_precision();
28        let overflow = Choice::from_u32_le(bits, shift);
29        let shift = overflow.select_u32(shift, 0);
30        self.bounded_shr_assign(shift, bits);
31        overflow
32    }
33
34    /// Right-shifts by `shift` bits, producing zero if the shift exceeds the precision.
35    #[inline(always)]
36    pub const fn unbounded_shr_assign(&mut self, shift: u32) {
37        let overflow = self.overflowing_shr_assign(shift);
38        self.conditional_set_zero(overflow);
39    }
40
41    /// Right-shifts by `shift` bits where `shift < shift_upper_bound`, producing zero if
42    /// the shift exceeds the precision.
43    ///
44    /// The runtime is determined by `shift_upper_bound` which may be smaller than
45    /// `self.bits_precision()`.
46    ///
47    /// # Panics
48    /// - if the shift exceeds the upper bound.
49    #[inline(always)]
50    pub const fn bounded_shr_assign(&mut self, shift: u32, shift_upper_bound: u32) {
51        assert!(shift < shift_upper_bound, "`shift` exceeds upper bound");
52
53        let bit_shift = if shift_upper_bound <= Limb::BITS {
54            shift
55        } else {
56            self.bounded_shr_by_limbs_assign(
57                shift >> Limb::LOG2_BITS,
58                shift_upper_bound.div_ceil(Limb::BITS),
59            );
60            shift & (Limb::BITS - 1)
61        };
62        self.shr_assign_limb_with_carry(bit_shift, Limb::ZERO);
63    }
64
65    /// Right-shifts by `shift * Limb::BITS` bits where `shift < shift_upper_bound`.
66    ///
67    /// The runtime is determined by `shift_upper_bound` which may be larger or smaller than
68    /// `self.bits_precision()`.
69    ///
70    /// # Panics
71    /// - if the shift exceeds the upper bound.
72    #[inline(always)]
73    pub(crate) const fn bounded_shr_by_limbs_assign(&mut self, shift: u32, shift_upper_bound: u32) {
74        assert!(shift < shift_upper_bound, "`shift` exceeds upper bound");
75
76        let shift_bits = u32_bits(shift_upper_bound - 1);
77        let mut i = 0;
78        while i < shift_bits {
79            let bit = Choice::from_u32_lsb(shift >> i);
80            self.conditional_shr_assign_by_limbs_vartime(1 << i, bit);
81            i += 1;
82        }
83    }
84
85    /// Conditionally right-shifts by `shift` limbs in a panic-free manner, producing zero
86    /// if the shift exceeds the precision.
87    ///
88    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
89    ///
90    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
91    #[inline(always)]
92    pub(crate) const fn conditional_shr_assign_by_limbs_vartime(&mut self, shift: u32, c: Choice) {
93        let shift = shift as usize;
94        let mut i = 0;
95        while i < self.nlimbs().saturating_sub(shift) {
96            self.limbs[i] = Limb::select(self.limbs[i], self.limbs[i + shift], c);
97            i += 1;
98        }
99        while i < self.nlimbs() {
100            self.limbs[i] = Limb::select(self.limbs[i], Limb::ZERO, c);
101            i += 1;
102        }
103    }
104
105    /// Right-shifts by `shift` limbs in a panic-free manner, producing zero if the shift
106    /// exceeds the precision.
107    #[inline(always)]
108    #[allow(clippy::cast_possible_truncation)]
109    pub(crate) const fn unbounded_shr_assign_by_limbs(&mut self, shift: u32) {
110        let nlimbs = self.nlimbs() as u32;
111        let overflow = Choice::from_u32_le(nlimbs, shift);
112        let shift = overflow.select_u32(shift, 0);
113        self.bounded_shr_by_limbs_assign(shift, nlimbs);
114        self.conditional_set_zero(overflow);
115    }
116
117    /// Right-shifts by `shift` limbs in a panic-free manner, producing zero if the shift
118    /// exceeds the precision.
119    ///
120    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
121    ///
122    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
123    #[inline(always)]
124    pub(crate) const fn unbounded_shr_assign_by_limbs_vartime(&mut self, shift: u32) {
125        let shift = shift as usize;
126        let mut i = 0;
127        while i < self.nlimbs().saturating_sub(shift) {
128            self.limbs[i] = self.limbs[i + shift];
129            i += 1;
130        }
131        while i < self.nlimbs() {
132            self.limbs[i] = Limb::ZERO;
133            i += 1;
134        }
135    }
136
137    /// Copies `self >> shift` into `out` in a panic-free manner, producing zero if the shift
138    /// exceeds the precision.
139    ///
140    /// `out` is assumed to be initialized with zeros.
141    ///
142    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
143    ///
144    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
145    #[inline(always)]
146    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
147    pub(crate) const fn unbounded_shr_vartime(&self, shift: u32, out: &mut Self) {
148        let count = self.nlimbs().saturating_sub((shift / Limb::BITS) as usize);
149        let target = out.leading_mut(count);
150        target.copy_from(self.trailing(self.nlimbs() - count));
151        target.shr_assign_limb_vartime(shift % Limb::BITS);
152    }
153
154    /// Right-shifts by `shift` bits in a panic-free manner, producing zero if the shift
155    /// exceeds the precision.
156    ///
157    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
158    ///
159    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
160    #[inline(always)]
161    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
162    pub const fn unbounded_shr_assign_vartime(&mut self, shift: u32) {
163        if shift >= self.bits_precision() {
164            self.conditional_set_zero(Choice::TRUE);
165            return;
166        }
167
168        let shift_limbs = shift / Limb::BITS;
169        let rem = shift % Limb::BITS;
170
171        self.unbounded_shr_assign_by_limbs_vartime(shift_limbs);
172        let top = self.nlimbs().saturating_sub(shift_limbs as usize);
173        self.leading_mut(top).shr_assign_limb_vartime(rem);
174    }
175
176    /// Right-shifts by `shift` bits in a panic-free manner, reducing shift modulo the type's width.
177    #[inline(always)]
178    pub const fn wrapping_shr_assign(&mut self, shift: u32) {
179        self.shr_assign(u32_rem(shift, self.bits_precision()));
180    }
181
182    /// Right-shifts by `shift` bits in a panic-free manner, reducing shift modulo the type's width.
183    ///
184    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
185    ///
186    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
187    #[inline(always)]
188    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
189    pub const fn wrapping_shr_assign_vartime(&mut self, shift: u32) {
190        self.unbounded_shr_assign_vartime(shift % self.bits_precision());
191    }
192
193    /// Right-shifts by a single bit in constant-time, returning `Limb::ONE << Limb::HI_BIT`
194    /// if the least significant bit was set, and [`Limb::ZERO`] otherwise.
195    #[inline(always)]
196    pub const fn shr1_assign(&mut self) -> Limb {
197        self.shr1_assign_with_carry(Limb::ZERO)
198    }
199
200    /// Right-shifts by a single bit in constant-time, returning `Limb::ONE << Limb::HI_BIT`
201    /// if the least significant bit was set, and [`Limb::ZERO`] otherwise.
202    #[inline(always)]
203    pub(crate) const fn shr1_assign_with_carry(&mut self, carry: Limb) -> Limb {
204        // NB: when used with a constant shift value, this method is constant time
205        self.shr_assign_limb_with_carry_vartime(1, carry)
206    }
207
208    /// Conditionally right-shifts by `shift` bits where `0 < shift < Limb::BITS`, returning
209    /// the carry.
210    ///
211    /// # Panics
212    /// - if `shift >= Limb::BITS`.
213    #[inline(always)]
214    pub(crate) const fn conditional_shr_assign_limb_nonzero(
215        &mut self,
216        shift: NonZeroU32,
217        mut carry: Limb,
218        choice: Choice,
219    ) -> Limb {
220        assert!(shift.get() < Limb::BITS);
221
222        let rshift = shift.get();
223        let lshift = Limb::BITS - rshift;
224
225        let mut i = self.nlimbs();
226        while i > 0 {
227            i -= 1;
228            (self.limbs[i], carry) = (
229                Limb::select(
230                    self.limbs[i],
231                    self.limbs[i].shr(rshift).bitor(carry),
232                    choice,
233                ),
234                self.limbs[i].shl(lshift),
235            );
236        }
237
238        Limb::select(Limb::ZERO, carry, choice)
239    }
240
241    /// Right-shifts by `shift` bits where `0 < shift < Limb::BITS`, returning the carry.
242    ///
243    /// # Panics
244    /// - if `shift >= Limb::BITS`.
245    #[inline(always)]
246    pub const fn shr_assign_limb(&mut self, shift: u32) -> Limb {
247        self.shr_assign_limb_with_carry(shift, Limb::ZERO)
248    }
249
250    /// Right-shifts by `shift` bits where `0 < shift < Limb::BITS`, returning the carry.
251    ///
252    /// # Panics
253    /// - if `shift >= Limb::BITS`.
254    #[inline(always)]
255    pub(crate) const fn shr_assign_limb_with_carry(&mut self, shift: u32, carry: Limb) -> Limb {
256        let nz = Choice::from_u32_nz(shift);
257        self.conditional_shr_assign_limb_nonzero(
258            NonZeroU32::new(nz.select_u32(1, shift)).expect("ensured non-zero"),
259            carry,
260            nz,
261        )
262    }
263
264    /// Right-shifts by `shift` bits where `0 < shift < Limb::BITS`, returning
265    /// the carry.
266    ///
267    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
268    ///
269    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
270    ///
271    /// # Panics
272    /// If the shift size is equal to or larger than the width of the integer.
273    #[inline(always)]
274    pub(crate) const fn shr_assign_limb_vartime(&mut self, shift: u32) -> Limb {
275        self.shr_assign_limb_with_carry_vartime(shift, Limb::ZERO)
276    }
277
278    /// Right-shifts by `shift` bits where `0 < shift < Limb::BITS`, returning
279    /// the carry.
280    ///
281    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
282    ///
283    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
284    ///
285    /// # Panics
286    /// If the shift size is equal to or larger than the width of the integer.
287    #[inline(always)]
288    pub(crate) const fn shr_assign_limb_with_carry_vartime(
289        &mut self,
290        shift: u32,
291        mut carry: Limb,
292    ) -> Limb {
293        assert!(shift < Limb::BITS);
294
295        if shift == 0 {
296            return Limb::ZERO;
297        }
298
299        let rshift = shift;
300        let lshift = Limb::BITS - shift;
301
302        let mut i = self.nlimbs();
303        while i > 0 {
304            i -= 1;
305            (self.limbs[i], carry) = (
306                self.limbs[i].shr(rshift).bitor(carry),
307                self.limbs[i].shl(lshift),
308            );
309        }
310
311        carry
312    }
313}
314
315#[cfg(test)]
316mod tests {
317    use crate::{Limb, U256, Uint};
318
319    const N: U256 =
320        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
321
322    const N_2: U256 =
323        U256::from_be_hex("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0");
324
325    #[test]
326    fn shr1_assign() {
327        let mut n = N;
328        let carry = n.as_mut_uint_ref().shr1_assign();
329        assert_eq!(n, N_2);
330        assert!(carry.is_nonzero().to_bool());
331
332        let mut m = U256::MAX;
333        let carry = m.as_mut_uint_ref().shr1_assign();
334        assert_eq!(m, U256::MAX.shr_vartime(1));
335        assert!(carry.is_nonzero().to_bool());
336
337        let mut z = U256::ZERO;
338        let carry = z.as_mut_uint_ref().shr1_assign();
339        assert_eq!(z, U256::ZERO);
340        assert!(carry.is_zero().to_bool());
341    }
342
343    #[test]
344    fn shr256() {
345        let mut n = N;
346        assert!(bool::from(n.as_mut_uint_ref().overflowing_shr_assign(256)));
347    }
348
349    #[test]
350    fn shr_assign_limb() {
351        // Shift by zero
352        let mut val = N;
353        let carry = val.as_mut_uint_ref().shr_assign_limb(0);
354        assert_eq!(val, N);
355        assert_eq!(carry, Limb::ZERO);
356
357        // Shift by one
358        let mut val = N;
359        let carry = val.as_mut_uint_ref().shr_assign_limb(1);
360        assert_eq!(val, N.shr_vartime(1));
361        assert_eq!(carry, N.limbs[0].shl(Limb::BITS - 1));
362
363        // Shift by any
364        let mut val = N;
365        let carry = val.as_mut_uint_ref().shr_assign_limb(13);
366        assert_eq!(val, N.shr_vartime(13));
367        assert_eq!(carry, N.limbs[0].shl(Limb::BITS - 13));
368
369        // Shift by max
370        let mut val = N;
371        let carry = val.as_mut_uint_ref().shr_assign_limb(Limb::BITS - 1);
372        assert_eq!(val, N.shr_vartime(Limb::BITS - 1));
373        assert_eq!(carry, N.limbs[0].shl(1));
374    }
375
376    #[test]
377    fn unbounded_shr_by_limbs_vartime() {
378        let refval = Uint::<2>::from_words([1, 99]);
379
380        let mut val = refval;
381        val.as_mut_uint_ref()
382            .unbounded_shr_assign_by_limbs_vartime(0);
383        assert_eq!(val.as_words(), &[1, 99]);
384
385        let mut val = refval;
386        val.as_mut_uint_ref()
387            .unbounded_shr_assign_by_limbs_vartime(1);
388        assert_eq!(val.as_words(), &[99, 0]);
389
390        let mut val = refval;
391        val.as_mut_uint_ref()
392            .unbounded_shr_assign_by_limbs_vartime(2);
393        assert_eq!(val.as_words(), &[0, 0]);
394    }
395
396    #[test]
397    fn compare_shr_assign() {
398        for i in 0..256 {
399            let (mut a, mut b) = (N, N);
400            a.as_mut_uint_ref().bounded_shr_assign(i, 256);
401            b.as_mut_uint_ref().unbounded_shr_assign_vartime(i);
402            assert_eq!(a, b);
403        }
404    }
405}
crypto_bigint/uint/ref_type/shr.rs

crypto_bigint/uint/ref_type/
shr.rs
