binius_circuits/
util.rs

1// Copyright 2026 The Binius Developers
2//! Small shared circuit gadgets.
3
4use binius_core::Word;
5use binius_frontend::{CircuitBuilder, Wire};
6
7/// Zero the high `n` bits of a 64-bit word, keeping the low `64 - n` bits in place.
8///
9/// Lowers to a left-then-right shift pair. The two shifts do not compose into one shifted
10/// operand, so gate fusion commits the intermediate and spends one constraint on it — the same
11/// count masking with a `band` against a constant costs today. The pair is the cheaper form only
12/// once a committed linear definition lowers to a Zero constraint rather than an AND constraint.
13///
14/// # Example
15///
16/// ```
17/// use binius_circuits::util::clear_high_bits;
18/// use binius_frontend::CircuitBuilder;
19///
20/// let builder = CircuitBuilder::new();
21/// let word = builder.add_witness();
22/// // Keep the low 32 bits, zeroing the high 32.
23/// let low_half = clear_high_bits(&builder, word, 32);
24/// ```
25pub fn clear_high_bits(builder: &CircuitBuilder, w: Wire, n: u32) -> Wire {
26	builder.shr(builder.shl(w, n), n)
27}
28
29/// Pack two 32-bit values into the two halves of one 64-bit wire.
30///
31/// The first argument lands in the low half, the second in the high half.
32///
33/// ```text
34///     bits 32..64  <-  second argument, shifted up
35///     bits  0..32  <-  first argument, masked down
36/// ```
37///
38/// Neither operand has to arrive zero-extended.
39/// The shift that lifts one discards its high bits, and the other is masked explicitly.
40pub(crate) fn pack_u32_words(builder: &CircuitBuilder, lo: Wire, hi: Wire) -> Wire {
41	builder.bxor(clear_high_bits(builder, lo, 32), builder.shl(hi, 32))
42}
43
44/// Splits each 64-bit wire into two little-endian 32-bit word wires (low half, then high half).
45///
46/// Returns exactly `num_words` words, zero-padding when `data` runs out.
47pub(crate) fn split_u32_words(
48	builder: &CircuitBuilder,
49	data: &[Wire],
50	num_words: usize,
51) -> Vec<Wire> {
52	let mut words = Vec::with_capacity(num_words);
53	for &w in data {
54		if words.len() >= num_words {
55			break;
56		}
57		words.push(clear_high_bits(builder, w, 32));
58		if words.len() >= num_words {
59			break;
60		}
61		words.push(builder.shr(w, 32));
62	}
63	while words.len() < num_words {
64		words.push(builder.add_constant_64(0));
65	}
66	words
67}
68
69/// Splits a byte vector into `num_words` 32-bit words, forcing every byte at index `>= valid_bytes`
70/// to zero.
71///
72/// The zeroing closes a malleability gap:
73/// - a byte vector leaves bytes past its length unconstrained,
74/// - a hash compression mixes the whole block, including those bytes,
75/// - pinning them stops a prover from choosing the padding to alter the digest.
76///
77/// Each word is handled by its position relative to the content:
78/// - fully inside: passed through,
79/// - fully past: replaced by the zero constant,
80/// - straddling the boundary: masked to its low valid bytes.
81pub(crate) fn zeroed_u32_words(
82	builder: &CircuitBuilder,
83	data: &[Wire],
84	valid_bytes: usize,
85	num_words: usize,
86) -> Vec<Wire> {
87	let raw = split_u32_words(builder, data, num_words);
88	let zero = builder.add_constant_64(0);
89	(0..num_words)
90		.map(|i| {
91			let word_start = 4 * i;
92			if word_start + 4 <= valid_bytes {
93				raw[i]
94			} else if word_start >= valid_bytes {
95				zero
96			} else {
97				let keep_bits = (valid_bytes - word_start) * 8;
98				clear_high_bits(builder, raw[i], (64 - keep_bits) as u32)
99			}
100		})
101		.collect()
102}
103
104/// Returns a wire that is all-ones exactly when every wire in `booleans` is all-ones.
105///
106/// The fold starts from the all-ones constant, so an empty iterator yields all-ones.
107pub(crate) fn all_true(builder: &CircuitBuilder, booleans: impl IntoIterator<Item = Wire>) -> Wire {
108	booleans
109		.into_iter()
110		.fold(builder.add_constant(Word::ALL_ONE), |lhs, rhs| builder.band(lhs, rhs))
111}
binius_circuits/util.rs

binius_circuits/
util.rs
