1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

//! This module represents the Cairo memory, containing the
//! compiled Cairo program that occupies the first few entries

use std::{
    fmt::{Display, Formatter, Result},
    ops::{Index, IndexMut},
};

use crate::{helper::*, word::CairoWord};
use ark_ff::Field;
use core::iter::repeat;

/// This data structure stores the memory of the program
pub struct CairoMemory<F> {
    /// length of the public memory
    codelen: usize,
    /// full memory vector, None if non initialized
    data: Vec<Option<CairoWord<F>>>,
}

impl<F: Field> Index<F> for CairoMemory<F> {
    type Output = Option<CairoWord<F>>;
    fn index(&self, idx: F) -> &Self::Output {
        // Safely convert idx from F to usize (since this is a memory address
        // idx should not be too big, this should be safe)
        let addr: u64 = idx.to_u64();
        &self.data[addr as usize]
    }
}

impl<F: Field> IndexMut<F> for CairoMemory<F> {
    fn index_mut(&mut self, idx: F) -> &mut Self::Output {
        let addr: u64 = idx.to_u64();
        self.resize(addr); // Resize if necessary
        &mut self.data[addr as usize]
    }
}

impl<F: Field> Display for CairoMemory<F> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        for i in 1..self.len() {
            // Visualize content of memory excluding the 0th dummy entry
            if let Some(elem) = self[F::from(i)] {
                writeln!(f, "{0:>6}: 0x{1:}", i, elem.word().to_hex_be())
                    .map_err(|_| core::fmt::Error)?;
            } else {
                writeln!(f, "{i:>6}: None").map_err(|_| core::fmt::Error)?;
            }
        }
        Ok(())
    }
}

impl<F: Field> CairoMemory<F> {
    /// Create a new memory structure from a vector of field elements
    pub fn new(input: Vec<F>) -> CairoMemory<F> {
        // Initialized with the public memory (compiled instructions only)
        // starts intentionally with a zero word for ease of testing
        let mut aux = vec![F::zero()];
        aux.extend(input);
        CairoMemory {
            codelen: aux.len() - 1,
            data: aux.into_iter().map(|i| Some(CairoWord::new(i))).collect(),
        }
    }

    /// Get size of the public memory
    pub fn get_codelen(&self) -> usize {
        self.codelen
    }

    /// Get size of the full memory including dummy 0th entry
    pub fn len(&self) -> u64 {
        self.data.len() as u64
    }

    /// Returns whether the memory is empty (either length 0, or with the dummy first entry)
    pub fn is_empty(&self) -> bool {
        self.data.len() < 2
    }

    /// Resizes memory with enough additional None slots if necessary before writing or reading
    fn resize(&mut self, addr: u64) {
        // if you want to access an index of the memory but its size is less or equal than this
        // you will need to extend the vector with enough spaces (taking into account that
        // vectors start by index 0, the 0 address is dummy, and size starts in 1)
        if let Some(additional) = addr.checked_sub(self.len() - 1) {
            self.data.extend(repeat(None).take(additional as usize));
        }
    }

    /// Write u64 element in memory address
    pub fn write(&mut self, addr: F, elem: F) {
        self[addr] = Some(CairoWord::new(elem));
    }

    /// Read element in memory address
    pub fn read(&mut self, addr: F) -> Option<F> {
        self.resize(addr.to_u64()); // Resize if necessary
        self[addr].map(|x| x.word())
    }
}