crypto_bigint/uint/ref_type/
mul.rs

1//! Multiplication support for [`UintRef`].
2
3use crate::{Choice, Limb, UintRef, uint::mul::karatsuba};
4
5impl UintRef {
6    /// Compute the wrapping product of `self` and `rhs`, placing the result into `out`
7    /// and returning a `Choice` indicating whether overflow occurred.
8    #[inline(always)]
9    pub fn overflowing_mul(&self, rhs: &UintRef, out: &mut UintRef) -> Choice {
10        let carry = self.wrapping_mul(rhs, out);
11        self.check_mul_overflow(rhs, carry.is_nonzero())
12    }
13
14    /// Compute the wrapping squaring of `self`, placing the result into `out`
15    /// and returning a `Choice` indicating whether overflow occurred.
16    #[inline(always)]
17    pub fn overflowing_square(&self, out: &mut UintRef) -> Choice {
18        let carry = self.wrapping_square(out);
19        self.check_square_overflow(carry.is_nonzero())
20    }
21
22    /// Compute the wrapping product of `self` and `rhs`, placing the result into `out`
23    /// and returning a carry Limb.
24    #[inline(always)]
25    pub fn wrapping_mul(&self, rhs: &UintRef, out: &mut UintRef) -> Limb {
26        karatsuba::wrapping_mul(self, rhs, out, false)
27    }
28
29    /// Compute the wrapping squaring of `self`, placing the result into `out` and returning
30    /// a carry Limb.
31    #[inline(always)]
32    pub fn wrapping_square(&self, out: &mut UintRef) -> Limb {
33        karatsuba::wrapping_square(self, out)
34    }
35
36    /// Determine whether overflow occurs during wrapped multiplication.
37    ///
38    /// We determine this by comparing limbs in `self[i=0..n]` and `rhs[j=0..m]`.
39    /// Any combination where the sum of indexes `i + j >= n`, having `self[i] != 0`
40    /// and `rhs[j] != 0` would cause an overflow. For efficiency, we OR all limbs in
41    /// `rhs` that would apply to each limb in `self` in turn.
42    #[inline(always)]
43    pub(crate) const fn check_mul_overflow(&self, rhs: &UintRef, mut carry: Choice) -> Choice {
44        let mut rhs_tail = Limb::ZERO;
45        let mut i = 0;
46        let mut j = self.nlimbs();
47        let mut k = rhs.nlimbs().saturating_sub(1);
48        while k > j {
49            rhs_tail = rhs_tail.bitor(rhs.limbs[k]);
50            k -= 1;
51        }
52        while i < self.nlimbs() {
53            j = self.nlimbs() - i;
54            if j < rhs.nlimbs() {
55                rhs_tail = rhs_tail.bitor(rhs.limbs[j]);
56                carry = carry.or(self.limbs[i].is_nonzero().and(rhs_tail.is_nonzero()));
57            }
58            i += 1;
59        }
60        carry
61    }
62
63    /// Determine whether overflow occurs during wrapped squaring.
64    #[inline(always)]
65    pub(crate) const fn check_square_overflow(&self, carry: Choice) -> Choice {
66        self.check_mul_overflow(self, carry)
67    }
68}
crypto_bigint/uint/ref_type/mul.rs

crypto_bigint/uint/ref_type/
mul.rs
