1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
use eth_types::Field;
use gadgets::{binary_number::AsBits, util::Expr};
use halo2_proofs::{
    circuit::Value,
    plonk::{Error, Expression},
};

use crate::evm_circuit::util::{
    constraint_builder::{ConstrainBuilderCommon, EVMConstraintBuilder},
    CachedRegion, Cell,
};

#[derive(Clone, Debug)]
pub struct BinaryNumberGadget<F, const N: usize> {
    pub(crate) bits: [Cell<F>; N],
}

impl<F: Field, const N: usize> BinaryNumberGadget<F, N> {
    pub(crate) fn construct(cb: &mut EVMConstraintBuilder<F>, value: Expression<F>) -> Self {
        let bits = array_init::array_init(|_| cb.query_bool());

        // the binary representation of value must be correct.
        cb.require_equal(
            "binary representation of value should be correct",
            value,
            bits.iter()
                .fold(0.expr(), |res, bit| bit.expr() + res * 2.expr()),
        );

        Self { bits }
    }

    pub(crate) fn assign<T>(
        &self,
        region: &mut CachedRegion<'_, '_, F>,
        offset: usize,
        value: T,
    ) -> Result<(), Error>
    where
        T: AsBits<N>,
    {
        for (c, v) in self.bits.iter().zip(value.as_bits().iter()) {
            c.assign(region, offset, Value::known(F::from(*v as u64)))?;
        }
        Ok(())
    }

    pub(crate) fn _value(&self) -> Expression<F> {
        self.bits
            .iter()
            .fold(0.expr(), |res, bit| bit.expr() + res * 2.expr())
    }

    pub(crate) fn value_equals<T>(&self, other: T) -> Expression<F>
    where
        T: AsBits<N>,
    {
        gadgets::util::and::expr(other.as_bits().iter().zip(self.bits.iter()).map(
            |(other_bit, self_bit)| {
                if *other_bit {
                    self_bit.expr()
                } else {
                    gadgets::util::not::expr(self_bit.expr())
                }
            },
        ))
    }
}