crylib/big_int/
unsigned.rs

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

crylib/big_int/
unsigned.rs
