crypto_bigint/limb/
mul.rs

1//! Limb multiplication
2
3use crate::{Checked, CheckedMul, Limb, WideWord, Word, Wrapping, Zero};
4use core::ops::{Mul, MulAssign};
5use subtle::CtOption;
6
7impl Limb {
8    /// Computes `self + (b * c) + carry`, returning the result along with the new carry.
9    #[inline(always)]
10    pub const fn mac(self, b: Limb, c: Limb, carry: Limb) -> (Limb, Limb) {
11        let a = self.0 as WideWord;
12        let b = b.0 as WideWord;
13        let c = c.0 as WideWord;
14        let carry = carry.0 as WideWord;
15        let ret = a + (b * c) + carry;
16        (Limb(ret as Word), Limb((ret >> Self::BITS) as Word))
17    }
18
19    /// Perform saturating multiplication.
20    #[inline]
21    pub const fn saturating_mul(&self, rhs: Self) -> Self {
22        Limb(self.0.saturating_mul(rhs.0))
23    }
24
25    /// Perform wrapping multiplication, discarding overflow.
26    #[inline(always)]
27    pub const fn wrapping_mul(&self, rhs: Self) -> Self {
28        Limb(self.0.wrapping_mul(rhs.0))
29    }
30
31    /// Compute "wide" multiplication, with a product twice the size of the input.
32    pub(crate) const fn mul_wide(&self, rhs: Self) -> WideWord {
33        (self.0 as WideWord) * (rhs.0 as WideWord)
34    }
35}
36
37impl CheckedMul for Limb {
38    type Output = Self;
39
40    #[inline]
41    fn checked_mul(&self, rhs: Self) -> CtOption<Self> {
42        let result = self.mul_wide(rhs);
43        let overflow = Limb((result >> Self::BITS) as Word);
44        CtOption::new(Limb(result as Word), overflow.is_zero())
45    }
46}
47
48impl Mul for Wrapping<Limb> {
49    type Output = Self;
50
51    fn mul(self, rhs: Self) -> Wrapping<Limb> {
52        Wrapping(self.0.wrapping_mul(rhs.0))
53    }
54}
55
56impl Mul<&Wrapping<Limb>> for Wrapping<Limb> {
57    type Output = Wrapping<Limb>;
58
59    fn mul(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
60        Wrapping(self.0.wrapping_mul(rhs.0))
61    }
62}
63
64impl Mul<Wrapping<Limb>> for &Wrapping<Limb> {
65    type Output = Wrapping<Limb>;
66
67    fn mul(self, rhs: Wrapping<Limb>) -> Wrapping<Limb> {
68        Wrapping(self.0.wrapping_mul(rhs.0))
69    }
70}
71
72impl Mul<&Wrapping<Limb>> for &Wrapping<Limb> {
73    type Output = Wrapping<Limb>;
74
75    fn mul(self, rhs: &Wrapping<Limb>) -> Wrapping<Limb> {
76        Wrapping(self.0.wrapping_mul(rhs.0))
77    }
78}
79
80impl MulAssign for Wrapping<Limb> {
81    fn mul_assign(&mut self, other: Self) {
82        *self = *self * other;
83    }
84}
85
86impl MulAssign<&Wrapping<Limb>> for Wrapping<Limb> {
87    fn mul_assign(&mut self, other: &Self) {
88        *self = *self * other;
89    }
90}
91
92impl Mul for Checked<Limb> {
93    type Output = Self;
94
95    fn mul(self, rhs: Self) -> Checked<Limb> {
96        Checked(
97            self.0
98                .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
99        )
100    }
101}
102
103impl Mul<&Checked<Limb>> for Checked<Limb> {
104    type Output = Checked<Limb>;
105
106    fn mul(self, rhs: &Checked<Limb>) -> Checked<Limb> {
107        Checked(
108            self.0
109                .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
110        )
111    }
112}
113
114impl Mul<Checked<Limb>> for &Checked<Limb> {
115    type Output = Checked<Limb>;
116
117    fn mul(self, rhs: Checked<Limb>) -> Checked<Limb> {
118        Checked(
119            self.0
120                .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
121        )
122    }
123}
124
125impl Mul<&Checked<Limb>> for &Checked<Limb> {
126    type Output = Checked<Limb>;
127
128    fn mul(self, rhs: &Checked<Limb>) -> Checked<Limb> {
129        Checked(
130            self.0
131                .and_then(|lhs| rhs.0.and_then(|rhs| lhs.checked_mul(rhs))),
132        )
133    }
134}
135
136impl MulAssign for Checked<Limb> {
137    fn mul_assign(&mut self, other: Self) {
138        *self = *self * other;
139    }
140}
141
142impl MulAssign<&Checked<Limb>> for Checked<Limb> {
143    fn mul_assign(&mut self, other: &Self) {
144        *self = *self * other;
145    }
146}
147
148#[cfg(test)]
149mod tests {
150    use super::{CheckedMul, Limb, WideWord};
151
152    #[test]
153    fn mul_wide_zero_and_one() {
154        assert_eq!(Limb::ZERO.mul_wide(Limb::ZERO), 0);
155        assert_eq!(Limb::ZERO.mul_wide(Limb::ONE), 0);
156        assert_eq!(Limb::ONE.mul_wide(Limb::ZERO), 0);
157        assert_eq!(Limb::ONE.mul_wide(Limb::ONE), 1);
158    }
159
160    #[test]
161    fn mul_wide() {
162        let primes: &[u32] = &[3, 5, 17, 257, 65537];
163
164        for &a_int in primes {
165            for &b_int in primes {
166                let actual = Limb::from_u32(a_int).mul_wide(Limb::from_u32(b_int));
167                let expected = a_int as WideWord * b_int as WideWord;
168                assert_eq!(actual, expected);
169            }
170        }
171    }
172
173    #[test]
174    #[cfg(target_pointer_width = "32")]
175    fn checked_mul_ok() {
176        let n = Limb::from_u16(0xffff);
177        assert_eq!(n.checked_mul(n).unwrap(), Limb::from_u32(0xfffe_0001));
178    }
179
180    #[test]
181    #[cfg(target_pointer_width = "64")]
182    fn checked_mul_ok() {
183        let n = Limb::from_u32(0xffff_ffff);
184        assert_eq!(
185            n.checked_mul(n).unwrap(),
186            Limb::from_u64(0xffff_fffe_0000_0001)
187        );
188    }
189
190    #[test]
191    fn checked_mul_overflow() {
192        let n = Limb::MAX;
193        assert!(bool::from(n.checked_mul(n).is_none()));
194    }
195}
crypto_bigint/limb/mul.rs

crypto_bigint/limb/
mul.rs
