662 lines · c
1/*===-- blake3.c - BLAKE3 C Implementation ------------------------*- C -*-===*\2|* *|3|* Released into the public domain with CC0 1.0 *|4|* See 'llvm/lib/Support/BLAKE3/LICENSE' for info. *|5|* SPDX-License-Identifier: CC0-1.0 *|6|* *|7\*===----------------------------------------------------------------------===*/8 9#include <assert.h>10#include <stdbool.h>11#include <string.h>12 13#include "blake3_impl.h"14 15const char *llvm_blake3_version(void) { return BLAKE3_VERSION_STRING; }16 17INLINE void chunk_state_init(blake3_chunk_state *self, const uint32_t key[8],18 uint8_t flags) {19 memcpy(self->cv, key, BLAKE3_KEY_LEN);20 self->chunk_counter = 0;21 memset(self->buf, 0, BLAKE3_BLOCK_LEN);22 self->buf_len = 0;23 self->blocks_compressed = 0;24 self->flags = flags;25}26 27INLINE void chunk_state_reset(blake3_chunk_state *self, const uint32_t key[8],28 uint64_t chunk_counter) {29 memcpy(self->cv, key, BLAKE3_KEY_LEN);30 self->chunk_counter = chunk_counter;31 self->blocks_compressed = 0;32 memset(self->buf, 0, BLAKE3_BLOCK_LEN);33 self->buf_len = 0;34}35 36INLINE size_t chunk_state_len(const blake3_chunk_state *self) {37 return (BLAKE3_BLOCK_LEN * (size_t)self->blocks_compressed) +38 ((size_t)self->buf_len);39}40 41INLINE size_t chunk_state_fill_buf(blake3_chunk_state *self,42 const uint8_t *input, size_t input_len) {43 size_t take = BLAKE3_BLOCK_LEN - ((size_t)self->buf_len);44 if (take > input_len) {45 take = input_len;46 }47 uint8_t *dest = self->buf + ((size_t)self->buf_len);48 memcpy(dest, input, take);49 self->buf_len += (uint8_t)take;50 return take;51}52 53INLINE uint8_t chunk_state_maybe_start_flag(const blake3_chunk_state *self) {54 if (self->blocks_compressed == 0) {55 return CHUNK_START;56 } else {57 return 0;58 }59}60 61typedef struct {62 uint32_t input_cv[8];63 uint64_t counter;64 uint8_t block[BLAKE3_BLOCK_LEN];65 uint8_t block_len;66 uint8_t flags;67} output_t;68 69INLINE output_t make_output(const uint32_t input_cv[8],70 const uint8_t block[BLAKE3_BLOCK_LEN],71 uint8_t block_len, uint64_t counter,72 uint8_t flags) {73 output_t ret;74 memcpy(ret.input_cv, input_cv, 32);75 memcpy(ret.block, block, BLAKE3_BLOCK_LEN);76 ret.block_len = block_len;77 ret.counter = counter;78 ret.flags = flags;79 return ret;80}81 82// Chaining values within a given chunk (specifically the compress_in_place83// interface) are represented as words. This avoids unnecessary bytes<->words84// conversion overhead in the portable implementation. However, the hash_many85// interface handles both user input and parent node blocks, so it accepts86// bytes. For that reason, chaining values in the CV stack are represented as87// bytes.88INLINE void output_chaining_value(const output_t *self, uint8_t cv[32]) {89 uint32_t cv_words[8];90 memcpy(cv_words, self->input_cv, 32);91 blake3_compress_in_place(cv_words, self->block, self->block_len,92 self->counter, self->flags);93 store_cv_words(cv, cv_words);94}95 96INLINE void output_root_bytes(const output_t *self, uint64_t seek, uint8_t *out,97 size_t out_len) {98 if (out_len == 0) {99 return;100 }101 uint64_t output_block_counter = seek / 64;102 size_t offset_within_block = seek % 64;103 uint8_t wide_buf[64];104 if(offset_within_block) {105 blake3_compress_xof(self->input_cv, self->block, self->block_len, output_block_counter, self->flags | ROOT, wide_buf);106 const size_t available_bytes = 64 - offset_within_block;107 const size_t bytes = out_len > available_bytes ? available_bytes : out_len;108 memcpy(out, wide_buf + offset_within_block, bytes);109 out += bytes;110 out_len -= bytes;111 output_block_counter += 1;112 }113 if(out_len / 64) {114 blake3_xof_many(self->input_cv, self->block, self->block_len, output_block_counter, self->flags | ROOT, out, out_len / 64);115 }116 output_block_counter += out_len / 64;117 out += out_len & -64;118 out_len -= out_len & -64;119 if(out_len) {120 blake3_compress_xof(self->input_cv, self->block, self->block_len, output_block_counter, self->flags | ROOT, wide_buf);121 memcpy(out, wide_buf, out_len);122 }123}124 125INLINE void chunk_state_update(blake3_chunk_state *self, const uint8_t *input,126 size_t input_len) {127 if (self->buf_len > 0) {128 size_t take = chunk_state_fill_buf(self, input, input_len);129 input += take;130 input_len -= take;131 if (input_len > 0) {132 blake3_compress_in_place(133 self->cv, self->buf, BLAKE3_BLOCK_LEN, self->chunk_counter,134 self->flags | chunk_state_maybe_start_flag(self));135 self->blocks_compressed += 1;136 self->buf_len = 0;137 memset(self->buf, 0, BLAKE3_BLOCK_LEN);138 }139 }140 141 while (input_len > BLAKE3_BLOCK_LEN) {142 blake3_compress_in_place(self->cv, input, BLAKE3_BLOCK_LEN,143 self->chunk_counter,144 self->flags | chunk_state_maybe_start_flag(self));145 self->blocks_compressed += 1;146 input += BLAKE3_BLOCK_LEN;147 input_len -= BLAKE3_BLOCK_LEN;148 }149 150 chunk_state_fill_buf(self, input, input_len);151}152 153INLINE output_t chunk_state_output(const blake3_chunk_state *self) {154 uint8_t block_flags =155 self->flags | chunk_state_maybe_start_flag(self) | CHUNK_END;156 return make_output(self->cv, self->buf, self->buf_len, self->chunk_counter,157 block_flags);158}159 160INLINE output_t parent_output(const uint8_t block[BLAKE3_BLOCK_LEN],161 const uint32_t key[8], uint8_t flags) {162 return make_output(key, block, BLAKE3_BLOCK_LEN, 0, flags | PARENT);163}164 165// Given some input larger than one chunk, return the number of bytes that166// should go in the left subtree. This is the largest power-of-2 number of167// chunks that leaves at least 1 byte for the right subtree.168INLINE size_t left_subtree_len(size_t input_len) {169 // Subtract 1 to reserve at least one byte for the right side. input_len170 // should always be greater than BLAKE3_CHUNK_LEN.171 size_t full_chunks = (input_len - 1) / BLAKE3_CHUNK_LEN;172 return round_down_to_power_of_2(full_chunks) * BLAKE3_CHUNK_LEN;173}174 175// Use SIMD parallelism to hash up to MAX_SIMD_DEGREE chunks at the same time176// on a single thread. Write out the chunk chaining values and return the177// number of chunks hashed. These chunks are never the root and never empty;178// those cases use a different codepath.179INLINE size_t compress_chunks_parallel(const uint8_t *input, size_t input_len,180 const uint32_t key[8],181 uint64_t chunk_counter, uint8_t flags,182 uint8_t *out) {183#if defined(BLAKE3_TESTING)184 assert(0 < input_len);185 assert(input_len <= MAX_SIMD_DEGREE * BLAKE3_CHUNK_LEN);186#endif187 188 const uint8_t *chunks_array[MAX_SIMD_DEGREE];189 size_t input_position = 0;190 size_t chunks_array_len = 0;191 while (input_len - input_position >= BLAKE3_CHUNK_LEN) {192 chunks_array[chunks_array_len] = &input[input_position];193 input_position += BLAKE3_CHUNK_LEN;194 chunks_array_len += 1;195 }196 197 blake3_hash_many(chunks_array, chunks_array_len,198 BLAKE3_CHUNK_LEN / BLAKE3_BLOCK_LEN, key, chunk_counter,199 true, flags, CHUNK_START, CHUNK_END, out);200 201 // Hash the remaining partial chunk, if there is one. Note that the empty202 // chunk (meaning the empty message) is a different codepath.203 if (input_len > input_position) {204 uint64_t counter = chunk_counter + (uint64_t)chunks_array_len;205 blake3_chunk_state chunk_state;206 chunk_state_init(&chunk_state, key, flags);207 chunk_state.chunk_counter = counter;208 chunk_state_update(&chunk_state, &input[input_position],209 input_len - input_position);210 output_t output = chunk_state_output(&chunk_state);211 output_chaining_value(&output, &out[chunks_array_len * BLAKE3_OUT_LEN]);212 return chunks_array_len + 1;213 } else {214 return chunks_array_len;215 }216}217 218// Use SIMD parallelism to hash up to MAX_SIMD_DEGREE parents at the same time219// on a single thread. Write out the parent chaining values and return the220// number of parents hashed. (If there's an odd input chaining value left over,221// return it as an additional output.) These parents are never the root and222// never empty; those cases use a different codepath.223INLINE size_t compress_parents_parallel(const uint8_t *child_chaining_values,224 size_t num_chaining_values,225 const uint32_t key[8], uint8_t flags,226 uint8_t *out) {227#if defined(BLAKE3_TESTING)228 assert(2 <= num_chaining_values);229 assert(num_chaining_values <= 2 * MAX_SIMD_DEGREE_OR_2);230#endif231 232 const uint8_t *parents_array[MAX_SIMD_DEGREE_OR_2];233 size_t parents_array_len = 0;234 while (num_chaining_values - (2 * parents_array_len) >= 2) {235 parents_array[parents_array_len] =236 &child_chaining_values[2 * parents_array_len * BLAKE3_OUT_LEN];237 parents_array_len += 1;238 }239 240 blake3_hash_many(parents_array, parents_array_len, 1, key,241 0, // Parents always use counter 0.242 false, flags | PARENT,243 0, // Parents have no start flags.244 0, // Parents have no end flags.245 out);246 247 // If there's an odd child left over, it becomes an output.248 if (num_chaining_values > 2 * parents_array_len) {249 memcpy(&out[parents_array_len * BLAKE3_OUT_LEN],250 &child_chaining_values[2 * parents_array_len * BLAKE3_OUT_LEN],251 BLAKE3_OUT_LEN);252 return parents_array_len + 1;253 } else {254 return parents_array_len;255 }256}257 258// The wide helper function returns (writes out) an array of chaining values259// and returns the length of that array. The number of chaining values returned260// is the dynamically detected SIMD degree, at most MAX_SIMD_DEGREE. Or fewer,261// if the input is shorter than that many chunks. The reason for maintaining a262// wide array of chaining values going back up the tree, is to allow the263// implementation to hash as many parents in parallel as possible.264//265// As a special case when the SIMD degree is 1, this function will still return266// at least 2 outputs. This guarantees that this function doesn't perform the267// root compression. (If it did, it would use the wrong flags, and also we268// wouldn't be able to implement extendable output.) Note that this function is269// not used when the whole input is only 1 chunk long; that's a different270// codepath.271//272// Why not just have the caller split the input on the first update(), instead273// of implementing this special rule? Because we don't want to limit SIMD or274// multi-threading parallelism for that update().275size_t blake3_compress_subtree_wide(const uint8_t *input, size_t input_len,276 const uint32_t key[8],277 uint64_t chunk_counter, uint8_t flags,278 uint8_t *out, bool use_tbb) {279 // Note that the single chunk case does *not* bump the SIMD degree up to 2280 // when it is 1. If this implementation adds multi-threading in the future,281 // this gives us the option of multi-threading even the 2-chunk case, which282 // can help performance on smaller platforms.283 if (input_len <= blake3_simd_degree() * BLAKE3_CHUNK_LEN) {284 return compress_chunks_parallel(input, input_len, key, chunk_counter, flags,285 out);286 }287 288 // With more than simd_degree chunks, we need to recurse. Start by dividing289 // the input into left and right subtrees. (Note that this is only optimal290 // as long as the SIMD degree is a power of 2. If we ever get a SIMD degree291 // of 3 or something, we'll need a more complicated strategy.)292 size_t left_input_len = left_subtree_len(input_len);293 size_t right_input_len = input_len - left_input_len;294 const uint8_t *right_input = &input[left_input_len];295 uint64_t right_chunk_counter =296 chunk_counter + (uint64_t)(left_input_len / BLAKE3_CHUNK_LEN);297 298 // Make space for the child outputs. Here we use MAX_SIMD_DEGREE_OR_2 to299 // account for the special case of returning 2 outputs when the SIMD degree300 // is 1.301 uint8_t cv_array[2 * MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN];302 size_t degree = blake3_simd_degree();303 if (left_input_len > BLAKE3_CHUNK_LEN && degree == 1) {304 // The special case: We always use a degree of at least two, to make305 // sure there are two outputs. Except, as noted above, at the chunk306 // level, where we allow degree=1. (Note that the 1-chunk-input case is307 // a different codepath.)308 degree = 2;309 }310 uint8_t *right_cvs = &cv_array[degree * BLAKE3_OUT_LEN];311 312 // Recurse!313 size_t left_n = -1;314 size_t right_n = -1;315 316#if defined(BLAKE3_USE_TBB)317 blake3_compress_subtree_wide_join_tbb(318 key, flags, use_tbb,319 // left-hand side320 input, left_input_len, chunk_counter, cv_array, &left_n,321 // right-hand side322 right_input, right_input_len, right_chunk_counter, right_cvs, &right_n);323#else324 left_n = blake3_compress_subtree_wide(325 input, left_input_len, key, chunk_counter, flags, cv_array, use_tbb);326 right_n = blake3_compress_subtree_wide(right_input, right_input_len, key,327 right_chunk_counter, flags, right_cvs,328 use_tbb);329#endif // BLAKE3_USE_TBB330 331 // The special case again. If simd_degree=1, then we'll have left_n=1 and332 // right_n=1. Rather than compressing them into a single output, return333 // them directly, to make sure we always have at least two outputs.334 if (left_n == 1) {335 memcpy(out, cv_array, 2 * BLAKE3_OUT_LEN);336 return 2;337 }338 339 // Otherwise, do one layer of parent node compression.340 size_t num_chaining_values = left_n + right_n;341 return compress_parents_parallel(cv_array, num_chaining_values, key, flags,342 out);343}344 345// Hash a subtree with compress_subtree_wide(), and then condense the resulting346// list of chaining values down to a single parent node. Don't compress that347// last parent node, however. Instead, return its message bytes (the348// concatenated chaining values of its children). This is necessary when the349// first call to update() supplies a complete subtree, because the topmost350// parent node of that subtree could end up being the root. It's also necessary351// for extended output in the general case.352//353// As with compress_subtree_wide(), this function is not used on inputs of 1354// chunk or less. That's a different codepath.355INLINE void356compress_subtree_to_parent_node(const uint8_t *input, size_t input_len,357 const uint32_t key[8], uint64_t chunk_counter,358 uint8_t flags, uint8_t out[2 * BLAKE3_OUT_LEN],359 bool use_tbb) {360#if defined(BLAKE3_TESTING)361 assert(input_len > BLAKE3_CHUNK_LEN);362#endif363 364 uint8_t cv_array[MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN];365 size_t num_cvs = blake3_compress_subtree_wide(input, input_len, key,366 chunk_counter, flags, cv_array, use_tbb);367 assert(num_cvs <= MAX_SIMD_DEGREE_OR_2);368 // The following loop never executes when MAX_SIMD_DEGREE_OR_2 is 2, because369 // as we just asserted, num_cvs will always be <=2 in that case. But GCC370 // (particularly GCC 8.5) can't tell that it never executes, and if NDEBUG is371 // set then it emits incorrect warnings here. We tried a few different372 // hacks to silence these, but in the end our hacks just produced different373 // warnings (see https://github.com/BLAKE3-team/BLAKE3/pull/380). Out of374 // desperation, we ifdef out this entire loop when we know it's not needed.375#if MAX_SIMD_DEGREE_OR_2 > 2376 // If MAX_SIMD_DEGREE_OR_2 is greater than 2 and there's enough input,377 // compress_subtree_wide() returns more than 2 chaining values. Condense378 // them into 2 by forming parent nodes repeatedly.379 uint8_t out_array[MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN / 2];380 while (num_cvs > 2) {381 num_cvs =382 compress_parents_parallel(cv_array, num_cvs, key, flags, out_array);383 memcpy(cv_array, out_array, num_cvs * BLAKE3_OUT_LEN);384 }385#endif386 memcpy(out, cv_array, 2 * BLAKE3_OUT_LEN);387}388 389INLINE void hasher_init_base(blake3_hasher *self, const uint32_t key[8],390 uint8_t flags) {391 memcpy(self->key, key, BLAKE3_KEY_LEN);392 chunk_state_init(&self->chunk, key, flags);393 self->cv_stack_len = 0;394}395 396void llvm_blake3_hasher_init(blake3_hasher *self) { hasher_init_base(self, IV, 0); }397 398void llvm_blake3_hasher_init_keyed(blake3_hasher *self,399 const uint8_t key[BLAKE3_KEY_LEN]) {400 uint32_t key_words[8];401 load_key_words(key, key_words);402 hasher_init_base(self, key_words, KEYED_HASH);403}404 405void llvm_blake3_hasher_init_derive_key_raw(blake3_hasher *self, const void *context,406 size_t context_len) {407 blake3_hasher context_hasher;408 hasher_init_base(&context_hasher, IV, DERIVE_KEY_CONTEXT);409 llvm_blake3_hasher_update(&context_hasher, context, context_len);410 uint8_t context_key[BLAKE3_KEY_LEN];411 llvm_blake3_hasher_finalize(&context_hasher, context_key, BLAKE3_KEY_LEN);412 uint32_t context_key_words[8];413 load_key_words(context_key, context_key_words);414 hasher_init_base(self, context_key_words, DERIVE_KEY_MATERIAL);415}416 417void llvm_blake3_hasher_init_derive_key(blake3_hasher *self, const char *context) {418 llvm_blake3_hasher_init_derive_key_raw(self, context, strlen(context));419}420 421// As described in hasher_push_cv() below, we do "lazy merging", delaying422// merges until right before the next CV is about to be added. This is423// different from the reference implementation. Another difference is that we424// aren't always merging 1 chunk at a time. Instead, each CV might represent425// any power-of-two number of chunks, as long as the smaller-above-larger stack426// order is maintained. Instead of the "count the trailing 0-bits" algorithm427// described in the spec, we use a "count the total number of 1-bits" variant428// that doesn't require us to retain the subtree size of the CV on top of the429// stack. The principle is the same: each CV that should remain in the stack is430// represented by a 1-bit in the total number of chunks (or bytes) so far.431INLINE void hasher_merge_cv_stack(blake3_hasher *self, uint64_t total_len) {432 size_t post_merge_stack_len = (size_t)popcnt(total_len);433 while (self->cv_stack_len > post_merge_stack_len) {434 uint8_t *parent_node =435 &self->cv_stack[(self->cv_stack_len - 2) * BLAKE3_OUT_LEN];436 output_t output = parent_output(parent_node, self->key, self->chunk.flags);437 output_chaining_value(&output, parent_node);438 self->cv_stack_len -= 1;439 }440}441 442// In reference_impl.rs, we merge the new CV with existing CVs from the stack443// before pushing it. We can do that because we know more input is coming, so444// we know none of the merges are root.445//446// This setting is different. We want to feed as much input as possible to447// compress_subtree_wide(), without setting aside anything for the chunk_state.448// If the user gives us 64 KiB, we want to parallelize over all 64 KiB at once449// as a single subtree, if at all possible.450//451// This leads to two problems:452// 1) This 64 KiB input might be the only call that ever gets made to update.453// In this case, the root node of the 64 KiB subtree would be the root node454// of the whole tree, and it would need to be ROOT finalized. We can't455// compress it until we know.456// 2) This 64 KiB input might complete a larger tree, whose root node is457// similarly going to be the root of the whole tree. For example, maybe458// we have 196 KiB (that is, 128 + 64) hashed so far. We can't compress the459// node at the root of the 256 KiB subtree until we know how to finalize it.460//461// The second problem is solved with "lazy merging". That is, when we're about462// to add a CV to the stack, we don't merge it with anything first, as the463// reference impl does. Instead we do merges using the *previous* CV that was464// added, which is sitting on top of the stack, and we put the new CV465// (unmerged) on top of the stack afterwards. This guarantees that we never466// merge the root node until finalize().467//468// Solving the first problem requires an additional tool,469// compress_subtree_to_parent_node(). That function always returns the top470// *two* chaining values of the subtree it's compressing. We then do lazy471// merging with each of them separately, so that the second CV will always472// remain unmerged. (That also helps us support extendable output when we're473// hashing an input all-at-once.)474INLINE void hasher_push_cv(blake3_hasher *self, uint8_t new_cv[BLAKE3_OUT_LEN],475 uint64_t chunk_counter) {476 hasher_merge_cv_stack(self, chunk_counter);477 memcpy(&self->cv_stack[self->cv_stack_len * BLAKE3_OUT_LEN], new_cv,478 BLAKE3_OUT_LEN);479 self->cv_stack_len += 1;480}481 482INLINE void blake3_hasher_update_base(blake3_hasher *self, const void *input,483 size_t input_len, bool use_tbb) {484 // Explicitly checking for zero avoids causing UB by passing a null pointer485 // to memcpy. This comes up in practice with things like:486 // std::vector<uint8_t> v;487 // blake3_hasher_update(&hasher, v.data(), v.size());488 if (input_len == 0) {489 return;490 }491 492 const uint8_t *input_bytes = (const uint8_t *)input;493 494 // If we have some partial chunk bytes in the internal chunk_state, we need495 // to finish that chunk first.496 if (chunk_state_len(&self->chunk) > 0) {497 size_t take = BLAKE3_CHUNK_LEN - chunk_state_len(&self->chunk);498 if (take > input_len) {499 take = input_len;500 }501 chunk_state_update(&self->chunk, input_bytes, take);502 input_bytes += take;503 input_len -= take;504 // If we've filled the current chunk and there's more coming, finalize this505 // chunk and proceed. In this case we know it's not the root.506 if (input_len > 0) {507 output_t output = chunk_state_output(&self->chunk);508 uint8_t chunk_cv[32];509 output_chaining_value(&output, chunk_cv);510 hasher_push_cv(self, chunk_cv, self->chunk.chunk_counter);511 chunk_state_reset(&self->chunk, self->key, self->chunk.chunk_counter + 1);512 } else {513 return;514 }515 }516 517 // Now the chunk_state is clear, and we have more input. If there's more than518 // a single chunk (so, definitely not the root chunk), hash the largest whole519 // subtree we can, with the full benefits of SIMD (and maybe in the future,520 // multi-threading) parallelism. Two restrictions:521 // - The subtree has to be a power-of-2 number of chunks. Only subtrees along522 // the right edge can be incomplete, and we don't know where the right edge523 // is going to be until we get to finalize().524 // - The subtree must evenly divide the total number of chunks up until this525 // point (if total is not 0). If the current incomplete subtree is only526 // waiting for 1 more chunk, we can't hash a subtree of 4 chunks. We have527 // to complete the current subtree first.528 // Because we might need to break up the input to form powers of 2, or to529 // evenly divide what we already have, this part runs in a loop.530 while (input_len > BLAKE3_CHUNK_LEN) {531 size_t subtree_len = round_down_to_power_of_2(input_len);532 uint64_t count_so_far = self->chunk.chunk_counter * BLAKE3_CHUNK_LEN;533 // Shrink the subtree_len until it evenly divides the count so far. We know534 // that subtree_len itself is a power of 2, so we can use a bitmasking535 // trick instead of an actual remainder operation. (Note that if the caller536 // consistently passes power-of-2 inputs of the same size, as is hopefully537 // typical, this loop condition will always fail, and subtree_len will538 // always be the full length of the input.)539 //540 // An aside: We don't have to shrink subtree_len quite this much. For541 // example, if count_so_far is 1, we could pass 2 chunks to542 // compress_subtree_to_parent_node. Since we'll get 2 CVs back, we'll still543 // get the right answer in the end, and we might get to use 2-way SIMD544 // parallelism. The problem with this optimization, is that it gets us545 // stuck always hashing 2 chunks. The total number of chunks will remain546 // odd, and we'll never graduate to higher degrees of parallelism. See547 // https://github.com/BLAKE3-team/BLAKE3/issues/69.548 while ((((uint64_t)(subtree_len - 1)) & count_so_far) != 0) {549 subtree_len /= 2;550 }551 // The shrunken subtree_len might now be 1 chunk long. If so, hash that one552 // chunk by itself. Otherwise, compress the subtree into a pair of CVs.553 uint64_t subtree_chunks = subtree_len / BLAKE3_CHUNK_LEN;554 if (subtree_len <= BLAKE3_CHUNK_LEN) {555 blake3_chunk_state chunk_state;556 chunk_state_init(&chunk_state, self->key, self->chunk.flags);557 chunk_state.chunk_counter = self->chunk.chunk_counter;558 chunk_state_update(&chunk_state, input_bytes, subtree_len);559 output_t output = chunk_state_output(&chunk_state);560 uint8_t cv[BLAKE3_OUT_LEN];561 output_chaining_value(&output, cv);562 hasher_push_cv(self, cv, chunk_state.chunk_counter);563 } else {564 // This is the high-performance happy path, though getting here depends565 // on the caller giving us a long enough input.566 uint8_t cv_pair[2 * BLAKE3_OUT_LEN];567 compress_subtree_to_parent_node(input_bytes, subtree_len, self->key,568 self->chunk.chunk_counter,569 self->chunk.flags, cv_pair, use_tbb);570 hasher_push_cv(self, cv_pair, self->chunk.chunk_counter);571 hasher_push_cv(self, &cv_pair[BLAKE3_OUT_LEN],572 self->chunk.chunk_counter + (subtree_chunks / 2));573 }574 self->chunk.chunk_counter += subtree_chunks;575 input_bytes += subtree_len;576 input_len -= subtree_len;577 }578 579 // If there's any remaining input less than a full chunk, add it to the chunk580 // state. In that case, also do a final merge loop to make sure the subtree581 // stack doesn't contain any unmerged pairs. The remaining input means we582 // know these merges are non-root. This merge loop isn't strictly necessary583 // here, because hasher_push_chunk_cv already does its own merge loop, but it584 // simplifies blake3_hasher_finalize below.585 if (input_len > 0) {586 chunk_state_update(&self->chunk, input_bytes, input_len);587 hasher_merge_cv_stack(self, self->chunk.chunk_counter);588 }589}590 591void llvm_blake3_hasher_update(blake3_hasher *self, const void *input,592 size_t input_len) {593 bool use_tbb = false;594 blake3_hasher_update_base(self, input, input_len, use_tbb);595}596 597#if defined(BLAKE3_USE_TBB)598void blake3_hasher_update_tbb(blake3_hasher *self, const void *input,599 size_t input_len) {600 bool use_tbb = true;601 blake3_hasher_update_base(self, input, input_len, use_tbb);602}603#endif // BLAKE3_USE_TBB604 605void llvm_blake3_hasher_finalize(const blake3_hasher *self, uint8_t *out,606 size_t out_len) {607 llvm_blake3_hasher_finalize_seek(self, 0, out, out_len);608#if LLVM_MEMORY_SANITIZER_BUILD609 // Avoid false positives due to uninstrumented assembly code.610 __msan_unpoison(out, out_len);611#endif612}613 614void llvm_blake3_hasher_finalize_seek(const blake3_hasher *self, uint64_t seek,615 uint8_t *out, size_t out_len) {616 // Explicitly checking for zero avoids causing UB by passing a null pointer617 // to memcpy. This comes up in practice with things like:618 // std::vector<uint8_t> v;619 // blake3_hasher_finalize(&hasher, v.data(), v.size());620 if (out_len == 0) {621 return;622 }623 624 // If the subtree stack is empty, then the current chunk is the root.625 if (self->cv_stack_len == 0) {626 output_t output = chunk_state_output(&self->chunk);627 output_root_bytes(&output, seek, out, out_len);628 return;629 }630 // If there are any bytes in the chunk state, finalize that chunk and do a631 // roll-up merge between that chunk hash and every subtree in the stack. In632 // this case, the extra merge loop at the end of blake3_hasher_update633 // guarantees that none of the subtrees in the stack need to be merged with634 // each other first. Otherwise, if there are no bytes in the chunk state,635 // then the top of the stack is a chunk hash, and we start the merge from636 // that.637 output_t output;638 size_t cvs_remaining;639 if (chunk_state_len(&self->chunk) > 0) {640 cvs_remaining = self->cv_stack_len;641 output = chunk_state_output(&self->chunk);642 } else {643 // There are always at least 2 CVs in the stack in this case.644 cvs_remaining = self->cv_stack_len - 2;645 output = parent_output(&self->cv_stack[cvs_remaining * 32], self->key,646 self->chunk.flags);647 }648 while (cvs_remaining > 0) {649 cvs_remaining -= 1;650 uint8_t parent_block[BLAKE3_BLOCK_LEN];651 memcpy(parent_block, &self->cv_stack[cvs_remaining * 32], 32);652 output_chaining_value(&output, &parent_block[32]);653 output = parent_output(parent_block, self->key, self->chunk.flags);654 }655 output_root_bytes(&output, seek, out, out_len);656}657 658void llvm_blake3_hasher_reset(blake3_hasher *self) {659 chunk_state_reset(&self->chunk, self->key, 0);660 self->cv_stack_len = 0;661}662