1use std::mem::MaybeUninit;
26
27use binius_hash::{Sha256Compression, Sha256HashSuite};
28use binius_utils::{
29 FixedSizeSerializeBytes, SerializeBytes,
30 rayon::{
31 iter::{IndexedParallelIterator, ParallelIterator},
32 slice::{ParallelSlice, ParallelSliceMut},
33 task_size::{WorkPerItem, min_len_for_work},
34 },
35};
36use bytemuck::must_cast;
37use portable::LANES;
38use sha2::{Sha256, digest::Output};
39
40use crate::{
41 parallel_compression::ParallelPseudoCompression,
42 parallel_digest::{ParallelDigest, ParallelDigestAdapter},
43 suite::ParallelHashSuite,
44};
45
46pub mod portable;
47
48#[cfg(all(
50 target_arch = "x86_64",
51 target_feature = "sha",
52 target_feature = "sse2",
53 target_feature = "ssse3",
54 target_feature = "sse4.1"
55))]
56mod sha_ni;
57
58#[cfg(all(
63 target_arch = "x86_64",
64 target_feature = "avx512f",
65 target_feature = "avx512bw"
66))]
67mod avx512;
68
69#[cfg(all(target_arch = "aarch64", target_feature = "sha2"))]
71mod neon;
72
73const BLOCK_LEN: usize = 64;
75
76const DIGEST_LEN: usize = 32;
78
79const IV: [u32; 8] = [
84 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
85];
86
87const K: [u32; 64] = [
91 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
92 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
93 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
94 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
95 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
96 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
97 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
98 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
99];
100
101const SINGLE_BLOCK_MAX_LEN: usize = BLOCK_LEN - 1 - 8;
109
110#[inline]
116fn min_batches_per_task(batch: usize) -> usize {
117 min_len_for_work(WorkPerItem::HashCompression).div_ceil(batch)
118}
119
120#[inline]
124fn be_digest(state: &[u32; 8]) -> Output<Sha256> {
125 let mut digest = Output::<Sha256>::default();
126 let (chunks, _) = digest.as_chunks_mut::<4>();
127 for (chunk, word) in chunks.iter_mut().zip(state) {
128 chunk.copy_from_slice(&word.to_be_bytes());
129 }
130 digest
131}
132
133impl ParallelHashSuite for Sha256HashSuite {
135 type ParLeafHash = ParallelSha256Digest;
136 type ParCompression = ParallelSha256Compression;
137}
138
139#[inline]
146fn compress_node_pairs<const N: usize>(
147 initial_state: &[u32; 8],
148 inputs: &[Output<Sha256>],
149 out: &mut [MaybeUninit<Output<Sha256>>],
150) {
151 let mut blocks = [[0u8; BLOCK_LEN]; N];
153 let (pairs, _) = inputs.as_chunks::<2>();
154 for (block, pair) in blocks.iter_mut().zip(pairs) {
155 block[..DIGEST_LEN].copy_from_slice(&pair[0]);
156 block[DIGEST_LEN..].copy_from_slice(&pair[1]);
157 }
158
159 let mut states = [*initial_state; N];
161 portable::compress256_multi(&mut states, &blocks);
162
163 for (slot, state) in out.iter_mut().zip(states) {
164 slot.write(must_cast::<[u32; 8], [u8; DIGEST_LEN]>(state).into());
165 }
166}
167
168#[derive(Debug, Clone, Default)]
173pub struct ParallelSha256Compression {
174 compression: Sha256Compression,
176}
177
178impl ParallelPseudoCompression<Output<Sha256>, 2> for ParallelSha256Compression {
179 type Compression = Sha256Compression;
180
181 fn compression(&self) -> &Self::Compression {
182 &self.compression
183 }
184
185 fn parallel_compress(
186 &self,
187 inputs: &[Output<Sha256>],
188 out: &mut [MaybeUninit<Output<Sha256>>],
189 ) {
190 assert_eq!(inputs.len(), 2 * out.len(), "Input length must be N * output length");
191
192 inputs
195 .par_chunks(2 * LANES)
196 .zip(out.par_chunks_mut(LANES))
197 .with_min_len(min_batches_per_task(LANES))
198 .for_each(|(pairs, out_batch)| {
199 compress_node_pairs::<LANES>(self.compression.initial_state(), pairs, out_batch);
200 });
201 }
202}
203
204fn digest_single_block_leaves<const N: usize, I>(
216 leaf_len: usize,
217 source: impl IndexedParallelIterator<Item = I>,
218 out: &mut [MaybeUninit<Output<Sha256>>],
219) where
220 I: IntoIterator<Item: SerializeBytes>,
221{
222 debug_assert!(leaf_len <= SINGLE_BLOCK_MAX_LEN, "pre-condition: the leaf fits in one block");
223
224 let mut template = [0u8; BLOCK_LEN];
226 template[leaf_len] = 0x80;
227 template[BLOCK_LEN - 8..].copy_from_slice(&((leaf_len as u64) * 8).to_be_bytes());
228
229 source
230 .chunks(N)
231 .zip(out.par_chunks_mut(N))
232 .with_min_len(min_batches_per_task(N))
233 .for_each_with([template; N], |blocks, (leaves, out_batch)| {
234 for (block, items) in blocks.iter_mut().zip(leaves) {
237 let mut cursor = &mut block[..leaf_len];
238 for item in items {
239 item.serialize(&mut cursor)
240 .expect("pre-condition: items must serialize without error");
241 }
242 debug_assert!(cursor.is_empty(), "pre-condition: each leaf serializes to leaf_len");
243 }
244
245 let mut states = [IV; N];
248 portable::compress256_multi(&mut states, blocks);
249 for (slot, state) in out_batch.iter_mut().zip(states) {
250 slot.write(be_digest(&state));
251 }
252 });
253}
254
255fn digest_multi_block_leaves<const N: usize, I>(
263 leaf_len: usize,
264 source: impl IndexedParallelIterator<Item = I>,
265 out: &mut [MaybeUninit<Output<Sha256>>],
266) where
267 I: IntoIterator<Item: SerializeBytes>,
268{
269 use bytes::BytesMut;
270
271 source
272 .chunks(N)
273 .zip(out.par_chunks_mut(N))
274 .with_min_len(min_batches_per_task(N))
275 .for_each_with(
276 std::array::from_fn::<_, N, _>(|_| BytesMut::new()),
277 |bufs, (leaves, out_batch)| {
278 let n_leaves = leaves.len();
279 for (buf, items) in bufs.iter_mut().zip(leaves) {
280 buf.clear();
282 for item in items {
283 item.serialize(&mut *buf)
284 .expect("pre-condition: items must serialize without error");
285 }
286 assert_eq!(
287 buf.len(),
288 leaf_len,
289 "pre-condition: each leaf serializes to leaf_len"
290 );
291 }
292
293 for buf in &mut bufs[n_leaves..] {
296 buf.resize(leaf_len, 0);
297 }
298
299 let inputs: [&[u8]; N] = std::array::from_fn(|i| bufs[i].as_ref());
300 for (slot, digest) in out_batch.iter_mut().zip(portable::sha256_multi(inputs)) {
301 slot.write(digest.into());
302 }
303 },
304 );
305}
306
307#[derive(Debug, Clone, Default)]
319pub struct ParallelSha256Digest;
320
321impl ParallelDigest for ParallelSha256Digest {
322 type Digest = Sha256;
323
324 fn new() -> Self {
325 Self
326 }
327
328 fn digest<I: IntoIterator<Item: SerializeBytes>>(
329 &self,
330 source: impl IndexedParallelIterator<Item = I>,
331 out: &mut [MaybeUninit<Output<Sha256>>],
332 ) {
333 ParallelDigestAdapter::<Sha256>::new().digest(source, out);
334 }
335
336 fn digest_with_const_len<I: IntoIterator<Item: FixedSizeSerializeBytes>>(
337 &self,
338 n_items_per_input: usize,
339 source: impl IndexedParallelIterator<Item = I>,
340 out: &mut [MaybeUninit<Output<Sha256>>],
341 ) {
342 let leaf_len = n_items_per_input * <I::Item as FixedSizeSerializeBytes>::BYTE_SIZE;
344
345 if leaf_len <= SINGLE_BLOCK_MAX_LEN {
346 digest_single_block_leaves::<LANES, I>(leaf_len, source, out);
347 } else {
348 digest_multi_block_leaves::<LANES, I>(leaf_len, source, out);
349 }
350 }
351}
352
353#[cfg(test)]
354mod tests {
355 use std::iter::repeat_with;
356
357 use binius_utils::rayon::iter::{IntoParallelRefIterator, ParallelIterator};
358 use digest::Digest;
359 use rand::{Rng, RngExt, SeedableRng, rngs::StdRng};
360
361 use super::*;
362 use crate::parallel_compression::ParallelCompressionAdaptor;
363
364 #[test]
365 fn test_batch_floor_counts_compressions_not_batches() {
366 let per_compression = min_len_for_work(WorkPerItem::HashCompression);
371 assert_eq!(min_batches_per_task(1), per_compression);
372
373 for batch in [2usize, 4, 8, 16] {
374 let batches = min_batches_per_task(batch);
375 assert!(batches * batch >= per_compression, "batch {batch} undershoots the floor");
377 assert!(
378 (batches - 1) * batch < per_compression,
379 "batch {batch} overshoots by a whole batch"
380 );
381 }
382 }
383
384 #[test]
385 fn test_parallel_compression_matches_adaptor() {
386 let mut rng = StdRng::seed_from_u64(0);
387
388 for n_nodes in [1usize, 2, 3, 4, 5, 8, 9, 16, 17, 64, 1000] {
397 let inputs: Vec<Output<Sha256>> = repeat_with(|| {
399 let mut digest = Output::<Sha256>::default();
400 rng.fill_bytes(&mut digest);
401 digest
402 })
403 .take(2 * n_nodes)
404 .collect();
405
406 let mut got = repeat_with(MaybeUninit::<Output<Sha256>>::uninit)
408 .take(n_nodes)
409 .collect::<Vec<_>>();
410 ParallelSha256Compression::default().parallel_compress(&inputs, &mut got);
411
412 let mut want = repeat_with(MaybeUninit::<Output<Sha256>>::uninit)
414 .take(n_nodes)
415 .collect::<Vec<_>>();
416 ParallelCompressionAdaptor::new(Sha256Compression::default())
417 .parallel_compress(&inputs, &mut want);
418
419 for (i, (got_i, want_i)) in got.iter().zip(&want).enumerate() {
420 let (got_i, want_i) =
422 unsafe { (got_i.assume_init_ref(), want_i.assume_init_ref()) };
423 assert_eq!(got_i, want_i, "mismatch at node {i} of {n_nodes}");
424 }
425 }
426 }
427
428 fn check_const_len_leaves(rng: &mut StdRng, n_items: usize, n_leaves: usize) {
430 let leaves: Vec<Vec<u128>> = (0..n_leaves)
432 .map(|_| (0..n_items).map(|_| rng.random()).collect())
433 .collect();
434
435 let mut got = repeat_with(MaybeUninit::<Output<Sha256>>::uninit)
436 .take(n_leaves)
437 .collect::<Vec<_>>();
438 ParallelSha256Digest::new().digest_with_const_len(
439 n_items,
440 leaves.par_iter().map(|leaf| leaf.iter().copied()),
441 &mut got,
442 );
443
444 for (i, (slot, leaf)) in got.into_iter().zip(&leaves).enumerate() {
445 let mut bytes = Vec::new();
446 for &item in leaf {
447 bytes.extend_from_slice(&item.to_le_bytes());
448 }
449 let got_i = unsafe { slot.assume_init() };
451 assert_eq!(
452 got_i,
453 <Sha256 as Digest>::digest(&bytes),
454 "leaf {i} of {n_leaves}, {n_items} items"
455 );
456 }
457 }
458
459 #[test]
460 fn test_const_len_leaves_match_serial() {
461 let mut rng = StdRng::seed_from_u64(0);
462
463 for n_items in [1, 2, 3, 4, 8] {
471 for n_leaves in [1, 4, 7, 8, 9, 16, 17, 48, 50] {
472 check_const_len_leaves(&mut rng, n_items, n_leaves);
473 }
474 }
475 }
476
477 #[test]
478 fn test_variable_len_leaves_match_serial() {
479 let mut rng = StdRng::seed_from_u64(1);
480 let n_leaves = 50;
484 let leaves: Vec<Vec<u128>> = (0..n_leaves)
485 .map(|_| (0..4).map(|_| rng.random()).collect())
486 .collect();
487
488 let mut got = repeat_with(MaybeUninit::<Output<Sha256>>::uninit)
489 .take(n_leaves)
490 .collect::<Vec<_>>();
491 ParallelSha256Digest::new()
492 .digest(leaves.par_iter().map(|leaf| leaf.iter().copied()), &mut got);
493
494 for (slot, leaf) in got.into_iter().zip(&leaves) {
495 let mut bytes = Vec::new();
496 for &item in leaf {
497 bytes.extend_from_slice(&item.to_le_bytes());
498 }
499 assert_eq!(unsafe { slot.assume_init() }, <Sha256 as Digest>::digest(&bytes));
501 }
502 }
503}