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

crypto_bigint/
limb.rs
