1use alloc::vec::Vec;
2use core::borrow::BorrowMut;
3
4use miden_air::{
5 AceCols, QuadFeltExpr,
6 trace::{RowIndex, chiplets::ace::ACE_CHIPLET_NUM_COLS},
7};
8use miden_core::{
9 Felt, Word,
10 field::{BasedVectorSpace, QuadFelt},
11 serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
12};
13
14use super::{
15 MAX_NUM_ACE_WIRES,
16 instruction::{Op, decode_instruction},
17};
18use crate::{ContextId, errors::AceError};
19
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23#[cfg_attr(
24 all(feature = "arbitrary", test),
25 miden_test_serialization_macros::serialization_test
26)]
27struct ReadNode {
28 ptr: Felt,
29 id_0: Felt,
30 v_0: QuadFelt,
31 id_1: Felt,
32 v_1: QuadFelt,
33}
34
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39#[cfg_attr(
40 all(feature = "arbitrary", test),
41 miden_test_serialization_macros::serialization_test
42)]
43struct EvalNode {
44 ptr: Felt,
45 eval_op: Felt,
46 id_0: Felt,
47 v_0: QuadFelt,
48 id_1: Felt,
49 v_1: QuadFelt,
50 id_2: Felt,
51 v_2: QuadFelt,
52}
53
54#[derive(Debug, Clone, PartialEq, Eq)]
59#[cfg_attr(
60 all(feature = "arbitrary", test),
61 miden_test_serialization_macros::serialization_test
62)]
63pub struct CircuitEvaluation {
64 ctx: ContextId,
65 clk: RowIndex,
66 wire_bus: WireBus,
67 read_nodes: Vec<ReadNode>,
68 eval_nodes: Vec<EvalNode>,
69}
70
71impl CircuitEvaluation {
72 pub fn new(ctx: ContextId, clk: RowIndex, num_read_rows: u32, num_eval_rows: u32) -> Self {
79 let num_wires = 2 * (num_read_rows as u64) + (num_eval_rows as u64);
80 assert!(num_wires <= MAX_NUM_ACE_WIRES as u64, "too many wires");
81
82 Self {
83 ctx,
84 clk,
85 wire_bus: WireBus::new(num_wires as u32),
86 read_nodes: Vec::with_capacity(num_read_rows as usize),
87 eval_nodes: Vec::with_capacity(num_eval_rows as usize),
88 }
89 }
90
91 pub fn num_rows(&self) -> usize {
92 self.read_nodes.len() + self.eval_nodes.len()
93 }
94
95 pub fn clk(&self) -> u32 {
96 self.clk.into()
97 }
98
99 pub fn ctx(&self) -> u32 {
100 self.ctx.into()
101 }
102
103 pub fn num_read_rows(&self) -> u32 {
104 self.read_nodes.len() as u32
105 }
106
107 pub fn num_eval_rows(&self) -> u32 {
108 self.eval_nodes.len() as u32
109 }
110
111 pub fn do_read(&mut self, ptr: Felt, word: Word) {
114 let v_0 = QuadFelt::from_basis_coefficients_fn(|i: usize| [word[0], word[1]][i]);
115 let id_0 = self.wire_bus.insert(v_0);
116
117 let v_1 = QuadFelt::from_basis_coefficients_fn(|i: usize| [word[2], word[3]][i]);
118 let id_1 = self.wire_bus.insert(v_1);
119
120 self.read_nodes.push(ReadNode { ptr, id_0, v_0, id_1, v_1 });
121 }
122
123 pub fn do_eval(&mut self, ptr: Felt, instruction: Felt) -> Result<(), AceError> {
126 let (id_l, id_r, op) = decode_instruction(instruction)
127 .ok_or(AceError("failed to decode instruction".into()))?;
128
129 let v_l = self
130 .wire_bus
131 .read_value(id_l)
132 .ok_or(AceError("failed to read from the wiring bus".into()))?;
133 let id_1 = Felt::from_u32(id_l);
134
135 let v_r = self
136 .wire_bus
137 .read_value(id_r)
138 .ok_or(AceError("failed to read from the wiring bus".into()))?;
139 let id_2 = Felt::from_u32(id_r);
140
141 let v_0 = match op {
142 Op::Sub => v_l - v_r,
143 Op::Mul => v_l * v_r,
144 Op::Add => v_l + v_r,
145 };
146 let id_0 = self.wire_bus.insert(v_0);
147
148 let eval_op = match op {
149 Op::Sub => -Felt::ONE,
150 Op::Mul => Felt::ZERO,
151 Op::Add => Felt::ONE,
152 };
153
154 self.eval_nodes.push(EvalNode {
155 ptr,
156 eval_op,
157 id_0,
158 v_0,
159 id_1,
160 v_1: v_l,
161 id_2,
162 v_2: v_r,
163 });
164 Ok(())
165 }
166
167 pub fn fill(&self, offset: usize, out: &mut [Felt]) {
171 const W: usize = ACE_CHIPLET_NUM_COLS;
172 let (out_rows, _) = out.as_chunks_mut::<W>();
173 let num_read_rows = self.read_nodes.len();
174 let num_eval_rows = self.eval_nodes.len();
175
176 let ctx_felt: Felt = self.ctx.into();
177 let clk_felt: Felt = self.clk.into();
178 let eval_section_first_idx = Felt::from_u32(num_eval_rows as u32 - 1);
179 let mut multiplicities_iter = self.wire_bus.wires.iter().map(|(_v, m)| Felt::from_u32(*m));
180
181 for (i, node) in self.read_nodes.iter().enumerate() {
183 let cols: &mut AceCols<Felt> = out_rows[offset + i].as_mut_slice().borrow_mut();
184 cols.s_start = if i == 0 { Felt::ONE } else { Felt::ZERO };
185 cols.s_block = Felt::ZERO;
186 cols.ctx = ctx_felt;
187 cols.clk = clk_felt;
188 cols.ptr = node.ptr;
189 cols.id_0 = node.id_0;
190 cols.v_0 = quad_to_expr(node.v_0);
191 cols.id_1 = node.id_1;
192 cols.v_1 = quad_to_expr(node.v_1);
193
194 let m_0 = multiplicities_iter
195 .next()
196 .expect("the m0 multiplicities were not constructed properly");
197 let m_1 = multiplicities_iter
198 .next()
199 .expect("the m1 multiplicities were not constructed properly");
200
201 let read = cols.read_mut();
202 read.num_eval = eval_section_first_idx;
203 read.m_0 = m_0;
204 read.m_1 = m_1;
205 }
206
207 for (i, node) in self.eval_nodes.iter().enumerate() {
209 let cols: &mut AceCols<Felt> =
210 out_rows[offset + num_read_rows + i].as_mut_slice().borrow_mut();
211 cols.s_start = Felt::ZERO;
212 cols.s_block = Felt::ONE;
213 cols.ctx = ctx_felt;
214 cols.clk = clk_felt;
215 cols.ptr = node.ptr;
216 cols.eval_op = node.eval_op;
217 cols.id_0 = node.id_0;
218 cols.v_0 = quad_to_expr(node.v_0);
219 cols.id_1 = node.id_1;
220 cols.v_1 = quad_to_expr(node.v_1);
221
222 let m_0 = multiplicities_iter
223 .next()
224 .expect("the m0 multiplicities were not constructed properly");
225
226 let eval = cols.eval_mut();
227 eval.id_2 = node.id_2;
228 eval.v_2 = quad_to_expr(node.v_2);
229 eval.m_0 = m_0;
230 }
231
232 let next = multiplicities_iter.next();
233 debug_assert!(next.is_none());
234 }
235
236 pub fn output_value(&self) -> Option<QuadFelt> {
238 if !self.wire_bus.is_finalized() {
239 return None;
240 }
241 self.wire_bus.wires.last().map(|(v, _m)| *v)
242 }
243}
244
245fn quad_to_expr(v: QuadFelt) -> QuadFeltExpr<Felt> {
248 let c = v.as_basis_coefficients_slice();
249 QuadFeltExpr(c[0], c[1])
250}
251
252#[derive(Debug, Clone, PartialEq, Eq)]
264#[cfg_attr(
265 all(feature = "arbitrary", test),
266 miden_test_serialization_macros::serialization_test
267)]
268struct WireBus {
269 id_next: Felt,
271 wires: Vec<(QuadFelt, u32)>,
274 num_wires: u32,
276}
277
278impl WireBus {
279 fn new(num_wires: u32) -> Self {
280 Self {
281 wires: Vec::with_capacity(num_wires as usize),
282 num_wires,
283 id_next: Felt::from_u32(num_wires - 1),
284 }
285 }
286
287 fn insert(&mut self, value: QuadFelt) -> Felt {
289 debug_assert!(!self.is_finalized());
290 self.wires.push((value, 0));
291 let id = self.id_next;
292 self.id_next -= Felt::ONE;
293 id
294 }
295
296 fn read_value(&mut self, id: u32) -> Option<QuadFelt> {
299 let (v, m) = self
301 .num_wires
302 .checked_sub(id + 1)
303 .and_then(|id| self.wires.get_mut(id as usize))?;
304 *m += 1;
305 Some(*v)
306 }
307
308 fn is_finalized(&self) -> bool {
310 self.wires.len() == self.num_wires as usize
311 }
312}
313
314impl Serializable for ReadNode {
318 fn write_into<W: ByteWriter>(&self, target: &mut W) {
319 self.ptr.write_into(target);
320 self.id_0.write_into(target);
321 self.v_0.write_into(target);
322 self.id_1.write_into(target);
323 self.v_1.write_into(target);
324 }
325}
326
327impl Deserializable for ReadNode {
328 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
329 Ok(Self {
330 ptr: Felt::read_from(source)?,
331 id_0: Felt::read_from(source)?,
332 v_0: QuadFelt::read_from(source)?,
333 id_1: Felt::read_from(source)?,
334 v_1: QuadFelt::read_from(source)?,
335 })
336 }
337
338 fn min_serialized_size() -> usize {
339 Felt::min_serialized_size() * 3 + QuadFelt::min_serialized_size() * 2
340 }
341}
342
343impl Serializable for EvalNode {
344 fn write_into<W: ByteWriter>(&self, target: &mut W) {
345 self.ptr.write_into(target);
346 self.eval_op.write_into(target);
347 self.id_0.write_into(target);
348 self.v_0.write_into(target);
349 self.id_1.write_into(target);
350 self.v_1.write_into(target);
351 self.id_2.write_into(target);
352 self.v_2.write_into(target);
353 }
354}
355
356impl Deserializable for EvalNode {
357 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
358 Ok(Self {
359 ptr: Felt::read_from(source)?,
360 eval_op: Felt::read_from(source)?,
361 id_0: Felt::read_from(source)?,
362 v_0: QuadFelt::read_from(source)?,
363 id_1: Felt::read_from(source)?,
364 v_1: QuadFelt::read_from(source)?,
365 id_2: Felt::read_from(source)?,
366 v_2: QuadFelt::read_from(source)?,
367 })
368 }
369
370 fn min_serialized_size() -> usize {
371 Felt::min_serialized_size() * 5 + QuadFelt::min_serialized_size() * 3
372 }
373}
374
375impl Serializable for WireBus {
376 fn write_into<W: ByteWriter>(&self, target: &mut W) {
377 self.id_next.write_into(target);
378 self.wires.write_into(target);
379 self.num_wires.write_into(target);
380 }
381}
382
383impl Deserializable for WireBus {
384 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
385 let id_next = Felt::read_from(source)?;
386 let wires = Vec::<(QuadFelt, u32)>::read_from(source)?;
387 let wire_count = wires.len();
388 let num_wires = u32::read_from(source)?;
389 if num_wires == 0 {
390 return Err(DeserializationError::InvalidValue(
391 "ACE wire bus must contain at least one wire".into(),
392 ));
393 }
394 if num_wires > MAX_NUM_ACE_WIRES {
395 return Err(DeserializationError::InvalidValue(format!(
396 "ACE declared wire count {num_wires} exceeds maximum {MAX_NUM_ACE_WIRES}"
397 )));
398 }
399 if wire_count != num_wires as usize {
400 return Err(DeserializationError::InvalidValue(format!(
401 "ACE wire count {wire_count} does not match declared wire count {num_wires}"
402 )));
403 }
404 Ok(Self { id_next, wires, num_wires })
405 }
406
407 fn min_serialized_size() -> usize {
408 Felt::min_serialized_size() + Vec::<u8>::min_serialized_size() + u32::min_serialized_size()
409 }
410}
411
412impl Serializable for CircuitEvaluation {
413 fn write_into<W: ByteWriter>(&self, target: &mut W) {
414 self.ctx.write_into(target);
415 self.clk.write_into(target);
416 self.wire_bus.write_into(target);
417 self.read_nodes.write_into(target);
418 self.eval_nodes.write_into(target);
419 }
420}
421
422impl Deserializable for CircuitEvaluation {
423 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
424 let evaluation = Self {
425 ctx: ContextId::read_from(source)?,
426 clk: RowIndex::read_from(source)?,
427 wire_bus: WireBus::read_from(source)?,
428 read_nodes: Vec::<ReadNode>::read_from(source)?,
429 eval_nodes: Vec::<EvalNode>::read_from(source)?,
430 };
431 evaluation.validate_wire_count()?;
432 Ok(evaluation)
433 }
434
435 fn min_serialized_size() -> usize {
436 ContextId::min_serialized_size()
437 + RowIndex::min_serialized_size()
438 + WireBus::min_serialized_size()
439 + Vec::<ReadNode>::min_serialized_size()
440 + Vec::<EvalNode>::min_serialized_size()
441 }
442}
443
444impl CircuitEvaluation {
445 fn validate_wire_count(&self) -> Result<(), DeserializationError> {
446 if self.eval_nodes.is_empty() {
447 return Err(DeserializationError::InvalidValue(
448 "ACE circuit evaluation must contain at least one eval node".into(),
449 ));
450 }
451 let read_wires = self.read_nodes.len().checked_mul(2).ok_or_else(|| {
452 DeserializationError::InvalidValue("ACE read-node wire count overflow".into())
453 })?;
454 let expected_wires = read_wires.checked_add(self.eval_nodes.len()).ok_or_else(|| {
455 DeserializationError::InvalidValue("ACE total wire count overflow".into())
456 })?;
457
458 if expected_wires == 0 {
459 return Err(DeserializationError::InvalidValue(
460 "ACE circuit evaluation must contain at least one wire".into(),
461 ));
462 }
463 if expected_wires > MAX_NUM_ACE_WIRES as usize {
464 return Err(DeserializationError::InvalidValue(format!(
465 "ACE circuit evaluation wire count {expected_wires} exceeds maximum {MAX_NUM_ACE_WIRES}"
466 )));
467 }
468 if self.wire_bus.num_wires as usize != expected_wires {
469 return Err(DeserializationError::InvalidValue(format!(
470 "ACE wire bus count {} does not match read/eval node wire count {expected_wires}",
471 self.wire_bus.num_wires
472 )));
473 }
474
475 Ok(())
476 }
477}
478
479#[cfg(test)]
480mod serialization_tests {
481 use alloc::vec;
482
483 use super::*;
484
485 fn sample_read_node(value: QuadFelt) -> ReadNode {
486 ReadNode {
487 ptr: Felt::ZERO,
488 id_0: Felt::ZERO,
489 v_0: value,
490 id_1: Felt::ONE,
491 v_1: value,
492 }
493 }
494
495 fn sample_eval_node(value: QuadFelt) -> EvalNode {
496 EvalNode {
497 ptr: Felt::ZERO,
498 eval_op: Felt::ZERO,
499 id_0: Felt::ZERO,
500 v_0: value,
501 id_1: Felt::ZERO,
502 v_1: value,
503 id_2: Felt::ONE,
504 v_2: value,
505 }
506 }
507
508 #[test]
509 fn circuit_evaluation_read_rejects_mismatched_wire_bus_count() {
510 let value = QuadFelt::new([Felt::ONE, Felt::ZERO]);
511 let evaluation = CircuitEvaluation {
512 ctx: ContextId::from(0),
513 clk: RowIndex::from(0_u32),
514 wire_bus: WireBus {
515 id_next: Felt::ZERO,
516 wires: vec![(value, 0), (value, 0)],
517 num_wires: 2,
518 },
519 read_nodes: vec![sample_read_node(value)],
520 eval_nodes: vec![sample_eval_node(value)],
521 };
522
523 let err = CircuitEvaluation::read_from_bytes(&evaluation.to_bytes()).unwrap_err();
524 let DeserializationError::InvalidValue(message) = err else {
525 panic!("expected invalid ACE wire count error");
526 };
527 assert!(message.contains("does not match read/eval node wire count"));
528 }
529
530 #[test]
531 fn circuit_evaluation_read_rejects_empty_eval_section() {
532 let value = QuadFelt::new([Felt::ONE, Felt::ZERO]);
533 let evaluation = CircuitEvaluation {
534 ctx: ContextId::from(0),
535 clk: RowIndex::from(0_u32),
536 wire_bus: WireBus {
537 id_next: Felt::ZERO,
538 wires: vec![(value, 0), (value, 0)],
539 num_wires: 2,
540 },
541 read_nodes: vec![sample_read_node(value)],
542 eval_nodes: Vec::new(),
543 };
544
545 let err = CircuitEvaluation::read_from_bytes(&evaluation.to_bytes()).unwrap_err();
546 let DeserializationError::InvalidValue(message) = err else {
547 panic!("expected invalid ACE eval section error");
548 };
549 assert!(message.contains("at least one eval node"));
550 }
551}
552
553#[cfg(any(test, feature = "arbitrary"))]
557mod arbitrary {
558 use proptest::prelude::*;
559
560 use super::{CircuitEvaluation, ContextId, EvalNode, Felt, QuadFelt, ReadNode, WireBus};
561 use crate::RowIndex;
562
563 fn quad() -> impl Strategy<Value = QuadFelt> {
564 (any::<Felt>(), any::<Felt>()).prop_map(|(a, b)| QuadFelt::new([a, b]))
565 }
566
567 impl Arbitrary for ReadNode {
568 type Parameters = ();
569 type Strategy = BoxedStrategy<Self>;
570
571 fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
572 (any::<Felt>(), any::<Felt>(), quad(), any::<Felt>(), quad())
574 .prop_map(|(ptr, id_0, v_0, id_1, v_1)| Self { ptr, id_0, v_0, id_1, v_1 })
575 .boxed()
576 }
577 }
578
579 impl Arbitrary for EvalNode {
580 type Parameters = ();
581 type Strategy = BoxedStrategy<Self>;
582
583 fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
584 (
585 any::<Felt>(),
586 any::<Felt>(),
587 any::<Felt>(),
588 quad(),
589 any::<Felt>(),
590 quad(),
591 any::<Felt>(),
592 quad(),
593 )
594 .prop_map(|(ptr, eval_op, id_0, v_0, id_1, v_1, id_2, v_2)| Self {
595 ptr,
596 eval_op,
597 id_0,
598 v_0,
599 id_1,
600 v_1,
601 id_2,
602 v_2,
603 })
604 .boxed()
605 }
606 }
607
608 impl Arbitrary for WireBus {
609 type Parameters = ();
610 type Strategy = BoxedStrategy<Self>;
611
612 fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
613 proptest::collection::vec((quad(), any::<u32>()), 1..=8)
617 .prop_map(|wires| {
618 let num_wires = wires.len() as u32;
619 Self {
620 id_next: Felt::from_u32(num_wires - 1),
621 wires,
622 num_wires,
623 }
624 })
625 .boxed()
626 }
627 }
628
629 impl Arbitrary for CircuitEvaluation {
630 type Parameters = ();
631 type Strategy = BoxedStrategy<Self>;
632
633 fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
634 (any::<ContextId>(), any::<RowIndex>(), 0usize..=4, 1usize..=4)
638 .prop_flat_map(|(ctx, clk, read_count, eval_count)| {
639 (
640 Just(ctx),
641 Just(clk),
642 Just(read_count),
643 Just(eval_count),
644 proptest::collection::vec(any::<ReadNode>(), read_count),
645 proptest::collection::vec(any::<EvalNode>(), eval_count),
646 )
647 })
648 .prop_map(|(ctx, clk, read_count, eval_count, read_nodes, eval_nodes)| {
649 let num_wires = (2 * read_count + eval_count) as u32;
650 let mut wire_bus = WireBus::new(num_wires);
651 for node in &read_nodes {
652 wire_bus.insert(node.v_0);
653 wire_bus.insert(node.v_1);
654 }
655 for node in &eval_nodes {
656 wire_bus.insert(node.v_0);
657 }
658 Self {
659 ctx,
660 clk,
661 wire_bus,
662 read_nodes,
663 eval_nodes,
664 }
665 })
666 .boxed()
667 }
668 }
669}