1 #include <assert.h>
2 #include <stdbool.h>
3 #include <string.h>
4
5 #include "blake3.h"
6 #include "blake3_impl.h"
7
blake3_version(void)8 const char *blake3_version(void) { return BLAKE3_VERSION_STRING; }
9
chunk_state_init(blake3_chunk_state * self,const uint32_t key[8],uint8_t flags)10 INLINE void chunk_state_init(blake3_chunk_state *self, const uint32_t key[8],
11 uint8_t flags) {
12 memcpy(self->cv, key, BLAKE3_KEY_LEN);
13 self->chunk_counter = 0;
14 memset(self->buf, 0, BLAKE3_BLOCK_LEN);
15 self->buf_len = 0;
16 self->blocks_compressed = 0;
17 self->flags = flags;
18 }
19
chunk_state_reset(blake3_chunk_state * self,const uint32_t key[8],uint64_t chunk_counter)20 INLINE void chunk_state_reset(blake3_chunk_state *self, const uint32_t key[8],
21 uint64_t chunk_counter) {
22 memcpy(self->cv, key, BLAKE3_KEY_LEN);
23 self->chunk_counter = chunk_counter;
24 self->blocks_compressed = 0;
25 memset(self->buf, 0, BLAKE3_BLOCK_LEN);
26 self->buf_len = 0;
27 }
28
chunk_state_len(const blake3_chunk_state * self)29 INLINE size_t chunk_state_len(const blake3_chunk_state *self) {
30 return (BLAKE3_BLOCK_LEN * (size_t)self->blocks_compressed) +
31 ((size_t)self->buf_len);
32 }
33
chunk_state_fill_buf(blake3_chunk_state * self,const uint8_t * input,size_t input_len)34 INLINE size_t chunk_state_fill_buf(blake3_chunk_state *self,
35 const uint8_t *input, size_t input_len) {
36 size_t take = BLAKE3_BLOCK_LEN - ((size_t)self->buf_len);
37 if (take > input_len) {
38 take = input_len;
39 }
40 uint8_t *dest = self->buf + ((size_t)self->buf_len);
41 memcpy(dest, input, take);
42 self->buf_len += (uint8_t)take;
43 return take;
44 }
45
chunk_state_maybe_start_flag(const blake3_chunk_state * self)46 INLINE uint8_t chunk_state_maybe_start_flag(const blake3_chunk_state *self) {
47 if (self->blocks_compressed == 0) {
48 return CHUNK_START;
49 } else {
50 return 0;
51 }
52 }
53
54 typedef struct {
55 uint32_t input_cv[8];
56 uint64_t counter;
57 uint8_t block[BLAKE3_BLOCK_LEN];
58 uint8_t block_len;
59 uint8_t flags;
60 } output_t;
61
make_output(const uint32_t input_cv[8],const uint8_t block[BLAKE3_BLOCK_LEN],uint8_t block_len,uint64_t counter,uint8_t flags)62 INLINE output_t make_output(const uint32_t input_cv[8],
63 const uint8_t block[BLAKE3_BLOCK_LEN],
64 uint8_t block_len, uint64_t counter,
65 uint8_t flags) {
66 output_t ret;
67 memcpy(ret.input_cv, input_cv, 32);
68 memcpy(ret.block, block, BLAKE3_BLOCK_LEN);
69 ret.block_len = block_len;
70 ret.counter = counter;
71 ret.flags = flags;
72 return ret;
73 }
74
75 // Chaining values within a given chunk (specifically the compress_in_place
76 // interface) are represented as words. This avoids unnecessary bytes<->words
77 // conversion overhead in the portable implementation. However, the hash_many
78 // interface handles both user input and parent node blocks, so it accepts
79 // bytes. For that reason, chaining values in the CV stack are represented as
80 // bytes.
output_chaining_value(const output_t * self,uint8_t cv[32])81 INLINE void output_chaining_value(const output_t *self, uint8_t cv[32]) {
82 uint32_t cv_words[8];
83 memcpy(cv_words, self->input_cv, 32);
84 blake3_compress_in_place(cv_words, self->block, self->block_len,
85 self->counter, self->flags);
86 store_cv_words(cv, cv_words);
87 }
88
output_root_bytes(const output_t * self,uint64_t seek,uint8_t * out,size_t out_len)89 INLINE void output_root_bytes(const output_t *self, uint64_t seek, uint8_t *out,
90 size_t out_len) {
91 uint64_t output_block_counter = seek / 64;
92 size_t offset_within_block = seek % 64;
93 uint8_t wide_buf[64];
94 while (out_len > 0) {
95 blake3_compress_xof(self->input_cv, self->block, self->block_len,
96 output_block_counter, self->flags | ROOT, wide_buf);
97 size_t available_bytes = 64 - offset_within_block;
98 size_t memcpy_len;
99 if (out_len > available_bytes) {
100 memcpy_len = available_bytes;
101 } else {
102 memcpy_len = out_len;
103 }
104 memcpy(out, wide_buf + offset_within_block, memcpy_len);
105 out += memcpy_len;
106 out_len -= memcpy_len;
107 output_block_counter += 1;
108 offset_within_block = 0;
109 }
110 }
111
chunk_state_update(blake3_chunk_state * self,const uint8_t * input,size_t input_len)112 INLINE void chunk_state_update(blake3_chunk_state *self, const uint8_t *input,
113 size_t input_len) {
114 if (self->buf_len > 0) {
115 size_t take = chunk_state_fill_buf(self, input, input_len);
116 input += take;
117 input_len -= take;
118 if (input_len > 0) {
119 blake3_compress_in_place(
120 self->cv, self->buf, BLAKE3_BLOCK_LEN, self->chunk_counter,
121 self->flags | chunk_state_maybe_start_flag(self));
122 self->blocks_compressed += 1;
123 self->buf_len = 0;
124 memset(self->buf, 0, BLAKE3_BLOCK_LEN);
125 }
126 }
127
128 while (input_len > BLAKE3_BLOCK_LEN) {
129 blake3_compress_in_place(self->cv, input, BLAKE3_BLOCK_LEN,
130 self->chunk_counter,
131 self->flags | chunk_state_maybe_start_flag(self));
132 self->blocks_compressed += 1;
133 input += BLAKE3_BLOCK_LEN;
134 input_len -= BLAKE3_BLOCK_LEN;
135 }
136
137 size_t take = chunk_state_fill_buf(self, input, input_len);
138 input += take;
139 input_len -= take;
140 }
141
chunk_state_output(const blake3_chunk_state * self)142 INLINE output_t chunk_state_output(const blake3_chunk_state *self) {
143 uint8_t block_flags =
144 self->flags | chunk_state_maybe_start_flag(self) | CHUNK_END;
145 return make_output(self->cv, self->buf, self->buf_len, self->chunk_counter,
146 block_flags);
147 }
148
parent_output(const uint8_t block[BLAKE3_BLOCK_LEN],const uint32_t key[8],uint8_t flags)149 INLINE output_t parent_output(const uint8_t block[BLAKE3_BLOCK_LEN],
150 const uint32_t key[8], uint8_t flags) {
151 return make_output(key, block, BLAKE3_BLOCK_LEN, 0, flags | PARENT);
152 }
153
154 // Given some input larger than one chunk, return the number of bytes that
155 // should go in the left subtree. This is the largest power-of-2 number of
156 // chunks that leaves at least 1 byte for the right subtree.
left_len(size_t content_len)157 INLINE size_t left_len(size_t content_len) {
158 // Subtract 1 to reserve at least one byte for the right side. content_len
159 // should always be greater than BLAKE3_CHUNK_LEN.
160 size_t full_chunks = (content_len - 1) / BLAKE3_CHUNK_LEN;
161 return round_down_to_power_of_2(full_chunks) * BLAKE3_CHUNK_LEN;
162 }
163
164 // Use SIMD parallelism to hash up to MAX_SIMD_DEGREE chunks at the same time
165 // on a single thread. Write out the chunk chaining values and return the
166 // number of chunks hashed. These chunks are never the root and never empty;
167 // those cases use a different codepath.
compress_chunks_parallel(const uint8_t * input,size_t input_len,const uint32_t key[8],uint64_t chunk_counter,uint8_t flags,uint8_t * out)168 INLINE size_t compress_chunks_parallel(const uint8_t *input, size_t input_len,
169 const uint32_t key[8],
170 uint64_t chunk_counter, uint8_t flags,
171 uint8_t *out) {
172 #if defined(BLAKE3_TESTING)
173 assert(0 < input_len);
174 assert(input_len <= MAX_SIMD_DEGREE * BLAKE3_CHUNK_LEN);
175 #endif
176
177 const uint8_t *chunks_array[MAX_SIMD_DEGREE];
178 size_t input_position = 0;
179 size_t chunks_array_len = 0;
180 while (input_len - input_position >= BLAKE3_CHUNK_LEN) {
181 chunks_array[chunks_array_len] = &input[input_position];
182 input_position += BLAKE3_CHUNK_LEN;
183 chunks_array_len += 1;
184 }
185
186 blake3_hash_many(chunks_array, chunks_array_len,
187 BLAKE3_CHUNK_LEN / BLAKE3_BLOCK_LEN, key, chunk_counter,
188 true, flags, CHUNK_START, CHUNK_END, out);
189
190 // Hash the remaining partial chunk, if there is one. Note that the empty
191 // chunk (meaning the empty message) is a different codepath.
192 if (input_len > input_position) {
193 uint64_t counter = chunk_counter + (uint64_t)chunks_array_len;
194 blake3_chunk_state chunk_state;
195 chunk_state_init(&chunk_state, key, flags);
196 chunk_state.chunk_counter = counter;
197 chunk_state_update(&chunk_state, &input[input_position],
198 input_len - input_position);
199 output_t output = chunk_state_output(&chunk_state);
200 output_chaining_value(&output, &out[chunks_array_len * BLAKE3_OUT_LEN]);
201 return chunks_array_len + 1;
202 } else {
203 return chunks_array_len;
204 }
205 }
206
207 // Use SIMD parallelism to hash up to MAX_SIMD_DEGREE parents at the same time
208 // on a single thread. Write out the parent chaining values and return the
209 // number of parents hashed. (If there's an odd input chaining value left over,
210 // return it as an additional output.) These parents are never the root and
211 // never empty; those cases use a different codepath.
compress_parents_parallel(const uint8_t * child_chaining_values,size_t num_chaining_values,const uint32_t key[8],uint8_t flags,uint8_t * out)212 INLINE size_t compress_parents_parallel(const uint8_t *child_chaining_values,
213 size_t num_chaining_values,
214 const uint32_t key[8], uint8_t flags,
215 uint8_t *out) {
216 #if defined(BLAKE3_TESTING)
217 assert(2 <= num_chaining_values);
218 assert(num_chaining_values <= 2 * MAX_SIMD_DEGREE_OR_2);
219 #endif
220
221 const uint8_t *parents_array[MAX_SIMD_DEGREE_OR_2];
222 size_t parents_array_len = 0;
223 while (num_chaining_values - (2 * parents_array_len) >= 2) {
224 parents_array[parents_array_len] =
225 &child_chaining_values[2 * parents_array_len * BLAKE3_OUT_LEN];
226 parents_array_len += 1;
227 }
228
229 blake3_hash_many(parents_array, parents_array_len, 1, key,
230 0, // Parents always use counter 0.
231 false, flags | PARENT,
232 0, // Parents have no start flags.
233 0, // Parents have no end flags.
234 out);
235
236 // If there's an odd child left over, it becomes an output.
237 if (num_chaining_values > 2 * parents_array_len) {
238 memcpy(&out[parents_array_len * BLAKE3_OUT_LEN],
239 &child_chaining_values[2 * parents_array_len * BLAKE3_OUT_LEN],
240 BLAKE3_OUT_LEN);
241 return parents_array_len + 1;
242 } else {
243 return parents_array_len;
244 }
245 }
246
247 // The wide helper function returns (writes out) an array of chaining values
248 // and returns the length of that array. The number of chaining values returned
249 // is the dynamically detected SIMD degree, at most MAX_SIMD_DEGREE. Or fewer,
250 // if the input is shorter than that many chunks. The reason for maintaining a
251 // wide array of chaining values going back up the tree, is to allow the
252 // implementation to hash as many parents in parallel as possible.
253 //
254 // As a special case when the SIMD degree is 1, this function will still return
255 // at least 2 outputs. This guarantees that this function doesn't perform the
256 // root compression. (If it did, it would use the wrong flags, and also we
257 // wouldn't be able to implement exendable output.) Note that this function is
258 // not used when the whole input is only 1 chunk long; that's a different
259 // codepath.
260 //
261 // Why not just have the caller split the input on the first update(), instead
262 // of implementing this special rule? Because we don't want to limit SIMD or
263 // multi-threading parallelism for that update().
blake3_compress_subtree_wide(const uint8_t * input,size_t input_len,const uint32_t key[8],uint64_t chunk_counter,uint8_t flags,uint8_t * out)264 static size_t blake3_compress_subtree_wide(const uint8_t *input,
265 size_t input_len,
266 const uint32_t key[8],
267 uint64_t chunk_counter,
268 uint8_t flags, uint8_t *out) {
269 // Note that the single chunk case does *not* bump the SIMD degree up to 2
270 // when it is 1. If this implementation adds multi-threading in the future,
271 // this gives us the option of multi-threading even the 2-chunk case, which
272 // can help performance on smaller platforms.
273 if (input_len <= blake3_simd_degree() * BLAKE3_CHUNK_LEN) {
274 return compress_chunks_parallel(input, input_len, key, chunk_counter, flags,
275 out);
276 }
277
278 // With more than simd_degree chunks, we need to recurse. Start by dividing
279 // the input into left and right subtrees. (Note that this is only optimal
280 // as long as the SIMD degree is a power of 2. If we ever get a SIMD degree
281 // of 3 or something, we'll need a more complicated strategy.)
282 size_t left_input_len = left_len(input_len);
283 size_t right_input_len = input_len - left_input_len;
284 const uint8_t *right_input = &input[left_input_len];
285 uint64_t right_chunk_counter =
286 chunk_counter + (uint64_t)(left_input_len / BLAKE3_CHUNK_LEN);
287
288 // Make space for the child outputs. Here we use MAX_SIMD_DEGREE_OR_2 to
289 // account for the special case of returning 2 outputs when the SIMD degree
290 // is 1.
291 uint8_t cv_array[2 * MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN];
292 size_t degree = blake3_simd_degree();
293 if (left_input_len > BLAKE3_CHUNK_LEN && degree == 1) {
294 // The special case: We always use a degree of at least two, to make
295 // sure there are two outputs. Except, as noted above, at the chunk
296 // level, where we allow degree=1. (Note that the 1-chunk-input case is
297 // a different codepath.)
298 degree = 2;
299 }
300 uint8_t *right_cvs = &cv_array[degree * BLAKE3_OUT_LEN];
301
302 // Recurse! If this implementation adds multi-threading support in the
303 // future, this is where it will go.
304 size_t left_n = blake3_compress_subtree_wide(input, left_input_len, key,
305 chunk_counter, flags, cv_array);
306 size_t right_n = blake3_compress_subtree_wide(
307 right_input, right_input_len, key, right_chunk_counter, flags, right_cvs);
308
309 // The special case again. If simd_degree=1, then we'll have left_n=1 and
310 // right_n=1. Rather than compressing them into a single output, return
311 // them directly, to make sure we always have at least two outputs.
312 if (left_n == 1) {
313 memcpy(out, cv_array, 2 * BLAKE3_OUT_LEN);
314 return 2;
315 }
316
317 // Otherwise, do one layer of parent node compression.
318 size_t num_chaining_values = left_n + right_n;
319 return compress_parents_parallel(cv_array, num_chaining_values, key, flags,
320 out);
321 }
322
323 // Hash a subtree with compress_subtree_wide(), and then condense the resulting
324 // list of chaining values down to a single parent node. Don't compress that
325 // last parent node, however. Instead, return its message bytes (the
326 // concatenated chaining values of its children). This is necessary when the
327 // first call to update() supplies a complete subtree, because the topmost
328 // parent node of that subtree could end up being the root. It's also necessary
329 // for extended output in the general case.
330 //
331 // As with compress_subtree_wide(), this function is not used on inputs of 1
332 // chunk or less. That's a different codepath.
compress_subtree_to_parent_node(const uint8_t * input,size_t input_len,const uint32_t key[8],uint64_t chunk_counter,uint8_t flags,uint8_t out[2* BLAKE3_OUT_LEN])333 INLINE void compress_subtree_to_parent_node(
334 const uint8_t *input, size_t input_len, const uint32_t key[8],
335 uint64_t chunk_counter, uint8_t flags, uint8_t out[2 * BLAKE3_OUT_LEN]) {
336 #if defined(BLAKE3_TESTING)
337 assert(input_len > BLAKE3_CHUNK_LEN);
338 #endif
339
340 uint8_t cv_array[MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN];
341 size_t num_cvs = blake3_compress_subtree_wide(input, input_len, key,
342 chunk_counter, flags, cv_array);
343 assert(num_cvs <= MAX_SIMD_DEGREE_OR_2);
344
345 // If MAX_SIMD_DEGREE is greater than 2 and there's enough input,
346 // compress_subtree_wide() returns more than 2 chaining values. Condense
347 // them into 2 by forming parent nodes repeatedly.
348 uint8_t out_array[MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN / 2];
349 // The second half of this loop condition is always true, and we just
350 // asserted it above. But GCC can't tell that it's always true, and if NDEBUG
351 // is set on platforms where MAX_SIMD_DEGREE_OR_2 == 2, GCC emits spurious
352 // warnings here. GCC 8.5 is particularly sensitive, so if you're changing
353 // this code, test it against that version.
354 while (num_cvs > 2 && num_cvs <= MAX_SIMD_DEGREE_OR_2) {
355 num_cvs =
356 compress_parents_parallel(cv_array, num_cvs, key, flags, out_array);
357 memcpy(cv_array, out_array, num_cvs * BLAKE3_OUT_LEN);
358 }
359 memcpy(out, cv_array, 2 * BLAKE3_OUT_LEN);
360 }
361
hasher_init_base(blake3_hasher * self,const uint32_t key[8],uint8_t flags)362 INLINE void hasher_init_base(blake3_hasher *self, const uint32_t key[8],
363 uint8_t flags) {
364 memcpy(self->key, key, BLAKE3_KEY_LEN);
365 chunk_state_init(&self->chunk, key, flags);
366 self->cv_stack_len = 0;
367 }
368
blake3_hasher_init(blake3_hasher * self)369 void blake3_hasher_init(blake3_hasher *self) { hasher_init_base(self, IV, 0); }
370
blake3_hasher_init_keyed(blake3_hasher * self,const uint8_t key[BLAKE3_KEY_LEN])371 void blake3_hasher_init_keyed(blake3_hasher *self,
372 const uint8_t key[BLAKE3_KEY_LEN]) {
373 uint32_t key_words[8];
374 load_key_words(key, key_words);
375 hasher_init_base(self, key_words, KEYED_HASH);
376 }
377
blake3_hasher_init_derive_key_raw(blake3_hasher * self,const void * context,size_t context_len)378 void blake3_hasher_init_derive_key_raw(blake3_hasher *self, const void *context,
379 size_t context_len) {
380 blake3_hasher context_hasher;
381 hasher_init_base(&context_hasher, IV, DERIVE_KEY_CONTEXT);
382 blake3_hasher_update(&context_hasher, context, context_len);
383 uint8_t context_key[BLAKE3_KEY_LEN];
384 blake3_hasher_finalize(&context_hasher, context_key, BLAKE3_KEY_LEN);
385 uint32_t context_key_words[8];
386 load_key_words(context_key, context_key_words);
387 hasher_init_base(self, context_key_words, DERIVE_KEY_MATERIAL);
388 }
389
blake3_hasher_init_derive_key(blake3_hasher * self,const char * context)390 void blake3_hasher_init_derive_key(blake3_hasher *self, const char *context) {
391 blake3_hasher_init_derive_key_raw(self, context, strlen(context));
392 }
393
394 // As described in hasher_push_cv() below, we do "lazy merging", delaying
395 // merges until right before the next CV is about to be added. This is
396 // different from the reference implementation. Another difference is that we
397 // aren't always merging 1 chunk at a time. Instead, each CV might represent
398 // any power-of-two number of chunks, as long as the smaller-above-larger stack
399 // order is maintained. Instead of the "count the trailing 0-bits" algorithm
400 // described in the spec, we use a "count the total number of 1-bits" variant
401 // that doesn't require us to retain the subtree size of the CV on top of the
402 // stack. The principle is the same: each CV that should remain in the stack is
403 // represented by a 1-bit in the total number of chunks (or bytes) so far.
hasher_merge_cv_stack(blake3_hasher * self,uint64_t total_len)404 INLINE void hasher_merge_cv_stack(blake3_hasher *self, uint64_t total_len) {
405 size_t post_merge_stack_len = (size_t)popcnt(total_len);
406 while (self->cv_stack_len > post_merge_stack_len) {
407 uint8_t *parent_node =
408 &self->cv_stack[(self->cv_stack_len - 2) * BLAKE3_OUT_LEN];
409 output_t output = parent_output(parent_node, self->key, self->chunk.flags);
410 output_chaining_value(&output, parent_node);
411 self->cv_stack_len -= 1;
412 }
413 }
414
415 // In reference_impl.rs, we merge the new CV with existing CVs from the stack
416 // before pushing it. We can do that because we know more input is coming, so
417 // we know none of the merges are root.
418 //
419 // This setting is different. We want to feed as much input as possible to
420 // compress_subtree_wide(), without setting aside anything for the chunk_state.
421 // If the user gives us 64 KiB, we want to parallelize over all 64 KiB at once
422 // as a single subtree, if at all possible.
423 //
424 // This leads to two problems:
425 // 1) This 64 KiB input might be the only call that ever gets made to update.
426 // In this case, the root node of the 64 KiB subtree would be the root node
427 // of the whole tree, and it would need to be ROOT finalized. We can't
428 // compress it until we know.
429 // 2) This 64 KiB input might complete a larger tree, whose root node is
430 // similarly going to be the the root of the whole tree. For example, maybe
431 // we have 196 KiB (that is, 128 + 64) hashed so far. We can't compress the
432 // node at the root of the 256 KiB subtree until we know how to finalize it.
433 //
434 // The second problem is solved with "lazy merging". That is, when we're about
435 // to add a CV to the stack, we don't merge it with anything first, as the
436 // reference impl does. Instead we do merges using the *previous* CV that was
437 // added, which is sitting on top of the stack, and we put the new CV
438 // (unmerged) on top of the stack afterwards. This guarantees that we never
439 // merge the root node until finalize().
440 //
441 // Solving the first problem requires an additional tool,
442 // compress_subtree_to_parent_node(). That function always returns the top
443 // *two* chaining values of the subtree it's compressing. We then do lazy
444 // merging with each of them separately, so that the second CV will always
445 // remain unmerged. (That also helps us support extendable output when we're
446 // hashing an input all-at-once.)
hasher_push_cv(blake3_hasher * self,uint8_t new_cv[BLAKE3_OUT_LEN],uint64_t chunk_counter)447 INLINE void hasher_push_cv(blake3_hasher *self, uint8_t new_cv[BLAKE3_OUT_LEN],
448 uint64_t chunk_counter) {
449 hasher_merge_cv_stack(self, chunk_counter);
450 memcpy(&self->cv_stack[self->cv_stack_len * BLAKE3_OUT_LEN], new_cv,
451 BLAKE3_OUT_LEN);
452 self->cv_stack_len += 1;
453 }
454
blake3_hasher_update(blake3_hasher * self,const void * input,size_t input_len)455 void blake3_hasher_update(blake3_hasher *self, const void *input,
456 size_t input_len) {
457 // Explicitly checking for zero avoids causing UB by passing a null pointer
458 // to memcpy. This comes up in practice with things like:
459 // std::vector<uint8_t> v;
460 // blake3_hasher_update(&hasher, v.data(), v.size());
461 if (input_len == 0) {
462 return;
463 }
464
465 const uint8_t *input_bytes = (const uint8_t *)input;
466
467 // If we have some partial chunk bytes in the internal chunk_state, we need
468 // to finish that chunk first.
469 if (chunk_state_len(&self->chunk) > 0) {
470 size_t take = BLAKE3_CHUNK_LEN - chunk_state_len(&self->chunk);
471 if (take > input_len) {
472 take = input_len;
473 }
474 chunk_state_update(&self->chunk, input_bytes, take);
475 input_bytes += take;
476 input_len -= take;
477 // If we've filled the current chunk and there's more coming, finalize this
478 // chunk and proceed. In this case we know it's not the root.
479 if (input_len > 0) {
480 output_t output = chunk_state_output(&self->chunk);
481 uint8_t chunk_cv[32];
482 output_chaining_value(&output, chunk_cv);
483 hasher_push_cv(self, chunk_cv, self->chunk.chunk_counter);
484 chunk_state_reset(&self->chunk, self->key, self->chunk.chunk_counter + 1);
485 } else {
486 return;
487 }
488 }
489
490 // Now the chunk_state is clear, and we have more input. If there's more than
491 // a single chunk (so, definitely not the root chunk), hash the largest whole
492 // subtree we can, with the full benefits of SIMD (and maybe in the future,
493 // multi-threading) parallelism. Two restrictions:
494 // - The subtree has to be a power-of-2 number of chunks. Only subtrees along
495 // the right edge can be incomplete, and we don't know where the right edge
496 // is going to be until we get to finalize().
497 // - The subtree must evenly divide the total number of chunks up until this
498 // point (if total is not 0). If the current incomplete subtree is only
499 // waiting for 1 more chunk, we can't hash a subtree of 4 chunks. We have
500 // to complete the current subtree first.
501 // Because we might need to break up the input to form powers of 2, or to
502 // evenly divide what we already have, this part runs in a loop.
503 while (input_len > BLAKE3_CHUNK_LEN) {
504 size_t subtree_len = round_down_to_power_of_2(input_len);
505 uint64_t count_so_far = self->chunk.chunk_counter * BLAKE3_CHUNK_LEN;
506 // Shrink the subtree_len until it evenly divides the count so far. We know
507 // that subtree_len itself is a power of 2, so we can use a bitmasking
508 // trick instead of an actual remainder operation. (Note that if the caller
509 // consistently passes power-of-2 inputs of the same size, as is hopefully
510 // typical, this loop condition will always fail, and subtree_len will
511 // always be the full length of the input.)
512 //
513 // An aside: We don't have to shrink subtree_len quite this much. For
514 // example, if count_so_far is 1, we could pass 2 chunks to
515 // compress_subtree_to_parent_node. Since we'll get 2 CVs back, we'll still
516 // get the right answer in the end, and we might get to use 2-way SIMD
517 // parallelism. The problem with this optimization, is that it gets us
518 // stuck always hashing 2 chunks. The total number of chunks will remain
519 // odd, and we'll never graduate to higher degrees of parallelism. See
520 // https://github.com/BLAKE3-team/BLAKE3/issues/69.
521 while ((((uint64_t)(subtree_len - 1)) & count_so_far) != 0) {
522 subtree_len /= 2;
523 }
524 // The shrunken subtree_len might now be 1 chunk long. If so, hash that one
525 // chunk by itself. Otherwise, compress the subtree into a pair of CVs.
526 uint64_t subtree_chunks = subtree_len / BLAKE3_CHUNK_LEN;
527 if (subtree_len <= BLAKE3_CHUNK_LEN) {
528 blake3_chunk_state chunk_state;
529 chunk_state_init(&chunk_state, self->key, self->chunk.flags);
530 chunk_state.chunk_counter = self->chunk.chunk_counter;
531 chunk_state_update(&chunk_state, input_bytes, subtree_len);
532 output_t output = chunk_state_output(&chunk_state);
533 uint8_t cv[BLAKE3_OUT_LEN];
534 output_chaining_value(&output, cv);
535 hasher_push_cv(self, cv, chunk_state.chunk_counter);
536 } else {
537 // This is the high-performance happy path, though getting here depends
538 // on the caller giving us a long enough input.
539 uint8_t cv_pair[2 * BLAKE3_OUT_LEN];
540 compress_subtree_to_parent_node(input_bytes, subtree_len, self->key,
541 self->chunk.chunk_counter,
542 self->chunk.flags, cv_pair);
543 hasher_push_cv(self, cv_pair, self->chunk.chunk_counter);
544 hasher_push_cv(self, &cv_pair[BLAKE3_OUT_LEN],
545 self->chunk.chunk_counter + (subtree_chunks / 2));
546 }
547 self->chunk.chunk_counter += subtree_chunks;
548 input_bytes += subtree_len;
549 input_len -= subtree_len;
550 }
551
552 // If there's any remaining input less than a full chunk, add it to the chunk
553 // state. In that case, also do a final merge loop to make sure the subtree
554 // stack doesn't contain any unmerged pairs. The remaining input means we
555 // know these merges are non-root. This merge loop isn't strictly necessary
556 // here, because hasher_push_chunk_cv already does its own merge loop, but it
557 // simplifies blake3_hasher_finalize below.
558 if (input_len > 0) {
559 chunk_state_update(&self->chunk, input_bytes, input_len);
560 hasher_merge_cv_stack(self, self->chunk.chunk_counter);
561 }
562 }
563
blake3_hasher_finalize(const blake3_hasher * self,uint8_t * out,size_t out_len)564 void blake3_hasher_finalize(const blake3_hasher *self, uint8_t *out,
565 size_t out_len) {
566 blake3_hasher_finalize_seek(self, 0, out, out_len);
567 }
568
blake3_hasher_finalize_seek(const blake3_hasher * self,uint64_t seek,uint8_t * out,size_t out_len)569 void blake3_hasher_finalize_seek(const blake3_hasher *self, uint64_t seek,
570 uint8_t *out, size_t out_len) {
571 // Explicitly checking for zero avoids causing UB by passing a null pointer
572 // to memcpy. This comes up in practice with things like:
573 // std::vector<uint8_t> v;
574 // blake3_hasher_finalize(&hasher, v.data(), v.size());
575 if (out_len == 0) {
576 return;
577 }
578
579 // If the subtree stack is empty, then the current chunk is the root.
580 if (self->cv_stack_len == 0) {
581 output_t output = chunk_state_output(&self->chunk);
582 output_root_bytes(&output, seek, out, out_len);
583 return;
584 }
585 // If there are any bytes in the chunk state, finalize that chunk and do a
586 // roll-up merge between that chunk hash and every subtree in the stack. In
587 // this case, the extra merge loop at the end of blake3_hasher_update
588 // guarantees that none of the subtrees in the stack need to be merged with
589 // each other first. Otherwise, if there are no bytes in the chunk state,
590 // then the top of the stack is a chunk hash, and we start the merge from
591 // that.
592 output_t output;
593 size_t cvs_remaining;
594 if (chunk_state_len(&self->chunk) > 0) {
595 cvs_remaining = self->cv_stack_len;
596 output = chunk_state_output(&self->chunk);
597 } else {
598 // There are always at least 2 CVs in the stack in this case.
599 cvs_remaining = self->cv_stack_len - 2;
600 output = parent_output(&self->cv_stack[cvs_remaining * 32], self->key,
601 self->chunk.flags);
602 }
603 while (cvs_remaining > 0) {
604 cvs_remaining -= 1;
605 uint8_t parent_block[BLAKE3_BLOCK_LEN];
606 memcpy(parent_block, &self->cv_stack[cvs_remaining * 32], 32);
607 output_chaining_value(&output, &parent_block[32]);
608 output = parent_output(parent_block, self->key, self->chunk.flags);
609 }
610 output_root_bytes(&output, seek, out, out_len);
611 }
612
blake3_hasher_reset(blake3_hasher * self)613 void blake3_hasher_reset(blake3_hasher *self) {
614 chunk_state_reset(&self->chunk, self->key, 0);
615 self->cv_stack_len = 0;
616 }
617