crypto_bigint/limb/
bits.rs

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

crypto_bigint/limb/
bits.rs
