miden_processor/trace/
utils.rs

1use alloc::vec::Vec;
2use core::slice;
3
4use miden_air::{trace::main_trace::MainTrace, RowIndex};
5#[cfg(test)]
6use vm_core::{utils::ToElements, Operation};
7
8use super::{Felt, FieldElement, NUM_RAND_ROWS};
9use crate::{chiplets::Chiplets, utils::uninit_vector};
10
11// TRACE FRAGMENT
12// ================================================================================================
13
14/// TODO: add docs
15pub struct TraceFragment<'a> {
16    data: Vec<&'a mut [Felt]>,
17}
18
19impl<'a> TraceFragment<'a> {
20    /// Creates a new TraceFragment with its data allocated to the specified capacity.
21    pub fn new(capacity: usize) -> Self {
22        TraceFragment { data: Vec::with_capacity(capacity) }
23    }
24
25    // PUBLIC ACCESSORS
26    // --------------------------------------------------------------------------------------------
27
28    /// Returns the number of columns in this execution trace fragment.
29    pub fn width(&self) -> usize {
30        self.data.len()
31    }
32
33    /// Returns the number of rows in this execution trace fragment.
34    pub fn len(&self) -> usize {
35        self.data[0].len()
36    }
37
38    // DATA MUTATORS
39    // --------------------------------------------------------------------------------------------
40
41    /// Updates a single cell in this fragment with provided value.
42    #[inline(always)]
43    pub fn set(&mut self, row_idx: RowIndex, col_idx: usize, value: Felt) {
44        self.data[col_idx][row_idx] = value;
45    }
46
47    /// Returns a mutable iterator to the columns of this fragment.
48    pub fn columns(&mut self) -> slice::IterMut<'_, &'a mut [Felt]> {
49        self.data.iter_mut()
50    }
51
52    /// Adds a new column to this fragment by pushing a mutable slice with the first `len`
53    /// elements of the provided column. Returns the rest of the provided column as a separate
54    /// mutable slice.
55    pub fn push_column_slice(&mut self, column: &'a mut [Felt], len: usize) -> &'a mut [Felt] {
56        let (column_fragment, rest) = column.split_at_mut(len);
57        self.data.push(column_fragment);
58        rest
59    }
60
61    // TEST METHODS
62    // --------------------------------------------------------------------------------------------
63
64    #[cfg(test)]
65    pub fn trace_to_fragment(trace: &'a mut [Vec<Felt>]) -> Self {
66        let mut data = Vec::new();
67        for column in trace.iter_mut() {
68            data.push(column.as_mut_slice());
69        }
70        Self { data }
71    }
72}
73
74// TRACE LENGTH SUMMARY
75// ================================================================================================
76
77/// Contains the data about lengths of the trace parts.
78///
79/// - `main_trace_len` contains the length of the main trace.
80/// - `range_trace_len` contains the length of the range checker trace.
81/// - `chiplets_trace_len` contains the trace lengths of the all chiplets (hash, bitwise, memory,
82///   kernel ROM)
83#[derive(Debug, Default, Eq, PartialEq, Clone, Copy)]
84pub struct TraceLenSummary {
85    main_trace_len: usize,
86    range_trace_len: usize,
87    chiplets_trace_len: ChipletsLengths,
88}
89
90impl TraceLenSummary {
91    pub fn new(
92        main_trace_len: usize,
93        range_trace_len: usize,
94        chiplets_trace_len: ChipletsLengths,
95    ) -> Self {
96        TraceLenSummary {
97            main_trace_len,
98            range_trace_len,
99            chiplets_trace_len,
100        }
101    }
102
103    /// Returns length of the main trace.
104    pub fn main_trace_len(&self) -> usize {
105        self.main_trace_len
106    }
107
108    /// Returns length of the range checker trace.
109    pub fn range_trace_len(&self) -> usize {
110        self.range_trace_len
111    }
112
113    /// Returns [ChipletsLengths] which contains trace lengths of all chilplets.
114    pub fn chiplets_trace_len(&self) -> ChipletsLengths {
115        self.chiplets_trace_len
116    }
117
118    /// Returns the maximum of all component lengths.
119    pub fn trace_len(&self) -> usize {
120        self.range_trace_len
121            .max(self.main_trace_len)
122            .max(self.chiplets_trace_len.trace_len())
123    }
124
125    /// Returns `trace_len` rounded up to the next power of two.
126    pub fn padded_trace_len(&self) -> usize {
127        (self.trace_len() + NUM_RAND_ROWS).next_power_of_two()
128    }
129
130    /// Returns the percent (0 - 100) of the steps that were added to the trace to pad it to the
131    /// next power of tow.
132    pub fn padding_percentage(&self) -> usize {
133        (self.padded_trace_len() - self.trace_len()) * 100 / self.padded_trace_len()
134    }
135}
136
137/// Contains trace lengths of all chilplets: hash, bitwise, memory and kernel ROM trace
138/// lengths.
139#[derive(Default, Clone, Copy, Debug, PartialEq, Eq)]
140pub struct ChipletsLengths {
141    hash_chiplet_len: usize,
142    bitwise_chiplet_len: usize,
143    memory_chiplet_len: usize,
144    kernel_rom_len: usize,
145}
146
147impl ChipletsLengths {
148    pub fn new(chiplets: &Chiplets) -> Self {
149        ChipletsLengths {
150            hash_chiplet_len: chiplets.bitwise_start().into(),
151            bitwise_chiplet_len: chiplets.memory_start() - chiplets.bitwise_start(),
152            memory_chiplet_len: chiplets.kernel_rom_start() - chiplets.memory_start(),
153            kernel_rom_len: chiplets.padding_start() - chiplets.kernel_rom_start(),
154        }
155    }
156
157    pub fn from_parts(
158        hash_len: usize,
159        bitwise_len: usize,
160        memory_len: usize,
161        kernel_len: usize,
162    ) -> Self {
163        ChipletsLengths {
164            hash_chiplet_len: hash_len,
165            bitwise_chiplet_len: bitwise_len,
166            memory_chiplet_len: memory_len,
167            kernel_rom_len: kernel_len,
168        }
169    }
170
171    /// Returns the length of the hash chiplet trace
172    pub fn hash_chiplet_len(&self) -> usize {
173        self.hash_chiplet_len
174    }
175
176    /// Returns the length of the bitwise trace
177    pub fn bitwise_chiplet_len(&self) -> usize {
178        self.bitwise_chiplet_len
179    }
180
181    /// Returns the length of the memory trace
182    pub fn memory_chiplet_len(&self) -> usize {
183        self.memory_chiplet_len
184    }
185
186    /// Returns the length of the kernel ROM trace
187    pub fn kernel_rom_len(&self) -> usize {
188        self.kernel_rom_len
189    }
190
191    /// Returns the length of the trace required to accommodate chiplet components and 1
192    /// mandatory padding row required for ensuring sufficient trace length for auxiliary connector
193    /// columns that rely on the memory chiplet.
194    pub fn trace_len(&self) -> usize {
195        self.hash_chiplet_len()
196            + self.bitwise_chiplet_len()
197            + self.memory_chiplet_len()
198            + self.kernel_rom_len()
199            + 1
200    }
201}
202
203// AUXILIARY COLUMN BUILDER
204// ================================================================================================
205
206/// Defines a builder responsible for building a single column in an auxiliary segment of the
207/// execution trace.
208pub trait AuxColumnBuilder<E: FieldElement<BaseField = Felt>> {
209    // REQUIRED METHODS
210    // --------------------------------------------------------------------------------------------
211
212    fn get_requests_at(&self, main_trace: &MainTrace, alphas: &[E], row: RowIndex) -> E;
213
214    fn get_responses_at(&self, main_trace: &MainTrace, alphas: &[E], row: RowIndex) -> E;
215
216    // PROVIDED METHODS
217    // --------------------------------------------------------------------------------------------
218
219    fn init_requests(&self, _main_trace: &MainTrace, _alphas: &[E]) -> E {
220        E::ONE
221    }
222
223    fn init_responses(&self, _main_trace: &MainTrace, _alphas: &[E]) -> E {
224        E::ONE
225    }
226
227    /// Builds the chiplets bus auxiliary trace column.
228    fn build_aux_column(&self, main_trace: &MainTrace, alphas: &[E]) -> Vec<E> {
229        let mut responses_prod: Vec<E> = unsafe { uninit_vector(main_trace.num_rows()) };
230        let mut requests: Vec<E> = unsafe { uninit_vector(main_trace.num_rows()) };
231
232        responses_prod[0] = self.init_responses(main_trace, alphas);
233        requests[0] = self.init_requests(main_trace, alphas);
234
235        let mut requests_running_prod = requests[0];
236        for row_idx in 0..main_trace.num_rows() - 1 {
237            let row = row_idx.into();
238            responses_prod[row_idx + 1] =
239                responses_prod[row_idx] * self.get_responses_at(main_trace, alphas, row);
240            requests[row_idx + 1] = self.get_requests_at(main_trace, alphas, row);
241            requests_running_prod *= requests[row_idx + 1];
242        }
243
244        let mut requests_running_divisor = requests_running_prod.inv();
245        let mut result_aux_column = responses_prod;
246        for i in (0..main_trace.num_rows()).rev() {
247            result_aux_column[i] *= requests_running_divisor;
248            requests_running_divisor *= requests[i];
249        }
250        result_aux_column
251    }
252}
253
254// TEST HELPERS
255// ================================================================================================
256
257#[cfg(test)]
258pub fn build_span_with_respan_ops() -> (Vec<Operation>, Vec<Felt>) {
259    let iv = [1, 3, 5, 7, 9, 11, 13, 15, 17].to_elements();
260    let ops = vec![
261        Operation::Push(iv[0]),
262        Operation::Push(iv[1]),
263        Operation::Push(iv[2]),
264        Operation::Push(iv[3]),
265        Operation::Push(iv[4]),
266        Operation::Push(iv[5]),
267        Operation::Push(iv[6]),
268        // next batch
269        Operation::Push(iv[7]),
270        Operation::Push(iv[8]),
271        Operation::Add,
272        // drops to make sure stack overflow is empty on exit
273        Operation::Drop,
274        Operation::Drop,
275        Operation::Drop,
276        Operation::Drop,
277        Operation::Drop,
278        Operation::Drop,
279        Operation::Drop,
280        Operation::Drop,
281    ];
282    (ops, iv)
283}
miden_processor/trace/utils.rs

miden_processor/trace/
utils.rs
