//! Low-level tree manipulations and other sharp tools

//!

//! The target audience for this module is projects like [Bao](https://github.com/oconnor663/bao),

//! which work directly with the interior hashes ("chaining values") of BLAKE3 chunks and subtrees.

//! For example, you could use these functions to implement a BitTorrent-like protocol using the

//! BLAKE3 tree structure, or to hash an input that's distributed across different machines. These

//! use cases are advanced, and most applications don't need this module. Also:

//!

//! <div class="warning">

//!

//! **Warning:** This module is *hazardous material*. If you've heard folks say *don't roll your

//! own crypto,* this is the sort of thing they're talking about. These functions have complicated

//! requirements, and any mistakes will give you garbage output and/or break the security

//! properties that BLAKE3 is supposed to have. Read section 2.1 of [the BLAKE3

//! paper](https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf) to understand the

//! tree structure you need to maintain. Test your code against [`blake3::hash`](../fn.hash.html)

//! and make sure you can get the same outputs for [lots of different

//! inputs](https://github.com/BLAKE3-team/BLAKE3/blob/master/test_vectors/test_vectors.json).

//!

//! </div>

//!

//! On the other hand:

//!

//! <div class="warning">

//!

//! **Encouragement:** Playing with these functions is a great way to learn how BLAKE3 works on the

//! inside. Have fun!

//!

//! </div>

//!

//! The main entrypoint for this module is the [`HasherExt`] trait, particularly the

//! [`set_input_offset`](HasherExt::set_input_offset) and

//! [`finalize_non_root`](HasherExt::finalize_non_root) methods. These let you compute the chaining

//! values of individual chunks or subtrees. You then combine these chaining values into larger

//! subtrees using [`merge_subtrees_non_root`] and finally (once at the very top)

//! [`merge_subtrees_root`] or [`merge_subtrees_root_xof`].

//!

//! # Examples

//!

//! Here's an example of computing all the interior hashes in a 3-chunk tree:

//!

//! ```text

//!            root

//!          /      \

//!      parent      \

//!    /       \      \

//! chunk0  chunk1  chunk2

//! ```

//!

//! ```

//! # fn main() {

//! use blake3::{Hasher, CHUNK_LEN};

//! use blake3::hazmat::{merge_subtrees_non_root, merge_subtrees_root, Mode};

//! use blake3::hazmat::HasherExt; // an extension trait for Hasher

//!

//! let chunk0 = [b'a'; CHUNK_LEN];

//! let chunk1 = [b'b'; CHUNK_LEN];

//! let chunk2 = [b'c'; 42]; // The final chunk can be short.

//!

//! // Compute the non-root hashes ("chaining values") of all three chunks. Chunks or subtrees

//! // that don't begin at the start of the input use `set_input_offset` to say where they begin.

//! let chunk0_cv = Hasher::new()

//!     // .set_input_offset(0) is the default.

//!     .update(&chunk0)

//!     .finalize_non_root();

//! let chunk1_cv = Hasher::new()

//!     .set_input_offset(CHUNK_LEN as u64)

//!     .update(&chunk1)

//!     .finalize_non_root();

//! let chunk2_cv = Hasher::new()

//!     .set_input_offset(2 * CHUNK_LEN as u64)

//!     .update(&chunk2)

//!     .finalize_non_root();

//!

//! // Join the first two chunks with a non-root parent node and compute its chaining value.

//! let parent_cv = merge_subtrees_non_root(&chunk0_cv, &chunk1_cv, Mode::Hash);

//!

//! // Join that parent node and the third chunk with a root parent node and compute the hash.

//! let root_hash = merge_subtrees_root(&parent_cv, &chunk2_cv, Mode::Hash);

//!

//! // Double check that we got the right answer.

//! let mut combined_input = Vec::new();

//! combined_input.extend_from_slice(&chunk0);

//! combined_input.extend_from_slice(&chunk1);

//! combined_input.extend_from_slice(&chunk2);

//! assert_eq!(root_hash, blake3::hash(&combined_input));

//! # }

//! ```

//!

//! Hashing many chunks together is important for performance, because it allows the implementation

