Skip to main content

binius_field/arch/portable/
packed_arithmetic.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::ops::{Shl, Shr};
5
6use crate::underlier::UnderlierType;
7
8/// Interleave using the provided even mask slice.
9///
10/// See [Hacker's Delight](https://dl.acm.org/doi/10.5555/2462741), Section 7-3.
11pub fn interleave_with_mask<U: UnderlierType + Shr<usize, Output = U> + Shl<usize, Output = U>>(
12	a: U,
13	b: U,
14	log_block_len: usize,
15	even_mask: &[U],
16) -> (U, U) {
17	assert!(log_block_len < even_mask.len());
18
19	let block_len = 1 << log_block_len;
20	let t = ((a >> block_len) ^ b) & even_mask[log_block_len];
21	let c = a ^ t << block_len;
22	let d = b ^ t;
23
24	(c, d)
25}
26
27/// Generate the mask with ones in the odd packed element positions and zeros in even
28macro_rules! interleave_mask_even {
29	($underlier:ty, $tower_level:literal) => {{
30		let scalar_bits = 1 << $tower_level;
31
32		let mut mask: $underlier = (1 << scalar_bits) - 1;
33		let log_width = <$underlier>::LOG_BITS - $tower_level;
34		let mut i = 1;
35		while i < log_width {
36			mask |= mask << (scalar_bits << i);
37			i += 1;
38		}
39
40		mask
41	}};
42}
43
44pub(crate) use interleave_mask_even;