1 use int::{DInt, HInt, Int}; 2 3 trait Mul: DInt 4 where 5 Self::H: DInt, 6 { mul(self, rhs: Self) -> Self7 fn mul(self, rhs: Self) -> Self { 8 // In order to prevent infinite recursion, we cannot use the `widen_mul` in this: 9 //self.lo().widen_mul(rhs.lo()) 10 // .wrapping_add(self.lo().wrapping_mul(rhs.hi()).widen_hi()) 11 // .wrapping_add(self.hi().wrapping_mul(rhs.lo()).widen_hi()) 12 13 let lhs_lo = self.lo(); 14 let rhs_lo = rhs.lo(); 15 // construct the widening multiplication using only `Self::H` sized multiplications 16 let tmp_0 = lhs_lo.lo().zero_widen_mul(rhs_lo.lo()); 17 let tmp_1 = lhs_lo.lo().zero_widen_mul(rhs_lo.hi()); 18 let tmp_2 = lhs_lo.hi().zero_widen_mul(rhs_lo.lo()); 19 let tmp_3 = lhs_lo.hi().zero_widen_mul(rhs_lo.hi()); 20 // sum up all widening partials 21 let mul = Self::from_lo_hi(tmp_0, tmp_3) 22 .wrapping_add(tmp_1.zero_widen() << (Self::BITS / 4)) 23 .wrapping_add(tmp_2.zero_widen() << (Self::BITS / 4)); 24 // add the higher partials 25 mul.wrapping_add(lhs_lo.wrapping_mul(rhs.hi()).widen_hi()) 26 .wrapping_add(self.hi().wrapping_mul(rhs_lo).widen_hi()) 27 } 28 } 29 30 impl Mul for u64 {} 31 impl Mul for i128 {} 32 33 pub(crate) trait UMulo: Int + DInt { mulo(self, rhs: Self) -> (Self, bool)34 fn mulo(self, rhs: Self) -> (Self, bool) { 35 match (self.hi().is_zero(), rhs.hi().is_zero()) { 36 // overflow is guaranteed 37 (false, false) => (self.wrapping_mul(rhs), true), 38 (true, false) => { 39 let mul_lo = self.lo().widen_mul(rhs.lo()); 40 let mul_hi = self.lo().widen_mul(rhs.hi()); 41 let (mul, o) = mul_lo.overflowing_add(mul_hi.lo().widen_hi()); 42 (mul, o || !mul_hi.hi().is_zero()) 43 } 44 (false, true) => { 45 let mul_lo = rhs.lo().widen_mul(self.lo()); 46 let mul_hi = rhs.lo().widen_mul(self.hi()); 47 let (mul, o) = mul_lo.overflowing_add(mul_hi.lo().widen_hi()); 48 (mul, o || !mul_hi.hi().is_zero()) 49 } 50 // overflow is guaranteed to not happen, and use a smaller widening multiplication 51 (true, true) => (self.lo().widen_mul(rhs.lo()), false), 52 } 53 } 54 } 55 56 impl UMulo for u32 {} 57 impl UMulo for u64 {} 58 impl UMulo for u128 {} 59 60 macro_rules! impl_signed_mulo { 61 ($fn:ident, $iD:ident, $uD:ident) => { 62 fn $fn(lhs: $iD, rhs: $iD) -> ($iD, bool) { 63 let mut lhs = lhs; 64 let mut rhs = rhs; 65 // the test against `mul_neg` below fails without this early return 66 if lhs == 0 || rhs == 0 { 67 return (0, false); 68 } 69 70 let lhs_neg = lhs < 0; 71 let rhs_neg = rhs < 0; 72 if lhs_neg { 73 lhs = lhs.wrapping_neg(); 74 } 75 if rhs_neg { 76 rhs = rhs.wrapping_neg(); 77 } 78 let mul_neg = lhs_neg != rhs_neg; 79 80 let (mul, o) = (lhs as $uD).mulo(rhs as $uD); 81 let mut mul = mul as $iD; 82 83 if mul_neg { 84 mul = mul.wrapping_neg(); 85 } 86 if (mul < 0) != mul_neg { 87 // this one check happens to catch all edge cases related to `$iD::MIN` 88 (mul, true) 89 } else { 90 (mul, o) 91 } 92 } 93 }; 94 } 95 96 impl_signed_mulo!(i32_overflowing_mul, i32, u32); 97 impl_signed_mulo!(i64_overflowing_mul, i64, u64); 98 impl_signed_mulo!(i128_overflowing_mul, i128, u128); 99 100 intrinsics! { 101 #[maybe_use_optimized_c_shim] 102 #[arm_aeabi_alias = __aeabi_lmul] 103 pub extern "C" fn __muldi3(a: u64, b: u64) -> u64 { 104 a.mul(b) 105 } 106 107 pub extern "C" fn __multi3(a: i128, b: i128) -> i128 { 108 a.mul(b) 109 } 110 111 pub extern "C" fn __mulosi4(a: i32, b: i32, oflow: &mut i32) -> i32 { 112 let (mul, o) = i32_overflowing_mul(a, b); 113 *oflow = o as i32; 114 mul 115 } 116 117 pub extern "C" fn __mulodi4(a: i64, b: i64, oflow: &mut i32) -> i64 { 118 let (mul, o) = i64_overflowing_mul(a, b); 119 *oflow = o as i32; 120 mul 121 } 122 123 #[unadjusted_on_win64] 124 pub extern "C" fn __muloti4(a: i128, b: i128, oflow: &mut i32) -> i128 { 125 let (mul, o) = i128_overflowing_mul(a, b); 126 *oflow = o as i32; 127 mul 128 } 129 130 pub extern "C" fn __rust_i128_mulo(a: i128, b: i128) -> (i128, bool) { 131 i128_overflowing_mul(a, b) 132 } 133 134 pub extern "C" fn __rust_u128_mulo(a: u128, b: u128) -> (u128, bool) { 135 a.mulo(b) 136 } 137 } 138