1use crate::FieldExt;
 2use serde::{Deserialize, Serialize};
 3
 4#[derive(Serialize, Deserialize)]
 5pub struct EqPoly<F: FieldExt> {
 6    t: Vec<F>,
 7}
 8
 9impl<F: FieldExt> EqPoly<F> {
10    // `t` should be in big-endian.
11    pub fn new(t: Vec<F>) -> Self {
12        Self { t }
13    }
14
15    pub fn eval(&self, x: &[F]) -> F {
16        let mut result = F::ONE;
17        let one = F::ONE;
18
19        for i in 0..x.len() {
20            result *= self.t[i] * x[i] + (one - self.t[i]) * (one - x[i]);
21        }
22        result
23    }
24
25    // Copied from microsoft/Spartan
26    pub fn evals(&self) -> Vec<F> {
27        let ell = self.t.len();
28
29        let mut evals: Vec<F> = vec![F::ONE; 2usize.pow(ell as u32)];
30        let mut size = 1;
31        for j in 0..ell {
32            // in each iteration, we double the size of chis
33            size *= 2;
34            for i in (0..size).rev().step_by(2) {
35                // copy each element from the prior iteration twice
36                let scalar = evals[i / 2];
37                evals[i] = scalar * self.t[j];
38                evals[i - 1] = scalar - evals[i];
39            }
40        }
41        evals
42    }
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48    type F = halo2curves::secp256k1::Fp;
49    use halo2curves::ff::Field;
50
51    #[test]
52    fn test_eq_poly() {
53        let m = 4;
54        let t = (0..m).map(|i| F::from((i + 33) as u64)).collect::<Vec<F>>();
55        let eq_poly = EqPoly::new(t.clone());
56        let evals = eq_poly.evals();
57
58        let eval_first = eq_poly.eval(&[F::ZERO, F::ZERO, F::ZERO, F::ZERO]);
59        assert_eq!(eval_first, evals[0], "The first evaluation is not correct");
60
61        let eval_second = eq_poly.eval(&[F::ZERO, F::ZERO, F::ZERO, F::ONE]);
62        assert_eq!(
63            eval_second, evals[1],
64            "The second evaluation is not correct"
65        );
66
67        let eval_last = eq_poly.eval(&[F::ONE, F::ONE, F::ONE, F::ONE]);
68        assert_eq!(
69            eval_last,
70            evals[evals.len() - 1],
71            "The last evaluation is not correct"
72        );
73    }
74}