vendor/crypto-bigint/src/uint/mul.rs

   1 //! [`UInt`] addition operations.
   2
   3 use crate::{Checked, CheckedMul, Concat, Limb, UInt, Wrapping, Zero};
   4 use core::ops::{Mul, MulAssign};
   5 use subtle::CtOption;
   6
   7 impl<const LIMBS: usize> UInt<LIMBS> {
   8     /// Compute "wide" multiplication, with a product twice the size of the input.
   9     ///
  10     /// Returns a tuple containing the `(lo, hi)` components of the product.
  11     ///
  12     /// # Ordering note
  13     ///
  14     /// Releases of `crypto-bigint` prior to v0.3 used `(hi, lo)` ordering
  15     /// instead. This has been changed for better consistency with the rest of
  16     /// the APIs in this crate.
  17     ///
  18     /// For more info see: <https://github.com/RustCrypto/crypto-bigint/issues/4>
  19     // TODO(tarcieri): use `concat` to construct a wide output
  20     pub const fn mul_wide(&self, rhs: &Self) -> (Self, Self) {
  21         let mut i = 0;
  22         let mut lo = Self::ZERO;
  23         let mut hi = Self::ZERO;
  24
  25         // Schoolbook multiplication.
  26         // TODO(tarcieri): use Karatsuba for better performance?
  27         while i < LIMBS {
  28             let mut j = 0;
  29             let mut carry = Limb::ZERO;
  30
  31             while j < LIMBS {
  32                 let k = i + j;
  33
  34                 if k >= LIMBS {
  35                     let (n, c) = hi.limbs[k - LIMBS].mac(self.limbs[i], rhs.limbs[j], carry);
  36                     hi.limbs[k - LIMBS] = n;
  37                     carry = c;
  38                 } else {
  39                     let (n, c) = lo.limbs[k].mac(self.limbs[i], rhs.limbs[j], carry);
  40                     lo.limbs[k] = n;
  41                     carry = c;
  42                 }
  43
  44                 j += 1;
  45             }
  46
  47             hi.limbs[i + j - LIMBS] = carry;
  48             i += 1;
  49         }
  50
  51         (lo, hi)
  52     }
  53
  54     /// Perform saturating multiplication, returning `MAX` on overflow.
  55     pub const fn saturating_mul(&self, rhs: &Self) -> Self {
  56         let (res, overflow) = self.mul_wide(rhs);
  57
  58         let mut i = 0;
  59         let mut accumulator = 0;
  60
  61         while i < LIMBS {
  62             accumulator |= overflow.limbs[i].0;
  63             i += 1;
  64         }
  65
  66         if accumulator == 0 {
  67             res
  68         } else {
  69             Self::MAX
  70         }
  71     }
  72
  73     /// Perform wrapping multiplication, discarding overflow.
  74     pub const fn wrapping_mul(&self, rhs: &Self) -> Self {
  75         self.mul_wide(rhs).0
  76     }
  77
  78     /// Square self, returning a "wide" result.
  79     pub fn square(&self) -> <Self as Concat>::Output
  80     where
  81         Self: Concat,
  82     {
  83         let (lo, hi) = self.mul_wide(self);
  84         hi.concat(&lo)
  85     }
  86 }
  87
  88 impl<const LIMBS: usize> CheckedMul<&UInt<LIMBS>> for UInt<LIMBS> {
  89     type Output = Self;
  90
  91     fn checked_mul(&self, rhs: &Self) -> CtOption<Self> {
  92         let (lo, hi) = self.mul_wide(rhs);
  93         CtOption::new(lo, hi.is_zero())
  94     }
  95 }
  96
  97 impl<const LIMBS: usize> Mul for Wrapping<UInt<LIMBS>> {
  98     type Output = Self;
  99
 100     fn mul(self, rhs: Self) -> Wrapping<UInt<LIMBS>> {
 101         Wrapping(self.0.wrapping_mul(&rhs.0))
 102     }
 103 }
 104
 105 impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
 106     type Output = Wrapping<UInt<LIMBS>>;
 107
 108     fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
 109         Wrapping(self.0.wrapping_mul(&rhs.0))
 110     }
 111 }
 112
 113 impl<const LIMBS: usize> Mul<Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
 114     type Output = Wrapping<UInt<LIMBS>>;
 115
 116     fn mul(self, rhs: Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
 117         Wrapping(self.0.wrapping_mul(&rhs.0))
 118     }
 119 }
 120
 121 impl<const LIMBS: usize> Mul<&Wrapping<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
 122     type Output = Wrapping<UInt<LIMBS>>;
 123
 124     fn mul(self, rhs: &Wrapping<UInt<LIMBS>>) -> Wrapping<UInt<LIMBS>> {
 125         Wrapping(self.0.wrapping_mul(&rhs.0))
 126     }
 127 }
 128
 129 impl<const LIMBS: usize> MulAssign for Wrapping<UInt<LIMBS>> {
 130     fn mul_assign(&mut self, other: Self) {
 131         *self = *self * other;
 132     }
 133 }
 134
 135 impl<const LIMBS: usize> MulAssign<&Wrapping<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
 136     fn mul_assign(&mut self, other: &Self) {
 137         *self = *self * other;
 138     }
 139 }
 140
 141 impl<const LIMBS: usize> Mul for Checked<UInt<LIMBS>> {
 142     type Output = Self;
 143
 144     fn mul(self, rhs: Self) -> Checked<UInt<LIMBS>> {
 145         Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
 146     }
 147 }
 148
 149 impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
 150     type Output = Checked<UInt<LIMBS>>;
 151
 152     fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
 153         Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
 154     }
 155 }
 156
 157 impl<const LIMBS: usize> Mul<Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
 158     type Output = Checked<UInt<LIMBS>>;
 159
 160     fn mul(self, rhs: Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
 161         Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
 162     }
 163 }
 164
 165 impl<const LIMBS: usize> Mul<&Checked<UInt<LIMBS>>> for &Checked<UInt<LIMBS>> {
 166     type Output = Checked<UInt<LIMBS>>;
 167
 168     fn mul(self, rhs: &Checked<UInt<LIMBS>>) -> Checked<UInt<LIMBS>> {
 169         Checked(self.0.and_then(|a| rhs.0.and_then(|b| a.checked_mul(&b))))
 170     }
 171 }
 172
 173 impl<const LIMBS: usize> MulAssign for Checked<UInt<LIMBS>> {
 174     fn mul_assign(&mut self, other: Self) {
 175         *self = *self * other;
 176     }
 177 }
 178
 179 impl<const LIMBS: usize> MulAssign<&Checked<UInt<LIMBS>>> for Checked<UInt<LIMBS>> {
 180     fn mul_assign(&mut self, other: &Self) {
 181         *self = *self * other;
 182     }
 183 }
 184
 185 #[cfg(test)]
 186 mod tests {
 187     use crate::{CheckedMul, Zero, U64};
 188
 189     #[test]
 190     fn mul_wide_zero_and_one() {
 191         assert_eq!(U64::ZERO.mul_wide(&U64::ZERO), (U64::ZERO, U64::ZERO));
 192         assert_eq!(U64::ZERO.mul_wide(&U64::ONE), (U64::ZERO, U64::ZERO));
 193         assert_eq!(U64::ONE.mul_wide(&U64::ZERO), (U64::ZERO, U64::ZERO));
 194         assert_eq!(U64::ONE.mul_wide(&U64::ONE), (U64::ONE, U64::ZERO));
 195     }
 196
 197     #[test]
 198     fn mul_wide_lo_only() {
 199         let primes: &[u32] = &[3, 5, 17, 256, 65537];
 200
 201         for &a_int in primes {
 202             for &b_int in primes {
 203                 let (lo, hi) = U64::from_u32(a_int).mul_wide(&U64::from_u32(b_int));
 204                 let expected = U64::from_u64(a_int as u64 * b_int as u64);
 205                 assert_eq!(lo, expected);
 206                 assert!(bool::from(hi.is_zero()));
 207             }
 208         }
 209     }
 210
 211     #[test]
 212     fn checked_mul_ok() {
 213         let n = U64::from_u32(0xffff_ffff);
 214         assert_eq!(
 215             n.checked_mul(&n).unwrap(),
 216             U64::from_u64(0xffff_fffe_0000_0001)
 217         );
 218     }
 219
 220     #[test]
 221     fn checked_mul_overflow() {
 222         let n = U64::from_u64(0xffff_ffff_ffff_ffff);
 223         assert!(bool::from(n.checked_mul(&n).is_none()));
 224     }
 225
 226     #[test]
 227     fn saturating_mul_no_overflow() {
 228         let n = U64::from_u8(8);
 229         assert_eq!(n.saturating_mul(&n), U64::from_u8(64));
 230     }
 231
 232     #[test]
 233     fn saturating_mul_overflow() {
 234         let a = U64::from(0xffff_ffff_ffff_ffffu64);
 235         let b = U64::from(2u8);
 236         assert_eq!(a.saturating_mul(&b), U64::MAX);
 237     }
 238
 239     #[test]
 240     fn square() {
 241         let n = U64::from_u64(0xffff_ffff_ffff_ffff);
 242         let (hi, lo) = n.square().split();
 243         assert_eq!(lo, U64::from_u64(1));
 244         assert_eq!(hi, U64::from_u64(0xffff_ffff_ffff_fffe));
 245     }
 246 }