openvm_native_recursion/
utils.rs

1use openvm_native_compiler::ir::{Builder, CanSelect, Config, Felt, MemVariable, Var};
2use openvm_stark_backend::{
3    p3_commit::TwoAdicMultiplicativeCoset,
4    p3_field::{FieldAlgebra, 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 {
22            log_n: i,
23            shift: C::F::ONE,
24        };
25        let domain_value: TwoAdicMultiplicativeCosetVariable<_> = builder.constant(constant_domain);
26        // ATTENTION: here must use `builder.set_value`. `builder.set` will convert `Usize::Const`
27        // to `Usize::Var` because it calls `builder.eval`.
28        builder.set_value(&subgroups, i, domain_value);
29    }
30    FriConfigVariable {
31        log_blowup: params.log_blowup,
32        blowup: 1 << params.log_blowup,
33        log_final_poly_len: params.log_final_poly_len,
34        num_queries: params.num_queries,
35        proof_of_work_bits: params.proof_of_work_bits,
36        subgroups,
37        generators,
38    }
39}
40
41/// Reference: <https://github.com/Plonky3/Plonky3/blob/622375885320ac6bf3c338001760ed8f2230e3cb/field/src/helpers.rs#L136>
42pub fn reduce_32<C: Config>(builder: &mut Builder<C>, vals: &[Felt<C::F>]) -> Var<C::N> {
43    let mut power = C::N::ONE;
44    let result: Var<C::N> = builder.eval(C::N::ZERO);
45    for val in vals.iter() {
46        let val = builder.cast_felt_to_var(*val);
47        builder.assign(&result, result + val * power);
48        power *= C::N::from_canonical_usize(1usize << 32);
49    }
50    result
51}
52
53/// Reference: <https://github.com/Plonky3/Plonky3/blob/622375885320ac6bf3c338001760ed8f2230e3cb/field/src/helpers.rs#L149>
54pub fn split_32<C: Config>(builder: &mut Builder<C>, val: Var<C::N>, n: usize) -> Vec<Felt<C::F>> {
55    let felts = builder.var_to_64bits_f_circuit(val);
56    assert!(n <= felts.len());
57    felts[0..n].to_vec()
58}
59
60/// Eval two expressions, return in the reversed order if cond == 1. Otherwise, return in the original order.
61/// This is a helper function for optimal performance.
62pub fn cond_eval<C: Config, V: MemVariable<C, Expression: Clone> + CanSelect<C>>(
63    builder: &mut Builder<C>,
64    cond: Var<C::N>,
65    v1: impl Into<V::Expression>,
66    v2: impl Into<V::Expression>,
67) -> [V; 2] {
68    let a: V;
69    let b: V;
70    if builder.flags.static_only {
71        let v1: V = builder.eval(v1.into());
72        let v2: V = builder.eval(v2.into());
73        a = V::select(builder, cond, v2.clone(), v1.clone());
74        b = V::select(builder, cond, v1, v2);
75    } else {
76        let v1 = v1.into();
77        let v2 = v2.into();
78        a = builder.uninit();
79        b = builder.uninit();
80        builder.if_eq(cond, C::N::ONE).then_or_else(
81            |builder| {
82                builder.assign(&a, v2.clone());
83                builder.assign(&b, v1.clone());
84            },
85            |builder| {
86                builder.assign(&a, v1.clone());
87                builder.assign(&b, v2.clone());
88            },
89        );
90    }
91    [a, b]
92}