sp1_core_machine/operations/
bitwise.rs

1use crate::air::SP1Operation;
2use serde::{Deserialize, Serialize};
3use slop_algebra::Field;
4use sp1_core_executor::{
5    events::{ByteLookupEvent, ByteRecord},
6    ByteOpcode, Opcode,
7};
8use sp1_derive::{AlignedBorrow, InputExpr, InputParams, IntoShape, SP1OperationBuilder};
9use sp1_hypercube::air::SP1AirBuilder;
10use sp1_primitives::consts::WORD_BYTE_SIZE;
11use struct_reflection::{StructReflection, StructReflectionHelper};
12
13/// A set of columns needed to compute the bitwise operation over u64s in byte form.
14#[derive(
15    AlignedBorrow,
16    Default,
17    Debug,
18    Clone,
19    Copy,
20    Serialize,
21    Deserialize,
22    IntoShape,
23    SP1OperationBuilder,
24    StructReflection,
25)]
26#[repr(C)]
27pub struct BitwiseOperation<T> {
28    /// The result of the bitwise operation in bytes.
29    pub result: [T; WORD_BYTE_SIZE],
30}
31
32impl<F: Field> BitwiseOperation<F> {
33    pub fn populate_bitwise(
34        &mut self,
35        record: &mut impl ByteRecord,
36        a_u64: u64,
37        b_u64: u64,
38        c_u64: u64,
39        opcode: Opcode,
40    ) {
41        let a = a_u64.to_le_bytes();
42        let b = b_u64.to_le_bytes();
43        let c = c_u64.to_le_bytes();
44
45        self.result = a.map(|x| F::from_canonical_u8(x));
46
47        for ((b_a, b_b), b_c) in a.into_iter().zip(b).zip(c) {
48            let byte_event =
49                ByteLookupEvent { opcode: ByteOpcode::from(opcode), a: b_a as u16, b: b_b, c: b_c };
50            record.add_byte_lookup_event(byte_event);
51        }
52    }
53
54    /// Evaluate the bitwise operation over two u64s in byte form.
55    /// Assumes that `is_real` is boolean.
56    /// If `is_real` is true, constrains that the inputs are valid bytes.
57    /// If `is_real` is true, constrains that the `result` is the correct result.
58    fn eval_bitwise<AB: SP1AirBuilder>(
59        builder: &mut AB,
60        a: [AB::Expr; WORD_BYTE_SIZE],
61        b: [AB::Expr; WORD_BYTE_SIZE],
62        cols: BitwiseOperation<AB::Var>,
63        opcode: AB::Expr,
64        is_real: AB::Expr,
65    ) {
66        // The byte table will constrain that, if `is_real` is true,
67        //  - `a[i], b[i]` are bytes.
68        //  - `result[i] = op(a[i], b[i])`.
69        for i in 0..WORD_BYTE_SIZE {
70            builder.send_byte(
71                opcode.clone(),
72                cols.result[i],
73                a[i].clone(),
74                b[i].clone(),
75                is_real.clone(),
76            );
77        }
78    }
79}
80
81#[derive(Clone, InputParams, InputExpr)]
82pub struct BitwiseOperationInput<AB: SP1AirBuilder> {
83    pub a: [AB::Expr; WORD_BYTE_SIZE],
84    pub b: [AB::Expr; WORD_BYTE_SIZE],
85    pub cols: BitwiseOperation<AB::Var>,
86    pub opcode: AB::Expr,
87    pub is_real: AB::Expr,
88}
89
90impl<AB: SP1AirBuilder> SP1Operation<AB> for BitwiseOperation<AB::F> {
91    type Input = BitwiseOperationInput<AB>;
92    type Output = ();
93
94    fn lower(builder: &mut AB, input: Self::Input) {
95        BitwiseOperation::<AB::F>::eval_bitwise(
96            builder,
97            input.a,
98            input.b,
99            input.cols,
100            input.opcode,
101            input.is_real,
102        );
103    }
104}
sp1_core_machine/operations/bitwise.rs

sp1_core_machine/operations/
bitwise.rs
