1use crate::boolean::Boolean;
 2use crate::fields::fp::FpVar;
 3use crate::fields::FieldVar;
 4use ark_ff::PrimeField;
 5use ark_relations::r1cs::SynthesisError;
 6use ark_std::vec::Vec;
 7
 8pub mod vanishing_poly;
 9
10#[derive(Copy, Clone, Hash, Eq, PartialEq, Debug)]
11/// Defines an evaluation domain over a prime field. The domain is a coset of size `1<<dim`.
12///
13/// Native code corresponds to `ark-poly::univariate::domain::radix2`, but `ark-poly` only supports
14/// subgroup for now.
15///
16/// TODO: support cosets in `ark-poly`.
17pub struct Radix2Domain<F: PrimeField> {
18    /// generator of subgroup g
19    pub gen: F,
20    /// index of the quotient group (i.e. the `offset`)
21    pub offset: F,
22    /// dimension of evaluation domain
23    pub dim: u64,
24}
25
26impl<F: PrimeField> Radix2Domain<F> {
27    /// order of the domain
28    pub fn order(&self) -> usize {
29        1 << self.dim
30    }
31
32    /// Returns g, g^2, ..., g^{dim}
33    fn powers_of_gen(&self, dim: usize) -> Vec<F> {
34        let mut result = Vec::new();
35        let mut cur = self.gen;
36        for _ in 0..dim {
37            result.push(cur);
38            cur = cur * cur;
39        }
40        result
41    }
42
43    /// For domain `h<g>` with dimension `n`, `position` represented by `query_pos` in big endian form,
44    /// returns `h*g^{position}<g^{n-query_pos.len()}>`
45    pub fn query_position_to_coset(
46        &self,
47        query_pos: &[Boolean<F>],
48        coset_dim: u64,
49    ) -> Result<Vec<FpVar<F>>, SynthesisError> {
50        let mut coset_index = query_pos;
51        assert!(
52            query_pos.len() == self.dim as usize
53                || query_pos.len() == (self.dim - coset_dim) as usize
54        );
55        if query_pos.len() == self.dim as usize {
56            coset_index = &coset_index[0..(coset_index.len() - coset_dim as usize)];
57        }
58        let mut coset = Vec::new();
59        let powers_of_g = &self.powers_of_gen(self.dim as usize)[(coset_dim as usize)..];
60
61        let mut first_point_in_coset: FpVar<F> = FpVar::zero();
62        for i in 0..coset_index.len() {
63            let term = coset_index[i].select(&FpVar::constant(powers_of_g[i]), &FpVar::zero())?;
64            first_point_in_coset += &term;
65        }
66
67        first_point_in_coset *= &FpVar::Constant(self.offset);
68
69        coset.push(first_point_in_coset);
70        for i in 1..(1 << (coset_dim as usize)) {
71            let new_elem = &coset[i - 1] * &FpVar::Constant(self.gen);
72            coset.push(new_elem);
73        }
74
75        Ok(coset)
76    }
77}