turshi/runner.rs
1//! This module represents a run of a Cairo program as a series of consecutive
2//! execution steps, each of which define the execution logic of Cairo instructions
3
4use crate::{
5 flags::*,
6 memory::CairoMemory,
7 word::{CairoWord, FlagBits, FlagSets, Offsets},
8};
9use ark_ff::Field;
10
11/// A structure to store program counter, allocation pointer and frame pointer
12#[derive(Clone, Copy)]
13pub struct CairoState<F> {
14 /// Program counter: points to address in memory
15 pc: F,
16 /// Allocation pointer: points to first free space in memory
17 ap: F,
18 /// Frame pointer: points to the beginning of the stack in memory (for arguments)
19 fp: F,
20}
21
22/// This trait contains functions to obtain the Cairo pointers (program counter, allocation pointer and frame pointer)
23pub trait Pointers<F> {
24 /// Returns the program counter
25 fn pc(&self) -> F;
26
27 /// Returns the allocation pointer
28 fn ap(&self) -> F;
29
30 /// Returns the frame pointer
31 fn fp(&self) -> F;
32}
33
34impl<F: Field> CairoState<F> {
35 /// Creates a new triple of pointers
36 pub fn new(pc: F, ap: F, fp: F) -> Self {
37 CairoState { pc, ap, fp }
38 }
39}
40
41impl<F: Field> Pointers<F> for CairoState<F> {
42 fn pc(&self) -> F {
43 self.pc
44 }
45
46 fn ap(&self) -> F {
47 self.ap
48 }
49
50 fn fp(&self) -> F {
51 self.fp
52 }
53}
54
55#[derive(Clone, Copy)]
56/// A structure to store auxiliary variables throughout computation
57pub struct CairoContext<F> {
58 /// Destination
59 dst: Option<F>,
60 /// First operand
61 op0: Option<F>,
62 /// Second operand
63 op1: Option<F>,
64 /// Result
65 res: Option<F>,
66 /// Destination address
67 adr_dst: F,
68 /// First operand address
69 adr_op0: F,
70 /// Second operand address
71 adr_op1: F,
72 /// Size of the instruction
73 size: F,
74}
75
76impl<F: Field> Default for CairoContext<F> {
77 /// This function creates an instance of a default [CairoContext] struct
78 fn default() -> Self {
79 Self {
80 dst: None,
81 op0: None,
82 op1: None,
83 res: None,
84 adr_dst: F::zero(),
85 adr_op0: F::zero(),
86 adr_op1: F::zero(),
87 size: F::zero(),
88 }
89 }
90}
91
92#[derive(Clone, Copy)]
93/// This structure stores all the needed information relative to an instruction at a given step of computation
94pub struct CairoInstruction<F> {
95 /// instruction word
96 word: CairoWord<F>,
97 /// pointers
98 ptrs: CairoState<F>,
99 /// auxiliary variables
100 vars: CairoContext<F>,
101}
102
103impl<F: Field> CairoInstruction<F> {
104 /// Creates a [CairoInstruction]
105 pub fn new(word: CairoWord<F>, ptrs: CairoState<F>, vars: CairoContext<F>) -> Self {
106 Self { word, ptrs, vars }
107 }
108
109 /// Returns the field element corresponding to the [CairoInstruction]
110 pub fn instr(&self) -> F {
111 self.word.word()
112 }
113
114 /// Returns the size of the instruction
115 pub fn size(&self) -> F {
116 self.vars.size
117 }
118
119 /// Returns the result of the instruction
120 pub fn res(&self) -> F {
121 self.vars.res.expect("None res")
122 }
123
124 /// Returns the destination of the instruction
125 pub fn dst(&self) -> F {
126 self.vars.dst.expect("None dst")
127 }
128
129 /// Returns the first operand of the instruction
130 pub fn op0(&self) -> F {
131 self.vars.op0.expect("None op0")
132 }
133
134 /// Returns the second operand of the instruction
135 pub fn op1(&self) -> F {
136 self.vars.op1.expect("None op1")
137 }
138
139 /// Returns the destination address of the instruction
140 pub fn adr_dst(&self) -> F {
141 self.vars.adr_dst
142 }
143
144 /// Returns the first operand address of the instruction
145 pub fn adr_op0(&self) -> F {
146 self.vars.adr_op0
147 }
148
149 /// Returns the second operand address of the instruction
150 pub fn adr_op1(&self) -> F {
151 self.vars.adr_op1
152 }
153}
154
155impl<F: Field> Pointers<F> for CairoInstruction<F> {
156 fn pc(&self) -> F {
157 self.ptrs.pc // Returns the current program counter
158 }
159
160 fn ap(&self) -> F {
161 self.ptrs.ap //Returns the current allocation pointer
162 }
163
164 fn fp(&self) -> F {
165 self.ptrs.fp // Returns the current program counter
166 }
167}
168
169impl<F: Field> Offsets<F> for CairoInstruction<F> {
170 fn off_dst(&self) -> F {
171 self.word.off_dst()
172 }
173
174 fn off_op0(&self) -> F {
175 self.word.off_op0()
176 }
177
178 fn off_op1(&self) -> F {
179 self.word.off_op1()
180 }
181}
182
183impl<F: Field> FlagBits<F> for CairoInstruction<F> {
184 fn f_dst_fp(&self) -> F {
185 self.word.f_dst_fp()
186 }
187
188 fn f_op0_fp(&self) -> F {
189 self.word.f_op0_fp()
190 }
191
192 fn f_op1_val(&self) -> F {
193 self.word.f_op1_val()
194 }
195
196 fn f_op1_fp(&self) -> F {
197 self.word.f_op1_fp()
198 }
199
200 fn f_op1_ap(&self) -> F {
201 self.word.f_op1_ap()
202 }
203
204 fn f_res_add(&self) -> F {
205 self.word.f_res_add()
206 }
207
208 fn f_res_mul(&self) -> F {
209 self.word.f_res_mul()
210 }
211
212 fn f_pc_abs(&self) -> F {
213 self.word.f_pc_abs()
214 }
215
216 fn f_pc_rel(&self) -> F {
217 self.word.f_pc_rel()
218 }
219
220 fn f_pc_jnz(&self) -> F {
221 self.word.f_pc_jnz()
222 }
223
224 fn f_ap_add(&self) -> F {
225 self.word.f_ap_add()
226 }
227
228 fn f_ap_one(&self) -> F {
229 self.word.f_ap_one()
230 }
231
232 fn f_opc_call(&self) -> F {
233 self.word.f_opc_call()
234 }
235
236 fn f_opc_ret(&self) -> F {
237 self.word.f_opc_ret()
238 }
239
240 fn f_opc_aeq(&self) -> F {
241 self.word.f_opc_aeq()
242 }
243
244 fn f15(&self) -> F {
245 self.word.f15()
246 }
247}
248
249/// A data structure to store a current step of Cairo computation
250pub struct CairoStep<'a, F> {
251 /// state of the computation
252 pub mem: &'a mut CairoMemory<F>,
253 // comment instr for efficiency
254 /// current pointers
255 pub curr: CairoState<F>,
256 /// (if any) next pointers
257 pub next: Option<CairoState<F>>,
258 /// state auxiliary variables
259 pub vars: CairoContext<F>,
260}
261
262impl<'a, F: Field> CairoStep<'a, F> {
263 /// Creates a new Cairo execution step from a step index, a Cairo word, and current pointers
264 pub fn new(mem: &mut CairoMemory<F>, ptrs: CairoState<F>) -> CairoStep<F> {
265 CairoStep {
266 mem,
267 curr: ptrs,
268 next: None,
269 vars: CairoContext::default(),
270 }
271 }
272
273 /// Executes a Cairo step from the current registers
274 pub fn execute(&mut self) -> CairoInstruction<F> {
275 // This order is important in order to allocate the memory in time
276 self.set_op0();
277 self.set_op1();
278 self.set_res();
279 self.set_dst();
280 // If the Option<> is not a guarantee for continuation of the program, we may be removing this
281 let next_pc = self.next_pc();
282 let (next_ap, next_fp) = self.next_apfp();
283 self.next = Some(CairoState::new(
284 next_pc.expect("Empty next program counter"),
285 next_ap.expect("Empty next allocation pointer"),
286 next_fp.expect("Empty next frame pointer"),
287 ));
288 CairoInstruction::new(self.instr(), self.curr, self.vars)
289 }
290
291 /// This function returns the current word instruction being executed
292 pub fn instr(&mut self) -> CairoWord<F> {
293 CairoWord::new(self.mem.read(self.curr.pc).expect("pc points to None cell"))
294 }
295
296 /// This function computes the first operand address
297 pub fn set_op0(&mut self) {
298 let reg = match self.instr().op0_reg() {
299 /*0*/ OP0_AP => self.curr.ap, // reads first word from allocated memory
300 /*1*/ _ => self.curr.fp, // reads first word from input stack
301 }; // no more values than 0 and 1 because op0_reg is one bit
302 self.vars.adr_op0 = reg + self.instr().off_op0();
303 self.vars.op0 = self.mem.read(self.vars.adr_op0);
304 }
305
306 /// This function computes the second operand address and content and the instruction size
307 /// Panics if the flagset `OP1_SRC` has more than 1 nonzero bit
308 pub fn set_op1(&mut self) {
309 let (reg, size) = match self.instr().op1_src() {
310 /*0*/
311 OP1_DBL => (self.vars.op0.expect("None op0 for OP1_DBL"), F::one()), // double indexing, op0 should be positive for address
312 /*1*/
313 OP1_VAL => (self.curr.pc, F::from(2u32)), // off_op1 will be 1 and then op1 contains an immediate value
314 /*2*/ OP1_FP => (self.curr.fp, F::one()),
315 /*4*/ OP1_AP => (self.curr.ap, F::one()),
316 _ => panic!("Invalid op1_src flagset"),
317 };
318 self.vars.size = size;
319 self.vars.adr_op1 = reg + self.instr().off_op1(); // apply second offset to corresponding register
320 self.vars.op1 = self.mem.read(self.vars.adr_op1);
321 }
322
323 /// This function computes the value of the result of the arithmetic operation
324 /// Panics if a `jnz` instruction is used with an invalid format
325 /// or if the flagset `RES_LOG` has more than 1 nonzero bit
326 pub fn set_res(&mut self) {
327 if self.instr().pc_up() == PC_JNZ {
328 /*4*/
329 // jnz instruction
330 if self.instr().res_log() == RES_ONE /*0*/
331 && self.instr().opcode() == OPC_JMP_INC /*0*/
332 && self.instr().ap_up() != AP_ADD
333 /* not 1*/
334 {
335 self.vars.res = Some(F::zero()); // "unused"
336 } else {
337 panic!("Invalid JNZ instruction");
338 }
339 } else if self.instr().pc_up() == PC_SIZ /*0*/
340 || self.instr().pc_up() == PC_ABS /*1*/
341 || self.instr().pc_up() == PC_REL
342 /*2*/
343 {
344 // rest of types of updates
345 // common increase || absolute jump || relative jump
346 match self.instr().res_log() {
347 /*0*/
348 RES_ONE => self.vars.res = self.vars.op1, // right part is single operand
349 /*1*/
350 RES_ADD => {
351 self.vars.res = Some(
352 self.vars.op0.expect("None op0 after RES_ADD")
353 + self.vars.op1.expect("None op1 after RES_ADD"),
354 )
355 } // right part is addition
356 /*2*/
357 RES_MUL => {
358 self.vars.res = Some(
359 self.vars.op0.expect("None op0 after RES_MUL")
360 * self.vars.op1.expect("None op1 after RES_MUL"),
361 )
362 } // right part is multiplication
363 _ => panic!("Invalid res_log flagset"),
364 }
365 } else {
366 // multiple bits take value 1
367 panic!("Invalid pc_up flagset");
368 }
369 }
370
371 /// This function computes the destination address
372 pub fn set_dst(&mut self) {
373 let reg = match self.instr().dst_reg() {
374 /*0*/ DST_AP => self.curr.ap, // read from stack
375 /*1*/ _ => self.curr.fp, // read from parameters
376 }; // no more values than 0 and 1 because op0_reg is one bit
377 self.vars.adr_dst = reg + self.instr().off_dst();
378 self.vars.dst = self.mem.read(self.vars.adr_dst);
379 }
380
381 /// This function computes the next program counter
382 /// Panics if the flagset `PC_UP` has more than 1 nonzero bit
383 pub fn next_pc(&mut self) -> Option<F> {
384 match self.instr().pc_up() {
385 /*0*/
386 PC_SIZ => Some(self.curr.pc + self.vars.size), // common case, next instruction is right after the current one
387 /*1*/
388 PC_ABS => Some(self.vars.res.expect("None res after PC_ABS")), // absolute jump, next instruction is in res,
389 /*2*/
390 PC_REL => Some(self.curr.pc + self.vars.res.expect("None res after PC_REL")), // relative jump, go to some address relative to pc
391 /*4*/
392 PC_JNZ => {
393 // conditional relative jump (jnz)
394 if self.vars.dst == Some(F::zero()) {
395 Some(self.curr.pc + self.vars.size) // if condition false, common case
396 } else {
397 // if condition true, relative jump with second operand
398 Some(self.curr.pc + self.vars.op1.expect("None op1 after PC_JNZ"))
399 }
400 }
401 _ => panic!("Invalid pc_up flagset"),
402 }
403 }
404
405 /// This function computes the next values of the allocation and frame pointers
406 /// Panics if in a `call` instruction the flagset [FlagSets::ap_up] is incorrect
407 /// or if in any other instruction the flagset [FlagSets::ap_up] has more than 1 nonzero bit
408 /// or if the flagset `OPCODE` has more than 1 nonzero bit
409 fn next_apfp(&mut self) -> (Option<F>, Option<F>) {
410 let (next_ap, next_fp);
411 // The following branches don't include the assertions. That is done in the verification.
412 if self.instr().opcode() == OPC_CALL {
413 /*1*/
414 // "call" instruction
415 self.mem.write(self.curr.ap, self.curr.fp); // Save current fp
416 self.vars.dst = self.mem.read(self.curr.ap); // update dst content
417 self.mem
418 .write(self.curr.ap + F::one(), self.curr.pc + self.vars.size); // Save next instruction
419 self.vars.op0 = self.mem.read(self.curr.ap + F::one()); //update op0 content
420
421 // Update fp
422 next_fp = Some(self.curr.ap + F::from(2u32)); // pointer for next frame is after current fp and instruction after call
423 // Update ap
424 match self.instr().ap_up() {
425 /*0*/
426 AP_Z2 => next_ap = Some(self.curr.ap + F::from(2u32)), // two words were written so advance 2 positions
427 _ => panic!("ap increment in call instruction"), // ap increments not allowed in call instructions
428 };
429 } else if self.instr().opcode() == OPC_JMP_INC /*0*/
430 || self.instr().opcode() == OPC_RET /*2*/
431 || self.instr().opcode() == OPC_AEQ
432 /*4*/
433 {
434 // rest of types of instruction
435 // jumps and increments || return || assert equal
436 match self.instr().ap_up() {
437 /*0*/ AP_Z2 => next_ap = Some(self.curr.ap), // no modification on ap
438 /*1*/
439 AP_ADD => {
440 // ap += <op> should be larger than current ap
441 next_ap = Some(self.curr.ap + self.vars.res.expect("None res after AP_ADD"))
442 }
443 /*2*/ AP_ONE => next_ap = Some(self.curr.ap + F::one()), // ap++
444 _ => panic!("Invalid ap_up flagset"),
445 }
446
447 match self.instr().opcode() {
448 /*0*/
449 OPC_JMP_INC => next_fp = Some(self.curr.fp), // no modification on fp
450 /*2*/
451 OPC_RET => next_fp = Some(self.vars.dst.expect("None dst after OPC_RET")), // ret sets fp to previous fp that was in [ap-2]
452 /*4*/
453 OPC_AEQ => {
454 // The following conditional is a fix that is not explained in the whitepaper
455 // The goal is to distinguish two types of ASSERT_EQUAL where one checks that
456 // dst = res , but in order for this to be true, one sometimes needs to write
457 // the res in mem(adr_dst) and sometimes write dst in mem(res_dir). The only
458 // case where res can be None is when res = op1 and thus res_dir = adr_op1
459 if self.vars.res.is_none() {
460 // res = dst
461 self.mem.write(
462 self.vars.adr_op1,
463 self.vars.dst.expect("None dst after OPC_AEQ"),
464 );
465 // update the value of the variable as well
466 self.vars.op1 = self.mem.read(self.vars.adr_op1);
467 self.vars.res = self.mem.read(self.vars.adr_op1);
468 } else {
469 // dst = res
470 self.mem.write(
471 self.vars.adr_dst,
472 self.vars.res.expect("None res after OPC_AEQ"),
473 );
474 // update the value of the variable as well
475 self.vars.dst = self.mem.read(self.vars.adr_dst);
476 }
477 next_fp = Some(self.curr.fp); // no modification on fp
478 }
479 _ => {
480 panic!("This case must never happen")
481 }
482 }
483 } else {
484 panic!("Invalid opcode flagset");
485 }
486 (next_ap, next_fp)
487 }
488}
489
490/// This struct stores the needed information to run a program
491pub struct CairoProgram<'a, F> {
492 /// total number of steps
493 pub steps: F,
494 /// full execution memory
495 pub mem: &'a mut CairoMemory<F>,
496 /// initial computation registers
497 pub ini: CairoState<F>,
498 /// final computation pointers
499 pub fin: CairoState<F>,
500 /// execution trace as a vector of [CairoInstruction]
501 pub trace: Vec<CairoInstruction<F>>,
502}
503
504impl<'a, F: Field> CairoProgram<'a, F> {
505 /// Creates a Cairo execution from the public information (memory and initial pointers)
506 pub fn new(mem: &mut CairoMemory<F>, pc: u64) -> CairoProgram<F> {
507 let ap = mem.len();
508 let mut prog = CairoProgram {
509 steps: F::zero(),
510 mem,
511 ini: CairoState::new(F::from(pc), F::from(ap), F::from(ap)),
512 fin: CairoState::new(F::zero(), F::zero(), F::zero()),
513 trace: Vec::new(),
514 };
515 prog.execute();
516 prog
517 }
518
519 /// Outputs the total number of steps of the execution carried out by the runner
520 pub fn steps(&self) -> F {
521 self.steps
522 }
523
524 /// Outputs the initial value of the pointers after the execution carried out by the runner
525 pub fn ini(&self) -> CairoState<F> {
526 self.ini
527 }
528
529 /// Outputs the final value of the pointers after the execution carried out by the runner
530 pub fn fin(&self) -> CairoState<F> {
531 self.fin
532 }
533
534 /// Returns a reference to the set of instructions
535 pub fn trace(&self) -> &Vec<CairoInstruction<F>> {
536 &self.trace
537 }
538
539 /// This function simulates an execution of the Cairo program received as input.
540 /// It generates the full memory stack and the execution trace
541 fn execute(&mut self) {
542 // set finishing flag to false, as it just started
543 let mut end = false;
544 // saves local copy of the initial (claimed) pointers of the program
545 let mut curr = self.ini;
546 let mut next = self.ini;
547 // first timestamp
548 let mut n: u64 = 0;
549 // keep executing steps until the end is reached
550 while !end {
551 // create current step of computation
552 let mut step = CairoStep::new(self.mem, next);
553 // save current value of the pointers
554 curr = step.curr;
555 // execute current step and increase time counter
556 let instr = step.execute();
557 self.trace.push(instr);
558 n += 1;
559 match step.next {
560 None => end = true, // if find no next pointers, end
561 _ => {
562 // if there are next pointers
563 end = false;
564 // update next value of pointers
565 next = step.next.expect("Empty next pointers");
566 if curr.ap <= next.pc {
567 // if reading from unallocated memory, end
568 end = true;
569 }
570 }
571 }
572 }
573 self.steps = F::from(n);
574 self.fin = CairoState::new(curr.pc, curr.ap, curr.fp);
575 }
576}