1use binius_core::constraint_system::{ConstraintSystem, InoutSegment, Operand};
4use binius_field::{BinaryField, FieldOps, util::FieldFn};
5use binius_math::{
6 line::extrapolate_line,
7 multilinear::{
8 eq::eq_ind_zero,
9 sparse::{
10 SparseBitVector, evaluate_sparse_b1_multilinear, evaluate_sparse_b1_multilinear_native,
11 },
12 },
13};
14use getset::{CopyGetters, Getters};
15
16use super::LOG_SHIFT_COUNT;
17use crate::reduction::{LOG_OPERANDS, log_constraint_point};
18
19const LOG_TERM_BITS: usize = LOG_OPERANDS + 2 * LOG_SHIFT_COUNT;
21
22#[derive(Debug, Clone, Getters, CopyGetters)]
57pub struct WiringInfo {
58 #[getset(get = "pub")]
60 public_segment: SparseBitVector,
61 #[getset(get = "pub")]
63 hidden_segment: SparseBitVector,
64 #[getset(get_copy = "pub")]
66 log_public_words: usize,
67 #[getset(get_copy = "pub")]
70 log_segment_words: usize,
71 #[getset(get_copy = "pub")]
73 log_constraint_point: usize,
74}
75
76impl WiringInfo {
77 pub fn new(cs: &ConstraintSystem, inout: InoutSegment) -> Self {
85 let log_public_words = cs.log_public_words(inout);
86 let log_segment_words = cs.log_segment_words(inout);
87 let log_constraint_point = log_constraint_point(cs);
88 let log_words = [log_public_words, log_segment_words];
89 let log_lens = log_words.map(|log_words| LOG_TERM_BITS + log_words + log_constraint_point);
90 assert!(
91 log_lens[1] < u64::BITS as usize,
92 "the wiring address needs {} bits; at most 63 fit",
93 log_lens[1]
94 );
95
96 let n_public_words = cs.n_public_words(inout);
98 let mut indices = [Vec::new(), Vec::new()];
99 let mut push = |column: usize, constraint_index: usize, terms: &Operand| {
100 for term in terms {
101 let word = cs.word_offset(term.value_index);
102 let (segment, word) = if word < n_public_words {
103 (0, word)
104 } else {
105 (1, word - n_public_words)
106 };
107 let index = column as u64
108 | (term.inner().index() as u64) << LOG_OPERANDS
109 | (term.outer().index() as u64) << (LOG_OPERANDS + LOG_SHIFT_COUNT)
110 | (word as u64) << LOG_TERM_BITS
111 | (constraint_index as u64) << (LOG_TERM_BITS + log_words[segment]);
112 indices[segment].push(index);
113 }
114 };
115
116 fn walk<C: AsRef<[Operand; ARITY]>, const ARITY: usize>(
119 first_column: usize,
120 constraints: &[C],
121 push: &mut impl FnMut(usize, usize, &Operand),
122 ) -> usize {
123 for (constraint_index, constraint) in constraints.iter().enumerate() {
124 for (operand_index, terms) in constraint.as_ref().iter().enumerate() {
125 push(first_column + operand_index, constraint_index, terms);
126 }
127 }
128 first_column + ARITY
129 }
130
131 let column = walk(0, &cs.zero_constraints, &mut push);
132 let column = walk(column, &cs.and_constraints, &mut push);
133 let column = walk(column, &cs.imul_constraints, &mut push);
134 walk(column, &cs.bmul_constraints, &mut push);
135
136 let [public, hidden] = indices;
137 let [public_log_len, hidden_log_len] = log_lens;
138 Self {
139 public_segment: SparseBitVector::new(public_log_len, public),
140 hidden_segment: SparseBitVector::new(hidden_log_len, hidden),
141 log_public_words,
142 log_segment_words,
143 log_constraint_point,
144 }
145 }
146
147 fn eval<E: FieldOps>(&self, vals: &[E], eval: impl Fn(&SparseBitVector, &[E]) -> E) -> E {
149 let (r_segment, point_hid) = vals.split_first().expect("the input leads with r_segment");
150 assert_eq!(point_hid.len(), self.hidden_segment.log_len());
151
152 let public_end = LOG_TERM_BITS + self.log_public_words;
153 let r_y_end = LOG_TERM_BITS + self.log_segment_words;
154 let point_pub = [&point_hid[..public_end], &point_hid[r_y_end..]].concat();
155 let public_eval =
156 eq_ind_zero(&point_hid[public_end..r_y_end]) * eval(&self.public_segment, &point_pub);
157 let hidden_eval = eval(&self.hidden_segment, point_hid);
158 extrapolate_line(public_eval, hidden_eval, r_segment.clone())
159 }
160}
161
162impl<F: BinaryField> FieldFn<F> for WiringInfo {
163 fn call<E: FieldOps<Scalar = F> + From<F>>(&self, vals: &[E]) -> E {
164 self.eval(vals, evaluate_sparse_b1_multilinear)
165 }
166
167 fn call_native(&self, vals: &[F]) -> F {
168 self.eval(vals, evaluate_sparse_b1_multilinear_native)
169 }
170}
171
172#[cfg(test)]
173mod tests {
174 use std::array;
175
176 use binius_core::{
177 ShiftVariant,
178 constraint_system::{
179 AndConstraint, BmulConstraint, ImulConstraint, Shift, ShiftedValueIndex, ValueIndex,
180 ValueSegment, ZeroConstraint,
181 },
182 word::Word,
183 };
184 use binius_field::Field;
185 use binius_math::{multilinear::eq::eq_ind_partial_eval_scalars, test_utils::random_scalars};
186 use rand::{RngExt, SeedableRng, rngs::StdRng};
187
188 use super::*;
189 use crate::config::B128;
190
191 fn random_system(rng: &mut StdRng, with_imul: bool) -> ConstraintSystem {
195 let constants = vec![Word::ZERO, Word::ONE, Word::ALL_ONE];
196 let n_inout = 5;
197 let n_private = 12;
198 let term = |rng: &mut StdRng| {
199 let value_index = match rng.random_range(0..3) {
200 0 => ValueIndex::constant(rng.random_range(0..constants.len()) as u32),
201 1 => ValueIndex::inout(rng.random_range(0..n_inout) as u32),
202 _ => ValueIndex::private(rng.random_range(0..n_private) as u32),
203 };
204 let shift = |rng: &mut StdRng| Shift {
205 variant: [ShiftVariant::Sll, ShiftVariant::Sar, ShiftVariant::Rotr32]
206 [rng.random_range(0..3)],
207 amount: rng.random_range(0..Word::BITS) as u8,
208 };
209 ShiftedValueIndex::new(value_index, [shift(rng), shift(rng)])
210 };
211 let operand = |rng: &mut StdRng| (0..rng.random_range(0..3)).map(|_| term(rng)).collect();
212
213 ConstraintSystem {
214 zero_constraints: (0..5)
215 .map(|_| ZeroConstraint(array::from_fn(|_| operand(rng))))
216 .collect(),
217 and_constraints: (0..7)
218 .map(|_| AndConstraint(array::from_fn(|_| operand(rng))))
219 .collect(),
220 imul_constraints: if with_imul {
221 (0..3)
222 .map(|_| ImulConstraint(array::from_fn(|_| operand(rng))))
223 .collect()
224 } else {
225 Vec::new()
226 },
227 bmul_constraints: (0..3)
228 .map(|_| BmulConstraint(array::from_fn(|_| operand(rng))))
229 .collect(),
230 constants,
231 n_inout,
232 n_private,
233 }
234 }
235
236 fn contract(cs: &ConstraintSystem, inout: InoutSegment, vals: &[B128]) -> B128 {
242 let (&r_segment, point) = vals.split_first().unwrap();
243 let r_y_len = cs.log_segment_words(inout);
244 let (inner, rest) = point.split_at(LOG_OPERANDS + LOG_SHIFT_COUNT);
245 let (outer, rest) = rest.split_at(LOG_SHIFT_COUNT);
246 let (r_y, r_x) = rest.split_at(r_y_len);
247
248 let inner = eq_ind_partial_eval_scalars(inner);
249 let outer = eq_ind_partial_eval_scalars(outer);
250 let value = eq_ind_partial_eval_scalars(&[r_y, &[r_segment]].concat());
251 let constraint = eq_ind_partial_eval_scalars(r_x);
252
253 let hidden = 1 << r_y_len;
254 let address = |value_index: ValueIndex| {
255 let index = value_index.index() as usize;
256 match (value_index.segment(), inout) {
257 (ValueSegment::Constant, _) => index,
258 (ValueSegment::InOut, InoutSegment::Public) => cs.n_const() + index,
259 (ValueSegment::InOut, InoutSegment::Hidden) => hidden + index,
260 (ValueSegment::Private, InoutSegment::Public) => hidden + index,
261 (ValueSegment::Private, InoutSegment::Hidden) => hidden + cs.n_inout + index,
262 (ValueSegment::Scratch, _) => unreachable!(),
263 }
264 };
265
266 let operations: [(usize, Vec<&[Operand]>); 4] = [
268 (0, cs.zero_constraints.iter().map(|c| &c.0[..]).collect()),
269 (1, cs.and_constraints.iter().map(|c| &c.0[..]).collect()),
270 (4, cs.imul_constraints.iter().map(|c| &c.0[..]).collect()),
271 (8, cs.bmul_constraints.iter().map(|c| &c.0[..]).collect()),
272 ];
273 let mut acc = B128::ZERO;
274 for (first_column, constraints) in operations {
275 for (constraint_index, operands) in constraints.into_iter().enumerate() {
276 for (operand_index, terms) in operands.iter().enumerate() {
277 for term in terms {
278 let column = first_column + operand_index;
279 acc += constraint[constraint_index]
280 * inner[(term.inner().index() << LOG_OPERANDS) | column]
281 * outer[term.outer().index()]
282 * value[address(term.value_index)];
283 }
284 }
285 }
286 }
287 acc
288 }
289
290 #[test]
291 fn the_wiring_bits_evaluate_to_the_contracted_tensor() {
292 let mut rng = StdRng::seed_from_u64(31);
293 for with_imul in [false, true] {
294 let cs = random_system(&mut rng, with_imul);
295 for inout in [InoutSegment::Public, InoutSegment::Hidden] {
296 let wiring = WiringInfo::new(&cs, inout);
297 let vals = random_scalars::<B128>(&mut rng, 1 + wiring.hidden_segment().log_len());
298
299 let got = FieldFn::<B128>::call::<B128>(&wiring, &vals);
300 assert_ne!(got, B128::ZERO);
302 assert_eq!(got, contract(&cs, inout, &vals), "{inout:?}, imul: {with_imul}");
303 assert_eq!(got, FieldFn::<B128>::call_native(&wiring, &vals));
304 }
305 }
306 }
307
308 #[test]
309 fn a_repeated_term_cancels() {
310 let term = ShiftedValueIndex::new(ValueIndex::private(1), [Shift::srl(7), Shift::srl(3)]);
312 let mut cs = empty_system(0, 2);
313 cs.and_constraints = vec![AndConstraint([vec![term, term], vec![term], vec![]])];
314 let wiring = WiringInfo::new(&cs, InoutSegment::Public);
315 assert!(wiring.public_segment().indices().is_empty());
316 assert_eq!(wiring.hidden_segment().indices().len(), 1);
317 }
318
319 fn empty_system(log_constraints: usize, log_words: usize) -> ConstraintSystem {
321 ConstraintSystem {
322 constants: Vec::new(),
323 n_inout: 0,
324 n_private: 1 << log_words,
325 zero_constraints: vec![ZeroConstraint::default(); 1 << log_constraints],
326 and_constraints: Vec::new(),
327 imul_constraints: Vec::new(),
328 bmul_constraints: Vec::new(),
329 }
330 }
331
332 #[test]
333 fn the_widest_address_that_fits_is_63_bits() {
334 let wiring = WiringInfo::new(&empty_system(15, 26), InoutSegment::Public);
335 assert_eq!(wiring.hidden_segment().log_len(), 63);
336 }
337
338 #[test]
339 #[should_panic(expected = "the wiring address needs 64 bits")]
340 fn a_system_whose_address_does_not_fit_is_rejected() {
341 let _ = WiringInfo::new(&empty_system(16, 26), InoutSegment::Public);
342 }
343}