openvm_native_recursion/
utils.rs

1use openvm_native_compiler::ir::{Builder, CanSelect, Config, Felt, MemVariable, Var};
2use openvm_stark_backend::p3_field::{
3    absorb_radix_bits, coset::TwoAdicMultiplicativeCoset, PrimeCharacteristicRing, PrimeField32,
4    TwoAdicField,
5};
6use openvm_stark_sdk::config::FriParameters;
7
8use crate::fri::{types::FriConfigVariable, TwoAdicMultiplicativeCosetVariable};
9
10pub fn const_fri_config<C: Config>(
11    builder: &mut Builder<C>,
12    params: &FriParameters,
13) -> FriConfigVariable<C> {
14    let two_adicity = C::F::TWO_ADICITY;
15    let generators = builder.array(two_adicity + 1);
16    let subgroups = builder.array(two_adicity + 1);
17    for i in 0..=C::F::TWO_ADICITY {
18        let constant_generator = C::F::two_adic_generator(i);
19        builder.set(&generators, i, constant_generator);
20
21        let constant_domain = TwoAdicMultiplicativeCoset::new(C::F::ONE, i).unwrap();
22        let domain_value: TwoAdicMultiplicativeCosetVariable<_> = builder.constant(constant_domain);
23        // ATTENTION: here must use `builder.set_value`. `builder.set` will convert `Usize::Const`
24        // to `Usize::Var` because it calls `builder.eval`.
25        builder.set_value(&subgroups, i, domain_value);
26    }
27    FriConfigVariable {
28        log_blowup: params.log_blowup,
29        blowup: 1 << params.log_blowup,
30        log_final_poly_len: params.log_final_poly_len,
31        num_queries: params.num_queries,
32        commit_proof_of_work_bits: params.commit_proof_of_work_bits,
33        query_proof_of_work_bits: params.query_proof_of_work_bits,
34        subgroups,
35        generators,
36    }
37}
38
39/// Reference: <https://github.com/Plonky3/Plonky3/blob/622375885320ac6bf3c338001760ed8f2230e3cb/field/src/helpers.rs#L136>
40pub fn reduce_32<C: Config>(builder: &mut Builder<C>, vals: &[Felt<C::F>]) -> Var<C::N> {
41    let mut power = C::N::ONE;
42    let result: Var<C::N> = builder.eval(C::N::ZERO);
43    for val in vals.iter() {
44        let val = builder.cast_felt_to_var(*val);
45        builder.assign(&result, result + val * power);
46        power *= C::N::from_usize(1usize << 32);
47    }
48    result
49}
50
51/// Reference: <https://github.com/Plonky3/Plonky3/blob/622375885320ac6bf3c338001760ed8f2230e3cb/field/src/helpers.rs#L149>
52pub fn split_32<C: Config>(builder: &mut Builder<C>, val: Var<C::N>, n: usize) -> Vec<Felt<C::F>> {
53    let felts = builder.var_to_64bits_f_circuit(val);
54    assert!(n <= felts.len());
55    felts[0..n].to_vec()
56}
57
58/// In-circuit equivalent of [`p3_field::reduce_packed`].
59pub fn reduce_packed<C: Config>(
60    builder: &mut Builder<C>,
61    vals: &[Felt<C::F>],
62    radix_bits: u32,
63) -> Var<C::N> {
64    debug_assert!((absorb_radix_bits::<C::F>() <= radix_bits) && (radix_bits < 64));
65    let base = C::N::from_u64(1u64 << radix_bits);
66    let result: Var<C::N> = builder.eval(C::N::ZERO);
67    for val in vals.iter().rev() {
68        let val = builder.cast_felt_to_var(*val);
69        builder.assign(&result, result * base + val);
70    }
71    result
72}
73
74/// In-circuit equivalent of [`p3_field::reduce_packed_shifted`].
75pub fn reduce_packed_shifted<C: Config>(
76    builder: &mut Builder<C>,
77    vals: &[Felt<C::F>],
78    radix_bits: u32,
79) -> Var<C::N> {
80    debug_assert!((radix_bits < 64) && ((C::F::ORDER_U32 as u64) < (1u64 << radix_bits)));
81    let base = C::N::from_u64(1u64 << radix_bits);
82    let result: Var<C::N> = builder.eval(C::N::ZERO);
83    for val in vals.iter().rev() {
84        let val = builder.cast_felt_to_var(*val);
85        builder.assign(&result, result * base + (val + C::N::ONE));
86    }
87    result
88}
89
90/// In-circuit equivalent of [`p3_field::split_pf_to_field_order_limbs`]: decompose `val` (a Var
91/// in `C::N`) into `n` little-endian base-|F| Felt limbs. Constraints are emitted so that the
92/// witnessed limbs are exactly the canonical decomposition.
93pub fn split_pf_to_field_order_limbs<C: Config>(
94    builder: &mut Builder<C>,
95    val: Var<C::N>,
96    n: usize,
97) -> Vec<Felt<C::F>> {
98    builder.var_to_field_order_f_limbs_circuit(val, n)
99}
100
101pub fn absorb_radix_bits_for_config<C: Config>() -> u32 {
102    absorb_radix_bits::<C::F>()
103}
104
105/// Eval two expressions, return in the reversed order if cond == 1. Otherwise, return in the
106/// original order. This is a helper function for optimal performance.
107pub fn cond_eval<C: Config, V: MemVariable<C, Expression: Clone> + CanSelect<C>>(
108    builder: &mut Builder<C>,
109    cond: Var<C::N>,
110    v1: impl Into<V::Expression>,
111    v2: impl Into<V::Expression>,
112) -> [V; 2] {
113    let a: V;
114    let b: V;
115    if builder.flags.static_only {
116        let v1: V = builder.eval(v1.into());
117        let v2: V = builder.eval(v2.into());
118        a = V::select(builder, cond, v2.clone(), v1.clone());
119        b = V::select(builder, cond, v1, v2);
120    } else {
121        let v1 = v1.into();
122        let v2 = v2.into();
123        a = builder.uninit();
124        b = builder.uninit();
125        builder.if_eq(cond, C::N::ONE).then_or_else(
126            |builder| {
127                builder.assign(&a, v2.clone());
128                builder.assign(&b, v1.clone());
129            },
130            |builder| {
131                builder.assign(&a, v1.clone());
132                builder.assign(&b, v2.clone());
133            },
134        );
135    }
136    [a, b]
137}
openvm_native_recursion/utils.rs

openvm_native_recursion/
utils.rs
