ruint/algorithms/
mul_redc.rs

1use super::addmul;
2use core::iter::zip;
3
4/// See Handbook of Applied Cryptography, Algorithm 14.32, p. 601.
5#[allow(clippy::cognitive_complexity)] // REFACTOR: Improve
6#[inline]
7pub fn mul_redc(a: &[u64], b: &[u64], result: &mut [u64], m: &[u64], inv: u64) {
8    debug_assert!(!m.is_empty());
9    debug_assert_eq!(a.len(), m.len());
10    debug_assert_eq!(b.len(), m.len());
11    debug_assert_eq!(result.len(), m.len());
12    debug_assert_eq!(inv.wrapping_mul(m[0]), u64::MAX);
13
14    // Compute temp full product.
15    // OPT: Do combined multiplication and reduction.
16    let mut temp = vec![0; 2 * m.len() + 1];
17    addmul(&mut temp, a, b);
18
19    // Reduce temp.
20    for i in 0..m.len() {
21        let u = temp[i].wrapping_mul(inv);
22
23        // REFACTOR: Create add_mul1 routine.
24        let mut carry = 0;
25        #[allow(clippy::cast_possible_truncation)] // Intentional
26        for j in 0..m.len() {
27            carry += u128::from(temp[i + j]) + u128::from(m[j]) * u128::from(u);
28            temp[i + j] = carry as u64;
29            carry >>= 64;
30        }
31        #[allow(clippy::cast_possible_truncation)] // Intentional
32        for j in m.len()..(temp.len() - i) {
33            carry += u128::from(temp[i + j]);
34            temp[i + j] = carry as u64;
35            carry >>= 64;
36        }
37        debug_assert!(carry == 0);
38    }
39    debug_assert!(temp[temp.len() - 1] <= 1); // Basically a carry flag.
40
41    // Copy result.
42    result.copy_from_slice(&temp[m.len()..2 * m.len()]);
43
44    // Subtract one more m if result >= m
45    let mut reduce = true;
46    // REFACTOR: Create cmp routine
47    if temp[temp.len() - 1] == 0 {
48        for (r, m) in zip(result.iter().rev(), m.iter().rev()) {
49            if r < m {
50                reduce = false;
51                break;
52            }
53            if r > m {
54                break;
55            }
56        }
57    }
58    if reduce {
59        // REFACTOR: Create sub routine
60        let mut carry = 0;
61        #[allow(clippy::cast_possible_truncation)] // Intentional
62        #[allow(clippy::cast_sign_loss)] // Intentional
63        for (r, m) in zip(result.iter_mut(), m.iter().copied()) {
64            carry += i128::from(*r) - i128::from(m);
65            *r = carry as u64;
66            carry >>= 64; // Sign extending shift
67        }
68        debug_assert!(carry == 0 || temp[temp.len() - 1] == 1);
69    }
70}
ruint/algorithms/mul_redc.rs

ruint/algorithms/
mul_redc.rs
