binius_m3/builder/
column.rs

1// Copyright 2025 Irreducible Inc.
2
3use std::{marker::PhantomData, sync::Arc};
4
5use binius_core::{oracle::ShiftVariant, polynomial::MultivariatePoly};
6use binius_field::{ExtensionField, TowerField};
7use binius_math::ArithExpr;
8
9use super::{table::TableId, types::B128};
10
11/// An index of a column within a table.
12pub type ColumnIndex = usize;
13
14/// An index of a column within a table.
15pub type ColumnPartitionIndex = usize;
16
17/// A typed identifier for a column in a table.
18///
19/// The column has entries that are elements of `F`. In practice, the fields used will always be
20/// from the canonical tower (B1, B8, B16, B32, B64, B128). The second constant represents how many
21/// elements are packed vertically into a single logical row. For example, a column of type
22/// `Col<B1, 32>` will have 2^5 = 32 elements of `B1` packed into a single row.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct Col<F: TowerField, const VALUES_PER_ROW: usize = 1> {
25	pub table_id: TableId,
26	pub table_index: TableId,
27	// Denormalized partition index so that we can use it to construct arithmetic expressions over
28	// the partition columns.
29	pub partition_index: ColumnPartitionIndex,
30	_marker: PhantomData<F>,
31}
32
33impl<F: TowerField, const VALUES_PER_ROW: usize> Col<F, VALUES_PER_ROW> {
34	/// Creates a new typed column handle.
35	///
36	/// This has limited visibility to ensure that only the [`TableBuilder`] can create them. This
37	/// ensures the type parameters are consistent with the column definition.
38	pub(super) fn new(id: ColumnId, partition_index: ColumnPartitionIndex) -> Self {
39		assert!(VALUES_PER_ROW.is_power_of_two());
40		Self {
41			table_id: id.table_id,
42			table_index: id.table_index,
43			partition_index,
44			_marker: PhantomData,
45		}
46	}
47
48	pub fn shape(&self) -> ColumnShape {
49		ColumnShape {
50			tower_height: F::TOWER_LEVEL,
51			log_values_per_row: VALUES_PER_ROW.ilog2() as usize,
52		}
53	}
54
55	pub fn id(&self) -> ColumnId {
56		ColumnId {
57			table_id: self.table_id,
58			table_index: self.table_index,
59		}
60	}
61}
62
63/// Upcast a column from a subfield to an extension field..
64pub fn upcast_col<F, FSub, const V: usize>(col: Col<FSub, V>) -> Col<F, V>
65where
66	FSub: TowerField,
67	F: TowerField + ExtensionField<FSub>,
68{
69	let Col {
70		table_id,
71		table_index,
72		partition_index,
73		_marker: _,
74	} = col;
75	// REVIEW: Maybe this should retain the info of the smallest tower level
76	Col {
77		table_id,
78		table_index,
79		partition_index,
80		_marker: PhantomData,
81	}
82}
83
84/// Complete description of a column within a table.
85#[derive(Debug)]
86pub struct ColumnInfo<F: TowerField = B128> {
87	pub id: ColumnId,
88	pub col: ColumnDef<F>,
89	pub name: String,
90	pub shape: ColumnShape,
91	/// Whether the column is constrained to be non-zero.
92	pub is_nonzero: bool,
93}
94
95/// The shape of each cell in a column.
96#[derive(Debug, Clone, Copy)]
97pub struct ColumnShape {
98	/// The tower height of the field elements.
99	pub tower_height: usize,
100	/// The binary logarithm of the number of elements packed vertically per event row.
101	pub log_values_per_row: usize,
102}
103
104impl ColumnShape {
105	/// Returns the binary logarithm of the number of bits each cell occupies.
106	pub fn log_cell_size(&self) -> usize {
107		self.tower_height + self.log_values_per_row
108	}
109}
110
111/// Unique identifier for a column within a constraint system.
112///
113/// IDs are assigned when columns are added to the constraint system and remain stable when more
114/// columns are added.
115#[derive(Debug, Clone, Copy)]
116pub struct ColumnId {
117	pub table_id: TableId,
118	pub table_index: ColumnIndex,
119}
120
121/// A definition of a column in a table.
122#[derive(Debug)]
123pub enum ColumnDef<F: TowerField = B128> {
124	Committed {
125		tower_level: usize,
126	},
127	Selected {
128		col: ColumnId,
129		index: usize,
130		index_bits: usize,
131	},
132	Projected {
133		col: ColumnId,
134		start_index: usize,
135		query_size: usize,
136		query_bits: usize,
137	},
138	Shifted {
139		col: ColumnId,
140		offset: usize,
141		log_block_size: usize,
142		variant: ShiftVariant,
143	},
144	Packed {
145		col: ColumnId,
146		log_degree: usize,
147	},
148	Computed {
149		cols: Vec<ColumnIndex>,
150		expr: ArithExpr<F>,
151	},
152	Constant {
153		poly: Arc<dyn MultivariatePoly<F>>,
154	},
155	StaticExp {
156		bit_cols: Vec<ColumnIndex>,
157		base: F,
158		base_tower_level: usize,
159	},
160	DynamicExp {
161		bit_cols: Vec<ColumnIndex>,
162		base: ColumnIndex,
163		base_tower_level: usize,
164	},
165}
binius_m3/builder/column.rs

binius_m3/builder/
column.rs
