{"header":{"message":"Initial import for blake3","description":null,"timestamp":"2022-08-19T10:31:47.731960639Z","authors":[{}]},"hash":"X36ICMJNYKJF35ZUEVCCR33JOZPCPZQ6KSGEQI3RZND2P5EDASLQC","authors":[{"login":"laumann","key":"AFgzZkD8ARgC21gkkCvxPV5HbL7YDVzgYEhbAxQG7UQY"}],"deps":{"hashes":[["X36ICMJNYKJF35ZUEVCCR33JOZPCPZQ6KSGEQI3RZND2P5EDASLQC","Initial import for blake3"],["AA",null],["3OHR6ZPHN53SVWJL4GUKKUC223IPXA73UPBFJCM4ENGS27AKHN6AC","make: prettify output"],["FB67XX5EGNF45JNAQISW7CBLSLS36F6JEUOBTTPUMVBMOVLGA3VQC","add argument parsing setup"],["3NA345CN3HKNUQOWTUMUTINQMFLYATWPO4H74J4AFGEUQKGQYBWQC","Add zstd_seekable + many headers"],["B3XLVPNC4COLLC3FUE34Y7HIKTMF6CJZUASZOU3YM2YGPZKJZP7QC","Add ani.c and initial Makefile"],["PEUS54XQ5KJQYAVUYBG5MWLEHIOVPMZ3ANVC7HPQP6JUWWPRDW5AC",""]],"deps":["3OHR6ZPHN53SVWJL4GUKKUC223IPXA73UPBFJCM4ENGS27AKHN6AC"],"known":["B3XLVPNC4COLLC3FUE34Y7HIKTMF6CJZUASZOU3YM2YGPZKJZP7QC","FB67XX5EGNF45JNAQISW7CBLSLS36F6JEUOBTTPUMVBMOVLGA3VQC","3NA345CN3HKNUQOWTUMUTINQMFLYATWPO4H74J4AFGEUQKGQYBWQC"]},"hunks":[{"FileAdd":{"meta":{"basename":"blake3_portable.c","metadata":0},"context":[{"change":7,"pos":1}],"contents":[{"Add":"#include \"blake3_impl.h\""},{"Add":"#include "},{"Add":""},{"Add":"INLINE uint32_t rotr32(uint32_t w, uint32_t c) {"},{"Add":" return (w >> c) | (w << (32 - c));"},{"Add":"}"},{"Add":""},{"Add":"INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d,"},{"Add":" uint32_t x, uint32_t y) {"},{"Add":" state[a] = state[a] + state[b] + x;"},{"Add":" state[d] = rotr32(state[d] ^ state[a], 16);"},{"Add":" state[c] = state[c] + state[d];"},{"Add":" state[b] = rotr32(state[b] ^ state[c], 12);"},{"Add":" state[a] = state[a] + state[b] + y;"},{"Add":" state[d] = rotr32(state[d] ^ state[a], 8);"},{"Add":" state[c] = state[c] + state[d];"},{"Add":" state[b] = rotr32(state[b] ^ state[c], 7);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void round_fn(uint32_t state[16], const uint32_t *msg, size_t round) {"},{"Add":" // Select the message schedule based on the round."},{"Add":" const uint8_t *schedule = MSG_SCHEDULE[round];"},{"Add":""},{"Add":" // Mix the columns."},{"Add":" g(state, 0, 4, 8, 12, msg[schedule[0]], msg[schedule[1]]);"},{"Add":" g(state, 1, 5, 9, 13, msg[schedule[2]], msg[schedule[3]]);"},{"Add":" g(state, 2, 6, 10, 14, msg[schedule[4]], msg[schedule[5]]);"},{"Add":" g(state, 3, 7, 11, 15, msg[schedule[6]], msg[schedule[7]]);"},{"Add":""},{"Add":" // Mix the rows."},{"Add":" g(state, 0, 5, 10, 15, msg[schedule[8]], msg[schedule[9]]);"},{"Add":" g(state, 1, 6, 11, 12, msg[schedule[10]], msg[schedule[11]]);"},{"Add":" g(state, 2, 7, 8, 13, msg[schedule[12]], msg[schedule[13]]);"},{"Add":" g(state, 3, 4, 9, 14, msg[schedule[14]], msg[schedule[15]]);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void compress_pre(uint32_t state[16], const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter, uint8_t flags) {"},{"Add":" uint32_t block_words[16];"},{"Add":" block_words[0] = load32(block + 4 * 0);"},{"Add":" block_words[1] = load32(block + 4 * 1);"},{"Add":" block_words[2] = load32(block + 4 * 2);"},{"Add":" block_words[3] = load32(block + 4 * 3);"},{"Add":" block_words[4] = load32(block + 4 * 4);"},{"Add":" block_words[5] = load32(block + 4 * 5);"},{"Add":" block_words[6] = load32(block + 4 * 6);"},{"Add":" block_words[7] = load32(block + 4 * 7);"},{"Add":" block_words[8] = load32(block + 4 * 8);"},{"Add":" block_words[9] = load32(block + 4 * 9);"},{"Add":" block_words[10] = load32(block + 4 * 10);"},{"Add":" block_words[11] = load32(block + 4 * 11);"},{"Add":" block_words[12] = load32(block + 4 * 12);"},{"Add":" block_words[13] = load32(block + 4 * 13);"},{"Add":" block_words[14] = load32(block + 4 * 14);"},{"Add":" block_words[15] = load32(block + 4 * 15);"},{"Add":""},{"Add":" state[0] = cv[0];"},{"Add":" state[1] = cv[1];"},{"Add":" state[2] = cv[2];"},{"Add":" state[3] = cv[3];"},{"Add":" state[4] = cv[4];"},{"Add":" state[5] = cv[5];"},{"Add":" state[6] = cv[6];"},{"Add":" state[7] = cv[7];"},{"Add":" state[8] = IV[0];"},{"Add":" state[9] = IV[1];"},{"Add":" state[10] = IV[2];"},{"Add":" state[11] = IV[3];"},{"Add":" state[12] = counter_low(counter);"},{"Add":" state[13] = counter_high(counter);"},{"Add":" state[14] = (uint32_t)block_len;"},{"Add":" state[15] = (uint32_t)flags;"},{"Add":""},{"Add":" round_fn(state, &block_words[0], 0);"},{"Add":" round_fn(state, &block_words[0], 1);"},{"Add":" round_fn(state, &block_words[0], 2);"},{"Add":" round_fn(state, &block_words[0], 3);"},{"Add":" round_fn(state, &block_words[0], 4);"},{"Add":" round_fn(state, &block_words[0], 5);"},{"Add":" round_fn(state, &block_words[0], 6);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_compress_in_place_portable(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags) {"},{"Add":" uint32_t state[16];"},{"Add":" compress_pre(state, cv, block, block_len, counter, flags);"},{"Add":" cv[0] = state[0] ^ state[8];"},{"Add":" cv[1] = state[1] ^ state[9];"},{"Add":" cv[2] = state[2] ^ state[10];"},{"Add":" cv[3] = state[3] ^ state[11];"},{"Add":" cv[4] = state[4] ^ state[12];"},{"Add":" cv[5] = state[5] ^ state[13];"},{"Add":" cv[6] = state[6] ^ state[14];"},{"Add":" cv[7] = state[7] ^ state[15];"},{"Add":"}"},{"Add":""},{"Add":"void blake3_compress_xof_portable(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags, uint8_t out[64]) {"},{"Add":" uint32_t state[16];"},{"Add":" compress_pre(state, cv, block, block_len, counter, flags);"},{"Add":""},{"Add":" store32(&out[0 * 4], state[0] ^ state[8]);"},{"Add":" store32(&out[1 * 4], state[1] ^ state[9]);"},{"Add":" store32(&out[2 * 4], state[2] ^ state[10]);"},{"Add":" store32(&out[3 * 4], state[3] ^ state[11]);"},{"Add":" store32(&out[4 * 4], state[4] ^ state[12]);"},{"Add":" store32(&out[5 * 4], state[5] ^ state[13]);"},{"Add":" store32(&out[6 * 4], state[6] ^ state[14]);"},{"Add":" store32(&out[7 * 4], state[7] ^ state[15]);"},{"Add":" store32(&out[8 * 4], state[8] ^ cv[0]);"},{"Add":" store32(&out[9 * 4], state[9] ^ cv[1]);"},{"Add":" store32(&out[10 * 4], state[10] ^ cv[2]);"},{"Add":" store32(&out[11 * 4], state[11] ^ cv[3]);"},{"Add":" store32(&out[12 * 4], state[12] ^ cv[4]);"},{"Add":" store32(&out[13 * 4], state[13] ^ cv[5]);"},{"Add":" store32(&out[14 * 4], state[14] ^ cv[6]);"},{"Add":" store32(&out[15 * 4], state[15] ^ cv[7]);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void hash_one_portable(const uint8_t *input, size_t blocks,"},{"Add":" const uint32_t key[8], uint64_t counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t out[BLAKE3_OUT_LEN]) {"},{"Add":" uint32_t cv[8];"},{"Add":" memcpy(cv, key, BLAKE3_KEY_LEN);"},{"Add":" uint8_t block_flags = flags | flags_start;"},{"Add":" while (blocks > 0) {"},{"Add":" if (blocks == 1) {"},{"Add":" block_flags |= flags_end;"},{"Add":" }"},{"Add":" blake3_compress_in_place_portable(cv, input, BLAKE3_BLOCK_LEN, counter,"},{"Add":" block_flags);"},{"Add":" input = &input[BLAKE3_BLOCK_LEN];"},{"Add":" blocks -= 1;"},{"Add":" block_flags = flags;"},{"Add":" }"},{"Add":" store_cv_words(out, cv);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hash_many_portable(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out) {"},{"Add":" while (num_inputs > 0) {"},{"Add":" hash_one_portable(inputs[0], blocks, key, counter, flags, flags_start,"},{"Add":" flags_end, out);"},{"Add":" if (increment_counter) {"},{"Add":" counter += 1;"},{"Add":" }"},{"Add":" inputs += 1;"},{"Add":" num_inputs -= 1;"},{"Add":" out = &out[BLAKE3_OUT_LEN];"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"blake3_impl.h","metadata":0},"context":[{"change":7,"pos":1}],"contents":[{"Add":"#ifndef BLAKE3_IMPL_H"},{"Add":"#define BLAKE3_IMPL_H"},{"Add":""},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":""},{"Add":"#include \"blake3.h\""},{"Add":""},{"Add":"// internal flags"},{"Add":"enum blake3_flags {"},{"Add":" CHUNK_START = 1 << 0,"},{"Add":" CHUNK_END = 1 << 1,"},{"Add":" PARENT = 1 << 2,"},{"Add":" ROOT = 1 << 3,"},{"Add":" KEYED_HASH = 1 << 4,"},{"Add":" DERIVE_KEY_CONTEXT = 1 << 5,"},{"Add":" DERIVE_KEY_MATERIAL = 1 << 6,"},{"Add":"};"},{"Add":""},{"Add":"// This C implementation tries to support recent versions of GCC, Clang, and"},{"Add":"// MSVC."},{"Add":"#if defined(_MSC_VER)"},{"Add":"#define INLINE static __forceinline"},{"Add":"#else"},{"Add":"#define INLINE static inline __attribute__((always_inline))"},{"Add":"#endif"},{"Add":""},{"Add":"#if defined(__x86_64__) || defined(_M_X64) "},{"Add":"#define IS_X86"},{"Add":"#define IS_X86_64"},{"Add":"#endif"},{"Add":""},{"Add":"#if defined(__i386__) || defined(_M_IX86)"},{"Add":"#define IS_X86"},{"Add":"#define IS_X86_32"},{"Add":"#endif"},{"Add":""},{"Add":"#if defined(__aarch64__) || defined(_M_ARM64)"},{"Add":"#define IS_AARCH64"},{"Add":"#endif"},{"Add":""},{"Add":"#if defined(IS_X86)"},{"Add":"#if defined(_MSC_VER)"},{"Add":"#include "},{"Add":"#endif"},{"Add":"#include "},{"Add":"#endif"},{"Add":""},{"Add":"#if !defined(BLAKE3_USE_NEON) "},{"Add":" // If BLAKE3_USE_NEON not manually set, autodetect based on AArch64ness"},{"Add":" #if defined(IS_AARCH64)"},{"Add":" #define BLAKE3_USE_NEON 1"},{"Add":" #else"},{"Add":" #define BLAKE3_USE_NEON 0"},{"Add":" #endif"},{"Add":"#endif"},{"Add":""},{"Add":"#if defined(IS_X86)"},{"Add":"#define MAX_SIMD_DEGREE 16"},{"Add":"#elif BLAKE3_USE_NEON == 1"},{"Add":"#define MAX_SIMD_DEGREE 4"},{"Add":"#else"},{"Add":"#define MAX_SIMD_DEGREE 1"},{"Add":"#endif"},{"Add":""},{"Add":"// There are some places where we want a static size that's equal to the"},{"Add":"// MAX_SIMD_DEGREE, but also at least 2."},{"Add":"#define MAX_SIMD_DEGREE_OR_2 (MAX_SIMD_DEGREE > 2 ? MAX_SIMD_DEGREE : 2)"},{"Add":""},{"Add":"static const uint32_t IV[8] = {0x6A09E667UL, 0xBB67AE85UL, 0x3C6EF372UL,"},{"Add":" 0xA54FF53AUL, 0x510E527FUL, 0x9B05688CUL,"},{"Add":" 0x1F83D9ABUL, 0x5BE0CD19UL};"},{"Add":""},{"Add":"static const uint8_t MSG_SCHEDULE[7][16] = {"},{"Add":" {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},"},{"Add":" {2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8},"},{"Add":" {3, 4, 10, 12, 13, 2, 7, 14, 6, 5, 9, 0, 11, 15, 8, 1},"},{"Add":" {10, 7, 12, 9, 14, 3, 13, 15, 4, 0, 11, 2, 5, 8, 1, 6},"},{"Add":" {12, 13, 9, 11, 15, 10, 14, 8, 7, 2, 5, 3, 0, 1, 6, 4},"},{"Add":" {9, 14, 11, 5, 8, 12, 15, 1, 13, 3, 0, 10, 2, 6, 4, 7},"},{"Add":" {11, 15, 5, 0, 1, 9, 8, 6, 14, 10, 2, 12, 3, 4, 7, 13},"},{"Add":"};"},{"Add":""},{"Add":"/* Find index of the highest set bit */"},{"Add":"/* x is assumed to be nonzero. */"},{"Add":"static unsigned int highest_one(uint64_t x) {"},{"Add":"#if defined(__GNUC__) || defined(__clang__)"},{"Add":" return 63 ^ __builtin_clzll(x);"},{"Add":"#elif defined(_MSC_VER) && defined(IS_X86_64)"},{"Add":" unsigned long index;"},{"Add":" _BitScanReverse64(&index, x);"},{"Add":" return index;"},{"Add":"#elif defined(_MSC_VER) && defined(IS_X86_32)"},{"Add":" if(x >> 32) {"},{"Add":" unsigned long index;"},{"Add":" _BitScanReverse(&index, (unsigned long)(x >> 32));"},{"Add":" return 32 + index;"},{"Add":" } else {"},{"Add":" unsigned long index;"},{"Add":" _BitScanReverse(&index, (unsigned long)x);"},{"Add":" return index;"},{"Add":" }"},{"Add":"#else"},{"Add":" unsigned int c = 0;"},{"Add":" if(x & 0xffffffff00000000ULL) { x >>= 32; c += 32; }"},{"Add":" if(x & 0x00000000ffff0000ULL) { x >>= 16; c += 16; }"},{"Add":" if(x & 0x000000000000ff00ULL) { x >>= 8; c += 8; }"},{"Add":" if(x & 0x00000000000000f0ULL) { x >>= 4; c += 4; }"},{"Add":" if(x & 0x000000000000000cULL) { x >>= 2; c += 2; }"},{"Add":" if(x & 0x0000000000000002ULL) { c += 1; }"},{"Add":" return c;"},{"Add":"#endif"},{"Add":"}"},{"Add":""},{"Add":"// Count the number of 1 bits."},{"Add":"INLINE unsigned int popcnt(uint64_t x) {"},{"Add":"#if defined(__GNUC__) || defined(__clang__)"},{"Add":" return __builtin_popcountll(x);"},{"Add":"#else"},{"Add":" unsigned int count = 0;"},{"Add":" while (x != 0) {"},{"Add":" count += 1;"},{"Add":" x &= x - 1;"},{"Add":" }"},{"Add":" return count;"},{"Add":"#endif"},{"Add":"}"},{"Add":""},{"Add":"// Largest power of two less than or equal to x. As a special case, returns 1"},{"Add":"// when x is 0. "},{"Add":"INLINE uint64_t round_down_to_power_of_2(uint64_t x) {"},{"Add":" return 1ULL << highest_one(x | 1);"},{"Add":"}"},{"Add":""},{"Add":"INLINE uint32_t counter_low(uint64_t counter) { return (uint32_t)counter; }"},{"Add":""},{"Add":"INLINE uint32_t counter_high(uint64_t counter) {"},{"Add":" return (uint32_t)(counter >> 32);"},{"Add":"}"},{"Add":""},{"Add":"INLINE uint32_t load32(const void *src) {"},{"Add":" const uint8_t *p = (const uint8_t *)src;"},{"Add":" return ((uint32_t)(p[0]) << 0) | ((uint32_t)(p[1]) << 8) |"},{"Add":" ((uint32_t)(p[2]) << 16) | ((uint32_t)(p[3]) << 24);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void load_key_words(const uint8_t key[BLAKE3_KEY_LEN],"},{"Add":" uint32_t key_words[8]) {"},{"Add":" key_words[0] = load32(&key[0 * 4]);"},{"Add":" key_words[1] = load32(&key[1 * 4]);"},{"Add":" key_words[2] = load32(&key[2 * 4]);"},{"Add":" key_words[3] = load32(&key[3 * 4]);"},{"Add":" key_words[4] = load32(&key[4 * 4]);"},{"Add":" key_words[5] = load32(&key[5 * 4]);"},{"Add":" key_words[6] = load32(&key[6 * 4]);"},{"Add":" key_words[7] = load32(&key[7 * 4]);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void store32(void *dst, uint32_t w) {"},{"Add":" uint8_t *p = (uint8_t *)dst;"},{"Add":" p[0] = (uint8_t)(w >> 0);"},{"Add":" p[1] = (uint8_t)(w >> 8);"},{"Add":" p[2] = (uint8_t)(w >> 16);"},{"Add":" p[3] = (uint8_t)(w >> 24);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void store_cv_words(uint8_t bytes_out[32], uint32_t cv_words[8]) {"},{"Add":" store32(&bytes_out[0 * 4], cv_words[0]);"},{"Add":" store32(&bytes_out[1 * 4], cv_words[1]);"},{"Add":" store32(&bytes_out[2 * 4], cv_words[2]);"},{"Add":" store32(&bytes_out[3 * 4], cv_words[3]);"},{"Add":" store32(&bytes_out[4 * 4], cv_words[4]);"},{"Add":" store32(&bytes_out[5 * 4], cv_words[5]);"},{"Add":" store32(&bytes_out[6 * 4], cv_words[6]);"},{"Add":" store32(&bytes_out[7 * 4], cv_words[7]);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_compress_in_place(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags);"},{"Add":""},{"Add":"void blake3_compress_xof(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter, uint8_t flags,"},{"Add":" uint8_t out[64]);"},{"Add":""},{"Add":"void blake3_hash_many(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8], uint64_t counter,"},{"Add":" bool increment_counter, uint8_t flags,"},{"Add":" uint8_t flags_start, uint8_t flags_end, uint8_t *out);"},{"Add":""},{"Add":"size_t blake3_simd_degree(void);"},{"Add":""},{"Add":""},{"Add":"// Declarations for implementation-specific functions."},{"Add":"void blake3_compress_in_place_portable(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags);"},{"Add":""},{"Add":"void blake3_compress_xof_portable(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags, uint8_t out[64]);"},{"Add":""},{"Add":"void blake3_hash_many_portable(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out);"},{"Add":""},{"Add":"#if defined(IS_X86)"},{"Add":"#if !defined(BLAKE3_NO_SSE2)"},{"Add":"void blake3_compress_in_place_sse2(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags);"},{"Add":"void blake3_compress_xof_sse2(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags, uint8_t out[64]);"},{"Add":"void blake3_hash_many_sse2(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out);"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE41)"},{"Add":"void blake3_compress_in_place_sse41(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags);"},{"Add":"void blake3_compress_xof_sse41(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags, uint8_t out[64]);"},{"Add":"void blake3_hash_many_sse41(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out);"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_AVX2)"},{"Add":"void blake3_hash_many_avx2(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out);"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_AVX512)"},{"Add":"void blake3_compress_in_place_avx512(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags);"},{"Add":""},{"Add":"void blake3_compress_xof_avx512(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags, uint8_t out[64]);"},{"Add":""},{"Add":"void blake3_hash_many_avx512(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out);"},{"Add":"#endif"},{"Add":"#endif"},{"Add":""},{"Add":"#if BLAKE3_USE_NEON == 1"},{"Add":"void blake3_hash_many_neon(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8],"},{"Add":" uint64_t counter, bool increment_counter,"},{"Add":" uint8_t flags, uint8_t flags_start,"},{"Add":" uint8_t flags_end, uint8_t *out);"},{"Add":"#endif"},{"Add":""},{"Add":""},{"Add":"#endif /* BLAKE3_IMPL_H */"}]}},{"FileAdd":{"meta":{"basename":"blake3_dispatch.c","metadata":0},"context":[{"change":7,"pos":1}],"contents":[{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":""},{"Add":"#include \"blake3_impl.h\""},{"Add":""},{"Add":"#if defined(IS_X86)"},{"Add":"#if defined(_MSC_VER)"},{"Add":"#include "},{"Add":"#elif defined(__GNUC__)"},{"Add":"#include "},{"Add":"#else"},{"Add":"#error \"Unimplemented!\""},{"Add":"#endif"},{"Add":"#endif"},{"Add":""},{"Add":"#define MAYBE_UNUSED(x) (void)((x))"},{"Add":""},{"Add":"#if defined(IS_X86)"},{"Add":"static uint64_t xgetbv(void) {"},{"Add":"#if defined(_MSC_VER)"},{"Add":" return _xgetbv(0);"},{"Add":"#else"},{"Add":" uint32_t eax = 0, edx = 0;"},{"Add":" __asm__ __volatile__(\"xgetbv\\n\" : \"=a\"(eax), \"=d\"(edx) : \"c\"(0));"},{"Add":" return ((uint64_t)edx << 32) | eax;"},{"Add":"#endif"},{"Add":"}"},{"Add":""},{"Add":"static void cpuid(uint32_t out[4], uint32_t id) {"},{"Add":"#if defined(_MSC_VER)"},{"Add":" __cpuid((int *)out, id);"},{"Add":"#elif defined(__i386__) || defined(_M_IX86)"},{"Add":" __asm__ __volatile__(\"movl %%ebx, %1\\n\""},{"Add":" \"cpuid\\n\""},{"Add":" \"xchgl %1, %%ebx\\n\""},{"Add":" : \"=a\"(out[0]), \"=r\"(out[1]), \"=c\"(out[2]), \"=d\"(out[3])"},{"Add":" : \"a\"(id));"},{"Add":"#else"},{"Add":" __asm__ __volatile__(\"cpuid\\n\""},{"Add":" : \"=a\"(out[0]), \"=b\"(out[1]), \"=c\"(out[2]), \"=d\"(out[3])"},{"Add":" : \"a\"(id));"},{"Add":"#endif"},{"Add":"}"},{"Add":""},{"Add":"static void cpuidex(uint32_t out[4], uint32_t id, uint32_t sid) {"},{"Add":"#if defined(_MSC_VER)"},{"Add":" __cpuidex((int *)out, id, sid);"},{"Add":"#elif defined(__i386__) || defined(_M_IX86)"},{"Add":" __asm__ __volatile__(\"movl %%ebx, %1\\n\""},{"Add":" \"cpuid\\n\""},{"Add":" \"xchgl %1, %%ebx\\n\""},{"Add":" : \"=a\"(out[0]), \"=r\"(out[1]), \"=c\"(out[2]), \"=d\"(out[3])"},{"Add":" : \"a\"(id), \"c\"(sid));"},{"Add":"#else"},{"Add":" __asm__ __volatile__(\"cpuid\\n\""},{"Add":" : \"=a\"(out[0]), \"=b\"(out[1]), \"=c\"(out[2]), \"=d\"(out[3])"},{"Add":" : \"a\"(id), \"c\"(sid));"},{"Add":"#endif"},{"Add":"}"},{"Add":""},{"Add":"#endif"},{"Add":""},{"Add":"enum cpu_feature {"},{"Add":" SSE2 = 1 << 0,"},{"Add":" SSSE3 = 1 << 1,"},{"Add":" SSE41 = 1 << 2,"},{"Add":" AVX = 1 << 3,"},{"Add":" AVX2 = 1 << 4,"},{"Add":" AVX512F = 1 << 5,"},{"Add":" AVX512VL = 1 << 6,"},{"Add":" /* ... */"},{"Add":" UNDEFINED = 1 << 30"},{"Add":"};"},{"Add":""},{"Add":"#if !defined(BLAKE3_TESTING)"},{"Add":"static /* Allow the variable to be controlled manually for testing */"},{"Add":"#endif"},{"Add":" enum cpu_feature g_cpu_features = UNDEFINED;"},{"Add":""},{"Add":"#if !defined(BLAKE3_TESTING)"},{"Add":"static"},{"Add":"#endif"},{"Add":" enum cpu_feature"},{"Add":" get_cpu_features(void) {"},{"Add":""},{"Add":" if (g_cpu_features != UNDEFINED) {"},{"Add":" return g_cpu_features;"},{"Add":" } else {"},{"Add":"#if defined(IS_X86)"},{"Add":" uint32_t regs[4] = {0};"},{"Add":" uint32_t *eax = ®s[0], *ebx = ®s[1], *ecx = ®s[2], *edx = ®s[3];"},{"Add":" (void)edx;"},{"Add":" enum cpu_feature features = 0;"},{"Add":" cpuid(regs, 0);"},{"Add":" const int max_id = *eax;"},{"Add":" cpuid(regs, 1);"},{"Add":"#if defined(__amd64__) || defined(_M_X64)"},{"Add":" features |= SSE2;"},{"Add":"#else"},{"Add":" if (*edx & (1UL << 26))"},{"Add":" features |= SSE2;"},{"Add":"#endif"},{"Add":" if (*ecx & (1UL << 0))"},{"Add":" features |= SSSE3;"},{"Add":" if (*ecx & (1UL << 19))"},{"Add":" features |= SSE41;"},{"Add":""},{"Add":" if (*ecx & (1UL << 27)) { // OSXSAVE"},{"Add":" const uint64_t mask = xgetbv();"},{"Add":" if ((mask & 6) == 6) { // SSE and AVX states"},{"Add":" if (*ecx & (1UL << 28))"},{"Add":" features |= AVX;"},{"Add":" if (max_id >= 7) {"},{"Add":" cpuidex(regs, 7, 0);"},{"Add":" if (*ebx & (1UL << 5))"},{"Add":" features |= AVX2;"},{"Add":" if ((mask & 224) == 224) { // Opmask, ZMM_Hi256, Hi16_Zmm"},{"Add":" if (*ebx & (1UL << 31))"},{"Add":" features |= AVX512VL;"},{"Add":" if (*ebx & (1UL << 16))"},{"Add":" features |= AVX512F;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" g_cpu_features = features;"},{"Add":" return features;"},{"Add":"#else"},{"Add":" /* How to detect NEON? */"},{"Add":" return 0;"},{"Add":"#endif"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"void blake3_compress_in_place(uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags) {"},{"Add":"#if defined(IS_X86)"},{"Add":" const enum cpu_feature features = get_cpu_features();"},{"Add":" MAYBE_UNUSED(features);"},{"Add":"#if !defined(BLAKE3_NO_AVX512)"},{"Add":" if (features & AVX512VL) {"},{"Add":" blake3_compress_in_place_avx512(cv, block, block_len, counter, flags);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE41)"},{"Add":" if (features & SSE41) {"},{"Add":" blake3_compress_in_place_sse41(cv, block, block_len, counter, flags);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE2)"},{"Add":" if (features & SSE2) {"},{"Add":" blake3_compress_in_place_sse2(cv, block, block_len, counter, flags);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#endif"},{"Add":" blake3_compress_in_place_portable(cv, block, block_len, counter, flags);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_compress_xof(const uint32_t cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter, uint8_t flags,"},{"Add":" uint8_t out[64]) {"},{"Add":"#if defined(IS_X86)"},{"Add":" const enum cpu_feature features = get_cpu_features();"},{"Add":" MAYBE_UNUSED(features);"},{"Add":"#if !defined(BLAKE3_NO_AVX512)"},{"Add":" if (features & AVX512VL) {"},{"Add":" blake3_compress_xof_avx512(cv, block, block_len, counter, flags, out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE41)"},{"Add":" if (features & SSE41) {"},{"Add":" blake3_compress_xof_sse41(cv, block, block_len, counter, flags, out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE2)"},{"Add":" if (features & SSE2) {"},{"Add":" blake3_compress_xof_sse2(cv, block, block_len, counter, flags, out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#endif"},{"Add":" blake3_compress_xof_portable(cv, block, block_len, counter, flags, out);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hash_many(const uint8_t *const *inputs, size_t num_inputs,"},{"Add":" size_t blocks, const uint32_t key[8], uint64_t counter,"},{"Add":" bool increment_counter, uint8_t flags,"},{"Add":" uint8_t flags_start, uint8_t flags_end, uint8_t *out) {"},{"Add":"#if defined(IS_X86)"},{"Add":" const enum cpu_feature features = get_cpu_features();"},{"Add":" MAYBE_UNUSED(features);"},{"Add":"#if !defined(BLAKE3_NO_AVX512)"},{"Add":" if ((features & (AVX512F|AVX512VL)) == (AVX512F|AVX512VL)) {"},{"Add":" blake3_hash_many_avx512(inputs, num_inputs, blocks, key, counter,"},{"Add":" increment_counter, flags, flags_start, flags_end,"},{"Add":" out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_AVX2)"},{"Add":" if (features & AVX2) {"},{"Add":" blake3_hash_many_avx2(inputs, num_inputs, blocks, key, counter,"},{"Add":" increment_counter, flags, flags_start, flags_end,"},{"Add":" out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE41)"},{"Add":" if (features & SSE41) {"},{"Add":" blake3_hash_many_sse41(inputs, num_inputs, blocks, key, counter,"},{"Add":" increment_counter, flags, flags_start, flags_end,"},{"Add":" out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE2)"},{"Add":" if (features & SSE2) {"},{"Add":" blake3_hash_many_sse2(inputs, num_inputs, blocks, key, counter,"},{"Add":" increment_counter, flags, flags_start, flags_end,"},{"Add":" out);"},{"Add":" return;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#endif"},{"Add":""},{"Add":"#if BLAKE3_USE_NEON == 1"},{"Add":" blake3_hash_many_neon(inputs, num_inputs, blocks, key, counter,"},{"Add":" increment_counter, flags, flags_start, flags_end, out);"},{"Add":" return;"},{"Add":"#endif"},{"Add":""},{"Add":" blake3_hash_many_portable(inputs, num_inputs, blocks, key, counter,"},{"Add":" increment_counter, flags, flags_start, flags_end,"},{"Add":" out);"},{"Add":"}"},{"Add":""},{"Add":"// The dynamically detected SIMD degree of the current platform."},{"Add":"size_t blake3_simd_degree(void) {"},{"Add":"#if defined(IS_X86)"},{"Add":" const enum cpu_feature features = get_cpu_features();"},{"Add":" MAYBE_UNUSED(features);"},{"Add":"#if !defined(BLAKE3_NO_AVX512)"},{"Add":" if ((features & (AVX512F|AVX512VL)) == (AVX512F|AVX512VL)) {"},{"Add":" return 16;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_AVX2)"},{"Add":" if (features & AVX2) {"},{"Add":" return 8;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE41)"},{"Add":" if (features & SSE41) {"},{"Add":" return 4;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#if !defined(BLAKE3_NO_SSE2)"},{"Add":" if (features & SSE2) {"},{"Add":" return 4;"},{"Add":" }"},{"Add":"#endif"},{"Add":"#endif"},{"Add":"#if BLAKE3_USE_NEON == 1"},{"Add":" return 4;"},{"Add":"#endif"},{"Add":" return 1;"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"blake3.h","metadata":0},"context":[{"change":7,"pos":1}],"contents":[{"Add":"#ifndef BLAKE3_H"},{"Add":"#define BLAKE3_H"},{"Add":""},{"Add":"#include "},{"Add":"#include "},{"Add":""},{"Add":"#ifdef __cplusplus"},{"Add":"extern \"C\" {"},{"Add":"#endif"},{"Add":""},{"Add":"#define BLAKE3_VERSION_STRING \"1.3.1\""},{"Add":"#define BLAKE3_KEY_LEN 32"},{"Add":"#define BLAKE3_OUT_LEN 32"},{"Add":"#define BLAKE3_BLOCK_LEN 64"},{"Add":"#define BLAKE3_CHUNK_LEN 1024"},{"Add":"#define BLAKE3_MAX_DEPTH 54"},{"Add":""},{"Add":"// This struct is a private implementation detail. It has to be here because"},{"Add":"// it's part of blake3_hasher below."},{"Add":"typedef struct {"},{"Add":" uint32_t cv[8];"},{"Add":" uint64_t chunk_counter;"},{"Add":" uint8_t buf[BLAKE3_BLOCK_LEN];"},{"Add":" uint8_t buf_len;"},{"Add":" uint8_t blocks_compressed;"},{"Add":" uint8_t flags;"},{"Add":"} blake3_chunk_state;"},{"Add":""},{"Add":"typedef struct {"},{"Add":" uint32_t key[8];"},{"Add":" blake3_chunk_state chunk;"},{"Add":" uint8_t cv_stack_len;"},{"Add":" // The stack size is MAX_DEPTH + 1 because we do lazy merging. For example,"},{"Add":" // with 7 chunks, we have 3 entries in the stack. Adding an 8th chunk"},{"Add":" // requires a 4th entry, rather than merging everything down to 1, because we"},{"Add":" // don't know whether more input is coming. This is different from how the"},{"Add":" // reference implementation does things."},{"Add":" uint8_t cv_stack[(BLAKE3_MAX_DEPTH + 1) * BLAKE3_OUT_LEN];"},{"Add":"} blake3_hasher;"},{"Add":""},{"Add":"const char *blake3_version(void);"},{"Add":"void blake3_hasher_init(blake3_hasher *self);"},{"Add":"void blake3_hasher_init_keyed(blake3_hasher *self,"},{"Add":" const uint8_t key[BLAKE3_KEY_LEN]);"},{"Add":"void blake3_hasher_init_derive_key(blake3_hasher *self, const char *context);"},{"Add":"void blake3_hasher_init_derive_key_raw(blake3_hasher *self, const void *context,"},{"Add":" size_t context_len);"},{"Add":"void blake3_hasher_update(blake3_hasher *self, const void *input,"},{"Add":" size_t input_len);"},{"Add":"void blake3_hasher_finalize(const blake3_hasher *self, uint8_t *out,"},{"Add":" size_t out_len);"},{"Add":"void blake3_hasher_finalize_seek(const blake3_hasher *self, uint64_t seek,"},{"Add":" uint8_t *out, size_t out_len);"},{"Add":"void blake3_hasher_reset(blake3_hasher *self);"},{"Add":""},{"Add":"#ifdef __cplusplus"},{"Add":"}"},{"Add":"#endif"},{"Add":""},{"Add":"#endif /* BLAKE3_H */"}]}},{"FileAdd":{"meta":{"basename":"blake3.c","metadata":0},"context":[{"change":7,"pos":1}],"contents":[{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":""},{"Add":"#include \"blake3.h\""},{"Add":"#include \"blake3_impl.h\""},{"Add":""},{"Add":"const char *blake3_version(void) { return BLAKE3_VERSION_STRING; }"},{"Add":""},{"Add":"INLINE void chunk_state_init(blake3_chunk_state *self, const uint32_t key[8],"},{"Add":" uint8_t flags) {"},{"Add":" memcpy(self->cv, key, BLAKE3_KEY_LEN);"},{"Add":" self->chunk_counter = 0;"},{"Add":" memset(self->buf, 0, BLAKE3_BLOCK_LEN);"},{"Add":" self->buf_len = 0;"},{"Add":" self->blocks_compressed = 0;"},{"Add":" self->flags = flags;"},{"Add":"}"},{"Add":""},{"Add":"INLINE void chunk_state_reset(blake3_chunk_state *self, const uint32_t key[8],"},{"Add":" uint64_t chunk_counter) {"},{"Add":" memcpy(self->cv, key, BLAKE3_KEY_LEN);"},{"Add":" self->chunk_counter = chunk_counter;"},{"Add":" self->blocks_compressed = 0;"},{"Add":" memset(self->buf, 0, BLAKE3_BLOCK_LEN);"},{"Add":" self->buf_len = 0;"},{"Add":"}"},{"Add":""},{"Add":"INLINE size_t chunk_state_len(const blake3_chunk_state *self) {"},{"Add":" return (BLAKE3_BLOCK_LEN * (size_t)self->blocks_compressed) +"},{"Add":" ((size_t)self->buf_len);"},{"Add":"}"},{"Add":""},{"Add":"INLINE size_t chunk_state_fill_buf(blake3_chunk_state *self,"},{"Add":" const uint8_t *input, size_t input_len) {"},{"Add":" size_t take = BLAKE3_BLOCK_LEN - ((size_t)self->buf_len);"},{"Add":" if (take > input_len) {"},{"Add":" take = input_len;"},{"Add":" }"},{"Add":" uint8_t *dest = self->buf + ((size_t)self->buf_len);"},{"Add":" memcpy(dest, input, take);"},{"Add":" self->buf_len += (uint8_t)take;"},{"Add":" return take;"},{"Add":"}"},{"Add":""},{"Add":"INLINE uint8_t chunk_state_maybe_start_flag(const blake3_chunk_state *self) {"},{"Add":" if (self->blocks_compressed == 0) {"},{"Add":" return CHUNK_START;"},{"Add":" } else {"},{"Add":" return 0;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"typedef struct {"},{"Add":" uint32_t input_cv[8];"},{"Add":" uint64_t counter;"},{"Add":" uint8_t block[BLAKE3_BLOCK_LEN];"},{"Add":" uint8_t block_len;"},{"Add":" uint8_t flags;"},{"Add":"} output_t;"},{"Add":""},{"Add":"INLINE output_t make_output(const uint32_t input_cv[8],"},{"Add":" const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" uint8_t block_len, uint64_t counter,"},{"Add":" uint8_t flags) {"},{"Add":" output_t ret;"},{"Add":" memcpy(ret.input_cv, input_cv, 32);"},{"Add":" memcpy(ret.block, block, BLAKE3_BLOCK_LEN);"},{"Add":" ret.block_len = block_len;"},{"Add":" ret.counter = counter;"},{"Add":" ret.flags = flags;"},{"Add":" return ret;"},{"Add":"}"},{"Add":""},{"Add":"// Chaining values within a given chunk (specifically the compress_in_place"},{"Add":"// interface) are represented as words. This avoids unnecessary bytes<->words"},{"Add":"// conversion overhead in the portable implementation. However, the hash_many"},{"Add":"// interface handles both user input and parent node blocks, so it accepts"},{"Add":"// bytes. For that reason, chaining values in the CV stack are represented as"},{"Add":"// bytes."},{"Add":"INLINE void output_chaining_value(const output_t *self, uint8_t cv[32]) {"},{"Add":" uint32_t cv_words[8];"},{"Add":" memcpy(cv_words, self->input_cv, 32);"},{"Add":" blake3_compress_in_place(cv_words, self->block, self->block_len,"},{"Add":" self->counter, self->flags);"},{"Add":" store_cv_words(cv, cv_words);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void output_root_bytes(const output_t *self, uint64_t seek, uint8_t *out,"},{"Add":" size_t out_len) {"},{"Add":" uint64_t output_block_counter = seek / 64;"},{"Add":" size_t offset_within_block = seek % 64;"},{"Add":" uint8_t wide_buf[64];"},{"Add":" while (out_len > 0) {"},{"Add":" blake3_compress_xof(self->input_cv, self->block, self->block_len,"},{"Add":" output_block_counter, self->flags | ROOT, wide_buf);"},{"Add":" size_t available_bytes = 64 - offset_within_block;"},{"Add":" size_t memcpy_len;"},{"Add":" if (out_len > available_bytes) {"},{"Add":" memcpy_len = available_bytes;"},{"Add":" } else {"},{"Add":" memcpy_len = out_len;"},{"Add":" }"},{"Add":" memcpy(out, wide_buf + offset_within_block, memcpy_len);"},{"Add":" out += memcpy_len;"},{"Add":" out_len -= memcpy_len;"},{"Add":" output_block_counter += 1;"},{"Add":" offset_within_block = 0;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"INLINE void chunk_state_update(blake3_chunk_state *self, const uint8_t *input,"},{"Add":" size_t input_len) {"},{"Add":" if (self->buf_len > 0) {"},{"Add":" size_t take = chunk_state_fill_buf(self, input, input_len);"},{"Add":" input += take;"},{"Add":" input_len -= take;"},{"Add":" if (input_len > 0) {"},{"Add":" blake3_compress_in_place("},{"Add":" self->cv, self->buf, BLAKE3_BLOCK_LEN, self->chunk_counter,"},{"Add":" self->flags | chunk_state_maybe_start_flag(self));"},{"Add":" self->blocks_compressed += 1;"},{"Add":" self->buf_len = 0;"},{"Add":" memset(self->buf, 0, BLAKE3_BLOCK_LEN);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" while (input_len > BLAKE3_BLOCK_LEN) {"},{"Add":" blake3_compress_in_place(self->cv, input, BLAKE3_BLOCK_LEN,"},{"Add":" self->chunk_counter,"},{"Add":" self->flags | chunk_state_maybe_start_flag(self));"},{"Add":" self->blocks_compressed += 1;"},{"Add":" input += BLAKE3_BLOCK_LEN;"},{"Add":" input_len -= BLAKE3_BLOCK_LEN;"},{"Add":" }"},{"Add":""},{"Add":" size_t take = chunk_state_fill_buf(self, input, input_len);"},{"Add":" input += take;"},{"Add":" input_len -= take;"},{"Add":"}"},{"Add":""},{"Add":"INLINE output_t chunk_state_output(const blake3_chunk_state *self) {"},{"Add":" uint8_t block_flags ="},{"Add":" self->flags | chunk_state_maybe_start_flag(self) | CHUNK_END;"},{"Add":" return make_output(self->cv, self->buf, self->buf_len, self->chunk_counter,"},{"Add":" block_flags);"},{"Add":"}"},{"Add":""},{"Add":"INLINE output_t parent_output(const uint8_t block[BLAKE3_BLOCK_LEN],"},{"Add":" const uint32_t key[8], uint8_t flags) {"},{"Add":" return make_output(key, block, BLAKE3_BLOCK_LEN, 0, flags | PARENT);"},{"Add":"}"},{"Add":""},{"Add":"// Given some input larger than one chunk, return the number of bytes that"},{"Add":"// should go in the left subtree. This is the largest power-of-2 number of"},{"Add":"// chunks that leaves at least 1 byte for the right subtree."},{"Add":"INLINE size_t left_len(size_t content_len) {"},{"Add":" // Subtract 1 to reserve at least one byte for the right side. content_len"},{"Add":" // should always be greater than BLAKE3_CHUNK_LEN."},{"Add":" size_t full_chunks = (content_len - 1) / BLAKE3_CHUNK_LEN;"},{"Add":" return round_down_to_power_of_2(full_chunks) * BLAKE3_CHUNK_LEN;"},{"Add":"}"},{"Add":""},{"Add":"// Use SIMD parallelism to hash up to MAX_SIMD_DEGREE chunks at the same time"},{"Add":"// on a single thread. Write out the chunk chaining values and return the"},{"Add":"// number of chunks hashed. These chunks are never the root and never empty;"},{"Add":"// those cases use a different codepath."},{"Add":"INLINE size_t compress_chunks_parallel(const uint8_t *input, size_t input_len,"},{"Add":" const uint32_t key[8],"},{"Add":" uint64_t chunk_counter, uint8_t flags,"},{"Add":" uint8_t *out) {"},{"Add":"#if defined(BLAKE3_TESTING)"},{"Add":" assert(0 < input_len);"},{"Add":" assert(input_len <= MAX_SIMD_DEGREE * BLAKE3_CHUNK_LEN);"},{"Add":"#endif"},{"Add":""},{"Add":" const uint8_t *chunks_array[MAX_SIMD_DEGREE];"},{"Add":" size_t input_position = 0;"},{"Add":" size_t chunks_array_len = 0;"},{"Add":" while (input_len - input_position >= BLAKE3_CHUNK_LEN) {"},{"Add":" chunks_array[chunks_array_len] = &input[input_position];"},{"Add":" input_position += BLAKE3_CHUNK_LEN;"},{"Add":" chunks_array_len += 1;"},{"Add":" }"},{"Add":""},{"Add":" blake3_hash_many(chunks_array, chunks_array_len,"},{"Add":" BLAKE3_CHUNK_LEN / BLAKE3_BLOCK_LEN, key, chunk_counter,"},{"Add":" true, flags, CHUNK_START, CHUNK_END, out);"},{"Add":""},{"Add":" // Hash the remaining partial chunk, if there is one. Note that the empty"},{"Add":" // chunk (meaning the empty message) is a different codepath."},{"Add":" if (input_len > input_position) {"},{"Add":" uint64_t counter = chunk_counter + (uint64_t)chunks_array_len;"},{"Add":" blake3_chunk_state chunk_state;"},{"Add":" chunk_state_init(&chunk_state, key, flags);"},{"Add":" chunk_state.chunk_counter = counter;"},{"Add":" chunk_state_update(&chunk_state, &input[input_position],"},{"Add":" input_len - input_position);"},{"Add":" output_t output = chunk_state_output(&chunk_state);"},{"Add":" output_chaining_value(&output, &out[chunks_array_len * BLAKE3_OUT_LEN]);"},{"Add":" return chunks_array_len + 1;"},{"Add":" } else {"},{"Add":" return chunks_array_len;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// Use SIMD parallelism to hash up to MAX_SIMD_DEGREE parents at the same time"},{"Add":"// on a single thread. Write out the parent chaining values and return the"},{"Add":"// number of parents hashed. (If there's an odd input chaining value left over,"},{"Add":"// return it as an additional output.) These parents are never the root and"},{"Add":"// never empty; those cases use a different codepath."},{"Add":"INLINE size_t compress_parents_parallel(const uint8_t *child_chaining_values,"},{"Add":" size_t num_chaining_values,"},{"Add":" const uint32_t key[8], uint8_t flags,"},{"Add":" uint8_t *out) {"},{"Add":"#if defined(BLAKE3_TESTING)"},{"Add":" assert(2 <= num_chaining_values);"},{"Add":" assert(num_chaining_values <= 2 * MAX_SIMD_DEGREE_OR_2);"},{"Add":"#endif"},{"Add":""},{"Add":" const uint8_t *parents_array[MAX_SIMD_DEGREE_OR_2];"},{"Add":" size_t parents_array_len = 0;"},{"Add":" while (num_chaining_values - (2 * parents_array_len) >= 2) {"},{"Add":" parents_array[parents_array_len] ="},{"Add":" &child_chaining_values[2 * parents_array_len * BLAKE3_OUT_LEN];"},{"Add":" parents_array_len += 1;"},{"Add":" }"},{"Add":""},{"Add":" blake3_hash_many(parents_array, parents_array_len, 1, key,"},{"Add":" 0, // Parents always use counter 0."},{"Add":" false, flags | PARENT,"},{"Add":" 0, // Parents have no start flags."},{"Add":" 0, // Parents have no end flags."},{"Add":" out);"},{"Add":""},{"Add":" // If there's an odd child left over, it becomes an output."},{"Add":" if (num_chaining_values > 2 * parents_array_len) {"},{"Add":" memcpy(&out[parents_array_len * BLAKE3_OUT_LEN],"},{"Add":" &child_chaining_values[2 * parents_array_len * BLAKE3_OUT_LEN],"},{"Add":" BLAKE3_OUT_LEN);"},{"Add":" return parents_array_len + 1;"},{"Add":" } else {"},{"Add":" return parents_array_len;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// The wide helper function returns (writes out) an array of chaining values"},{"Add":"// and returns the length of that array. The number of chaining values returned"},{"Add":"// is the dynamically detected SIMD degree, at most MAX_SIMD_DEGREE. Or fewer,"},{"Add":"// if the input is shorter than that many chunks. The reason for maintaining a"},{"Add":"// wide array of chaining values going back up the tree, is to allow the"},{"Add":"// implementation to hash as many parents in parallel as possible."},{"Add":"//"},{"Add":"// As a special case when the SIMD degree is 1, this function will still return"},{"Add":"// at least 2 outputs. This guarantees that this function doesn't perform the"},{"Add":"// root compression. (If it did, it would use the wrong flags, and also we"},{"Add":"// wouldn't be able to implement exendable output.) Note that this function is"},{"Add":"// not used when the whole input is only 1 chunk long; that's a different"},{"Add":"// codepath."},{"Add":"//"},{"Add":"// Why not just have the caller split the input on the first update(), instead"},{"Add":"// of implementing this special rule? Because we don't want to limit SIMD or"},{"Add":"// multi-threading parallelism for that update()."},{"Add":"static size_t blake3_compress_subtree_wide(const uint8_t *input,"},{"Add":" size_t input_len,"},{"Add":" const uint32_t key[8],"},{"Add":" uint64_t chunk_counter,"},{"Add":" uint8_t flags, uint8_t *out) {"},{"Add":" // Note that the single chunk case does *not* bump the SIMD degree up to 2"},{"Add":" // when it is 1. If this implementation adds multi-threading in the future,"},{"Add":" // this gives us the option of multi-threading even the 2-chunk case, which"},{"Add":" // can help performance on smaller platforms."},{"Add":" if (input_len <= blake3_simd_degree() * BLAKE3_CHUNK_LEN) {"},{"Add":" return compress_chunks_parallel(input, input_len, key, chunk_counter, flags,"},{"Add":" out);"},{"Add":" }"},{"Add":""},{"Add":" // With more than simd_degree chunks, we need to recurse. Start by dividing"},{"Add":" // the input into left and right subtrees. (Note that this is only optimal"},{"Add":" // as long as the SIMD degree is a power of 2. If we ever get a SIMD degree"},{"Add":" // of 3 or something, we'll need a more complicated strategy.)"},{"Add":" size_t left_input_len = left_len(input_len);"},{"Add":" size_t right_input_len = input_len - left_input_len;"},{"Add":" const uint8_t *right_input = &input[left_input_len];"},{"Add":" uint64_t right_chunk_counter ="},{"Add":" chunk_counter + (uint64_t)(left_input_len / BLAKE3_CHUNK_LEN);"},{"Add":""},{"Add":" // Make space for the child outputs. Here we use MAX_SIMD_DEGREE_OR_2 to"},{"Add":" // account for the special case of returning 2 outputs when the SIMD degree"},{"Add":" // is 1."},{"Add":" uint8_t cv_array[2 * MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN];"},{"Add":" size_t degree = blake3_simd_degree();"},{"Add":" if (left_input_len > BLAKE3_CHUNK_LEN && degree == 1) {"},{"Add":" // The special case: We always use a degree of at least two, to make"},{"Add":" // sure there are two outputs. Except, as noted above, at the chunk"},{"Add":" // level, where we allow degree=1. (Note that the 1-chunk-input case is"},{"Add":" // a different codepath.)"},{"Add":" degree = 2;"},{"Add":" }"},{"Add":" uint8_t *right_cvs = &cv_array[degree * BLAKE3_OUT_LEN];"},{"Add":""},{"Add":" // Recurse! If this implementation adds multi-threading support in the"},{"Add":" // future, this is where it will go."},{"Add":" size_t left_n = blake3_compress_subtree_wide(input, left_input_len, key,"},{"Add":" chunk_counter, flags, cv_array);"},{"Add":" size_t right_n = blake3_compress_subtree_wide("},{"Add":" right_input, right_input_len, key, right_chunk_counter, flags, right_cvs);"},{"Add":""},{"Add":" // The special case again. If simd_degree=1, then we'll have left_n=1 and"},{"Add":" // right_n=1. Rather than compressing them into a single output, return"},{"Add":" // them directly, to make sure we always have at least two outputs."},{"Add":" if (left_n == 1) {"},{"Add":" memcpy(out, cv_array, 2 * BLAKE3_OUT_LEN);"},{"Add":" return 2;"},{"Add":" }"},{"Add":""},{"Add":" // Otherwise, do one layer of parent node compression."},{"Add":" size_t num_chaining_values = left_n + right_n;"},{"Add":" return compress_parents_parallel(cv_array, num_chaining_values, key, flags,"},{"Add":" out);"},{"Add":"}"},{"Add":""},{"Add":"// Hash a subtree with compress_subtree_wide(), and then condense the resulting"},{"Add":"// list of chaining values down to a single parent node. Don't compress that"},{"Add":"// last parent node, however. Instead, return its message bytes (the"},{"Add":"// concatenated chaining values of its children). This is necessary when the"},{"Add":"// first call to update() supplies a complete subtree, because the topmost"},{"Add":"// parent node of that subtree could end up being the root. It's also necessary"},{"Add":"// for extended output in the general case."},{"Add":"//"},{"Add":"// As with compress_subtree_wide(), this function is not used on inputs of 1"},{"Add":"// chunk or less. That's a different codepath."},{"Add":"INLINE void compress_subtree_to_parent_node("},{"Add":" const uint8_t *input, size_t input_len, const uint32_t key[8],"},{"Add":" uint64_t chunk_counter, uint8_t flags, uint8_t out[2 * BLAKE3_OUT_LEN]) {"},{"Add":"#if defined(BLAKE3_TESTING)"},{"Add":" assert(input_len > BLAKE3_CHUNK_LEN);"},{"Add":"#endif"},{"Add":""},{"Add":" uint8_t cv_array[MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN];"},{"Add":" size_t num_cvs = blake3_compress_subtree_wide(input, input_len, key,"},{"Add":" chunk_counter, flags, cv_array);"},{"Add":" assert(num_cvs <= MAX_SIMD_DEGREE_OR_2);"},{"Add":""},{"Add":" // If MAX_SIMD_DEGREE is greater than 2 and there's enough input,"},{"Add":" // compress_subtree_wide() returns more than 2 chaining values. Condense"},{"Add":" // them into 2 by forming parent nodes repeatedly."},{"Add":" uint8_t out_array[MAX_SIMD_DEGREE_OR_2 * BLAKE3_OUT_LEN / 2];"},{"Add":" // The second half of this loop condition is always true, and we just"},{"Add":" // asserted it above. But GCC can't tell that it's always true, and if NDEBUG"},{"Add":" // is set on platforms where MAX_SIMD_DEGREE_OR_2 == 2, GCC emits spurious"},{"Add":" // warnings here. GCC 8.5 is particularly sensitive, so if you're changing"},{"Add":" // this code, test it against that version."},{"Add":" while (num_cvs > 2 && num_cvs <= MAX_SIMD_DEGREE_OR_2) {"},{"Add":" num_cvs ="},{"Add":" compress_parents_parallel(cv_array, num_cvs, key, flags, out_array);"},{"Add":" memcpy(cv_array, out_array, num_cvs * BLAKE3_OUT_LEN);"},{"Add":" }"},{"Add":" memcpy(out, cv_array, 2 * BLAKE3_OUT_LEN);"},{"Add":"}"},{"Add":""},{"Add":"INLINE void hasher_init_base(blake3_hasher *self, const uint32_t key[8],"},{"Add":" uint8_t flags) {"},{"Add":" memcpy(self->key, key, BLAKE3_KEY_LEN);"},{"Add":" chunk_state_init(&self->chunk, key, flags);"},{"Add":" self->cv_stack_len = 0;"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_init(blake3_hasher *self) { hasher_init_base(self, IV, 0); }"},{"Add":""},{"Add":"void blake3_hasher_init_keyed(blake3_hasher *self,"},{"Add":" const uint8_t key[BLAKE3_KEY_LEN]) {"},{"Add":" uint32_t key_words[8];"},{"Add":" load_key_words(key, key_words);"},{"Add":" hasher_init_base(self, key_words, KEYED_HASH);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_init_derive_key_raw(blake3_hasher *self, const void *context,"},{"Add":" size_t context_len) {"},{"Add":" blake3_hasher context_hasher;"},{"Add":" hasher_init_base(&context_hasher, IV, DERIVE_KEY_CONTEXT);"},{"Add":" blake3_hasher_update(&context_hasher, context, context_len);"},{"Add":" uint8_t context_key[BLAKE3_KEY_LEN];"},{"Add":" blake3_hasher_finalize(&context_hasher, context_key, BLAKE3_KEY_LEN);"},{"Add":" uint32_t context_key_words[8];"},{"Add":" load_key_words(context_key, context_key_words);"},{"Add":" hasher_init_base(self, context_key_words, DERIVE_KEY_MATERIAL);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_init_derive_key(blake3_hasher *self, const char *context) {"},{"Add":" blake3_hasher_init_derive_key_raw(self, context, strlen(context));"},{"Add":"}"},{"Add":""},{"Add":"// As described in hasher_push_cv() below, we do \"lazy merging\", delaying"},{"Add":"// merges until right before the next CV is about to be added. This is"},{"Add":"// different from the reference implementation. Another difference is that we"},{"Add":"// aren't always merging 1 chunk at a time. Instead, each CV might represent"},{"Add":"// any power-of-two number of chunks, as long as the smaller-above-larger stack"},{"Add":"// order is maintained. Instead of the \"count the trailing 0-bits\" algorithm"},{"Add":"// described in the spec, we use a \"count the total number of 1-bits\" variant"},{"Add":"// that doesn't require us to retain the subtree size of the CV on top of the"},{"Add":"// stack. The principle is the same: each CV that should remain in the stack is"},{"Add":"// represented by a 1-bit in the total number of chunks (or bytes) so far."},{"Add":"INLINE void hasher_merge_cv_stack(blake3_hasher *self, uint64_t total_len) {"},{"Add":" size_t post_merge_stack_len = (size_t)popcnt(total_len);"},{"Add":" while (self->cv_stack_len > post_merge_stack_len) {"},{"Add":" uint8_t *parent_node ="},{"Add":" &self->cv_stack[(self->cv_stack_len - 2) * BLAKE3_OUT_LEN];"},{"Add":" output_t output = parent_output(parent_node, self->key, self->chunk.flags);"},{"Add":" output_chaining_value(&output, parent_node);"},{"Add":" self->cv_stack_len -= 1;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"// In reference_impl.rs, we merge the new CV with existing CVs from the stack"},{"Add":"// before pushing it. We can do that because we know more input is coming, so"},{"Add":"// we know none of the merges are root."},{"Add":"//"},{"Add":"// This setting is different. We want to feed as much input as possible to"},{"Add":"// compress_subtree_wide(), without setting aside anything for the chunk_state."},{"Add":"// If the user gives us 64 KiB, we want to parallelize over all 64 KiB at once"},{"Add":"// as a single subtree, if at all possible."},{"Add":"//"},{"Add":"// This leads to two problems:"},{"Add":"// 1) This 64 KiB input might be the only call that ever gets made to update."},{"Add":"// In this case, the root node of the 64 KiB subtree would be the root node"},{"Add":"// of the whole tree, and it would need to be ROOT finalized. We can't"},{"Add":"// compress it until we know."},{"Add":"// 2) This 64 KiB input might complete a larger tree, whose root node is"},{"Add":"// similarly going to be the the root of the whole tree. For example, maybe"},{"Add":"// we have 196 KiB (that is, 128 + 64) hashed so far. We can't compress the"},{"Add":"// node at the root of the 256 KiB subtree until we know how to finalize it."},{"Add":"//"},{"Add":"// The second problem is solved with \"lazy merging\". That is, when we're about"},{"Add":"// to add a CV to the stack, we don't merge it with anything first, as the"},{"Add":"// reference impl does. Instead we do merges using the *previous* CV that was"},{"Add":"// added, which is sitting on top of the stack, and we put the new CV"},{"Add":"// (unmerged) on top of the stack afterwards. This guarantees that we never"},{"Add":"// merge the root node until finalize()."},{"Add":"//"},{"Add":"// Solving the first problem requires an additional tool,"},{"Add":"// compress_subtree_to_parent_node(). That function always returns the top"},{"Add":"// *two* chaining values of the subtree it's compressing. We then do lazy"},{"Add":"// merging with each of them separately, so that the second CV will always"},{"Add":"// remain unmerged. (That also helps us support extendable output when we're"},{"Add":"// hashing an input all-at-once.)"},{"Add":"INLINE void hasher_push_cv(blake3_hasher *self, uint8_t new_cv[BLAKE3_OUT_LEN],"},{"Add":" uint64_t chunk_counter) {"},{"Add":" hasher_merge_cv_stack(self, chunk_counter);"},{"Add":" memcpy(&self->cv_stack[self->cv_stack_len * BLAKE3_OUT_LEN], new_cv,"},{"Add":" BLAKE3_OUT_LEN);"},{"Add":" self->cv_stack_len += 1;"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_update(blake3_hasher *self, const void *input,"},{"Add":" size_t input_len) {"},{"Add":" // Explicitly checking for zero avoids causing UB by passing a null pointer"},{"Add":" // to memcpy. This comes up in practice with things like:"},{"Add":" // std::vector v;"},{"Add":" // blake3_hasher_update(&hasher, v.data(), v.size());"},{"Add":" if (input_len == 0) {"},{"Add":" return;"},{"Add":" }"},{"Add":""},{"Add":" const uint8_t *input_bytes = (const uint8_t *)input;"},{"Add":""},{"Add":" // If we have some partial chunk bytes in the internal chunk_state, we need"},{"Add":" // to finish that chunk first."},{"Add":" if (chunk_state_len(&self->chunk) > 0) {"},{"Add":" size_t take = BLAKE3_CHUNK_LEN - chunk_state_len(&self->chunk);"},{"Add":" if (take > input_len) {"},{"Add":" take = input_len;"},{"Add":" }"},{"Add":" chunk_state_update(&self->chunk, input_bytes, take);"},{"Add":" input_bytes += take;"},{"Add":" input_len -= take;"},{"Add":" // If we've filled the current chunk and there's more coming, finalize this"},{"Add":" // chunk and proceed. In this case we know it's not the root."},{"Add":" if (input_len > 0) {"},{"Add":" output_t output = chunk_state_output(&self->chunk);"},{"Add":" uint8_t chunk_cv[32];"},{"Add":" output_chaining_value(&output, chunk_cv);"},{"Add":" hasher_push_cv(self, chunk_cv, self->chunk.chunk_counter);"},{"Add":" chunk_state_reset(&self->chunk, self->key, self->chunk.chunk_counter + 1);"},{"Add":" } else {"},{"Add":" return;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Now the chunk_state is clear, and we have more input. If there's more than"},{"Add":" // a single chunk (so, definitely not the root chunk), hash the largest whole"},{"Add":" // subtree we can, with the full benefits of SIMD (and maybe in the future,"},{"Add":" // multi-threading) parallelism. Two restrictions:"},{"Add":" // - The subtree has to be a power-of-2 number of chunks. Only subtrees along"},{"Add":" // the right edge can be incomplete, and we don't know where the right edge"},{"Add":" // is going to be until we get to finalize()."},{"Add":" // - The subtree must evenly divide the total number of chunks up until this"},{"Add":" // point (if total is not 0). If the current incomplete subtree is only"},{"Add":" // waiting for 1 more chunk, we can't hash a subtree of 4 chunks. We have"},{"Add":" // to complete the current subtree first."},{"Add":" // Because we might need to break up the input to form powers of 2, or to"},{"Add":" // evenly divide what we already have, this part runs in a loop."},{"Add":" while (input_len > BLAKE3_CHUNK_LEN) {"},{"Add":" size_t subtree_len = round_down_to_power_of_2(input_len);"},{"Add":" uint64_t count_so_far = self->chunk.chunk_counter * BLAKE3_CHUNK_LEN;"},{"Add":" // Shrink the subtree_len until it evenly divides the count so far. We know"},{"Add":" // that subtree_len itself is a power of 2, so we can use a bitmasking"},{"Add":" // trick instead of an actual remainder operation. (Note that if the caller"},{"Add":" // consistently passes power-of-2 inputs of the same size, as is hopefully"},{"Add":" // typical, this loop condition will always fail, and subtree_len will"},{"Add":" // always be the full length of the input.)"},{"Add":" //"},{"Add":" // An aside: We don't have to shrink subtree_len quite this much. For"},{"Add":" // example, if count_so_far is 1, we could pass 2 chunks to"},{"Add":" // compress_subtree_to_parent_node. Since we'll get 2 CVs back, we'll still"},{"Add":" // get the right answer in the end, and we might get to use 2-way SIMD"},{"Add":" // parallelism. The problem with this optimization, is that it gets us"},{"Add":" // stuck always hashing 2 chunks. The total number of chunks will remain"},{"Add":" // odd, and we'll never graduate to higher degrees of parallelism. See"},{"Add":" // https://github.com/BLAKE3-team/BLAKE3/issues/69."},{"Add":" while ((((uint64_t)(subtree_len - 1)) & count_so_far) != 0) {"},{"Add":" subtree_len /= 2;"},{"Add":" }"},{"Add":" // The shrunken subtree_len might now be 1 chunk long. If so, hash that one"},{"Add":" // chunk by itself. Otherwise, compress the subtree into a pair of CVs."},{"Add":" uint64_t subtree_chunks = subtree_len / BLAKE3_CHUNK_LEN;"},{"Add":" if (subtree_len <= BLAKE3_CHUNK_LEN) {"},{"Add":" blake3_chunk_state chunk_state;"},{"Add":" chunk_state_init(&chunk_state, self->key, self->chunk.flags);"},{"Add":" chunk_state.chunk_counter = self->chunk.chunk_counter;"},{"Add":" chunk_state_update(&chunk_state, input_bytes, subtree_len);"},{"Add":" output_t output = chunk_state_output(&chunk_state);"},{"Add":" uint8_t cv[BLAKE3_OUT_LEN];"},{"Add":" output_chaining_value(&output, cv);"},{"Add":" hasher_push_cv(self, cv, chunk_state.chunk_counter);"},{"Add":" } else {"},{"Add":" // This is the high-performance happy path, though getting here depends"},{"Add":" // on the caller giving us a long enough input."},{"Add":" uint8_t cv_pair[2 * BLAKE3_OUT_LEN];"},{"Add":" compress_subtree_to_parent_node(input_bytes, subtree_len, self->key,"},{"Add":" self->chunk.chunk_counter,"},{"Add":" self->chunk.flags, cv_pair);"},{"Add":" hasher_push_cv(self, cv_pair, self->chunk.chunk_counter);"},{"Add":" hasher_push_cv(self, &cv_pair[BLAKE3_OUT_LEN],"},{"Add":" self->chunk.chunk_counter + (subtree_chunks / 2));"},{"Add":" }"},{"Add":" self->chunk.chunk_counter += subtree_chunks;"},{"Add":" input_bytes += subtree_len;"},{"Add":" input_len -= subtree_len;"},{"Add":" }"},{"Add":""},{"Add":" // If there's any remaining input less than a full chunk, add it to the chunk"},{"Add":" // state. In that case, also do a final merge loop to make sure the subtree"},{"Add":" // stack doesn't contain any unmerged pairs. The remaining input means we"},{"Add":" // know these merges are non-root. This merge loop isn't strictly necessary"},{"Add":" // here, because hasher_push_chunk_cv already does its own merge loop, but it"},{"Add":" // simplifies blake3_hasher_finalize below."},{"Add":" if (input_len > 0) {"},{"Add":" chunk_state_update(&self->chunk, input_bytes, input_len);"},{"Add":" hasher_merge_cv_stack(self, self->chunk.chunk_counter);"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_finalize(const blake3_hasher *self, uint8_t *out,"},{"Add":" size_t out_len) {"},{"Add":" blake3_hasher_finalize_seek(self, 0, out, out_len);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_finalize_seek(const blake3_hasher *self, uint64_t seek,"},{"Add":" uint8_t *out, size_t out_len) {"},{"Add":" // Explicitly checking for zero avoids causing UB by passing a null pointer"},{"Add":" // to memcpy. This comes up in practice with things like:"},{"Add":" // std::vector v;"},{"Add":" // blake3_hasher_finalize(&hasher, v.data(), v.size());"},{"Add":" if (out_len == 0) {"},{"Add":" return;"},{"Add":" }"},{"Add":""},{"Add":" // If the subtree stack is empty, then the current chunk is the root."},{"Add":" if (self->cv_stack_len == 0) {"},{"Add":" output_t output = chunk_state_output(&self->chunk);"},{"Add":" output_root_bytes(&output, seek, out, out_len);"},{"Add":" return;"},{"Add":" }"},{"Add":" // If there are any bytes in the chunk state, finalize that chunk and do a"},{"Add":" // roll-up merge between that chunk hash and every subtree in the stack. In"},{"Add":" // this case, the extra merge loop at the end of blake3_hasher_update"},{"Add":" // guarantees that none of the subtrees in the stack need to be merged with"},{"Add":" // each other first. Otherwise, if there are no bytes in the chunk state,"},{"Add":" // then the top of the stack is a chunk hash, and we start the merge from"},{"Add":" // that."},{"Add":" output_t output;"},{"Add":" size_t cvs_remaining;"},{"Add":" if (chunk_state_len(&self->chunk) > 0) {"},{"Add":" cvs_remaining = self->cv_stack_len;"},{"Add":" output = chunk_state_output(&self->chunk);"},{"Add":" } else {"},{"Add":" // There are always at least 2 CVs in the stack in this case."},{"Add":" cvs_remaining = self->cv_stack_len - 2;"},{"Add":" output = parent_output(&self->cv_stack[cvs_remaining * 32], self->key,"},{"Add":" self->chunk.flags);"},{"Add":" }"},{"Add":" while (cvs_remaining > 0) {"},{"Add":" cvs_remaining -= 1;"},{"Add":" uint8_t parent_block[BLAKE3_BLOCK_LEN];"},{"Add":" memcpy(parent_block, &self->cv_stack[cvs_remaining * 32], 32);"},{"Add":" output_chaining_value(&output, &parent_block[32]);"},{"Add":" output = parent_output(parent_block, self->key, self->chunk.flags);"},{"Add":" }"},{"Add":" output_root_bytes(&output, seek, out, out_len);"},{"Add":"}"},{"Add":""},{"Add":"void blake3_hasher_reset(blake3_hasher *self) {"},{"Add":" chunk_state_reset(&self->chunk, self->key, 0);"},{"Add":" self->cv_stack_len = 0;"},{"Add":"}"}]}},{"Replacement":{"inode":{"change":3,"pos":458},"path":"Makefile","line":15,"ins":{"up_context":[{"change":3,"pos":607}],"down_context":[{"change":3,"pos":2004}],"flag":"BLOCK","start":53385,"end":53399,"inode":{"change":3,"pos":458}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":607},"to":{"change":3,"start":607,"end":620},"introduced_by":3}],"inode":{"change":3,"pos":458}},"ins_contents":[{"Add":"OBJS = ani.o"}],"del_contents":[{"Del":"OBJS = ani.o\n"}]}},{"Edit":{"inode":{"change":3,"pos":458},"path":"Makefile","line":20,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":78838}],"down_context":[{"change":3,"pos":620}],"flag":"BLOCK","start":53400,"end":53605,"inode":{"change":3,"pos":458}}},"contents":[{"Add":"OBJS += blake3.o"},{"Add":"OBJS += blake3_dispatch.o"},{"Add":"OBJS += blake3_portable.o"},{"Add":""},{"Add":"ASM = blake3_avx2_x86-64_unix.S"},{"Add":"ASM += blake3_avx512_x86-64_unix.S"},{"Add":"ASM += blake3_sse2_x86-64_unix.S"},{"Add":"ASM += blake3_sse41_x86-64_unix.S"}]}},{"Replacement":{"inode":{"change":3,"pos":458},"path":"Makefile","line":31,"ins":{"up_context":[{"change":2,"pos":118}],"down_context":[{"change":3,"pos":676}],"flag":"BLOCK","start":53606,"end":53682,"inode":{"change":3,"pos":458}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":2,"pos":118},"to":{"change":2,"start":118,"end":187},"introduced_by":2}],"inode":{"change":3,"pos":458}},"ins_contents":[{"Add":"\t@$(CC) $(CFLAGS) -o $@ $(LDFLAGS) $(OBJS) $(ASM) $(ZSTD_LIB) $(XXHASH_LIB)"}],"del_contents":[{"Del":"\t@$(CC) $(CFLAGS) -o $@ $(LDFLAGS) $(OBJS) $(ZSTD_LIB) $(XXHASH_LIB)\n"}]}}],"owner":"laumann","repo":"ani","token":"qFYnMKsfRRdZskptLxrDmZMLKXKXQp71A0XN1TXbeBM=","login":null}

…

Dependencies

Change contents