crypto_bigint/uint/
mul.rs

Help
1//! [`UInt`] addition operations.
2
3use crate::{Checked, CheckedMul, Concat, Limb, UInt, Wrapping, Zero};
4use core::ops::{Mul, MulAssign};
5use subtle::CtOption;
6
7impl<const LIMBS: usize> UInt<LIMBS> {
8    /// Compute "wide" multiplication, with a product twice the size of the input.
9    ///
10    /// Returns a tuple containing the `(lo, hi)` components of the product.
11    ///
12    /// # Ordering note
13    ///
14    /// Releases of `crypto-bigint` prior to v0.3 used `(hi, lo)` ordering
15    /// instead. This has been changed for better consistency with the rest of
16    /// the APIs in this crate.
17    ///
18    /// For more info see: <https://github.com/RustCrypto/crypto-bigint/issues/4>
19    // TODO(tarcieri): use `concat` to construct a wide output
20    pub const fn mul_wide(&self, rhs: &Self) -> (Self, Self) {
21        let mut i = 0;
22        let mut lo = Self::ZERO;
23        let mut hi = Self::ZERO;
24
25        // Schoolbook multiplication.
26        // TODO(tarcieri): use Karatsuba for better performance?
27        while i < LIMBS {
28            let mut j = 0;
29            let mut carry = Limb::ZERO;
30
31            while j < LIMBS {
32                let k = i + j;
33
34                if k >= LIMBS {
35                    let (n, c) = hi.limbs[k - LIMBS].mac(self.limbs[i], rhs.limbs[j], carry);
36                    hi.limbs[k - LIMBS] = n;
37                    carry = c;
38                } else {
39                    let (n, c) = lo.limbs[k].mac(self.limbs[i], rhs.limbs[j], carry);
40                    lo.limbs[k] = n;
41                    carry = c;
42                }
43
44                j += 1;
45            }
46
47            hi.limbs[i + j - LIMBS] = carry;
48            i += 1;
49        }
50
51        (lo, hi)
52    }
53
54    /// Perform saturating multiplication, returning `MAX` on overflow.
55    pub const fn saturating_mul(&self, rhs: &Self) -> Self {
56        let (res, overflow) = self.mul_wide(rhs);
57
58        let mut i = 0;
59        let mut accumulator = 0;
60
61        while i < LIMBS {
62            accumulator |= overflow.limbs[i].0;
63            i += 1;
64        }
65
66        if accumulator == 0 {
67            res
68        } else {
69            Self::MAX
70        }
71    }
72
73    /// Perform wrapping multiplication, discarding overflow.
74    pub const fn wrapping_mul(&self, rhs: &Self) -> Self {
75        self.mul_wide(rhs).0
76    }
77
78    /// Square self, returning a "wide" result.
79    pub fn square(&self) -> <Self as Concat>::Output
80    where
81        Self: Concat,
82    {
83        let (lo, hi) = self.mul_wide(self);
84        hi.concat(&lo)
85    }
86}
87
88impl<const LIMBS: usize> CheckedMul<&UInt<LIMBS>> for UInt<LIMBS> {
89    type Output = Self;
90
91    fn checked_mul(&self, rhs: &Self) -> CtOption<Self> {
92        let (lo, hi) = self.mul_wide(rhs);
93        CtOption::new(lo, hi.is_zero())
94    }
95}
96
97impl<const LIMBS: usize> Mul for Wrapping<UInt<LIMBS>> {
98    type Output = Self;
99
100    fn mul(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
101        Wrapping(self.0.wrapping_mul(&rhs.0))
102    }
103}
104
105impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
106    type Output = Wrapping<UInt<LIMBS>>;
107
108    fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
109        Wrapping(self.0.wrapping_mul(&rhs.0))
110    }
111}
112
113impl<const LIMBS: usize> Mul<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
114    type Output = Wrapping<UInt<LIMBS>>;
115
116    fn mul(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
117        Wrapping(self.0.wrapping_mul(&rhs.0))
118    }
119}
120
121impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
122    type Output = Wrapping<UInt<LIMBS>>;
123
124    fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
125        Wrapping(self.0.wrapping_mul(&rhs.0))
126    }
127}
128
129impl<const LIMBS: usize> MulAssign for Wrapping<UInt<LIMBS>> {
130    fn mul_assign(&mut self, other: Self) {
131        *self = *self * other;
132    }
133}
134
135impl<const LIMBS: usize> MulAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
136    fn mul_assign(&mut self, other: &Self) {
137        *self = *self * other;
138    }
139}
140
141impl<const LIMBS: usize> Mul for Checked<UInt<LIMBS>> {
142    type Output = Self;
143
144    fn mul(self, rhs: Self) -> Checked<UInt<LIMBS>> {
145        Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
146    }
147}
148
149impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
150    type Output = Checked<UInt<LIMBS>>;
151
152    fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
153        Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
154    }
155}
156
157impl<const LIMBS: usize> Mul<Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
158    type Output = Checked<UInt<LIMBS>>;
159
160    fn mul(self, rhs: Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
161        Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
162    }
163}
164
165impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
166    type Output = Checked<UInt<LIMBS>>;
167
168    fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
169        Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
170    }
171}
172
173impl<const LIMBS: usize> MulAssign for Checked<UInt<LIMBS>> {
174    fn mul_assign(&mut self, other: Self) {
175        *self = *self * other;
176    }
177}
178
179impl<const LIMBS: usize> MulAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
180    fn mul_assign(&mut self, other: &Self) {
181        *self = *self * other;
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use crate::{CheckedMul, Zero, U64};
188
189    #[test]
190    fn mul_wide_zero_and_one() {
191        assert_eq!(U64::ZERO.mul_wide(&U64::ZERO), (U64::ZERO, U64::ZERO));
192        assert_eq!(U64::ZERO.mul_wide(&U64::ONE), (U64::ZERO, U64::ZERO));
193        assert_eq!(U64::ONE.mul_wide(&U64::ZERO), (U64::ZERO, U64::ZERO));
194        assert_eq!(U64::ONE.mul_wide(&U64::ONE), (U64::ONE, U64::ZERO));
195    }
196
197    #[test]
198    fn mul_wide_lo_only() {
199        let primes: &[u32] = &[3, 5, 17, 256, 65537];
200
201        for &a_int in primes {
202            for &b_int in primes {
203                let (lo, hi) = U64::from_u32(a_int).mul_wide(&U64::from_u32(b_int));
204                let expected = U64::from_u64(a_int as u64 * b_int as u64);
205                assert_eq!(lo, expected);
206                assert!(bool::from(hi.is_zero()));
207            }
208        }
209    }
210
211    #[test]
212    fn checked_mul_ok() {
213        let n = U64::from_u32(0xffff_ffff);
214        assert_eq!(
215            n.checked_mul(&n).unwrap(),
216            U64::from_u64(0xffff_fffe_0000_0001)
217        );
218    }
219
220    #[test]
221    fn checked_mul_overflow() {
222        let n = U64::from_u64(0xffff_ffff_ffff_ffff);
223        assert!(bool::from(n.checked_mul(&n).is_none()));
224    }
225
226    #[test]
227    fn saturating_mul_no_overflow() {
228        let n = U64::from_u8(8);
229        assert_eq!(n.saturating_mul(&n), U64::from_u8(64));
230    }
231
232    #[test]
233    fn saturating_mul_overflow() {
234        let a = U64::from(0xffff_ffff_ffff_ffffu64);
235        let b = U64::from(2u8);
236        assert_eq!(a.saturating_mul(&b), U64::MAX);
237    }
238
239    #[test]
240    fn square() {
241        let n = U64::from_u64(0xffff_ffff_ffff_ffff);
242        let (hi, lo) = n.square().split();
243        assert_eq!(lo, U64::from_u64(1));
244        assert_eq!(hi, U64::from_u64(0xffff_ffff_ffff_fffe));
245    }
246}
crypto_bigint/uint/mul.rs

crypto_bigint/uint/
mul.rs
