1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  //! Work with sparse and dense polynomials.
 20  
 21  use crate::fft::{EvaluationDomain, Evaluations};
 22  use alphavm_fields::{Field, PrimeField};
 23  use alphavm_utilities::{cfg_iter_mut, serialize::*, SerializationError};
 24  use Polynomial::*;
 25  
 26  use anyhow::{ensure, Result};
 27  use std::{borrow::Cow, convert::TryInto};
 28  
 29  #[cfg(not(feature = "serial"))]
 30  use rayon::prelude::*;
 31  
 32  mod dense;
 33  pub use dense::DensePolynomial;
 34  
 35  mod sparse;
 36  pub use sparse::SparsePolynomial;
 37  
 38  mod multiplier;
 39  pub use multiplier::*;
 40  
 41  /// Represents either a sparse polynomial or a dense one.
 42  #[derive(Clone, Debug, PartialEq, Eq)]
 43  pub enum Polynomial<'a, F: Field> {
 44      /// Represents the case where `self` is a sparse polynomial
 45      Sparse(Cow<'a, SparsePolynomial<F>>),
 46      /// Represents the case where `self` is a dense polynomial
 47      Dense(Cow<'a, DensePolynomial<F>>),
 48  }
 49  
 50  impl<F: Field> CanonicalSerialize for Polynomial<'_, F> {
 51      fn serialize_with_mode<W: Write>(&self, writer: W, compress: Compress) -> Result<(), SerializationError> {
 52          match self {
 53              Sparse(p) => {
 54                  let p: DensePolynomial<F> = p.clone().into_owned().into();
 55                  CanonicalSerialize::serialize_with_mode(&p.coeffs, writer, compress)
 56              }
 57              Dense(p) => CanonicalSerialize::serialize_with_mode(&p.coeffs, writer, compress),
 58          }
 59      }
 60  
 61      fn serialized_size(&self, mode: Compress) -> usize {
 62          match self {
 63              Sparse(p) => {
 64                  let p: DensePolynomial<F> = p.clone().into_owned().into();
 65                  p.serialized_size(mode)
 66              }
 67              Dense(p) => p.serialized_size(mode),
 68          }
 69      }
 70  }
 71  
 72  impl<F: Field> Valid for Polynomial<'_, F> {
 73      fn check(&self) -> Result<(), SerializationError> {
 74          // Check that the polynomial contains a trailing zero coefficient.
 75          let has_trailing_zero = match self {
 76              Sparse(p) => p.coeffs().last().map(|(_, c)| c.is_zero()),
 77              Dense(p) => p.coeffs.last().map(|c| c.is_zero()),
 78          };
 79          // Fail if the trailing coefficient is zero.
 80          match has_trailing_zero {
 81              Some(true) => Err(SerializationError::InvalidData),
 82              Some(false) | None => Ok(()),
 83          }
 84      }
 85  }
 86  
 87  impl<F: Field> CanonicalDeserialize for Polynomial<'_, F> {
 88      fn deserialize_with_mode<R: Read>(
 89          reader: R,
 90          compress: Compress,
 91          validate: Validate,
 92      ) -> Result<Self, SerializationError> {
 93          DensePolynomial::<F>::deserialize_with_mode(reader, compress, validate).map(|e| Self::Dense(Cow::Owned(e)))
 94      }
 95  }
 96  
 97  impl<F: Field> From<DensePolynomial<F>> for Polynomial<'_, F> {
 98      fn from(other: DensePolynomial<F>) -> Self {
 99          Dense(Cow::Owned(other))
100      }
101  }
102  
103  impl<'a, F: Field> From<&'a DensePolynomial<F>> for Polynomial<'a, F> {
104      fn from(other: &'a DensePolynomial<F>) -> Self {
105          Dense(Cow::Borrowed(other))
106      }
107  }
108  
109  impl<F: Field> From<SparsePolynomial<F>> for Polynomial<'_, F> {
110      fn from(other: SparsePolynomial<F>) -> Self {
111          Sparse(Cow::Owned(other))
112      }
113  }
114  
115  impl<'a, F: Field> From<&'a SparsePolynomial<F>> for Polynomial<'a, F> {
116      fn from(other: &'a SparsePolynomial<F>) -> Self {
117          Sparse(Cow::Borrowed(other))
118      }
119  }
120  
121  #[allow(clippy::from_over_into)]
122  impl<F: Field> Into<DensePolynomial<F>> for Polynomial<'_, F> {
123      fn into(self) -> DensePolynomial<F> {
124          match self {
125              Dense(p) => p.into_owned(),
126              Sparse(p) => p.into_owned().into(),
127          }
128      }
129  }
130  
131  impl<F: Field> TryInto<SparsePolynomial<F>> for Polynomial<'_, F> {
132      type Error = ();
133  
134      fn try_into(self) -> Result<SparsePolynomial<F>, ()> {
135          match self {
136              Sparse(p) => Ok(p.into_owned()),
137              _ => Err(()),
138          }
139      }
140  }
141  
142  impl<'a, F: Field> Polynomial<'a, F> {
143      /// The zero polynomial.
144      pub fn zero() -> Self {
145          Sparse(Cow::Owned(SparsePolynomial::zero()))
146      }
147  
148      /// Checks if the given polynomial is zero.
149      pub fn is_zero(&self) -> bool {
150          match self {
151              Sparse(s) => s.is_zero(),
152              Dense(d) => d.is_zero(),
153          }
154      }
155  
156      /// Return the degree of `self.
157      pub fn degree(&self) -> usize {
158          match self {
159              Sparse(s) => s.degree(),
160              Dense(d) => d.degree(),
161          }
162      }
163  
164      #[inline]
165      pub fn leading_coefficient(&self) -> Option<&F> {
166          match self {
167              Sparse(p) => p.coeffs().last().map(|(_, c)| c),
168              Dense(p) => p.last(),
169          }
170      }
171  
172      #[inline]
173      pub fn as_dense(&self) -> Option<&DensePolynomial<F>> {
174          match self {
175              Dense(p) => Some(p.as_ref()),
176              _ => None,
177          }
178      }
179  
180      #[inline]
181      pub fn to_dense(&self) -> Cow<'_, DensePolynomial<F>> {
182          match self {
183              Dense(p) => Cow::Borrowed(p.as_ref()),
184              Sparse(p) => Cow::Owned(p.clone().into_owned().into()),
185          }
186      }
187  
188      #[inline]
189      pub fn as_dense_mut(&mut self) -> Option<&mut DensePolynomial<F>> {
190          match self {
191              Dense(p) => Some(p.to_mut()),
192              _ => None,
193          }
194      }
195  
196      #[inline]
197      pub fn as_sparse(&self) -> Option<&SparsePolynomial<F>> {
198          match self {
199              Sparse(p) => Some(p.as_ref()),
200              _ => None,
201          }
202      }
203  
204      #[inline]
205      pub fn into_dense(&self) -> DensePolynomial<F> {
206          self.clone().into()
207      }
208  
209      #[inline]
210      pub fn evaluate(&self, point: F) -> F {
211          match self {
212              Sparse(p) => p.evaluate(point),
213              Dense(p) => p.evaluate(point),
214          }
215      }
216  
217      pub fn coeffs(&'a self) -> Box<dyn Iterator<Item = (usize, &'a F)> + 'a> {
218          match self {
219              Sparse(p) => Box::new(p.coeffs().map(|(c, f)| (*c, f))),
220              Dense(p) => Box::new(p.coeffs.iter().enumerate()),
221          }
222      }
223  
224      /// Divide self by another (sparse or dense) polynomial, and returns the
225      /// quotient and remainder.
226      pub fn divide_with_q_and_r(&self, divisor: &Self) -> Result<(DensePolynomial<F>, DensePolynomial<F>)> {
227          ensure!(!divisor.is_zero(), "Dividing by zero polynomial is undefined");
228  
229          if self.is_zero() {
230              Ok((DensePolynomial::zero(), DensePolynomial::zero()))
231          } else if self.degree() < divisor.degree() {
232              Ok((DensePolynomial::zero(), self.clone().into()))
233          } else {
234              // Now we know that self.degree() >= divisor.degree();
235              let mut quotient = vec![F::zero(); self.degree() - divisor.degree() + 1];
236              let mut remainder: DensePolynomial<F> = self.clone().into();
237              // Can unwrap here because we know self is not zero.
238              let divisor_leading_inv = divisor.leading_coefficient().unwrap().inverse().unwrap();
239              while !remainder.is_zero() && remainder.degree() >= divisor.degree() {
240                  let cur_q_coeff = *remainder.coeffs.last().unwrap() * divisor_leading_inv;
241                  let cur_q_degree = remainder.degree() - divisor.degree();
242                  quotient[cur_q_degree] = cur_q_coeff;
243  
244                  if let Sparse(p) = divisor {
245                      for (i, div_coeff) in p.coeffs() {
246                          remainder[cur_q_degree + i] -= &(cur_q_coeff * div_coeff);
247                      }
248                  } else if let Dense(p) = divisor {
249                      for (i, div_coeff) in p.iter().enumerate() {
250                          remainder[cur_q_degree + i] -= &(cur_q_coeff * div_coeff);
251                      }
252                  }
253  
254                  while let Some(true) = remainder.coeffs.last().map(|c| c.is_zero()) {
255                      remainder.coeffs.pop();
256                  }
257              }
258              Ok((DensePolynomial::from_coefficients_vec(quotient), remainder))
259          }
260      }
261  }
262  
263  impl<F: PrimeField> Polynomial<'_, F> {
264      /// Construct `Evaluations` by evaluating a polynomial over the domain
265      /// `domain`.
266      pub fn evaluate_over_domain(poly: impl Into<Self>, domain: EvaluationDomain<F>) -> Evaluations<F> {
267          let poly = poly.into();
268          poly.eval_over_domain_helper(domain)
269      }
270  
271      fn eval_over_domain_helper(self, domain: EvaluationDomain<F>) -> Evaluations<F> {
272          match self {
273              Sparse(Cow::Borrowed(s)) => {
274                  let evals = domain.elements().map(|elem| s.evaluate(elem)).collect();
275                  Evaluations::from_vec_and_domain(evals, domain)
276              }
277              Sparse(Cow::Owned(s)) => {
278                  let evals = domain.elements().map(|elem| s.evaluate(elem)).collect();
279                  Evaluations::from_vec_and_domain(evals, domain)
280              }
281              Dense(Cow::Borrowed(d)) => {
282                  if d.degree() >= domain.size() {
283                      d.coeffs
284                          .chunks(domain.size())
285                          .map(|d| Evaluations::from_vec_and_domain(domain.fft(d), domain))
286                          .fold(Evaluations::from_vec_and_domain(vec![F::zero(); domain.size()], domain), |mut acc, e| {
287                              cfg_iter_mut!(acc.evaluations).zip(e.evaluations).for_each(|(a, e)| *a += e);
288                              acc
289                          })
290                  } else {
291                      Evaluations::from_vec_and_domain(domain.fft(&d.coeffs), domain)
292                  }
293              }
294              Dense(Cow::Owned(mut d)) => {
295                  if d.degree() >= domain.size() {
296                      d.coeffs
297                          .chunks(domain.size())
298                          .map(|d| Evaluations::from_vec_and_domain(domain.fft(d), domain))
299                          .fold(Evaluations::from_vec_and_domain(vec![F::zero(); domain.size()], domain), |mut acc, e| {
300                              cfg_iter_mut!(acc.evaluations).zip(e.evaluations).for_each(|(a, e)| *a += e);
301                              acc
302                          })
303                  } else {
304                      domain.fft_in_place(&mut d.coeffs);
305                      Evaluations::from_vec_and_domain(d.coeffs, domain)
306                  }
307              }
308          }
309      }
310  }