// multiply the 256-bit number 'a' by the 128-bit number 'b' and return the uppermost 128 bits of the product // ripped directly from num-biguint's long multiplication algorithm (mac3, mac_with_carry, adc), but with fixed-size arrays instead of slices #[inline] pub(crate) fn multiply_256_by_128_upperbits(a_hi: u128, a_lo: u128, b: u128) -> u128 { // Break a and b into little-endian 64-bit chunks let a_chunks = [ a_lo as u64, (a_lo >> 64) as u64, a_hi as u64, (a_hi >> 64) as u64, ]; let b_chunks = [ b as u64, (b >> 64) as u64, ]; // Multiply b by a, one chink of b at a time let mut product = [0; 6]; for (b_index, &b_digit) in b_chunks.iter().enumerate() { multiply_256_by_64_helper(&mut product[b_index..], &a_chunks, b_digit); } // the last 2 elements of the array have the part of the productthat we care about ((product[5] as u128) << 64) | (product[4] as u128) } #[inline] fn multiply_256_by_64_helper(product: &mut [u64], a: &[u64;4], b: u64) { if b == 0 { return; } let mut carry = 0; let (product_lo, product_hi) = product.split_at_mut(a.len()); // Multiply each of the digits in a by b, adding them into the 'product' value. // 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 for (p, &a_digit) in product_lo.iter_mut().zip(a) { carry += *p as u128; carry += (a_digit as u128) * (b as u128); *p = carry as u64; carry >>= 64; } // We're done multiplying, we just need to finish carrying through the rest of the product. let mut p = product_hi.iter_mut(); while carry != 0 { let p = p.next().expect("carry overflow during multiplication!"); carry += *p as u128; *p = carry as u64; carry >>= 64; } } // compute product += a * b #[inline] pub(crate) fn long_multiply(a: &[u64], b: u64, product: &mut [u64]) { if b == 0 { return; } let mut carry = 0; let (product_lo, product_hi) = product.split_at_mut(a.len()); // Multiply each of the digits in a by b, adding them into the 'product' value. // 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 for (p, &a_digit) in product_lo.iter_mut().zip(a) { carry += *p as u128; carry += (a_digit as u128) * (b as u128); *p = carry as u64; carry >>= 64; } // We're done multiplying, we just need to finish carrying through the rest of the product. let mut p = product_hi.iter_mut(); while carry != 0 { let p = p.next().expect("carry overflow during multiplication!"); carry += *p as u128; *p = carry as u64; carry >>= 64; } }