crypto_bigint/limb/
mul.rs

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

crypto_bigint/limb/
mul.rs
