1mod bit;
 2mod delta;
 3mod error;
 4mod full;
 5mod inorder;
 6mod partial;
 7mod peaks;
 8mod proof;
 9
10#[cfg(test)]
11mod tests;
12
13// REEXPORTS
14// ================================================================================================
15pub use delta::MmrDelta;
16pub use error::MmrError;
17pub use full::Mmr;
18pub use inorder::InOrderIndex;
19pub use partial::PartialMmr;
20pub use peaks::MmrPeaks;
21pub use proof::MmrProof;
22
23use super::{Felt, Rpo256, RpoDigest, Word};
24
25// UTILITIES
26// ===============================================================================================
27
28/// Given a 0-indexed leaf position and the current forest, return the tree number responsible for
29/// the position.
30///
31/// Note:
32/// The result is a tree position `p`, it has the following interpretations. $p+1$ is the depth of
33/// the tree. Because the root element is not part of the proof, $p$ is the length of the
34/// authentication path. $2^p$ is equal to the number of leaves in this particular tree. and
35/// $2^(p+1)-1$ corresponds to size of the tree.
36const fn leaf_to_corresponding_tree(pos: usize, forest: usize) -> Option<u32> {
37    if pos >= forest {
38        None
39    } else {
40        // - each bit in the forest is a unique tree and the bit position its power-of-two size
41        // - each tree owns a consecutive range of positions equal to its size from left-to-right
42        // - this means the first tree owns from `0` up to the `2^k_0` first positions, where `k_0`
43        //   is the highest true bit position, the second tree from `2^k_0 + 1` up to `2^k_1` where
44        //   `k_1` is the second highest bit, so on.
45        // - this means the highest bits work as a category marker, and the position is owned by the
46        //   first tree which doesn't share a high bit with the position
47        let before = forest & pos;
48        let after = forest ^ before;
49        let tree = after.ilog2();
50
51        Some(tree)
52    }
53}
54
55/// Return the total number of nodes of a given forest
56///
57/// Panics:
58///
59/// This will panic if the forest has size greater than `usize::MAX / 2`
60const fn nodes_in_forest(forest: usize) -> usize {
61    // - the size of a perfect binary tree is $2^{k+1}-1$ or $2*2^k-1$
62    // - the forest represents the sum of $2^k$ so a single multiplication is necessary
63    // - the number of `-1` is the same as the number of trees, which is the same as the number
64    // bits set
65    let tree_count = forest.count_ones() as usize;
66    forest * 2 - tree_count
67}