lib_q_hash/
parallelhash.rs

1//! ParallelHash implementation
2//!
3//! This module provides ParallelHash128 and ParallelHash256 implementations as specified in SP800-185.
4//! ParallelHash is designed for efficient hashing of very long strings using parallel processing.
5
6use alloc::vec;
7use alloc::vec::Vec;
8use core::fmt;
9
10use digest::block_api::{
11    AlgorithmName,
12    Block,
13    BlockSizeUser,
14    BufferKindUser,
15    Eager,
16    UpdateCore,
17};
18use digest::common::hazmat::{
19    DeserializeStateError,
20    SerializableState,
21    SerializedState,
22};
23use digest::consts::{
24    U16,
25    U32,
26    U136,
27    U168,
28    U400,
29};
30use digest::{
31    CollisionResistance,
32    ExtendableOutput,
33    HashMarker,
34    Reset,
35    Update,
36    XofReader,
37};
38#[cfg(feature = "parallelhash")]
39use rayon::prelude::*;
40
41use crate::cshake::{
42    CShake128,
43    CShake128Reader,
44    CShake256,
45    CShake256Reader,
46};
47use crate::shake::{
48    Shake128,
49    Shake256,
50};
51use crate::utils::{
52    MAX_SP800185_FIXED_OUTPUT_BYTES,
53    left_encode,
54    right_encode,
55};
56
57/// ParallelHash128 implementation
58#[derive(Clone)]
59pub struct ParallelHash128 {
60    inner: CShake128,
61    buf: Vec<u8>,
62    n: u64,
63    rate: usize,
64    blocksize: usize,
65}
66
67/// ParallelHash256 implementation
68#[derive(Clone)]
69pub struct ParallelHash256 {
70    inner: CShake256,
71    buf: Vec<u8>,
72    n: u64,
73    rate: usize,
74    blocksize: usize,
75}
76
77/// ParallelHash128 XOF reader
78#[derive(Clone)]
79pub struct ParallelHash128Reader {
80    inner: CShake128Reader,
81}
82
83/// ParallelHash256 XOF reader
84#[derive(Clone)]
85pub struct ParallelHash256Reader {
86    inner: CShake256Reader,
87}
88
89macro_rules! impl_parallelhash {
90    (
91        $name:ident, $inner_type:ident, $reader_name:ident, $inner_reader_type:ident, $shake_type:ident, $rate:ident, $rate_expr:expr, $alg_name:expr
92    ) => {
93        impl $name {
94            /// Creates a new ParallelHash instance with the given customization string and block size
95            pub fn new(custom: &[u8], blocksize: usize) -> Self {
96                let mut hasher = Self {
97                    inner: $inner_type::new_with_function_name(b"ParallelHash", custom),
98                    buf: Vec::new(),
99                    n: 0,
100                    rate: $rate_expr,
101                    blocksize,
102                };
103                hasher.init();
104                hasher
105            }
106
107            fn init(&mut self) {
108                let mut enc_buf = [0u8; 9];
109
110                // left_encode(B)
111                let encoded = left_encode(self.blocksize as u64, &mut enc_buf);
112                Update::update(&mut self.inner, encoded);
113            }
114
115            /// Hash a single block using SHAKE
116            fn hash_block(block: &[u8], rate: usize) -> Vec<u8> {
117                let mut shake = $shake_type::default();
118                Update::update(&mut shake, block);
119                let mut output = vec![0u8; rate / 8];
120                ExtendableOutput::finalize_xof_into(shake, &mut output);
121                output
122            }
123
124            /// Update with data
125            pub fn update(&mut self, data: &[u8]) {
126                let mut pos = 0;
127
128                // Handle any remaining data in buffer
129                if !self.buf.is_empty() {
130                    let len = self.blocksize - self.buf.len();
131                    if data.len() < len {
132                        self.buf.extend_from_slice(data);
133                        return;
134                    } else {
135                        self.buf.extend_from_slice(&data[..len]);
136                        let block_hash = Self::hash_block(&self.buf, self.rate);
137                        Update::update(&mut self.inner, &block_hash);
138                        self.buf.clear();
139                        self.n += 1;
140                        pos = len;
141                    }
142                }
143
144                // Process complete blocks
145                #[cfg(feature = "parallelhash")]
146                {
147                    let rate = self.rate;
148                    let blocksize = self.blocksize;
149
150                    // Process complete blocks in parallel
151                    let complete_blocks = (data.len() - pos) / blocksize;
152                    if complete_blocks > 0 {
153                        let block_data = &data[pos..pos + complete_blocks * blocksize];
154                        let hashes: Vec<Vec<u8>> = block_data
155                            .par_chunks(blocksize)
156                            .map(|chunk| Self::hash_block(chunk, rate))
157                            .collect();
158
159                        for hash in hashes {
160                            Update::update(&mut self.inner, &hash);
161                            self.n += 1;
162                        }
163                        pos += complete_blocks * blocksize;
164                    }
165
166                    // Store remaining data
167                    if pos < data.len() {
168                        self.buf.extend_from_slice(&data[pos..]);
169                    }
170                }
171
172                #[cfg(not(feature = "parallelhash"))]
173                {
174                    while pos + self.blocksize <= data.len() {
175                        let block_hash =
176                            Self::hash_block(&data[pos..pos + self.blocksize], self.rate);
177                        Update::update(&mut self.inner, &block_hash);
178                        self.n += 1;
179                        pos += self.blocksize;
180                    }
181
182                    // Store remaining data
183                    if pos < data.len() {
184                        self.buf.extend_from_slice(&data[pos..]);
185                    }
186                }
187            }
188
189            /// Finalize with specified output length.
190            ///
191            /// `output.len()` must not exceed [`MAX_SP800185_FIXED_OUTPUT_BYTES`]. For longer
192            /// output, use [`Self::xof`].
193            ///
194            /// Returns [`None`] if `output.len()` is greater than
195            /// [`MAX_SP800185_FIXED_OUTPUT_BYTES`].
196            pub fn finalize(mut self, output: &mut [u8]) -> Option<()> {
197                if output.len() > MAX_SP800185_FIXED_OUTPUT_BYTES {
198                    return None;
199                }
200                self.with_bitlength((output.len() * 8) as u64);
201                ExtendableOutput::finalize_xof_into(self.inner, output);
202                Some(())
203            }
204
205            /// Finalize with specified output length and return as [`Vec`].
206            ///
207            /// Returns [`None`] if `output_len` is greater than [`MAX_SP800185_FIXED_OUTPUT_BYTES`].
208            /// For longer output, use [`Self::xof`].
209            pub fn finalize_with_length(mut self, output_len: usize) -> Option<Vec<u8>> {
210                if output_len > MAX_SP800185_FIXED_OUTPUT_BYTES {
211                    return None;
212                }
213                let mut output = vec![0u8; output_len];
214                self.with_bitlength((output_len * 8) as u64);
215                ExtendableOutput::finalize_xof_into(self.inner, &mut output);
216                Some(output)
217            }
218
219            /// Returns an XOF reader for variable-length output.
220            ///
221            /// SP 800-185 encodes XOF mode with `right_encode(0)` (output bit length zero) before
222            /// squeezing.
223            ///
224            /// This consumes `self` and finalizes the sponge; you cannot call [`Self::update`]
225            /// afterward on this value.
226            pub fn xof(mut self) -> $reader_name {
227                self.with_bitlength(0);
228                $reader_name {
229                    inner: ExtendableOutput::finalize_xof(self.inner),
230                }
231            }
232
233            fn with_bitlength(&mut self, bitlength: u64) {
234                // Process any remaining data in buffer
235                if !self.buf.is_empty() {
236                    let block_hash = Self::hash_block(&self.buf, self.rate);
237                    Update::update(&mut self.inner, &block_hash);
238                    self.buf.clear();
239                    self.n += 1;
240                }
241
242                let mut enc_buf = [0u8; 9];
243
244                // right_encode(n)
245                let encoded = right_encode(self.n, &mut enc_buf);
246                Update::update(&mut self.inner, encoded);
247
248                // right_encode(L)
249                let length_encoded = right_encode(bitlength, &mut enc_buf);
250                Update::update(&mut self.inner, length_encoded);
251            }
252        }
253
254        // Digest trait implementations
255        impl BlockSizeUser for $name {
256            type BlockSize = $rate;
257        }
258
259        impl BufferKindUser for $name {
260            type BufferKind = Eager;
261        }
262
263        impl HashMarker for $name {}
264
265        impl Update for $name {
266            #[inline]
267            fn update(&mut self, data: &[u8]) {
268                // Delegate to the public update method
269                let mut pos = 0;
270
271                // Handle any remaining data in buffer
272                if !self.buf.is_empty() {
273                    let len = self.blocksize - self.buf.len();
274                    if data.len() < len {
275                        self.buf.extend_from_slice(data);
276                        return;
277                    } else {
278                        self.buf.extend_from_slice(&data[..len]);
279                        let block_hash = Self::hash_block(&self.buf, self.rate);
280                        Update::update(&mut self.inner, &block_hash);
281                        self.buf.clear();
282                        self.n += 1;
283                        pos = len;
284                    }
285                }
286
287                // Process complete blocks
288                #[cfg(feature = "parallelhash")]
289                {
290                    let rate = self.rate;
291                    let blocksize = self.blocksize;
292
293                    // Process complete blocks in parallel
294                    let complete_blocks = (data.len() - pos) / blocksize;
295                    if complete_blocks > 0 {
296                        let block_data = &data[pos..pos + complete_blocks * blocksize];
297                        let hashes: Vec<Vec<u8>> = block_data
298                            .par_chunks(blocksize)
299                            .map(|chunk| Self::hash_block(chunk, rate))
300                            .collect();
301
302                        for hash in hashes {
303                            Update::update(&mut self.inner, &hash);
304                            self.n += 1;
305                        }
306                        pos += complete_blocks * blocksize;
307                    }
308
309                    // Store remaining data
310                    if pos < data.len() {
311                        self.buf.extend_from_slice(&data[pos..]);
312                    }
313                }
314
315                #[cfg(not(feature = "parallelhash"))]
316                {
317                    while pos + self.blocksize <= data.len() {
318                        let block_hash =
319                            Self::hash_block(&data[pos..pos + self.blocksize], self.rate);
320                        Update::update(&mut self.inner, &block_hash);
321                        self.n += 1;
322                        pos += self.blocksize;
323                    }
324
325                    // Store remaining data
326                    if pos < data.len() {
327                        self.buf.extend_from_slice(&data[pos..]);
328                    }
329                }
330            }
331        }
332
333        impl UpdateCore for $name {
334            #[inline]
335            fn update_blocks(&mut self, blocks: &[Block<Self>]) {
336                for block in blocks {
337                    self.update(block);
338                }
339            }
340        }
341
342        impl Reset for $name {
343            #[inline]
344            fn reset(&mut self) {
345                self.inner.reset();
346                self.buf.clear();
347                self.n = 0;
348                self.init();
349            }
350        }
351
352        impl AlgorithmName for $name {
353            fn write_alg_name(f: &mut fmt::Formatter<'_>) -> fmt::Result {
354                f.write_str($alg_name)
355            }
356        }
357
358        impl fmt::Debug for $name {
359            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
360                f.write_str(concat!(stringify!($name), " { ... }"))
361            }
362        }
363
364        #[cfg(feature = "zeroize")]
365        impl digest::zeroize::ZeroizeOnDrop for $name {}
366
367        // Implement Default trait
368        impl Default for $name {
369            fn default() -> Self {
370                Self::new(b"", 8192)
371            }
372        }
373
374        // Implement XofReader for the reader type
375        impl XofReader for $reader_name {
376            fn read(&mut self, buf: &mut [u8]) {
377                self.inner.read(buf);
378            }
379        }
380
381        impl fmt::Debug for $reader_name {
382            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
383                f.write_str(concat!(stringify!($reader_name), " { ... }"))
384            }
385        }
386    };
387}
388
389impl_parallelhash!(
390    ParallelHash128,
391    CShake128,
392    ParallelHash128Reader,
393    CShake128Reader,
394    Shake128,
395    U168,
396    168,
397    "ParallelHash128"
398);
399impl_parallelhash!(
400    ParallelHash256,
401    CShake256,
402    ParallelHash256Reader,
403    CShake256Reader,
404    Shake256,
405    U136,
406    136,
407    "ParallelHash256"
408);
409
410impl CollisionResistance for ParallelHash128 {
411    type CollisionResistance = U16;
412}
413
414impl CollisionResistance for ParallelHash256 {
415    type CollisionResistance = U32;
416}
417
418// Add SerializableState for ParallelHash types
419impl SerializableState for ParallelHash128 {
420    type SerializedStateSize = U400;
421
422    fn serialize(&self) -> SerializedState<Self> {
423        self.inner.serialize()
424    }
425
426    fn deserialize(
427        serialized_state: &SerializedState<Self>,
428    ) -> Result<Self, DeserializeStateError> {
429        let inner = CShake128::deserialize(serialized_state)?;
430        Ok(Self {
431            inner,
432            buf: Vec::new(),
433            n: 0,
434            rate: 168,
435            blocksize: 8192,
436        })
437    }
438}
439
440impl SerializableState for ParallelHash256 {
441    type SerializedStateSize = U400;
442
443    fn serialize(&self) -> SerializedState<Self> {
444        self.inner.serialize()
445    }
446
447    fn deserialize(
448        serialized_state: &SerializedState<Self>,
449    ) -> Result<Self, DeserializeStateError> {
450        let inner = CShake256::deserialize(serialized_state)?;
451        Ok(Self {
452            inner,
453            buf: Vec::new(),
454            n: 0,
455            rate: 136,
456            blocksize: 8192,
457        })
458    }
459}
460
461// Note: Zeroization is handled by the existing ZeroizeOnDrop implementations
462// which are feature-gated and will zeroize the inner cSHAKE state
463
464#[cfg(test)]
465mod tests {
466    use super::*;
467
468    #[test]
469    fn test_parallelhash128_basic() {
470        let custom = b"custom";
471        let data = b"test_data";
472
473        let mut parallelhash = ParallelHash128::new(custom, 16);
474        parallelhash.update(data);
475
476        let mut output = [0u8; 32];
477        parallelhash.finalize(&mut output).unwrap();
478        assert_ne!(output, [0u8; 32]);
479    }
480
481    #[test]
482    fn test_parallelhash256_basic() {
483        let custom = b"custom";
484        let data = b"test_data";
485
486        let mut parallelhash = ParallelHash256::new(custom, 16);
487        parallelhash.update(data);
488
489        let mut output = [0u8; 64];
490        parallelhash.finalize(&mut output).unwrap();
491        assert_ne!(output, [0u8; 64]);
492    }
493
494    #[test]
495    fn test_parallelhash_xof() {
496        let custom = b"custom";
497        let data = b"test_data";
498
499        let mut parallelhash = ParallelHash128::new(custom, 16);
500        parallelhash.update(data);
501
502        let mut reader = parallelhash.xof();
503        let mut output = [0u8; 100];
504        reader.read(&mut output);
505        assert_ne!(output, [0u8; 100]);
506    }
507
508    #[test]
509    fn test_parallelhash_different_block_sizes() {
510        let custom = b"custom";
511        let data = b"test_data_that_is_long_enough";
512
513        let mut parallelhash1 = ParallelHash128::new(custom, 8);
514        parallelhash1.update(data);
515        let mut output1 = [0u8; 32];
516        parallelhash1.finalize(&mut output1).unwrap();
517
518        let mut parallelhash2 = ParallelHash128::new(custom, 16);
519        parallelhash2.update(data);
520        let mut output2 = [0u8; 32];
521        parallelhash2.finalize(&mut output2).unwrap();
522
523        // Different block sizes should produce different results
524        assert_ne!(output1, output2);
525    }
526
527    #[test]
528    fn test_parallelhash_different_customs() {
529        let data = b"test_data";
530
531        let mut parallelhash1 = ParallelHash128::new(b"custom1", 16);
532        parallelhash1.update(data);
533        let mut output1 = [0u8; 32];
534        parallelhash1.finalize(&mut output1).unwrap();
535
536        let mut parallelhash2 = ParallelHash128::new(b"custom2", 16);
537        parallelhash2.update(data);
538        let mut output2 = [0u8; 32];
539        parallelhash2.finalize(&mut output2).unwrap();
540
541        assert_ne!(output1, output2);
542    }
543
544    #[test]
545    #[cfg(feature = "parallelhash")]
546    fn test_parallelhash_performance_comparison() {
547        // Create a large dataset to demonstrate parallel processing
548        let large_data: Vec<u8> = (0..1024 * 1024).map(|i| (i % 256) as u8).collect();
549        let custom = b"performance_test";
550        let block_size = 8192;
551
552        // Test with parallel processing
553        let mut parallelhash = ParallelHash128::new(custom, block_size);
554        parallelhash.update(&large_data);
555        let mut output = [0u8; 64];
556        parallelhash.finalize(&mut output).unwrap();
557
558        // Verify we got a valid hash
559        assert_ne!(output, [0u8; 64]);
560
561        // This test demonstrates that parallel processing works
562        // The fact that it completes without errors shows parallel processing is functional
563    }
564
565    #[test]
566    fn test_parallelhash_reset() {
567        let custom = b"custom";
568        let data = b"test_data";
569
570        let mut parallelhash = ParallelHash128::new(custom, 16);
571        parallelhash.update(data);
572
573        // Reset and test again
574        parallelhash.reset();
575        parallelhash.update(data);
576
577        let mut output = [0u8; 32];
578        parallelhash.finalize(&mut output).unwrap();
579        assert_ne!(output, [0u8; 32]);
580    }
581
582    #[test]
583    fn test_parallelhash_default() {
584        let parallelhash = ParallelHash128::default();
585        let data = b"test_data";
586
587        let mut hasher = parallelhash;
588        hasher.update(data);
589        let result = hasher.finalize_with_length(32).unwrap();
590        assert_eq!(result.len(), 32);
591    }
592
593    #[test]
594    fn test_parallelhash_serialization() {
595        let custom = b"custom";
596        let data = b"test_data";
597
598        let mut parallelhash = ParallelHash128::new(custom, 16);
599        parallelhash.update(data);
600
601        // Serialize the state
602        let serialized = parallelhash.serialize();
603
604        // Deserialize and continue
605        let mut parallelhash2 = ParallelHash128::deserialize(&serialized).unwrap();
606        parallelhash2.update(b"more_data");
607
608        let mut output = [0u8; 32];
609        parallelhash2.finalize(&mut output).unwrap();
610        assert_ne!(output, [0u8; 32]);
611    }
612
613    #[test]
614    fn test_parallelhash_finalize_with_length_rejects_over_cap() {
615        let mut h = ParallelHash128::new(b"", 16);
616        h.update(b"x");
617        assert!(
618            h.finalize_with_length(MAX_SP800185_FIXED_OUTPUT_BYTES + 1)
619                .is_none()
620        );
621    }
622
623    #[test]
624    fn test_parallelhash_finalize_rejects_over_cap_buffer() {
625        let mut h = ParallelHash128::new(b"", 16);
626        h.update(b"x");
627        let mut out = vec![0u8; MAX_SP800185_FIXED_OUTPUT_BYTES + 1];
628        assert!(h.finalize(&mut out).is_none());
629    }
630}
lib_q_hash/parallelhash.rs

lib_q_hash/
parallelhash.rs
