crypto_bigint/uint/
boxed.rs

1//! Heap-allocated big unsigned integers.
2
3mod add;
4mod add_mod;
5mod bit_and;
6mod bit_not;
7mod bit_or;
8mod bit_xor;
9mod bits;
10mod cmp;
11mod ct;
12pub(crate) mod div;
13mod div_limb;
14pub(crate) mod encoding;
15mod from;
16mod gcd;
17mod inv_mod;
18mod mul;
19mod mul_mod;
20mod neg;
21mod neg_mod;
22mod shl;
23mod shr;
24mod sqrt;
25mod sub;
26mod sub_mod;
27
28#[cfg(feature = "rand_core")]
29mod rand;
30
31use crate::{modular::BoxedMontyForm, Integer, Limb, NonZero, Odd, Word, Zero};
32use alloc::{boxed::Box, vec, vec::Vec};
33use core::fmt;
34use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
35
36#[cfg(feature = "zeroize")]
37use zeroize::Zeroize;
38
39/// Fixed-precision heap-allocated big unsigned integer.
40///
41/// Alternative to the stack-allocated [`Uint`][`crate::Uint`] but with a
42/// fixed precision chosen at runtime instead of compile time.
43///
44/// Unlike many other heap-allocated big integer libraries, this type is not
45/// arbitrary precision and will wrap at its fixed-precision rather than
46/// automatically growing.
47#[allow(clippy::derived_hash_with_manual_eq)]
48#[derive(Clone, Hash)]
49pub struct BoxedUint {
50    /// Boxed slice containing limbs.
51    ///
52    /// Stored from least significant to most significant.
53    pub(crate) limbs: Box<[Limb]>,
54}
55
56impl BoxedUint {
57    fn limbs_for_precision(at_least_bits_precision: u32) -> usize {
58        at_least_bits_precision.div_ceil(Limb::BITS) as usize
59    }
60
61    /// Get the value `0` represented as succinctly as possible.
62    pub fn zero() -> Self {
63        Self {
64            limbs: vec![Limb::ZERO; 1].into(),
65        }
66    }
67
68    /// Get the value `0` with the given number of bits of precision.
69    ///
70    /// `at_least_bits_precision` is rounded up to a multiple of [`Limb::BITS`].
71    pub fn zero_with_precision(at_least_bits_precision: u32) -> Self {
72        vec![Limb::ZERO; Self::limbs_for_precision(at_least_bits_precision)].into()
73    }
74
75    /// Get the value `1`, represented as succinctly as possible.
76    pub fn one() -> Self {
77        Self {
78            limbs: vec![Limb::ONE; 1].into(),
79        }
80    }
81
82    /// Get the value `1` with the given number of bits of precision.
83    ///
84    /// `at_least_bits_precision` is rounded up to a multiple of [`Limb::BITS`].
85    pub fn one_with_precision(at_least_bits_precision: u32) -> Self {
86        let mut ret = Self::zero_with_precision(at_least_bits_precision);
87        ret.limbs[0] = Limb::ONE;
88        ret
89    }
90
91    /// Is this [`BoxedUint`] equal to zero?
92    pub fn is_zero(&self) -> Choice {
93        self.limbs
94            .iter()
95            .fold(Choice::from(1), |acc, limb| acc & limb.is_zero())
96    }
97
98    /// Is this [`BoxedUint`] *NOT* equal to zero?
99    #[inline]
100    pub fn is_nonzero(&self) -> Choice {
101        !self.is_zero()
102    }
103
104    /// Is this [`BoxedUint`] equal to one?
105    pub fn is_one(&self) -> Choice {
106        let mut iter = self.limbs.iter();
107        let choice = iter.next().copied().unwrap_or(Limb::ZERO).ct_eq(&Limb::ONE);
108        iter.fold(choice, |acc, limb| acc & limb.is_zero())
109    }
110
111    /// Get the maximum value for a `BoxedUint` created with `at_least_bits_precision`
112    /// precision bits requested.
113    ///
114    /// That is, returns the value `2^self.bits_precision() - 1`.
115    pub fn max(at_least_bits_precision: u32) -> Self {
116        vec![Limb::MAX; Self::limbs_for_precision(at_least_bits_precision)].into()
117    }
118
119    /// Create a [`BoxedUint`] from an array of [`Word`]s (i.e. word-sized unsigned
120    /// integers).
121    #[inline]
122    pub fn from_words(words: impl IntoIterator<Item = Word>) -> Self {
123        Self {
124            limbs: words.into_iter().map(Into::into).collect(),
125        }
126    }
127
128    /// Create a boxed slice of [`Word`]s (i.e. word-sized unsigned integers) from
129    /// a [`BoxedUint`].
130    #[inline]
131    pub fn to_words(&self) -> Box<[Word]> {
132        self.limbs.iter().copied().map(Into::into).collect()
133    }
134
135    /// Borrow the inner limbs as a slice of [`Word`]s.
136    pub fn as_words(&self) -> &[Word] {
137        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
138        #[allow(trivial_casts, unsafe_code)]
139        unsafe {
140            &*((&*self.limbs as *const [Limb]) as *const [Word])
141        }
142    }
143
144    /// Borrow the inner limbs as a mutable slice of [`Word`]s.
145    pub fn as_words_mut(&mut self) -> &mut [Word] {
146        // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word`
147        #[allow(trivial_casts, unsafe_code)]
148        unsafe {
149            &mut *((&mut *self.limbs as *mut [Limb]) as *mut [Word])
150        }
151    }
152
153    /// Borrow the limbs of this [`BoxedUint`].
154    pub fn as_limbs(&self) -> &[Limb] {
155        self.limbs.as_ref()
156    }
157
158    /// Borrow the limbs of this [`BoxedUint`] mutably.
159    pub fn as_limbs_mut(&mut self) -> &mut [Limb] {
160        self.limbs.as_mut()
161    }
162
163    /// Convert this [`BoxedUint`] into its inner limbs.
164    pub fn to_limbs(&self) -> Box<[Limb]> {
165        self.limbs.clone()
166    }
167
168    /// Convert this [`BoxedUint`] into its inner limbs.
169    pub fn into_limbs(self) -> Box<[Limb]> {
170        self.limbs
171    }
172
173    /// Get the number of limbs in this [`BoxedUint`].
174    pub fn nlimbs(&self) -> usize {
175        self.limbs.len()
176    }
177
178    /// Convert into an [`Odd`].
179    pub fn to_odd(&self) -> CtOption<Odd<Self>> {
180        let is_odd = self.is_odd();
181        CtOption::new(Odd(self.clone()), is_odd)
182    }
183
184    /// Widen this type's precision to the given number of bits.
185    ///
186    /// Panics if `at_least_bits_precision` is smaller than the current precision.
187    #[must_use]
188    pub fn widen(&self, at_least_bits_precision: u32) -> BoxedUint {
189        assert!(at_least_bits_precision >= self.bits_precision());
190
191        let mut ret = BoxedUint::zero_with_precision(at_least_bits_precision);
192        ret.limbs[..self.nlimbs()].copy_from_slice(&self.limbs);
193        ret
194    }
195
196    /// Shortens this type's precision to the given number of bits.
197    ///
198    /// Panics if `at_least_bits_precision` is larger than the current precision.
199    #[must_use]
200    pub fn shorten(&self, at_least_bits_precision: u32) -> BoxedUint {
201        assert!(at_least_bits_precision <= self.bits_precision());
202        let mut ret = BoxedUint::zero_with_precision(at_least_bits_precision);
203        let nlimbs = ret.nlimbs();
204        ret.limbs.copy_from_slice(&self.limbs[..nlimbs]);
205        ret
206    }
207
208    /// Perform a carry chain-like operation over the limbs of the inputs,
209    /// constructing a result from the returned limbs and carry which is
210    /// widened to the same width as the widest input.
211    ///
212    /// If one of the two values has fewer limbs than the other, pads with
213    /// [`Limb::ZERO`] as the value for that limb.
214    #[inline]
215    fn fold_limbs<F>(lhs: &Self, rhs: &Self, mut carry: Limb, f: F) -> (Self, Limb)
216    where
217        F: Fn(Limb, Limb, Limb) -> (Limb, Limb),
218    {
219        let nlimbs = cmp::max(lhs.nlimbs(), rhs.nlimbs());
220        let mut limbs = Vec::with_capacity(nlimbs);
221
222        for i in 0..nlimbs {
223            let &a = lhs.limbs.get(i).unwrap_or(&Limb::ZERO);
224            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
225            let (limb, c) = f(a, b, carry);
226            limbs.push(limb);
227            carry = c;
228        }
229
230        (limbs.into(), carry)
231    }
232
233    /// Iterate over the limbs of the inputs, applying the given function, and
234    /// constructing a result from the returned values.
235    #[inline]
236    fn map_limbs<F>(lhs: &Self, rhs: &Self, f: F) -> Self
237    where
238        F: Fn(Limb, Limb) -> Limb,
239    {
240        let nlimbs = cmp::max(lhs.nlimbs(), rhs.nlimbs());
241        let mut limbs = Vec::with_capacity(nlimbs);
242
243        for i in 0..nlimbs {
244            let &a = lhs.limbs.get(i).unwrap_or(&Limb::ZERO);
245            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
246            limbs.push(f(a, b));
247        }
248
249        limbs.into()
250    }
251
252    /// Set the value of `self` to zero in-place if `choice` is truthy.
253    pub(crate) fn conditional_set_zero(&mut self, choice: Choice) {
254        let nlimbs = self.nlimbs();
255        let limbs = self.limbs.as_mut();
256        for i in 0..nlimbs {
257            limbs[i] = Limb::conditional_select(&limbs[i], &Limb::ZERO, choice);
258        }
259    }
260}
261
262impl NonZero<BoxedUint> {
263    /// Widen this type's precision to the given number of bits.
264    ///
265    /// See [`BoxedUint::widen`] for more information, including panic conditions.
266    pub fn widen(&self, bits_precision: u32) -> Self {
267        NonZero(self.0.widen(bits_precision))
268    }
269}
270
271impl AsRef<[Word]> for BoxedUint {
272    fn as_ref(&self) -> &[Word] {
273        self.as_words()
274    }
275}
276
277impl AsMut<[Word]> for BoxedUint {
278    fn as_mut(&mut self) -> &mut [Word] {
279        self.as_words_mut()
280    }
281}
282
283impl AsRef<[Limb]> for BoxedUint {
284    fn as_ref(&self) -> &[Limb] {
285        self.as_limbs()
286    }
287}
288
289impl AsMut<[Limb]> for BoxedUint {
290    fn as_mut(&mut self) -> &mut [Limb] {
291        self.as_limbs_mut()
292    }
293}
294
295impl Default for BoxedUint {
296    fn default() -> Self {
297        Self::zero()
298    }
299}
300
301impl Integer for BoxedUint {
302    type Monty = BoxedMontyForm;
303
304    fn one() -> Self {
305        Self::one()
306    }
307
308    fn from_limb_like(limb: Limb, other: &Self) -> Self {
309        let mut ret = Self::zero_with_precision(other.bits_precision());
310        ret.limbs[0] = limb;
311        ret
312    }
313
314    fn nlimbs(&self) -> usize {
315        self.nlimbs()
316    }
317}
318
319impl Zero for BoxedUint {
320    fn zero() -> Self {
321        Self::zero()
322    }
323
324    fn is_zero(&self) -> Choice {
325        self.is_zero()
326    }
327
328    fn set_zero(&mut self) {
329        self.limbs.as_mut().fill(Limb::ZERO)
330    }
331}
332
333impl num_traits::Zero for BoxedUint {
334    fn zero() -> Self {
335        Self::zero()
336    }
337
338    fn is_zero(&self) -> bool {
339        self.is_zero().into()
340    }
341}
342
343impl num_traits::One for BoxedUint {
344    fn one() -> Self {
345        Self::one()
346    }
347
348    fn is_one(&self) -> bool {
349        self.is_one().into()
350    }
351}
352
353#[cfg(feature = "zeroize")]
354impl Zeroize for BoxedUint {
355    fn zeroize(&mut self) {
356        self.limbs.zeroize();
357    }
358}
359
360impl fmt::Debug for BoxedUint {
361    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
362        write!(f, "BoxedUint(0x{self:X})")
363    }
364}
365
366impl fmt::Display for BoxedUint {
367    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
368        fmt::UpperHex::fmt(self, f)
369    }
370}
371
372impl fmt::Binary for BoxedUint {
373    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
374        if self.limbs.is_empty() {
375            return fmt::Binary::fmt(&Limb::ZERO, f);
376        }
377
378        for limb in self.limbs.iter().rev() {
379            fmt::Binary::fmt(limb, f)?;
380        }
381        Ok(())
382    }
383}
384
385impl fmt::LowerHex for BoxedUint {
386    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
387        if self.limbs.is_empty() {
388            return fmt::LowerHex::fmt(&Limb::ZERO, f);
389        }
390
391        for limb in self.limbs.iter().rev() {
392            fmt::LowerHex::fmt(limb, f)?;
393        }
394        Ok(())
395    }
396}
397
398impl fmt::UpperHex for BoxedUint {
399    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
400        if self.limbs.is_empty() {
401            return fmt::LowerHex::fmt(&Limb::ZERO, f);
402        }
403
404        for limb in self.limbs.iter().rev() {
405            fmt::UpperHex::fmt(limb, f)?;
406        }
407        Ok(())
408    }
409}
410
411#[cfg(test)]
412mod tests {
413    use super::BoxedUint;
414    use crate::Word;
415    use alloc::vec::Vec;
416
417    #[test]
418    fn from_word_vec() {
419        let words: &[Word] = &[0, 1, 2, 3];
420        let uint = BoxedUint::from(Vec::from(words));
421        assert_eq!(uint.nlimbs(), 4);
422        assert_eq!(uint.as_words(), words);
423    }
424}
crypto_bigint/uint/boxed.rs

crypto_bigint/uint/
boxed.rs
