crypto_bigint/uint/
bits.rs

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

crypto_bigint/uint/
bits.rs
