crypto_bigint/uint/
bits.rs

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

crypto_bigint/uint/
bits.rs
