crypto_bigint/int/
mul_uint.rs

1use core::ops::Mul;
2
3use subtle::CtOption;
4
5use crate::{CheckedMul, ConcatMixed, ConstChoice, Int, Uint, Zero};
6
7impl<const LIMBS: usize> Int<LIMBS> {
8    /// Compute "wide" multiplication between an [`Int`] and [`Uint`] as 3-tuple `(lo, hi, negate)`.
9    /// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
10    /// corresponding to the sizes of the operands; `negate` indicates whether the result should be
11    /// negated when converted from [`Uint`] to [`Int`].
12    ///
13    /// Note: even if `negate` is truthy, the magnitude might be zero!
14    pub const fn split_mul_uint<const RHS_LIMBS: usize>(
15        &self,
16        rhs: &Uint<RHS_LIMBS>,
17    ) -> (Uint<{ LIMBS }>, Uint<{ RHS_LIMBS }>, ConstChoice) {
18        // Step 1. split self into its sign and magnitude.
19        let (lhs_abs, lhs_sgn) = self.abs_sign();
20
21        // Step 2. Multiply the magnitudes
22        let (lo, hi) = lhs_abs.split_mul(rhs);
23
24        // Step 3. negate if and only if self has a negative sign.
25        (lo, hi, lhs_sgn)
26    }
27
28    /// Compute "wide" multiplication between an [`Int`] and [`Uint`] as 3-tuple `(lo, hi, negate)`.
29    /// The `(lo, hi)` components contain the _magnitude of the product_, with sizes
30    /// corresponding to the sizes of the operands, in reversed order; `negate` indicates whether
31    /// the result should be negated when converted from [`Uint`] to [`Int`].
32    ///
33    /// Note: even if `negate` is truthy, the magnitude might be zero!
34    pub const fn split_mul_uint_right<const RHS_LIMBS: usize>(
35        &self,
36        rhs: &Uint<RHS_LIMBS>,
37    ) -> (Uint<{ RHS_LIMBS }>, Uint<{ LIMBS }>, ConstChoice) {
38        let (lhs_abs, lhs_sgn) = self.abs_sign();
39        let (lo, hi) = rhs.split_mul(&lhs_abs);
40        (lo, hi, lhs_sgn)
41    }
42
43    /// Multiply `self` by [`Uint`] `rhs`, returning a concatenated "wide" result.
44    pub const fn widening_mul_uint<const RHS_LIMBS: usize, const WIDE_LIMBS: usize>(
45        &self,
46        rhs: &Uint<RHS_LIMBS>,
47    ) -> Int<WIDE_LIMBS>
48    where
49        Uint<LIMBS>: ConcatMixed<Uint<RHS_LIMBS>, MixedOutput = Uint<WIDE_LIMBS>>,
50    {
51        let (lhs_abs, lhs_sign) = self.abs_sign();
52        let product_abs = lhs_abs.widening_mul(rhs);
53
54        // always fits
55        product_abs.wrapping_neg_if(lhs_sign).as_int()
56    }
57
58    /// Checked multiplication of self with an `Uint<RHS_LIMBS>`, where the result is to be stored
59    /// in an `Int<RHS_LIMBS>`.
60    pub fn checked_mul_uint_right<const RHS_LIMBS: usize>(
61        &self,
62        rhs: &Uint<RHS_LIMBS>,
63    ) -> CtOption<Int<RHS_LIMBS>> {
64        let (lo, hi, is_negative) = self.split_mul_uint_right(rhs);
65        let val = Int::<RHS_LIMBS>::new_from_abs_sign(lo, is_negative);
66        CtOption::from(val).and_then(|int| CtOption::new(int, hi.is_zero()))
67    }
68}
69
70impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedMul<Uint<RHS_LIMBS>> for Int<LIMBS> {
71    #[inline]
72    fn checked_mul(&self, rhs: &Uint<RHS_LIMBS>) -> CtOption<Self> {
73        let (lo, hi, is_negative) = self.split_mul_uint(rhs);
74        let val = Self::new_from_abs_sign(lo, is_negative);
75        CtOption::from(val).and_then(|int| CtOption::new(int, hi.is_zero()))
76    }
77}
78
79impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Uint<RHS_LIMBS>> for Int<LIMBS> {
80    type Output = Int<LIMBS>;
81
82    fn mul(self, rhs: Uint<RHS_LIMBS>) -> Self {
83        self.mul(&rhs)
84    }
85}
86
87impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Uint<RHS_LIMBS>> for Int<LIMBS> {
88    type Output = Int<LIMBS>;
89
90    fn mul(self, rhs: &Uint<RHS_LIMBS>) -> Self {
91        (&self).mul(rhs)
92    }
93}
94
95impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Uint<RHS_LIMBS>> for &Int<LIMBS> {
96    type Output = Int<LIMBS>;
97
98    fn mul(self, rhs: Uint<RHS_LIMBS>) -> Self::Output {
99        self.mul(&rhs)
100    }
101}
102
103impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Uint<RHS_LIMBS>> for &Int<LIMBS> {
104    type Output = Int<LIMBS>;
105
106    fn mul(self, rhs: &Uint<RHS_LIMBS>) -> Self::Output {
107        self.checked_mul(rhs)
108            .expect("attempted to multiply with overflow")
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use crate::{CheckedMul, I128, I256, U128, U256};
115
116    #[test]
117    fn test_checked_mul_uint() {
118        // lhs = min
119
120        let result = I128::MIN.checked_mul(&U128::ZERO);
121        assert_eq!(result.unwrap(), I128::ZERO);
122
123        let result = I128::MIN.checked_mul(&U128::ONE);
124        assert_eq!(result.unwrap(), I128::MIN);
125
126        let result = I128::MIN.checked_mul(&U128::MAX);
127        assert!(bool::from(result.is_none()));
128
129        // lhs = -1
130
131        let result = I128::MINUS_ONE.checked_mul(&U128::ZERO);
132        assert_eq!(result.unwrap(), I128::ZERO);
133
134        let result = I128::MINUS_ONE.checked_mul(&U128::ONE);
135        assert_eq!(result.unwrap(), I128::MINUS_ONE);
136
137        let result = I128::MINUS_ONE.checked_mul(&U128::MAX);
138        assert!(bool::from(result.is_none()));
139
140        // lhs = 0
141
142        let result = I128::ZERO.checked_mul(&U128::ZERO);
143        assert_eq!(result.unwrap(), I128::ZERO);
144
145        let result = I128::ZERO.checked_mul(&U128::ONE);
146        assert_eq!(result.unwrap(), I128::ZERO);
147
148        let result = I128::ZERO.checked_mul(&U128::MAX);
149        assert_eq!(result.unwrap(), I128::ZERO);
150
151        // lhs = 1
152
153        let result = I128::ONE.checked_mul(&U128::ZERO);
154        assert_eq!(result.unwrap(), I128::ZERO);
155
156        let result = I128::ONE.checked_mul(&U128::ONE);
157        assert_eq!(result.unwrap(), I128::ONE);
158
159        let result = I128::ONE.checked_mul(&U128::MAX);
160        assert!(bool::from(result.is_none()));
161
162        // lhs = max
163
164        let result = I128::MAX.checked_mul(&U128::ZERO);
165        assert_eq!(result.unwrap(), I128::ZERO);
166
167        let result = I128::MAX.checked_mul(&U128::ONE);
168        assert_eq!(result.unwrap(), I128::MAX);
169
170        let result = I128::MAX.checked_mul(&U128::MAX);
171        assert!(bool::from(result.is_none()));
172    }
173
174    #[test]
175    fn test_checked_mul_uint_right() {
176        // rhs = 0
177        let result = I256::MIN.checked_mul_uint_right(&U128::ZERO);
178        assert!(bool::from(result.is_some()));
179        assert_eq!(result.unwrap(), I128::ZERO);
180
181        let result = I128::MIN.checked_mul_uint_right(&U256::ZERO);
182        assert!(bool::from(result.is_some()));
183        assert_eq!(result.unwrap(), I256::ZERO);
184
185        // rhs = 1
186        let result = I256::MIN.checked_mul_uint_right(&U128::ONE);
187        assert!(bool::from(result.is_none()));
188
189        let result = I128::MIN.checked_mul_uint_right(&U256::ONE);
190        assert!(bool::from(result.is_some()));
191        assert_eq!(result.unwrap(), I128::MIN.resize());
192
193        // rhs > 1
194        let result = I256::ONE.checked_mul_uint_right(&I128::MAX.as_uint());
195        assert!(bool::from(result.is_some()));
196        assert_eq!(result.unwrap(), I128::MAX.resize());
197
198        let result = I128::ONE.checked_mul_uint_right(&I256::MAX.as_uint());
199        assert!(bool::from(result.is_some()));
200        assert_eq!(result.unwrap(), I256::MAX);
201
202        // rhs = MAX
203        let result = I256::ONE.checked_mul_uint_right(&U128::MAX);
204        assert!(bool::from(result.is_none()));
205
206        let result = I128::MIN.checked_mul_uint_right(&U256::MAX);
207        assert!(bool::from(result.is_none()));
208    }
209
210    #[test]
211    fn test_widening_mul_uint() {
212        assert_eq!(I128::MIN.widening_mul_uint(&U128::ZERO), I256::ZERO);
213        assert_eq!(
214            I128::MIN.widening_mul_uint(&U128::ONE),
215            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000")
216        );
217        assert_eq!(
218            I128::MIN.widening_mul_uint(&U128::MAX),
219            I256::from_be_hex("8000000000000000000000000000000080000000000000000000000000000000")
220        );
221
222        assert_eq!(I128::MINUS_ONE.widening_mul_uint(&U128::ZERO), I256::ZERO);
223        assert_eq!(
224            I128::MINUS_ONE.widening_mul_uint(&U128::ONE),
225            I256::MINUS_ONE
226        );
227        assert_eq!(
228            I128::MINUS_ONE.widening_mul_uint(&U128::MAX),
229            I256::from_be_hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000001")
230        );
231
232        assert_eq!(I128::ZERO.widening_mul_uint(&U128::ZERO), I256::ZERO);
233        assert_eq!(I128::ZERO.widening_mul_uint(&U128::ONE), I256::ZERO);
234        assert_eq!(I128::ZERO.widening_mul_uint(&U128::MAX), I256::ZERO);
235
236        assert_eq!(I128::ONE.widening_mul_uint(&U128::ZERO), I256::ZERO);
237        assert_eq!(I128::ONE.widening_mul_uint(&U128::ONE), I256::ONE);
238        assert_eq!(
239            I128::ONE.widening_mul_uint(&U128::MAX),
240            I256::from_be_hex("00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
241        );
242
243        assert_eq!(I128::MAX.widening_mul_uint(&U128::ZERO), I256::ZERO);
244        assert_eq!(
245            I128::MAX.widening_mul_uint(&U128::ONE),
246            I256::from_be_hex("000000000000000000000000000000007FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
247        );
248        assert_eq!(
249            I128::MAX.widening_mul_uint(&U128::MAX),
250            I256::from_be_hex("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE80000000000000000000000000000001")
251        );
252    }
253}
crypto_bigint/int/mul_uint.rs

crypto_bigint/int/
mul_uint.rs