//! to use SIMD parallelism internally. ([AVX-512](https://en.wikipedia.org/wiki/AVX-512) for

//! example needs 16 chunks to really get going.) We can reproduce `parent_cv` by hashing `chunk0`

//! and `chunk1` at the same time:

//!

//! ```

//! # fn main() {

//! # use blake3::{Hasher, CHUNK_LEN};

//! # use blake3::hazmat::{Mode, HasherExt, merge_subtrees_non_root, merge_subtrees_root};

//! # let chunk0 = [b'a'; CHUNK_LEN];

//! # let chunk1 = [b'b'; CHUNK_LEN];

//! # let chunk0_cv = Hasher::new().update(&chunk0).finalize_non_root();

//! # let chunk1_cv = Hasher::new().set_input_offset(CHUNK_LEN as u64).update(&chunk1).finalize_non_root();

//! # let parent_cv = merge_subtrees_non_root(&chunk0_cv, &chunk1_cv, Mode::Hash);

//! # let mut combined_input = Vec::new();

//! # combined_input.extend_from_slice(&chunk0);

//! # combined_input.extend_from_slice(&chunk1);

//! let left_subtree_cv = Hasher::new()

//!     // .set_input_offset(0) is the default.

//!     .update(&combined_input[..2 * CHUNK_LEN])

//!     .finalize_non_root();

//! assert_eq!(left_subtree_cv, parent_cv);

//!

//! // Using multiple updates gives the same answer, though it's not as efficient.

//! let mut subtree_hasher = Hasher::new();

//! // Again, .set_input_offset(0) is the default.

//! subtree_hasher.update(&chunk0);

//! subtree_hasher.update(&chunk1);

//! assert_eq!(left_subtree_cv, subtree_hasher.finalize_non_root());

//! # }

//! ```

//!

//! However, hashing multiple chunks together **must** respect the overall tree structure. Hashing

//! `chunk0` and `chunk1` together is valid, but hashing `chunk1` and `chunk2` together is

//! incorrect and gives a garbage result that will never match a standard BLAKE3 hash. The

//! implementation includes a few best-effort asserts to catch some of these mistakes, but these

//! checks aren't guaranteed. For example, this second call to `update` currently panics:

//!

//! ```should_panic

//! # fn main() {

//! # use blake3::{Hasher, CHUNK_LEN};

//! # use blake3::hazmat::HasherExt;

//! # let chunk0 = [b'a'; CHUNK_LEN];

//! # let chunk1 = [b'b'; CHUNK_LEN];

//! # let chunk2 = [b'c'; 42];

//! let oops = Hasher::new()

//!     .set_input_offset(CHUNK_LEN as u64)

//!     .update(&chunk1)

//!     // PANIC: "the subtree starting at 1024 contains at most 1024 bytes"

//!     .update(&chunk2)

//!     .finalize_non_root();

//! # }

//! ```

//!

//! For more on valid tree structures, see the docs for and [`left_subtree_len`] and

//! [`max_subtree_len`], and see section 2.1 of [the BLAKE3

//! paper](https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf). Note that the

//! merging functions ([`merge_subtrees_root`] and friends) don't know the shape of the left and

//! right subtrees you're giving them, and they can't help you catch mistakes. The best way to

//! catch mistakes with these is to compare your root output to the [`blake3::hash`](crate::hash)

//! of the same input.

use crate::platform::Platform;

use crate::{CVWords, Hasher, CHUNK_LEN, IV, KEY_LEN, OUT_LEN};

/// Extension methods for [`Hasher`]. This is the main entrypoint to the `hazmat` module.

pub trait HasherExt {

    /// Similar to [`Hasher::new_derive_key`] but using a pre-hashed [`ContextKey`] from

    /// [`hash_derive_key_context`].

    ///

    /// The [`hash_derive_key_context`] function is the _only_ valid source of the [`ContextKey`].

    /// Any other source ([`hash`](crate::hash), [`keyed_hash`](crate::keyed_hash), arbitrary bytes

    /// from the caller) violates the security requirements.

    ///

    /// Calling [`derive_key`](crate::derive_key) or [`Hasher::new_derive_key`] in a loop will

