binius_field/arch/portable/
packed_arithmetic.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use crate::{
4	PackedField,
5	binary_field::BinaryField,
6	linear_transformation::{FieldLinearTransformation, Transformation},
7	packed::PackedBinaryField,
8	underlier::{UnderlierWithBitOps, WithUnderlier},
9};
10
11/// Interleave using the provided even mask slice.
12///
13/// See [Hacker's Delight](https://dl.acm.org/doi/10.5555/2462741), Section 7-3.
14pub fn interleave_with_mask<U: UnderlierWithBitOps>(
15	a: U,
16	b: U,
17	log_block_len: usize,
18	even_mask: &[U],
19) -> (U, U) {
20	assert!(log_block_len < even_mask.len());
21
22	let block_len = 1 << log_block_len;
23	let t = ((a >> block_len) ^ b) & even_mask[log_block_len];
24	let c = a ^ t << block_len;
25	let d = b ^ t;
26
27	(c, d)
28}
29
30/// Generate the mask with ones in the odd packed element positions and zeros in even
31macro_rules! interleave_mask_even {
32	($underlier:ty, $tower_level:literal) => {{
33		let scalar_bits = 1 << $tower_level;
34
35		let mut mask: $underlier = (1 << scalar_bits) - 1;
36		let log_width = <$underlier>::LOG_BITS - $tower_level;
37		let mut i = 1;
38		while i < log_width {
39			mask |= mask << (scalar_bits << i);
40			i += 1;
41		}
42
43		mask
44	}};
45}
46
47pub(crate) use interleave_mask_even;
48
49/// Packed transformation implementation.
50/// Stores bases in a form of:
51/// [
52///     [<base vec 1> ... <base vec 1>],
53///     ...
54///     [<base vec N> ... <base vec N>]
55/// ]
56/// Transformation complexity is `N*log(N)` where `N` is `OP::Scalar::DEGREE`.
57pub struct PackedTransformation<OP> {
58	bases: Vec<OP>,
59}
60
61impl<OP> PackedTransformation<OP>
62where
63	OP: PackedBinaryField,
64{
65	pub fn new<Data: AsRef<[OP::Scalar]> + Sync>(
66		transformation: &FieldLinearTransformation<OP::Scalar, Data>,
67	) -> Self {
68		Self {
69			bases: transformation
70				.bases()
71				.iter()
72				.map(|base| OP::broadcast(*base))
73				.collect(),
74		}
75	}
76}
77
78/// Broadcast lowest field for each element, e.g. `[<0001><0000>] -> [<1111><0000>]`
79fn broadcast_lowest_bit<U: UnderlierWithBitOps>(mut data: U, log_packed_bits: usize) -> U {
80	for i in 0..log_packed_bits {
81		data |= data << (1 << i)
82	}
83
84	data
85}
86
87impl<U, IP, OP, IF, OF> Transformation<IP, OP> for PackedTransformation<OP>
88where
89	IP: PackedField<Scalar = IF> + WithUnderlier<Underlier = U>,
90	OP: PackedField<Scalar = OF> + WithUnderlier<Underlier = U>,
91	IF: BinaryField,
92	OF: BinaryField,
93	U: UnderlierWithBitOps,
94{
95	fn transform(&self, input: &IP) -> OP {
96		let mut result = OP::zero();
97		let ones = OP::one().to_underlier();
98		let mut input = input.to_underlier();
99
100		for base in &self.bases {
101			let base_component = input & ones;
102			// contains ones at positions which correspond to non-zero components
103			let mask = broadcast_lowest_bit(base_component, OF::LOG_DEGREE);
104			result += OP::from_underlier(mask & base.to_underlier());
105			input = input >> 1;
106		}
107
108		result
109	}
110}
binius_field/arch/portable/packed_arithmetic.rs

binius_field/arch/portable/
packed_arithmetic.rs
