crypto_bigint/uint/ref_type/
shl.rs

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

crypto_bigint/uint/ref_type/
shl.rs
