dig_merkle/size.rs
1//! The `.dig` store size as a power-of-2 bucket (SPEC §2, CLVM alist key `"sz"`).
2//!
3//! A `.dig` store's on-chain size hint is quantised to a power-of-2 **bucket** rather than an exact
4//! byte count, so it reveals only a coarse magnitude and encodes in a single CLVM byte. The bucket
5//! exponent `k ∈ 0..=10` maps to `2^k MB`, where — and this is the canonical unit contract that
6//! dig-store must not drift from — **1 MB = 1 MiB = 2^20 bytes**. The ladder is therefore:
7//!
8//! | k | size | | k | size |
9//! |---|------|-----|---|------|
10//! | 0 | 1 MB | | 6 | 64 MB |
11//! | 1 | 2 MB | | 7 | 128 MB |
12//! | 2 | 4 MB | | 8 | 256 MB |
13//! | 3 | 8 MB | | 9 | 512 MB |
14//! | 4 | 16 MB | | 10 | 1024 MB = 1 GB |
15//! | 5 | 32 MB |
16//!
17//! [`SizeBucket`] is the CANONICAL source of the ladder AND the byte→bucket mapping
18//! ([`SizeBucket::for_byte_len`]) so a consumer (dig-store's SIZE PROOF) never re-derives it and drifts.
19
20use crate::{MerkleError, MerkleResult};
21
22/// The largest bucket exponent: `k = 10` is `2^10 MiB = 1024 MB = 1 GB`, the ceiling a `.dig` store
23/// size is quantised into. A byte length above `2^30` (1 GiB) has no bucket and is rejected.
24const MAX_EXPONENT: u8 = 10;
25
26/// A `.dig` store size quantised to a power-of-2 bucket: exponent `k ∈ 0..=10` ↔ `2^k MiB`
27/// (1 MB..1 GB). See the module docs for the full ladder and the canonical unit (1 MB = 1 MiB).
28///
29/// A `SizeBucket` is always valid by construction — the only ways to make one
30/// ([`from_exponent`](Self::from_exponent), [`for_byte_len`](Self::for_byte_len)) reject an
31/// out-of-range value — so `exponent()` is guaranteed to be in `0..=10`.
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub struct SizeBucket {
34 /// The validated bucket exponent, always in `0..=10`.
35 k: u8,
36}
37
38impl SizeBucket {
39 /// Builds a bucket from its exponent `k`, rejecting `k > 10` (the ladder ceiling).
40 ///
41 /// # Errors
42 ///
43 /// Returns [`MerkleError::InvalidSize`] if `k > 10` — there is no bucket larger than 1 GB.
44 pub fn from_exponent(k: u8) -> MerkleResult<Self> {
45 if k > MAX_EXPONENT {
46 return Err(MerkleError::InvalidSize(format!(
47 "size-bucket exponent {k} exceeds the maximum {MAX_EXPONENT} (1 GB)"
48 )));
49 }
50 Ok(Self { k })
51 }
52
53 /// The validated bucket exponent, always in `0..=10`.
54 pub fn exponent(&self) -> u8 {
55 self.k
56 }
57
58 /// The bucket size in megabytes (`2^k`, with 1 MB = 1 MiB): 1, 2, 4, … 1024.
59 pub fn megabytes(&self) -> u32 {
60 1u32 << self.k
61 }
62
63 /// The bucket size in bytes (`2^(k+20)`): the exact byte capacity of this bucket.
64 pub fn byte_len(&self) -> u64 {
65 1u64 << (u32::from(self.k) + 20)
66 }
67
68 /// The CANONICAL byte length → bucket mapping: the SMALLEST `k` whose bucket (`2^(k+20)` bytes)
69 /// is at least `bytes`. A store of 0 or 1 byte → `k = 0`; exactly 1 MiB → `k = 0`; 1 MiB + 1 →
70 /// `k = 1`; exactly 1 GiB → `k = 10`.
71 ///
72 /// This is the ergonomics dig-store's SIZE PROOF consumes so the ladder lives in ONE place.
73 ///
74 /// # Errors
75 ///
76 /// Returns [`MerkleError::InvalidSize`] if `bytes > 2^30` (1 GiB) — beyond the ladder ceiling.
77 pub fn for_byte_len(bytes: u64) -> MerkleResult<Self> {
78 for k in 0..=MAX_EXPONENT {
79 // 2^(k+20) is the byte capacity of bucket k; the first that fits `bytes` wins.
80 if bytes <= (1u64 << (u32::from(k) + 20)) {
81 return Ok(Self { k });
82 }
83 }
84 Err(MerkleError::InvalidSize(format!(
85 "size {bytes} bytes exceeds the maximum bucket 2^30 (1 GiB)"
86 )))
87 }
88}
89
90#[cfg(test)]
91mod tests {
92 use super::*;
93
94 /// The exponent→megabytes ladder is exactly the powers of two 1..1024, `k = 10` is 1 GB, and
95 /// `byte_len()` is `2^(k+20)` for every bucket (SPEC §2).
96 #[test]
97 fn exponent_to_megabytes_ladder() {
98 let expected_mb = [1u32, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
99 for (k, &mb) in expected_mb.iter().enumerate() {
100 let bucket = SizeBucket::from_exponent(k as u8).expect("k in range");
101 assert_eq!(bucket.megabytes(), mb, "k={k} megabytes");
102 assert_eq!(bucket.exponent(), k as u8, "k={k} exponent round-trips");
103 assert_eq!(bucket.byte_len(), 1u64 << (k as u32 + 20), "k={k} byte_len");
104 }
105 // k=10 is a full gigabyte.
106 assert_eq!(SizeBucket::from_exponent(10).unwrap().megabytes(), 1024);
107 assert_eq!(SizeBucket::from_exponent(10).unwrap().byte_len(), 1 << 30);
108 }
109
110 /// `from_exponent` rejects any exponent above the 1 GB ceiling.
111 #[test]
112 fn from_exponent_rejects_out_of_range() {
113 assert!(matches!(
114 SizeBucket::from_exponent(11),
115 Err(MerkleError::InvalidSize(_))
116 ));
117 assert!(matches!(
118 SizeBucket::from_exponent(255),
119 Err(MerkleError::InvalidSize(_))
120 ));
121 }
122
123 /// The canonical byte→bucket boundaries: the smallest bucket that fits, with 0/1 byte → k0,
124 /// exact powers landing in their own bucket, and anything above 1 GiB rejected.
125 #[test]
126 fn for_byte_len_boundaries() {
127 const MIB: u64 = 1 << 20;
128 const GIB: u64 = 1 << 30;
129
130 let expect = |bytes: u64, k: u8| {
131 assert_eq!(
132 SizeBucket::for_byte_len(bytes)
133 .expect("in range")
134 .exponent(),
135 k,
136 "for_byte_len({bytes}) should be k={k}"
137 );
138 };
139
140 expect(0, 0);
141 expect(1, 0);
142 expect(MIB, 0); // exactly 1 MiB fits bucket 0
143 expect(MIB + 1, 1); // one byte over → next bucket
144 expect(512 * MIB, 9); // 512 MiB == 2^29 fits bucket 9
145 expect(512 * MIB + 1, 10);
146 expect(GIB, 10); // exactly 1 GiB fits the top bucket
147 assert!(
148 matches!(
149 SizeBucket::for_byte_len(GIB + 1),
150 Err(MerkleError::InvalidSize(_))
151 ),
152 "one byte over 1 GiB has no bucket"
153 );
154 }
155}