crypto_bigint/uint/
shl.rs

1//! [`Uint`] bitwise left shift operations.
2
3use crate::{CtOption, Limb, Shl, ShlAssign, ShlVartime, Uint, WrappingShl, 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 shl(&self, shift: u32) -> Self {
14        let mut res = *self;
15        res.as_mut_uint_ref().bounded_shl_assign(shift, Self::BITS);
16        res
17    }
18
19    /// Computes `self << shift` in variable time.
20    ///
21    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
22    ///
23    /// When used with a fixed `shift`, this function is constant-time with respect
24    /// to `self`.
25    ///
26    /// # Panics
27    /// - if `shift >= Self::BITS`.
28    #[inline(always)]
29    #[must_use]
30    #[track_caller]
31    pub const fn shl_vartime(&self, shift: u32) -> Self {
32        self.overflowing_shl_vartime(shift)
33            .expect("`shift` exceeds upper bound")
34    }
35
36    /// Computes `self << shift`.
37    ///
38    /// Returns `None` if `shift >= Self::BITS`.
39    #[inline(never)]
40    #[must_use]
41    pub const fn overflowing_shl(&self, shift: u32) -> CtOption<Self> {
42        let mut res = *self;
43        let overflow = res.as_mut_uint_ref().overflowing_shl_assign(shift);
44        CtOption::new(res, overflow.not())
45    }
46
47    /// Computes `self << shift`.
48    ///
49    /// Returns `None` if `shift >= Self::BITS`.
50    ///
51    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
52    ///
53    /// When used with a fixed `shift`, this function is constant-time with respect
54    /// to `self`.
55    #[inline(always)]
56    #[must_use]
57    pub const fn overflowing_shl_vartime(&self, shift: u32) -> Option<Self> {
58        if shift < Self::BITS {
59            Some(self.unbounded_shl_vartime(shift))
60        } else {
61            None
62        }
63    }
64
65    /// Computes a left shift on a wide input as `(lo, hi)`.
66    ///
67    /// Returns `None` if `shift >= Self::BITS`.
68    ///
69    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
70    ///
71    /// When used with a fixed `shift`, this function is constant-time with respect
72    /// to `self`.
73    #[inline(always)]
74    #[must_use]
75    pub const fn overflowing_shl_vartime_wide(
76        lower_upper: (Self, Self),
77        shift: u32,
78    ) -> Option<(Self, Self)> {
79        let (lower, upper) = lower_upper;
80        if shift >= 2 * Self::BITS {
81            None
82        } else if shift >= Self::BITS {
83            let upper = lower.unbounded_shl_vartime(shift - Self::BITS);
84            Some((Self::ZERO, upper))
85        } else {
86            let new_lower = lower.unbounded_shl_vartime(shift);
87            let upper_lo = lower.unbounded_shr_vartime(Self::BITS - shift);
88            let upper_hi = upper.unbounded_shl_vartime(shift);
89            Some((new_lower, upper_lo.bitor(&upper_hi)))
90        }
91    }
92
93    /// Computes `self << shift` in a panic-free manner, returning zero if the shift exceeds the
94    /// precision.
95    #[inline(never)]
96    #[must_use]
97    pub const fn unbounded_shl(&self, shift: u32) -> Self {
98        let mut res = *self;
99        res.as_mut_uint_ref().unbounded_shl_assign(shift);
100        res
101    }
102
103    /// Computes `self << shift` in variable time in a panic-free manner, returning zero if the
104    /// shift exceeds the precision.
105    ///
106    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
107    ///
108    /// When used with a fixed `shift`, this function is constant-time with respect
109    /// to `self`.
110    #[inline(always)]
111    #[must_use]
112    pub const fn unbounded_shl_vartime(&self, shift: u32) -> Self {
113        let mut res = Self::ZERO;
114        self.as_uint_ref()
115            .unbounded_shl_vartime(shift, res.as_mut_uint_ref());
116        res
117    }
118
119    /// Computes `self << (shift * Limb::BITS)` in a panic-free manner, returning zero if the
120    /// shift exceeds the precision.
121    ///
122    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
123    ///
124    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
125    #[inline(always)]
126    #[must_use]
127    pub(crate) const fn unbounded_shl_by_limbs_vartime(&self, shift: u32) -> Self {
128        let mut res = *self;
129        res.as_mut_uint_ref()
130            .unbounded_shl_assign_by_limbs_vartime(shift);
131        res
132    }
133
134    /// Computes `self << shift` where `shift < shift_upper_bound`.
135    ///
136    /// The runtime is determined by `shift_upper_bound` which may be larger or smaller than
137    /// `Self::BITS`.
138    ///
139    /// # Panics
140    /// - if the shift exceeds the upper bound.
141    #[inline(never)]
142    #[must_use]
143    #[track_caller]
144    pub const fn bounded_shl(&self, shift: u32, shift_upper_bound: u32) -> Self {
145        let mut res = *self;
146        res.as_mut_uint_ref()
147            .bounded_shl_assign(shift, shift_upper_bound);
148        res
149    }
150
151    /// Computes `self << shift` in a panic-free manner, reducing shift modulo the type's width.
152    #[inline(always)]
153    #[must_use]
154    pub const fn wrapping_shl(&self, shift: u32) -> Self {
155        self.shl(u32_rem(shift, Self::BITS))
156    }
157
158    /// Computes `self << shift` in variable-time in a panic-free manner, reducing shift modulo
159    /// the type's width.
160    ///
161    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
162    ///
163    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
164    #[inline(always)]
165    #[must_use]
166    #[allow(clippy::integer_division_remainder_used, reason = "vartime")]
167    pub const fn wrapping_shl_vartime(&self, shift: u32) -> Self {
168        self.unbounded_shl_vartime(shift % Self::BITS)
169    }
170
171    /// Computes `self << 1` in constant-time.
172    #[inline(always)]
173    #[must_use]
174    pub(crate) const fn shl1(&self) -> Self {
175        let mut res = *self;
176        res.as_mut_uint_ref().shl1_assign();
177        res
178    }
179
180    /// Computes `self << 1` in constant-time, returning the shifted result
181    /// and a high carry limb.
182    #[inline(always)]
183    #[must_use]
184    pub(crate) const fn shl1_with_carry(&self, carry: Limb) -> (Self, Limb) {
185        let mut res = *self;
186        let carry = res.as_mut_uint_ref().shl1_assign_with_carry(carry);
187        (res, carry)
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 shl_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            .shl_assign_limb_with_carry(shift, carry);
203        (res, carry)
204    }
205}
206
207macro_rules! impl_shl {
208    ($($shift:ty),+) => {
209        $(
210            impl<const LIMBS: usize> Shl<$shift> for Uint<LIMBS> {
211                type Output = Uint<LIMBS>;
212
213                #[inline]
214                fn shl(self, shift: $shift) -> Uint<LIMBS> {
215                    <&Self>::shl(&self, shift)
216                }
217            }
218
219            impl<const LIMBS: usize> Shl<$shift> for &Uint<LIMBS> {
220                type Output = Uint<LIMBS>;
221
222                #[inline]
223                fn shl(self, shift: $shift) -> Uint<LIMBS> {
224                    Uint::<LIMBS>::shl(self, u32::try_from(shift).expect("invalid shift"))
225                }
226            }
227
228            impl<const LIMBS: usize> ShlAssign<$shift> for Uint<LIMBS> {
229                fn shl_assign(&mut self, shift: $shift) {
230                    *self = self.shl(shift)
231                }
232            }
233        )+
234    };
235}
236
237impl_shl!(i32, u32, usize);
238
239impl<const LIMBS: usize> WrappingShl for Uint<LIMBS> {
240    fn wrapping_shl(&self, shift: u32) -> Uint<LIMBS> {
241        self.wrapping_shl(shift)
242    }
243}
244
245impl<const LIMBS: usize> ShlVartime for Uint<LIMBS> {
246    fn overflowing_shl_vartime(&self, shift: u32) -> Option<Self> {
247        self.overflowing_shl_vartime(shift)
248    }
249
250    fn unbounded_shl_vartime(&self, shift: u32) -> Self {
251        self.unbounded_shl_vartime(shift)
252    }
253
254    fn wrapping_shl_vartime(&self, shift: u32) -> Self {
255        self.wrapping_shl_vartime(shift)
256    }
257}
258
259#[cfg(test)]
260mod tests {
261    use crate::{Limb, ShlVartime, U128, U192, U256, Uint, WrappingShl};
262
263    const N: U256 =
264        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
265
266    const TWO_N: U256 =
267        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD755DB9CD5E9140777FA4BD19A06C8282");
268
269    const FOUR_N: U256 =
270        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFAEABB739ABD2280EEFF497A3340D90504");
271
272    const SIXTY_FIVE: U256 =
273        U256::from_be_hex("FFFFFFFFFFFFFFFD755DB9CD5E9140777FA4BD19A06C82820000000000000000");
274
275    const EIGHTY_EIGHT: U256 =
276        U256::from_be_hex("FFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD03641410000000000000000000000");
277
278    const SIXTY_FOUR: U256 =
279        U256::from_be_hex("FFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD03641410000000000000000");
280
281    #[test]
282    fn shl_simple() {
283        let mut t = U256::from(1u8);
284        assert_eq!(t << 1, U256::from(2u8));
285        t = U256::from(3u8);
286        assert_eq!(t << 8, U256::from(0x300u16));
287    }
288
289    #[test]
290    fn shl1() {
291        assert_eq!(N << 1, TWO_N);
292        assert_eq!(N.shl1(), TWO_N);
293        assert_eq!(N.shl1_with_carry(Limb::ZERO), (TWO_N, Limb::ONE));
294        assert_eq!(N.bounded_shl(1, 2), TWO_N);
295        assert_eq!(ShlVartime::overflowing_shl_vartime(&N, 1), Some(TWO_N));
296        assert_eq!(ShlVartime::unbounded_shl_vartime(&N, 1), TWO_N);
297        assert_eq!(ShlVartime::wrapping_shl_vartime(&N, 1), TWO_N);
298    }
299
300    #[test]
301    fn shl2() {
302        assert_eq!(N << 2, FOUR_N);
303    }
304
305    #[test]
306    fn shl64() {
307        assert_eq!(N << 64, SIXTY_FOUR);
308    }
309
310    #[test]
311    fn shl65() {
312        assert_eq!(N << 65, SIXTY_FIVE);
313    }
314
315    #[test]
316    fn shl88() {
317        assert_eq!(N << 88, EIGHTY_EIGHT);
318    }
319
320    #[test]
321    fn shl_limb() {
322        let (lo, carry) = U128::ZERO.shl_limb_with_carry(16, Limb::ZERO);
323        assert_eq!((lo, carry), (U128::ZERO, Limb::ZERO));
324        let (lo, carry) = U128::ONE.shl_limb_with_carry(16, Limb::ZERO);
325        assert_eq!((lo, carry), (U128::from_u128(0x10000), Limb::ZERO));
326        let (lo, carry) = U128::MAX.shl_limb_with_carry(16, Limb::ZERO);
327        assert_eq!(
328            (lo, carry),
329            (
330                U128::from_u128(0xffffffffffffffffffffffffffff0000),
331                Limb::from_u32(0xffff)
332            )
333        );
334        let (lo, carry) = U128::MAX.shl_limb_with_carry(16, Limb::MAX);
335        assert_eq!(
336            (lo, carry),
337            (
338                U128::from_u128(0xffffffffffffffffffffffffffffffff),
339                Limb::from_u32(0xffff)
340            )
341        );
342    }
343
344    #[test]
345    fn shl_bounds() {
346        assert!(N.overflowing_shl(256).is_none().to_bool_vartime());
347        assert!(N.overflowing_shl_vartime(256).is_none());
348        assert_eq!(N.unbounded_shl(256), Uint::ZERO);
349        assert_eq!(N.unbounded_shl_vartime(256), Uint::ZERO);
350        assert_eq!(N.wrapping_shl(256), N);
351        assert_eq!(N.wrapping_shl_vartime(256), N);
352    }
353
354    #[test]
355    #[should_panic(expected = "`shift` exceeds upper bound")]
356    fn shl_bounds_panic() {
357        let _ = N << 256;
358    }
359
360    #[test]
361    fn shl_wide_1_1_128() {
362        assert_eq!(
363            Uint::overflowing_shl_vartime_wide((U128::ONE, U128::ONE), 128).unwrap(),
364            (U128::ZERO, U128::ONE)
365        );
366        assert_eq!(
367            Uint::overflowing_shl_vartime_wide((U128::ONE, U128::ONE), 128).unwrap(),
368            (U128::ZERO, U128::ONE)
369        );
370    }
371
372    #[test]
373    fn shl_wide_max_0_1() {
374        assert_eq!(
375            Uint::overflowing_shl_vartime_wide((U128::MAX, U128::ZERO), 1).unwrap(),
376            (U128::MAX.borrowing_sub(&U128::ONE, Limb::ZERO).0, U128::ONE)
377        );
378    }
379
380    #[test]
381    fn shl_wide_max_max_256() {
382        assert!(Uint::overflowing_shl_vartime_wide((U128::MAX, U128::MAX), 256).is_none());
383    }
384
385    #[test]
386    fn shl_by_limbs() {
387        let val = Uint::<2>::from_words([1, 99]);
388        assert_eq!(val.unbounded_shl_by_limbs_vartime(0).as_words(), &[1, 99]);
389        assert_eq!(val.unbounded_shl_by_limbs_vartime(1).as_words(), &[0, 1]);
390        assert_eq!(val.unbounded_shl_by_limbs_vartime(2).as_words(), &[0, 0]);
391    }
392
393    #[test]
394    fn overflowing_shl() {
395        assert_eq!(
396            U192::ONE.overflowing_shl(2).into_option(),
397            Some(U192::from_u8(4))
398        );
399        assert_eq!(U192::MAX.overflowing_shl(U192::BITS).into_option(), None);
400        assert_eq!(
401            ShlVartime::overflowing_shl_vartime(&U192::ONE, 2),
402            Some(U192::from_u8(4))
403        );
404        assert_eq!(
405            ShlVartime::overflowing_shl_vartime(&U192::MAX, U192::BITS),
406            None
407        );
408    }
409
410    #[test]
411    fn unbounded_shl() {
412        assert_eq!(U192::ONE.unbounded_shl(2), U192::from_u8(4));
413        assert_eq!(U192::MAX.unbounded_shl(U192::BITS), U192::ZERO);
414        assert_eq!(
415            ShlVartime::unbounded_shl_vartime(&U192::ONE, 2),
416            U192::from_u8(4)
417        );
418        assert_eq!(
419            ShlVartime::unbounded_shl_vartime(&U192::MAX, U192::BITS),
420            U192::ZERO
421        );
422    }
423
424    #[test]
425    fn wrapping_shl() {
426        assert_eq!(WrappingShl::wrapping_shl(&U192::ONE, 2), U192::from_u8(4));
427        assert_eq!(WrappingShl::wrapping_shl(&U192::ONE, U192::BITS), U192::ONE);
428        assert_eq!(
429            ShlVartime::wrapping_shl_vartime(&U192::ONE, 2),
430            U192::from_u8(4)
431        );
432        assert_eq!(
433            ShlVartime::wrapping_shl_vartime(&U192::ONE, U192::BITS),
434            U192::ONE
435        );
436    }
437}
crypto_bigint/uint/shl.rs

crypto_bigint/uint/
shl.rs
