port compress_subtree_to_parent_node from Rust to C

This recursive function performs parallel parent node hashing, which is
an important optimization.

1 files changed, 6 insertions, 1 deletions

diff --git a/c/blake3.h b/c/blake3.h
index c16747d..43e6522 100644
--- a/c/blake3.h
+++ b/c/blake3.h
@@ -23,7 +23,12 @@ typedef struct {
   uint32_t key[8];
   blake3_chunk_state chunk;
   uint8_t cv_stack_len;
-  uint8_t cv_stack[BLAKE3_MAX_DEPTH * BLAKE3_OUT_LEN];
+  // The stack size is MAX_DEPTH + 1 because we do lazy merging. For example,
+  // with 7 chunks, we have 3 entries in the stack. Adding an 8th chunk
+  // requires a 4th entry, rather than merging everything down to 1, because we
+  // don't know whether more input is coming. This is different from how the
+  // reference implementation does things.
+  uint8_t cv_stack[(BLAKE3_MAX_DEPTH + 1) * BLAKE3_OUT_LEN];
 } blake3_hasher;
 
 void blake3_hasher_init(blake3_hasher *self);