miden_processor/trace/
utils.rs

1use alloc::{string::ToString, vec::Vec};
2use core::slice;
3
4use miden_air::{RowIndex, trace::main_trace::MainTrace};
5#[cfg(test)]
6use miden_core::{Operation, utils::ToElements};
7
8use super::{Felt, FieldElement, NUM_RAND_ROWS};
9use crate::{chiplets::Chiplets, debug::BusDebugger, 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(
213        &self,
214        main_trace: &MainTrace,
215        alphas: &[E],
216        row: RowIndex,
217        debugger: &mut BusDebugger<E>,
218    ) -> E;
219
220    fn get_responses_at(
221        &self,
222        main_trace: &MainTrace,
223        alphas: &[E],
224        row: RowIndex,
225        debugger: &mut BusDebugger<E>,
226    ) -> E;
227
228    // PROVIDED METHODS
229    // --------------------------------------------------------------------------------------------
230
231    fn init_requests(
232        &self,
233        _main_trace: &MainTrace,
234        _alphas: &[E],
235        _debugger: &mut BusDebugger<E>,
236    ) -> E {
237        E::ONE
238    }
239
240    fn init_responses(
241        &self,
242        _main_trace: &MainTrace,
243        _alphas: &[E],
244        _debugger: &mut BusDebugger<E>,
245    ) -> E {
246        E::ONE
247    }
248
249    /// Builds the chiplets bus auxiliary trace column.
250    fn build_aux_column(&self, main_trace: &MainTrace, alphas: &[E]) -> Vec<E> {
251        let mut bus_debugger = BusDebugger::new("chiplets bus".to_string());
252
253        let mut requests: Vec<E> = unsafe { uninit_vector(main_trace.num_rows()) };
254        requests[0] = self.init_requests(main_trace, alphas, &mut bus_debugger);
255
256        let mut responses_prod: Vec<E> = unsafe { uninit_vector(main_trace.num_rows()) };
257        responses_prod[0] = self.init_responses(main_trace, alphas, &mut bus_debugger);
258
259        let mut requests_running_prod = requests[0];
260
261        // Product of all requests to be inverted, used to compute inverses of requests.
262        for row_idx in 0..main_trace.num_rows() - 1 {
263            let row = row_idx.into();
264
265            let response = self.get_responses_at(main_trace, alphas, row, &mut bus_debugger);
266            responses_prod[row_idx + 1] = responses_prod[row_idx] * response;
267
268            let request = self.get_requests_at(main_trace, alphas, row, &mut bus_debugger);
269            requests[row_idx + 1] = request;
270            requests_running_prod *= request;
271        }
272
273        // Use batch-inversion method to compute running product of `response[i]/request[i]`.
274        let mut result_aux_column = responses_prod;
275        let mut requests_running_divisor = requests_running_prod.inv();
276        for i in (0..main_trace.num_rows()).rev() {
277            result_aux_column[i] *= requests_running_divisor;
278            requests_running_divisor *= requests[i];
279        }
280
281        #[cfg(any(test, feature = "bus-debugger"))]
282        assert!(bus_debugger.is_empty(), "{bus_debugger}");
283
284        result_aux_column
285    }
286}
287
288// TEST HELPERS
289// ================================================================================================
290
291#[cfg(test)]
292pub fn build_span_with_respan_ops() -> (Vec<Operation>, Vec<Felt>) {
293    let iv = [1, 3, 5, 7, 9, 11, 13, 15, 17].to_elements();
294    let ops = vec![
295        Operation::Push(iv[0]),
296        Operation::Push(iv[1]),
297        Operation::Push(iv[2]),
298        Operation::Push(iv[3]),
299        Operation::Push(iv[4]),
300        Operation::Push(iv[5]),
301        Operation::Push(iv[6]),
302        // next batch
303        Operation::Push(iv[7]),
304        Operation::Push(iv[8]),
305        Operation::Add,
306        // drops to make sure stack overflow is empty on exit
307        Operation::Drop,
308        Operation::Drop,
309        Operation::Drop,
310        Operation::Drop,
311        Operation::Drop,
312        Operation::Drop,
313        Operation::Drop,
314        Operation::Drop,
315    ];
316    (ops, iv)
317}
miden_processor/trace/utils.rs

miden_processor/trace/
utils.rs
