bnum/buint/
bigint_helpers.rs

1use crate::digit;
2use crate::doc;
3
4macro_rules! bigint_helpers {
5    ($BUint: ident, $BInt: ident, $Digit: ident) => {
6        #[doc = doc::bigint_helpers::impl_desc!()]
7        impl<const N: usize> $BUint<N> {
8            crate::int::bigint_helpers::impls!(U);
9
10            #[doc = doc::bigint_helpers::widening_mul!(U)]
11            #[must_use = doc::must_use_op!()]
12            #[inline]
13            pub const fn widening_mul(self, rhs: Self) -> (Self, Self) {
14                let mut low = Self::ZERO;
15                let mut high = Self::ZERO;
16                let mut carry: $Digit;
17
18                let mut i = 0;
19                while i < N {
20                    carry = 0;
21                    let mut j = 0;
22                    while j < N - i {
23                        let index = i + j;
24                        let d = low.digits[index];
25                        let (new_digit, new_carry) =
26                            digit::$Digit::carrying_mul(self.digits[i], rhs.digits[j], carry, d);
27                        carry = new_carry;
28                        low.digits[index] = new_digit;
29                        j += 1;
30                    }
31                    while j < N {
32                        let index = i + j - N;
33                        let d = high.digits[index];
34                        let (new_digit, new_carry) =
35                            digit::$Digit::carrying_mul(self.digits[i], rhs.digits[j], carry, d);
36                        carry = new_carry;
37                        high.digits[index] = new_digit;
38                        j += 1;
39                    }
40                    high.digits[i] = carry;
41                    i += 1;
42                }
43
44                (low, high)
45            }
46
47            #[doc = doc::bigint_helpers::carrying_mul!(U)]
48            #[must_use = doc::must_use_op!()]
49            #[inline]
50            pub const fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self) {
51                let (low, high) = self.widening_mul(rhs);
52                let (low, overflow) = low.overflowing_add(carry);
53                if overflow {
54                    (low, high.wrapping_add(Self::ONE))
55                } else {
56                    (low, high)
57                }
58            }
59        }
60    };
61}
62
63#[cfg(test)]
64crate::test::all_digit_tests! {
65    crate::int::bigint_helpers::tests!(utest);
66
67    #[cfg(test_int_bits = "64")]
68    test_bignum! {
69        function: <utest>::widening_mul(a: utest, b: utest),
70        cases: [
71            (utest::MAX, utest::MAX)
72        ]
73    }
74
75    #[cfg(test_int_bits = "64")]
76    test_bignum! {
77        function: <utest>::carrying_mul(a: utest, b: utest, c: utest),
78        cases: [
79            (utest::MAX, utest::MAX, utest::MAX),
80            (utest::MAX, utest::MAX, 1 as utest)
81        ]
82    }
83}
84
85crate::macro_impl!(bigint_helpers);
bnum/buint/bigint_helpers.rs

bnum/buint/
bigint_helpers.rs
