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, 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 Unsigned for Limb {
264    #[inline]
265    fn as_uint_ref(&self) -> &UintRef {
266        self.as_ref()
267    }
268
269    #[inline]
270    fn as_mut_uint_ref(&mut self) -> &mut UintRef {
271        self.as_mut()
272    }
273
274    #[inline]
275    fn from_limb_like(limb: Limb, _other: &Self) -> Self {
276        limb
277    }
278}
279
280impl fmt::Debug for Limb {
281    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
282        write!(f, "Limb(0x{self:X})")
283    }
284}
285
286impl fmt::Display for Limb {
287    #[inline]
288    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
289        fmt::UpperHex::fmt(self, f)
290    }
291}
292
293impl fmt::Binary for Limb {
294    #[inline]
295    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
296        if f.alternate() {
297            write!(f, "0b")?;
298        }
299
300        write!(f, "{:0width$b}", &self.0, width = Self::BITS as usize)
301    }
302}
303
304impl fmt::Octal for Limb {
305    #[inline]
306    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307        if f.alternate() {
308            write!(f, "0o")?;
309        }
310        write!(
311            f,
312            "{:0width$o}",
313            &self.0,
314            width = Self::BITS.div_ceil(3) as usize
315        )
316    }
317}
318
319impl fmt::LowerHex for Limb {
320    #[inline]
321    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
322        if f.alternate() {
323            write!(f, "0x")?;
324        }
325        write!(f, "{:0width$x}", &self.0, width = Self::BYTES * 2)
326    }
327}
328
329impl fmt::UpperHex for Limb {
330    #[inline]
331    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
332        if f.alternate() {
333            write!(f, "0x")?;
334        }
335        write!(f, "{:0width$X}", &self.0, width = Self::BYTES * 2)
336    }
337}
338
339#[cfg(feature = "serde")]
340impl<'de> Deserialize<'de> for Limb {
341    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
342    where
343        D: Deserializer<'de>,
344    {
345        Ok(Self(Word::deserialize(deserializer)?))
346    }
347}
348
349#[cfg(feature = "serde")]
350impl Serialize for Limb {
351    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
352    where
353        S: Serializer,
354    {
355        self.0.serialize(serializer)
356    }
357}
358
359#[cfg(feature = "zeroize")]
360impl zeroize::DefaultIsZeroes for Limb {}
361
362#[cfg(test)]
363mod tests {
364    use super::Limb;
365    #[cfg(feature = "alloc")]
366    use alloc::format;
367
368    cpubits::cpubits! {
369        32 => {
370            #[test]
371            fn nlimbs_for_bits_macro() {
372                assert_eq!(super::nlimbs(64), 2);
373                assert_eq!(super::nlimbs(65), 3);
374                assert_eq!(super::nlimbs(128), 4);
375                assert_eq!(super::nlimbs(129), 5);
376                assert_eq!(super::nlimbs(192), 6);
377                assert_eq!(super::nlimbs(193), 7);
378                assert_eq!(super::nlimbs(256), 8);
379                assert_eq!(super::nlimbs(257), 9);
380            }
381        }
382        64 => {
383            #[test]
384            fn nlimbs_for_bits_macro() {
385                assert_eq!(super::nlimbs(64), 1);
386                assert_eq!(super::nlimbs(65), 2);
387                assert_eq!(super::nlimbs(128), 2);
388                assert_eq!(super::nlimbs(129), 3);
389                assert_eq!(super::nlimbs(192), 3);
390                assert_eq!(super::nlimbs(193), 4);
391                assert_eq!(super::nlimbs(256), 4);
392            }
393        }
394    }
395
396    #[cfg(feature = "alloc")]
397    #[test]
398    fn debug() {
399        cpubits::cpubits! {
400            32 => { assert_eq!(format!("{:?}", Limb(42)), "Limb(0x0000002A)"); }
401            64 => { assert_eq!(format!("{:?}", Limb(42)), "Limb(0x000000000000002A)"); }
402        }
403    }
404
405    #[cfg(feature = "alloc")]
406    #[test]
407    fn binary() {
408        cpubits::cpubits! {
409            32 => {
410                assert_eq!(
411                    format!("{:b}", Limb(42)),
412                    "00000000000000000000000000101010"
413                );
414                assert_eq!(
415                    format!("{:#b}", Limb(42)),
416                    "0b00000000000000000000000000101010"
417                );
418            }
419            64 => {
420                assert_eq!(
421                    format!("{:b}", Limb(42)),
422                    "0000000000000000000000000000000000000000000000000000000000101010"
423                );
424                assert_eq!(
425                    format!("{:#b}", Limb(42)),
426                    "0b0000000000000000000000000000000000000000000000000000000000101010"
427                );
428            }
429        }
430    }
431
432    #[cfg(feature = "alloc")]
433    #[test]
434    fn octal() {
435        cpubits::cpubits! {
436            32 => {
437                assert_eq!(format!("{:o}", Limb(42)), "00000000052");
438                assert_eq!(format!("{:#o}", Limb(42)), "0o00000000052");
439            }
440            64 => {
441                assert_eq!(format!("{:o}", Limb(42)), "0000000000000000000052");
442                assert_eq!(format!("{:#o}", Limb(42)), "0o0000000000000000000052");
443            }
444        }
445    }
446
447    #[cfg(feature = "alloc")]
448    #[test]
449    fn lower_hex() {
450        cpubits::cpubits! {
451            32 => {
452                assert_eq!(format!("{:x}", Limb(42)), "0000002a");
453                assert_eq!(format!("{:#x}", Limb(42)), "0x0000002a");
454            }
455            64 => {
456                assert_eq!(format!("{:x}", Limb(42)), "000000000000002a");
457                assert_eq!(format!("{:#x}", Limb(42)), "0x000000000000002a");
458            }
459        }
460    }
461
462    #[cfg(feature = "alloc")]
463    #[test]
464    fn upper_hex() {
465        cpubits::cpubits! {
466            32 => {
467                assert_eq!(format!("{:X}", Limb(42)), "0000002A");
468                assert_eq!(format!("{:#X}", Limb(42)), "0x0000002A");
469            }
470            64 => {
471                assert_eq!(format!("{:X}", Limb(42)), "000000000000002A");
472                assert_eq!(format!("{:#X}", Limb(42)), "0x000000000000002A");
473            }
474        }
475    }
476
477    #[test]
478    fn test_unsigned() {
479        crate::traits::tests::test_unsigned(Limb::ZERO, Limb::MAX);
480    }
481}
crypto_bigint/limb.rs

crypto_bigint/
limb.rs
