crylib/big_int/
unsigned.rs

1//! Unsigned large integers.
2//!
3//! Unlike many multi-precision libraries, these integers have a fixed (but arbitrary) size.
4//!
5//! Due to current limitations in Rust, some functions can only be applied on a per-size basis,
6//! rather than being generic over any size. This will hopefully be fixed some day.
7
8use super::{carry_mul, BigInt, FromNegErr};
9use core::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
10
11/// An unsigned integer of size `N * 64` bits.
12///
13/// Internally, [`UBigInt<N>`] is a little-endian `[u64; N]`.
14#[derive(Clone, Copy, PartialEq, Eq, Hash)]
15#[repr(transparent)]
16pub struct UBigInt<const N: usize>(pub [u64; N]);
17
18impl<const N: usize> core::fmt::Display for UBigInt<N> {
19    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
20        core::fmt::LowerHex::fmt(&self, f)
21    }
22}
23
24impl<const N: usize> core::fmt::LowerHex for UBigInt<N> {
25    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
26        f.write_str("0x")?;
27        for i in self.0.iter().rev() {
28            write!(f, "{:016x}", i)?
29        }
30        Ok(())
31    }
32}
33
34impl<const N: usize> core::fmt::UpperHex for UBigInt<N> {
35    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
36        f.write_str("0x")?;
37        for i in self.0.iter().rev() {
38            write!(f, "{:016X}", i)?
39        }
40        Ok(())
41    }
42}
43
44impl<const N: usize> core::fmt::Debug for UBigInt<N> {
45    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
46        f.write_str("{ ")?;
47        for i in self.0 {
48            write!(f, "{:016x}, ", i)?
49        }
50        f.write_str("}")?;
51        Ok(())
52    }
53}
54
55impl<const N: usize> UBigInt<N> {
56    /// Constructs a new `UBigInt` of length `N` from a little-endian `[u64; N]`.
57    ///
58    /// This is the same as `Self(value)`
59    pub const fn new(value: [u64; N]) -> Self {
60        Self(value)
61    }
62
63    pub const fn from_ref(value: &[u64; N]) -> &Self {
64        let ptr = value as *const [u64; N] as *const UBigInt<N>;
65        // SAFETY: `UBigInt<N>` is repr(transparent) and therefore has the same memory layout as
66        // `[u64; N]`.
67        unsafe { &*ptr }
68    }
69
70    pub const fn from_ref_mut(value: &mut [u64; N]) -> &mut Self {
71        let ptr = value as *mut [u64; N] as *mut UBigInt<N>;
72        // SAFETY: `UBigInt<N>` is repr(transparent) and therefore has the same memory layout as
73        // `[u64; N]`.
74        unsafe { &mut *ptr }
75    }
76
77    /// The zero value of [`UBigInt<N>`]
78    ///
79    /// # Examples
80    /// ```
81    /// use crylib::big_int::UBigInt;
82    ///
83    /// assert_eq!(UBigInt::<4>::ZERO, UBigInt::MIN);
84    /// assert_eq!(UBigInt::<4>::ZERO.count_digits(), 0);
85    /// ```
86    ///
87    /// This has the same value as [`UBigInt<N>::MIN`].
88    pub const ZERO: Self = Self([u64::MIN; N]);
89
90    /// The maximum value representable by [`UBigInt<N>`].
91    ///
92    /// # Examples
93    /// ```
94    /// use crylib::big_int::UBigInt;
95    ///
96    /// assert_eq!(UBigInt::<4>::MAX.count_digits(), 4);
97    /// ```
98    pub const MAX: Self = Self([u64::MAX; N]);
99
100    /// The minimum value representable by [`UBigInt<N>`].
101    ///
102    /// This has the same value as [`UBigInt<N>::ZERO`].
103    pub const MIN: Self = Self::ZERO;
104
105    /// A [`UBigInt`] with value `1`.
106    pub const ONE: Self = {
107        let mut one = Self::ZERO;
108        one.0[0] = 1;
109        one
110    };
111
112    /// Subtracts `rhs` from `self`, returning the result and whether the operation
113    /// overflowed.
114    ///
115    /// If overflow occurs, it wraps around.
116    ///
117    /// # Constant-timedness
118    /// This operation is constant-time.
119    pub fn overflowing_sub(&self, rhs: &Self) -> (Self, bool) {
120        let mut buf = *self;
121        let overflowed = buf.overflowing_sub_assign(rhs);
122        (buf, overflowed)
123    }
124
125    /// Subtracts `rhs` from `self`, storing the result in `self` and
126    /// returning whether the operation overflowed.
127    ///
128    /// If overflow occurs, it wraps around.
129    ///
130    /// # Constant-timedness
131    /// This operation is constant-time.
132    pub fn overflowing_sub_assign(&mut self, rhs: &Self) -> bool {
133        let mut carry = false;
134        for i in 0..N {
135            // TODO: use libcore implementation once stabilized
136            (self.0[i], carry) = super::carry_sub(self.0[i], rhs.0[i], carry);
137        }
138        carry
139    }
140
141    /// Adds `self` and `rhs`, returning the result and whether the operation
142    /// overflowed.
143    ///
144    /// If overflow occurs, it wraps around.
145    ///
146    /// # Constant-timedness
147    /// This operation is constant-time.
148    pub fn overflowing_add(&self, rhs: &Self) -> (Self, bool) {
149        let mut buf = *self;
150        let overflowed = buf.overflowing_add_assign(rhs);
151        (buf, overflowed)
152    }
153
154    /// Adds `self` and `rhs`, storing the result in `self` and
155    /// returning whether the operation overflowed.
156    ///
157    /// If overflow occurs, it wraps around.
158    ///
159    /// # Constant-timedness
160    /// This operation is constant-time.
161    pub fn overflowing_add_assign(&mut self, rhs: &Self) -> bool {
162        let mut carry = false;
163        for i in 0..N {
164            // TODO: use core implementation once stabilized
165            (self.0[i], carry) = super::carry_add(self.0[i], rhs.0[i], carry);
166        }
167        carry
168    }
169
170    /// Returns the number of used digits in `self`.
171    ///
172    /// This is *not* the same as [`Self::len()`].
173    ///
174    /// Note: this function has not yet been benchmarked. It may not actually be any faster.
175    ///
176    /// # Constant-timedness
177    /// This operation is *NOT* constant-time.
178    /// If constant-time is needed, use [`Self::count_digits()`].
179    pub fn count_digits_fast(&self) -> usize {
180        for (count, digit) in self.0.into_iter().rev().enumerate() {
181            if digit != 0 {
182                return N - count;
183            };
184        }
185        0
186    }
187
188    /// Returns the number of digits in `self`.
189    ///
190    /// This is the same as `floor(log64(self))`
191    ///
192    /// This is *not* the same as [`Self::len()`].
193    ///
194    /// # Examples
195    /// ```
196    /// use crylib::big_int::UBigInt;
197    ///
198    /// let large_int = UBigInt([0x0123456789abcdef, 0xfedcba9876543210, 0x0, 0x0]);
199    ///
200    /// assert_eq!(large_int.count_digits(), 2);
201    /// ```
202    ///
203    /// # Constant-timedness
204    /// This is a constant-time operation.
205    /// If constant-time is not needed, consider using [`Self::count_digits_fast()`].
206    pub fn count_digits(&self) -> usize {
207        let mut num_digts = 0;
208        let mut digit_encounterd = false;
209        for digit in self.0.iter().rev() {
210            digit_encounterd |= *digit != 0;
211            num_digts += digit_encounterd as usize;
212        }
213        num_digts
214    }
215
216    /// Returns `self + rhs`, wrapping on overflow.
217    ///
218    /// If overflow occurs, it wraps around.
219    ///
220    /// # Examples
221    /// ```
222    /// use crylib::big_int::UBigInt;
223    ///
224    /// assert_eq!(UBigInt::<4>::ZERO.add(&UBigInt::ONE), UBigInt::ONE);
225    /// assert_eq!(UBigInt::<4>::MAX.add(&UBigInt::ONE), UBigInt::ZERO);
226    /// ```
227    ///
228    /// # Constant-timedness
229    /// This is a constant-time operation.
230    pub fn add(&self, rhs: &Self) -> Self {
231        let mut buf = *self;
232        buf.add_assign(rhs);
233        buf
234    }
235
236    /// Sets `self` to `self + rhs`, wrapping on overflow.
237    ///
238    /// # Examples
239    /// ```
240    /// use crylib::big_int::UBigInt;
241    /// let mut zero: UBigInt<4> = UBigInt::ZERO;
242    /// let mut max: UBigInt<4> = UBigInt::MAX;
243    ///
244    /// zero.add_assign(&UBigInt::ONE);
245    /// max.add_assign(&UBigInt::ONE);
246    ///
247    /// assert_eq!(zero, UBigInt::ONE);
248    /// assert_eq!(max, UBigInt::ZERO);
249    /// ```
250    ///
251    /// # Constant-timedness
252    /// This is a constant-time operation.
253    pub fn add_assign(&mut self, rhs: &Self) {
254        let mut carry = false;
255        for i in 0..N {
256            // TODO: use core implementation once stabilized
257            (self.0[i], carry) = super::carry_add(self.0[i], rhs.0[i], carry);
258        }
259    }
260
261    pub fn double(&self) -> Self {
262        self.add(self)
263    }
264
265    pub fn double_assign(&mut self) {
266        let mut carry = false;
267        for i in 0..N {
268            // TODO: use core implementation once stabilized
269            (self.0[i], carry) = super::carry_add(self.0[i], self.0[i], carry);
270        }
271    }
272
273    /// Sets `self` to `self * digit`, wrapping on overflow.
274    ///
275    /// # Constant-timedness
276    /// This is a constant-time operation.
277    pub fn mul_digit_assign(&mut self, digit: u64) {
278        let mut carry = 0;
279        for i in self.0.iter_mut() {
280            (*i, carry) = carry_mul(*i, digit, carry);
281        }
282    }
283
284    /// Returns `self * digit`, wrapping on overflow.
285    pub fn mul_digit(&self, digit: u64) -> Self {
286        let mut buf = *self;
287        buf.mul_digit_assign(digit);
288        buf
289    }
290
291    pub fn overflowing_mul_digit(&self, digit: u64) -> (Self, u64) {
292        let mut buf = *self;
293        let overflow = buf.overflowing_mul_digit_assign(digit);
294        (buf, overflow)
295    }
296
297    pub fn overflowing_mul_digit_assign(&mut self, digit: u64) -> u64 {
298        let mut carry = 0;
299        for i in self.0.iter_mut() {
300            (*i, carry) = carry_mul(*i, digit, carry);
301        }
302        carry
303    }
304
305    /// Returns `self - rhs`, wrapping on overflow.
306    ///
307    /// # Examples
308    /// ```
309    /// use crylib::big_int::UBigInt;
310    ///
311    /// assert_eq!(UBigInt::<4>::ONE.sub(&UBigInt::ONE), UBigInt::ZERO);
312    /// assert_eq!(UBigInt::<4>::ZERO.sub(&UBigInt::ONE), UBigInt::MAX);
313    /// ```
314    ///
315    /// # Constant-timedness
316    /// This is a constant-time operation
317    pub fn sub(&self, rhs: &Self) -> Self {
318        let mut buf = *self;
319        buf.sub_assign(rhs);
320        buf
321    }
322
323    /// Sets `self` to `self - rhs`, wrapping on overflow.
324    ///
325    /// # Examples
326    /// ```
327    /// use crylib::big_int::UBigInt;
328    /// let mut one: UBigInt<4> = UBigInt::ONE;
329    /// let mut zero: UBigInt<4> = UBigInt::ZERO;
330    ///
331    /// one.sub_assign(&UBigInt::ONE);
332    /// zero.sub_assign(&UBigInt::ONE);
333    ///
334    /// assert_eq!(one, UBigInt::ZERO);
335    /// assert_eq!(zero, UBigInt::MAX);
336    /// ```
337    ///
338    /// # Constant-timedness
339    /// This is a constant-time operation
340    pub fn sub_assign(&mut self, rhs: &Self) {
341        let mut carry = false;
342        for i in 0..N {
343            // TODO: use libcore implementation once stabilized
344            (self.0[i], carry) = super::carry_sub(self.0[i], rhs.0[i], carry);
345        }
346    }
347
348    /// Returns `self` if `rhs` is `true`, otherwise `Self::ZERO`.
349    ///
350    /// # Constant-timedness
351    /// This is a constant-time operation.
352    pub fn and_bool(&self, rhs: bool) -> Self {
353        let mut buf = *self;
354        buf.and_bool_assign(rhs);
355        buf
356    }
357
358    /// reasigns `self` to equal `self` if `rhs` is `true`, otherwise `Self::ZERO`.
359    ///
360    /// # Constant-timedness
361    /// This is a constant-time operation.
362    pub fn and_bool_assign(&mut self, rhs: bool) {
363        let mask = (rhs as u64).wrapping_neg();
364        for digit in self.0.iter_mut() {
365            *digit &= mask
366        }
367    }
368
369    /// Shifts `self` to the left until the most significant bit is on.
370    ///
371    /// This function does not align leading 0-digits; it only considers the ones after the last
372    /// leading `0`.
373    ///
374    /// # Constant-timedness
375    /// This is a constant-time operation.
376    pub fn left_align(&mut self) -> u64 {
377        let num_digits = self.count_digits();
378        assert_ne!(num_digits, 0);
379        let left_shift = self.0[num_digits - 1].leading_zeros() as u64;
380        self.shift_left_assign(left_shift);
381        left_shift
382    }
383
384    /// Performs a bitshift `rhs % 64` to the right and stores the result in `self`.
385    ///
386    /// # Constant-timedness
387    /// This is a constant-time operation.
388    pub fn shift_right_assign(&mut self, mut rhs: u64) {
389        rhs %= 64;
390        let left_shift = (64 - rhs) % 64;
391        let mask = ((rhs != 0) as u64).wrapping_neg();
392
393        for i in 0..N - 1 {
394            self.0[i] >>= rhs;
395            self.0[i] |= (self.0[i + 1] << left_shift) & mask;
396        }
397        self.0[N - 1] >>= rhs;
398    }
399
400    /// Performs a bitshift `rhs % 64` to the right and returns the result.
401    ///
402    /// # Constant-timedness
403    /// This is a constant-time operation.
404    pub fn shift_right(&self, rhs: u64) -> Self {
405        let mut buf = *self;
406        buf.shift_right_assign(rhs);
407        buf
408    }
409
410    /// Performs a bitshift `rhs % 64` to the left and stores the result in `self`.
411    ///
412    /// # Constant-timedness
413    /// This is a constant-time operation.
414    pub fn shift_left_assign(&mut self, mut rhs: u64) {
415        rhs %= 64;
416        let right_shift = (64 - rhs) % 64;
417        let mask = ((rhs != 0) as u64).wrapping_neg();
418
419        for i in (1..N).rev() {
420            self.0[i] <<= rhs;
421            self.0[i] |= (self.0[i - 1] >> right_shift) & mask;
422        }
423        self.0[0] <<= rhs;
424    }
425
426    /// Performs a bitshift `rhs` to the right and returns the result.
427    ///
428    /// # Constant-timedness
429    /// This is a constant-time operation.
430    pub fn shift_left(&self, rhs: u64) -> Self {
431        let mut buf = *self;
432        buf.shift_left_assign(rhs);
433        buf
434    }
435
436    /// Converts `self` into its one's compliment.
437    ///
438    /// # Constant-timedness
439    /// This is a constant-time operation.
440    pub fn not_assign(&mut self) {
441        for digit in self.0.iter_mut() {
442            *digit = !*digit
443        }
444    }
445
446    /// Returns the one's compliment of `self`
447    ///
448    /// # Constant-timedness
449    /// This is a constant-time operation.
450    pub fn not(&self) -> Self {
451        let mut buf = *self;
452        buf.not_assign();
453        buf
454    }
455
456    /// Performs a bitwise `XOR` on `self` and `rhs` and stores the result in `self`.
457    ///
458    /// # Constant-timedness
459    /// This is a constant-time operation.
460    pub fn xor_assign(&mut self, rhs: &Self) {
461        for (digit, rhs_digit) in self.0.iter_mut().zip(rhs.0) {
462            *digit ^= rhs_digit;
463        }
464    }
465
466    /// Performs a bitwise `XOR` on `self` and `rhs` and returns the result.
467    ///
468    /// # Constant-timedness
469    /// This is a constant-time operation.
470    pub fn xor(&self, rhs: &Self) -> Self {
471        let mut buf = *self;
472        buf.xor_assign(rhs);
473        buf
474    }
475
476    /// Performs a bitwise `AND` on `self` and `rhs` and stores the result in `self`.
477    ///
478    /// # Constant-timedness
479    /// This is a constant-time operation.
480    pub fn and_assign(&mut self, rhs: &Self) {
481        for (digit, rhs_digit) in self.0.iter_mut().zip(rhs.0) {
482            *digit &= rhs_digit;
483        }
484    }
485
486    /// Performs a bitwise `AND` on `self` and `rhs` and returns the result.
487    ///
488    /// # Constant-timedness
489    /// This is a constant-time operation.
490    pub fn and(&self, rhs: &Self) -> Self {
491        let mut buf = *self;
492        buf.and_assign(rhs);
493        buf
494    }
495
496    /// Performs a bitwise `OR` on `self` and `rhs` and stores the result in `self`.
497    ///
498    /// # Constant-timedness
499    /// This is a constant-time operation.
500    pub fn or_assign(&mut self, rhs: &Self) {
501        for (digit, rhs_digit) in self.0.iter_mut().zip(rhs.0) {
502            *digit |= rhs_digit;
503        }
504    }
505
506    /// Performs a bitwise `OR` on `self` and `rhs` and returns the result.
507    ///
508    /// # Constant-timedness
509    /// This is a constant-time operation.
510    pub fn or(&self, rhs: &Self) -> Self {
511        let mut buf = *self;
512        buf.or_assign(rhs);
513        buf
514    }
515
516    /// Performs a bitwise `NOR` on `self` and `rhs` and stores the result in `self`.
517    ///
518    /// # Constant-timedness
519    /// This is a constant-time operation.
520    pub fn nor_assign(&mut self, rhs: &Self) {
521        for (digit, rhs_digit) in self.0.iter_mut().zip(rhs.0) {
522            *digit = !(*digit | rhs_digit);
523        }
524    }
525
526    /// Performs a bitwise `NOR` on `self` and `rhs` and returns the result.
527    ///
528    /// # Constant-timedness
529    /// This is a constant-time operation.
530    pub fn nor(&self, rhs: &Self) -> Self {
531        let mut buf = *self;
532        buf.nor_assign(rhs);
533        buf
534    }
535
536    /// Performs a bitwise `XNOR` on `self` and `rhs` and stores the result in `self`.
537    ///
538    /// # Constant-timedness
539    /// This is a constant-time operation.
540    pub fn xnor_assign(&mut self, rhs: &Self) {
541        for (digit, rhs_digit) in self.0.iter_mut().zip(rhs.0) {
542            *digit = !(*digit ^ rhs_digit);
543        }
544    }
545
546    /// Performs a bitwise `XNOR` on `self` and `rhs` and returns the result.
547    ///
548    /// # Constant-timedness
549    /// This is a constant-time operation.
550    pub fn xnor(&self, rhs: &Self) -> Self {
551        let mut buf = *self;
552        buf.xnor_assign(rhs);
553        buf
554    }
555
556    /// Performs a bitwise `NAND` on `self` and `rhs` and stores the result in `self`.
557    ///
558    /// # Constant-timedness
559    /// This is a constant-time operation.
560    pub fn nand_assign(&mut self, rhs: &Self) {
561        for (digit, rhs_digit) in self.0.iter_mut().zip(rhs.0) {
562            *digit = !(*digit & rhs_digit);
563        }
564    }
565
566    /// Performs a bitwise `NAND` on `self` and `rhs` and returns the result.
567    ///
568    /// # Constant-timedness
569    /// This is a constant-time operation.
570    pub fn nand(&self, rhs: &Self) -> Self {
571        let mut buf = *self;
572        buf.nand_assign(rhs);
573        buf
574    }
575
576    /// Returns the number of digits `self` can store.
577    ///
578    /// # Examples
579    /// ```
580    /// use crylib::big_int::UBigInt;
581    ///
582    /// assert_eq!(UBigInt::<4>::ZERO.len(), 4);
583    /// assert_eq!(UBigInt::<3>::MAX.len(), 3);
584    /// ```
585    ///
586    /// # Constant-timedness
587    /// This is a constant-time operation.
588    #[allow(clippy::len_without_is_empty)]
589    pub const fn len(&self) -> usize {
590        self.0.len()
591    }
592
593    /// Resizes a `UBigInt<N>` to a `UBigInt<O>`, truncating most significant bits if necessary.
594    pub fn resize<const O: usize>(self) -> UBigInt<O> {
595        let min = core::cmp::min(O, N);
596        let mut new = UBigInt([0; O]);
597        new.0[..min].copy_from_slice(&self.0[..min]);
598        new
599    }
600
601    pub const fn get_bit(&self, bit: usize) -> bool {
602        assert!(bit < u64::BITS as usize * N);
603        self.0[bit / (u64::BITS as usize)] & 1 << (bit % (u64::BITS as usize)) != 0
604    }
605
606    pub fn set_bit(&mut self, bit: usize, value: bool) {
607        let digit = bit / (u64::BITS) as usize;
608        assert!(digit < N);
609        let bit = bit % u64::BITS as usize;
610
611        // turn bit off
612        self.0[digit] &= !(1 << bit);
613
614        // set bit to value
615        self.0[digit] |= (value as u64) << bit;
616    }
617
618    pub fn set_byte(&mut self, byte: usize, value: u8) {
619        let digit = byte / size_of::<u64>();
620        assert!(digit < N);
621        let byte = byte % size_of::<u64>() * u8::BITS as usize;
622
623        // turn bit off
624        self.0[digit] &= !(0xff << byte);
625
626        // set bit to value
627        self.0[digit] |= (value as u64) << byte;
628    }
629
630    /// Counts the number of significant bits in `self`.
631    ///
632    /// This is the same as `floor(log2(self))`
633    pub fn count_bits(&self) -> usize {
634        let num_ditis = self.count_digits().saturating_sub(1);
635        let bits = u64::BITS as usize - self.0[num_ditis].leading_zeros() as usize;
636        num_ditis * u64::BITS as usize + bits
637    }
638}
639
640// credits: this function was borrowed from OpenSSL's `bn_div_3_words`.
641// TODO: figure out what this does to see if it can be simplified
642fn partial_div(m0: u64, m1: u64, d1: u64, d0: u64) -> u64 {
643    let mut r = ((m0 as u128) << 64) | m1 as u128;
644    let mut d = ((d0 as u128) << 64) | d1 as u128;
645    let mut q: u64 = 0;
646
647    for _ in 0..64 {
648        q <<= 1;
649        if r >= d {
650            q |= 1;
651            r -= d;
652        }
653        d >>= 1;
654    }
655
656    let mask = (q >> (64 - 1)).wrapping_neg();
657
658    q <<= 1;
659    q |= (r >= d) as u64;
660
661    q | mask
662}
663
664macro_rules! impl_non_generic {
665    ($n:literal) => {
666        impl UBigInt<$n> {
667            const _POSITIVE_N: () = assert!($n > 0);
668            /// Calculates `self * rhs`, widening the output to avoid overflow.
669            ///
670            /// # Constant-timedness
671            /// This is a constant-time operation.
672            pub fn widening_mul(&self, rhs: &Self) -> UBigInt<{ $n * 2 }> {
673                let mut product = [0u64; $n * 2];
674                for i in 0..self.len() {
675                    let mut carry = 0;
676                    for j in 0..rhs.len() {
677                        // TODO: use libcore carry_mul once stabilized
678                        let partial_product;
679                        (partial_product, carry) = super::carry_mul(self.0[i], rhs.0[j], carry);
680                        let (sum, overflowed) = product[i + j].overflowing_add(partial_product);
681                        product[i + j] = sum;
682                        carry += overflowed as u64;
683                    }
684                    product[i + rhs.len()] = carry;
685                }
686                product.into()
687            }
688
689            /// Left-shifts `self` by `rhs % 64` bits.
690            ///
691            /// The output is 64 bits longer, so ovelflow never occurs.
692            ///
693            /// # Constant-timedness
694            /// This is a constant-time operation.
695            pub fn widening_shift_left(&self, mut rhs: u64) -> UBigInt<{ $n + 1 }> {
696                rhs %= 64;
697                let mut expanded = [0u64; $n + 1];
698                let right_shift = (64 - rhs) % 64;
699                let mask = ((rhs != 0) as u64).wrapping_neg();
700
701                expanded[$n] = self.0[$n - 1] >> right_shift & mask;
702                for i in (1..$n).rev() {
703                    expanded[i] = self.0[i] << rhs;
704                    expanded[i] |= (self.0[i - 1] >> right_shift) & mask;
705                }
706                expanded[0] = self.0[0] << rhs;
707                expanded.into()
708            }
709
710            /// Calculates `self / rhs`, returning the quotient and the remainder.
711            ///
712            /// # Panics
713            /// This function will panic if `divisor` equals `Self::ZERO`.
714            ///
715            /// # Constant-timedness
716            /// TODO: document constant-timedness
717            // credits: this function is a modified version of OpenSSL's `bn_div_fixed_top`.
718            pub fn div(&self, rhs: &Self) -> (Self, Self) {
719                // This is a modified version of OpenSSL's `BN_div` which was originally written in C.
720
721                assert_ne!(*rhs, Self::ZERO);
722
723                let num_len = self.count_digits() + 1;
724                let div_len = rhs.count_digits();
725
726                // Normalize both numerator and denominator
727                let norm_shift;
728                let sdiv = {
729                    let mut sdiv = *rhs;
730                    norm_shift = sdiv.left_align();
731                    sdiv
732                };
733                let mut snum = self.widening_shift_left(norm_shift);
734
735                // `div_n` is guaranteed to be at least 1
736                let d0 = sdiv.0[div_len - 1];
737                let d1 = match div_len {
738                    0 => unreachable!(),
739                    1 => 0,
740                    _ => sdiv.0[div_len - 2],
741                };
742
743                let num_loops = num_len.saturating_sub(div_len);
744
745                let mut quotient = Self::ZERO;
746                let mut quotient_pos = num_loops;
747
748                for (win_bot, win_top) in (0..num_loops).zip(num_len - num_loops..num_len).rev() {
749                    let mut temp = UBigInt::<{ $n + 1 }>::ZERO;
750                    let mut partial_quotient =
751                        partial_div(snum.0[win_top], snum.0[win_top - 1], d1, d0);
752
753                    // multiply `sdiv` by `partial_quotient`
754                    let mut mul_carry = 0;
755                    for i in 0..div_len {
756                        (temp.0[i], mul_carry) =
757                            super::carry_mul(sdiv.0[i], partial_quotient, mul_carry);
758                    }
759                    temp.0[div_len] = mul_carry;
760
761                    // subtract result from `snum`
762                    let mut sub_carry = false;
763                    for i in 0..div_len + 1 {
764                        (snum.0[win_bot + i], sub_carry) =
765                            super::carry_sub(snum.0[win_bot + i], temp.0[i], sub_carry);
766                    }
767
768                    partial_quotient -= sub_carry as u64;
769
770                    // add back if overflow occured
771                    let mask = (sub_carry as u64).wrapping_neg();
772                    let mut add_carry = false;
773                    for i in 0..div_len {
774                        (snum.0[win_bot + i], add_carry) =
775                            super::carry_add(snum.0[win_bot + i], sdiv.0[i] & mask, add_carry);
776                    }
777                    snum.0[win_top] = snum.0[win_top].wrapping_add(add_carry as u64);
778                    debug_assert!(snum.0[win_top] == 0);
779
780                    quotient_pos -= 1;
781                    quotient.0[quotient_pos] = partial_quotient;
782                }
783                // Un-normalize remainder
784                snum.shift_right_assign(norm_shift);
785                // we can safely unwrap because because `snum.len()` is 5
786                (quotient, snum.0[..$n].try_into().unwrap())
787            }
788
789            /// Divides `self` by `rhs` and stores the result in `self`
790            pub fn div_assign(&mut self, rhs: &Self) {
791                *self = self.div(rhs).0;
792            }
793
794            /// converts a big-endian byte array to a [`UBigInt`]
795            // TODO: implement this for all values of `N` once const_generic operations are stabilized
796            pub fn from_be_bytes(bytes: [u8; $n * size_of::<u64>()]) -> Self {
797                // TODO: consider using uninitialized array
798                let mut output = [0; $n];
799                // TODO: use array_chunks once stabilized
800                for (chunk, digit) in bytes.rchunks_exact(size_of::<u64>()).zip(output.iter_mut()) {
801                    *digit = u64::from_be_bytes(chunk.try_into().unwrap())
802                }
803                output.into()
804            }
805
806            /// converts a big-endian byte array to a [`UBigInt`]
807            // TODO: implement this for all values of `N` once const_generic operations are stabilized
808            pub fn from_le_bytes(bytes: [u8; $n * size_of::<u64>()]) -> Self {
809                // TODO: consider using uninitialized array
810                let mut output = [0; $n];
811                // TODO: use array_chunks once stabilized
812                for (chunk, digit) in bytes.chunks_exact(size_of::<u64>()).zip(output.iter_mut()) {
813                    *digit = u64::from_le_bytes(chunk.try_into().unwrap())
814                }
815                output.into()
816            }
817
818            pub fn to_be_bytes(self) -> [u8; $n * size_of::<u64>()] {
819                let mut output = [0; $n * size_of::<u64>()];
820                for (digit, chunk) in self
821                    .0
822                    .into_iter()
823                    .zip(output.chunks_exact_mut(size_of::<u64>()).rev())
824                {
825                    chunk.copy_from_slice(&digit.to_be_bytes());
826                }
827                output
828            }
829
830            pub fn to_le_bytes(self) -> [u8; $n * size_of::<u64>()] {
831                let mut output = [0; $n * size_of::<u64>()];
832                for (digit, chunk) in self
833                    .0
834                    .into_iter()
835                    .zip(output.chunks_exact_mut(size_of::<u64>()))
836                {
837                    chunk.copy_from_slice(&digit.to_le_bytes());
838                }
839                output
840            }
841        }
842    };
843}
844
845impl_non_generic!(2);
846impl_non_generic!(3);
847impl_non_generic!(4);
848impl_non_generic!(8);
849impl_non_generic!(5);
850impl_non_generic!(6);
851
852impl<const N: usize> Ord for UBigInt<N> {
853    // TODO: make this constant-time?
854    fn cmp(&self, other: &Self) -> Ordering {
855        let overflowed = self.overflowing_sub(other).1;
856
857        if overflowed {
858            return Ordering::Less;
859        }
860
861        if self.0 == other.0 {
862            return Ordering::Equal;
863        }
864        Ordering::Greater
865    }
866}
867
868impl<const N: usize> PartialOrd for UBigInt<N> {
869    fn lt(&self, other: &Self) -> bool {
870        self.overflowing_sub(other).1
871    }
872
873    fn le(&self, other: &Self) -> bool {
874        !self.gt(other)
875    }
876
877    fn gt(&self, other: &Self) -> bool {
878        other.overflowing_sub(self).1
879    }
880
881    fn ge(&self, other: &Self) -> bool {
882        !self.lt(other)
883    }
884
885    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
886        Some(self.cmp(other))
887    }
888}
889
890impl<const N: usize> From<[u64; N]> for UBigInt<N> {
891    fn from(value: [u64; N]) -> Self {
892        Self(value)
893    }
894}
895
896impl<const N: usize> From<UBigInt<N>> for [u64; N] {
897    fn from(value: UBigInt<N>) -> Self {
898        value.0
899    }
900}
901
902impl<const N: usize> From<u64> for UBigInt<N> {
903    fn from(value: u64) -> Self {
904        let mut big_int = [0u64; N];
905        big_int[0] = value;
906        big_int.into()
907    }
908}
909
910impl<const N: usize> Default for UBigInt<N> {
911    fn default() -> Self {
912        Self::ZERO
913    }
914}
915
916impl<const N: usize> TryFrom<&[u64]> for UBigInt<N> {
917    type Error = core::array::TryFromSliceError;
918    fn try_from(value: &[u64]) -> Result<Self, Self::Error> {
919        Ok(Self(<[u64; N]>::try_from(value)?))
920    }
921}
922
923impl<const N: usize> TryFrom<BigInt<N>> for UBigInt<N> {
924    type Error = FromNegErr;
925    fn try_from(value: BigInt<N>) -> Result<Self, Self::Error> {
926        if value.is_negative() {
927            return Err(FromNegErr);
928        };
929        Ok(value.digits)
930    }
931}
932
933impl<const N: usize> AsRef<[u64; N]> for UBigInt<N> {
934    fn as_ref(&self) -> &[u64; N] {
935        &self.0
936    }
937}
938
939impl<const N: usize> AsMut<[u64; N]> for UBigInt<N> {
940    fn as_mut(&mut self) -> &mut [u64; N] {
941        &mut self.0
942    }
943}
944
945impl<const N: usize> AsRef<UBigInt<N>> for [u64; N] {
946    fn as_ref(&self) -> &UBigInt<N> {
947        todo!()
948    }
949}
950
951impl<const N: usize> AsMut<UBigInt<N>> for [u64; N] {
952    fn as_mut(&mut self) -> &mut UBigInt<N> {
953        UBigInt::from_ref_mut(self)
954    }
955}
956
957#[cfg(test)]
958mod tests {
959
960    use super::UBigInt;
961
962    #[test]
963    fn add() {
964        let x = UBigInt([
965            0xfedcba9876543210,
966            0x0123456789abcdef,
967            0xfedcba9876543210,
968            0x0123456789abcdef,
969        ]);
970        let y = UBigInt([
971            0x0123456789abcdef,
972            0xfedcba9876543210,
973            0x0123456789abcdef,
974            0xfedcba9876543210,
975        ]);
976        assert_eq!(x.add(&y), UBigInt::MAX);
977
978        let x = UBigInt([
979            0xfedcba9876543211,
980            0x0123456789abcdef,
981            0xfedcba9876543210,
982            0x0123456789abcdef,
983        ]);
984        assert_eq!(x.add(&y), UBigInt::ZERO);
985    }
986
987    #[test]
988    fn sub() {
989        let x = UBigInt([
990            0xfedcba9876543210,
991            0x0123456789abcdef,
992            0xfedcba9876543210,
993            0x0123456789abcdef,
994        ]);
995        let y = UBigInt([
996            0x0123456789abcdef,
997            0xfedcba9876543210,
998            0x0123456789abcdef,
999            0xfedcba9876543210,
1000        ]);
1001        assert_eq!(UBigInt::MAX.sub(&x), y);
1002
1003        let x = UBigInt([
1004            0xfedcba9876543211,
1005            0x0123456789abcdef,
1006            0xfedcba9876543210,
1007            0x0123456789abcdef,
1008        ]);
1009        assert_eq!(UBigInt::ZERO.sub(&y), x);
1010    }
1011
1012    #[test]
1013    fn widening_mul() {
1014        let x = UBigInt([
1015            0x0000000000000000,
1016            0x0000000000000000,
1017            0x0000000000000000,
1018            0x1000000000000000,
1019        ]);
1020        let y = UBigInt([
1021            0x0000000000000000,
1022            0x0000000000000000,
1023            0x0000000000010000,
1024            0x0000000000000000,
1025        ]);
1026        let product = UBigInt([
1027            0x0000000000000000,
1028            0x0000000000000000,
1029            0x0000000000000000,
1030            0x0000000000000000,
1031            0x0000000000000000,
1032            0x0000000000000000,
1033            0x0000000000001000,
1034            0x0000000000000000,
1035        ]);
1036        assert_eq!(x.widening_mul(&y), product);
1037
1038        let y = UBigInt([
1039            0xfedcba9876543211,
1040            0x0123456789abcdef,
1041            0xfedcba9876543210,
1042            0x0123456789abcdef,
1043        ]);
1044        assert_eq!(y.widening_mul(&UBigInt::ONE), y.resize());
1045        let a = UBigInt([0x124924924924924, 0, 0, 0]);
1046        let b = UBigInt([
1047            0xfedcba9876543210,
1048            0x0123456789abcdef,
1049            0xfedcba9876543210,
1050            0x0000000000000000,
1051        ]);
1052        // TODO: make this hex
1053        let product = UBigInt([
1054            0x80a670cd733d9a40,
1055            0x7f584250f1dbea8b,
1056            0x80a7bdaf0e241574,
1057            81985529216486895,
1058        ]);
1059        assert_eq!(a.widening_mul(&b).resize(), product);
1060    }
1061
1062    #[test]
1063    fn div() {
1064        let y = UBigInt([
1065            0x0123456789abcdef,
1066            0xfedcba9876543210,
1067            0x0123456789abcdef,
1068            0xfedcba9876543210,
1069        ]);
1070        assert_eq!(y.div(&y), (UBigInt::ONE, UBigInt::ZERO));
1071
1072        let x = UBigInt([0, 1, 0, 0]);
1073        let quotient = UBigInt([
1074            0xfedcba9876543210,
1075            0x0123456789abcdef,
1076            0xfedcba9876543210,
1077            0x0000000000000000,
1078        ]);
1079        let remainder = UBigInt([0x0123456789abcdef, 0, 0, 0]);
1080        assert_eq!(y.div(&x), (quotient, remainder));
1081
1082        assert_eq!(quotient.div(&y), (UBigInt::ZERO, quotient));
1083
1084        let a = UBigInt([
1085            0xfedcba9876543210,
1086            0x0123456789abcdef,
1087            0xfedcba9876543210,
1088            0x0123456789abcdef,
1089        ]);
1090        let b = UBigInt([
1091            0xfedcba9876543210,
1092            0x0123456789abcdef,
1093            0xfedcba9876543210,
1094            0x0000000000000000,
1095        ]);
1096        let quotient = UBigInt([0x124924924924924, 0, 0, 0]);
1097        let remainder = UBigInt([
1098            0x7e3649cb031697d0,
1099            0x81cb031697cfe364,
1100            0x7e34fce968301c9b,
1101            0x0000000000000000,
1102        ]);
1103        assert_eq!(a.div(&b), (quotient, remainder));
1104    }
1105
1106    #[test]
1107    fn widening_shift_left() {
1108        let x = UBigInt([
1109            0x0123456789abcdef,
1110            0xfedcba9876543210,
1111            0x0123456789abcdef,
1112            0xfedcba9876543210,
1113        ]);
1114        let shifted = UBigInt([
1115            0x3456789abcdef000,
1116            0xcba9876543210012,
1117            0x3456789abcdeffed,
1118            0xcba9876543210012,
1119            0x0000000000000fed,
1120        ]);
1121        assert_eq!(x.widening_shift_left(12), shifted);
1122
1123        let mut widened_x = UBigInt::ZERO;
1124        widened_x.0[..x.len()].copy_from_slice(&x.0[..]);
1125        assert_eq!(x.widening_shift_left(0), widened_x);
1126    }
1127
1128    #[test]
1129    fn left_align() {
1130        let mut x = UBigInt([
1131            0xfedcba9876543210,
1132            0x0123456789abcdef,
1133            0xfedcba9876543210,
1134            0x0823456789abcdef,
1135        ]);
1136        let shift_amount = x.left_align();
1137        let aligned = UBigInt([
1138            0xedcba98765432100,
1139            0x123456789abcdeff,
1140            0xedcba98765432100,
1141            0x823456789abcdeff,
1142        ]);
1143        assert_eq!(x, aligned);
1144        assert_eq!(shift_amount, 4);
1145    }
1146
1147    #[test]
1148    fn count_digits_fast() {
1149        let x = UBigInt([
1150            0x0123456789abcdef,
1151            0xfedcba9876543210,
1152            0x0123456789abcdef,
1153            0xfedcba9876543210,
1154        ]);
1155        assert_eq!(x.count_digits_fast(), 4);
1156
1157        let y = UBigInt([
1158            0x0123456789abcdef,
1159            0xfedcba9876543210,
1160            0x0000000000000000,
1161            0xfedcba9876543210,
1162        ]);
1163        assert_eq!(y.count_digits_fast(), 4);
1164
1165        let z = UBigInt([
1166            0x0123456789abcdef,
1167            0xfedcba9876543210,
1168            0x0123456789abcdef,
1169            0x0000000000000000,
1170        ]);
1171        assert_eq!(z.count_digits_fast(), 3);
1172        assert_eq!(UBigInt::<4>::ZERO.count_digits_fast(), 0);
1173    }
1174
1175    #[test]
1176    fn count_digits() {
1177        let x = UBigInt([
1178            0x0123456789abcdef,
1179            0xfedcba9876543210,
1180            0x0123456789abcdef,
1181            0xfedcba9876543210,
1182        ]);
1183        assert_eq!(x.count_digits(), 4);
1184
1185        let y = UBigInt([
1186            0x0123456789abcdef,
1187            0xfedcba9876543210,
1188            0x0000000000000000,
1189            0xfedcba9876543210,
1190        ]);
1191        assert_eq!(y.count_digits(), 4);
1192
1193        let z = UBigInt([
1194            0x0123456789abcdef,
1195            0xfedcba9876543210,
1196            0x0123456789abcdef,
1197            0x0000000000000000,
1198        ]);
1199        assert_eq!(z.count_digits(), 3);
1200        assert_eq!(UBigInt::<4>::ZERO.count_digits(), 0);
1201    }
1202
1203    #[test]
1204    fn get_bit() {
1205        let z = UBigInt([
1206            0x0000000000000000,
1207            0x0123456789abcdef,
1208            0xfedcba9876543210,
1209            0x0123456789abcdef,
1210        ]);
1211        assert!(!z.get_bit(0));
1212        assert!(z.get_bit(64));
1213        assert!(z.get_bit(248));
1214        assert!(!z.get_bit(255));
1215    }
1216
1217    #[test]
1218    fn count_bits() {
1219        let z = UBigInt([
1220            0x0000000000000000,
1221            0x0123456789abcdef,
1222            0x0000000000000000,
1223            0xf123456789abcdef,
1224        ]);
1225        assert_eq!(z.count_bits(), 256);
1226        let x = UBigInt([
1227            0x0123456789abcdef,
1228            0xfedcba9876543210,
1229            0x0123456789abcdef,
1230            0x0000000000000000,
1231        ]);
1232        assert_eq!(x.count_bits(), 185);
1233
1234        assert_eq!(UBigInt::<4>::ZERO.count_bits(), 0);
1235        assert_eq!(UBigInt::<4>::ONE.count_bits(), 1);
1236    }
1237
1238    #[test]
1239    fn from_le_bytes() {
1240        let bytes = [
1241            0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e,
1242            0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c,
1243            0x1d, 0x1e, 0x1f, 0x20,
1244        ];
1245        let num = UBigInt([
1246            0x0807060504030201,
1247            0x100f0e0d0c0b0a09,
1248            0x1817161514131211,
1249            0x201f1e1d1c1b1a19,
1250        ]);
1251        assert_eq!(UBigInt::<4>::from_le_bytes(bytes), num);
1252    }
1253
1254    #[test]
1255    fn to_le_bytes() {
1256        let num = UBigInt([
1257            0x0807060504030201,
1258            0x100f0e0d0c0b0a09,
1259            0x1817161514131211,
1260            0x201f1e1d1c1b1a19,
1261        ]);
1262        let bytes = [
1263            0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e,
1264            0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c,
1265            0x1d, 0x1e, 0x1f, 0x20,
1266        ];
1267        assert_eq!(num.to_le_bytes(), bytes);
1268    }
1269}
crylib/big_int/unsigned.rs

crylib/big_int/
unsigned.rs
