crypto_bigint/uint/
bits.rs

1use crate::{CtChoice, Limb, Uint, Word};
2
3impl<const LIMBS: usize> Uint<LIMBS> {
4    /// Returns `true` if the bit at position `index` is set, `false` otherwise.
5    ///
6    /// # Remarks
7    /// This operation is variable time with respect to `index` only.
8    #[inline(always)]
9    pub const fn bit_vartime(&self, index: usize) -> bool {
10        if index >= Self::BITS {
11            false
12        } else {
13            (self.limbs[index / Limb::BITS].0 >> (index % Limb::BITS)) & 1 == 1
14        }
15    }
16
17    /// Calculate the number of bits needed to represent this number.
18    pub const fn bits_vartime(&self) -> usize {
19        let mut i = LIMBS - 1;
20        while i > 0 && self.limbs[i].0 == 0 {
21            i -= 1;
22        }
23
24        let limb = self.limbs[i];
25        Limb::BITS * (i + 1) - limb.leading_zeros()
26    }
27
28    /// Calculate the number of leading zeros in the binary representation of this number.
29    pub const fn leading_zeros(&self) -> usize {
30        let limbs = self.as_limbs();
31
32        let mut count: Word = 0;
33        let mut i = LIMBS;
34        let mut nonzero_limb_not_encountered = CtChoice::TRUE;
35        while i > 0 {
36            i -= 1;
37            let l = limbs[i];
38            let z = l.leading_zeros() as Word;
39            count += nonzero_limb_not_encountered.if_true(z);
40            nonzero_limb_not_encountered =
41                nonzero_limb_not_encountered.and(l.ct_is_nonzero().not());
42        }
43
44        count as usize
45    }
46
47    /// Calculate the number of leading zeros in the binary representation of this number,
48    /// variable time in `self`.
49    pub const fn leading_zeros_vartime(&self) -> usize {
50        let limbs = self.as_limbs();
51
52        let mut count = 0;
53        let mut i = LIMBS;
54        while i > 0 {
55            i -= 1;
56            let l = limbs[i];
57            let z = l.leading_zeros();
58            count += z;
59            if z != Limb::BITS {
60                break;
61            }
62        }
63
64        count
65    }
66
67    /// Calculate the number of trailing zeros in the binary representation of this number.
68    pub const fn trailing_zeros(&self) -> usize {
69        let limbs = self.as_limbs();
70
71        let mut count: Word = 0;
72        let mut i = 0;
73        let mut nonzero_limb_not_encountered = CtChoice::TRUE;
74        while i < LIMBS {
75            let l = limbs[i];
76            let z = l.trailing_zeros() as Word;
77            count += nonzero_limb_not_encountered.if_true(z);
78            nonzero_limb_not_encountered =
79                nonzero_limb_not_encountered.and(l.ct_is_nonzero().not());
80            i += 1;
81        }
82
83        count as usize
84    }
85
86    /// Calculate the number of trailing zeros in the binary representation of this number,
87    /// variable time in `self`.
88    pub const fn trailing_zeros_vartime(&self) -> usize {
89        let limbs = self.as_limbs();
90
91        let mut count = 0;
92        let mut i = 0;
93        while i < LIMBS {
94            let l = limbs[i];
95            let z = l.trailing_zeros();
96            count += z;
97            if z != Limb::BITS {
98                break;
99            }
100            i += 1;
101        }
102
103        count
104    }
105
106    /// Calculate the number of trailing ones in the binary representation of this number.
107    pub const fn trailing_ones(&self) -> usize {
108        let limbs = self.as_limbs();
109
110        let mut count: Word = 0;
111        let mut i = 0;
112        let mut nonmax_limb_not_encountered = CtChoice::TRUE;
113        while i < LIMBS {
114            let l = limbs[i];
115            let z = l.trailing_ones() as Word;
116            count += nonmax_limb_not_encountered.if_true(z);
117            nonmax_limb_not_encountered =
118                nonmax_limb_not_encountered.and(Limb::ct_eq(l, Limb::MAX));
119            i += 1;
120        }
121
122        count as usize
123    }
124
125    /// Calculate the number of trailing ones in the binary representation of this number,
126    /// variable time in `self`.
127    pub const fn trailing_ones_vartime(&self) -> usize {
128        let limbs = self.as_limbs();
129
130        let mut count = 0;
131        let mut i = 0;
132        while i < LIMBS {
133            let l = limbs[i];
134            let z = l.trailing_ones();
135            count += z;
136            if z != Limb::BITS {
137                break;
138            }
139            i += 1;
140        }
141
142        count
143    }
144
145    /// Calculate the number of bits needed to represent this number.
146    pub const fn bits(&self) -> usize {
147        Self::BITS - self.leading_zeros()
148    }
149
150    /// Get the value of the bit at position `index`, as a truthy or falsy `CtChoice`.
151    /// Returns the falsy value for indices out of range.
152    pub const fn bit(&self, index: usize) -> CtChoice {
153        let limb_num = index / Limb::BITS;
154        let index_in_limb = index % Limb::BITS;
155        let index_mask = 1 << index_in_limb;
156
157        let limbs = self.as_words();
158
159        let mut result: Word = 0;
160        let mut i = 0;
161        while i < LIMBS {
162            let bit = limbs[i] & index_mask;
163            let is_right_limb = CtChoice::from_usize_equality(i, limb_num);
164            result |= is_right_limb.if_true(bit);
165            i += 1;
166        }
167
168        CtChoice::from_lsb(result >> index_in_limb)
169    }
170
171    /// Sets the bit at `index` to 0 or 1 depending on the value of `bit_value`.
172    pub(crate) const fn set_bit(self, index: usize, bit_value: CtChoice) -> Self {
173        let mut result = self;
174        let limb_num = index / Limb::BITS;
175        let index_in_limb = index % Limb::BITS;
176        let index_mask = 1 << index_in_limb;
177
178        let mut i = 0;
179        while i < LIMBS {
180            let is_right_limb = CtChoice::from_usize_equality(i, limb_num);
181            let old_limb = result.limbs[i].0;
182            let new_limb = bit_value.select(old_limb & !index_mask, old_limb | index_mask);
183            result.limbs[i] = Limb(is_right_limb.select(old_limb, new_limb));
184            i += 1;
185        }
186        result
187    }
188}
189
190#[cfg(test)]
191mod tests {
192    use crate::{CtChoice, U256};
193
194    fn uint_with_bits_at(positions: &[usize]) -> U256 {
195        let mut result = U256::ZERO;
196        for pos in positions {
197            result |= U256::ONE << *pos;
198        }
199        result
200    }
201
202    #[test]
203    fn bit_vartime() {
204        let u = uint_with_bits_at(&[16, 48, 112, 127, 255]);
205        assert!(!u.bit_vartime(0));
206        assert!(!u.bit_vartime(1));
207        assert!(u.bit_vartime(16));
208        assert!(u.bit_vartime(127));
209        assert!(u.bit_vartime(255));
210        assert!(!u.bit_vartime(256));
211        assert!(!u.bit_vartime(260));
212    }
213
214    #[test]
215    fn bit() {
216        let u = uint_with_bits_at(&[16, 48, 112, 127, 255]);
217        assert!(!u.bit(0).is_true_vartime());
218        assert!(!u.bit(1).is_true_vartime());
219        assert!(u.bit(16).is_true_vartime());
220        assert!(u.bit(127).is_true_vartime());
221        assert!(u.bit(255).is_true_vartime());
222        assert!(!u.bit(256).is_true_vartime());
223        assert!(!u.bit(260).is_true_vartime());
224    }
225
226    #[test]
227    fn leading_zeros() {
228        let u = uint_with_bits_at(&[256 - 16, 256 - 79, 256 - 207]);
229        assert_eq!(u.leading_zeros(), 15);
230
231        let u = uint_with_bits_at(&[256 - 79, 256 - 207]);
232        assert_eq!(u.leading_zeros(), 78);
233
234        let u = uint_with_bits_at(&[256 - 207]);
235        assert_eq!(u.leading_zeros(), 206);
236
237        let u = uint_with_bits_at(&[256 - 1, 256 - 75, 256 - 150]);
238        assert_eq!(u.leading_zeros(), 0);
239
240        let u = U256::ZERO;
241        assert_eq!(u.leading_zeros(), 256);
242    }
243
244    #[test]
245    fn leading_zeros_vartime() {
246        let u = uint_with_bits_at(&[256 - 16, 256 - 79, 256 - 207]);
247        assert_eq!(u.leading_zeros_vartime(), 15);
248
249        let u = uint_with_bits_at(&[256 - 79, 256 - 207]);
250        assert_eq!(u.leading_zeros_vartime(), 78);
251
252        let u = uint_with_bits_at(&[256 - 207]);
253        assert_eq!(u.leading_zeros_vartime(), 206);
254
255        let u = uint_with_bits_at(&[256 - 1, 256 - 75, 256 - 150]);
256        assert_eq!(u.leading_zeros_vartime(), 0);
257
258        let u = U256::ZERO;
259        assert_eq!(u.leading_zeros_vartime(), 256);
260    }
261
262    #[test]
263    fn trailing_zeros() {
264        let u = uint_with_bits_at(&[16, 79, 150]);
265        assert_eq!(u.trailing_zeros(), 16);
266
267        let u = uint_with_bits_at(&[79, 150]);
268        assert_eq!(u.trailing_zeros(), 79);
269
270        let u = uint_with_bits_at(&[150, 207]);
271        assert_eq!(u.trailing_zeros(), 150);
272
273        let u = uint_with_bits_at(&[0, 150, 207]);
274        assert_eq!(u.trailing_zeros(), 0);
275
276        let u = U256::ZERO;
277        assert_eq!(u.trailing_zeros(), 256);
278    }
279
280    #[test]
281    fn trailing_zeros_vartime() {
282        let u = uint_with_bits_at(&[16, 79, 150]);
283        assert_eq!(u.trailing_zeros_vartime(), 16);
284
285        let u = uint_with_bits_at(&[79, 150]);
286        assert_eq!(u.trailing_zeros_vartime(), 79);
287
288        let u = uint_with_bits_at(&[150, 207]);
289        assert_eq!(u.trailing_zeros_vartime(), 150);
290
291        let u = uint_with_bits_at(&[0, 150, 207]);
292        assert_eq!(u.trailing_zeros_vartime(), 0);
293
294        let u = U256::ZERO;
295        assert_eq!(u.trailing_zeros_vartime(), 256);
296    }
297
298    #[test]
299    fn trailing_ones() {
300        let u = !uint_with_bits_at(&[16, 79, 150]);
301        assert_eq!(u.trailing_ones(), 16);
302
303        let u = !uint_with_bits_at(&[79, 150]);
304        assert_eq!(u.trailing_ones(), 79);
305
306        let u = !uint_with_bits_at(&[150, 207]);
307        assert_eq!(u.trailing_ones(), 150);
308
309        let u = !uint_with_bits_at(&[0, 150, 207]);
310        assert_eq!(u.trailing_ones(), 0);
311
312        let u = U256::MAX;
313        assert_eq!(u.trailing_ones(), 256);
314    }
315
316    #[test]
317    fn trailing_ones_vartime() {
318        let u = !uint_with_bits_at(&[16, 79, 150]);
319        assert_eq!(u.trailing_ones_vartime(), 16);
320
321        let u = !uint_with_bits_at(&[79, 150]);
322        assert_eq!(u.trailing_ones_vartime(), 79);
323
324        let u = !uint_with_bits_at(&[150, 207]);
325        assert_eq!(u.trailing_ones_vartime(), 150);
326
327        let u = !uint_with_bits_at(&[0, 150, 207]);
328        assert_eq!(u.trailing_ones_vartime(), 0);
329
330        let u = U256::MAX;
331        assert_eq!(u.trailing_ones_vartime(), 256);
332    }
333
334    #[test]
335    fn set_bit() {
336        let u = uint_with_bits_at(&[16, 79, 150]);
337        assert_eq!(
338            u.set_bit(127, CtChoice::TRUE),
339            uint_with_bits_at(&[16, 79, 127, 150])
340        );
341
342        let u = uint_with_bits_at(&[16, 79, 150]);
343        assert_eq!(
344            u.set_bit(150, CtChoice::TRUE),
345            uint_with_bits_at(&[16, 79, 150])
346        );
347
348        let u = uint_with_bits_at(&[16, 79, 150]);
349        assert_eq!(
350            u.set_bit(127, CtChoice::FALSE),
351            uint_with_bits_at(&[16, 79, 150])
352        );
353
354        let u = uint_with_bits_at(&[16, 79, 150]);
355        assert_eq!(
356            u.set_bit(150, CtChoice::FALSE),
357            uint_with_bits_at(&[16, 79])
358        );
359    }
360}
crypto_bigint/uint/bits.rs

crypto_bigint/uint/
bits.rs
