miden_processor/trace/
utils.rs

1use alloc::{string::ToString, vec::Vec};
2use core::slice;
3
4use miden_air::trace::MainTrace;
5
6use super::chiplets::Chiplets;
7use crate::{Felt, RowIndex, debug::BusDebugger, field::ExtensionField, utils::uninit_vector};
8#[cfg(test)]
9use crate::{operation::Operation, utils::ToElements};
10
11// TRACE FRAGMENT
12// ================================================================================================
13
14/// TODO: add docs
15pub struct TraceFragment<'a> {
16    data: Vec<&'a mut [Felt]>,
17    num_rows: usize,
18}
19
20impl<'a> TraceFragment<'a> {
21    /// Creates a new [TraceFragment] with the expected number of columns and rows.
22    ///
23    /// The memory needed to hold the trace fragment data is not allocated during construction.
24    pub fn new(num_columns: usize, num_rows: usize) -> Self {
25        TraceFragment {
26            data: Vec::with_capacity(num_columns),
27            num_rows,
28        }
29    }
30
31    // PUBLIC ACCESSORS
32    // --------------------------------------------------------------------------------------------
33
34    /// Returns the number of columns in this execution trace fragment.
35    pub fn width(&self) -> usize {
36        self.data.len()
37    }
38
39    /// Returns the number of rows in this execution trace fragment.
40    pub fn len(&self) -> usize {
41        self.num_rows
42    }
43
44    // DATA MUTATORS
45    // --------------------------------------------------------------------------------------------
46
47    /// Updates a single cell in this fragment with provided value.
48    #[inline(always)]
49    pub fn set(&mut self, row_idx: RowIndex, col_idx: usize, value: Felt) {
50        self.data[col_idx][row_idx] = value;
51    }
52
53    /// Returns a mutable iterator to the columns of this fragment.
54    pub fn columns(&mut self) -> slice::IterMut<'_, &'a mut [Felt]> {
55        self.data.iter_mut()
56    }
57
58    /// Adds a new column to this fragment by pushing a mutable slice with the first `self.len()`
59    /// elements of the provided column.
60    ///
61    /// Returns the rest of the provided column as a separate mutable slice.
62    pub fn push_column_slice(&mut self, column: &'a mut [Felt]) -> &'a mut [Felt] {
63        let (column_fragment, rest) = column.split_at_mut(self.num_rows);
64        self.data.push(column_fragment);
65        rest
66    }
67
68    // TEST METHODS
69    // --------------------------------------------------------------------------------------------
70
71    #[cfg(test)]
72    pub fn trace_to_fragment(trace: &'a mut [Vec<Felt>]) -> Self {
73        assert!(!trace.is_empty(), "expected trace to have at least one column");
74        let mut data = Vec::new();
75        for column in trace.iter_mut() {
76            data.push(column.as_mut_slice());
77        }
78
79        let num_rows = data[0].len();
80        Self { data, num_rows }
81    }
82}
83
84// TRACE LENGTH SUMMARY
85// ================================================================================================
86
87/// Contains the data about lengths of the trace parts.
88///
89/// - `main_trace_len` contains the length of the main trace.
90/// - `range_trace_len` contains the length of the range checker trace.
91/// - `chiplets_trace_len` contains the trace lengths of the all chiplets (hash, bitwise, memory,
92///   kernel ROM)
93#[derive(Debug, Default, Eq, PartialEq, Clone, Copy)]
94pub struct TraceLenSummary {
95    main_trace_len: usize,
96    range_trace_len: usize,
97    chiplets_trace_len: ChipletsLengths,
98}
99
100impl TraceLenSummary {
101    pub fn new(
102        main_trace_len: usize,
103        range_trace_len: usize,
104        chiplets_trace_len: ChipletsLengths,
105    ) -> Self {
106        TraceLenSummary {
107            main_trace_len,
108            range_trace_len,
109            chiplets_trace_len,
110        }
111    }
112
113    /// Returns length of the main trace.
114    pub fn main_trace_len(&self) -> usize {
115        self.main_trace_len
116    }
117
118    /// Returns length of the range checker trace.
119    pub fn range_trace_len(&self) -> usize {
120        self.range_trace_len
121    }
122
123    /// Returns [ChipletsLengths] which contains trace lengths of all chilplets.
124    pub fn chiplets_trace_len(&self) -> ChipletsLengths {
125        self.chiplets_trace_len
126    }
127
128    /// Returns the maximum of all component lengths.
129    pub fn trace_len(&self) -> usize {
130        self.range_trace_len
131            .max(self.main_trace_len)
132            .max(self.chiplets_trace_len.trace_len())
133    }
134
135    /// Returns `trace_len` rounded up to the next power of two.
136    pub fn padded_trace_len(&self) -> usize {
137        self.trace_len().next_power_of_two()
138    }
139
140    /// Returns the percent (0 - 100) of the steps that were added to the trace to pad it to the
141    /// next power of tow.
142    pub fn padding_percentage(&self) -> usize {
143        (self.padded_trace_len() - self.trace_len()) * 100 / self.padded_trace_len()
144    }
145}
146
147// CHIPLET LENGTHS
148// ================================================================================================
149
150/// Contains trace lengths of all chilplets: hash, bitwise, memory and kernel ROM trace
151/// lengths.
152#[derive(Default, Clone, Copy, Debug, PartialEq, Eq)]
153pub struct ChipletsLengths {
154    hash_chiplet_len: usize,
155    bitwise_chiplet_len: usize,
156    memory_chiplet_len: usize,
157    kernel_rom_len: usize,
158}
159
160impl ChipletsLengths {
161    pub fn new(chiplets: &Chiplets) -> Self {
162        ChipletsLengths {
163            hash_chiplet_len: chiplets.bitwise_start().into(),
164            bitwise_chiplet_len: chiplets.memory_start() - chiplets.bitwise_start(),
165            memory_chiplet_len: chiplets.kernel_rom_start() - chiplets.memory_start(),
166            kernel_rom_len: chiplets.padding_start() - chiplets.kernel_rom_start(),
167        }
168    }
169
170    pub fn from_parts(
171        hash_len: usize,
172        bitwise_len: usize,
173        memory_len: usize,
174        kernel_len: usize,
175    ) -> Self {
176        ChipletsLengths {
177            hash_chiplet_len: hash_len,
178            bitwise_chiplet_len: bitwise_len,
179            memory_chiplet_len: memory_len,
180            kernel_rom_len: kernel_len,
181        }
182    }
183
184    /// Returns the length of the hash chiplet trace
185    pub fn hash_chiplet_len(&self) -> usize {
186        self.hash_chiplet_len
187    }
188
189    /// Returns the length of the bitwise trace
190    pub fn bitwise_chiplet_len(&self) -> usize {
191        self.bitwise_chiplet_len
192    }
193
194    /// Returns the length of the memory trace
195    pub fn memory_chiplet_len(&self) -> usize {
196        self.memory_chiplet_len
197    }
198
199    /// Returns the length of the kernel ROM trace
200    pub fn kernel_rom_len(&self) -> usize {
201        self.kernel_rom_len
202    }
203
204    /// Returns the length of the trace required to accommodate chiplet components and 1
205    /// mandatory padding row required for ensuring sufficient trace length for auxiliary connector
206    /// columns that rely on the memory chiplet.
207    pub fn trace_len(&self) -> usize {
208        self.hash_chiplet_len()
209            + self.bitwise_chiplet_len()
210            + self.memory_chiplet_len()
211            + self.kernel_rom_len()
212            + 1
213    }
214}
215
216// AUXILIARY COLUMN BUILDER
217// ================================================================================================
218
219/// Defines a builder responsible for building a single column in an auxiliary segment of the
220/// execution trace.
221pub(crate) trait AuxColumnBuilder<E: ExtensionField<Felt>> {
222    // REQUIRED METHODS
223    // --------------------------------------------------------------------------------------------
224
225    fn get_requests_at(
226        &self,
227        main_trace: &MainTrace,
228        alphas: &[E],
229        row: RowIndex,
230        debugger: &mut BusDebugger<E>,
231    ) -> E;
232
233    fn get_responses_at(
234        &self,
235        main_trace: &MainTrace,
236        alphas: &[E],
237        row: RowIndex,
238        debugger: &mut BusDebugger<E>,
239    ) -> E;
240
241    // PROVIDED METHODS
242    // --------------------------------------------------------------------------------------------
243
244    fn init_requests(
245        &self,
246        _main_trace: &MainTrace,
247        _alphas: &[E],
248        _debugger: &mut BusDebugger<E>,
249    ) -> E {
250        E::ONE
251    }
252
253    fn init_responses(
254        &self,
255        _main_trace: &MainTrace,
256        _alphas: &[E],
257        _debugger: &mut BusDebugger<E>,
258    ) -> E {
259        E::ONE
260    }
261
262    /// Builds the chiplets bus auxiliary trace column.
263    fn build_aux_column(&self, main_trace: &MainTrace, alphas: &[E]) -> Vec<E> {
264        let mut bus_debugger = BusDebugger::new("chiplets bus".to_string());
265
266        let mut requests: Vec<E> = unsafe { uninit_vector(main_trace.num_rows()) };
267        requests[0] = self.init_requests(main_trace, alphas, &mut bus_debugger);
268
269        let mut responses_prod: Vec<E> = unsafe { uninit_vector(main_trace.num_rows()) };
270        responses_prod[0] = self.init_responses(main_trace, alphas, &mut bus_debugger);
271
272        let mut requests_running_prod = requests[0];
273
274        // Product of all requests to be inverted, used to compute inverses of requests.
275        for row_idx in 0..main_trace.num_rows() - 1 {
276            let row = row_idx.into();
277
278            let response = self.get_responses_at(main_trace, alphas, row, &mut bus_debugger);
279            responses_prod[row_idx + 1] = responses_prod[row_idx] * response;
280
281            let request = self.get_requests_at(main_trace, alphas, row, &mut bus_debugger);
282            requests[row_idx + 1] = request;
283            requests_running_prod *= request;
284        }
285
286        // Use batch-inversion method to compute running product of `response[i]/request[i]`.
287        let mut result_aux_column = responses_prod;
288        let mut requests_running_divisor = requests_running_prod.inverse();
289        for i in (0..main_trace.num_rows()).rev() {
290            result_aux_column[i] *= requests_running_divisor;
291            requests_running_divisor *= requests[i];
292        }
293
294        #[cfg(any(test, feature = "bus-debugger"))]
295        assert!(bus_debugger.is_empty(), "{bus_debugger}");
296
297        result_aux_column
298    }
299}
300
301// U32 HELPERS
302// ================================================================================================
303
304/// Splits an element into two 16 bit integer limbs. It assumes that the field element contains a
305/// valid 32-bit integer value.
306pub(crate) fn split_element_u32_into_u16(value: Felt) -> (Felt, Felt) {
307    let (hi, lo) = split_u32_into_u16(value.as_canonical_u64());
308    (Felt::new(hi as u64), Felt::new(lo as u64))
309}
310
311/// Splits a u64 integer assumed to contain a 32-bit value into two u16 integers.
312///
313/// # Errors
314/// Fails in debug mode if the provided value is not a 32-bit value.
315pub(crate) fn split_u32_into_u16(value: u64) -> (u16, u16) {
316    const U32MAX: u64 = u32::MAX as u64;
317    debug_assert!(value <= U32MAX, "not a 32-bit value");
318
319    let lo = value as u16;
320    let hi = (value >> 16) as u16;
321
322    (hi, lo)
323}
324
325// TEST HELPERS
326// ================================================================================================
327
328#[cfg(test)]
329pub fn build_span_with_respan_ops() -> (Vec<Operation>, Vec<Felt>) {
330    let iv = [1, 3, 5, 7, 9, 11, 13, 15, 17].to_elements();
331    let ops = vec![
332        Operation::Push(iv[0]),
333        Operation::Push(iv[1]),
334        Operation::Push(iv[2]),
335        Operation::Push(iv[3]),
336        Operation::Push(iv[4]),
337        Operation::Push(iv[5]),
338        Operation::Push(iv[6]),
339        // next batch
340        Operation::Push(iv[7]),
341        Operation::Push(iv[8]),
342        Operation::Add,
343        // drops to make sure stack overflow is empty on exit
344        Operation::Drop,
345        Operation::Drop,
346        Operation::Drop,
347        Operation::Drop,
348        Operation::Drop,
349        Operation::Drop,
350        Operation::Drop,
351        Operation::Drop,
352    ];
353    (ops, iv)
354}
miden_processor/trace/utils.rs

miden_processor/trace/
utils.rs
