crypto_bigint/boxed/
uint.rs

1//! Heap-allocated big unsigned integers.
2
3mod add;
4mod cmp;
5
6use crate::{Limb, Word};
7use alloc::{vec, vec::Vec};
8use core::fmt;
9
10#[cfg(feature = "zeroize")]
11use zeroize::Zeroize;
12
13/// Fixed-precision heap-allocated big unsigned integer.
14///
15/// Alternative to the stack-allocated [`Uint`][`crate::Uint`] but with a
16/// fixed precision chosen at runtime instead of compile time.
17///
18/// Unlike many other heap-allocated big integer libraries, this type is not
19/// arbitrary precision and will wrap at its fixed-precision rather than
20/// automatically growing.
21#[derive(Clone, Default)]
22pub struct BoxedUint {
23    /// Inner limb vector. Stored from least significant to most significant.
24    limbs: Vec<Limb>,
25}
26
27impl BoxedUint {
28    /// Get the value `0`, represented as succinctly as possible.
29    pub fn zero() -> Self {
30        Self::default()
31    }
32
33    /// Get the value `1`, represented as succinctly as possible.
34    pub fn one() -> Self {
35        Self {
36            limbs: vec![Limb::ONE; 1],
37        }
38    }
39
40    /// Create a new [`BoxedUint`] with the given number of bits of precision.
41    ///
42    /// Returns `None` if the number of bits is not a multiple of the
43    /// [`Limb`] size.
44    pub fn new(bits_precision: usize) -> Option<Self> {
45        if bits_precision == 0 || bits_precision % Limb::BITS != 0 {
46            return None;
47        }
48
49        let nlimbs = bits_precision / Limb::BITS;
50
51        Some(Self {
52            limbs: vec![Limb::ZERO; nlimbs],
53        })
54    }
55
56    /// Get the maximum value for a given number of bits of precision.
57    ///
58    /// Returns `None` if the number of bits is not a multiple of the
59    /// [`Limb`] size.
60    pub fn max(bits_precision: usize) -> Option<Self> {
61        let mut ret = Self::new(bits_precision)?;
62
63        for limb in &mut ret.limbs {
64            *limb = Limb::MAX;
65        }
66
67        Some(ret)
68    }
69
70    /// Create a [`BoxedUint`] from an array of [`Word`]s (i.e. word-sized unsigned
71    /// integers).
72    #[inline]
73    pub fn from_words(words: &[Word]) -> Self {
74        Self {
75            limbs: words.iter().copied().map(Into::into).collect(),
76        }
77    }
78
79    /// Create an array of [`Word`]s (i.e. word-sized unsigned integers) from
80    /// a [`BoxedUint`].
81    #[inline]
82    pub fn to_words(&self) -> Vec<Word> {
83        self.limbs.iter().copied().map(Into::into).collect()
84    }
85
86    /// Borrow the inner limbs as a slice of [`Word`]s.
87    pub fn as_words(&self) -> &[Word] {
88        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
89        #[allow(trivial_casts, unsafe_code)]
90        unsafe {
91            &*((self.limbs.as_slice() as *const _) as *const [Word])
92        }
93    }
94
95    /// Borrow the inner limbs as a mutable array of [`Word`]s.
96    pub fn as_words_mut(&mut self) -> &mut [Word] {
97        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
98        #[allow(trivial_casts, unsafe_code)]
99        unsafe {
100            &mut *((self.limbs.as_mut_slice() as *mut _) as *mut [Word])
101        }
102    }
103
104    /// Borrow the limbs of this [`BoxedUint`].
105    pub fn as_limbs(&self) -> &[Limb] {
106        self.limbs.as_ref()
107    }
108
109    /// Borrow the limbs of this [`BoxedUint`] mutably.
110    pub fn as_limbs_mut(&mut self) -> &mut [Limb] {
111        self.limbs.as_mut()
112    }
113
114    /// Convert this [`BoxedUint`] into its inner limbs.
115    pub fn to_limbs(&self) -> Vec<Limb> {
116        self.limbs.clone()
117    }
118
119    /// Convert this [`BoxedUint`] into its inner limbs.
120    pub fn into_limbs(self) -> Vec<Limb> {
121        self.limbs
122    }
123
124    /// Get the precision of this [`BoxedUint`] in bits.
125    pub fn bits(&self) -> usize {
126        self.limbs.len() * Limb::BITS
127    }
128
129    /// Sort two [`BoxedUint`]s by precision, returning a tuple of the shorter
130    /// followed by the longer, or the original order if their precision is
131    /// equal.
132    fn sort_by_precision<'a>(a: &'a Self, b: &'a Self) -> (&'a Self, &'a Self) {
133        if a.limbs.len() <= b.limbs.len() {
134            (a, b)
135        } else {
136            (b, a)
137        }
138    }
139
140    /// Perform a carry chain-like operation over the limbs of the inputs,
141    /// constructing a result from the returned limbs and carry.
142    ///
143    /// If one of the two values has fewer limbs than the other, passes
144    /// [`Limb::ZERO`] as the value for that limb.
145    fn chain<F>(a: &Self, b: &Self, mut carry: Limb, f: F) -> (Self, Limb)
146    where
147        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
148    {
149        let (shorter, longer) = Self::sort_by_precision(a, b);
150        let mut limbs = Vec::with_capacity(longer.limbs.len());
151
152        for i in 0..longer.limbs.len() {
153            let &a = shorter.limbs.get(i).unwrap_or(&Limb::ZERO);
154            let &b = longer.limbs.get(i).unwrap_or(&Limb::ZERO);
155            let (limb, c) = f(a, b, carry);
156            limbs.push(limb);
157            carry = c;
158        }
159
160        (Self { limbs }, carry)
161    }
162}
163
164impl AsRef<[Word]> for BoxedUint {
165    fn as_ref(&self) -> &[Word] {
166        self.as_words()
167    }
168}
169
170impl AsMut<[Word]> for BoxedUint {
171    fn as_mut(&mut self) -> &mut [Word] {
172        self.as_words_mut()
173    }
174}
175
176impl AsRef<[Limb]> for BoxedUint {
177    fn as_ref(&self) -> &[Limb] {
178        self.as_limbs()
179    }
180}
181
182impl AsMut<[Limb]> for BoxedUint {
183    fn as_mut(&mut self) -> &mut [Limb] {
184        self.as_limbs_mut()
185    }
186}
187
188impl fmt::Debug for BoxedUint {
189    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
190        write!(f, "BoxedUint(0x{self:X})")
191    }
192}
193
194impl fmt::Display for BoxedUint {
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        fmt::UpperHex::fmt(self, f)
197    }
198}
199
200impl fmt::LowerHex for BoxedUint {
201    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
202        if self.limbs.is_empty() {
203            return fmt::LowerHex::fmt(&Limb::ZERO, f);
204        }
205
206        for limb in self.limbs.iter().rev() {
207            fmt::LowerHex::fmt(limb, f)?;
208        }
209        Ok(())
210    }
211}
212
213impl fmt::UpperHex for BoxedUint {
214    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
215        if self.limbs.is_empty() {
216            return fmt::LowerHex::fmt(&Limb::ZERO, f);
217        }
218
219        for limb in self.limbs.iter().rev() {
220            fmt::UpperHex::fmt(limb, f)?;
221        }
222        Ok(())
223    }
224}
225
226#[cfg(feature = "zeroize")]
227impl Zeroize for BoxedUint {
228    fn zeroize(&mut self) {
229        self.limbs.zeroize();
230    }
231}
crypto_bigint/boxed/uint.rs

crypto_bigint/boxed/
uint.rs
