crypto_bigint/uint/
shl.rs

1//! [`Uint`] bitwise left shift operations.
2
3use crate::{CtChoice, Limb, Uint, Word};
4use core::ops::{Shl, ShlAssign};
5
6impl<const LIMBS: usize> Uint<LIMBS> {
7    /// Computes `self << shift` where `0 <= shift < Limb::BITS`,
8    /// returning the result and the carry.
9    #[inline(always)]
10    pub(crate) const fn shl_limb(&self, n: usize) -> (Self, Limb) {
11        let mut limbs = [Limb::ZERO; LIMBS];
12
13        let nz = Limb(n as Word).ct_is_nonzero();
14        let lshift = n as Word;
15        let rshift = Limb::ct_select(Limb::ZERO, Limb((Limb::BITS - n) as Word), nz).0;
16        let carry = Limb::ct_select(
17            Limb::ZERO,
18            Limb(self.limbs[LIMBS - 1].0.wrapping_shr(Word::BITS - n as u32)),
19            nz,
20        );
21
22        let mut i = LIMBS - 1;
23        while i > 0 {
24            let mut limb = self.limbs[i].0 << lshift;
25            let hi = self.limbs[i - 1].0 >> rshift;
26            limb |= nz.if_true(hi);
27            limbs[i] = Limb(limb);
28            i -= 1
29        }
30        limbs[0] = Limb(self.limbs[0].0 << lshift);
31
32        (Uint::<LIMBS>::new(limbs), carry)
33    }
34
35    /// Computes `self << shift`.
36    ///
37    /// NOTE: this operation is variable time with respect to `n` *ONLY*.
38    ///
39    /// When used with a fixed `n`, this function is constant-time with respect
40    /// to `self`.
41    #[inline(always)]
42    pub const fn shl_vartime(&self, n: usize) -> Self {
43        let mut limbs = [Limb::ZERO; LIMBS];
44
45        if n >= Limb::BITS * LIMBS {
46            return Self { limbs };
47        }
48
49        let shift_num = n / Limb::BITS;
50        let rem = n % Limb::BITS;
51
52        let mut i = LIMBS;
53        while i > shift_num {
54            i -= 1;
55            limbs[i] = self.limbs[i - shift_num];
56        }
57
58        let (new_lower, _carry) = (Self { limbs }).shl_limb(rem);
59        new_lower
60    }
61
62    /// Computes a left shift on a wide input as `(lo, hi)`.
63    ///
64    /// NOTE: this operation is variable time with respect to `n` *ONLY*.
65    ///
66    /// When used with a fixed `n`, this function is constant-time with respect
67    /// to `self`.
68    #[inline(always)]
69    pub const fn shl_vartime_wide(lower_upper: (Self, Self), n: usize) -> (Self, Self) {
70        let (lower, mut upper) = lower_upper;
71        let new_lower = lower.shl_vartime(n);
72        upper = upper.shl_vartime(n);
73        if n >= Self::BITS {
74            upper = upper.bitor(&lower.shl_vartime(n - Self::BITS));
75        } else {
76            upper = upper.bitor(&lower.shr_vartime(Self::BITS - n));
77        }
78
79        (new_lower, upper)
80    }
81
82    /// Computes `self << n`.
83    /// Returns zero if `n >= Self::BITS`.
84    pub const fn shl(&self, shift: usize) -> Self {
85        let overflow = CtChoice::from_usize_lt(shift, Self::BITS).not();
86        let shift = shift % Self::BITS;
87        let mut result = *self;
88        let mut i = 0;
89        while i < Self::LOG2_BITS {
90            let bit = CtChoice::from_lsb((shift as Word >> i) & 1);
91            result = Uint::ct_select(&result, &result.shl_vartime(1 << i), bit);
92            i += 1;
93        }
94
95        Uint::ct_select(&result, &Self::ZERO, overflow)
96    }
97}
98
99impl<const LIMBS: usize> Shl<usize> for Uint<LIMBS> {
100    type Output = Uint<LIMBS>;
101
102    /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
103    ///
104    /// When used with a fixed `rhs`, this function is constant-time with respect
105    /// to `self`.
106    fn shl(self, rhs: usize) -> Uint<LIMBS> {
107        Uint::<LIMBS>::shl(&self, rhs)
108    }
109}
110
111impl<const LIMBS: usize> Shl<usize> for &Uint<LIMBS> {
112    type Output = Uint<LIMBS>;
113
114    /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
115    ///
116    /// When used with a fixed `rhs`, this function is constant-time with respect
117    /// to `self`.
118    fn shl(self, rhs: usize) -> Uint<LIMBS> {
119        self.shl(rhs)
120    }
121}
122
123impl<const LIMBS: usize> ShlAssign<usize> for Uint<LIMBS> {
124    /// NOTE: this operation is variable time with respect to `rhs` *ONLY*.
125    ///
126    /// When used with a fixed `rhs`, this function is constant-time with respect
127    /// to `self`.
128    fn shl_assign(&mut self, rhs: usize) {
129        *self = self.shl(rhs)
130    }
131}
132
133#[cfg(test)]
134mod tests {
135    use crate::{Limb, Uint, U128, U256};
136
137    const N: U256 =
138        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141");
139
140    const TWO_N: U256 =
141        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD755DB9CD5E9140777FA4BD19A06C8282");
142
143    const FOUR_N: U256 =
144        U256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFAEABB739ABD2280EEFF497A3340D90504");
145
146    const SIXTY_FIVE: U256 =
147        U256::from_be_hex("FFFFFFFFFFFFFFFD755DB9CD5E9140777FA4BD19A06C82820000000000000000");
148
149    const EIGHTY_EIGHT: U256 =
150        U256::from_be_hex("FFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD03641410000000000000000000000");
151
152    const SIXTY_FOUR: U256 =
153        U256::from_be_hex("FFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD03641410000000000000000");
154
155    #[test]
156    fn shl_simple() {
157        let mut t = U256::from(1u8);
158        assert_eq!(t << 1, U256::from(2u8));
159        t = U256::from(3u8);
160        assert_eq!(t << 8, U256::from(0x300u16));
161    }
162
163    #[test]
164    fn shl1() {
165        assert_eq!(N << 1, TWO_N);
166    }
167
168    #[test]
169    fn shl2() {
170        assert_eq!(N << 2, FOUR_N);
171    }
172
173    #[test]
174    fn shl65() {
175        assert_eq!(N << 65, SIXTY_FIVE);
176    }
177
178    #[test]
179    fn shl88() {
180        assert_eq!(N << 88, EIGHTY_EIGHT);
181    }
182
183    #[test]
184    fn shl256() {
185        assert_eq!(N << 256, U256::default());
186    }
187
188    #[test]
189    fn shl64() {
190        assert_eq!(N << 64, SIXTY_FOUR);
191    }
192
193    #[test]
194    fn shl_wide_1_1_128() {
195        assert_eq!(
196            Uint::shl_vartime_wide((U128::ONE, U128::ONE), 128),
197            (U128::ZERO, U128::ONE)
198        );
199    }
200
201    #[test]
202    fn shl_wide_max_0_1() {
203        assert_eq!(
204            Uint::shl_vartime_wide((U128::MAX, U128::ZERO), 1),
205            (U128::MAX.sbb(&U128::ONE, Limb::ZERO).0, U128::ONE)
206        );
207    }
208
209    #[test]
210    fn shl_wide_max_max_256() {
211        assert_eq!(
212            Uint::shl_vartime_wide((U128::MAX, U128::MAX), 256),
213            (U128::ZERO, U128::ZERO)
214        );
215    }
216}
crypto_bigint/uint/shl.rs

crypto_bigint/uint/
shl.rs
