openvm_circuit/system/memory/controller/
dimensions.rs

1use derive_new::new;
2use openvm_stark_backend::p3_util::log2_strict_usize;
3use serde::{Deserialize, Serialize};
4
5use crate::{
6    arch::{MemoryConfig, ADDR_SPACE_OFFSET},
7    system::memory::CHUNK,
8};
9
10// indicates that there are 2^`addr_space_height` address spaces numbered starting from 1,
11// and that each address space has 2^`address_height` addresses numbered starting from 0
12#[derive(Clone, Copy, Debug, Serialize, Deserialize, new)]
13pub struct MemoryDimensions {
14    /// Address space height
15    pub addr_space_height: usize,
16    /// Pointer height
17    pub address_height: usize,
18}
19
20impl MemoryDimensions {
21    pub fn overall_height(&self) -> usize {
22        self.addr_space_height + self.address_height
23    }
24    /// Convert an address label (address space, block id) to its index in the memory merkle tree.
25    ///
26    /// Assumes that `label = (addr_space, block_id)` satisfies `block_id < 2^address_height`.
27    ///
28    /// This function is primarily for internal use for accessing the memory merkle tree.
29    /// Users should use a higher-level API when possible.
30    pub fn label_to_index(&self, (addr_space, block_id): (u32, u32)) -> u64 {
31        debug_assert!(
32            block_id < (1 << self.address_height),
33            "block_id={block_id} exceeds address_height={}",
34            self.address_height
35        );
36        (((addr_space - ADDR_SPACE_OFFSET) as u64) << self.address_height) + block_id as u64
37    }
38
39    /// Convert an index in the memory merkle tree to an address label (address space, block id).
40    ///
41    /// This function performs the inverse operation of `label_to_index`.
42    pub fn index_to_label(&self, index: u64) -> (u32, u32) {
43        let block_id = (index & ((1 << self.address_height) - 1)) as u32;
44        let addr_space = (index >> self.address_height) as u32 + ADDR_SPACE_OFFSET;
45        (addr_space, block_id)
46    }
47}
48
49impl MemoryConfig {
50    pub fn memory_dimensions(&self) -> MemoryDimensions {
51        MemoryDimensions {
52            addr_space_height: self.addr_space_height,
53            address_height: self.pointer_max_bits - log2_strict_usize(CHUNK),
54        }
55    }
56}
openvm_circuit/system/memory/controller/dimensions.rs

openvm_circuit/system/memory/controller/
dimensions.rs
