1use crate::FieldExt;
 2use serde::{Deserialize, Serialize};
 3
 4#[derive(Serialize, Deserialize)]
 5pub struct UniPoly<F: FieldExt> {
 6    pub coeffs: Vec<F>,
 7}
 8
 9impl<F: FieldExt> UniPoly<F> {
10    fn eval_cubic(&self, x: F) -> F {
11        // ax^3 + bx^2 + cx + d
12        let x_sq = x.square();
13        let x_cub = x_sq * x;
14
15        let a = self.coeffs[0];
16        let b = self.coeffs[1];
17        let c = self.coeffs[2];
18        let d = self.coeffs[3];
19
20        a * x_cub + b * x_sq + c * x + d
21    }
22
23    fn eval_quadratic(&self, x: F) -> F {
24        // ax^3 + bx^2 + cx + d
25        let x_sq = x.square();
26
27        let a = self.coeffs[0];
28        let b = self.coeffs[1];
29        let c = self.coeffs[2];
30
31        a * x_sq + b * x + c
32    }
33
34    pub fn eval(&self, x: F) -> F {
35        if self.coeffs.len() == 3 {
36            self.eval_quadratic(x)
37        } else {
38            self.eval_cubic(x)
39        }
40    }
41
42    pub fn interpolate(evals: &[F]) -> Self {
43        debug_assert!(
44            evals.len() == 4 || evals.len() == 3,
45            "Only cubic and quadratic polynomials are supported"
46        );
47
48        let two_inv = F::TWO_INV;
49
50        if evals.len() == 4 {
51            // ax^3 + bx^2 + cx + d
52            let six_inv = F::from(6u64).invert().unwrap();
53
54            let d = evals[0];
55            let a = six_inv
56                * (evals[3] - evals[2] - evals[2] - evals[2] + evals[1] + evals[1] + evals[1]
57                    - evals[0]);
58            let b = two_inv
59                * (evals[0] + evals[0] - evals[1] - evals[1] - evals[1] - evals[1] - evals[1]
60                    + evals[2]
61                    + evals[2]
62                    + evals[2]
63                    + evals[2]
64                    - evals[3]);
65
66            let c = evals[1] - d - a - b;
67
68            Self {
69                coeffs: vec![a, b, c, d],
70            }
71        } else {
72            let c = evals[0];
73            let a = (evals[2] - evals[1] - evals[1] + evals[0]) * two_inv;
74            let b = evals[1] - a - c;
75
76            Self {
77                coeffs: vec![a, b, c],
78            }
79        }
80    }
81}