| 1 |
|
| 2 |
// multiply the 256-bit number 'a' by the 128-bit number 'b' and return the uppermost 128 bits of the product |
| 3 |
// ripped directly from num-biguint's long multiplication algorithm (mac3, mac_with_carry, adc), but with fixed-size arrays instead of slices |
| 4 |
#[inline] |
| 5 |
pub(crate) fn multiply_256_by_128_upperbits(a_hi: u128, a_lo: u128, b: u128) -> u128 { |
| 6 |
// Break a and b into little-endian 64-bit chunks |
| 7 |
let a_chunks = [ |
| 8 |
a_lo as u64, |
| 9 |
(a_lo >> 64) as u64, |
| 10 |
a_hi as u64, |
| 11 |
(a_hi >> 64) as u64, |
| 12 |
]; |
| 13 |
let b_chunks = [ |
| 14 |
b as u64, |
| 15 |
(b >> 64) as u64, |
| 16 |
]; |
| 17 |
|
| 18 |
// Multiply b by a, one chink of b at a time |
| 19 |
let mut product = [0; 6]; |
| 20 |
for (b_index, &b_digit) in b_chunks.iter().enumerate() { |
| 21 |
multiply_256_by_64_helper(&mut product[b_index..], &a_chunks, b_digit); |
| 22 |
} |
| 23 |
|
| 24 |
// the last 2 elements of the array have the part of the productthat we care about |
| 25 |
((product[5] as u128) << 64) | (product[4] as u128) |
| 26 |
} |
| 27 |
|
| 28 |
#[inline] |
| 29 |
fn multiply_256_by_64_helper(product: &mut [u64], a: &[u64;4], b: u64) { |
| 30 |
if b == 0 { |
| 31 |
return; |
| 32 |
} |
| 33 |
|
| 34 |
let mut carry = 0; |
| 35 |
let (product_lo, product_hi) = product.split_at_mut(a.len()); |
| 36 |
|
| 37 |
// Multiply each of the digits in a by b, adding them into the 'product' value. |
| 38 |
// We don't zero out product, because we this will be called multiple times, so it probably contains a previous iteration's partial product, and we're adding + carrying on top of it |
| 39 |
for (p, &a_digit) in product_lo.iter_mut().zip(a) { |
| 40 |
carry += *p as u128; |
| 41 |
carry += (a_digit as u128) * (b as u128); |
| 42 |
|
| 43 |
*p = carry as u64; |
| 44 |
carry >>= 64; |
| 45 |
} |
| 46 |
|
| 47 |
// We're done multiplying, we just need to finish carrying through the rest of the product. |
| 48 |
let mut p = product_hi.iter_mut(); |
| 49 |
while carry != 0 { |
| 50 |
let p = p.next().expect("carry overflow during multiplication!"); |
| 51 |
carry += *p as u128; |
| 52 |
|
| 53 |
*p = carry as u64; |
| 54 |
carry >>= 64; |
| 55 |
} |
| 56 |
} |
| 57 |
|
| 58 |
// compute product += a * b |
| 59 |
#[inline] |
| 60 |
pub(crate) fn long_multiply(a: &[u64], b: u64, product: &mut [u64]) { |
| 61 |
if b == 0 { |
| 62 |
return; |
| 63 |
} |
| 64 |
|
| 65 |
let mut carry = 0; |
| 66 |
let (product_lo, product_hi) = product.split_at_mut(a.len()); |
| 67 |
|
| 68 |
// Multiply each of the digits in a by b, adding them into the 'product' value. |
| 69 |
// We don't zero out product, because we this will be called multiple times, so it probably contains a previous iteration's partial product, and we're adding + carrying on top of it |
| 70 |
for (p, &a_digit) in product_lo.iter_mut().zip(a) { |
| 71 |
carry += *p as u128; |
| 72 |
carry += (a_digit as u128) * (b as u128); |
| 73 |
|
| 74 |
*p = carry as u64; |
| 75 |
carry >>= 64; |
| 76 |
} |
| 77 |
|
| 78 |
// We're done multiplying, we just need to finish carrying through the rest of the product. |
| 79 |
let mut p = product_hi.iter_mut(); |
| 80 |
while carry != 0 { |
| 81 |
let p = p.next().expect("carry overflow during multiplication!"); |
| 82 |
carry += *p as u128; |
| 83 |
|
| 84 |
*p = carry as u64; |
| 85 |
carry >>= 64; |
| 86 |
} |
| 87 |
} |