openvm_native_compiler/ir/
bits.rs

1use std::{any::TypeId, array};
2
3use openvm_stark_backend::p3_field::FieldAlgebra;
4use openvm_stark_sdk::p3_baby_bear::BabyBear;
5
6use super::{Array, Builder, Config, DslIr, Felt, MemIndex, Var};
7
8impl<C: Config> Builder<C> {
9    /// Converts a felt to bits. Will result in a failed assertion if `num` has more than `num_bits`
10    /// bits. Only works for C::F = BabyBear
11    pub fn num2bits_f(&mut self, num: Felt<C::F>, num_bits: u32) -> Array<C, Var<C::N>> {
12        assert_eq!(TypeId::of::<C::F>(), TypeId::of::<BabyBear>());
13
14        self.push(DslIr::HintBitsF(num, num_bits));
15        let output = self.dyn_array::<Felt<_>>(num_bits as usize);
16
17        let sum: Felt<_> = self.eval(C::F::ZERO);
18        // if `num_bits >= 27`, this will be used to compute b_0 + ... + b_26 * 2^26
19        // otherwise, this will be 0
20        let prefix_sum: Felt<_> = self.eval(C::F::ZERO);
21        // if `num_bits >= 27`, this will be used to compute b_27 + ... + b_30
22        // otherwise, this will be 0
23        let suffix_bit_sum: Felt<_> = self.eval(C::F::ZERO);
24        for i in 0..num_bits as usize {
25            let index = MemIndex {
26                index: i.into(),
27                offset: 0,
28                size: 1,
29            };
30            self.push(DslIr::StoreHintWord(output.ptr(), index));
31
32            let bit = self.get(&output, i);
33            self.assert_felt_eq(bit * (bit - C::F::ONE), C::F::ZERO);
34            self.assign(&sum, sum + bit * C::F::from_canonical_u32(1 << i));
35            if i == 26 {
36                self.assign(&prefix_sum, sum);
37            }
38            if i > 26 {
39                self.assign(&suffix_bit_sum, suffix_bit_sum + bit);
40            }
41        }
42        self.assert_felt_eq(sum, num);
43
44        // Check that the bits represent the number without overflow.
45        // If F is BabyBear, then any element of F can be represented either as:
46        //    * 2^30 + ... + 2^x + y for y in [0, 2^(x - 1)) and 27 < x <= 30
47        //    * 2^30 + ... + 2^27
48        //    * y for y in [0, 2^27)
49        // To check that bits `b[0], ..., b[30]` represent `num = b[0] + ... + b[30] * 2^30` without
50        // overflow, we may check that:
51        //    * if `num_bits < 27`, then `b[30] = 0`, so overflow is impossible. In this case,
52        //      `suffix_bit_sum = 0`, so the check below passes.
53        //    * if `num_bits >= 27`, then we must check: if `suffix_bit_sum = b[27] + ... + b[30] =
54        //      4`, then `prefix_sum = b[0] + ... + b[26] * 2^26 = 0`
55        let suffix_bit_sum_var = self.cast_felt_to_var(suffix_bit_sum);
56        self.if_eq(suffix_bit_sum_var, C::N::from_canonical_u32(4))
57            .then(|builder| {
58                builder.assert_felt_eq(prefix_sum, C::F::ZERO);
59            });
60
61        // Cast Array<C, Felt<C::F>> to Array<C, Var<C::N>>
62        Array::Dyn(output.ptr(), output.len())
63    }
64
65    /// Converts a felt to bits inside a circuit.
66    pub fn num2bits_f_circuit(&mut self, num: Felt<C::F>) -> Vec<Var<C::N>> {
67        let mut output = Vec::new();
68        for _ in 0..32 {
69            output.push(self.uninit());
70        }
71
72        self.push(DslIr::CircuitNum2BitsF(num, output.clone()));
73
74        output
75    }
76
77    /// Convert bits to a variable inside a circuit.
78    pub fn bits2num_v_circuit(&mut self, bits: &[Var<C::N>]) -> Var<C::N> {
79        let result: Var<_> = self.eval(C::N::ZERO);
80        for i in 0..bits.len() {
81            self.assign(&result, result + bits[i] * C::N::from_canonical_u32(1 << i));
82        }
83        result
84    }
85
86    /// Decompose a Var into 64-bit Felt limbs.
87    pub fn var_to_64bits_f_circuit(&mut self, value: Var<C::N>) -> [Felt<C::F>; 4] {
88        let ret = array::from_fn(|_| self.uninit());
89        self.push(DslIr::CircuitVarTo64BitsF(value, ret));
90        ret
91    }
92}
openvm_native_compiler/ir/bits.rs

openvm_native_compiler/ir/
bits.rs
