strength_reduce/
long_multiplication.rs

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]
5pub(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]
29fn 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]
60pub(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}
strength_reduce/long_multiplication.rs

strength_reduce/
long_multiplication.rs
