Debian Codegraph @

.cargo/vendor/strength_reduce/src/long_multiplication.rs

raw
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 }