binius_field/
util.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use std::iter;
4
5use crate::{Field, PackedField, UnderlierType, field::FieldOps};
6
7/// An arithmetic function over field elements, generic in the field it evaluates in.
8///
9/// A closure `FnOnce(&[F]) -> F` is monomorphic: it runs in one fixed field.
10/// Carrying the genericity on the method instead lets one value run in many fields:
11/// - natively, in the verifier's own base field `F`;
12/// - over any larger field `E` whose scalar is `F`.
13pub trait FieldFn<F: Field> {
14	/// Evaluates the function on `inputs` in the field `E`, returning one element.
15	///
16	/// The scalar of `E` is the base field `F`.
17	/// The `From<F>` bound lets the function embed base-field constants into `E`.
18	fn call<E: FieldOps<Scalar = F> + From<F>>(&self, inputs: &[E]) -> E;
19
20	/// Evaluates the function on `inputs` natively in the base field `F`.
21	///
22	/// The default is `self.call::<F>(inputs)`; implementors may override with a base-field
23	/// specialized fast path (e.g. deferred `WideMul` reduction) that the generic
24	/// [`call`](Self::call) — which cannot assume `E: WideMul` — can't express. Callers evaluating
25	/// in `F` should prefer this.
26	fn call_native(&self, inputs: &[F]) -> F {
27		self.call::<F>(inputs)
28	}
29}
30
31/// Iterate the powers of a given value, beginning with 1 (the 0'th power).
32pub fn powers<F: FieldOps>(val: F) -> impl Iterator<Item = F> {
33	iter::successors(Some(F::one()), move |power| Some(power.clone() * val.clone()))
34}
35
36/// Expands an array of field elements into all possible subset sums.
37///
38/// For an input array `[a, b, c]`, this computes all possible sums of subsets:
39/// `[0, a, b, a+b, c, a+c, b+c, a+b+c]`
40///
41/// This is used to create lookup tables for the Method of Four Russians optimization,
42/// where we precompute all possible combinations of a small set of values to avoid
43/// doing the additions at runtime.
44///
45/// ## Type Parameters
46///
47/// * `F` - The field element type
48/// * `N` - Size of the input array
49/// * `N_EXP2` - Size of the output array, must be 2^N
50///
51/// ## Arguments
52///
53/// * `elems` - Input array of N field elements
54///
55/// ## Returns
56///
57/// An array of size N_EXP2 containing all possible subset sums of the input elements
58///
59/// ## Preconditions
60///
61/// * N_EXP2 must equal 2^N
62///
63/// ## Example
64///
65/// ```ignore
66/// let input = [F::ONE, F::from(2)];
67/// let sums = expand_subset_sums_array(input);
68/// // sums = [F::ZERO, F::ONE, F::from(2), F::from(3)]
69/// ```
70pub fn expand_subset_sums_array<P: PackedField, const N: usize, const N_EXP2: usize>(
71	elems: [P; N],
72) -> [P; N_EXP2] {
73	assert_eq!(N_EXP2, 1 << N);
74
75	let mut expanded = [P::zero(); N_EXP2];
76	for (i, elem_i) in elems.into_iter().enumerate() {
77		let span = &mut expanded[..1 << (i + 1)];
78		let (lo_half, hi_half) = span.split_at_mut(1 << i);
79		for (lo_half_i, hi_half_i) in iter::zip(lo_half, hi_half) {
80			*hi_half_i = *lo_half_i + elem_i;
81		}
82	}
83	expanded
84}
85
86/// Expands `elems` into all `2^N` subset XOR combinations, indexed by subset bitmask.
87///
88/// Entry `mask` holds the XOR of `elems[i]` over every bit `i` set in `mask`. This is the
89/// bitwise-XOR analogue of [`expand_subset_sums_array`] over raw underliers, used to build Method
90/// of Four Russians lookup tables.
91///
92/// ## Preconditions
93///
94/// * `N_EXP2` must equal `2^N`
95pub fn expand_subset_xors<U: UnderlierType, const N: usize, const N_EXP2: usize>(
96	elems: [U; N],
97) -> [U; N_EXP2] {
98	assert_eq!(N_EXP2, 1 << N);
99
100	let mut expanded = [U::ZERO; N_EXP2];
101	for (i, elem_i) in elems.into_iter().enumerate() {
102		let span = &mut expanded[..1 << (i + 1)];
103		let (lo_half, hi_half) = span.split_at_mut(1 << i);
104		for (lo_half_i, hi_half_i) in iter::zip(lo_half, hi_half) {
105			*hi_half_i = *lo_half_i ^ elem_i;
106		}
107	}
108	expanded
109}
110
111#[cfg(test)]
112mod tests {
113	use std::array;
114
115	use proptest::prelude::*;
116	use rand::{SeedableRng, rngs::StdRng};
117
118	use super::*;
119	use crate::{BinaryField128bGhash, Random};
120
121	#[test]
122	fn test_powers_against_pow() {
123		let generator = BinaryField128bGhash::MULTIPLICATIVE_GENERATOR;
124		let power_values: Vec<_> = powers(generator).take(10).collect();
125
126		for i in 0..10 {
127			assert_eq!(power_values[i], generator.pow(i as u64));
128		}
129	}
130
131	type F = BinaryField128bGhash;
132
133	/// Expands `N` random elements and asserts that entry `index` of the resulting `2^N`-sized
134	/// lookup table equals the subset sum selected by the set bits of `index`.
135	fn check_subset_sums<const N: usize, const N_EXP2: usize>(seed: u64, index: usize) {
136		let mut rng = StdRng::seed_from_u64(seed);
137		let elems: [F; N] = array::from_fn(|_| F::random(&mut rng));
138
139		let result = expand_subset_sums_array::<_, N, N_EXP2>(elems);
140		assert_eq!(result.len(), N_EXP2);
141
142		// Compute expected sum based on the binary representation of index.
143		let index = index % N_EXP2;
144		let mut expected = F::ZERO;
145		for (bit_pos, &elem) in elems.iter().enumerate() {
146			if (index >> bit_pos) & 1 == 1 {
147				expected += elem;
148			}
149		}
150
151		assert_eq!(
152			result[index], expected,
153			"index {index} should hold the subset sum for its binary representation"
154		);
155	}
156
157	proptest! {
158		#[test]
159		fn test_expand_subset_sums_array_correctness(
160			n in 0usize..=8,  // Input length (small to avoid exponential blowup)
161			index in 0usize..256,  // Index to check
162		) {
163			// Dispatch to the const-generic helper: `expand_subset_sums_array` needs the output
164			// length `2^n` at compile time.
165			match n {
166				0 => check_subset_sums::<0, 1>(n as u64, index),
167				1 => check_subset_sums::<1, 2>(n as u64, index),
168				2 => check_subset_sums::<2, 4>(n as u64, index),
169				3 => check_subset_sums::<3, 8>(n as u64, index),
170				4 => check_subset_sums::<4, 16>(n as u64, index),
171				5 => check_subset_sums::<5, 32>(n as u64, index),
172				6 => check_subset_sums::<6, 64>(n as u64, index),
173				7 => check_subset_sums::<7, 128>(n as u64, index),
174				8 => check_subset_sums::<8, 256>(n as u64, index),
175				_ => unreachable!("n is constrained to 0..=8"),
176			}
177		}
178	}
179}
binius_field/util.rs

binius_field/
util.rs
