binius_hash_prover/sha256/
portable.rs1use std::array;
19
20#[cfg(all(
21 target_arch = "x86_64",
22 target_feature = "avx512f",
23 target_feature = "avx512bw"
24))]
25use super::avx512;
26#[cfg(all(target_arch = "aarch64", target_feature = "sha2"))]
27use super::neon;
28#[cfg(all(
29 target_arch = "x86_64",
30 target_feature = "sha",
31 target_feature = "sse2",
32 target_feature = "ssse3",
33 target_feature = "sse4.1"
34))]
35use super::sha_ni;
36use super::{BLOCK_LEN, DIGEST_LEN, IV, K, SINGLE_BLOCK_MAX_LEN};
37
38pub const LANES: usize =
51 if cfg!(all(target_arch = "x86_64", target_feature = "avx512f", target_feature = "avx512bw")) {
52 16
54 } else if cfg!(all(target_arch = "x86_64", target_feature = "sha")) {
55 8
56 } else if cfg!(all(target_arch = "aarch64", target_feature = "sha2")) {
57 4
58 } else {
59 8
61 };
62
63#[inline(always)]
76fn round<const N: usize>(state: [[u32; N]; 8], w: &[u32; N], k: u32) -> [[u32; N]; 8] {
77 let [a, b, c, d, e, f, g, h] = state;
78 let mut next_a = [0u32; N];
79 let mut next_e = [0u32; N];
80
81 for i in 0..N {
84 let sigma1 = e[i].rotate_right(6) ^ e[i].rotate_right(11) ^ e[i].rotate_right(25);
86 let ch = (e[i] & f[i]) ^ (!e[i] & g[i]);
88 let t1 = h[i]
89 .wrapping_add(sigma1)
90 .wrapping_add(ch)
91 .wrapping_add(k)
92 .wrapping_add(w[i]);
93 let sigma0 = a[i].rotate_right(2) ^ a[i].rotate_right(13) ^ a[i].rotate_right(22);
95 let maj = (a[i] & b[i]) ^ (a[i] & c[i]) ^ (b[i] & c[i]);
97
98 next_e[i] = d[i].wrapping_add(t1);
99 next_a[i] = t1.wrapping_add(sigma0.wrapping_add(maj));
100 }
101
102 [next_a, a, b, c, next_e, e, f, g]
107}
108
109#[inline(always)]
130fn extend_window<const N: usize>(w: &mut [[u32; N]; 16]) {
131 for j in 0..16 {
132 let m15 = w[(j + 1) & 15];
134 let m7 = w[(j + 9) & 15];
135 let m2 = w[(j + 14) & 15];
136 for i in 0..N {
137 let sigma0 = m15[i].rotate_right(7) ^ m15[i].rotate_right(18) ^ (m15[i] >> 3);
138 let sigma1 = m2[i].rotate_right(17) ^ m2[i].rotate_right(19) ^ (m2[i] >> 10);
139 w[j][i] = w[j][i]
140 .wrapping_add(sigma0)
141 .wrapping_add(m7[i])
142 .wrapping_add(sigma1);
143 }
144 }
145}
146
147#[inline(always)]
152fn load_block_words<const N: usize>(blocks: &[[u8; BLOCK_LEN]; N]) -> [[u32; N]; 16] {
153 #[cfg(all(
154 target_arch = "x86_64",
155 target_feature = "avx512f",
156 target_feature = "avx512bw"
157 ))]
158 if avx512::handles_lanes(N) {
159 return avx512::load_block_words(blocks);
160 }
161
162 load_block_words_portable(blocks)
163}
164
165#[inline(always)]
170fn load_block_words_portable<const N: usize>(blocks: &[[u8; BLOCK_LEN]; N]) -> [[u32; N]; 16] {
171 let mut w = [[0u32; N]; 16];
172 for lane in 0..N {
173 for (t, slot) in w.iter_mut().enumerate() {
174 let off = t * 4;
175 slot[lane] = u32::from_be_bytes([
177 blocks[lane][off],
178 blocks[lane][off + 1],
179 blocks[lane][off + 2],
180 blocks[lane][off + 3],
181 ]);
182 }
183 }
184 w
185}
186
187#[inline]
194pub fn compress256_multi<const N: usize>(
195 states: &mut [[u32; 8]; N],
196 blocks: &[[u8; BLOCK_LEN]; N],
197) {
198 #[cfg(all(
200 target_arch = "x86_64",
201 target_feature = "avx512f",
202 target_feature = "avx512bw"
203 ))]
204 if avx512::handles_lanes(N) {
205 unsafe { avx512::compress256_multi(states, blocks) };
207 return;
208 }
209
210 #[cfg(all(
211 target_arch = "x86_64",
212 target_feature = "sha",
213 target_feature = "sse2",
214 target_feature = "ssse3",
215 target_feature = "sse4.1"
216 ))]
217 if sha_ni::handles_lanes(N) {
218 unsafe { sha_ni::compress256_multi(states, blocks) };
220 return;
221 }
222
223 #[cfg(all(target_arch = "aarch64", target_feature = "sha2"))]
224 if neon::handles_lanes(N) {
225 unsafe { neon::compress256_multi(states, blocks) };
227 return;
228 }
229
230 compress256_multi_portable(states, blocks);
231}
232
233#[inline]
238pub fn compress256_multi_portable<const N: usize>(
239 states: &mut [[u32; 8]; N],
240 blocks: &[[u8; BLOCK_LEN]; N],
241) {
242 let mut w = load_block_words(blocks);
243
244 let mut state: [[u32; N]; 8] = array::from_fn(|t| array::from_fn(|lane| states[lane][t]));
246 let incoming = state;
247
248 for group in 0..4 {
251 if group > 0 {
252 extend_window(&mut w);
253 }
254 for t in 16 * group..16 * group + 16 {
255 state = round(state, &w[t & 15], K[t]);
256 }
257 }
258
259 for (lane, out) in states.iter_mut().enumerate() {
261 for (t, word) in out.iter_mut().enumerate() {
262 *word = state[t][lane].wrapping_add(incoming[t][lane]);
263 }
264 }
265}
266
267pub fn sha256_multi<const N: usize>(inputs: [&[u8]; N]) -> [[u8; DIGEST_LEN]; N] {
275 let len = inputs[0].len();
276 assert!(inputs.iter().all(|input| input.len() == len), "the inputs must have equal length");
277
278 let mut states = [IV; N];
279 let mut blocks = [[0u8; BLOCK_LEN]; N];
280
281 for b in 0..len / BLOCK_LEN {
283 for (block, input) in blocks.iter_mut().zip(inputs) {
284 block.copy_from_slice(&input[b * BLOCK_LEN..(b + 1) * BLOCK_LEN]);
285 }
286 compress256_multi(&mut states, &blocks);
287 }
288
289 let rem = len % BLOCK_LEN;
293 let n_tail = if rem <= SINGLE_BLOCK_MAX_LEN { 1 } else { 2 };
294 let mut tails = [[0u8; 2 * BLOCK_LEN]; N];
295 for (tail, input) in tails.iter_mut().zip(inputs) {
296 tail[..rem].copy_from_slice(&input[len - rem..]);
297 tail[rem] = 0x80;
298 tail[n_tail * BLOCK_LEN - 8..n_tail * BLOCK_LEN]
299 .copy_from_slice(&((len as u64) * 8).to_be_bytes());
300 }
301 for b in 0..n_tail {
302 for (block, tail) in blocks.iter_mut().zip(&tails) {
303 block.copy_from_slice(&tail[b * BLOCK_LEN..(b + 1) * BLOCK_LEN]);
304 }
305 compress256_multi(&mut states, &blocks);
306 }
307
308 states.map(|state| {
310 let mut digest = [0u8; DIGEST_LEN];
311 let (chunks, _) = digest.as_chunks_mut::<4>();
312 for (chunk, word) in chunks.iter_mut().zip(state) {
313 chunk.copy_from_slice(&word.to_be_bytes());
314 }
315 digest
316 })
317}
318
319#[cfg(test)]
320mod tests {
321 use proptest::prelude::*;
322 use rand::{Rng, RngExt, SeedableRng, rngs::StdRng};
323 use sha2::{Digest, Sha256, block_api::compress256};
324
325 use super::*;
326
327 fn check_portable_against_sha2<const N: usize>(rng: &mut StdRng) {
330 let states: [[u32; 8]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
333 let blocks: [[u8; BLOCK_LEN]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
334
335 let mut got = states;
336 compress256_multi_portable(&mut got, &blocks);
337
338 for (lane, (got_lane, state)) in got.iter().zip(&states).enumerate() {
340 let mut want = *state;
341 compress256(&mut want, std::slice::from_ref(&blocks[lane]));
342 assert_eq!(*got_lane, want, "lane {lane} of {N} diverged from sha2");
343 }
344 }
345
346 #[test]
347 fn test_portable_matches_sha2() {
348 let mut rng = StdRng::seed_from_u64(0);
349 for _ in 0..16 {
352 check_portable_against_sha2::<1>(&mut rng);
353 check_portable_against_sha2::<4>(&mut rng);
354 check_portable_against_sha2::<8>(&mut rng);
355 check_portable_against_sha2::<16>(&mut rng);
356 }
357 }
358
359 #[test]
360 fn test_portable_matches_sha2_at_state_extremes() {
361 for state_word in [0u32, u32::MAX] {
363 for block_byte in [0u8, 0xff] {
364 let states = [[state_word; 8]; 4];
365 let blocks = [[block_byte; BLOCK_LEN]; 4];
366
367 let mut got = states;
368 compress256_multi_portable(&mut got, &blocks);
369
370 let mut want = states[0];
371 compress256(&mut want, &blocks[..1]);
372 for (lane, got_lane) in got.iter().enumerate() {
373 assert_eq!(*got_lane, want, "lane {lane}, state {state_word:#x}");
374 }
375 }
376 }
377 }
378
379 fn check_dispatch_against_portable<const N: usize>(rng: &mut StdRng) {
383 let states: [[u32; 8]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
384 let blocks: [[u8; BLOCK_LEN]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
385
386 let mut want = states;
387 compress256_multi_portable(&mut want, &blocks);
388
389 let mut got = states;
390 compress256_multi(&mut got, &blocks);
391
392 assert_eq!(got, want, "the dispatched kernel diverged from the lane loops at {N} lanes");
393 }
394
395 #[test]
396 fn test_dispatch_matches_portable() {
397 let mut rng = StdRng::seed_from_u64(1);
398 for _ in 0..16 {
400 check_dispatch_against_portable::<1>(&mut rng);
401 check_dispatch_against_portable::<2>(&mut rng);
402 check_dispatch_against_portable::<4>(&mut rng);
403 check_dispatch_against_portable::<8>(&mut rng);
404 check_dispatch_against_portable::<16>(&mut rng);
405 }
406 }
407
408 proptest! {
409 #[test]
410 fn dispatch_matches_portable_proptest(seed in any::<u64>()) {
411 let mut rng = StdRng::seed_from_u64(seed);
414 check_dispatch_against_portable::<LANES>(&mut rng);
415 check_dispatch_against_portable::<16>(&mut rng);
416 }
417 }
418
419 fn check_sha256_multi<const N: usize>(rng: &mut StdRng, len: usize) {
421 let messages: [Vec<u8>; N] = array::from_fn(|_| {
423 let mut m = vec![0u8; len];
424 rng.fill_bytes(&mut m);
425 m
426 });
427 let refs: [&[u8]; N] = array::from_fn(|i| messages[i].as_slice());
428
429 let got = sha256_multi(refs);
430 for (lane, (got_lane, message)) in got.iter().zip(&messages).enumerate() {
431 let want: [u8; DIGEST_LEN] = <Sha256 as Digest>::digest(message).into();
432 assert_eq!(*got_lane, want, "len {len}, lane {lane} of {N}");
433 }
434 }
435
436 #[test]
437 fn test_sha256_multi_matches_sha2_at_padding_boundaries() {
438 let mut rng = StdRng::seed_from_u64(2);
439 for len in [0, 1, 54, 55, 56, 63, 64, 65, 119, 120, 128, 256] {
447 check_sha256_multi::<1>(&mut rng, len);
448 check_sha256_multi::<4>(&mut rng, len);
449 check_sha256_multi::<LANES>(&mut rng, len);
450 }
451 }
452
453 proptest! {
454 #[test]
455 fn sha256_multi_matches_sha2_proptest(seed in any::<u64>(), len in 0..300usize) {
456 let mut rng = StdRng::seed_from_u64(seed);
457 check_sha256_multi::<LANES>(&mut rng, len);
458 }
459 }
460
461 #[test]
462 #[should_panic(expected = "the inputs must have equal length")]
463 fn test_sha256_multi_rejects_unequal_lengths() {
464 sha256_multi::<2>([&[0u8; 8], &[0u8; 9]]);
466 }
467
468 #[cfg(all(
470 target_arch = "x86_64",
471 target_feature = "avx512f",
472 target_feature = "avx512bw"
473 ))]
474 fn check_avx512_transpose<const N: usize>(rng: &mut StdRng) {
475 let blocks: [[u8; BLOCK_LEN]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
477
478 assert_eq!(
480 avx512::load_block_words(&blocks),
481 load_block_words_portable(&blocks),
482 "the shuffle network diverged from the byte-wise loader at {N} lanes"
483 );
484 }
485
486 #[cfg(all(
487 target_arch = "x86_64",
488 target_feature = "avx512f",
489 target_feature = "avx512bw"
490 ))]
491 #[test]
492 fn test_avx512_transpose_places_every_word() {
493 let mut blocks = [[0u8; BLOCK_LEN]; 16];
505 for (lane, block) in blocks.iter_mut().enumerate() {
506 let (words, _) = block.as_chunks_mut::<4>();
507 for (w, word) in words.iter_mut().enumerate() {
508 word.copy_from_slice(&((lane * 16 + w) as u32).to_be_bytes());
509 }
510 }
511
512 let m = avx512::load_block_words(&blocks);
513 for (w, row) in m.iter().enumerate() {
514 for (lane, got) in row.iter().enumerate() {
515 assert_eq!(*got, (lane * 16 + w) as u32, "row {w}, lane {lane}");
516 }
517 }
518
519 let mut rng = StdRng::seed_from_u64(3);
521 for _ in 0..64 {
522 check_avx512_transpose::<16>(&mut rng);
523 }
524 }
525
526 #[cfg(all(
528 target_arch = "x86_64",
529 target_feature = "avx512f",
530 target_feature = "avx512bw"
531 ))]
532 fn check_avx512_core(rng: &mut StdRng) {
533 let states: [[u32; 8]; 16] = array::from_fn(|_| array::from_fn(|_| rng.random()));
534 let blocks: [[u8; BLOCK_LEN]; 16] = array::from_fn(|_| array::from_fn(|_| rng.random()));
535
536 let mut want = states;
537 compress256_multi_portable(&mut want, &blocks);
538
539 let mut got = states;
540 unsafe { avx512::compress256_multi(&mut got, &blocks) };
542
543 assert_eq!(got, want, "the AVX-512 kernel diverged from the lane loops");
544 }
545
546 #[cfg(all(
547 target_arch = "x86_64",
548 target_feature = "avx512f",
549 target_feature = "avx512bw"
550 ))]
551 #[test]
552 fn test_avx512_core_matches_portable() {
553 let mut rng = StdRng::seed_from_u64(4);
556 for _ in 0..64 {
557 check_avx512_core(&mut rng);
558 }
559 }
560
561 #[cfg(all(
562 target_arch = "x86_64",
563 target_feature = "avx512f",
564 target_feature = "avx512bw"
565 ))]
566 proptest! {
567 #[test]
568 fn avx512_core_matches_portable_proptest(seed in any::<u64>()) {
569 let mut rng = StdRng::seed_from_u64(seed);
570 check_avx512_core(&mut rng);
571 check_avx512_transpose::<16>(&mut rng);
572 }
573 }
574
575 #[cfg(all(
577 target_arch = "x86_64",
578 target_feature = "sha",
579 target_feature = "sse2",
580 target_feature = "ssse3",
581 target_feature = "sse4.1"
582 ))]
583 fn check_sha_ni_core<const N: usize>(rng: &mut StdRng) {
584 let states: [[u32; 8]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
585 let blocks: [[u8; BLOCK_LEN]; N] = array::from_fn(|_| array::from_fn(|_| rng.random()));
586
587 let mut want = states;
588 compress256_multi_portable(&mut want, &blocks);
589
590 let mut got = states;
591 unsafe { sha_ni::compress256_multi(&mut got, &blocks) };
593
594 assert_eq!(got, want, "the SHA-extension kernel diverged from the lane loops at {N} lanes");
595 }
596
597 #[cfg(all(
598 target_arch = "x86_64",
599 target_feature = "sha",
600 target_feature = "sse2",
601 target_feature = "ssse3",
602 target_feature = "sse4.1"
603 ))]
604 #[test]
605 fn test_sha_ni_core_matches_portable() {
606 let mut rng = StdRng::seed_from_u64(5);
607 for _ in 0..32 {
609 check_sha_ni_core::<1>(&mut rng);
610 check_sha_ni_core::<2>(&mut rng);
611 check_sha_ni_core::<4>(&mut rng);
612 check_sha_ni_core::<8>(&mut rng);
613 check_sha_ni_core::<16>(&mut rng);
614 }
615 }
616
617 #[cfg(all(
618 target_arch = "x86_64",
619 target_feature = "sha",
620 target_feature = "sse2",
621 target_feature = "ssse3",
622 target_feature = "sse4.1"
623 ))]
624 proptest! {
625 #[test]
626 fn sha_ni_core_matches_portable_proptest(seed in any::<u64>()) {
627 let mut rng = StdRng::seed_from_u64(seed);
628 check_sha_ni_core::<8>(&mut rng);
629 }
630 }
631
632 #[cfg(all(target_arch = "aarch64", target_feature = "sha2"))]
634 fn check_neon_core(rng: &mut StdRng) {
635 let states: [[u32; 8]; 4] = array::from_fn(|_| array::from_fn(|_| rng.random()));
636 let blocks: [[u8; BLOCK_LEN]; 4] = array::from_fn(|_| array::from_fn(|_| rng.random()));
637
638 let mut want = states;
639 compress256_multi_portable(&mut want, &blocks);
640
641 let mut got = states;
642 unsafe { neon::compress256_multi(&mut got, &blocks) };
644
645 assert_eq!(got, want, "the crypto-extension kernel diverged from the lane loops");
646 }
647
648 #[cfg(all(target_arch = "aarch64", target_feature = "sha2"))]
649 #[test]
650 fn test_neon_core_matches_portable() {
651 let mut rng = StdRng::seed_from_u64(6);
652 for _ in 0..64 {
653 check_neon_core(&mut rng);
654 }
655 }
656
657 #[cfg(all(target_arch = "aarch64", target_feature = "sha2"))]
658 proptest! {
659 #[test]
660 fn neon_core_matches_portable_proptest(seed in any::<u64>()) {
661 let mut rng = StdRng::seed_from_u64(seed);
662 check_neon_core(&mut rng);
663 }
664 }
665}