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    pub(crate) const fn widening_mul(self, rhs: Self) -> (Self, Self) {
44        let (lo, hi) = widening_mul(self.0, rhs.0);
45        (Limb(lo), Limb(hi))
46    }
47
48    /// Compute "wide" squaring, with a product twice the size of the input.
49    pub(crate) const fn widening_square(self) -> (Self, Self) {
50        let (lo, hi) = widening_mul(self.0, self.0);
51        (Limb(lo), Limb(hi))
52    }
53
54    /// Compute "wide" squaring, with a product twice the size of the input.
55    pub(crate) const fn rem_wide(lo_hi: (Self, Self), p: NonZero<Self>) -> Self {
56        UintRef::new_mut(&mut [lo_hi.0, lo_hi.1]).div_rem_limb(p)
57    }
58}
59
60impl CheckedMul for Limb {
61    #[inline]
62    fn checked_mul(&self, rhs: &Self) -> CtOption<Self> {
63        let (lo, hi) = self.widening_mul(*rhs);
64        CtOption::new(lo, hi.is_zero())
65    }
66}
67
68impl Mul<Limb> for Limb {
69    type Output = Limb;
70
71    #[inline]
72    fn mul(self, rhs: Limb) -> Self {
73        self.checked_mul(&rhs)
74            .expect("attempted to multiply with overflow")
75    }
76}
77
78impl Mul<&Limb> for Limb {
79    type Output = Limb;
80
81    #[inline]
82    fn mul(self, rhs: &Limb) -> Self {
83        self * *rhs
84    }
85}
86
87impl Mul<Limb> for &Limb {
88    type Output = Limb;
89
90    #[inline]
91    fn mul(self, rhs: Limb) -> Self::Output {
92        *self * rhs
93    }
94}
95
96impl Mul<&Limb> for &Limb {
97    type Output = Limb;
98
99    #[inline]
100    fn mul(self, rhs: &Limb) -> Self::Output {
101        *self * *rhs
102    }
103}
104
105impl MulAssign for Limb {
106    #[inline]
107    fn mul_assign(&mut self, other: Self) {
108        *self = *self * other;
109    }
110}
111
112impl MulAssign<&Limb> for Limb {
113    #[inline]
114    fn mul_assign(&mut self, other: &Self) {
115        *self = *self * *other;
116    }
117}
118
119impl MulAssign for Wrapping<Limb> {
120    #[inline]
121    fn mul_assign(&mut self, other: Self) {
122        *self = *self * other;
123    }
124}
125
126impl MulAssign<&Wrapping<Limb>> for Wrapping<Limb> {
127    #[inline]
128    fn mul_assign(&mut self, other: &Self) {
129        *self = *self * other;
130    }
131}
132
133impl MulAssign for Checked<Limb> {
134    #[inline]
135    fn mul_assign(&mut self, other: Self) {
136        *self = *self * other;
137    }
138}
139
140impl MulAssign<&Checked<Limb>> for Checked<Limb> {
141    #[inline]
142    fn mul_assign(&mut self, other: &Self) {
143        *self = *self * other;
144    }
145}
146
147impl WrappingMul for Limb {
148    #[inline]
149    fn wrapping_mul(&self, v: &Self) -> Self {
150        Self::wrapping_mul(*self, *v)
151    }
152}
153
154impl MulMod for Limb {
155    type Output = Self;
156
157    fn mul_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self::Output {
158        let lo_hi = self.widening_mul(*rhs);
159        Self::rem_wide(lo_hi, *p)
160    }
161}
162
163impl SquareMod for Limb {
164    type Output = Self;
165
166    fn square_mod(&self, p: &NonZero<Self>) -> Self::Output {
167        let lo_hi = self.widening_square();
168        Self::rem_wide(lo_hi, *p)
169    }
170}
171
172#[cfg(test)]
173mod tests {
174    use super::{CheckedMul, Limb};
175
176    cpubits::cpubits! {
177        32 => {
178            #[test]
179            fn checked_mul_ok() {
180                let n = Limb::from_u16(0xffff);
181                assert_eq!(n.checked_mul(&n).unwrap(), Limb::from_u32(0xfffe_0001));
182            }
183        }
184        64 => {
185            #[test]
186            fn checked_mul_ok() {
187                let n = Limb::from_u32(0xffff_ffff);
188                assert_eq!(
189                    n.checked_mul(&n).unwrap(),
190                    Limb::from_u64(0xffff_fffe_0000_0001)
191                );
192            }
193        }
194    }
195
196    #[test]
197    fn checked_mul_overflow() {
198        let n = Limb::MAX;
199        assert!(bool::from(n.checked_mul(&n).is_none()));
200    }
201}
crypto_bigint/limb/mul.rs

crypto_bigint/limb/
mul.rs
