crypto_bigint/int/
mul.rs

1//! [`Int`] multiplication operations.
2
3use core::ops::{Mul, MulAssign};
4
5use subtle::CtOption;
6
7use crate::{Checked, CheckedMul, ConcatMixed, ConstChoice, ConstCtOption, Int, Uint, Zero};
8
9impl<const LIMBS: usize> Int<LIMBS> {
10    /// Compute "wide" multiplication as a 3-tuple `(lo, hi, negate)`.
11    /// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
12    /// corresponding to the sizes of the operands; `negate` indicates whether the result should be
13    /// negated when converted from [`Uint`] to [`Int`].
14    ///
15    /// Note: even if `negate` is truthy, the magnitude might be zero!
16    pub const fn split_mul<const RHS_LIMBS: usize>(
17        &self,
18        rhs: &Int<RHS_LIMBS>,
19    ) -> (Uint<{ LIMBS }>, Uint<{ RHS_LIMBS }>, ConstChoice) {
20        // Step 1: split operands into their signs and magnitudes.
21        let (lhs_abs, lhs_sgn) = self.abs_sign();
22        let (rhs_abs, rhs_sgn) = rhs.abs_sign();
23
24        // Step 2: multiply the magnitudes
25        let (lo, hi) = lhs_abs.split_mul(&rhs_abs);
26
27        // Step 3. Determine if the result should be negated.
28        // This should be done if and only if lhs and rhs have opposing signs.
29        // Note: if either operand is zero, the resulting magnitude will also be zero. Negating
30        // zero, however, still yields zero, so having a truthy `negate` in that scenario is OK.
31        let negate = lhs_sgn.xor(rhs_sgn);
32
33        (lo, hi, negate)
34    }
35
36    /// Multiply `self` by `rhs`, returning a concatenated "wide" result.
37    pub const fn widening_mul<const RHS_LIMBS: usize, const WIDE_LIMBS: usize>(
38        &self,
39        rhs: &Int<RHS_LIMBS>,
40    ) -> Int<WIDE_LIMBS>
41    where
42        Uint<LIMBS>: ConcatMixed<Uint<RHS_LIMBS>, MixedOutput = Uint<WIDE_LIMBS>>,
43    {
44        let (lhs_abs, lhs_sign) = self.abs_sign();
45        let (rhs_abs, rhs_sign) = rhs.abs_sign();
46        let product_abs = lhs_abs.widening_mul(&rhs_abs);
47        let product_sign = lhs_sign.xor(rhs_sign);
48
49        // always fits
50        Int::from_bits(product_abs.wrapping_neg_if(product_sign))
51    }
52}
53
54/// Squaring operations.
55impl<const LIMBS: usize> Int<LIMBS> {
56    /// Square self, returning a concatenated "wide" result.
57    pub fn widening_square<const WIDE_LIMBS: usize>(&self) -> Uint<WIDE_LIMBS>
58    where
59        Uint<LIMBS>: ConcatMixed<Uint<LIMBS>, MixedOutput = Uint<WIDE_LIMBS>>,
60    {
61        self.abs().widening_square()
62    }
63
64    /// Square self, checking that the result fits in the original [`Uint`] size.
65    pub fn checked_square(&self) -> ConstCtOption<Uint<LIMBS>> {
66        self.abs().checked_square()
67    }
68
69    /// Perform wrapping square, discarding overflow.
70    pub const fn wrapping_square(&self) -> Uint<LIMBS> {
71        self.abs().wrapping_square()
72    }
73
74    /// Perform saturating squaring, returning `MAX` on overflow.
75    pub const fn saturating_square(&self) -> Uint<LIMBS> {
76        self.abs().saturating_square()
77    }
78}
79
80impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedMul<Int<RHS_LIMBS>> for Int<LIMBS> {
81    #[inline]
82    fn checked_mul(&self, rhs: &Int<RHS_LIMBS>) -> CtOption<Self> {
83        let (lo, hi, is_negative) = self.split_mul(rhs);
84        let val = Self::new_from_abs_sign(lo, is_negative);
85        CtOption::from(val).and_then(|int| CtOption::new(int, hi.is_zero()))
86    }
87}
88
89impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Int<RHS_LIMBS>> for Int<LIMBS> {
90    type Output = Int<LIMBS>;
91
92    fn mul(self, rhs: Int<RHS_LIMBS>) -> Self {
93        self.mul(&rhs)
94    }
95}
96
97impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Int<RHS_LIMBS>> for Int<LIMBS> {
98    type Output = Int<LIMBS>;
99
100    fn mul(self, rhs: &Int<RHS_LIMBS>) -> Self {
101        (&self).mul(rhs)
102    }
103}
104
105impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Int<RHS_LIMBS>> for &Int<LIMBS> {
106    type Output = Int<LIMBS>;
107
108    fn mul(self, rhs: Int<RHS_LIMBS>) -> Self::Output {
109        self.mul(&rhs)
110    }
111}
112
113impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Int<RHS_LIMBS>> for &Int<LIMBS> {
114    type Output = Int<LIMBS>;
115
116    fn mul(self, rhs: &Int<RHS_LIMBS>) -> Self::Output {
117        self.checked_mul(rhs)
118            .expect("attempted to multiply with overflow")
119    }
120}
121
122impl<const LIMBS: usize> MulAssign<Checked<Int<LIMBS>>> for Checked<Int<LIMBS>> {
123    fn mul_assign(&mut self, other: Checked<Int<LIMBS>>) {
124        *self = *self * other;
125    }
126}
127
128impl<const LIMBS: usize> MulAssign<&Checked<Int<LIMBS>>> for Checked<Int<LIMBS>> {
129    fn mul_assign(&mut self, other: &Checked<Int<LIMBS>>) {
130        *self = *self * other;
131    }
132}
133
134// TODO(lleoha): unfortunately we cannot satisfy this (yet!).
135// impl<const LIMBS: usize, const RHS_LIMBS: usize, const WIDE_LIMBS: usize>
136// WideningMul<Int<RHS_LIMBS>> for Int<LIMBS>
137// where
138//     Uint<LIMBS>: ConcatMixed<Uint<RHS_LIMBS>, MixedOutput = Uint<WIDE_LIMBS>>,
139// {
140//     type Output = Int<WIDE_LIMBS>;
141//
142//     #[inline]
143//     fn widening_mul(&self, rhs: Int<RHS_LIMBS>) -> Self::Output {
144//         self.widening_mul(&rhs)
145//     }
146// }
147
148#[cfg(test)]
149mod tests {
150    use crate::{CheckedMul, ConstChoice, Int, I128, I256, U128, U256};
151
152    #[test]
153    fn test_checked_mul() {
154        let min_plus_one = Int {
155            0: I128::MIN.0.wrapping_add(&I128::ONE.0),
156        };
157
158        // lhs = min
159
160        let result = I128::MIN.checked_mul(&I128::MIN);
161        assert!(bool::from(result.is_none()));
162
163        let result = I128::MIN.checked_mul(&I128::MINUS_ONE);
164        assert!(bool::from(result.is_none()));
165
166        let result = I128::MIN.checked_mul(&I128::ZERO);
167        assert_eq!(result.unwrap(), I128::ZERO);
168
169        let result = I128::MIN.checked_mul(&I128::ONE);
170        assert_eq!(result.unwrap(), I128::MIN);
171
172        let result = I128::MIN.checked_mul(&I128::MAX);
173        assert!(bool::from(result.is_none()));
174
175        // lhs = -1
176
177        let result = I128::MINUS_ONE.checked_mul(&I128::MIN);
178        assert!(bool::from(result.is_none()));
179
180        let result = I128::MINUS_ONE.checked_mul(&I128::MINUS_ONE);
181        assert_eq!(result.unwrap(), I128::ONE);
182
183        let result = I128::MINUS_ONE.checked_mul(&I128::ZERO);
184        assert_eq!(result.unwrap(), I128::ZERO);
185
186        let result = I128::MINUS_ONE.checked_mul(&I128::ONE);
187        assert_eq!(result.unwrap(), I128::MINUS_ONE);
188
189        let result = I128::MINUS_ONE.checked_mul(&I128::MAX);
190        assert_eq!(result.unwrap(), min_plus_one);
191
192        // lhs = 0
193
194        let result = I128::ZERO.checked_mul(&I128::MIN);
195        assert_eq!(result.unwrap(), I128::ZERO);
196
197        let result = I128::ZERO.checked_mul(&I128::MINUS_ONE);
198        assert_eq!(result.unwrap(), I128::ZERO);
199
200        let result = I128::ZERO.checked_mul(&I128::ZERO);
201        assert_eq!(result.unwrap(), I128::ZERO);
202
203        let result = I128::ZERO.checked_mul(&I128::ONE);
204        assert_eq!(result.unwrap(), I128::ZERO);
205
206        let result = I128::ZERO.checked_mul(&I128::MAX);
207        assert_eq!(result.unwrap(), I128::ZERO);
208
209        // lhs = 1
210
211        let result = I128::ONE.checked_mul(&I128::MIN);
212        assert_eq!(result.unwrap(), I128::MIN);
213
214        let result = I128::ONE.checked_mul(&I128::MINUS_ONE);
215        assert_eq!(result.unwrap(), I128::MINUS_ONE);
216
217        let result = I128::ONE.checked_mul(&I128::ZERO);
218        assert_eq!(result.unwrap(), I128::ZERO);
219
220        let result = I128::ONE.checked_mul(&I128::ONE);
221        assert_eq!(result.unwrap(), I128::ONE);
222
223        let result = I128::ONE.checked_mul(&I128::MAX);
224        assert_eq!(result.unwrap(), I128::MAX);
225
226        // lhs = max
227
228        let result = I128::MAX.checked_mul(&I128::MIN);
229        assert!(bool::from(result.is_none()));
230
231        let result = I128::MAX.checked_mul(&I128::MINUS_ONE);
232        assert_eq!(result.unwrap(), min_plus_one);
233
234        let result = I128::MAX.checked_mul(&I128::ZERO);
235        assert_eq!(result.unwrap(), I128::ZERO);
236
237        let result = I128::MAX.checked_mul(&I128::ONE);
238        assert_eq!(result.unwrap(), I128::MAX);
239
240        let result = I128::MAX.checked_mul(&I128::MAX);
241        assert!(bool::from(result.is_none()));
242    }
243
244    #[test]
245    fn test_widening_mul() {
246        assert_eq!(
247            I128::MIN.widening_mul(&I128::MIN),
248            I256::from_be_hex("4000000000000000000000000000000000000000000000000000000000000000")
249        );
250        assert_eq!(
251            I128::MIN.widening_mul(&I128::MINUS_ONE),
252            I256::from_be_hex("0000000000000000000000000000000080000000000000000000000000000000")
253        );
254        assert_eq!(I128::MIN.widening_mul(&I128::ZERO), I256::ZERO);
255        assert_eq!(
256            I128::MIN.widening_mul(&I128::ONE),
257            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
258        );
259        assert_eq!(
260            I128::MIN.widening_mul(&I128::MAX),
261            I256::from_be_hex("C000000000000000000000000000000080000000000000000000000000000000")
262        );
263
264        assert_eq!(
265            I128::MINUS_ONE.widening_mul(&I128::MIN),
266            I256::from_be_hex("0000000000000000000000000000000080000000000000000000000000000000")
267        );
268        assert_eq!(I128::MINUS_ONE.widening_mul(&I128::MINUS_ONE), I256::ONE);
269        assert_eq!(I128::MINUS_ONE.widening_mul(&I128::ZERO), I256::ZERO);
270        assert_eq!(I128::MINUS_ONE.widening_mul(&I128::ONE), I256::MINUS_ONE);
271        assert_eq!(
272            I128::MINUS_ONE.widening_mul(&I128::MAX),
273            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000001")
274        );
275
276        assert_eq!(I128::ZERO.widening_mul(&I128::MIN), I256::ZERO);
277        assert_eq!(I128::ZERO.widening_mul(&I128::MINUS_ONE), I256::ZERO);
278        assert_eq!(I128::ZERO.widening_mul(&I128::ZERO), I256::ZERO);
279        assert_eq!(I128::ZERO.widening_mul(&I128::ONE), I256::ZERO);
280        assert_eq!(I128::ZERO.widening_mul(&I128::MAX), I256::ZERO);
281
282        assert_eq!(
283            I128::ONE.widening_mul(&I128::MIN),
284            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
285        );
286        assert_eq!(I128::ONE.widening_mul(&I128::MINUS_ONE), I256::MINUS_ONE);
287        assert_eq!(I128::ONE.widening_mul(&I128::ZERO), I256::ZERO);
288        assert_eq!(I128::ONE.widening_mul(&I128::ONE), I256::ONE);
289        assert_eq!(
290            I128::ONE.widening_mul(&I128::MAX),
291            I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
292        );
293
294        assert_eq!(
295            I128::MAX.widening_mul(&I128::MIN),
296            I256::from_be_hex("C000000000000000000000000000000080000000000000000000000000000000")
297        );
298        assert_eq!(
299            I128::MAX.widening_mul(&I128::MINUS_ONE),
300            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000001")
301        );
302        assert_eq!(I128::MAX.widening_mul(&I128::ZERO), I256::ZERO);
303        assert_eq!(
304            I128::MAX.widening_mul(&I128::ONE),
305            I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
306        );
307        assert_eq!(
308            I128::MAX.widening_mul(&I128::MAX),
309            I256::from_be_hex("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000001")
310        );
311    }
312
313    #[test]
314    fn test_widening_square() {
315        let res = I128::from_i64(i64::MIN).widening_square();
316        assert_eq!(
317            res,
318            U256::from_be_hex("0000000000000000000000000000000040000000000000000000000000000000")
319        );
320
321        let x: I128 = I128::MINUS_ONE << 64;
322        let res = x.widening_square();
323        assert_eq!(
324            res,
325            U256::from_be_hex("0000000000000000000000000000000100000000000000000000000000000000")
326        )
327    }
328
329    #[test]
330    fn test_checked_square() {
331        let res = I128::from_i64(i64::MIN).checked_square();
332        assert_eq!(res.is_some(), ConstChoice::TRUE);
333        assert_eq!(
334            res.unwrap(),
335            U128::from_be_hex("40000000000000000000000000000000")
336        );
337
338        let x: I128 = I128::MINUS_ONE << 64;
339        let res = x.checked_square();
340        assert_eq!(res.is_none(), ConstChoice::TRUE)
341    }
342
343    #[test]
344    fn test_wrapping_square() {
345        let res = I128::from_i64(i64::MIN).wrapping_square();
346        assert_eq!(res, U128::from_be_hex("40000000000000000000000000000000"));
347
348        let x: I128 = I128::MINUS_ONE << 64;
349        let res = x.wrapping_square();
350        assert_eq!(res, U128::ZERO);
351
352        let x: I128 = I128::from_i64(i64::MAX);
353        let res = x.wrapping_square();
354        assert_eq!(res, U128::from_be_hex("3FFFFFFFFFFFFFFF0000000000000001"))
355    }
356
357    #[test]
358    fn test_saturating_square() {
359        assert_eq!(
360            I128::from_i64(i64::MIN).saturating_square(),
361            U128::from_be_hex("40000000000000000000000000000000")
362        );
363        let x: I128 = I128::MINUS_ONE << 64;
364        assert_eq!(x.saturating_square(), U128::MAX);
365    }
366}
crypto_bigint/int/mul.rs

crypto_bigint/int/
mul.rs
