sp1_core_machine/bytes/
mod.rs

1pub mod air;
2pub mod columns;
3// pub mod event;
4// pub mod opcode;
5pub mod trace;
6pub mod utils;
7
8use sp1_core_executor::{events::ByteLookupEvent, ByteOpcode};
9
10use core::borrow::BorrowMut;
11use std::marker::PhantomData;
12
13use itertools::Itertools;
14use p3_field::Field;
15use p3_matrix::dense::RowMajorMatrix;
16
17use self::{
18    columns::{BytePreprocessedCols, NUM_BYTE_PREPROCESSED_COLS},
19    utils::shr_carry,
20};
21use crate::{bytes::trace::NUM_ROWS, utils::zeroed_f_vec};
22
23/// The number of different byte operations.
24pub const NUM_BYTE_OPS: usize = 9;
25
26/// A chip for computing byte operations.
27///
28/// The chip contains a preprocessed table of all possible byte operations. Other chips can then
29/// use lookups into this table to compute their own operations.
30#[derive(Debug, Clone, Copy, Default)]
31pub struct ByteChip<F>(PhantomData<F>);
32
33impl<F: Field> ByteChip<F> {
34    /// Creates the preprocessed byte trace.
35    ///
36    /// This function returns a `trace` which is a matrix containing all possible byte operations.
37    pub fn trace() -> RowMajorMatrix<F> {
38        // The trace containing all values, with all multiplicities set to zero.
39        let mut initial_trace = RowMajorMatrix::new(
40            zeroed_f_vec(NUM_ROWS * NUM_BYTE_PREPROCESSED_COLS),
41            NUM_BYTE_PREPROCESSED_COLS,
42        );
43
44        // Record all the necessary operations for each byte lookup.
45        let opcodes = ByteOpcode::all();
46
47        // Iterate over all options for pairs of bytes `a` and `b`.
48        for (row_index, (b, c)) in (0..=u8::MAX).cartesian_product(0..=u8::MAX).enumerate() {
49            let b = b as u8;
50            let c = c as u8;
51            let col: &mut BytePreprocessedCols<F> = initial_trace.row_mut(row_index).borrow_mut();
52
53            // Set the values of `b` and `c`.
54            col.b = F::from_canonical_u8(b);
55            col.c = F::from_canonical_u8(c);
56
57            // Iterate over all operations for results and updating the table map.
58            for opcode in opcodes.iter() {
59                match opcode {
60                    ByteOpcode::AND => {
61                        let and = b & c;
62                        col.and = F::from_canonical_u8(and);
63                        ByteLookupEvent::new(*opcode, and as u16, 0, b, c)
64                    }
65                    ByteOpcode::OR => {
66                        let or = b | c;
67                        col.or = F::from_canonical_u8(or);
68                        ByteLookupEvent::new(*opcode, or as u16, 0, b, c)
69                    }
70                    ByteOpcode::XOR => {
71                        let xor = b ^ c;
72                        col.xor = F::from_canonical_u8(xor);
73                        ByteLookupEvent::new(*opcode, xor as u16, 0, b, c)
74                    }
75                    ByteOpcode::SLL => {
76                        let sll = b << (c & 7);
77                        col.sll = F::from_canonical_u8(sll);
78                        ByteLookupEvent::new(*opcode, sll as u16, 0, b, c)
79                    }
80                    ByteOpcode::U8Range => ByteLookupEvent::new(*opcode, 0, 0, b, c),
81                    ByteOpcode::ShrCarry => {
82                        let (res, carry) = shr_carry(b, c);
83                        col.shr = F::from_canonical_u8(res);
84                        col.shr_carry = F::from_canonical_u8(carry);
85                        ByteLookupEvent::new(*opcode, res as u16, carry, b, c)
86                    }
87                    ByteOpcode::LTU => {
88                        let ltu = b < c;
89                        col.ltu = F::from_bool(ltu);
90                        ByteLookupEvent::new(*opcode, ltu as u16, 0, b, c)
91                    }
92                    ByteOpcode::MSB => {
93                        let msb = (b & 0b1000_0000) != 0;
94                        col.msb = F::from_bool(msb);
95                        ByteLookupEvent::new(*opcode, msb as u16, 0, b, 0)
96                    }
97                    ByteOpcode::U16Range => {
98                        let v = ((b as u32) << 8) + c as u32;
99                        col.value_u16 = F::from_canonical_u32(v);
100                        ByteLookupEvent::new(*opcode, v as u16, 0, 0, 0)
101                    }
102                };
103            }
104        }
105
106        initial_trace
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    #![allow(clippy::print_stdout)]
113
114    use p3_baby_bear::BabyBear;
115    use std::time::Instant;
116
117    use super::*;
118
119    #[test]
120    pub fn test_trace_and_map() {
121        let start = Instant::now();
122        ByteChip::<BabyBear>::trace();
123        println!("trace and map: {:?}", start.elapsed());
124    }
125}
sp1_core_machine/bytes/mod.rs

sp1_core_machine/bytes/
mod.rs
