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

crypto_bigint/
limb.rs
