turshi/
memory.rs

1//! This module represents the Cairo memory, containing the
2//! compiled Cairo program that occupies the first few entries
3
4use std::{
5    fmt::{Display, Formatter, Result},
6    ops::{Index, IndexMut},
7};
8
9use crate::{helper::*, word::CairoWord};
10use ark_ff::Field;
11use core::iter::repeat;
12
13/// This data structure stores the memory of the program
14pub struct CairoMemory<F> {
15    /// length of the public memory
16    codelen: usize,
17    /// full memory vector, None if non initialized
18    data: Vec<Option<CairoWord<F>>>,
19}
20
21impl<F: Field> Index<F> for CairoMemory<F> {
22    type Output = Option<CairoWord<F>>;
23    fn index(&self, idx: F) -> &Self::Output {
24        // Safely convert idx from F to usize (since this is a memory address
25        // idx should not be too big, this should be safe)
26        let addr: u64 = idx.to_u64();
27        &self.data[addr as usize]
28    }
29}
30
31impl<F: Field> IndexMut<F> for CairoMemory<F> {
32    fn index_mut(&mut self, idx: F) -> &mut Self::Output {
33        let addr: u64 = idx.to_u64();
34        self.resize(addr); // Resize if necessary
35        &mut self.data[addr as usize]
36    }
37}
38
39impl<F: Field> Display for CairoMemory<F> {
40    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
41        for i in 1..self.len() {
42            // Visualize content of memory excluding the 0th dummy entry
43            if let Some(elem) = self[F::from(i)] {
44                writeln!(f, "{0:>6}: 0x{1:}", i, elem.word().to_hex_be())
45                    .map_err(|_| core::fmt::Error)?;
46            } else {
47                writeln!(f, "{i:>6}: None").map_err(|_| core::fmt::Error)?;
48            }
49        }
50        Ok(())
51    }
52}
53
54impl<F: Field> CairoMemory<F> {
55    /// Create a new memory structure from a vector of field elements
56    pub fn new(input: Vec<F>) -> CairoMemory<F> {
57        // Initialized with the public memory (compiled instructions only)
58        // starts intentionally with a zero word for ease of testing
59        let mut aux = vec![F::zero()];
60        aux.extend(input);
61        CairoMemory {
62            codelen: aux.len() - 1,
63            data: aux.into_iter().map(|i| Some(CairoWord::new(i))).collect(),
64        }
65    }
66
67    /// Get size of the public memory
68    pub fn get_codelen(&self) -> usize {
69        self.codelen
70    }
71
72    /// Get size of the full memory including dummy 0th entry
73    pub fn len(&self) -> u64 {
74        self.data.len() as u64
75    }
76
77    /// Returns whether the memory is empty (either length 0, or with the dummy first entry)
78    pub fn is_empty(&self) -> bool {
79        self.data.len() < 2
80    }
81
82    /// Resizes memory with enough additional None slots if necessary before writing or reading
83    fn resize(&mut self, addr: u64) {
84        // if you want to access an index of the memory but its size is less or equal than this
85        // you will need to extend the vector with enough spaces (taking into account that
86        // vectors start by index 0, the 0 address is dummy, and size starts in 1)
87        if let Some(additional) = addr.checked_sub(self.len() - 1) {
88            self.data.extend(repeat(None).take(additional as usize));
89        }
90    }
91
92    /// Write u64 element in memory address
93    pub fn write(&mut self, addr: F, elem: F) {
94        self[addr] = Some(CairoWord::new(elem));
95    }
96
97    /// Read element in memory address
98    pub fn read(&mut self, addr: F) -> Option<F> {
99        self.resize(addr.to_u64()); // Resize if necessary
100        self[addr].map(|x| x.word())
101    }
102}
turshi/memory.rs

turshi/
memory.rs
