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 encoding;
12mod from;
13mod mul;
14mod neg;
15mod shl;
16mod shr;
17mod sub;
18
19#[cfg(feature = "rand_core")]
20mod rand;
21
22use crate::{Bounded, ConstCtOption, ConstZero, Constants, NonZero};
23use core::fmt;
24use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
25
26#[cfg(feature = "serde")]
27use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
28
29#[cfg(not(any(target_pointer_width = "32", target_pointer_width = "64")))]
30compile_error!("this crate builds on 32-bit and 64-bit platforms only");
31
32//
33// 32-bit definitions
34//
35
36/// Inner integer type that the [`Limb`] newtype wraps.
37#[cfg(target_pointer_width = "32")]
38pub type Word = u32;
39
40/// Unsigned wide integer type: double the width of [`Word`].
41#[cfg(target_pointer_width = "32")]
42pub type WideWord = u64;
43
44//
45// 64-bit definitions
46//
47
48/// Unsigned integer type that the [`Limb`] newtype wraps.
49#[cfg(target_pointer_width = "64")]
50pub type Word = u64;
51
52/// Wide integer type: double the width of [`Word`].
53#[cfg(target_pointer_width = "64")]
54pub type WideWord = u128;
55
56/// Big integers are represented as an array/vector of smaller CPU word-size integers called
57/// "limbs".
58///
59/// The [`Limb`] type uses a 32-bit or 64-bit saturated representation, depending on the target.
60/// All bits of an inner [`Word`] are used to represent larger big integer types.
61// Our PartialEq impl only differs from the default one by being constant-time, so this is safe
62#[allow(clippy::derived_hash_with_manual_eq)]
63#[derive(Copy, Clone, Default, Hash)]
64#[repr(transparent)]
65pub struct Limb(pub Word);
66
67impl Limb {
68    /// The value `0`.
69    pub const ZERO: Self = Limb(0);
70
71    /// The value `1`.
72    pub const ONE: Self = Limb(1);
73
74    /// Maximum value this [`Limb`] can express.
75    pub const MAX: Self = Limb(Word::MAX);
76
77    /// Highest bit in a [`Limb`].
78    pub(crate) const HI_BIT: u32 = Limb::BITS - 1;
79
80    // 32-bit
81
82    /// Size of the inner integer in bits.
83    #[cfg(target_pointer_width = "32")]
84    pub const BITS: u32 = 32;
85    /// Size of the inner integer in bytes.
86    #[cfg(target_pointer_width = "32")]
87    pub const BYTES: usize = 4;
88
89    // 64-bit
90
91    /// Size of the inner integer in bits.
92    #[cfg(target_pointer_width = "64")]
93    pub const BITS: u32 = 64;
94    /// Size of the inner integer in bytes.
95    #[cfg(target_pointer_width = "64")]
96    pub const BYTES: usize = 8;
97
98    /// Convert to a [`NonZero<Limb>`].
99    ///
100    /// Returns some if the original value is non-zero, and false otherwise.
101    pub const fn to_nz(self) -> ConstCtOption<NonZero<Self>> {
102        ConstCtOption::new(NonZero(self), self.is_nonzero())
103    }
104}
105
106impl Bounded for Limb {
107    const BITS: u32 = Self::BITS;
108    const BYTES: usize = Self::BYTES;
109}
110
111impl Constants for Limb {
112    const ONE: Self = Self::ONE;
113    const MAX: Self = Self::MAX;
114}
115
116impl ConditionallySelectable for Limb {
117    #[inline]
118    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
119        Self(Word::conditional_select(&a.0, &b.0, choice))
120    }
121}
122
123impl ConstZero for Limb {
124    const ZERO: Self = Self::ZERO;
125}
126
127impl num_traits::Zero for Limb {
128    fn zero() -> Self {
129        Self::ZERO
130    }
131
132    fn is_zero(&self) -> bool {
133        self.ct_eq(&Self::ZERO).into()
134    }
135}
136
137impl num_traits::One for Limb {
138    fn one() -> Self {
139        Self::ONE
140    }
141
142    fn is_one(&self) -> bool {
143        self.ct_eq(&Self::ONE).into()
144    }
145}
146
147impl fmt::Debug for Limb {
148    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
149        write!(f, "Limb(0x{self:X})")
150    }
151}
152
153impl fmt::Display for Limb {
154    #[inline]
155    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
156        fmt::UpperHex::fmt(self, f)
157    }
158}
159
160impl fmt::Binary for Limb {
161    #[inline]
162    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
163        write!(f, "{:0width$b}", &self.0, width = Self::BITS as usize)
164    }
165}
166
167impl fmt::LowerHex for Limb {
168    #[inline]
169    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
170        write!(f, "{:0width$x}", &self.0, width = Self::BYTES * 2)
171    }
172}
173
174impl fmt::UpperHex for Limb {
175    #[inline]
176    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
177        write!(f, "{:0width$X}", &self.0, width = Self::BYTES * 2)
178    }
179}
180
181#[cfg(feature = "serde")]
182impl<'de> Deserialize<'de> for Limb {
183    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
184    where
185        D: Deserializer<'de>,
186    {
187        Ok(Self(Word::deserialize(deserializer)?))
188    }
189}
190
191#[cfg(feature = "serde")]
192impl Serialize for Limb {
193    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
194    where
195        S: Serializer,
196    {
197        self.0.serialize(serializer)
198    }
199}
200
201#[cfg(feature = "zeroize")]
202impl zeroize::DefaultIsZeroes for Limb {}
203
204#[cfg(test)]
205mod tests {
206    #[cfg(feature = "alloc")]
207    use {super::Limb, alloc::format};
208
209    #[cfg(feature = "alloc")]
210    #[test]
211    fn debug() {
212        #[cfg(target_pointer_width = "32")]
213        assert_eq!(format!("{:?}", Limb(42)), "Limb(0x0000002A)");
214
215        #[cfg(target_pointer_width = "64")]
216        assert_eq!(format!("{:?}", Limb(42)), "Limb(0x000000000000002A)");
217    }
218}
crypto_bigint/limb.rs

crypto_bigint/
limb.rs