    /// re-hash the context string every time. This constructor function is a performance

    /// optimization to avoid that repeated work. If you hardcode the [`ContextKey`], the

    /// derive-key mode becomes zero-overhead, like the keyed mode.

    ///

    /// # Example

    ///

    /// ```

    /// use blake3::Hasher;

    /// use blake3::hazmat::HasherExt;

    ///

    /// let context_key = blake3::hazmat::hash_derive_key_context("foo");

    /// let mut hasher = Hasher::new_from_context_key(&context_key);

    /// hasher.update(b"bar");

    /// let derived_key = *hasher.finalize().as_bytes();

    ///

    /// assert_eq!(derived_key, blake3::derive_key("foo", b"bar"));

    /// ```

    fn new_from_context_key(context_key: &ContextKey) -> Self;

    /// Configure the `Hasher` to process a chunk or subtree starting at `offset` bytes into the

    /// whole input.

    ///

    /// You must call this function before processing any input with [`update`](Hasher::update) or

    /// similar. This step isn't required for the first chunk, or for a subtree that includes the

    /// first chunk (i.e. when the `offset` is zero), but it's required for all other chunks and

    /// subtrees.

    ///

    /// The starting input offset of a subtree implies a maximum possible length for that subtree.

    /// See [`max_subtree_len`] and section 2.1 of [the BLAKE3

    /// paper](https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf). Note that only

    /// subtrees along the right edge of the whole tree can have a length less than their maximum

    /// possible length.

    ///

    /// See the [module level examples](index.html#examples).

    ///

    /// # Panics

    ///

    /// This function panics if the `Hasher` has already accepted any input with

    /// [`update`](Hasher::update) or similar.

    ///

    /// This should always be paired with [`finalize_non_root`](HasherExt::finalize_non_root). It's

    /// never correct to use a non-zero input offset with [`finalize`](Hasher::finalize) or

    /// [`finalize_xof`](Hasher::finalize_xof). The `offset` must also be a multiple of

    /// `CHUNK_LEN`. Violating either of these rules will currently fail an assertion and panic,

    /// but this is not guaranteed.

    fn set_input_offset(&mut self, offset: u64) -> &mut Self;

    /// Finalize the non-root hash ("chaining value") of the current chunk or subtree.

    ///

    /// Afterwards you can merge subtree chaining values into parent nodes using

    /// [`merge_subtrees_non_root`] and ultimately into the root node with either

    /// [`merge_subtrees_root`] (similar to [`Hasher::finalize`]) or [`merge_subtrees_root_xof`]

    /// (similar to [`Hasher::finalize_xof`]).

    ///

    /// See the [module level examples](index.html#examples), particularly the discussion of valid

    /// tree structures.

    fn finalize_non_root(&self) -> ChainingValue;

}

impl HasherExt for Hasher {

    fn new_from_context_key(context_key: &[u8; KEY_LEN]) -> Hasher {

        let context_key_words = crate::platform::words_from_le_bytes_32(context_key);

        Hasher::new_internal(&context_key_words, crate::DERIVE_KEY_MATERIAL)

    }

    fn set_input_offset(&mut self, offset: u64) -> &mut Hasher {

        assert_eq!(self.count(), 0, "hasher has already accepted input");

        assert_eq!(

            offset % CHUNK_LEN as u64,

            0,

            "offset ({offset}) must be a chunk boundary (divisible by {CHUNK_LEN})",

        );

        let counter = offset / CHUNK_LEN as u64;

        self.chunk_state.chunk_counter = counter;

        self.initial_chunk_counter = counter;

        self

    }

    fn finalize_non_root(&self) -> ChainingValue {

        assert_ne!(self.count(), 0, "empty subtrees are never valid");

        self.final_output().chaining_value()

    }

}

/// The maximum length of a subtree in bytes, given its starting offset in bytes

///

/// If you try to hash more than this many bytes as one subtree, you'll end up merging parent nodes

/// that shouldn't be merged, and your output will be garbage. [`Hasher::update`] will currently

/// panic in this case, but this is not guaranteed.

///

