crypto_bigint/
limb.rs

1//! Big integers are represented as an array of smaller CPU word-size integers
2//! called "limbs".
3
4mod add;
5mod bit_and;
6mod bit_not;
7mod bit_or;
8mod bit_xor;
9mod bits;
10mod cmp;
11mod ct;
12mod div;
13mod encoding;
14mod from;
15mod gcd;
16mod invert_mod;
17mod mul;
18mod neg;
19mod shl;
20mod shr;
21mod sqrt;
22mod sub;
23
24#[cfg(feature = "rand_core")]
25mod rand;
26
27use crate::{
28    Bounded, Choice, ConstOne, ConstZero, Constants, CtEq, CtOption, Integer, NonZero, One,
29    UintRef, Unsigned, WideWord, Word, Zero, bitlen, primitives::u32_bits, traits::sealed::Sealed,
30    word,
31};
32use core::{fmt, ptr, slice};
33
34#[cfg(feature = "serde")]
35use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
36
37/// Calculate the number of limbs required to represent the given number of bits.
38// TODO(tarcieri): replace with `generic_const_exprs` (rust-lang/rust#76560) when stable
39#[inline(always)]
40#[must_use]
41pub const fn nlimbs(bits: u32) -> usize {
42    bitlen::to_limbs(bits)
43}
44
45/// Big integers are represented as an array/vector of smaller CPU word-size integers called
46/// "limbs".
47///
48/// The [`Limb`] type uses a 32-bit or 64-bit saturated representation, depending on the target.
49/// All bits of an inner [`Word`] are used to represent larger big integer types.
50// Our PartialEq impl only differs from the default one by being constant-time, so this is safe
51#[allow(clippy::derived_hash_with_manual_eq)]
52#[derive(Copy, Clone, Default, Hash)]
53#[repr(transparent)]
54pub struct Limb(pub Word);
55
56impl Limb {
57    /// The value `0`.
58    pub const ZERO: Self = Limb(0);
59
60    /// The value `1`.
61    pub const ONE: Self = Limb(1);
62
63    /// Maximum value this [`Limb`] can express.
64    pub const MAX: Self = Limb(Word::MAX);
65
66    /// Highest bit in a [`Limb`].
67    pub(crate) const HI_BIT: u32 = Limb::BITS - 1;
68
69    cpubits::cpubits! {
70        32 => {
71            /// Size of the inner integer in bits.
72            pub const BITS: u32 = 32;
73            /// Size of the inner integer in bytes.
74            pub const BYTES: usize = 4;
75        }
76        64 => {
77            /// Size of the inner integer in bits.
78            pub const BITS: u32 = 64;
79            /// Size of the inner integer in bytes.
80            pub const BYTES: usize = 8;
81        }
82    }
83
84    /// `floor(log2(Self::BITS))`.
85    pub const LOG2_BITS: u32 = u32_bits(Self::BITS - 1);
86
87    /// Is this limb equal to [`Limb::ZERO`]?
88    #[must_use]
89    pub const fn is_zero(&self) -> Choice {
90        word::choice_from_nz(self.0).not()
91    }
92
93    /// Convert to a [`NonZero<Limb>`].
94    ///
95    /// Returns some if the original value is non-zero, and none otherwise.
96    #[must_use]
97    pub const fn to_nz(self) -> CtOption<NonZero<Self>> {
98        let (nz, self_nz) = self.to_nz_or_one();
99        CtOption::new(nz, self_nz)
100    }
101
102    /// Convert to a [`NonZero<Limb>`], defaulting to `Self::ONE`.
103    ///
104    /// Returns a pair consisting of a [`NonZero<Limb>`], and a [`Choice`]
105    /// indicating whether the original value was non-zero (and preserved).
106    #[inline(always)]
107    #[must_use]
108    pub(crate) const fn to_nz_or_one(self) -> (NonZero<Self>, Choice) {
109        let is_nz = self.is_nonzero();
110        (
111            NonZero::new_unchecked(Self::select(Self::ONE, self, is_nz)),
112            is_nz,
113        )
114    }
115
116    /// Convert the least significant bit of this [`Limb`] to a [`Choice`].
117    #[must_use]
118    pub const fn lsb_to_choice(self) -> Choice {
119        word::choice_from_lsb(self.0)
120    }
121
122    /// Convert a shared reference to an array of [`Limb`]s into a shared reference to their inner
123    /// [`Word`]s for each limb.
124    #[inline]
125    #[must_use]
126    pub const fn array_as_words<const N: usize>(array: &[Self; N]) -> &[Word; N] {
127        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
128        #[allow(unsafe_code)]
129        unsafe {
130            &*array.as_ptr().cast()
131        }
132    }
133
134    /// Convert a mutable reference to an array of [`Limb`]s into a mutable reference to their inner
135    /// [`Word`]s for each limb.
136    #[inline]
137    pub const fn array_as_mut_words<const N: usize>(array: &mut [Self; N]) -> &mut [Word; N] {
138        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
139        #[allow(unsafe_code)]
140        unsafe {
141            &mut *array.as_mut_ptr().cast()
142        }
143    }
144
145    /// Convert a shared reference to an array of [`Limb`]s into a shared reference to their inner
146    /// [`Word`]s for each limb.
147    #[inline]
148    #[must_use]
149    pub const fn slice_as_words(slice: &[Self]) -> &[Word] {
150        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
151        #[allow(unsafe_code)]
152        unsafe {
153            &*(ptr::from_ref(slice) as *const [Word])
154        }
155    }
156
157    /// Convert a mutable reference to an array of [`Limb`]s into a mutable reference to their inner
158    /// [`Word`]s for each limb.
159    #[inline]
160    pub const fn slice_as_mut_words(slice: &mut [Self]) -> &mut [Word] {
161        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
162        #[allow(unsafe_code)]
163        unsafe {
164            &mut *(ptr::from_mut(slice) as *mut [Word])
165        }
166    }
167}
168
169impl AsRef<[Limb]> for Limb {
170    #[inline(always)]
171    fn as_ref(&self) -> &[Limb] {
172        slice::from_ref(self)
173    }
174}
175
176impl AsMut<[Limb]> for Limb {
177    #[inline(always)]
178    fn as_mut(&mut self) -> &mut [Limb] {
179        slice::from_mut(self)
180    }
181}
182
183impl AsRef<UintRef> for Limb {
184    #[inline(always)]
185    fn as_ref(&self) -> &UintRef {
186        UintRef::new(slice::from_ref(self))
187    }
188}
189
190impl AsMut<UintRef> for Limb {
191    #[inline(always)]
192    fn as_mut(&mut self) -> &mut UintRef {
193        UintRef::new_mut(slice::from_mut(self))
194    }
195}
196
197impl Bounded for Limb {
198    const BITS: u32 = Self::BITS;
199    const BYTES: usize = Self::BYTES;
200}
201
202impl Constants for Limb {
203    const MAX: Self = Self::MAX;
204}
205
206impl ConstZero for Limb {
207    const ZERO: Self = Self::ZERO;
208}
209
210impl ConstOne for Limb {
211    const ONE: Self = Self::ONE;
212}
213
214impl Zero for Limb {
215    #[inline(always)]
216    fn zero() -> Self {
217        Self::ZERO
218    }
219}
220
221impl One for Limb {
222    #[inline(always)]
223    fn one() -> Self {
224        Self::ONE
225    }
226}
227
228impl num_traits::Zero for Limb {
229    fn zero() -> Self {
230        Self::ZERO
231    }
232
233    fn is_zero(&self) -> bool {
234        self.ct_eq(&Self::ZERO).into()
235    }
236}
237
238impl num_traits::One for Limb {
239    fn one() -> Self {
240        Self::ONE
241    }
242
243    fn is_one(&self) -> bool {
244        self.ct_eq(&Self::ONE).into()
245    }
246}
247
248impl Integer for Limb {
249    #[inline]
250    fn as_limbs(&self) -> &[Limb] {
251        self.as_ref()
252    }
253
254    #[inline]
255    fn as_mut_limbs(&mut self) -> &mut [Limb] {
256        self.as_mut()
257    }
258
259    #[inline]
260    fn nlimbs(&self) -> usize {
261        1
262    }
263
264    fn is_even(&self) -> Choice {
265        (*self).is_odd().not()
266    }
267
268    fn is_odd(&self) -> Choice {
269        (*self).is_odd()
270    }
271}
272
273impl Sealed for Limb {}
274
275impl Unsigned for Limb {
276    #[inline]
277    fn as_uint_ref(&self) -> &UintRef {
278        self.as_ref()
279    }
280
281    #[inline]
282    fn as_mut_uint_ref(&mut self) -> &mut UintRef {
283        self.as_mut()
284    }
285
286    #[inline]
287    fn from_limb_like(limb: Limb, _other: &Self) -> Self {
288        limb
289    }
290}
291
292impl fmt::Debug for Limb {
293    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
294        write!(f, "Limb(0x{self:X})")
295    }
296}
297
298impl fmt::Display for Limb {
299    #[inline]
300    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
301        fmt::UpperHex::fmt(self, f)
302    }
303}
304
305impl fmt::Binary for Limb {
306    #[inline]
307    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
308        if f.alternate() {
309            write!(f, "0b")?;
310        }
311
312        write!(f, "{:0width$b}", &self.0, width = Self::BITS as usize)
313    }
314}
315
316impl fmt::Octal for Limb {
317    #[inline]
318    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
319        if f.alternate() {
320            write!(f, "0o")?;
321        }
322        write!(
323            f,
324            "{:0width$o}",
325            &self.0,
326            width = Self::BITS.div_ceil(3) as usize
327        )
328    }
329}
330
331impl fmt::LowerHex for Limb {
332    #[inline]
333    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334        if f.alternate() {
335            write!(f, "0x")?;
336        }
337        write!(f, "{:0width$x}", &self.0, width = Self::BYTES * 2)
338    }
339}
340
341impl fmt::UpperHex for Limb {
342    #[inline]
343    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
344        if f.alternate() {
345            write!(f, "0x")?;
346        }
347        write!(f, "{:0width$X}", &self.0, width = Self::BYTES * 2)
348    }
349}
350
351#[cfg(feature = "serde")]
352impl<'de> Deserialize<'de> for Limb {
353    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
354    where
355        D: Deserializer<'de>,
356    {
357        Ok(Self(Word::deserialize(deserializer)?))
358    }
359}
360
361#[cfg(feature = "serde")]
362impl Serialize for Limb {
363    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
364    where
365        S: Serializer,
366    {
367        self.0.serialize(serializer)
368    }
369}
370
371#[cfg(feature = "zeroize")]
372impl zeroize::DefaultIsZeroes for Limb {}
373
374#[cfg(test)]
375mod tests {
376    use super::Limb;
377    #[cfg(feature = "alloc")]
378    use alloc::format;
379
380    cpubits::cpubits! {
381        32 => {
382            #[test]
383            fn nlimbs_for_bits_macro() {
384                assert_eq!(super::nlimbs(64), 2);
385                assert_eq!(super::nlimbs(65), 3);
386                assert_eq!(super::nlimbs(128), 4);
387                assert_eq!(super::nlimbs(129), 5);
388                assert_eq!(super::nlimbs(192), 6);
389                assert_eq!(super::nlimbs(193), 7);
390                assert_eq!(super::nlimbs(256), 8);
391                assert_eq!(super::nlimbs(257), 9);
392            }
393        }
394        64 => {
395            #[test]
396            fn nlimbs_for_bits_macro() {
397                assert_eq!(super::nlimbs(64), 1);
398                assert_eq!(super::nlimbs(65), 2);
399                assert_eq!(super::nlimbs(128), 2);
400                assert_eq!(super::nlimbs(129), 3);
401                assert_eq!(super::nlimbs(192), 3);
402                assert_eq!(super::nlimbs(193), 4);
403                assert_eq!(super::nlimbs(256), 4);
404            }
405        }
406    }
407
408    #[test]
409    fn nlimbs_handles_max_bit_count() {
410        let expected = usize::try_from(u64::from(u32::MAX).div_ceil(u64::from(Limb::BITS)))
411            .expect("limb count fits in usize");
412        assert_eq!(super::nlimbs(u32::MAX), expected);
413    }
414
415    #[cfg(feature = "alloc")]
416    #[test]
417    fn debug() {
418        cpubits::cpubits! {
419            32 => { assert_eq!(format!("{:?}", Limb(42)), "Limb(0x0000002A)"); }
420            64 => { assert_eq!(format!("{:?}", Limb(42)), "Limb(0x000000000000002A)"); }
421        }
422    }
423
424    #[cfg(feature = "alloc")]
425    #[test]
426    fn binary() {
427        cpubits::cpubits! {
428            32 => {
429                assert_eq!(
430                    format!("{:b}", Limb(42)),
431                    "00000000000000000000000000101010"
432                );
433                assert_eq!(
434                    format!("{:#b}", Limb(42)),
435                    "0b00000000000000000000000000101010"
436                );
437            }
438            64 => {
439                assert_eq!(
440                    format!("{:b}", Limb(42)),
441                    "0000000000000000000000000000000000000000000000000000000000101010"
442                );
443                assert_eq!(
444                    format!("{:#b}", Limb(42)),
445                    "0b0000000000000000000000000000000000000000000000000000000000101010"
446                );
447            }
448        }
449    }
450
451    #[cfg(feature = "alloc")]
452    #[test]
453    fn octal() {
454        cpubits::cpubits! {
455            32 => {
456                assert_eq!(format!("{:o}", Limb(42)), "00000000052");
457                assert_eq!(format!("{:#o}", Limb(42)), "0o00000000052");
458            }
459            64 => {
460                assert_eq!(format!("{:o}", Limb(42)), "0000000000000000000052");
461                assert_eq!(format!("{:#o}", Limb(42)), "0o0000000000000000000052");
462            }
463        }
464    }
465
466    #[cfg(feature = "alloc")]
467    #[test]
468    fn lower_hex() {
469        cpubits::cpubits! {
470            32 => {
471                assert_eq!(format!("{:x}", Limb(42)), "0000002a");
472                assert_eq!(format!("{:#x}", Limb(42)), "0x0000002a");
473            }
474            64 => {
475                assert_eq!(format!("{:x}", Limb(42)), "000000000000002a");
476                assert_eq!(format!("{:#x}", Limb(42)), "0x000000000000002a");
477            }
478        }
479    }
480
481    #[cfg(feature = "alloc")]
482    #[test]
483    fn upper_hex() {
484        cpubits::cpubits! {
485            32 => {
486                assert_eq!(format!("{:X}", Limb(42)), "0000002A");
487                assert_eq!(format!("{:#X}", Limb(42)), "0x0000002A");
488            }
489            64 => {
490                assert_eq!(format!("{:X}", Limb(42)), "000000000000002A");
491                assert_eq!(format!("{:#X}", Limb(42)), "0x000000000000002A");
492            }
493        }
494    }
495
496    #[test]
497    fn test_unsigned() {
498        crate::traits::tests::test_unsigned(Limb::ZERO, Limb::MAX);
499    }
500}
crypto_bigint/limb.rs

crypto_bigint/
limb.rs
