blake3_servil/
each.rs

1//! [`hash_each_with`]: a collection of messages of any lengths, each hashed,
2//! with short messages' chunks side by side in the SIMD lanes.
3//!
4//! Chunk k of every message has chunk counter k, so the full chunks k of
5//! different messages hash in one call of the many-inputs kernel, at counter
6//! k for every lane. Messages of one chunk or less, and messages of 16 chunks
7//! or more (which fill the lanes alone), go through `hash_with`; a message's
8//! last partial chunk hashes on its own. Each message's chunk chaining values
9//! then merge into its root as BLAKE3's tree places them.
10
11use crate::platform::Platform;
12use crate::{CHUNK_END, CHUNK_LEN, CHUNK_START, CVBytes, CVWords, ChunkState, Hash, Hasher, IncrementCounter, Mode, OUT_LEN};
13
14/// [`hash_each_with`], using other CPU cores where that is faster: the
15/// same hashes, never slower. Collections of 512 KiB and more in all use
16/// them, as [`hash_multithreaded`](crate::hash_multithreaded) does.
17/// Requires `out.len() == items.len()`.
18///
19/// ```
20/// # blake3_servil::initialize_multithreaded(None);
21/// use blake3_servil::Mode;
22/// let items: Vec<Vec<u8>> = (0..100).map(|i| vec![i as u8; 1000 * i]).collect();
23/// let slices: Vec<&[u8]> = items.iter().map(|m| m.as_slice()).collect();
24/// let (mut a, mut b) = (vec![[0u8; 32]; 100], vec![[0u8; 32]; 100]);
25/// blake3_servil::hash_each_multithreaded_with(Mode::Hash, &slices, &mut a);
26/// blake3_servil::hash_each_with(Mode::Hash, &slices, &mut b);
27/// assert_eq!(a, b);
28/// ```
29#[cfg(feature = "std")]
30pub fn hash_each_multithreaded_with(mode: Mode, items: &[&[u8]], out: &mut [[u8; OUT_LEN]]) {
31    crate::lanes::require();
32    assert_eq!(items.len(), out.len(), "one digest per item");
33    let (key, flags) = mode.key_and_flags();
34    let alone = |item: &[u8]| item.len() >= crate::lanes::MIN_SPLIT_LEN;
35    // The collection with each item that hashes alone set aside (an empty
36    // stand-in, its digest written after).
37    let small: Vec<&[u8]> = items.iter().map(|&i| if alone(i) { &[][..] } else { i }).collect();
38    if small.iter().map(|i| i.len()).sum::<usize>() < crate::lanes::MIN_SPLIT_LEN {
39        hash_each_on(&key, flags, &small, out, Platform::detect(), |item| crate::hash_with(mode, item));
40    } else {
41        crate::lanes::hash_each(&key, flags, &small, out);
42    }
43    for (item, out) in items.iter().zip(out.iter_mut()) {
44        if alone(item) {
45            *out = *crate::lanes::hash_with_key(item, &key, flags).as_bytes();
46        }
47    }
48}
49
50/// Many messages arriving at once, such as a server's uploads, each with
51/// its own [`Hasher`]: one call takes the pieces that have arrived for all
52/// of them, which hash faster together than one [`update`](Hasher::update)
53/// each.
54impl Hasher {
55    /// Feed each piece to its hasher: `(i, bytes)` does
56    /// `hashers[i].update(bytes)`, each hasher's pieces in their order in
57    /// `pieces`. Call it once with all the pieces your program has in hand
58    /// (one turn of its event loop): never slower than one
59    /// [`update`](Hasher::update) each. Requires each `i < hashers.len()`.
60    ///
61    /// ```
62    /// # blake3_servil::initialize();
63    /// use blake3_servil::Hasher;
64    /// let mut hashers = vec![Hasher::new(), Hasher::new()];
65    /// Hasher::update_each(&mut hashers, &[(0, b"ab"), (1, b"xyz"), (0, b"c")]);
66    /// let mut out = [[0u8; 32]; 2];
67    /// Hasher::finalize_each(&hashers, &[0, 1], &mut out);
68    /// assert_eq!((&out[0], &out[1]), (blake3_servil::hash(b"abc").as_bytes(), blake3_servil::hash(b"xyz").as_bytes()));
69    /// ```
70    pub fn update_each(hashers: &mut [Hasher], pieces: &[(usize, &[u8])]) {
71        update_turn(hashers, pieces, false);
72    }
73
74    /// [`update_each`](Hasher::update_each), using other CPU cores where
75    /// that is faster (pieces of 512 KiB and more): the same result, never
76    /// slower.
77    /// Requires each `i < hashers.len()`.
78    #[cfg(feature = "std")]
79    pub fn update_each_multithreaded(hashers: &mut [Hasher], pieces: &[(usize, &[u8])]) {
80        crate::lanes::require();
81        update_turn(hashers, pieces, true);
82    }
83
84    /// The hash of each message `which` names: `out[k]` is
85    /// `hashers[which[k]].finalize()`. Requires `out.len() == which.len()`
86    /// and each index `< hashers.len()`.
87    pub fn finalize_each(hashers: &[Hasher], which: &[usize], out: &mut [[u8; OUT_LEN]]) {
88        assert_eq!(which.len(), out.len(), "one digest per message named");
89        for (&i, out) in which.iter().zip(out) {
90            *out = *hashers[i].finalize().as_bytes();
91        }
92    }
93}
94
95/// A turn of pieces for many hashers: each piece gathered into its
96/// hasher's stage, and every stage that fills a whole group held, its
97/// hasher's later pieces waiting, until the turn's held groups hash
98/// together: their chunks back to back, a group per call with nothing in
99/// between (the SME unit stays in its fast state), then each level of
100/// their parents in one call. Then the waiting pieces, the same way, until
101/// none is left.
102fn update_turn(hashers: &mut [Hasher], pieces: &[(usize, &[u8])], pooled: bool) {
103    let mut turn: Vec<(usize, &[u8])> = pieces.to_vec();
104    let mut waiting: Vec<(usize, &[u8])> = Vec::new();
105    let mut held: Vec<usize> = Vec::new();
106    while !turn.is_empty() {
107        for &(i, bytes) in &turn {
108            // A hasher holding a group takes no more until the turn's
109            // groups are hashed: its pieces wait, in order.
110            if hashers[i].held_group().is_some() {
111                waiting.push((i, bytes));
112                continue;
113            }
114            let rest = hashers[i].gather_part(bytes, pooled, true);
115            if hashers[i].held_group().is_some() {
116                held.push(i);
117                if !rest.is_empty() {
118                    waiting.push((i, rest));
119                }
120            }
121        }
122        hash_held(hashers, &held);
123        // The loop's variant: every held group was hashed, so each waiting
124        // piece gathers on the next pass, and the bytes in play shrink on
125        // every pass (a change that kept them would spin here forever;
126        // the assert makes it a failure a test sees).
127        assert!(held.iter().all(|&i| hashers[i].held_group().is_none()), "a held group outlived its turn");
128        let (before, after): (usize, usize) = (turn.iter().map(|p| p.1.len()).sum(), waiting.iter().map(|p| p.1.len()).sum());
129        assert!(
130            after < before || (after == before && waiting.len() < turn.len()),
131            "a turn's pass gathered nothing ({} pieces of {before} bytes before, {} of {after} after)",
132            turn.len(),
133            waiting.len()
134        );
135        held.clear();
136        core::mem::swap(&mut turn, &mut waiting);
137        waiting.clear();
138    }
139}
140
141/// Hash the whole groups `held` names, one in each of those hashers'
142/// stages, together where they share a key and flags, and pass each
143/// group's subtree to its hasher's core.
144#[cfg(feature = "std")]
145fn hash_held(hashers: &mut [Hasher], held: &[usize]) {
146    use crate::{BLOCK_LEN, PARENT};
147    let Some(&first) = held.first() else { return };
148    let (key, flags) = (hashers[first].core.key, hashers[first].core.chunk_state.flags);
149    let (alike, others): (Vec<usize>, Vec<usize>) = held.iter().partition(|&&i| hashers[i].core.key == key && hashers[i].core.chunk_state.flags == flags);
150    let turn = crate::platform::Sme2Turn::take(hashers[first].core.chunk_state.platform, true);
151    let platform = turn.platform();
152    let n = alike.len();
153    let per = crate::STAGE_LEN / CHUNK_LEN;
154    let chunks = n * per;
155    let mut level = vec![0u8; chunks * OUT_LEN];
156    let refs: Vec<&[u8; CHUNK_LEN]> =
157        alike.iter().flat_map(|&i| hashers[i].held_group().expect("a held group").1.chunks_exact(CHUNK_LEN)).map(|c| c.try_into().unwrap()).collect();
158    let counters: Vec<u64> = alike.iter().map(|&i| hashers[i].held_group().unwrap().0).collect();
159    // On SME2, every group in one kernel call, each at its own counter;
160    // elsewhere a call per group.
161    #[cfg(blake3_sme2)]
162    let on_sme2 = matches!(platform, Platform::SME2);
163    #[cfg(not(blake3_sme2))]
164    let on_sme2 = false;
165    if on_sme2 {
166        // Sound: the turn's platform is SME2 only where detect() found it.
167        #[cfg(blake3_sme2)]
168        unsafe {
169            crate::sme2::hash_groups_at(&refs, &counters, &key, flags, CHUNK_START, CHUNK_END, &mut level)
170        };
171    } else {
172        for (k, &counter) in counters.iter().enumerate() {
173            platform.hash_many(
174                &refs[k * per..(k + 1) * per],
175                &key,
176                counter,
177                IncrementCounter::Yes,
178                flags,
179                CHUNK_START,
180                CHUNK_END,
181                &mut level[k * per * OUT_LEN..(k + 1) * per * OUT_LEN],
182            );
183        }
184    }
185    // Three levels of parents to each group's two halves, then a fourth to
186    // its own value.
187    let mut values = chunks;
188    let mut next = vec![0u8; chunks / 2 * OUT_LEN];
189    let mut halves = vec![0u8; 2 * n * OUT_LEN];
190    for depth in 0..4 {
191        if depth == 3 {
192            halves.copy_from_slice(&level[..2 * n * OUT_LEN]);
193        }
194        let blocks: Vec<&[u8; BLOCK_LEN]> = level[..values * OUT_LEN].chunks_exact(BLOCK_LEN).map(|b| b.try_into().unwrap()).collect();
195        platform.hash_many(&blocks, &key, 0, IncrementCounter::No, flags | PARENT, 0, 0, &mut next[..values / 2 * OUT_LEN]);
196        values /= 2;
197        level[..values * OUT_LEN].copy_from_slice(&next[..values * OUT_LEN]);
198    }
199    drop(turn);
200    for (k, &i) in alike.iter().enumerate() {
201        let (counter, _) = hashers[i].held_group().unwrap();
202        let mut result = [0u8; BLOCK_LEN];
203        if counter == 0 {
204            result.copy_from_slice(&halves[k * BLOCK_LEN..(k + 1) * BLOCK_LEN]);
205        } else {
206            result[..OUT_LEN].copy_from_slice(&level[k * OUT_LEN..(k + 1) * OUT_LEN]);
207        }
208        hashers[i].take_held(&result);
209    }
210    hash_held(hashers, &others);
211}
212
213#[cfg(not(feature = "std"))]
214fn hash_held(_: &mut [Hasher], held: &[usize]) {
215    assert!(held.is_empty(), "nothing held without std");
216}
217
218/// Messages of this many chunks or more fill the lanes alone.
219const ALONE_CHUNKS: usize = 16;
220
221/// The hash of each message, of any lengths, on the calling thread:
222/// `out[i]` is [`hash_with`](crate::hash_with)`(mode, items[i])`. Short
223/// messages hash together, so a collection of small items (a directory's
224/// files, a repository's objects) takes less time than one call each.
225/// Requires `out.len() == items.len()`.
226///
227/// ```
228/// # blake3_servil::initialize();
229/// use blake3_servil::Mode;
230/// let items: Vec<Vec<u8>> = (0..100).map(|i| vec![i as u8; 100 * i]).collect();
231/// let slices: Vec<&[u8]> = items.iter().map(|m| m.as_slice()).collect();
232/// let mut out = vec![[0u8; 32]; slices.len()];
233/// blake3_servil::hash_each_with(Mode::Hash, &slices, &mut out);
234/// assert_eq!(&out[42], blake3_servil::hash(&items[42]).as_bytes());
235/// ```
236pub fn hash_each_with(mode: Mode, items: &[&[u8]], out: &mut [[u8; OUT_LEN]]) {
237    assert_eq!(items.len(), out.len(), "one digest per item");
238    let (key, flags) = mode.key_and_flags();
239    hash_each_on(&key, flags, items, out, Platform::detect(), |item| crate::hash_with(mode, item));
240}
241
242/// [`hash_each_with`] in the mode of `key` and `flags`, the lanes on
243/// `platform`, each message that fills the lanes alone (or is a chunk or
244/// less) through `alone`.
245pub(crate) fn hash_each_on(key: &CVWords, flags: u8, items: &[&[u8]], out: &mut [[u8; OUT_LEN]], platform: Platform, alone: impl Fn(&[u8]) -> Hash) {
246    let key = *key;
247    // The messages whose full chunks share the lanes: each one's index, and
248    // where its chunk values start in `cvs`.
249    let mut shared: Vec<(usize, usize)> = Vec::new();
250    let mut slots = 0;
251    let mut most_full = 0;
252    for (i, item) in items.iter().enumerate() {
253        let chunks = item.len().div_ceil(CHUNK_LEN);
254        if chunks <= 1 || chunks >= ALONE_CHUNKS {
255            out[i] = *alone(item).as_bytes();
256        } else {
257            most_full = most_full.max(item.len() / CHUNK_LEN);
258            shared.push((i, slots));
259            slots += chunks;
260        }
261    }
262    let mut cvs = vec![[0u8; OUT_LEN]; slots];
263    let mut refs: Vec<&[u8; CHUNK_LEN]> = Vec::with_capacity(shared.len());
264    let mut owners: Vec<usize> = Vec::with_capacity(shared.len());
265    let mut lane_out = vec![0u8; shared.len() * OUT_LEN];
266    for k in 0..most_full {
267        refs.clear();
268        owners.clear();
269        for &(i, at) in &shared {
270            if let Some(chunk) = items[i].get(k * CHUNK_LEN..(k + 1) * CHUNK_LEN) {
271                refs.push(chunk.try_into().unwrap());
272                owners.push(at + k);
273            }
274        }
275        let lanes = &mut lane_out[..refs.len() * OUT_LEN];
276        platform.hash_many(&refs, &key, k as u64, IncrementCounter::No, flags, CHUNK_START, CHUNK_END, lanes);
277        for (j, &slot) in owners.iter().enumerate() {
278            cvs[slot].copy_from_slice(&lanes[j * OUT_LEN..(j + 1) * OUT_LEN]);
279        }
280    }
281    for &(i, at) in &shared {
282        let item = items[i];
283        let chunks = item.len().div_ceil(CHUNK_LEN);
284        let full = item.len() / CHUNK_LEN;
285        if full < chunks {
286            cvs[at + full] = ChunkState::new(&key, full as u64, flags, platform).update(&item[full * CHUNK_LEN..]).output().chaining_value();
287        }
288        out[i] = *root(&cvs[at..at + chunks], &key, flags, platform).as_bytes();
289    }
290}
291
292/// The root of a message of two or more chunks, from its chunk values: the
293/// left subtree takes the largest power of two of chunks below the count.
294fn root(cvs: &[CVBytes], key: &CVWords, flags: u8, platform: Platform) -> Hash {
295    let split = left_len(cvs.len());
296    let left = subtree(&cvs[..split], key, flags, platform);
297    let right = subtree(&cvs[split..], key, flags, platform);
298    crate::hasher::parent_output(&left, &right, key, flags, platform).root_hash()
299}
300
301/// A non-root subtree's chaining value.
302fn subtree(cvs: &[CVBytes], key: &CVWords, flags: u8, platform: Platform) -> CVBytes {
303    if cvs.len() == 1 {
304        return cvs[0];
305    }
306    let split = left_len(cvs.len());
307    let left = subtree(&cvs[..split], key, flags, platform);
308    let right = subtree(&cvs[split..], key, flags, platform);
309    crate::hasher::parent_output(&left, &right, key, flags, platform).chaining_value()
310}
311
312/// The largest power of two below `n` (n of 2 or more).
313fn left_len(n: usize) -> usize {
314    debug_assert!(n >= 2);
315    1 << (usize::BITS - 1 - (n - 1).leading_zeros())
316}
317
318#[cfg(test)]
319mod test {
320    use super::*;
321
322    /// The pool's ranges of items (lanes::Work::Each), just past where the
323    /// pool takes them, against the calling thread's: small enough for
324    /// Miri (the CI's smoketest runs it).
325    #[test]
326    fn test_miri_hash_each_multithreaded() {
327        let mut input = vec![0u8; crate::lanes::MIN_SPLIT_LEN + 8 * 1024];
328        crate::test::paint_test_input(&mut input);
329        let items: Vec<&[u8]> = input.chunks(crate::lanes::MIN_SPLIT_LEN / 40 + 7).collect();
330        let (mut a, mut b) = (vec![[0u8; OUT_LEN]; items.len()], vec![[0u8; OUT_LEN]; items.len()]);
331        crate::RAN.with(|r| r.set(0));
332        hash_each_multithreaded_with(Mode::Hash, &items, &mut a);
333        crate::lanes::assert_past_the_split("the items");
334        hash_each_with(Mode::Hash, &items, &mut b);
335        assert_eq!(a, b);
336    }
337
338    /// A collection past the split (items around chunk, lane, and the
339    /// split's own length, a few of 512 KiB and more), every mode: the
340    /// multithreaded form gives hash_each_with's digests.
341    /// Keep: it detects, by hanging, mutants the clock then stops
342    /// (tools/mutants/timeouts-x86_64.txt: hash_each, initialize, Source::take, Source::finished, Source::wait, slot_len, hash_many_on, hash_run).
343    #[test]
344    fn test_hash_each_multithreaded() {
345        let mut input = vec![0u8; 3 << 20];
346        crate::test::paint_test_input(&mut input);
347        let lens = [0, 1, 1024, 1025, 3000, 15 * 1024, 16 * 1024, 100_000, 511 * 1024, 512 * 1024, 700_000];
348        let items: Vec<&[u8]> = (0..400)
349            .map(|k| {
350                let n = lens[k * 7 % lens.len()].min(input.len() - k);
351                &input[k..k + n]
352            })
353            .collect();
354        let key = [9u8; 32];
355        for mode in [Mode::Hash, Mode::Keyed(&key), Mode::DeriveKey("each mt")] {
356            let (mut a, mut b) = (vec![[0u8; OUT_LEN]; items.len()], vec![[0u8; OUT_LEN]; items.len()]);
357            hash_each_multithreaded_with(mode, &items, &mut a);
358            hash_each_with(mode, &items, &mut b);
359            assert_eq!(a, b);
360            // Below the split, on the calling thread: the items of 16 KiB
361            // or less, which sum to less than the split's length.
362            let small: Vec<usize> = (0..items.len()).filter(|&k| items[k].len() <= 16 * 1024).take(30).collect();
363            assert!(small.iter().map(|&k| items[k].len()).sum::<usize>() < crate::lanes::MIN_SPLIT_LEN);
364            let small_items: Vec<&[u8]> = small.iter().map(|&k| items[k]).collect();
365            let mut c = vec![[0u8; OUT_LEN]; small.len()];
366            hash_each_multithreaded_with(mode, &small_items, &mut c);
367            assert!(small.iter().zip(&c).all(|(&k, d)| *d == b[k]));
368        }
369    }
370
371    /// Many hashers fed in turns of interleaved pieces of many lengths:
372    /// update_each, its multithreaded twin, and finalize_each give every
373    /// message the hash one Hasher per message gives.
374    /// Turns in which several hashers hold a group each, under two keys
375    /// whose flags agree, beyond their first group and at it (nonzero
376    /// counters, and zero): the groups of one key hash together, each
377    /// lands in its own hasher.
378    #[test]
379    fn test_update_each_holds_groups_together() {
380        for platform in crate::test::every_platform() {
381            holds_groups_together(platform);
382        }
383    }
384
385    /// Hashers of subtrees at input offsets in update_each's turns,
386    /// beside hashers of whole messages: they hold no groups, and each
387    /// gives the chaining value one update of its subtree gives.
388    #[test]
389    fn test_update_each_at_offsets() {
390        use crate::test::SubtreeHasher;
391        let mut input = vec![0u8; 1 << 20];
392        crate::test::paint_test_input(&mut input);
393        // (offset, length): subtrees within what their offsets allow.
394        let subtrees = [(64 * CHUNK_LEN, 64 * CHUNK_LEN), (16 * CHUNK_LEN, 16 * CHUNK_LEN), (CHUNK_LEN, CHUNK_LEN), (128 * CHUNK_LEN, 100_000)];
395        let whole = [70_000usize, 300_000];
396        let mut hashers: Vec<Hasher> = subtrees
397            .iter()
398            .map(|&(offset, _)| {
399                let mut h = Hasher::new();
400                h.set_input_offset(offset as u64);
401                h
402            })
403            .collect();
404        hashers.extend(whole.iter().map(|_| Hasher::new()));
405        let lens: Vec<usize> = subtrees.iter().map(|&(_, len)| len).chain(whole).collect();
406        let mut done = vec![0usize; lens.len()];
407        let pieces = [1448usize, 31, 16384, 4096, 1];
408        let mut k = 0;
409        while done.iter().zip(&lens).any(|(d, l)| d < l) {
410            let mut turn: Vec<(usize, &[u8])> = Vec::new();
411            for _ in 0..9 {
412                let i = k % lens.len();
413                let n = pieces[k % pieces.len()].min(lens[i] - done[i]);
414                turn.push((i, &input[done[i]..done[i] + n]));
415                done[i] += n;
416                k += 1;
417            }
418            Hasher::update_each(&mut hashers, &turn);
419        }
420        for (i, &(offset, len)) in subtrees.iter().enumerate() {
421            let mut one = Hasher::new();
422            one.set_input_offset(offset as u64).update(&input[..len]);
423            assert_eq!(hashers[i].finalize_non_root(), one.finalize_non_root(), "subtree at {offset}, {len} bytes");
424        }
425        for (j, &len) in whole.iter().enumerate() {
426            assert_eq!(hashers[subtrees.len() + j].finalize(), crate::hash(&input[..len]), "whole message of {len} bytes");
427        }
428    }
429
430    fn holds_groups_together(platform: crate::platform::Platform) {
431        let mut input = vec![0u8; 3 * crate::STAGE_LEN];
432        crate::test::paint_test_input(&mut input);
433        let keys = [[1u8; 32], [2u8; 32]];
434        let on = |mut h: Hasher| {
435            h.core.chunk_state.platform = platform;
436            h
437        };
438        let mut hashers: Vec<Hasher> = (0..6).map(|i| on(Hasher::new_with(crate::Mode::Keyed(&keys[i % 2])))).collect();
439        // Each hasher a group in, its message at a different offset into the
440        // input; then one turn of two pieces each, which stage its second
441        // group from its start and fill it (held), and 7 bytes more.
442        let start = |i: usize| i * 1000;
443        let group = crate::STAGE_LEN;
444        for (i, h) in hashers.iter_mut().enumerate() {
445            h.update(&input[start(i)..start(i) + group]);
446        }
447        let turn: Vec<(usize, &[u8])> = (0..6)
448            .flat_map(|i| [(i, &input[start(i) + group..start(i) + group + 100]), (i, &input[start(i) + group + 100..start(i) + 2 * group + 7])])
449            .collect();
450        Hasher::update_each(&mut hashers, &turn);
451        for (i, h) in hashers.iter().enumerate() {
452            let message = &input[start(i)..start(i) + 2 * crate::STAGE_LEN + 7];
453            assert_eq!(h.finalize(), crate::hash_with(crate::Mode::Keyed(&keys[i % 2]), message), "hasher {i}, {platform:?}");
454        }
455        // And each hasher's first group (chunk counter zero, which hands
456        // its core the group's two halves), six at once: a first piece
457        // longer than a chunk, so it is staged from offset zero.
458        let mut fresh: Vec<Hasher> = (0..6).map(|i| on(Hasher::new_with(crate::Mode::Keyed(&keys[i % 2])))).collect();
459        let turn: Vec<(usize, &[u8])> =
460            (0..6).flat_map(|i| [(i, &input[start(i)..start(i) + 1100]), (i, &input[start(i) + 1100..start(i) + group + 7])]).collect();
461        Hasher::update_each(&mut fresh, &turn);
462        for (i, h) in fresh.iter().enumerate() {
463            assert_eq!(
464                h.finalize(),
465                crate::hash_with(crate::Mode::Keyed(&keys[i % 2]), &input[start(i)..start(i) + group + 7]),
466                "fresh hasher {i}, {platform:?}"
467            );
468        }
469    }
470
471    #[test]
472    fn test_update_each() {
473        let mut input = vec![0u8; 1 << 20];
474        crate::test::paint_test_input(&mut input);
475        let lens = [0, 1, 63, 64, 1023, 1024, 1025, 2048, 4470, 8191, 16384, 16385, 65536, 100_000, 300_000];
476        let piece_lens = [1, 1448, 4096, 1448, 16384, 31, 65536];
477        for multithreaded in [false, true] {
478            let key = [5u8; 32];
479            // Every third hasher keyed: a turn's held groups in two kinds.
480            let mut hashers: Vec<Hasher> =
481                (0..lens.len()).map(|i| if i % 3 == 1 { Hasher::new_with(crate::Mode::Keyed(&key)) } else { Hasher::new() }).collect();
482            let mut done = vec![0usize; lens.len()];
483            let mut k = 0;
484            while done.iter().zip(&lens).any(|(d, l)| d < l) {
485                let mut pieces: Vec<(usize, &[u8])> = Vec::new();
486                for _ in 0..23 {
487                    let i = k % lens.len();
488                    let n = piece_lens[k % piece_lens.len()].min(lens[i] - done[i]);
489                    pieces.push((i, &input[done[i]..done[i] + n]));
490                    done[i] += n;
491                    k += 1;
492                }
493                if multithreaded {
494                    Hasher::update_each_multithreaded(&mut hashers, &pieces);
495                } else {
496                    Hasher::update_each(&mut hashers, &pieces);
497                }
498            }
499            let which: Vec<usize> = (0..lens.len()).rev().collect();
500            let mut out = vec![[0u8; OUT_LEN]; lens.len()];
501            Hasher::finalize_each(&hashers, &which, &mut out);
502            for (k, &i) in which.iter().enumerate() {
503                let want = if i % 3 == 1 { crate::hash_with(crate::Mode::Keyed(&key), &input[..lens[i]]) } else { crate::hash(&input[..lens[i]]) };
504                assert_eq!(&out[k], want.as_bytes(), "len {} multithreaded {multithreaded}", lens[i]);
505            }
506        }
507    }
508
509    /// Every length around chunk and lane boundaries, in every mode, mixed in
510    /// one call, against `hash_with` on each.
511    /// Keep: it detects, by hanging, mutants the clock then stops
512    /// (tools/mutants/timeouts-x86_64.txt: Hasher::from_core, Hasher::gather).
513    #[test]
514    fn test_hash_each_matches_hash_with() {
515        let mut input = vec![0u8; 40 * CHUNK_LEN];
516        crate::test::paint_test_input(&mut input);
517        let mut lens = vec![
518            0,
519            1,
520            63,
521            64,
522            65,
523            1023,
524            1024,
525            1025,
526            2047,
527            2048,
528            2049,
529            3000,
530            4096,
531            5000,
532            15 * CHUNK_LEN,
533            15 * CHUNK_LEN + 1,
534            16 * CHUNK_LEN - 1,
535            16 * CHUNK_LEN,
536            16 * CHUNK_LEN + 1,
537            40 * CHUNK_LEN,
538        ];
539        for n in 2..16 {
540            lens.push(n * CHUNK_LEN);
541            lens.push(n * CHUNK_LEN - 7);
542        }
543        let items: Vec<&[u8]> = lens.iter().enumerate().map(|(j, &l)| &input[j % 3..j % 3 + l.min(input.len() - 2)]).collect();
544        let key = [9u8; 32];
545        for mode in [Mode::Hash, Mode::Keyed(&key), Mode::DeriveKey("hash_each test")] {
546            let mut out = vec![[0u8; OUT_LEN]; items.len()];
547            hash_each_with(mode, &items, &mut out);
548            for (item, digest) in items.iter().zip(&out) {
549                assert_eq!(digest, crate::hash_with(mode, item).as_bytes(), "length {}", item.len());
550            }
551        }
552    }
553}
blake3_servil/each.rs

blake3_servil/
each.rs
