sp1_core_machine/memory/
bump.rs

1use std::{
2    borrow::{Borrow, BorrowMut},
3    mem::{size_of, MaybeUninit},
4};
5
6use crate::{air::SP1CoreAirBuilder, utils::next_multiple_of_32};
7
8use super::MemoryAccessCols;
9use hashbrown::HashMap;
10use itertools::Itertools;
11use slop_air::{Air, BaseAir};
12use slop_algebra::{AbstractField, PrimeField32};
13use slop_matrix::Matrix;
14use sp1_core_executor::{
15    events::{ByteLookupEvent, ByteRecord, MemoryReadRecord, MemoryRecordEnum},
16    ByteOpcode, ExecutionRecord, Program,
17};
18use sp1_derive::AlignedBorrow;
19use sp1_hypercube::air::MachineAir;
20use struct_reflection::{StructReflection, StructReflectionHelper};
21
22pub(crate) const NUM_MEMORY_BUMP_COLS: usize = size_of::<MemoryBumpCols<u8>>();
23
24#[derive(AlignedBorrow, Clone, Copy, StructReflection)]
25#[repr(C)]
26pub struct MemoryBumpCols<T: Copy> {
27    pub access: MemoryAccessCols<T>,
28    pub clk_32_48: T,
29    pub clk_24_32: T,
30    pub clk_16_24: T,
31    pub clk_0_16: T,
32    pub addr: T,
33    pub is_real: T,
34}
35
36pub struct MemoryBumpChip {}
37
38impl MemoryBumpChip {
39    pub const fn new() -> Self {
40        Self {}
41    }
42}
43
44impl<F> BaseAir<F> for MemoryBumpChip {
45    fn width(&self) -> usize {
46        NUM_MEMORY_BUMP_COLS
47    }
48}
49
50impl<F: PrimeField32> MachineAir<F> for MemoryBumpChip {
51    type Record = ExecutionRecord;
52
53    type Program = Program;
54
55    fn name(&self) -> &'static str {
56        "MemoryBump"
57    }
58
59    fn generate_dependencies(&self, input: &Self::Record, output: &mut Self::Record) {
60        let chunk_size = 1;
61        let event_iter = input.bump_memory_events.chunks(chunk_size);
62
63        let blu_batches = event_iter
64            .map(|events| {
65                let mut blu: HashMap<ByteLookupEvent, usize> = HashMap::new();
66                events.iter().for_each(|(event, addr, is_refresh)| {
67                    let mut row = [F::zero(); NUM_MEMORY_BUMP_COLS];
68                    let cols: &mut MemoryBumpCols<F> = row.as_mut_slice().borrow_mut();
69                    let value = event.prev_value();
70                    let prev_timestamp = event.previous_record().timestamp;
71                    let mut timestamp = event.current_record().timestamp;
72                    if !is_refresh {
73                        timestamp = (timestamp >> 24) << 24;
74                    }
75                    let bump_event = MemoryRecordEnum::Read(MemoryReadRecord {
76                        value,
77                        prev_timestamp,
78                        timestamp,
79                        prev_page_prot_record: None,
80                    });
81                    cols.access.populate(bump_event, &mut blu);
82                    blu.add_u16_range_checks(&[
83                        (timestamp & 0xFFFF) as u16,
84                        ((timestamp >> 32) & 0xFFFF) as u16,
85                    ]);
86                    blu.add_u8_range_checks(&[
87                        ((timestamp >> 16) & 0xFF) as u8,
88                        ((timestamp >> 24) & 0xFF) as u8,
89                    ]);
90                    blu.add_byte_lookup_event(ByteLookupEvent {
91                        opcode: ByteOpcode::LTU,
92                        a: 1,
93                        b: *addr as u8,
94                        c: 32,
95                    });
96                    cols.is_real = F::one();
97                });
98                blu
99            })
100            .collect::<Vec<_>>();
101
102        output.add_byte_lookup_events_from_maps(blu_batches.iter().collect_vec());
103    }
104
105    fn num_rows(&self, input: &Self::Record) -> Option<usize> {
106        let nb_rows = input.bump_memory_events.len();
107        let size_log2 = input.fixed_log2_rows::<F, _>(self);
108        Some(next_multiple_of_32(nb_rows, size_log2))
109    }
110
111    fn generate_trace_into(
112        &self,
113        input: &ExecutionRecord,
114        _output: &mut ExecutionRecord,
115        buffer: &mut [MaybeUninit<F>],
116    ) {
117        let chunk_size = 1;
118        let padded_nb_rows = <MemoryBumpChip as MachineAir<F>>::num_rows(self, input).unwrap();
119        let num_event_rows = input.bump_memory_events.len();
120
121        unsafe {
122            let padding_start = num_event_rows * NUM_MEMORY_BUMP_COLS;
123            let padding_size = (padded_nb_rows - num_event_rows) * NUM_MEMORY_BUMP_COLS;
124            if padding_size > 0 {
125                core::ptr::write_bytes(buffer[padding_start..].as_mut_ptr(), 0, padding_size);
126            }
127        }
128
129        let buffer_ptr = buffer.as_mut_ptr() as *mut F;
130        let values = unsafe {
131            core::slice::from_raw_parts_mut(buffer_ptr, num_event_rows * NUM_MEMORY_BUMP_COLS)
132        };
133
134        values.chunks_mut(chunk_size * NUM_MEMORY_BUMP_COLS).enumerate().for_each(|(i, rows)| {
135            rows.chunks_mut(NUM_MEMORY_BUMP_COLS).enumerate().for_each(|(j, row)| {
136                let idx = i * chunk_size + j;
137                let cols: &mut MemoryBumpCols<F> = row.borrow_mut();
138
139                if idx < input.bump_memory_events.len() {
140                    let mut byte_lookup_events = Vec::new();
141                    let (event, addr, is_refresh) = input.bump_memory_events[idx];
142                    let value = event.prev_value();
143                    let prev_timestamp = event.previous_record().timestamp;
144                    let mut timestamp = event.current_record().timestamp;
145                    if !is_refresh {
146                        timestamp = (timestamp >> 24) << 24;
147                    }
148                    let bump_event = MemoryRecordEnum::Read(MemoryReadRecord {
149                        value,
150                        prev_timestamp,
151                        timestamp,
152                        prev_page_prot_record: None,
153                    });
154                    cols.access.populate(bump_event, &mut byte_lookup_events);
155                    cols.clk_0_16 = F::from_canonical_u16((timestamp & 0xFFFF) as u16);
156                    cols.clk_16_24 = F::from_canonical_u8(((timestamp >> 16) & 0xFF) as u8);
157                    cols.clk_24_32 = F::from_canonical_u8(((timestamp >> 24) & 0xFF) as u8);
158                    cols.clk_32_48 = F::from_canonical_u16(((timestamp >> 32) & 0xFFFF) as u16);
159                    cols.addr = F::from_canonical_u64(addr);
160                    cols.is_real = F::one();
161                }
162            })
163        });
164    }
165
166    fn included(&self, shard: &Self::Record) -> bool {
167        shard.cpu_event_count != 0
168    }
169
170    fn column_names(&self) -> Vec<String> {
171        MemoryBumpCols::<F>::struct_reflection().unwrap()
172    }
173}
174
175impl<AB> Air<AB> for MemoryBumpChip
176where
177    AB: SP1CoreAirBuilder,
178{
179    fn eval(&self, builder: &mut AB) {
180        let main = builder.main();
181        let local = main.row_slice(0);
182        let local: &MemoryBumpCols<AB::Var> = (*local).borrow();
183
184        // Check that `is_real` is a boolean value.
185        builder.assert_bool(local.is_real);
186
187        // Check that the timestamp limbs are within range.
188        builder.slice_range_check_u16(&[local.clk_0_16, local.clk_32_48], local.is_real);
189        builder.slice_range_check_u8(&[local.clk_16_24, local.clk_24_32], local.is_real);
190
191        // Check that the address is a valid register.
192        builder.send_byte(
193            AB::Expr::from_canonical_u32(ByteOpcode::LTU as u32),
194            AB::Expr::one(),
195            local.addr,
196            AB::Expr::from_canonical_u8(32),
197            local.is_real,
198        );
199
200        // Bump the memory timestamp by doing an additional read.
201        builder.eval_memory_access_read(
202            local.clk_24_32 + local.clk_32_48 * AB::Expr::from_canonical_u32(1 << 8),
203            local.clk_0_16 + local.clk_16_24 * AB::Expr::from_canonical_u32(1 << 16),
204            &[local.addr.into(), AB::Expr::zero(), AB::Expr::zero()],
205            local.access,
206            local.is_real,
207        );
208    }
209}
sp1_core_machine/memory/bump.rs

sp1_core_machine/memory/
bump.rs
