zinc_poly/univariate/
dynamic.rs

1mod multiplication;
2pub mod over_field;
3pub mod over_fixed_semiring;
4
5use std::{
6    fmt::Display,
7    ops::{AddAssign, Neg, SubAssign},
8};
9
10use crypto_primitives::Semiring;
11use itertools::Itertools;
12
13use crate::univariate::dynamic::multiplication::mul_schoolbook;
14
15#[allow(clippy::arithmetic_side_effects)]
16fn new_coeffs_trimmed<R: Clone>(coeffs: &[R], is_zero: impl Fn(&R) -> bool) -> Vec<R> {
17    if let Some((non_zero, _)) = coeffs.iter().rev().find_position(|&coeff| !is_zero(coeff)) {
18        let deg_plus_one = coeffs.len() - non_zero;
19
20        coeffs.iter().take(deg_plus_one).cloned().collect()
21    } else {
22        Vec::new()
23    }
24}
25
26#[allow(clippy::arithmetic_side_effects)]
27fn degree<R>(coeffs: &[R], is_zero: impl Fn(&R) -> bool) -> Option<usize> {
28    coeffs
29        .iter()
30        .rev()
31        .find_position(|coeff| !is_zero(coeff))
32        .map(|(non_zero, _)| coeffs.len() - non_zero - 1)
33}
34
35#[allow(clippy::arithmetic_side_effects)]
36fn trim<R>(coeffs: &mut Vec<R>, is_zero: impl Fn(&R) -> bool) {
37    coeffs.truncate(degree(coeffs, is_zero).map_or(0, |degree| degree + 1))
38}
39
40fn display<R: Display>(coeffs: &[R], f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
41    write!(f, "[")?;
42    let mut first = true;
43
44    for coeff in coeffs.iter() {
45        if first {
46            first = false;
47        } else {
48            write!(f, ", ")?;
49        }
50        write!(f, "{}", coeff)?;
51    }
52
53    write!(f, "]")
54}
55
56fn is_zero<R>(coeffs: &[R], is_zero: impl Fn(&R) -> bool) -> bool {
57    coeffs.iter().all(is_zero)
58}
59
60fn neg<R: Neg<Output = R>>(coeffs: Vec<R>) -> Vec<R> {
61    coeffs.into_iter().map(|coeff| coeff.neg()).collect()
62}
63
64macro_rules! impl_assign_op {
65    ($name:ident, $trait:ident) => {
66        #[allow(clippy::arithmetic_side_effects)] // by definition
67        fn $name<R: for<'a> $trait<&'a R> + Clone>(
68            lhs: &mut Vec<R>,
69            rhs: &[R],
70            zero_from_elem: impl Fn(&R) -> R,
71        ) {
72            if lhs.len() < rhs.len() {
73                lhs.resize(rhs.len(), zero_from_elem(&rhs[0]));
74            }
75
76            lhs.iter_mut().zip(rhs).for_each(|(lhs, rhs)| {
77                lhs.$name(rhs);
78            });
79        }
80    };
81}
82
83impl_assign_op!(add_assign, AddAssign);
84impl_assign_op!(sub_assign, SubAssign);
85
86#[allow(clippy::arithmetic_side_effects)]
87fn mul<R: Semiring, const CHECK: bool>(
88    lhs: &[R],
89    rhs: &[R],
90    is_zero_elem: impl Fn(&R) -> bool,
91) -> Option<Vec<R>> {
92    if is_zero(lhs, &is_zero_elem) || is_zero(rhs, is_zero_elem) {
93        return Some(Vec::new());
94    }
95
96    let degree = (lhs.len() - 1) + (rhs.len() - 1);
97    let mut coeffs = Vec::with_capacity(degree + 1);
98
99    mul_schoolbook::<_, CHECK>(lhs, rhs, coeffs.spare_capacity_mut())?;
100
101    // Safety: the multiplication algorithm should fill in the entire spare
102    // capacity.
103    unsafe {
104        coeffs.set_len(degree + 1);
105    }
106
107    Some(coeffs)
108}
zinc_poly/univariate/dynamic.rs

zinc_poly/univariate/
dynamic.rs
