ibig/mul/
helpers.rs

1//! Helper functions for multiplication algorithms.
2
3use crate::{
4    add,
5    arch::word::{SignedWord, Word},
6    memory::Memory,
7    mul,
8    sign::Sign,
9};
10
11/// c += sign * a * b
12///
13/// Splits a into chunks of chunk_len, using regular multiplication for the remainder if any.
14///
15/// Returns carry.
16pub(crate) fn add_signed_mul_split_into_chunks<F>(
17    mut c: &mut [Word],
18    sign: Sign,
19    mut a: &[Word],
20    b: &[Word],
21    chunk_len: usize,
22    memory: &mut Memory,
23    f_add_signed_mul_chunk: F,
24) -> SignedWord
25where
26    F: Fn(&mut [Word], Sign, &[Word], &[Word], &mut Memory) -> SignedWord,
27{
28    debug_assert!(a.len() >= b.len() && c.len() == a.len() + b.len());
29    debug_assert!(b.len() <= chunk_len);
30
31    let n = b.len();
32    let mut carry_n = 0; // at c[n]
33    while a.len() >= chunk_len {
34        let (a_lo, a_hi) = a.split_at(chunk_len);
35        // Propagate carry_n
36        carry_n = add::add_signed_word_in_place(&mut c[n..chunk_len + n], carry_n);
37        carry_n += f_add_signed_mul_chunk(&mut c[..chunk_len + n], sign, a_lo, b, memory);
38        a = a_hi;
39        c = &mut c[chunk_len..];
40    }
41    // Propagate carry_n
42    let mut carry = add::add_signed_word_in_place(&mut c[n..], carry_n);
43    if a.len() >= b.len() {
44        carry += mul::add_signed_mul(c, sign, a, b, memory);
45    } else if !a.is_empty() {
46        carry += mul::add_signed_mul(c, sign, b, a, memory);
47    }
48    carry
49}
ibig/mul/helpers.rs

ibig/mul/
helpers.rs
