winter_air/proof/
table.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Copyright (c) Facebook, Inc. and its affiliates.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.

use alloc::vec::Vec;
use core::iter::FusedIterator;

use math::FieldElement;
use utils::ByteReader;

use super::{DeserializationError, SliceReader};

// CONSTANTS
// ================================================================================================

const MAX_ROWS: usize = 255;
const MAX_COLS: usize = 255;

// TABLE
// ================================================================================================

/// A two-dimensional table of field elements arranged in row-major order.
///
/// This struct is used primarily to hold queried values of execution trace segments and constraint
/// evaluations. In such cases, each row in the table corresponds to a single query, and each
/// column corresponds to a trace segment column or a constraint evaluation column.
#[derive(Debug, Clone)]
pub struct Table<E: FieldElement> {
    data: Vec<E>,
    row_width: usize,
}

impl<E: FieldElement> Table<E> {
    // CONSTRUCTORS
    // --------------------------------------------------------------------------------------------
    /// Returns a new [Table] instantiated with data from the provided bytes.
    ///
    /// # Panics
    /// Panics if:
    /// * Specified number of rows is 0 or greater than 255.
    /// * Specified number of columns is 0 or greater than 255.
    /// * Provided bytes do not encode valid field elements required to fill the table.
    pub fn from_bytes(
        bytes: &[u8],
        num_rows: usize,
        num_cols: usize,
    ) -> Result<Self, DeserializationError> {
        assert!(num_rows > 0, "number of rows must be greater than 0");
        assert!(
            num_rows < MAX_ROWS,
            "number of rows cannot exceed {MAX_ROWS}, but was {num_rows}"
        );
        assert!(num_cols > 0, "number of columns must be greater than 0");
        assert!(
            num_cols < MAX_ROWS,
            "number of columns cannot exceed {MAX_COLS}, but was {num_cols}"
        );

        let mut reader = SliceReader::new(bytes);
        let num_elements = num_rows * num_cols;
        Ok(Self {
            data: reader.read_many(num_elements)?,
            row_width: num_cols,
        })
    }

    // PUBLIC ACCESSORS
    // --------------------------------------------------------------------------------------------

    /// Returns number of rows in this table.
    pub fn num_rows(&self) -> usize {
        self.data.len() / self.row_width
    }

    /// Returns number of columns in this table.
    pub fn num_columns(&self) -> usize {
        self.row_width
    }

    /// Returns a reference to a row at the specified index.
    pub fn get_row(&self, row_idx: usize) -> &[E] {
        let row_offset = row_idx * self.row_width;
        &self.data[row_offset..row_offset + self.row_width]
    }

    /// Returns an iterator over rows of this table.
    pub fn rows(&self) -> RowIterator<E> {
        RowIterator::new(self)
    }

    // TABLE PROCESSING
    // --------------------------------------------------------------------------------------------

    /// Combines multiple tables together into a single table by stacking tables column-wise (e.g.
    /// the number of rows remains the same but the number of columns changes).
    ///
    /// Currently, this method does not support inputs containing more than one table.
    ///
    /// # Panics
    /// Panics if the list of tables is empty.
    pub fn merge(mut tables: Vec<Table<E>>) -> Table<E> {
        assert!(!tables.is_empty(), "cannot merge an empty set of tables");
        if tables.len() == 1 {
            tables.remove(0)
        } else {
            unimplemented!("merging of multiple tables is not yet implemented")
        }
    }
}

// COLUMN ITERATOR
// ================================================================================================

pub struct RowIterator<'a, E: FieldElement> {
    table: &'a Table<E>,
    cursor: usize,
}

impl<'a, E: FieldElement> RowIterator<'a, E> {
    pub fn new(table: &'a Table<E>) -> Self {
        Self { table, cursor: 0 }
    }
}

impl<'a, E: FieldElement> Iterator for RowIterator<'a, E> {
    type Item = &'a [E];

    fn next(&mut self) -> Option<Self::Item> {
        match self.table.num_rows() - self.cursor {
            0 => None,
            _ => {
                let row = self.table.get_row(self.cursor);
                self.cursor += 1;
                Some(row)
            },
        }
    }
}

impl<E: FieldElement> ExactSizeIterator for RowIterator<'_, E> {
    fn len(&self) -> usize {
        self.table.num_rows()
    }
}

impl<E: FieldElement> FusedIterator for RowIterator<'_, E> {}