openvm_circuit/system/phantom/
mod.rs

1use std::{
2    borrow::{Borrow, BorrowMut},
3    sync::{Arc, Mutex, OnceLock},
4};
5
6use openvm_circuit_primitives_derive::AlignedBorrow;
7use openvm_instructions::{
8    instruction::Instruction, program::DEFAULT_PC_STEP, LocalOpcode, PhantomDiscriminant,
9    SysPhantom, SystemOpcode, VmOpcode,
10};
11use openvm_stark_backend::{
12    config::{StarkGenericConfig, Val},
13    interaction::InteractionBuilder,
14    p3_air::{Air, AirBuilder, BaseAir},
15    p3_field::{Field, FieldAlgebra, PrimeField32},
16    p3_matrix::{dense::RowMajorMatrix, Matrix},
17    p3_maybe_rayon::prelude::*,
18    prover::types::AirProofInput,
19    rap::{get_air_name, BaseAirWithPublicValues, PartitionedBaseAir},
20    AirRef, Chip, ChipUsageGetter,
21};
22use rustc_hash::FxHashMap;
23use serde::{Deserialize, Serialize};
24use serde_big_array::BigArray;
25
26use super::memory::MemoryController;
27use crate::{
28    arch::{
29        ExecutionBridge, ExecutionBus, ExecutionError, ExecutionState, InstructionExecutor,
30        PcIncOrSet, PhantomSubExecutor, Streams,
31    },
32    system::program::ProgramBus,
33};
34
35#[cfg(test)]
36mod tests;
37
38/// PhantomAir still needs columns for each nonzero operand in a phantom instruction.
39/// We currently allow `a,b,c` where the lower 16 bits of `c` are used as the [PhantomInstruction] discriminant.
40const NUM_PHANTOM_OPERANDS: usize = 3;
41
42#[derive(Clone, Debug)]
43pub struct PhantomAir {
44    pub execution_bridge: ExecutionBridge,
45    /// Global opcode for PhantomOpcode
46    pub phantom_opcode: VmOpcode,
47}
48
49#[repr(C)]
50#[derive(AlignedBorrow, Copy, Clone, Serialize, Deserialize)]
51pub struct PhantomCols<T> {
52    pub pc: T,
53    #[serde(with = "BigArray")]
54    pub operands: [T; NUM_PHANTOM_OPERANDS],
55    pub timestamp: T,
56    pub is_valid: T,
57}
58
59impl<F: Field> BaseAir<F> for PhantomAir {
60    fn width(&self) -> usize {
61        PhantomCols::<F>::width()
62    }
63}
64impl<F: Field> PartitionedBaseAir<F> for PhantomAir {}
65impl<F: Field> BaseAirWithPublicValues<F> for PhantomAir {}
66
67impl<AB: AirBuilder + InteractionBuilder> Air<AB> for PhantomAir {
68    fn eval(&self, builder: &mut AB) {
69        let main = builder.main();
70        let local = main.row_slice(0);
71        let &PhantomCols {
72            pc,
73            operands,
74            timestamp,
75            is_valid,
76        } = (*local).borrow();
77
78        self.execution_bridge
79            .execute_and_increment_or_set_pc(
80                self.phantom_opcode.to_field::<AB::F>(),
81                operands,
82                ExecutionState::<AB::Expr>::new(pc, timestamp),
83                AB::Expr::ONE,
84                PcIncOrSet::Inc(AB::Expr::from_canonical_u32(DEFAULT_PC_STEP)),
85            )
86            .eval(builder, is_valid);
87    }
88}
89
90pub struct PhantomChip<F> {
91    pub air: PhantomAir,
92    pub rows: Vec<PhantomCols<F>>,
93    streams: OnceLock<Arc<Mutex<Streams<F>>>>,
94    phantom_executors: FxHashMap<PhantomDiscriminant, Box<dyn PhantomSubExecutor<F>>>,
95}
96
97impl<F> PhantomChip<F> {
98    pub fn new(execution_bus: ExecutionBus, program_bus: ProgramBus, offset: usize) -> Self {
99        Self {
100            air: PhantomAir {
101                execution_bridge: ExecutionBridge::new(execution_bus, program_bus),
102                phantom_opcode: VmOpcode::from_usize(offset + SystemOpcode::PHANTOM.local_usize()),
103            },
104            rows: vec![],
105            streams: OnceLock::new(),
106            phantom_executors: FxHashMap::default(),
107        }
108    }
109
110    pub fn set_streams(&mut self, streams: Arc<Mutex<Streams<F>>>) {
111        if self.streams.set(streams).is_err() {
112            panic!("Streams should only be set once");
113        }
114    }
115
116    pub(crate) fn add_sub_executor<P: PhantomSubExecutor<F> + 'static>(
117        &mut self,
118        sub_executor: P,
119        discriminant: PhantomDiscriminant,
120    ) -> Option<Box<dyn PhantomSubExecutor<F>>> {
121        self.phantom_executors
122            .insert(discriminant, Box::new(sub_executor))
123    }
124}
125
126impl<F: PrimeField32> InstructionExecutor<F> for PhantomChip<F> {
127    fn execute(
128        &mut self,
129        memory: &mut MemoryController<F>,
130        instruction: &Instruction<F>,
131        from_state: ExecutionState<u32>,
132    ) -> Result<ExecutionState<u32>, ExecutionError> {
133        let &Instruction {
134            opcode, a, b, c, ..
135        } = instruction;
136        assert_eq!(opcode, self.air.phantom_opcode);
137
138        let c_u32 = c.as_canonical_u32();
139        let discriminant = PhantomDiscriminant(c_u32 as u16);
140        // If not a system phantom sub-instruction (which is handled in
141        // ExecutionSegment), look for a phantom sub-executor to handle it.
142        if SysPhantom::from_repr(discriminant.0).is_none() {
143            let sub_executor = self
144                .phantom_executors
145                .get_mut(&discriminant)
146                .ok_or_else(|| ExecutionError::PhantomNotFound {
147                    pc: from_state.pc,
148                    discriminant,
149                })?;
150            let mut streams = self.streams.get().unwrap().lock().unwrap();
151            sub_executor
152                .as_mut()
153                .phantom_execute(
154                    memory,
155                    &mut streams,
156                    discriminant,
157                    a,
158                    b,
159                    (c_u32 >> 16) as u16,
160                )
161                .map_err(|e| ExecutionError::Phantom {
162                    pc: from_state.pc,
163                    discriminant,
164                    inner: e,
165                })?;
166        }
167
168        self.rows.push(PhantomCols {
169            pc: F::from_canonical_u32(from_state.pc),
170            operands: [a, b, c],
171            timestamp: F::from_canonical_u32(from_state.timestamp),
172            is_valid: F::ONE,
173        });
174        memory.increment_timestamp();
175        Ok(ExecutionState::new(
176            from_state.pc + DEFAULT_PC_STEP,
177            from_state.timestamp + 1,
178        ))
179    }
180
181    fn get_opcode_name(&self, _: usize) -> String {
182        format!("{:?}", SystemOpcode::PHANTOM)
183    }
184}
185
186impl<F: PrimeField32> ChipUsageGetter for PhantomChip<F> {
187    fn air_name(&self) -> String {
188        get_air_name(&self.air)
189    }
190    fn current_trace_height(&self) -> usize {
191        self.rows.len()
192    }
193    fn trace_width(&self) -> usize {
194        PhantomCols::<F>::width()
195    }
196    fn current_trace_cells(&self) -> usize {
197        self.trace_width() * self.current_trace_height()
198    }
199}
200
201impl<SC: StarkGenericConfig> Chip<SC> for PhantomChip<Val<SC>>
202where
203    Val<SC>: PrimeField32,
204{
205    fn air(&self) -> AirRef<SC> {
206        Arc::new(self.air.clone())
207    }
208
209    fn generate_air_proof_input(self) -> AirProofInput<SC> {
210        let correct_height = self.rows.len().next_power_of_two();
211        let width = PhantomCols::<Val<SC>>::width();
212        let mut rows = Val::<SC>::zero_vec(width * correct_height);
213        rows.par_chunks_mut(width)
214            .zip(&self.rows)
215            .for_each(|(row, row_record)| {
216                let row: &mut PhantomCols<_> = row.borrow_mut();
217                *row = *row_record;
218            });
219        let trace = RowMajorMatrix::new(rows, width);
220
221        AirProofInput::simple(trace, vec![])
222    }
223}