winter_air/proof/
table.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use alloc::vec::Vec;
7use core::iter::FusedIterator;
8
9use math::FieldElement;
10use utils::ByteReader;
11
12use super::{DeserializationError, SliceReader};
13
14// CONSTANTS
15// ================================================================================================
16
17const MAX_ROWS: usize = 255;
18const MAX_COLS: usize = 255;
19
20// TABLE
21// ================================================================================================
22
23/// A two-dimensional table of field elements arranged in row-major order.
24///
25/// This struct is used primarily to hold queried values of execution trace segments and constraint
26/// evaluations. In such cases, each row in the table corresponds to a single query, and each
27/// column corresponds to a trace segment column or a constraint evaluation column.
28#[derive(Debug, Clone)]
29pub struct Table<E: FieldElement> {
30    data: Vec<E>,
31    row_width: usize,
32}
33
34impl<E: FieldElement> Table<E> {
35    // CONSTRUCTORS
36    // --------------------------------------------------------------------------------------------
37    /// Returns a new [Table] instantiated with data from the provided bytes.
38    ///
39    /// # Panics
40    /// Panics if:
41    /// * Specified number of rows is 0 or greater than 255.
42    /// * Specified number of columns is 0 or greater than 255.
43    /// * Provided bytes do not encode valid field elements required to fill the table.
44    pub fn from_bytes(
45        bytes: &[u8],
46        num_rows: usize,
47        num_cols: usize,
48    ) -> Result<Self, DeserializationError> {
49        assert!(num_rows > 0, "number of rows must be greater than 0");
50        assert!(
51            num_rows < MAX_ROWS,
52            "number of rows cannot exceed {MAX_ROWS}, but was {num_rows}"
53        );
54        assert!(num_cols > 0, "number of columns must be greater than 0");
55        assert!(
56            num_cols < MAX_ROWS,
57            "number of columns cannot exceed {MAX_COLS}, but was {num_cols}"
58        );
59
60        let mut reader = SliceReader::new(bytes);
61        let num_elements = num_rows * num_cols;
62        Ok(Self {
63            data: reader.read_many(num_elements)?,
64            row_width: num_cols,
65        })
66    }
67
68    // PUBLIC ACCESSORS
69    // --------------------------------------------------------------------------------------------
70
71    /// Returns number of rows in this table.
72    pub fn num_rows(&self) -> usize {
73        self.data.len() / self.row_width
74    }
75
76    /// Returns number of columns in this table.
77    pub fn num_columns(&self) -> usize {
78        self.row_width
79    }
80
81    /// Returns a reference to a row at the specified index.
82    pub fn get_row(&self, row_idx: usize) -> &[E] {
83        let row_offset = row_idx * self.row_width;
84        &self.data[row_offset..row_offset + self.row_width]
85    }
86
87    /// Returns an iterator over rows of this table.
88    pub fn rows(&self) -> RowIterator<E> {
89        RowIterator::new(self)
90    }
91
92    // TABLE PROCESSING
93    // --------------------------------------------------------------------------------------------
94
95    /// Combines multiple tables together into a single table by stacking tables column-wise (e.g.
96    /// the number of rows remains the same but the number of columns changes).
97    ///
98    /// Currently, this method does not support inputs containing more than one table.
99    ///
100    /// # Panics
101    /// Panics if the list of tables is empty.
102    pub fn merge(mut tables: Vec<Table<E>>) -> Table<E> {
103        assert!(!tables.is_empty(), "cannot merge an empty set of tables");
104        if tables.len() == 1 {
105            tables.remove(0)
106        } else {
107            unimplemented!("merging of multiple tables is not yet implemented")
108        }
109    }
110}
111
112// COLUMN ITERATOR
113// ================================================================================================
114
115pub struct RowIterator<'a, E: FieldElement> {
116    table: &'a Table<E>,
117    cursor: usize,
118}
119
120impl<'a, E: FieldElement> RowIterator<'a, E> {
121    pub fn new(table: &'a Table<E>) -> Self {
122        Self { table, cursor: 0 }
123    }
124}
125
126impl<'a, E: FieldElement> Iterator for RowIterator<'a, E> {
127    type Item = &'a [E];
128
129    fn next(&mut self) -> Option<Self::Item> {
130        match self.table.num_rows() - self.cursor {
131            0 => None,
132            _ => {
133                let row = self.table.get_row(self.cursor);
134                self.cursor += 1;
135                Some(row)
136            },
137        }
138    }
139}
140
141impl<E: FieldElement> ExactSizeIterator for RowIterator<'_, E> {
142    fn len(&self) -> usize {
143        self.table.num_rows()
144    }
145}
146
147impl<E: FieldElement> FusedIterator for RowIterator<'_, E> {}
winter_air/proof/table.rs

winter_air/proof/
table.rs