/// For input offset zero (the default), there is no maximum length, and this function returns

/// `None`. For all other offsets it returns `Some`. Note that valid offsets must be a multiple of

/// [`CHUNK_LEN`] (1024); it's not possible to start hashing a chunk in the middle.

///

/// In the example tree below, chunks are numbered by their _0-based index_. The subtree that

/// _starts_ with chunk 3, i.e. `input_offset = 3 * CHUNK_LEN`, includes only that one chunk, so

/// its max length is `Some(CHUNK_LEN)`. The subtree that starts with chunk 6 includes chunk 7 but

/// not chunk 8, so its max length is `Some(2 * CHUNK_LEN)`. The subtree that starts with chunk 12

/// includes chunks 13, 14, and 15, but if the tree were bigger it would not include chunk 16, so

/// its max length is `Some(4 * CHUNK_LEN)`. One way to think about the rule here is that, if you

/// go beyond the max subtree length from a given starting offset, you start dealing with subtrees

/// that include chunks _to the left_ of where you started.

///

/// ```text

///                           root

///                 /                       \

///              .                             .

///        /           \                 /           \

///       .             .               .             .

///    /    \         /    \         /    \         /    \

///   .      .       .      .       .      .       .      .

///  / \    / \     / \    / \     / \    / \     / \    / \

/// 0  1   2  3    4  5   6  7    8  9   10 11   12 13  14 15

/// ```

///

/// The general rule turns out to be that for a subtree starting at a 0-based chunk index N greater

/// than zero, the maximum number of chunks in that subtree is the largest power-of-two that

/// divides N, which is given by `1 << N.trailing_zeros()`.

///

/// This function can be useful for writing tests or debug assertions, but it's actually rare to

/// use this for real control flow. Callers who split their input recursively using

/// [`left_subtree_len`] will automatically satisfy the `max_subtree_len` bound and don't

/// necessarily need to check. It's also common to choose some fixed power-of-two subtree size, say

/// 64 chunks, and divide your input up into slices of that fixed length (with the final slice

/// possibly short). This approach also automatically satisfies the `max_subtree_len` bound and

/// doesn't need to check. Proving that this is true can be an interesting exercise. Note that

/// chunks 0, 4, 8, and 12 all begin subtrees of at least 4 chunks in the example tree above.

///

/// # Panics

///

/// This function currently panics if `input_offset` is not a multiple of `CHUNK_LEN`. This is not

/// guaranteed.

#[inline(always)]

pub fn max_subtree_len(input_offset: u64) -> Option<u64> {

    if input_offset == 0 {

        return None;

    }

    assert_eq!(input_offset % CHUNK_LEN as u64, 0);

    let counter = input_offset / CHUNK_LEN as u64;

    let max_chunks = 1 << counter.trailing_zeros();

    Some(max_chunks * CHUNK_LEN as u64)

}

#[test]

