sp1_core_machine/bytes/
mod.rs

1pub mod air;
2pub mod columns;
3pub mod trace;
4
5use sp1_core_executor::ByteOpcode;
6
7use core::borrow::BorrowMut;
8use std::marker::PhantomData;
9
10use itertools::Itertools;
11use slop_algebra::Field;
12use std::mem::MaybeUninit;
13
14use self::columns::{BytePreprocessedCols, NUM_BYTE_PREPROCESSED_COLS};
15use crate::bytes::trace::NUM_ROWS;
16
17/// The number of different byte operations in the byte table.
18pub const NUM_BYTE_OPS: usize = 6;
19
20/// A chip for computing byte operations.
21///
22/// The chip contains a preprocessed table of all possible byte operations. Other chips can then
23/// use lookups into this table to compute their own operations.
24#[derive(Debug, Clone, Copy, Default)]
25pub struct ByteChip<F>(PhantomData<F>);
26
27impl<F: Field> ByteChip<F> {
28    /// Creates the preprocessed byte trace.
29    ///
30    /// This writes the `buffer` which is a matrix containing all possible byte operations.
31    pub fn trace(buffer: &mut [MaybeUninit<F>]) {
32        let buffer_ptr = buffer.as_mut_ptr() as *mut F;
33        let values = unsafe {
34            core::slice::from_raw_parts_mut(buffer_ptr, NUM_BYTE_PREPROCESSED_COLS * NUM_ROWS)
35        };
36
37        // Record all the necessary operations for each byte lookup.
38        let opcodes = ByteOpcode::byte_table();
39
40        // Iterate over all options for pairs of bytes `a` and `b`.
41        for (row_index, (b, c)) in (0..=u8::MAX).cartesian_product(0..=u8::MAX).enumerate() {
42            let b = b as u8;
43            let c = c as u8;
44            let start = row_index * NUM_BYTE_PREPROCESSED_COLS;
45            let end = (row_index + 1) * NUM_BYTE_PREPROCESSED_COLS;
46            let col: &mut BytePreprocessedCols<F> = values[start..end].borrow_mut();
47
48            // Set the values of `b` and `c`.
49            col.b = F::from_canonical_u8(b);
50            col.c = F::from_canonical_u8(c);
51
52            // Iterate over all operations for results and updating the table map.
53            for opcode in opcodes.iter() {
54                match opcode {
55                    ByteOpcode::AND => {
56                        let and = b & c;
57                        col.and = F::from_canonical_u8(and);
58                    }
59                    ByteOpcode::OR => {
60                        let or = b | c;
61                        col.or = F::from_canonical_u8(or);
62                    }
63                    ByteOpcode::XOR => {
64                        let xor = b ^ c;
65                        col.xor = F::from_canonical_u8(xor);
66                    }
67                    ByteOpcode::U8Range => {}
68                    ByteOpcode::LTU => {
69                        let ltu = b < c;
70                        col.ltu = F::from_bool(ltu);
71                    }
72                    ByteOpcode::MSB => {
73                        let msb = (b & 0b1000_0000) != 0;
74                        col.msb = F::from_bool(msb);
75                    }
76                    _ => panic!("invalid opcode found in byte table"),
77                };
78            }
79        }
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    #![allow(clippy::print_stdout)]
86
87    use sp1_primitives::SP1Field;
88    use std::time::Instant;
89
90    use super::*;
91
92    #[test]
93    pub fn test_trace_and_map() {
94        let mut vec: Vec<SP1Field> = Vec::with_capacity(NUM_ROWS * NUM_BYTE_PREPROCESSED_COLS);
95        let start = Instant::now();
96        ByteChip::<SP1Field>::trace(vec.spare_capacity_mut());
97        println!("trace and map: {:?}", start.elapsed());
98    }
99}
sp1_core_machine/bytes/mod.rs

sp1_core_machine/bytes/
mod.rs
