Skip to main content

binius_hash_prover/blake3/
portable.rs

1// Copyright 2026 The Binius Developers
2
3//! Experimental portable, auto-vectorized Blake3 multi-lane kernel.
4//!
5//! Two batched entry points share one block-compression core:
6//! - Leaf hashing, for any message up to one 1024-byte chunk.
7//! - Two-to-one inner-node compression, `blake3(left || right)` over a 64-byte pair.
8//!
9//! An alternative to driving the `blake3` crate's hand-written SIMD kernel.
10//! The bet: LLVM auto-vectorizes plain lane loops into whatever the target has.
11//!
12//! - Each of the 16 compression-state words is held as `[u32; N]`, one lane per message.
13//! - Every step is a fixed-width `0..N` loop of plain scalar `u32` arithmetic.
14//! - No intrinsics, no `unsafe`, no per-target code inside the loops.
15//!
16//! Lanes the vectorizer is expected to fill, per target:
17//! - NEON (128-bit) on ARM64 -> 4 lanes per vector.
18//! - AVX2 / AVX-512 on x86 -> 8 / 16 lanes per vector.
19//! - SVE2 on capable ARM64 -> width-agnostic vectors.
20//!
21//! Where a hand-written kernel beats the vectorizer, the loops become the fallback:
22//! - `load_block_words` hands the message transpose to the parent's `avx512` or `neon` module.
23//! - `compress_block` hands the block compression to the parent's `neon` module.
24//!
25//! Each hands over only on the lane counts that kernel claims; every other count runs the loops.
26//!
27//! Output is bit-identical to `blake3::hash`, pinned to the reference in tests.
28//! Scope: any message up to one 1024-byte chunk, including sub-block and partial-block leaves.
29
30use std::{array, mem::MaybeUninit};
31
32use binius_hash::Blake3Compression;
33use binius_utils::{
34	FixedSizeSerializeBytes, SerializeBytes,
35	rayon::{
36		iter::{IndexedParallelIterator, ParallelIterator},
37		slice::{ParallelSlice, ParallelSliceMut},
38	},
39};
40use blake3::{BLOCK_LEN, CHUNK_LEN, OUT_LEN};
41use digest::Output;
42
43#[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
44use super::avx512;
45#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
46use super::neon;
47use super::{CHUNK_END, CHUNK_START, IV, MSG_SCHEDULE, ROOT};
48use crate::{
49	parallel_compression::ParallelPseudoCompression,
50	parallel_digest::{
51		MultiDigest, ParallelDigest, ParallelDigestAdapter, ParallelMultidigestImpl,
52	},
53};
54
55/// Applies one Blake3 quarter-round across all `N` lanes.
56///
57/// The state words at positions `a, b, c, d` are mixed with two message words per lane.
58/// Every line is an independent `0..N` map, which is what the vectorizer turns into SIMD.
59#[inline(always)]
60fn quarter_round<const N: usize>(
61	v: &mut [[u32; N]; 16],
62	a: usize,
63	b: usize,
64	c: usize,
65	d: usize,
66	mx: &[u32; N],
67	my: &[u32; N],
68) {
69	// One lane per iteration; lanes are independent, so the loop vectorizes.
70	for i in 0..N {
71		v[a][i] = v[a][i].wrapping_add(v[b][i]).wrapping_add(mx[i]);
72		v[d][i] = (v[d][i] ^ v[a][i]).rotate_right(16);
73		v[c][i] = v[c][i].wrapping_add(v[d][i]);
74		v[b][i] = (v[b][i] ^ v[c][i]).rotate_right(12);
75		v[a][i] = v[a][i].wrapping_add(v[b][i]).wrapping_add(my[i]);
76		v[d][i] = (v[d][i] ^ v[a][i]).rotate_right(8);
77		v[c][i] = v[c][i].wrapping_add(v[d][i]);
78		v[b][i] = (v[b][i] ^ v[c][i]).rotate_right(7);
79	}
80}
81
82/// Applies round `R`: four column mixes, then four diagonal mixes.
83///
84/// The two message words each quarter-round folds in come from row `R` of the schedule table.
85#[inline(always)]
86fn round<const R: usize, const N: usize>(v: &mut [[u32; N]; 16], m: &[[u32; N]; 16]) {
87	// The 16 message words this round reads, in slot order.
88	let s = MSG_SCHEDULE[R];
89
90	// Columns.
91	quarter_round(v, 0, 4, 8, 12, &m[s[0]], &m[s[1]]);
92	quarter_round(v, 1, 5, 9, 13, &m[s[2]], &m[s[3]]);
93	quarter_round(v, 2, 6, 10, 14, &m[s[4]], &m[s[5]]);
94	quarter_round(v, 3, 7, 11, 15, &m[s[6]], &m[s[7]]);
95	// Diagonals.
96	quarter_round(v, 0, 5, 10, 15, &m[s[8]], &m[s[9]]);
97	quarter_round(v, 1, 6, 11, 12, &m[s[10]], &m[s[11]]);
98	quarter_round(v, 2, 7, 8, 13, &m[s[12]], &m[s[13]]);
99	quarter_round(v, 3, 4, 9, 14, &m[s[14]], &m[s[15]]);
100}
101
102/// Loads one 64-byte block per lane into 16 little-endian message words.
103///
104/// The words arrive one block per lane and are consumed one word per lane, so this is a transpose.
105/// Where a vector kernel covers the lane count it moves the square with shuffles instead of loads.
106#[inline(always)]
107fn load_block_words<const N: usize>(block: &[[u8; BLOCK_LEN]; N]) -> [[u32; N]; 16] {
108	#[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
109	if avx512::handles_lanes(N) {
110		return avx512::load_block_words(block);
111	}
112
113	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
114	if neon::transposes_lanes(N) {
115		return neon::load_block_words(block);
116	}
117
118	load_block_words_portable(block)
119}
120
121/// Loads one 64-byte block per lane into 16 little-endian message words, one word at a time.
122///
123/// Every target without a hand-written transpose runs this.
124///
125/// It is also the reference the vector kernels are tested against.
126#[inline(always)]
127fn load_block_words_portable<const N: usize>(block: &[[u8; BLOCK_LEN]; N]) -> [[u32; N]; 16] {
128	let mut m = [[0u32; N]; 16];
129	for lane in 0..N {
130		for (w, slot) in m.iter_mut().enumerate() {
131			let off = w * 4;
132			slot[lane] = u32::from_le_bytes([
133				block[lane][off],
134				block[lane][off + 1],
135				block[lane][off + 2],
136				block[lane][off + 3],
137			]);
138		}
139	}
140	m
141}
142
143/// Compresses one 64-byte block across all `N` lanes, updating the chaining value in place.
144///
145/// The counter, block length, and flags are shared by every lane, so they broadcast.
146/// Only the input chaining value and the message differ per lane.
147#[inline(always)]
148fn compress_block<const N: usize>(
149	cv: &mut [[u32; N]; 8],
150	block: &[[u32; N]; 16],
151	counter: u64,
152	block_len: u32,
153	flags: u32,
154) {
155	// On aarch64 the hand-written vector kernel holds the same state in registers.
156	// Lane counts it does not cover fall through to the lane loops.
157	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
158	if neon::handles_lanes(N) {
159		neon::compress_block(cv, block, counter, block_len, flags);
160		return;
161	}
162
163	compress_block_portable(cv, block, counter, block_len, flags);
164}
165
166/// Compresses one 64-byte block across all `N` lanes with plain lane loops.
167///
168/// Every target without a hand-written kernel runs this, and it is the reference the vector
169/// kernels are tested against.
170#[inline(always)]
171fn compress_block_portable<const N: usize>(
172	cv: &mut [[u32; N]; 8],
173	block: &[[u32; N]; 16],
174	counter: u64,
175	block_len: u32,
176	flags: u32,
177) {
178	// Split the 64-bit counter into its two 32-bit words.
179	let counter_lo = counter as u32;
180	let counter_hi = (counter >> 32) as u32;
181
182	// Initialize the 16-word state: CV, four IV words, counter, block length, flags.
183	let mut v: [[u32; N]; 16] = [
184		cv[0],
185		cv[1],
186		cv[2],
187		cv[3],
188		cv[4],
189		cv[5],
190		cv[6],
191		cv[7],
192		[IV[0]; N],
193		[IV[1]; N],
194		[IV[2]; N],
195		[IV[3]; N],
196		[counter_lo; N],
197		[counter_hi; N],
198		[block_len; N],
199		[flags; N],
200	];
201
202	// Run 7 rounds, each reading the message through its own schedule row.
203	// Nothing rewrites the message, so it stays exactly where the caller built it.
204	round::<0, N>(&mut v, block);
205	round::<1, N>(&mut v, block);
206	round::<2, N>(&mut v, block);
207	round::<3, N>(&mut v, block);
208	round::<4, N>(&mut v, block);
209	round::<5, N>(&mut v, block);
210	round::<6, N>(&mut v, block);
211
212	// Truncated output: h_i = v_i XOR v_{i+8}, feeding the next block or the final digest.
213	for i in 0..8 {
214		for lane in 0..N {
215			cv[i][lane] = v[i][lane] ^ v[i + 8][lane];
216		}
217	}
218}
219
220/// Broadcasts the eight IV words across `N` lanes to seed a fresh chaining value.
221#[inline(always)]
222fn broadcast_iv<const N: usize>() -> [[u32; N]; 8] {
223	array::from_fn(|w| [IV[w]; N])
224}
225
226/// Serializes one lane's eight-word chaining value into its 32-byte little-endian digest.
227#[inline(always)]
228fn serialize_cv_lane<const N: usize>(cv: &[[u32; N]; 8], lane: usize) -> [u8; OUT_LEN] {
229	let mut digest = [0u8; OUT_LEN];
230	let (chunks, _) = digest.as_chunks_mut::<4>();
231	for (w, chunk) in chunks.iter_mut().enumerate() {
232		chunk.copy_from_slice(&cv[w][lane].to_le_bytes());
233	}
234	digest
235}
236
237/// Portable multi-lane Blake3 leaf digest over `N` messages, hashed a block at a time.
238///
239/// One chunk, so the chaining value stays at counter 0 and needs no CV stack.
240/// Each message is any length up to `CHUNK_LEN`; all `N` lanes must share that length.
241///
242/// A block is compressed only once the next block's first byte arrives, so the trailing block
243/// is deferred to finalization, where it alone carries `CHUNK_END | ROOT`.
244#[derive(Clone)]
245pub struct PortableBlake3MultiDigest<const N: usize> {
246	/// Running chaining value per lane; seeded from the IV.
247	cv: [[u32; N]; 8],
248	/// The current block being filled, one 64-byte buffer per lane.
249	block: [[u8; BLOCK_LEN]; N],
250	/// Bytes buffered in `block` so far, shared across lanes (all lanes share one length).
251	block_len: usize,
252	/// How many blocks have already been compressed into `cv`.
253	blocks_compressed: usize,
254}
255
256impl<const N: usize> Default for PortableBlake3MultiDigest<N> {
257	fn default() -> Self {
258		// Fresh chaining value at the IV, empty block buffer, nothing compressed yet.
259		Self {
260			cv: broadcast_iv(),
261			block: [[0u8; BLOCK_LEN]; N],
262			block_len: 0,
263			blocks_compressed: 0,
264		}
265	}
266}
267
268impl<const N: usize> PortableBlake3MultiDigest<N> {
269	/// Compresses the buffered block as a full, non-final block, then empties the buffer.
270	fn compress_full_block(&mut self) {
271		// Only the very first block of the chunk carries CHUNK_START.
272		let flags = if self.blocks_compressed == 0 {
273			CHUNK_START
274		} else {
275			0
276		};
277		let m = load_block_words(&self.block);
278		compress_block(&mut self.cv, &m, 0, BLOCK_LEN as u32, flags);
279		self.blocks_compressed += 1;
280		self.block_len = 0;
281	}
282
283	/// Compresses the trailing block as the chunk root and writes each lane's digest.
284	///
285	/// Runs on a copy of the state, so the hasher itself is left untouched for reset.
286	fn write_root(&self, out: &mut [MaybeUninit<Output<blake3::Hasher>>; N]) {
287		let mut cv = self.cv;
288		let mut block = self.block;
289		// Zero-pad the trailing block's unused tail, so padding never changes the digest.
290		for lane in 0..N {
291			block[lane][self.block_len..].fill(0);
292		}
293		// A single-block message has its only block be both the first and the root block.
294		let start = if self.blocks_compressed == 0 {
295			CHUNK_START
296		} else {
297			0
298		};
299		let m = load_block_words(&block);
300		compress_block(&mut cv, &m, 0, self.block_len as u32, start | CHUNK_END | ROOT);
301
302		// Serialize each lane's eight-word chaining value into its 32-byte digest.
303		for lane in 0..N {
304			out[lane].write(serialize_cv_lane(&cv, lane).into());
305		}
306	}
307}
308
309impl<const N: usize> MultiDigest<N> for PortableBlake3MultiDigest<N> {
310	type Digest = blake3::Hasher;
311
312	fn new() -> Self {
313		Self::default()
314	}
315
316	fn update(&mut self, data: [&[u8]; N]) {
317		// Per-lane read cursor into this call's input.
318		let mut consumed = [0usize; N];
319		loop {
320			// Bytes still pending this call; all present lanes share one length, so the max drives.
321			let remaining = (0..N)
322				.map(|i| data[i].len() - consumed[i])
323				.max()
324				.unwrap_or(0);
325			if remaining == 0 {
326				break;
327			}
328			// A full buffer with more input to come is a non-final block: compress and empty it.
329			if self.block_len == BLOCK_LEN {
330				self.compress_full_block();
331			}
332			// Fill the block buffer up to one block from the pending input.
333			let take = (BLOCK_LEN - self.block_len).min(remaining);
334			for lane in 0..N {
335				let avail = data[lane].len() - consumed[lane];
336				let n = take.min(avail);
337				self.block[lane][self.block_len..self.block_len + n]
338					.copy_from_slice(&data[lane][consumed[lane]..consumed[lane] + n]);
339				consumed[lane] += n;
340			}
341			self.block_len += take;
342		}
343	}
344
345	fn finalize_into(self, out: &mut [MaybeUninit<Output<Self::Digest>>; N]) {
346		self.write_root(out);
347	}
348
349	fn finalize_into_reset(&mut self, out: &mut [MaybeUninit<Output<Self::Digest>>; N]) {
350		self.write_root(out);
351		self.reset();
352	}
353
354	fn reset(&mut self) {
355		// Reseed the chaining value and forget the block progress; buffer bytes are overwritten
356		// on the next update, and the trailing block's tail is zero-padded at finalization.
357		self.cv = broadcast_iv();
358		self.block_len = 0;
359		self.blocks_compressed = 0;
360	}
361
362	fn digest(data: [&[u8]; N], out: &mut [MaybeUninit<Output<Self::Digest>>; N]) {
363		let mut hasher = Self::new();
364		hasher.update(data);
365		hasher.finalize_into(out);
366	}
367}
368
369/// Parallel Blake3 leaf digest backed by the portable auto-vectorized kernel.
370///
371/// `LANES` is the batch width handed to the vectorizer.
372/// Leaf size decides the path:
373/// - Up to one 1024-byte chunk (any length): batched through the portable kernel.
374/// - Larger (multi-chunk): hashed on its own by the scalar adapter, which walks the tree.
375#[derive(Debug, Clone, Default)]
376pub struct PortableBlake3ParallelDigest<const LANES: usize>;
377
378impl<const LANES: usize> ParallelDigest for PortableBlake3ParallelDigest<LANES> {
379	type Digest = blake3::Hasher;
380
381	fn new() -> Self {
382		Self
383	}
384
385	fn digest<I: IntoIterator<Item: SerializeBytes>>(
386		&self,
387		source: impl IndexedParallelIterator<Item = I>,
388		out: &mut [MaybeUninit<Output<Self::Digest>>],
389	) {
390		// Without a fixed leaf length a leaf could exceed one chunk, which the kernel cannot hash.
391		// Fall back to the scalar adapter, which handles any length.
392		ParallelDigestAdapter::<blake3::Hasher>::new().digest(source, out);
393	}
394
395	fn digest_with_const_len<I: IntoIterator<Item: FixedSizeSerializeBytes>>(
396		&self,
397		n_items_per_input: usize,
398		source: impl IndexedParallelIterator<Item = I>,
399		out: &mut [MaybeUninit<Output<Self::Digest>>],
400	) {
401		// Every leaf serializes to the same fixed byte length.
402		let leaf_len = n_items_per_input * I::Item::BYTE_SIZE;
403
404		if leaf_len <= CHUNK_LEN {
405			// One chunk or less, any block structure: batch it through the vectorized kernel.
406			ParallelMultidigestImpl::<PortableBlake3MultiDigest<LANES>, LANES>::new()
407				.digest(source, out);
408		} else {
409			// Multi-chunk leaves need the tree; hand them to the scalar adapter.
410			ParallelDigestAdapter::<blake3::Hasher>::new().digest(source, out);
411		}
412	}
413}
414
415/// Folds up to `N` node pairs with a single batched Blake3 block compression.
416///
417/// Each pair is a 64-byte concatenation `left || right` of two 32-byte digests.
418/// That 64-byte message is exactly one Blake3 block.
419/// A one-block message makes its single block the first, last, and root block at once:
420/// - counter   = 0       (a single chunk).
421/// - block_len = 64      (a full block).
422/// - flags     = CHUNK_START | CHUNK_END | ROOT.
423///
424/// Folds `out.len()` pairs, which must be at most `N`.
425/// `inputs.len()` must be `2 * out.len()`.
426/// A partial batch leaves the unused high lanes zero.
427/// Their output is never read.
428#[inline]
429fn compress_node_pairs<const N: usize>(
430	inputs: &[Output<blake3::Hasher>],
431	out: &mut [MaybeUninit<Output<blake3::Hasher>>],
432) {
433	// Pack each pair into one 64-byte block: bytes 0..32 = left child, 32..64 = right child.
434	let mut blocks = [[0u8; BLOCK_LEN]; N];
435	for (lane, block) in blocks.iter_mut().enumerate().take(out.len()) {
436		block[..OUT_LEN].copy_from_slice(inputs[2 * lane].as_slice());
437		block[OUT_LEN..].copy_from_slice(inputs[2 * lane + 1].as_slice());
438	}
439
440	// One block compression seeded from the IV yields each pair's two-to-one digest.
441	let m = load_block_words(&blocks);
442	let mut cv = broadcast_iv::<N>();
443	compress_block(&mut cv, &m, 0, BLOCK_LEN as u32, CHUNK_START | CHUNK_END | ROOT);
444
445	for (lane, slot) in out.iter_mut().enumerate() {
446		slot.write(serialize_cv_lane(&cv, lane).into());
447	}
448}
449
450/// Parallel Blake3 two-to-one compression backed by the portable auto-vectorized kernel.
451///
452/// The Merkle inner-node counterpart to the leaf digest [`PortableBlake3ParallelDigest`].
453/// Every parent folds a pair of 32-byte child digests as `blake3(left || right)`.
454/// A batch of `LANES` node pairs is a fixed-length batched Blake3 over 64-byte messages.
455/// Each batch runs through the shared block-compression core in one pass.
456///
457/// Output is bit-identical to the scalar [`Blake3Compression`], pinned to it in tests.
458#[derive(Debug, Clone, Default)]
459pub struct PortableBlake3ParallelCompression<const LANES: usize> {
460	/// The scalar two-to-one function this batched path reproduces, exposed via `compression()`.
461	compression: Blake3Compression,
462}
463
464impl<const LANES: usize> ParallelPseudoCompression<Output<blake3::Hasher>, 2>
465	for PortableBlake3ParallelCompression<LANES>
466{
467	type Compression = Blake3Compression;
468
469	fn compression(&self) -> &Self::Compression {
470		&self.compression
471	}
472
473	fn parallel_compress(
474		&self,
475		inputs: &[Output<blake3::Hasher>],
476		out: &mut [MaybeUninit<Output<blake3::Hasher>>],
477	) {
478		assert_eq!(inputs.len(), 2 * out.len(), "Input length must be 2 * output length");
479
480		// Fold `LANES` pairs per batch.
481		// A shorter trailing batch is fine: the kernel only reads its valid lanes.
482		inputs
483			.par_chunks(2 * LANES)
484			.zip(out.par_chunks_mut(LANES))
485			.for_each(|(in_batch, out_batch)| compress_node_pairs::<LANES>(in_batch, out_batch));
486	}
487}
488
489#[cfg(test)]
490mod tests {
491	use std::iter::repeat_with;
492
493	use binius_hash::CompressionFunction;
494	use binius_utils::rayon::iter::{IntoParallelRefIterator, ParallelIterator};
495	use proptest::prelude::*;
496	use rand::{Rng, SeedableRng, rngs::StdRng};
497
498	use super::*;
499
500	/// Folds `pairs` through the `N`-lane portable compression.
501	/// Pins every output bit-identical to the scalar [`Blake3Compression`].
502	fn check_parallel_compression<const N: usize>(pairs: &[[[u8; OUT_LEN]; 2]]) {
503		// Flatten pairs to the `[left_0, right_0, left_1, ...]` layout the compressor reads.
504		let inputs: Vec<Output<blake3::Hasher>> = pairs
505			.iter()
506			.flat_map(|[l, r]| [(*l).into(), (*r).into()])
507			.collect();
508		let mut out = repeat_with(MaybeUninit::<Output<blake3::Hasher>>::uninit)
509			.take(pairs.len())
510			.collect::<Vec<_>>();
511
512		PortableBlake3ParallelCompression::<N>::default().parallel_compress(&inputs, &mut out);
513
514		// Invariant: each batched lane equals the scalar two-to-one of the same pair.
515		for (slot, [l, r]) in out.into_iter().zip(pairs) {
516			let expected = Blake3Compression.compress([(*l).into(), (*r).into()]);
517			assert_eq!(unsafe { slot.assume_init() }.as_slice(), expected.as_slice());
518		}
519	}
520
521	#[test]
522	fn test_parallel_compression_boundaries() {
523		// Extreme digests exercise all-zero and all-ones message blocks in every left/right slot.
524		let zero = [0u8; OUT_LEN];
525		let ones = [0xffu8; OUT_LEN];
526		check_parallel_compression::<16>(&[[zero, zero], [ones, ones], [zero, ones], [ones, zero]]);
527
528		// Counts straddling the 16-lane batch boundary: empty, single, full, full+1, multi+partial.
529		let mut rng = StdRng::seed_from_u64(7);
530		for count in [0usize, 1, 15, 16, 17, 33] {
531			let pairs: Vec<[[u8; OUT_LEN]; 2]> = (0..count)
532				.map(|_| {
533					let mut pair = [[0u8; OUT_LEN]; 2];
534					rng.fill_bytes(&mut pair[0]);
535					rng.fill_bytes(&mut pair[1]);
536					pair
537				})
538				.collect();
539			check_parallel_compression::<16>(&pairs);
540		}
541	}
542
543	proptest! {
544		#[test]
545		fn parallel_compression_matches_scalar(
546			pairs in prop::collection::vec(
547				(prop::array::uniform32(any::<u8>()), prop::array::uniform32(any::<u8>())),
548				0..40usize,
549			),
550		) {
551			// The batch path is bit-identical to the scalar reference, at every vectorizer width.
552			let pairs: Vec<[[u8; OUT_LEN]; 2]> = pairs.into_iter().map(|(l, r)| [l, r]).collect();
553			check_parallel_compression::<4>(&pairs);
554			check_parallel_compression::<8>(&pairs);
555			check_parallel_compression::<16>(&pairs);
556		}
557	}
558
559	/// Transposes one random block through both loaders and pins the vector words to the byte-wise
560	/// words.
561	///
562	/// # Arguments
563	///
564	/// * `rng` - source of the random block bytes.
565	#[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
566	fn check_avx512_transpose<const N: usize>(rng: &mut StdRng) {
567		use rand::RngExt;
568
569		// Every lane gets its own random bytes.
570		// Sharing bytes across lanes would hide a network that reads the wrong row.
571		let block: [[u8; BLOCK_LEN]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
572
573		// Reference: the byte-wise loader every target without a transpose runs.
574		let want = load_block_words_portable(&block);
575
576		// Candidate: the shuffle network, over the same bytes.
577		let got = super::avx512::load_block_words(&block);
578
579		// A transpose only permutes words, so the two must agree on all 16 words of all N lanes.
580		assert_eq!(got, want, "vector transpose diverged from the byte-wise loader at {N} lanes");
581	}
582
583	#[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
584	#[test]
585	fn test_avx512_transpose_matches_portable() {
586		let mut rng = StdRng::seed_from_u64(13);
587
588		// A misplaced row shows up only when the bytes differ, so repeat over fresh random blocks.
589		for _ in 0..64 {
590			check_avx512_transpose::<16>(&mut rng);
591		}
592	}
593
594	#[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
595	#[test]
596	fn test_avx512_transpose_places_every_word() {
597		// A counting block makes each word its own (lane, word) coordinate.
598		// Any swapped row or lane then shows up as a wrong coordinate, not just wrong bytes.
599		let block: [[u8; BLOCK_LEN]; 16] = array::from_fn(|lane| {
600			array::from_fn(|byte| {
601				let word = byte / 4;
602				// Word `w` of lane `l` is the value `l * 16 + w`, little-endian.
603				match byte % 4 {
604					0 => (lane * 16 + word) as u8,
605					_ => 0,
606				}
607			})
608		});
609
610		let m = super::avx512::load_block_words(&block);
611
612		// Word `w` of lane `l` must land at `m[w][l]`.
613		for lane in 0..16 {
614			for word in 0..16 {
615				assert_eq!(
616					m[word][lane],
617					(lane * 16 + word) as u32,
618					"word {word} of lane {lane} landed wrongly"
619				);
620			}
621		}
622	}
623
624	#[cfg(all(target_arch = "x86_64", target_feature = "avx512f"))]
625	proptest! {
626		#[test]
627		fn avx512_transpose_matches_portable_proptest(seed in any::<u64>()) {
628			// The fixed cases above pin the layout; this sweeps arbitrary bytes.
629			let mut rng = StdRng::seed_from_u64(seed);
630			check_avx512_transpose::<16>(&mut rng);
631		}
632	}
633
634	/// Compresses one block through both cores and pins the vector words to the lane-loop words.
635	///
636	/// # Arguments
637	///
638	/// * `rng` - source of the random chaining value and message.
639	/// * `counter` - chunk counter to place in the state.
640	/// * `block_len` - message byte count to place in the state.
641	/// * `flags` - domain-separation flags to place in the state.
642	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
643	fn check_neon_core<const N: usize>(rng: &mut StdRng, counter: u64, block_len: u32, flags: u32) {
644		use rand::RngExt;
645
646		// Every lane gets its own random words.
647		// Sharing a value across lanes would hide a kernel that reads the wrong vector.
648		let cv_in: [[u32; N]; 8] = array::from_fn(|_| array::from_fn(|_| rng.random()));
649		let block: [[u32; N]; 16] = array::from_fn(|_| array::from_fn(|_| rng.random()));
650
651		// Reference: the lane loops every target without a vector kernel runs.
652		let mut want = cv_in;
653		compress_block_portable(&mut want, &block, counter, block_len, flags);
654
655		// Candidate: the vector kernel, started from the same chaining value.
656		let mut got = cv_in;
657		super::neon::compress_block(&mut got, &block, counter, block_len, flags);
658
659		// Compression is bit-exact, so the two must agree on all 8 words of all N lanes.
660		assert_eq!(got, want, "vector kernel diverged from the lane loops at {N} lanes");
661	}
662
663	/// Transposes one random block set through both loaders and pins the words together.
664	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
665	fn check_neon_transpose<const N: usize>(rng: &mut StdRng) {
666		// Fresh random bytes per lane, so no two lanes hold the same word by accident.
667		let mut blocks = [[0u8; BLOCK_LEN]; N];
668		for block in blocks.iter_mut() {
669			rng.fill_bytes(block);
670		}
671
672		// A transpose only permutes words, so the two loaders must agree on all 16 rows.
673		assert_eq!(
674			super::neon::load_block_words(&blocks),
675			load_block_words_portable(&blocks),
676			"the shuffle network diverged from the byte-wise loader at {N} lanes"
677		);
678	}
679
680	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
681	#[test]
682	fn test_neon_transpose_matches_portable() {
683		// Invariant: a word's output row is its word index, and its output lane is its block index.
684		//
685		// Fixture: word `w` of lane `l` carries the value `l * 16 + w`, so all 16 * N are distinct.
686		//
687		//     lane 0 block:  [  0,  1,  2, ...,  15 ]
688		//     lane 1 block:  [ 16, 17, 18, ...,  31 ]
689		//     ...
690		//     output row w:  [  w, 16 + w, 32 + w, ... ]
691		//
692		// Distinct values are what makes a swapped row or lane show up as a wrong value.
693		let mut blocks = [[0u8; BLOCK_LEN]; 16];
694		for (lane, block) in blocks.iter_mut().enumerate() {
695			let (words, _) = block.as_chunks_mut::<4>();
696			for (w, word) in words.iter_mut().enumerate() {
697				word.copy_from_slice(&((lane * 16 + w) as u32).to_le_bytes());
698			}
699		}
700
701		// Every one of the 16 rows must read back its own coordinate, at every lane.
702		let m = super::neon::load_block_words(&blocks);
703		for (w, row) in m.iter().enumerate() {
704			for (lane, got) in row.iter().enumerate() {
705				assert_eq!(*got, (lane * 16 + w) as u32, "row {w}, lane {lane}");
706			}
707		}
708
709		// Random blocks at every width the network claims, from one square up to four.
710		let mut rng = StdRng::seed_from_u64(23);
711		check_neon_transpose::<4>(&mut rng);
712		check_neon_transpose::<8>(&mut rng);
713		check_neon_transpose::<12>(&mut rng);
714		check_neon_transpose::<16>(&mut rng);
715	}
716
717	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
718	proptest! {
719		#[test]
720		fn neon_transpose_matches_portable_proptest(seed in any::<u64>()) {
721			// The fixed block above pins the coordinates.
722			// This sweeps arbitrary bytes at every width instead.
723			let mut rng = StdRng::seed_from_u64(seed);
724			check_neon_transpose::<4>(&mut rng);
725			check_neon_transpose::<8>(&mut rng);
726			check_neon_transpose::<12>(&mut rng);
727			check_neon_transpose::<16>(&mut rng);
728		}
729	}
730
731	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
732	#[test]
733	fn test_neon_core_matches_portable() {
734		let mut rng = StdRng::seed_from_u64(11);
735
736		// The last four state words are the ones a kernel is most likely to place wrongly.
737		// So cover the combinations a real chunk produces, plus the extremes of each field.
738		//
739		//     (counter, block_len, flags)
740		let cases = [
741			// Interior block of a multi-block chunk: no flags, full 64 bytes.
742			(0u64, 64u32, 0u32),
743			// First block of a chunk.
744			(0, 64, CHUNK_START),
745			// Last block of a chunk, and the last of the whole tree.
746			(0, 64, CHUNK_END | ROOT),
747			// A chunk that is one block long, so it carries every flag at once.
748			(0, 64, CHUNK_START | CHUNK_END | ROOT),
749			// A one-byte message: the block is almost entirely zero padding.
750			(0, 1, CHUNK_START | CHUNK_END | ROOT),
751			// The empty message, the shortest input Blake3 accepts.
752			(0, 0, CHUNK_START | CHUNK_END | ROOT),
753			// Both counter halves set, which catches a kernel that drops the high half.
754			(u64::MAX, 64, CHUNK_END),
755			// A counter whose low half is zero, which catches the two halves being swapped.
756			(1 << 32, 63, CHUNK_START),
757		];
758
759		// Check every lane count the kernel claims, from one vector group up to four.
760		for (counter, block_len, flags) in cases {
761			check_neon_core::<4>(&mut rng, counter, block_len, flags);
762			check_neon_core::<8>(&mut rng, counter, block_len, flags);
763			check_neon_core::<12>(&mut rng, counter, block_len, flags);
764			check_neon_core::<16>(&mut rng, counter, block_len, flags);
765		}
766	}
767
768	#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
769	proptest! {
770		#[test]
771		fn neon_core_matches_portable_proptest(
772			seed in any::<u64>(),
773			counter in any::<u64>(),
774			// A block never carries more than the 64 bytes it holds.
775			block_len in 0..=64u32,
776			// Blake3 defines flags in the low byte only.
777			flags in any::<u8>(),
778		) {
779			// The fixed cases above pin the boundaries; this sweeps arbitrary state at every width.
780			let mut rng = StdRng::seed_from_u64(seed);
781			check_neon_core::<4>(&mut rng, counter, block_len, flags as u32);
782			check_neon_core::<8>(&mut rng, counter, block_len, flags as u32);
783			check_neon_core::<12>(&mut rng, counter, block_len, flags as u32);
784			check_neon_core::<16>(&mut rng, counter, block_len, flags as u32);
785		}
786	}
787
788	/// Runs `N` equal-length messages of `len` bytes through the portable batch and pins each lane
789	/// to the scalar reference.
790	fn check_portable_batch<const N: usize>(rng: &mut StdRng, len: usize) {
791		// Fresh random bytes per lane, so lanes don't share a digest by accident.
792		let messages: [Vec<u8>; N] = array::from_fn(|_| {
793			let mut m = vec![0u8; len];
794			rng.fill_bytes(&mut m);
795			m
796		});
797		let refs: [&[u8]; N] = array::from_fn(|i| messages[i].as_slice());
798		let mut out = array::from_fn::<_, N, _>(|_| MaybeUninit::uninit());
799		PortableBlake3MultiDigest::<N>::digest(refs, &mut out);
800
801		// Each lane's output must equal the single-message reference hash of that lane.
802		for (o, message) in out.iter().zip(messages.iter()) {
803			let got = unsafe { o.assume_init_ref() };
804			assert_eq!(got.as_slice(), blake3::hash(message).as_bytes(), "len = {len}, N = {N}");
805		}
806	}
807
808	#[test]
809	fn test_portable_lengths_match_reference() {
810		let mut rng = StdRng::seed_from_u64(0);
811
812		// Invariant: the portable kernel reproduces blake3::hash for any single-chunk length.
813		// Lengths cover every block-structure case within one chunk:
814		// - 0             : the lone empty block.
815		// - 1, 31, 63     : a single sub-block, no full blocks.
816		// - 64, 128, 1024 : exact block multiples.
817		// - 65, 100, 1000 : leading full blocks plus a partial tail.
818		// Three lane widths per length: 4 (NEON), 8, and 16 (the throughput sweet spot).
819		for len in [0, 1, 31, 63, 64, 65, 100, 127, 128, 1000, 1024] {
820			check_portable_batch::<4>(&mut rng, len);
821			check_portable_batch::<8>(&mut rng, len);
822			check_portable_batch::<16>(&mut rng, len);
823		}
824	}
825
826	#[test]
827	fn test_portable_chained_update() {
828		let mut rng = StdRng::seed_from_u64(2);
829		// Four 200-byte messages: three full blocks plus a 8-byte partial tail.
830		let messages: [Vec<u8>; 4] = array::from_fn(|_| {
831			let mut m = vec![0u8; 200];
832			rng.fill_bytes(&mut m);
833			m
834		});
835
836		// Invariant: a message split across two updates hashes the same as one update of the whole.
837		// The 50/150 split lands mid-block, exercising the buffer-fill and deferred-compress paths.
838		let mut hasher = PortableBlake3MultiDigest::<4>::new();
839		hasher.update(array::from_fn(|i| &messages[i][..50]));
840		hasher.update(array::from_fn(|i| &messages[i][50..]));
841		let mut out = array::from_fn::<_, 4, _>(|_| MaybeUninit::uninit());
842		hasher.finalize_into(&mut out);
843
844		for (o, message) in out.iter().zip(messages.iter()) {
845			assert_eq!(unsafe { o.assume_init_ref() }.as_slice(), blake3::hash(message).as_bytes());
846		}
847	}
848
849	#[test]
850	fn test_portable_routing_matches_reference() {
851		let mut rng = StdRng::seed_from_u64(3);
852		// Build 50 leaves of `leaf_len` bytes each, fed as u8 items (BYTE_SIZE = 1).
853		let mut check = |leaf_len: usize| {
854			let leaves: Vec<Vec<u8>> = (0..50)
855				.map(|_| {
856					let mut m = vec![0u8; leaf_len];
857					rng.fill_bytes(&mut m);
858					m
859				})
860				.collect();
861			let digest = PortableBlake3ParallelDigest::<8>::new();
862			let mut results = repeat_with(MaybeUninit::<Output<blake3::Hasher>>::uninit)
863				.take(50)
864				.collect::<Vec<_>>();
865			digest.digest_with_const_len(
866				leaf_len,
867				leaves.par_iter().map(|leaf| leaf.iter().copied()),
868				&mut results,
869			);
870			for (result, leaf) in results.into_iter().zip(&leaves) {
871				let got = unsafe { result.assume_init() };
872				assert_eq!(got.as_slice(), blake3::hash(leaf).as_bytes(), "leaf_len {leaf_len}");
873			}
874		};
875
876		// Invariant: every leaf size reproduces the reference, on the batch or the adapter route.
877		// - 0, 1, 63      : sub-block             -> portable batch.
878		// - 65, 100, 1000 : partial trailing block -> portable batch.
879		// - 64, 1024      : whole blocks           -> portable batch.
880		// - 1025, 2048    : multi-chunk (> 1024)   -> scalar adapter.
881		for leaf_len in [0, 1, 63, 64, 65, 100, 1000, 1024, 1025, 2048] {
882			check(leaf_len);
883		}
884	}
885}