1use std::{any::TypeId, array};
23use openvm_stark_backend::p3_field::FieldAlgebra;
4use openvm_stark_sdk::p3_baby_bear::BabyBear;
56use super::{Array, Builder, Config, DslIr, Felt, MemIndex, Var};
78impl<C: Config> Builder<C> {
9/// Converts a felt to bits. Will result in a failed assertion if `num` has more than `num_bits` bits.
10 /// Only works for C::F = BabyBear
11pub fn num2bits_f(&mut self, num: Felt<C::F>, num_bits: u32) -> Array<C, Var<C::N>> {
12assert_eq!(TypeId::of::<C::F>(), TypeId::of::<BabyBear>());
1314self.push(DslIr::HintBitsF(num, num_bits));
15let output = self.dyn_array::<Felt<_>>(num_bits as usize);
1617let 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
20let 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
23let suffix_bit_sum: Felt<_> = self.eval(C::F::ZERO);
24for i in 0..num_bits as usize {
25let index = MemIndex {
26 index: i.into(),
27 offset: 0,
28 size: 1,
29 };
30self.push(DslIr::StoreHintWord(output.ptr(), index));
3132let bit = self.get(&output, i);
33self.assert_felt_eq(bit * (bit - C::F::ONE), C::F::ZERO);
34self.assign(&sum, sum + bit * C::F::from_canonical_u32(1 << i));
35if i == 26 {
36self.assign(&prefix_sum, sum);
37 }
38if i > 26 {
39self.assign(&suffix_bit_sum, suffix_bit_sum + bit);
40 }
41 }
42self.assert_felt_eq(sum, num);
4344// 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 overflow,
50 // we may check that:
51 // * if `num_bits < 27`, then `b[30] = 0`, so overflow is impossible.
52 // In this case, `suffix_bit_sum = 0`, so the check below passes.
53 // * if `num_bits >= 27`, then we must check:
54 // if `suffix_bit_sum = b[27] + ... + b[30] = 4`, then `prefix_sum = b[0] + ... + b[26] * 2^26 = 0`
55let suffix_bit_sum_var = self.cast_felt_to_var(suffix_bit_sum);
56self.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 });
6061// Cast Array<C, Felt<C::F>> to Array<C, Var<C::N>>
62Array::Dyn(output.ptr(), output.len())
63 }
6465/// Converts a felt to bits inside a circuit.
66pub fn num2bits_f_circuit(&mut self, num: Felt<C::F>) -> Vec<Var<C::N>> {
67let mut output = Vec::new();
68for _ in 0..32 {
69 output.push(self.uninit());
70 }
7172self.push(DslIr::CircuitNum2BitsF(num, output.clone()));
7374 output
75 }
7677/// Convert bits to a variable inside a circuit.
78pub fn bits2num_v_circuit(&mut self, bits: &[Var<C::N>]) -> Var<C::N> {
79let result: Var<_> = self.eval(C::N::ZERO);
80for i in 0..bits.len() {
81self.assign(&result, result + bits[i] * C::N::from_canonical_u32(1 << i));
82 }
83 result
84 }
8586/// Decompose a Var into 64-bit Felt limbs.
87pub fn var_to_64bits_f_circuit(&mut self, value: Var<C::N>) -> [Felt<C::F>; 4] {
88let ret = array::from_fn(|_| self.uninit());
89self.push(DslIr::CircuitVarTo64BitsF(value, ret));
90 ret
91 }
92}