ps_ecc/polynomial/methods/
eval_coefficient_iter_at.rs

1use crate::{
2    finite_field::{add, mul},
3    Polynomial,
4};
5
6impl Polynomial {
7    /// Evaluates a polynomial from an iterator of coefficients at the given point.
8    ///
9    /// Coefficients are yielded from degree 0 (constant term) to the leading term.
10    /// Requires `DoubleEndedIterator` for Horner's method.
11    #[must_use]
12    pub fn eval_coefficient_iter_at<I>(coefficients: I, x: u8) -> u8
13    where
14        I: DoubleEndedIterator<Item = u8>,
15    {
16        let mut result = 0u8;
17
18        for coef in coefficients.rev() {
19            result = add(mul(result, x), coef);
20        }
21
22        result
23    }
24}
25
26#[cfg(test)]
27mod tests {
28    use crate::{
29        finite_field::{add, mul},
30        Polynomial,
31    };
32
33    /// Computes expected value using naive polynomial evaluation.
34    fn naive_eval(coefficients: impl Iterator<Item = u8>, x: u8) -> u8 {
35        let mut result = 0u8;
36        let mut x_pow = 1u8;
37
38        for c in coefficients {
39            result = add(result, mul(c, x_pow));
40            x_pow = mul(x_pow, x);
41        }
42
43        result
44    }
45
46    /// Asserts that `eval_coefficient_iter_at` matches naive evaluation for all x in 0..=255.
47    fn assert_exhaustive(coefficients: &[u8]) {
48        for x in 0..=255u8 {
49            assert_eq!(
50                Polynomial::eval_coefficient_iter_at(coefficients.iter().copied(), x),
51                naive_eval(coefficients.iter().copied(), x)
52            );
53        }
54    }
55
56    /// Asserts that `eval_coefficient_iter_at` with chained slices matches naive evaluation for all x.
57    fn assert_exhaustive_chained(low: &[u8], high: &[u8]) {
58        for x in 0..=255u8 {
59            let iter = low.iter().chain(high.iter()).copied();
60
61            assert_eq!(
62                Polynomial::eval_coefficient_iter_at(low.iter().chain(high.iter()).copied(), x),
63                naive_eval(iter, x)
64            );
65        }
66    }
67
68    #[test]
69    fn empty_iterator() {
70        assert_exhaustive(&[]);
71    }
72
73    #[test]
74    fn zero_polynomial() {
75        assert_exhaustive(&[0]);
76    }
77
78    #[test]
79    fn constant_polynomial() {
80        assert_exhaustive(&[1]);
81        assert_exhaustive(&[42]);
82        assert_exhaustive(&[128]);
83        assert_exhaustive(&[255]);
84    }
85
86    #[test]
87    fn linear_polynomial() {
88        assert_exhaustive(&[5, 3]);
89        assert_exhaustive(&[0, 1]);
90        assert_exhaustive(&[255, 255]);
91    }
92
93    #[test]
94    fn quadratic_polynomial() {
95        assert_exhaustive(&[1, 0, 1]);
96        assert_exhaustive(&[0, 0, 1]);
97        assert_exhaustive(&[255, 128, 64]);
98    }
99
100    #[test]
101    fn cubic_polynomial() {
102        assert_exhaustive(&[0x12, 0x34, 0x56, 0x78]);
103        assert_exhaustive(&[1, 1, 1, 1]);
104        assert_exhaustive(&[0, 0, 0, 1]);
105    }
106
107    #[test]
108    fn high_degree_polynomial() {
109        assert_exhaustive(&[1, 2, 3, 4, 5, 6, 7, 8]);
110        assert_exhaustive(&[0, 0, 0, 0, 0, 0, 0, 1]);
111    }
112
113    #[test]
114    fn sparse_polynomial() {
115        assert_exhaustive(&[1, 0, 0, 0, 1]);
116        assert_exhaustive(&[0, 1, 0, 1, 0]);
117    }
118
119    #[test]
120    fn all_coefficients_max() {
121        assert_exhaustive(&[255, 255, 255, 255]);
122    }
123
124    #[test]
125    fn max_degree_monomial() {
126        let mut coefficients = [0u8; Polynomial::MAX_COEFFICIENTS as usize];
127
128        coefficients[Polynomial::MAX_DEGREE as usize] = 1;
129
130        assert_exhaustive(&coefficients);
131    }
132
133    #[test]
134    fn max_degree_all_ones() {
135        let coefficients = [1u8; Polynomial::MAX_COEFFICIENTS as usize];
136
137        assert_exhaustive(&coefficients);
138    }
139
140    #[test]
141    fn max_degree_all_max() {
142        let coefficients = [255u8; Polynomial::MAX_COEFFICIENTS as usize];
143
144        assert_exhaustive(&coefficients);
145    }
146
147    #[test]
148    fn chained_empty_slices() {
149        assert_exhaustive_chained(&[], &[]);
150    }
151
152    #[test]
153    fn chained_one_empty() {
154        assert_exhaustive_chained(&[1, 2, 3], &[]);
155        assert_exhaustive_chained(&[], &[1, 2, 3]);
156    }
157
158    #[test]
159    fn chained_equal_length() {
160        assert_exhaustive_chained(&[1, 2, 3], &[4, 5, 6]);
161        assert_exhaustive_chained(&[0, 0, 0], &[0, 0, 1]);
162        assert_exhaustive_chained(&[255, 255], &[255, 255]);
163    }
164
165    #[test]
166    fn chained_unequal_length() {
167        assert_exhaustive_chained(&[1], &[2, 3, 4, 5]);
168        assert_exhaustive_chained(&[1, 2, 3, 4], &[5]);
169    }
170
171    #[test]
172    fn matches_eval_coefficients_at() {
173        let coefficients = [0x12u8, 0x34, 0x56, 0x78];
174
175        for x in 0..=255u8 {
176            assert_eq!(
177                Polynomial::eval_coefficient_iter_at(coefficients.iter().copied(), x),
178                Polynomial::eval_coefficients_at(&coefficients, x)
179            );
180        }
181    }
182}
ps_ecc/polynomial/methods/eval_coefficient_iter_at.rs

ps_ecc/polynomial/methods/
eval_coefficient_iter_at.rs
