| 1 |
#include <assert.h> |
| 2 |
#include <stdbool.h> |
| 3 |
#include <string.h> |
| 4 |
|
| 5 |
#include "blake3.h" |
| 6 |
#include "blake3_impl.h" |
| 7 |
|
| 8 |
const char *blake3_version(void) { return BLAKE3_VERSION_STRING; } |
| 9 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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. |
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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. |
| 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. |
| 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. |
| 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(). |
| 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. |
| 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 |
|
| 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 |
|
| 369 |
void blake3_hasher_init(blake3_hasher *self) { hasher_init_base(self, IV, 0); } |
| 370 |
|
| 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 |
|
| 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 |
|
| 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. |
| 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.) |
| 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 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 613 |
void blake3_hasher_reset(blake3_hasher *self) { |
| 614 |
chunk_state_reset(&self->chunk, self->key, 0); |
| 615 |
self->cv_stack_len = 0; |
| 616 |
} |