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