miden_processor/trace/
utils.rs

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

miden_processor/trace/
utils.rs
