crypto_bigint/uint/boxed/
shl.rs

1//! [`BoxedUint`] bitwise left shift operations.
2
3use crate::{
4    BoxedUint, ConstChoice, ConstantTimeSelect, Limb, ShlVartime, Word, WrappingShl, Zero,
5};
6use core::ops::{Shl, ShlAssign};
7use subtle::{Choice, ConstantTimeLess, CtOption};
8
9impl BoxedUint {
10    /// Computes `self << shift`.
11    ///
12    /// Panics if `shift >= Self::BITS`.
13    pub fn shl(&self, shift: u32) -> BoxedUint {
14        let (result, overflow) = self.overflowing_shl(shift);
15        assert!(!bool::from(overflow), "attempt to shift left with overflow");
16        result
17    }
18
19    /// Computes `self <<= shift`.
20    ///
21    /// Panics if `shift >= Self::BITS`.
22    pub fn shl_assign(&mut self, shift: u32) {
23        let overflow = self.overflowing_shl_assign(shift);
24        assert!(!bool::from(overflow), "attempt to shift left with overflow");
25    }
26
27    /// Computes `self << shift`.
28    ///
29    /// Returns a zero and a truthy `Choice` if `shift >= self.bits_precision()`,
30    /// or the result and a falsy `Choice` otherwise.
31    pub fn overflowing_shl(&self, shift: u32) -> (Self, Choice) {
32        let mut result = self.clone();
33        let overflow = result.overflowing_shl_assign(shift);
34        (result, overflow)
35    }
36
37    /// Computes `self <<= shift`.
38    ///
39    /// Returns a truthy `Choice` if `shift >= self.bits_precision()` or a falsy `Choice` otherwise.
40    pub fn overflowing_shl_assign(&mut self, shift: u32) -> Choice {
41        // `floor(log2(bits_precision - 1))` is the number of bits in the representation of `shift`
42        // (which lies in range `0 <= shift < bits_precision`).
43        let shift_bits = u32::BITS - (self.bits_precision() - 1).leading_zeros();
44        let overflow = !shift.ct_lt(&self.bits_precision());
45        let shift = shift % self.bits_precision();
46        let mut temp = self.clone();
47
48        for i in 0..shift_bits {
49            let bit = Choice::from(((shift >> i) & 1) as u8);
50            temp.set_zero();
51            // Will not overflow by construction
52            self.shl_vartime_into(&mut temp, 1 << i)
53                .expect("shift within range");
54            self.ct_assign(&temp, bit);
55        }
56
57        #[cfg(feature = "zeroize")]
58        zeroize::Zeroize::zeroize(&mut temp);
59
60        self.conditional_set_zero(overflow);
61        overflow
62    }
63
64    /// Computes `self << shift` in a panic-free manner, masking off bits of `shift` which would cause the shift to
65    /// exceed the type's width.
66    pub fn wrapping_shl(&self, shift: u32) -> Self {
67        self.overflowing_shl(shift).0
68    }
69
70    /// Computes `self << shift` in variable-time in a panic-free manner, masking off bits of `shift` which would cause
71    /// the shift to exceed the type's width.
72    pub fn wrapping_shl_vartime(&self, shift: u32) -> Self {
73        let mut result = Self::zero_with_precision(self.bits_precision());
74        let _ = self.shl_vartime_into(&mut result, shift);
75        result
76    }
77
78    /// Computes `self << shift` and writes the result into `dest`.
79    /// Returns `None` if `shift >= self.bits_precision()`.
80    ///
81    /// WARNING: for performance reasons, `dest` is assumed to be pre-zeroized.
82    ///
83    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
84    ///
85    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
86    #[inline(always)]
87    fn shl_vartime_into(&self, dest: &mut Self, shift: u32) -> Option<()> {
88        if shift >= self.bits_precision() {
89            return None;
90        }
91
92        let nlimbs = self.nlimbs();
93        let shift_num = (shift / Limb::BITS) as usize;
94        let rem = shift % Limb::BITS;
95
96        for i in shift_num..nlimbs {
97            dest.limbs[i] = self.limbs[i - shift_num];
98        }
99
100        if rem == 0 {
101            return Some(());
102        }
103
104        let mut carry = Limb::ZERO;
105
106        for i in shift_num..nlimbs {
107            let shifted = dest.limbs[i].shl(rem);
108            let new_carry = dest.limbs[i].shr(Limb::BITS - rem);
109            dest.limbs[i] = shifted.bitor(carry);
110            carry = new_carry;
111        }
112
113        Some(())
114    }
115
116    /// Computes `self << shift`.
117    /// Returns `None` if `shift >= self.bits_precision()`.
118    ///
119    /// NOTE: this operation is variable time with respect to `shift` *ONLY*.
120    ///
121    /// When used with a fixed `shift`, this function is constant-time with respect to `self`.
122    #[inline(always)]
123    pub fn shl_vartime(&self, shift: u32) -> Option<Self> {
124        let mut result = Self::zero_with_precision(self.bits_precision());
125        let success = self.shl_vartime_into(&mut result, shift);
126        success.map(|_| result)
127    }
128
129    /// Computes `self << 1` in constant-time.
130    pub(crate) fn overflowing_shl1(&self) -> (Self, Limb) {
131        let mut ret = self.clone();
132        let carry = ret.shl1_assign();
133        (ret, carry)
134    }
135
136    /// Computes `self << 1` in-place in constant-time.
137    pub(crate) fn shl1_assign(&mut self) -> Limb {
138        let mut carry = self.limbs[0] >> Limb::HI_BIT;
139        self.limbs[0].shl_assign(1);
140        for i in 1..self.limbs.len() {
141            (self.limbs[i], carry) = ((self.limbs[i] << 1) | carry, self.limbs[i] >> Limb::HI_BIT);
142        }
143        carry
144    }
145
146    /// Computes `self << shift` where `0 <= shift < Limb::BITS`,
147    /// returning the result and the carry.
148    pub(crate) fn shl_limb(&self, shift: u32) -> (Self, Limb) {
149        let mut limbs = vec![Limb::ZERO; self.limbs.len()];
150
151        let nz = ConstChoice::from_u32_nonzero(shift);
152        let lshift = shift;
153        let rshift = nz.if_true_u32(Limb::BITS - shift);
154        let carry = nz.if_true_word(
155            self.limbs[self.limbs.len() - 1]
156                .0
157                .wrapping_shr(Word::BITS - shift),
158        );
159
160        limbs[0] = Limb(self.limbs[0].0 << lshift);
161        let mut i = 1;
162        while i < self.limbs.len() {
163            let mut limb = self.limbs[i].0 << lshift;
164            let hi = self.limbs[i - 1].0 >> rshift;
165            limb |= nz.if_true_word(hi);
166            limbs[i] = Limb(limb);
167            i += 1
168        }
169
170        (
171            BoxedUint {
172                limbs: limbs.into(),
173            },
174            Limb(carry),
175        )
176    }
177}
178
179macro_rules! impl_shl {
180    ($($shift:ty),+) => {
181        $(
182            impl Shl<$shift> for BoxedUint {
183                type Output = BoxedUint;
184
185                #[inline]
186                fn shl(self, shift: $shift) -> BoxedUint {
187                    <&Self>::shl(&self, shift)
188                }
189            }
190
191            impl Shl<$shift> for &BoxedUint {
192                type Output = BoxedUint;
193
194                #[inline]
195                fn shl(self, shift: $shift) -> BoxedUint {
196                    BoxedUint::shl(self, u32::try_from(shift).expect("invalid shift"))
197                }
198            }
199
200            impl ShlAssign<$shift> for BoxedUint {
201                fn shl_assign(&mut self, shift: $shift) {
202                    BoxedUint::shl_assign(self, u32::try_from(shift).expect("invalid shift"))
203                }
204            }
205        )+
206    };
207}
208
209impl_shl!(i32, u32, usize);
210
211impl WrappingShl for BoxedUint {
212    fn wrapping_shl(&self, shift: u32) -> BoxedUint {
213        self.wrapping_shl(shift)
214    }
215}
216
217impl ShlVartime for BoxedUint {
218    fn overflowing_shl_vartime(&self, shift: u32) -> CtOption<Self> {
219        let (result, overflow) = self.overflowing_shl(shift);
220        CtOption::new(result, !overflow)
221    }
222    fn wrapping_shl_vartime(&self, shift: u32) -> Self {
223        self.wrapping_shl(shift)
224    }
225}
226
227#[cfg(test)]
228mod tests {
229    use super::BoxedUint;
230
231    #[test]
232    fn shl() {
233        let one = BoxedUint::one_with_precision(128);
234
235        assert_eq!(BoxedUint::from(2u8), &one << 1);
236        assert_eq!(BoxedUint::from(4u8), &one << 2);
237        assert_eq!(
238            BoxedUint::from(0x80000000000000000u128),
239            one.shl_vartime(67).unwrap()
240        );
241    }
242
243    #[test]
244    fn shl1_assign() {
245        let mut n = BoxedUint::from(0x3c442b21f19185fe433f0a65af902b8fu128);
246        let n_shl1 = BoxedUint::from(0x78885643e3230bfc867e14cb5f20571eu128);
247        n.shl1_assign();
248        assert_eq!(n, n_shl1);
249    }
250
251    #[test]
252    fn shl_vartime() {
253        let one = BoxedUint::one_with_precision(128);
254
255        assert_eq!(BoxedUint::from(2u8), one.shl_vartime(1).unwrap());
256        assert_eq!(BoxedUint::from(4u8), one.shl_vartime(2).unwrap());
257        assert_eq!(
258            BoxedUint::from(0x80000000000000000u128),
259            one.shl_vartime(67).unwrap()
260        );
261    }
262}
crypto_bigint/uint/boxed/shl.rs

crypto_bigint/uint/boxed/
shl.rs
