1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
use crate::U256;
use core::mem::MaybeUninit;
#[inline]
pub fn mulddi3(a: &u128, b: &u128) -> U256 {
let mut high;
let mut low;
const BITS_IN_DWORD_2: u32 = 64;
const LOWER_MASK: u128 = u128::MAX >> BITS_IN_DWORD_2;
low = (a & LOWER_MASK) * (b & LOWER_MASK);
let mut t = low >> BITS_IN_DWORD_2;
low &= LOWER_MASK;
t += (a >> BITS_IN_DWORD_2) * (b & LOWER_MASK);
low += (t & LOWER_MASK) << BITS_IN_DWORD_2;
high = t >> BITS_IN_DWORD_2;
t = low >> BITS_IN_DWORD_2;
low &= LOWER_MASK;
t += (b >> BITS_IN_DWORD_2) * (a & LOWER_MASK);
low += (t & LOWER_MASK) << BITS_IN_DWORD_2;
high += t >> BITS_IN_DWORD_2;
high += (a >> BITS_IN_DWORD_2) * (b >> BITS_IN_DWORD_2);
U256::from_words(high, low)
}
#[inline]
pub fn mul3(res: &mut MaybeUninit<U256>, a: &U256, b: &U256) {
let mut r = mulddi3(a.low(), b.low());
let hi_lo = a.high().wrapping_mul(*b.low());
let lo_hi = a.low().wrapping_mul(*b.high());
*r.high_mut() = r.high().wrapping_add(hi_lo.wrapping_add(lo_hi));
unsafe {
res.as_mut_ptr().write(r);
}
}
#[inline]
pub fn mul2(r: &mut U256, a: &U256) {
let (a, b) = (*r, a);
let res = unsafe { &mut *(r as *mut U256).cast() };
mul3(res, &a, b);
}
#[inline]
pub fn mulc(r: &mut MaybeUninit<U256>, a: &U256, b: &U256) -> bool {
let mut res = mulddi3(a.low(), b.low());
let (hi_lo, overflow_hi_lo) = a.high().overflowing_mul(*b.low());
let (lo_hi, overflow_lo_hi) = a.low().overflowing_mul(*b.high());
let (hi, overflow_hi) = hi_lo.overflowing_add(lo_hi);
let (high, overflow_high) = res.high().overflowing_add(hi);
*res.high_mut() = high;
unsafe {
r.as_mut_ptr().write(res);
}
overflow_hi_lo | overflow_lo_hi | overflow_hi | overflow_high
}
#[cfg(test)]
mod tests {
use super::*;
use crate::AsU256;
fn mul(a: impl AsU256, b: impl AsU256) -> (U256, bool) {
let mut r = MaybeUninit::uninit();
let overflow = mulc(&mut r, &a.as_u256(), &b.as_u256());
(unsafe { r.assume_init() }, overflow)
}
#[test]
fn multiplication() {
assert_eq!(mul(6, 7), (42.as_u256(), false));
assert_eq!(mul(U256::MAX, 1), (U256::MAX, false));
assert_eq!(mul(1, U256::MAX), (U256::MAX, false));
assert_eq!(mul(U256::MAX, 0), (U256::ZERO, false));
assert_eq!(mul(0, U256::MAX), (U256::ZERO, false));
assert_eq!(mul(U256::MAX, 5), (U256::MAX ^ 4, true));
assert_eq!(
mul(u128::MAX, u128::MAX),
(U256::from_words(!0 << 1, 1), false),
);
}
}