bao_tree/
tree.rs

1//! Define a number of newtypes and operations on these newtypes
2//!
3//! Most operations are concerned with node indexes in an in order traversal of a binary tree.
4use std::{
5    fmt,
6    ops::{Add, Div, Mul, Sub},
7};
8
9use range_collections::range_set::RangeSetEntry;
10
11index_newtype! {
12    /// A number of blake3 chunks.
13    ///
14    /// This is a newtype for u64.
15    /// The blake3 chunk size is 1024 bytes.
16    pub struct ChunkNum(pub u64);
17}
18
19pub(crate) const BLAKE3_CHUNK_SIZE: usize = 1024;
20
21/// A block size.
22///
23/// Block sizes are powers of 2, with the smallest being 1024 bytes.
24/// They are encoded as the power of 2, minus 10, so 1 is 1024 bytes, 2 is 2048 bytes, etc.
25///
26/// Since only powers of 2 are valid, the log2 of the size in bytes / 1024 is given in the
27/// constructor. So a block size of 0 is 1024 bytes, 1 is 2048 bytes, etc.
28///
29/// The actual size in bytes can be computed with [BlockSize::bytes].
30#[repr(transparent)]
31#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
32pub struct BlockSize(pub(crate) u8);
33
34impl fmt::Display for BlockSize {
35    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36        fmt::Debug::fmt(&self, f)
37    }
38}
39
40impl BlockSize {
41    /// Create a block size from the log2 of the size in bytes / 1024
42    ///
43    /// 0 is 1024 bytes, 1 is 2048 bytes, etc.
44    pub const fn from_chunk_log(chunk_log: u8) -> Self {
45        Self(chunk_log)
46    }
47
48    /// Get the log2 of the number of 1 KiB blocks in a chunk.
49    pub const fn chunk_log(self) -> u8 {
50        self.0
51    }
52
53    /// The default block size, 1024 bytes
54    ///
55    /// This means that blocks and blake3 chunks are the same size.
56    pub const ZERO: BlockSize = BlockSize(0);
57
58    /// Number of bytes in a block at this level
59    pub const fn bytes(self) -> usize {
60        BLAKE3_CHUNK_SIZE << self.0
61    }
62
63    /// Compute a block size from bytes
64    pub const fn from_bytes(bytes: u64) -> Option<Self> {
65        if bytes.count_ones() != 1 {
66            // must be a power of 2
67            return None;
68        }
69        if bytes < 1024 {
70            // must be at least 1024 bytes
71            return None;
72        }
73        Some(Self((bytes.trailing_zeros() - 10) as u8))
74    }
75
76    /// Convert to an u32 for comparison with levels
77    pub(crate) const fn to_u32(self) -> u32 {
78        self.0 as u32
79    }
80}
81
82impl ChunkNum {
83    /// number of chunks that this number of bytes covers
84    ///
85    /// E.g. 1024 bytes is 1 chunk, 1025 bytes is 2 chunks
86    pub const fn chunks(size: u64) -> ChunkNum {
87        let mask = (1 << 10) - 1;
88        let part = ((size & mask) != 0) as u64;
89        let whole = size >> 10;
90        ChunkNum(whole + part)
91    }
92
93    /// number of chunks that this number of bytes covers
94    ///
95    /// E.g. 1024 bytes is 1 chunk, 1025 bytes is still 1 chunk
96    pub const fn full_chunks(size: u64) -> ChunkNum {
97        ChunkNum(size >> 10)
98    }
99
100    /// number of bytes that this number of chunks covers
101    pub const fn to_bytes(&self) -> u64 {
102        self.0 << 10
103    }
104}
bao_tree/tree.rs

bao_tree/
tree.rs
