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

crypto_bigint/
limb.rs
