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;
13pub(crate) mod encoding;
14mod from;
15mod gcd;
16mod invert_mod;
17mod lcm;
18mod mul;
19mod mul_mod;
20mod neg;
21mod neg_mod;
22mod pow;
23mod pow_mod;
24mod shl;
25mod shr;
26mod sqrt;
27mod sub;
28mod sub_mod;
29
30#[cfg(feature = "rand_core")]
31mod rand;
32
33use crate::{
34    Choice, CtAssign, CtEq, CtOption, Integer, Limb, NonZero, Odd, One, Resize, UintRef, Unsigned,
35    UnsignedWithMontyForm, Word, Zero, bitlen, modular::BoxedMontyForm, traits::sealed::Sealed,
36};
37use alloc::{boxed::Box, vec, vec::Vec};
38use core::{
39    borrow::{Borrow, BorrowMut},
40    fmt,
41    iter::repeat,
42};
43
44#[cfg(feature = "zeroize")]
45use zeroize::Zeroize;
46
47/// Fixed-precision heap-allocated big unsigned integer.
48///
49/// Alternative to the stack-allocated [`Uint`][`crate::Uint`] but with a
50/// fixed precision chosen at runtime instead of compile time.
51///
52/// Unlike many other heap-allocated big integer libraries, this type is not
53/// arbitrary precision and will wrap at its fixed-precision rather than
54/// automatically growing.
55#[derive(Clone)]
56pub struct BoxedUint {
57    /// Boxed slice containing limbs.
58    ///
59    /// Stored from least significant to most significant.
60    pub(crate) limbs: Box<[Limb]>,
61}
62
63impl BoxedUint {
64    /// Get the value `0` represented as succinctly as possible.
65    #[must_use]
66    pub fn zero() -> Self {
67        Self {
68            limbs: vec![Limb::ZERO; 1].into(),
69        }
70    }
71
72    /// Get the value `0` with the given number of bits of precision.
73    ///
74    /// `at_least_bits_precision` is rounded up to a multiple of [`Limb::BITS`].
75    #[must_use]
76    pub fn zero_with_precision(at_least_bits_precision: u32) -> Self {
77        vec![Limb::ZERO; bitlen::to_limbs(at_least_bits_precision)].into()
78    }
79
80    /// Get the value `1`, represented as succinctly as possible.
81    #[must_use]
82    pub fn one() -> Self {
83        Self {
84            limbs: vec![Limb::ONE; 1].into(),
85        }
86    }
87
88    /// Get the value `1` with the given number of bits of precision.
89    ///
90    /// `at_least_bits_precision` is rounded up to a multiple of [`Limb::BITS`].
91    #[must_use]
92    pub fn one_with_precision(at_least_bits_precision: u32) -> Self {
93        let mut ret = Self::zero_with_precision(at_least_bits_precision);
94        ret.limbs[0] = Limb::ONE;
95        ret
96    }
97
98    /// Is this [`BoxedUint`] equal to zero?
99    #[must_use]
100    pub fn is_zero(&self) -> Choice {
101        self.limbs
102            .iter()
103            .fold(Choice::TRUE, |acc, limb| acc & limb.is_zero())
104    }
105
106    /// Is this [`BoxedUint`] *NOT* equal to zero?
107    #[inline]
108    #[must_use]
109    pub fn is_nonzero(&self) -> Choice {
110        !self.is_zero()
111    }
112
113    /// Is this [`BoxedUint`] equal to one?
114    #[must_use]
115    pub fn is_one(&self) -> Choice {
116        let mut iter = self.limbs.iter();
117        let choice = iter.next().copied().unwrap_or(Limb::ZERO).ct_eq(&Limb::ONE);
118        iter.fold(choice, |acc, limb| acc & limb.is_zero())
119    }
120
121    /// Get the maximum value for a `BoxedUint` created with `at_least_bits_precision`
122    /// precision bits requested.
123    ///
124    /// That is, returns the value `2^self.bits_precision() - 1`.
125    #[must_use]
126    pub fn max(at_least_bits_precision: u32) -> Self {
127        vec![Limb::MAX; bitlen::to_limbs(at_least_bits_precision)].into()
128    }
129
130    /// Create a [`BoxedUint`] from an array of [`Word`]s (i.e. word-sized unsigned
131    /// integers).
132    #[inline]
133    pub fn from_words(words: impl IntoIterator<Item = Word>) -> Self {
134        Self {
135            limbs: words.into_iter().map(Into::into).collect(),
136        }
137    }
138
139    /// Create a [`BoxedUint`] from an array of [`Word`]s (i.e. word-sized unsigned
140    /// integers), specifying the precision of the result. Any words above the given
141    /// precision will be dropped.
142    #[inline]
143    pub fn from_words_with_precision(
144        words: impl IntoIterator<Item = Word>,
145        at_least_bits_precision: u32,
146    ) -> Self {
147        let size = bitlen::to_limbs(at_least_bits_precision);
148        Self {
149            limbs: words
150                .into_iter()
151                .map(Into::into)
152                .chain(repeat(Limb::ZERO))
153                .take(size)
154                .collect(),
155        }
156    }
157
158    /// Create a boxed slice of [`Word`]s (i.e. word-sized unsigned integers) from
159    /// a [`BoxedUint`].
160    #[inline]
161    pub fn to_words(&self) -> Box<[Word]> {
162        self.limbs.iter().copied().map(Into::into).collect()
163    }
164
165    /// Borrow the inner limbs as a slice of [`Word`]s.
166    #[must_use]
167    pub fn as_words(&self) -> &[Word] {
168        self.as_uint_ref().as_words()
169    }
170
171    /// Borrow the inner limbs as a mutable slice of [`Word`]s.
172    pub fn as_mut_words(&mut self) -> &mut [Word] {
173        self.as_mut_uint_ref().as_mut_words()
174    }
175
176    /// Borrow the inner limbs as a mutable slice of [`Word`]s.
177    #[deprecated(since = "0.7.0", note = "please use `as_mut_words` instead")]
178    pub fn as_words_mut(&mut self) -> &mut [Word] {
179        self.as_mut_words()
180    }
181
182    /// Borrow the limbs of this [`BoxedUint`].
183    #[must_use]
184    pub fn as_limbs(&self) -> &[Limb] {
185        self.limbs.as_ref()
186    }
187
188    /// Borrow the limbs of this [`BoxedUint`] mutably.
189    pub fn as_mut_limbs(&mut self) -> &mut [Limb] {
190        self.limbs.as_mut()
191    }
192
193    /// Borrow the limbs of this [`BoxedUint`] mutably.
194    #[deprecated(since = "0.7.0", note = "please use `as_mut_limbs` instead")]
195    pub fn as_limbs_mut(&mut self) -> &mut [Limb] {
196        self.as_mut_limbs()
197    }
198
199    /// Convert this [`BoxedUint`] into its inner limbs.
200    #[must_use]
201    pub fn to_limbs(&self) -> Box<[Limb]> {
202        self.limbs.clone()
203    }
204
205    /// Convert this [`BoxedUint`] into its inner limbs.
206    #[must_use]
207    pub fn into_limbs(self) -> Box<[Limb]> {
208        self.limbs
209    }
210
211    /// Borrow the limbs of this [`BoxedUint`] as a [`UintRef`].
212    #[inline]
213    #[must_use]
214    pub const fn as_uint_ref(&self) -> &UintRef {
215        UintRef::new(&self.limbs)
216    }
217
218    /// Mutably borrow the limbs of this [`BoxedUint`] as a [`UintRef`].
219    #[inline]
220    #[must_use]
221    pub const fn as_mut_uint_ref(&mut self) -> &mut UintRef {
222        UintRef::new_mut(&mut self.limbs)
223    }
224
225    /// Get the number of limbs in this [`BoxedUint`].
226    #[must_use]
227    pub fn nlimbs(&self) -> usize {
228        self.limbs.len()
229    }
230
231    /// Construct a [`NonZero`] reference, returning [`None`] in the event `self` is `0`.
232    #[must_use]
233    pub fn as_nz_vartime(&self) -> Option<&NonZero<Self>> {
234        if self.is_zero_vartime() {
235            None
236        } else {
237            Some(NonZero::new_ref_unchecked(self))
238        }
239    }
240
241    /// Convert to a [`NonZero<BoxedUint>`].
242    ///
243    /// Returns some if the original value is non-zero, and none otherwise.
244    #[must_use]
245    pub fn to_nz(&self) -> CtOption<NonZero<Self>> {
246        self.clone().into_nz()
247    }
248
249    /// Convert to a [`NonZero<BoxedUint>`], defaulting to one.
250    ///
251    /// Returns a pair consisting of a [`NonZero<BoxedUint>`], and a [`Choice`]
252    /// indicating whether the original value was non-zero (and preserved).
253    #[inline(always)]
254    #[must_use]
255    pub(crate) fn to_nz_or_one(&self) -> (NonZero<Self>, Choice) {
256        let is_zero = self.is_zero();
257        let mut nz = self.clone();
258        nz.as_mut_uint_ref().conditional_set_one(is_zero);
259        (NonZero::new_unchecked(nz), !is_zero)
260    }
261
262    /// Convert to an [`Odd<BoxedUint>`], defaulting to one.
263    ///
264    /// Returns a pair consisting of an [`Odd<BoxedUint>`], and a [`Choice`]
265    /// indicating whether the original value was odd (and preserved).
266    #[inline(always)]
267    #[must_use]
268    pub(crate) fn to_odd_or_one(&self) -> (Odd<Self>, Choice) {
269        let is_odd = self.is_odd();
270        let mut odd = self.clone();
271        odd.as_mut_uint_ref().conditional_set_one(is_odd.not());
272        (Odd::new_unchecked(odd), is_odd)
273    }
274
275    /// Construct an [`Odd`] reference, returning [`None`] in the event `self` is even.
276    #[must_use]
277    pub fn as_odd_vartime(&self) -> Option<&Odd<Self>> {
278        if !self.is_odd().to_bool_vartime() {
279            None
280        } else {
281            Some(Odd::new_ref_unchecked(self))
282        }
283    }
284
285    /// Convert to an [`Odd<BoxedUint>`].
286    ///
287    /// Returns some if the original value is odd, and none otherwise.
288    #[must_use]
289    pub fn to_odd(&self) -> CtOption<Odd<Self>> {
290        self.clone().into_odd()
291    }
292
293    /// Convert to a [`NonZero<BoxedUint>`].
294    ///
295    /// Returns some if the original value is non-zero, and none otherwise.
296    #[must_use]
297    pub fn into_nz(mut self) -> CtOption<NonZero<Self>> {
298        let is_nz = self.is_nonzero();
299
300        // Ensure the `NonZero` we construct is actually non-zero, even if the `CtOption` is none
301        self.limbs[0].ct_assign(&Limb::ONE, !is_nz);
302        CtOption::new(NonZero::new_unchecked(self), is_nz)
303    }
304
305    /// Convert to an [`Odd<BoxedUint>`].
306    ///
307    /// Returns some if the original value is odd, and none otherwise.
308    #[must_use]
309    pub fn into_odd(mut self) -> CtOption<Odd<Self>> {
310        let is_odd = self.is_odd();
311
312        // Ensure the `Odd` we construct is actually odd, even if the `CtOption` is none
313        self.limbs[0].ct_assign(&Limb::ONE, !is_odd);
314        CtOption::new(Odd::new_unchecked(self.clone()), is_odd)
315    }
316
317    /// Widen this type's precision to the given number of bits.
318    ///
319    /// # Panics
320    /// - if `at_least_bits_precision` is smaller than the current precision.
321    #[must_use]
322    #[deprecated(since = "0.7.0", note = "please use `resize` instead")]
323    pub fn widen(&self, at_least_bits_precision: u32) -> BoxedUint {
324        assert!(at_least_bits_precision >= self.bits_precision());
325
326        let mut ret = BoxedUint::zero_with_precision(at_least_bits_precision);
327        ret.limbs[..self.nlimbs()].copy_from_slice(&self.limbs);
328        ret
329    }
330
331    /// Shortens this type's precision to the given number of bits.
332    ///
333    /// # Panics
334    /// - if `at_least_bits_precision` is larger than the current precision.
335    #[must_use]
336    #[deprecated(since = "0.7.0", note = "please use `resize` instead")]
337    pub fn shorten(&self, at_least_bits_precision: u32) -> BoxedUint {
338        assert!(at_least_bits_precision <= self.bits_precision());
339        let mut ret = BoxedUint::zero_with_precision(at_least_bits_precision);
340        let nlimbs = ret.nlimbs();
341        ret.limbs.copy_from_slice(&self.limbs[..nlimbs]);
342        ret
343    }
344
345    /// Iterate over the limbs of the inputs, applying the given function, and
346    /// constructing a result from the returned values.
347    #[inline]
348    fn map_limbs<F>(lhs: &Self, rhs: &Self, f: F) -> Self
349    where
350        F: Fn(Limb, Limb) -> Limb,
351    {
352        let nlimbs = cmp::max(lhs.nlimbs(), rhs.nlimbs());
353        let mut limbs = Vec::with_capacity(nlimbs);
354
355        for i in 0..nlimbs {
356            let &a = lhs.limbs.get(i).unwrap_or(&Limb::ZERO);
357            let &b = rhs.limbs.get(i).unwrap_or(&Limb::ZERO);
358            limbs.push(f(a, b));
359        }
360
361        limbs.into()
362    }
363
364    /// Resize this value in place without checking whether the current value fits.
365    ///
366    /// If `at_least_bits_precision` is below the current precision, high limbs
367    /// are truncated. If it is above the current precision, new high limbs are
368    /// zero.
369    pub(crate) fn resize_in_place_unchecked(&mut self, at_least_bits_precision: u32) {
370        let new_len = bitlen::to_limbs(at_least_bits_precision);
371
372        if new_len != self.limbs.len() {
373            let mut limbs = core::mem::take(&mut self.limbs).into_vec();
374            limbs.resize(new_len, Limb::ZERO);
375            *self = Self::from(limbs);
376        }
377    }
378
379    /// Returns `true` if the integer's bit size is smaller or equal to `bits`.
380    pub(crate) fn is_within_bits(&self, bits: u32) -> bool {
381        bits >= self.bits_precision() || bits >= self.bits()
382    }
383}
384
385impl Resize for BoxedUint {
386    type Output = BoxedUint;
387
388    fn resize_unchecked(mut self, at_least_bits_precision: u32) -> Self::Output {
389        self.resize_in_place_unchecked(at_least_bits_precision);
390        self
391    }
392
393    fn try_resize(self, at_least_bits_precision: u32) -> Option<BoxedUint> {
394        if self.is_within_bits(at_least_bits_precision) {
395            Some(self.resize_unchecked(at_least_bits_precision))
396        } else {
397            None
398        }
399    }
400}
401
402impl Resize for &BoxedUint {
403    type Output = BoxedUint;
404
405    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
406        let mut ret = BoxedUint::zero_with_precision(at_least_bits_precision);
407        let num_limbs_to_copy = core::cmp::min(ret.limbs.len(), self.limbs.len());
408        ret.limbs[..num_limbs_to_copy].copy_from_slice(&self.limbs[..num_limbs_to_copy]);
409        ret
410    }
411
412    fn try_resize(self, at_least_bits_precision: u32) -> Option<BoxedUint> {
413        if self.is_within_bits(at_least_bits_precision) {
414            Some(self.resize_unchecked(at_least_bits_precision))
415        } else {
416            None
417        }
418    }
419}
420
421impl Resize for NonZero<BoxedUint> {
422    type Output = Self;
423
424    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
425        NonZero::new_unchecked(self.get().resize_unchecked(at_least_bits_precision))
426    }
427
428    fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
429        self.get()
430            .try_resize(at_least_bits_precision)
431            .map(NonZero::new_unchecked)
432    }
433}
434
435impl Resize for &NonZero<BoxedUint> {
436    type Output = NonZero<BoxedUint>;
437
438    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
439        NonZero::new_unchecked(self.as_ref().resize_unchecked(at_least_bits_precision))
440    }
441
442    fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
443        self.as_ref()
444            .try_resize(at_least_bits_precision)
445            .map(NonZero::new_unchecked)
446    }
447}
448
449impl AsRef<[Word]> for BoxedUint {
450    fn as_ref(&self) -> &[Word] {
451        self.as_words()
452    }
453}
454
455impl AsMut<[Word]> for BoxedUint {
456    fn as_mut(&mut self) -> &mut [Word] {
457        self.as_mut_words()
458    }
459}
460
461impl AsRef<[Limb]> for BoxedUint {
462    fn as_ref(&self) -> &[Limb] {
463        self.as_limbs()
464    }
465}
466
467impl AsMut<[Limb]> for BoxedUint {
468    fn as_mut(&mut self) -> &mut [Limb] {
469        self.as_mut_limbs()
470    }
471}
472
473impl AsRef<UintRef> for BoxedUint {
474    fn as_ref(&self) -> &UintRef {
475        self.as_uint_ref()
476    }
477}
478
479impl AsMut<UintRef> for BoxedUint {
480    fn as_mut(&mut self) -> &mut UintRef {
481        self.as_mut_uint_ref()
482    }
483}
484
485impl Borrow<UintRef> for BoxedUint {
486    fn borrow(&self) -> &UintRef {
487        self.as_uint_ref()
488    }
489}
490
491impl BorrowMut<UintRef> for BoxedUint {
492    fn borrow_mut(&mut self) -> &mut UintRef {
493        self.as_mut_uint_ref()
494    }
495}
496
497impl Default for BoxedUint {
498    fn default() -> Self {
499        Self::zero()
500    }
501}
502
503impl Integer for BoxedUint {
504    fn as_limbs(&self) -> &[Limb] {
505        &self.limbs
506    }
507
508    fn as_mut_limbs(&mut self) -> &mut [Limb] {
509        &mut self.limbs
510    }
511
512    fn nlimbs(&self) -> usize {
513        self.nlimbs()
514    }
515}
516
517impl Sealed for BoxedUint {}
518
519impl Unsigned for BoxedUint {
520    fn as_uint_ref(&self) -> &UintRef {
521        self.as_uint_ref()
522    }
523
524    fn as_mut_uint_ref(&mut self) -> &mut UintRef {
525        self.as_mut_uint_ref()
526    }
527
528    fn from_limb_like(limb: Limb, other: &Self) -> Self {
529        let mut ret = Self::zero_with_precision(other.bits_precision());
530        ret.limbs[0] = limb;
531        ret
532    }
533}
534
535impl UnsignedWithMontyForm for BoxedUint {
536    type MontyForm = BoxedMontyForm;
537}
538
539impl Zero for BoxedUint {
540    fn zero() -> Self {
541        Self::zero()
542    }
543
544    fn is_zero(&self) -> Choice {
545        self.is_zero()
546    }
547
548    fn set_zero(&mut self) {
549        self.limbs.as_mut().fill(Limb::ZERO);
550    }
551}
552
553impl One for BoxedUint {
554    fn one() -> Self {
555        Self::one()
556    }
557
558    fn one_like(other: &Self) -> Self {
559        let mut ret = other.clone();
560        ret.set_one();
561        ret
562    }
563
564    fn is_one(&self) -> Choice {
565        self.is_one()
566    }
567
568    fn set_one(&mut self) {
569        self.limbs.as_mut().fill(Limb::ZERO);
570        self.limbs[0] = Limb::ONE;
571    }
572}
573
574impl num_traits::Zero for BoxedUint {
575    fn zero() -> Self {
576        Self::zero()
577    }
578
579    fn is_zero(&self) -> bool {
580        self.is_zero().into()
581    }
582
583    fn set_zero(&mut self) {
584        Zero::set_zero(self);
585    }
586}
587
588impl num_traits::One for BoxedUint {
589    fn one() -> Self {
590        Self::one()
591    }
592
593    fn is_one(&self) -> bool {
594        self.is_one().into()
595    }
596
597    fn set_one(&mut self) {
598        One::set_one(self);
599    }
600}
601
602#[cfg(feature = "zeroize")]
603impl Zeroize for BoxedUint {
604    fn zeroize(&mut self) {
605        self.limbs.zeroize();
606    }
607}
608
609impl fmt::Debug for BoxedUint {
610    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
611        write!(f, "BoxedUint(0x{:X})", self.as_uint_ref())
612    }
613}
614
615impl fmt::Display for BoxedUint {
616    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
617        fmt::UpperHex::fmt(self, f)
618    }
619}
620
621impl fmt::Binary for BoxedUint {
622    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
623        fmt::Binary::fmt(self.as_uint_ref(), f)
624    }
625}
626
627impl fmt::LowerHex for BoxedUint {
628    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
629        fmt::LowerHex::fmt(self.as_uint_ref(), f)
630    }
631}
632
633impl fmt::UpperHex for BoxedUint {
634    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
635        fmt::UpperHex::fmt(self.as_uint_ref(), f)
636    }
637}
638
639#[cfg(test)]
640mod tests {
641    use super::BoxedUint;
642    use crate::Word;
643    use alloc::vec::Vec;
644
645    #[test]
646    fn from_word_vec() {
647        let words: &[Word] = &[0, 1, 2, 3];
648        let uint = BoxedUint::from(Vec::from(words));
649        assert_eq!(uint.nlimbs(), 4);
650        assert_eq!(uint.as_words(), words);
651    }
652
653    #[test]
654    fn fmt_lower_hex() {
655        let n = BoxedUint::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD", 128).unwrap();
656        assert_eq!(format!("{n:x}"), "aaaaaaaabbbbbbbbccccccccdddddddd");
657        assert_eq!(format!("{n:#x}"), "0xaaaaaaaabbbbbbbbccccccccdddddddd");
658    }
659
660    #[test]
661    fn fmt_upper_hex() {
662        let n = BoxedUint::from_be_hex("aaaaaaaabbbbbbbbccccccccdddddddd", 128).unwrap();
663        assert_eq!(format!("{n:X}"), "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
664        assert_eq!(format!("{n:#X}"), "0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
665    }
666
667    #[test]
668    fn fmt_binary() {
669        let n = BoxedUint::from_be_hex("aaaaaaaabbbbbbbbccccccccdddddddd", 128).unwrap();
670        assert_eq!(
671            format!("{n:b}"),
672            "10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
673        );
674        assert_eq!(
675            format!("{n:#b}"),
676            "0b10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
677        );
678    }
679
680    #[test]
681    fn test_unsigned() {
682        crate::traits::tests::test_unsigned(
683            BoxedUint::zero_with_precision(128),
684            BoxedUint::max(128),
685        );
686    }
687
688    #[test]
689    fn test_unsigned_monty_form() {
690        crate::traits::tests::test_unsigned_monty_form::<BoxedUint>();
691    }
692}
crypto_bigint/uint/boxed.rs

crypto_bigint/uint/
boxed.rs
