binius_circuits/
u32fib.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_core::oracle::{OracleId, ShiftVariant};
4use binius_field::{BinaryField1b, BinaryField32b, TowerField};
5use binius_macros::arith_expr;
6use binius_maybe_rayon::prelude::*;
7use rand::{thread_rng, Rng};
8
9use crate::{
10	arithmetic,
11	builder::{types::F, ConstraintSystemBuilder},
12	transparent::step_down,
13};
14
15pub fn u32fib(
16	builder: &mut ConstraintSystemBuilder,
17	name: impl ToString,
18	log_size: usize,
19) -> Result<OracleId, anyhow::Error> {
20	builder.push_namespace(name);
21	let current = builder.add_committed("current", log_size, BinaryField1b::TOWER_LEVEL);
22	let next = builder.add_shifted("next", current, 32, log_size, ShiftVariant::LogicalRight)?;
23	let next_next =
24		builder.add_shifted("next_next", current, 64, log_size, ShiftVariant::LogicalRight)?;
25
26	if let Some(witness) = builder.witness() {
27		let mut current = witness.new_column::<BinaryField1b>(current);
28		let mut next = witness.new_column::<BinaryField1b>(next);
29		let mut next_next = witness.new_column::<BinaryField1b>(next_next);
30
31		let mut rng = thread_rng();
32		let current = current.as_mut_slice::<u32>();
33		current[0] = rng.gen();
34		current[1] = rng.gen();
35		for i in 2..current.len() {
36			current[i] = rng.gen();
37			(current[i], _) = current[i - 1].overflowing_add(current[i - 2]);
38		}
39		(next.as_mut_slice::<u32>(), &current[1..])
40			.into_par_iter()
41			.for_each(|(next, current)| {
42				*next = *current;
43			});
44		(next_next.as_mut_slice::<u32>(), &current[2..])
45			.into_par_iter()
46			.for_each(|(next_next, current)| {
47				*next_next = *current;
48			});
49	}
50
51	let packed_log_size = log_size - 5;
52	let enabled = step_down(builder, "enabled", packed_log_size, (1 << packed_log_size) - 2)?;
53	let sum = arithmetic::u32::add(builder, "sum", current, next, arithmetic::Flags::Unchecked)?;
54	let sum_packed = builder.add_packed("sum_packed", sum, 5)?;
55	let next_next_packed = builder.add_packed("next_next_packed", next_next, 5)?;
56
57	if let Some(witness) = builder.witness() {
58		let next_next_packed_witness = witness.get::<BinaryField1b>(next_next)?;
59		witness.set(next_next_packed, next_next_packed_witness.repacked::<BinaryField32b>())?;
60
61		let sum_packed_witness = witness.get::<BinaryField1b>(sum)?;
62		witness.set(sum_packed, sum_packed_witness.repacked::<BinaryField32b>())?;
63	}
64
65	builder.assert_zero(
66		"step",
67		[sum_packed, next_next_packed, enabled],
68		arith_expr!(F[a, b, enabled] = (a - b) * enabled),
69	);
70
71	builder.pop_namespace();
72	Ok(current)
73}
74
75#[cfg(test)]
76mod tests {
77	use crate::builder::test_utils::test_circuit;
78
79	#[test]
80	fn test_u32fib() {
81		test_circuit(|builder| {
82			let log_size_1b = 14;
83			let _ = super::u32fib(builder, "u32fib", log_size_1b)?;
84			Ok(vec![])
85		})
86		.unwrap();
87	}
88}
binius_circuits/u32fib.rs

binius_circuits/
u32fib.rs
