openvm_rv32_adapters/
heap.rs

1use std::borrow::Borrow;
2
3use openvm_circuit::{
4    arch::{
5        AdapterAirContext, AdapterTraceExecutor, AdapterTraceFiller, BasicAdapterInterface,
6        ExecutionBridge, MinimalInstruction, VmAdapterAir,
7    },
8    system::memory::{offline_checker::MemoryBridge, online::TracingMemory, MemoryAuxColsFactory},
9};
10use openvm_circuit_primitives::bitwise_op_lookup::{
11    BitwiseOperationLookupBus, SharedBitwiseOperationLookupChip,
12};
13use openvm_instructions::{
14    instruction::Instruction,
15    riscv::{RV32_CELL_BITS, RV32_REGISTER_NUM_LIMBS},
16};
17use openvm_stark_backend::{
18    interaction::InteractionBuilder,
19    p3_air::BaseAir,
20    p3_field::{Field, PrimeField32},
21};
22
23use crate::{
24    Rv32VecHeapAdapterAir, Rv32VecHeapAdapterCols, Rv32VecHeapAdapterExecutor,
25    Rv32VecHeapAdapterFiller, Rv32VecHeapAdapterRecord,
26};
27
28/// This adapter reads from NUM_READS <= 2 pointers and writes to 1 pointer.
29/// * The data is read from the heap (address space 2), and the pointers are read from registers
30///   (address space 1).
31/// * Reads are from the addresses in `rs[0]` (and `rs[1]` if `R = 2`).
32/// * Writes are to the address in `rd`.
33
34#[derive(Clone, Copy, Debug, derive_new::new)]
35pub struct Rv32HeapAdapterAir<
36    const NUM_READS: usize,
37    const READ_SIZE: usize,
38    const WRITE_SIZE: usize,
39> {
40    pub(super) execution_bridge: ExecutionBridge,
41    pub(super) memory_bridge: MemoryBridge,
42    pub bus: BitwiseOperationLookupBus,
43    /// The max number of bits for an address in memory
44    address_bits: usize,
45}
46
47impl<F: Field, const NUM_READS: usize, const READ_SIZE: usize, const WRITE_SIZE: usize> BaseAir<F>
48    for Rv32HeapAdapterAir<NUM_READS, READ_SIZE, WRITE_SIZE>
49{
50    fn width(&self) -> usize {
51        Rv32VecHeapAdapterCols::<F, NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE>::width()
52    }
53}
54
55impl<
56        AB: InteractionBuilder,
57        const NUM_READS: usize,
58        const READ_SIZE: usize,
59        const WRITE_SIZE: usize,
60    > VmAdapterAir<AB> for Rv32HeapAdapterAir<NUM_READS, READ_SIZE, WRITE_SIZE>
61{
62    type Interface = BasicAdapterInterface<
63        AB::Expr,
64        MinimalInstruction<AB::Expr>,
65        NUM_READS,
66        1,
67        READ_SIZE,
68        WRITE_SIZE,
69    >;
70
71    fn eval(
72        &self,
73        builder: &mut AB,
74        local: &[AB::Var],
75        ctx: AdapterAirContext<AB::Expr, Self::Interface>,
76    ) {
77        let vec_heap_air: Rv32VecHeapAdapterAir<NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE> =
78            Rv32VecHeapAdapterAir::new(
79                self.execution_bridge,
80                self.memory_bridge,
81                self.bus,
82                self.address_bits,
83            );
84        vec_heap_air.eval(builder, local, ctx.into());
85    }
86
87    fn get_from_pc(&self, local: &[AB::Var]) -> AB::Var {
88        let cols: &Rv32VecHeapAdapterCols<_, NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE> =
89            local.borrow();
90        cols.from_state.pc
91    }
92}
93
94#[derive(Clone, Copy)]
95pub struct Rv32HeapAdapterExecutor<
96    const NUM_READS: usize,
97    const READ_SIZE: usize,
98    const WRITE_SIZE: usize,
99>(Rv32VecHeapAdapterExecutor<NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE>);
100
101impl<const NUM_READS: usize, const READ_SIZE: usize, const WRITE_SIZE: usize>
102    Rv32HeapAdapterExecutor<NUM_READS, READ_SIZE, WRITE_SIZE>
103{
104    pub fn new(pointer_max_bits: usize) -> Self {
105        assert!(NUM_READS <= 2);
106        assert!(
107            RV32_CELL_BITS * RV32_REGISTER_NUM_LIMBS - pointer_max_bits < RV32_CELL_BITS,
108            "pointer_max_bits={pointer_max_bits} needs to be large enough for high limb range check"
109        );
110        Rv32HeapAdapterExecutor(Rv32VecHeapAdapterExecutor::new(pointer_max_bits))
111    }
112}
113
114pub struct Rv32HeapAdapterFiller<
115    const NUM_READS: usize,
116    const READ_SIZE: usize,
117    const WRITE_SIZE: usize,
118>(Rv32VecHeapAdapterFiller<NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE>);
119
120impl<const NUM_READS: usize, const READ_SIZE: usize, const WRITE_SIZE: usize>
121    Rv32HeapAdapterFiller<NUM_READS, READ_SIZE, WRITE_SIZE>
122{
123    pub fn new(
124        pointer_max_bits: usize,
125        bitwise_lookup_chip: SharedBitwiseOperationLookupChip<RV32_CELL_BITS>,
126    ) -> Self {
127        assert!(NUM_READS <= 2);
128        assert!(
129            RV32_CELL_BITS * RV32_REGISTER_NUM_LIMBS - pointer_max_bits < RV32_CELL_BITS,
130            "pointer_max_bits={pointer_max_bits} needs to be large enough for high limb range check"
131        );
132        Rv32HeapAdapterFiller(Rv32VecHeapAdapterFiller::new(
133            pointer_max_bits,
134            bitwise_lookup_chip,
135        ))
136    }
137}
138
139impl<F: PrimeField32, const NUM_READS: usize, const READ_SIZE: usize, const WRITE_SIZE: usize>
140    AdapterTraceExecutor<F> for Rv32HeapAdapterExecutor<NUM_READS, READ_SIZE, WRITE_SIZE>
141where
142    F: PrimeField32,
143{
144    const WIDTH: usize =
145        Rv32VecHeapAdapterCols::<F, NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE>::width();
146    type ReadData = [[u8; READ_SIZE]; NUM_READS];
147    type WriteData = [[u8; WRITE_SIZE]; 1];
148    type RecordMut<'a> = &'a mut Rv32VecHeapAdapterRecord<NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE>;
149
150    fn start(pc: u32, memory: &TracingMemory, record: &mut Self::RecordMut<'_>) {
151        record.from_pc = pc;
152        record.from_timestamp = memory.timestamp;
153    }
154
155    fn read(
156        &self,
157        memory: &mut TracingMemory,
158        instruction: &Instruction<F>,
159        record: &mut Self::RecordMut<'_>,
160    ) -> Self::ReadData {
161        let read_data = AdapterTraceExecutor::<F>::read(&self.0, memory, instruction, record);
162        read_data.map(|r| r[0])
163    }
164
165    fn write(
166        &self,
167        memory: &mut TracingMemory,
168        instruction: &Instruction<F>,
169        data: Self::WriteData,
170        record: &mut Self::RecordMut<'_>,
171    ) {
172        AdapterTraceExecutor::<F>::write(&self.0, memory, instruction, data, record);
173    }
174}
175
176impl<F: PrimeField32, const NUM_READS: usize, const READ_SIZE: usize, const WRITE_SIZE: usize>
177    AdapterTraceFiller<F> for Rv32HeapAdapterFiller<NUM_READS, READ_SIZE, WRITE_SIZE>
178{
179    const WIDTH: usize =
180        Rv32VecHeapAdapterCols::<F, NUM_READS, 1, 1, READ_SIZE, WRITE_SIZE>::width();
181
182    fn fill_trace_row(&self, mem_helper: &MemoryAuxColsFactory<F>, adapter_row: &mut [F]) {
183        AdapterTraceFiller::<F>::fill_trace_row(&self.0, mem_helper, adapter_row);
184    }
185}
openvm_rv32_adapters/heap.rs

openvm_rv32_adapters/
heap.rs