fn test_max_subtree_len() {

    assert_eq!(max_subtree_len(0), None);

    // (chunk index, max chunks)

    let cases = [

        (1, 1),

        (2, 2),

        (3, 1),

        (4, 4),

        (5, 1),

        (6, 2),

        (7, 1),

        (8, 8),

    ];

    for (chunk_index, max_chunks) in cases {

        let input_offset = chunk_index * CHUNK_LEN as u64;

        assert_eq!(

            max_subtree_len(input_offset),

            Some(max_chunks * CHUNK_LEN as 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](https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf). For example, if an

/// input is exactly two chunks, the left subtree gets the first chunk and the right subtree gets

/// the second 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:

///

/// ```

/// # #[cfg(feature = "std")] {

/// 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));

/// # }

/// ```

#[inline(always)]

pub fn left_subtree_len(input_len: u64) -> u64 {

    debug_assert!(input_len > CHUNK_LEN as u64);

    // Note that .next_power_of_two() is greater than *or equal*.

    ((input_len + 1) / 2).next_power_of_two()

}

#[test]

fn test_left_subtree_len() {

    assert_eq!(left_subtree_len(1025), 1024);

    for boundary_case in [2, 4, 8, 16, 32, 64] {

        let input_len = boundary_case * CHUNK_LEN as u64;

        assert_eq!(left_subtree_len(input_len - 1), input_len / 2);

        assert_eq!(left_subtree_len(input_len), input_len / 2);

        assert_eq!(left_subtree_len(input_len + 1), input_len);

    }

}

/// The `mode` argument to [`merge_subtrees_root`] and friends

///

/// See the [module level examples](index.html#examples).

#[derive(Copy, Clone, Debug)]

pub enum Mode<'a> {

    /// Corresponding to [`hash`](crate::hash)

    Hash,

    /// Corresponding to [`keyed_hash`](crate::hash)

    KeyedHash(&'a [u8; KEY_LEN]),

    /// Corresponding to [`derive_key`](crate::hash)

    ///

    /// The [`ContextKey`] comes from [`hash_derive_key_context`].

    DeriveKeyMaterial(&'a ContextKey),

}

impl<'a> Mode<'a> {

    fn key_words(&self) -> CVWords {

        match self {

            Mode::Hash => *IV,

            Mode::KeyedHash(key) => crate::platform::words_from_le_bytes_32(key),

            Mode::DeriveKeyMaterial(cx_key) => crate::platform::words_from_le_bytes_32(cx_key),

        }

    }

    fn flags_byte(&self) -> u8 {

        match self {

            Mode::Hash => 0,

            Mode::KeyedHash(_) => crate::KEYED_HASH,

            Mode::DeriveKeyMaterial(_) => crate::DERIVE_KEY_MATERIAL,

        }

    }

}

/// "Chaining value" is the academic term for a non-root or non-final hash.

///

/// Besides just sounding fancy, it turns out there are [security

/// reasons](https://jacko.io/tree_hashing.html) to be careful about the difference between

/// (root/final) hashes and (non-root/non-final) chaining values.

pub type ChainingValue = [u8; OUT_LEN];

fn merge_subtrees_inner(

    left_child: &ChainingValue,

    right_child: &ChainingValue,

    mode: Mode,

) -> crate::Output {

    crate::parent_node_output(

        &left_child,

        &right_child,

        &mode.key_words(),

        mode.flags_byte(),

        Platform::detect(),

    )

}

/// Compute a non-root parent node chaining value from two child chaining values.

///

/// See the [module level examples](index.html#examples), particularly the discussion of valid tree

/// structures. The left and right child chaining values can come from either

/// [`Hasher::finalize_non_root`](HasherExt::finalize_non_root) or other calls to

/// `merge_subtrees_non_root`. "Chaining value" is the academic term for a non-root or non-final

/// hash.

pub fn merge_subtrees_non_root(

    left_child: &ChainingValue,

    right_child: &ChainingValue,

    mode: Mode,

) -> ChainingValue {

    merge_subtrees_inner(left_child, right_child, mode).chaining_value()

}

/// Compute a root hash from two child chaining values.

///

/// See the [module level examples](index.html#examples), particularly the discussion of valid tree

/// structures. The left and right child chaining values can come from either

/// [`Hasher::finalize_non_root`](HasherExt::finalize_non_root) or [`merge_subtrees_non_root`].

/// "Chaining value" is the academic term for a non-root or non-final hash.

///

/// Note that inputs of [`CHUNK_LEN`] or less don't produce any parent nodes and can't be hashed

/// using this function. In that case you must get the root hash from [`Hasher::finalize`] (or just

/// [`blake3::hash`](crate::hash)).

pub fn merge_subtrees_root(

    left_child: &ChainingValue,

    right_child: &ChainingValue,

    mode: Mode,

) -> crate::Hash {

    merge_subtrees_inner(left_child, right_child, mode).root_hash()

}

/// Build a root [`OutputReader`](crate::OutputReader) from two child chaining values.

///

/// See also the [module level examples](index.html#examples), particularly the discussion of valid

/// tree structures. The left and right child chaining values can come from either

/// [`Hasher::finalize_non_root`](HasherExt::finalize_non_root) or [`merge_subtrees_non_root`].

/// "Chaining value" is the academic term for a non-root or non-final hash.

///

/// Note that inputs of [`CHUNK_LEN`] or less don't produce any parent nodes and can't be hashed

/// using this function. In that case you must get the `OutputReader` from

/// [`Hasher::finalize_xof`].

///

/// # Example

///

/// ```

/// use blake3::hazmat::{merge_subtrees_root_xof, HasherExt, Mode};

/// use blake3::{Hasher, CHUNK_LEN};

///

/// // Hash a 2-chunk subtree in steps. Note that only

/// // the final chunk can be shorter than CHUNK_LEN.

/// let chunk0 = &[42; CHUNK_LEN];

/// let chunk1 = b"hello world";

/// let chunk0_cv = Hasher::new()

///     .update(chunk0)

///     .finalize_non_root();

/// let chunk1_cv = Hasher::new()

///     .set_input_offset(CHUNK_LEN as u64)

///     .update(chunk1)

///     .finalize_non_root();

///

/// // Obtain a blake3::OutputReader at the root and extract 1000 bytes.

/// let mut output_reader = merge_subtrees_root_xof(&chunk0_cv, &chunk1_cv, Mode::Hash);

/// let mut output_bytes = [0; 1_000];

/// output_reader.fill(&mut output_bytes);

///

/// // Double check the answer.

/// let mut hasher = Hasher::new();

/// hasher.update(chunk0);

/// hasher.update(chunk1);

/// let mut expected = [0; 1_000];

/// hasher.finalize_xof().fill(&mut expected);

/// assert_eq!(output_bytes, expected);

/// ```

pub fn merge_subtrees_root_xof(

    left_child: &ChainingValue,

    right_child: &ChainingValue,

    mode: Mode,

) -> crate::OutputReader {

    crate::OutputReader::new(merge_subtrees_inner(left_child, right_child, mode))

}

/// An alias to distinguish [`hash_derive_key_context`] outputs from other keys.

pub type ContextKey = [u8; KEY_LEN];

/// Hash a [`derive_key`](crate::derive_key) context string and return a [`ContextKey`].

///

/// This has the same security requirement as [`derive_key`](crate::derive_key). **The context

/// string should be hardcoded, globally unique, and application-specific.**

///

/// The _only_ valid uses for the returned [`ContextKey`] are

/// [`new_from_context_key`](HasherExt::new_from_context_key) and [`Mode::DeriveKeyMaterial`]

/// (together with the merge subtree functions).

///

/// # Example

///

/// ```

/// use blake3::Hasher;

/// use blake3::hazmat::HasherExt;

///

/// let context_key = blake3::hazmat::hash_derive_key_context("foo");

/// let mut hasher = Hasher::new_from_context_key(&context_key);

/// hasher.update(b"bar");

/// let derived_key = *hasher.finalize().as_bytes();

///

/// assert_eq!(derived_key, blake3::derive_key("foo", b"bar"));

/// ```

pub fn hash_derive_key_context(context: &str) -> ContextKey {

    crate::hash_all_at_once::<crate::join::SerialJoin>(

        context.as_bytes(),

        IV,

        crate::DERIVE_KEY_CONTEXT,

    )

    .root_hash()

    .0

}

#[cfg(test)]

mod test {

    use super::*;

    #[test]

    #[should_panic]

    fn test_empty_subtree_should_panic() {

        Hasher::new().finalize_non_root();

    }

    #[test]

    #[should_panic]

    fn test_unaligned_offset_should_panic() {

        Hasher::new().set_input_offset(1);

    }

    #[test]

    #[should_panic]

    fn test_hasher_already_accepted_input_should_panic() {

        Hasher::new().update(b"x").set_input_offset(0);

    }

    #[test]

    #[should_panic]

    fn test_too_much_input_should_panic() {

        Hasher::new()

            .set_input_offset(CHUNK_LEN as u64)

            .update(&[0; CHUNK_LEN + 1]);

    }

    #[test]

    #[should_panic]

    fn test_set_input_offset_cant_finalize() {

        Hasher::new().set_input_offset(CHUNK_LEN as u64).finalize();

    }

    #[test]

    #[should_panic]

    fn test_set_input_offset_cant_finalize_xof() {

        Hasher::new()

            .set_input_offset(CHUNK_LEN as u64)

            .finalize_xof();

    }

    #[test]

    fn test_grouped_hash() {

        const MAX_CHUNKS: usize = (crate::test::TEST_CASES_MAX + 1) / CHUNK_LEN;

        let mut input_buf = [0; crate::test::TEST_CASES_MAX];

        crate::test::paint_test_input(&mut input_buf);

        for subtree_chunks in [1, 2, 4, 8, 16, 32] {

            #[cfg(feature = "std")]

            dbg!(subtree_chunks);

            let subtree_len = subtree_chunks * CHUNK_LEN;

            for &case in crate::test::TEST_CASES {

                if case <= subtree_len {

                    continue;

                }

                #[cfg(feature = "std")]

                dbg!(case);

                let input = &input_buf[..case];

                let expected_hash = crate::hash(input);

                // Collect all the group chaining values.

                let mut chaining_values = arrayvec::ArrayVec::<ChainingValue, MAX_CHUNKS>::new();

                let mut subtree_offset = 0;

                while subtree_offset < input.len() {

                    let take = core::cmp::min(subtree_len, input.len() - subtree_offset);

                    let subtree_input = &input[subtree_offset..][..take];

                    let subtree_cv = Hasher::new()

                        .set_input_offset(subtree_offset as u64)

                        .update(subtree_input)

                        .finalize_non_root();

                    chaining_values.push(subtree_cv);

                    subtree_offset += take;

                }

                // Compress all the chaining_values together, layer by layer.

                assert!(chaining_values.len() >= 2);

                while chaining_values.len() > 2 {

                    let n = chaining_values.len();

                    // Merge each side-by-side pair in place, overwriting the front half of the

                    // array with the merged results. This moves us "up one level" in the tree.

                    for i in 0..(n / 2) {

                        chaining_values[i] = merge_subtrees_non_root(

                            &chaining_values[2 * i],

                            &chaining_values[2 * i + 1],

                            Mode::Hash,

                        );

                    }

                    // If there's an odd CV out, it moves up.

                    if n % 2 == 1 {

                        chaining_values[n / 2] = chaining_values[n - 1];

                    }

                    chaining_values.truncate(n / 2 + n % 2);

                }

                assert_eq!(chaining_values.len(), 2);

                let root_hash =

                    merge_subtrees_root(&chaining_values[0], &chaining_values[1], Mode::Hash);

                assert_eq!(expected_hash, root_hash);

            }

        }

    }

    #[test]

    fn test_keyed_hash_xof() {

        let group0 = &[42; 4096];

        let group1 = &[43; 4095];

        let mut input = [0; 8191];

        input[..4096].copy_from_slice(group0);

        input[4096..].copy_from_slice(group1);

        let key = &[44; 32];

        let mut expected_output = [0; 100];

        Hasher::new_keyed(&key)

            .update(&input)

            .finalize_xof()

            .fill(&mut expected_output);

        let mut hazmat_output = [0; 100];

        let left = Hasher::new_keyed(key).update(group0).finalize_non_root();

        let right = Hasher::new_keyed(key)

            .set_input_offset(group0.len() as u64)

            .update(group1)

            .finalize_non_root();

        merge_subtrees_root_xof(&left, &right, Mode::KeyedHash(&key)).fill(&mut hazmat_output);

        assert_eq!(expected_output, hazmat_output);

    }

    #[test]

    fn test_derive_key() {

        let context = "foo";

        let mut input = [0; 1025];

        crate::test::paint_test_input(&mut input);

        let expected = crate::derive_key(context, &input);

        let cx_key = hash_derive_key_context(context);

        let left = Hasher::new_from_context_key(&cx_key)

            .update(&input[..1024])

            .finalize_non_root();

        let right = Hasher::new_from_context_key(&cx_key)

            .set_input_offset(1024)

            .update(&input[1024..])

            .finalize_non_root();

        let derived_key = merge_subtrees_root(&left, &right, Mode::DeriveKeyMaterial(&cx_key)).0;

        assert_eq!(expected, derived_key);

    }

}