Function left_subtree_len

pub fn left_subtree_len(input_len: u64) -> u64

Given the length in bytes of either a complete input or a subtree input, return the number of bytes that belong to its left child subtree. The rest belong to its right child subtree.

Concretely, this function returns the largest power-of-two number of bytes that’s strictly less than input_len. This leads to a tree where all left subtrees are “complete” and at least as large as their sibling right subtrees, as specified in section 2.1 of the BLAKE3 paper. For example, if an input is exactly two chunks, its left and right subtrees both get one chunk. But if an input is two chunks plus one more byte, then its left subtree gets two chunks, and its right subtree only gets one byte.

This function isn’t meaningful for one chunk of input, because chunks don’t have children. It currently panics in debug mode if input_len <= CHUNK_LEN.

Example

Hash a input of random length as two subtrees:

use blake3::hazmat::{left_subtree_len, merge_subtrees_root, HasherExt, Mode};
use blake3::{Hasher, CHUNK_LEN};

// Generate a random-length input. Note that to be split into two subtrees, the input length
// must be greater than CHUNK_LEN.
let input_len = rand::random_range(CHUNK_LEN + 1..1_000_000);
let mut input = vec![0; input_len];
rand::fill(&mut input[..]);

// Compute the left and right subtree hashes and then the root hash. left_subtree_len() tells
// us exactly where to split the input. Any other split would either panic (if we're lucky) or
// lead to an incorrect root hash.
let left_len = left_subtree_len(input_len as u64) as usize;
let left_subtree_cv = Hasher::new()
    .update(&input[..left_len])
    .finalize_non_root();
let right_subtree_cv = Hasher::new()
    .set_input_offset(left_len as u64)
    .update(&input[left_len..])
    .finalize_non_root();
let root_hash = merge_subtrees_root(&left_subtree_cv, &right_subtree_cv, Mode::Hash);

// Double check the answer.
assert_eq!(root_hash, blake3::hash(&input));