cas_serve/chunker.rs
1//! Content-defined chunker — a thin wrapper over the `gearhash` crate.
2//!
3//! This reproduces the upstream xet-core `Chunker`
4//! (`deduplication/src/chunking.rs` at tag `git-xet-v0.2.0`) byte-for-byte:
5//! same `gearhash::Hasher` engine, same `TARGET_CHUNK_SIZE` (64 KiB), same
6//! minimum (`target / MINIMUM_CHUNK_DIVISOR` = 8 KiB) and maximum
7//! (`target * MAXIMUM_CHUNK_MULTIPLIER` = 128 KiB) bounds, and the same
8//! left-shifted FastCDC mask. Chunk hashing delegates to
9//! `merklehash::compute_data_hash`, i.e. BLAKE3 keyed with the XET `DATA_KEY`,
10//! which is exactly what `deduplication::Chunk::new` does.
11//!
12//! Reusing `gearhash` + `merklehash` directly (rather than depending on the
13//! `deduplication` crate) avoids pulling the heavy `xet_config` /
14//! `xet_runtime` / `mdb_shard` / `progress_tracking` tree into cas-serve,
15//! which is intended to stay lightweight (no libtorch). The boundary logic
16//! below is a direct port of xet-core's, so chunks produced here are
17//! identical to those produced by a stock xet-core client.
18
19use bytes::Bytes;
20use merklehash::MerkleHash;
21
22/// XET chunking constants, matching `deduplication/src/constants.rs`.
23///
24/// `TARGET_CHUNK_SIZE` is 64 KiB, giving an average chunk size of ~64 KiB and
25/// a per-xorb target of ~1024 chunks. `MINIMUM_CHUNK_DIVISOR = 8` yields a
26/// minimum chunk size of 8 KiB; `MAXIMUM_CHUNK_MULTIPLIER = 2` yields a
27/// maximum of 128 KiB. These match the values pinned at `git-xet-v0.2.0`.
28pub const TARGET_CHUNK_SIZE: usize = 64 * 1024;
29pub const MINIMUM_CHUNK_DIVISOR: usize = 8;
30pub const MAXIMUM_CHUNK_MULTIPLIER: usize = 2;
31
32/// XORB limits, matching `deduplication/src/constants.rs`:
33/// a xorb (eXclusive-OR Block) holds at most 64 MiB across at most 8192 chunks.
34pub const MAX_XORB_BYTES: usize = 64 * 1024 * 1024;
35pub const MAX_XORB_CHUNKS: usize = 8 * 1024;
36
37/// Gear-hash rolling-window size (bytes that must be processed before a
38/// boundary can trigger). Matches xet-core's `HASH_WINDOW_SIZE`.
39const HASH_WINDOW_SIZE: usize = 64;
40
41/// A content-defined chunk: its BLAKE3-keyed hash and its bytes.
42#[derive(Debug, Clone)]
43pub struct Chunk {
44 /// BLAKE3 keyed with the global XET `DATA_KEY` (`compute_data_hash`).
45 pub hash: MerkleHash,
46 pub data: Bytes,
47}
48
49impl Chunk {
50 pub fn new(data: Bytes) -> Self {
51 let hash = merklehash::compute_data_hash(&data);
52 Chunk { hash, data }
53 }
54}
55
56/// Content-defined chunker using the FastCDC / gear-hash algorithm.
57///
58/// Ported from xet-core's `Chunker` (`deduplication/src/chunking.rs`).
59pub struct Chunker {
60 hash: gearhash::Hasher<'static>,
61 minimum_chunk: usize,
62 maximum_chunk: usize,
63 mask: u64,
64 chunkbuf: Vec<u8>,
65}
66
67impl Default for Chunker {
68 fn default() -> Self {
69 Self::new(TARGET_CHUNK_SIZE)
70 }
71}
72
73impl Chunker {
74 /// Construct a chunker targeting the given average chunk size. The size
75 /// must be a power of two greater than the 64-byte gear-hash window.
76 pub fn new(target_chunk_size: usize) -> Self {
77 assert_eq!(
78 target_chunk_size.count_ones(),
79 1,
80 "target must be a power of two"
81 );
82 assert!(target_chunk_size > HASH_WINDOW_SIZE);
83 assert!(target_chunk_size < u32::MAX as usize);
84
85 // Build the FastCDC mask exactly as xet-core does: start from
86 // (target - 1), then shift it left to the top bits of the word so the
87 // rolling-hash window fully participates in the boundary decision.
88 let mask = (target_chunk_size - 1) as u64;
89 let mask = mask << mask.leading_zeros();
90
91 let minimum_chunk = target_chunk_size / MINIMUM_CHUNK_DIVISOR;
92 let maximum_chunk = target_chunk_size * MAXIMUM_CHUNK_MULTIPLIER;
93 assert!(maximum_chunk > minimum_chunk);
94
95 Chunker {
96 hash: gearhash::Hasher::default(),
97 minimum_chunk,
98 maximum_chunk,
99 mask,
100 chunkbuf: Vec::with_capacity(maximum_chunk),
101 }
102 }
103
104 /// Look for the next chunk boundary in `data`, carrying over any buffered
105 /// bytes from the previous call. Returns the offset into `data` at which
106 /// the chunk ends, or `None` if no boundary can be decided yet.
107 ///
108 /// Direct port of xet-core's `Chunker::next_boundary`.
109 #[inline]
110 pub fn next_boundary(&mut self, data: &[u8]) -> Option<usize> {
111 let n_bytes = data.len();
112 if n_bytes == 0 {
113 return None;
114 }
115
116 let previous_len = self.chunkbuf.len();
117 let mut cur_index = 0;
118 let mut create_chunk = false;
119
120 // Skip the minimum chunk size, accounting for the 64-byte hash window.
121 if previous_len + HASH_WINDOW_SIZE < self.minimum_chunk {
122 let skip = (self.minimum_chunk - previous_len - HASH_WINDOW_SIZE - 1).min(n_bytes);
123 cur_index += skip;
124 }
125
126 // Don't scan past the maximum chunk boundary.
127 let read_end = n_bytes.min(cur_index + self.maximum_chunk - previous_len);
128
129 loop {
130 if let Some(next_match) = self.hash.next_match(&data[cur_index..read_end], self.mask) {
131 cur_index += next_match;
132
133 // A boundary found before the minimum chunk size can be an
134 // artifact of the hasher's prior state (the window hasn't
135 // filled with current-chunk bytes yet); keep scanning.
136 if cur_index + previous_len < self.minimum_chunk {
137 continue;
138 }
139 create_chunk = true;
140 } else {
141 cur_index = read_end;
142 }
143 break;
144 }
145
146 // Force a boundary at the maximum chunk size.
147 if cur_index + previous_len >= self.maximum_chunk {
148 cur_index = self.maximum_chunk - previous_len;
149 create_chunk = true;
150 }
151
152 if create_chunk {
153 self.hash.set_hash(0); // reset for the next chunk
154 Some(cur_index)
155 } else {
156 None
157 }
158 }
159
160 /// Feed more data and return the next emitted chunk (if any) plus the
161 /// number of bytes consumed from `data`. When `is_final` is true the
162 /// remaining buffer is flushed as a final chunk.
163 ///
164 /// Direct port of xet-core's `Chunker::next`.
165 pub fn next(&mut self, data: &[u8], is_final: bool) -> (Option<Chunk>, usize) {
166 let (chunk_data, consume): (Bytes, usize) =
167 if let Some(next_boundary) = self.next_boundary(data) {
168 if self.chunkbuf.is_empty() {
169 (
170 Bytes::copy_from_slice(&data[..next_boundary]),
171 next_boundary,
172 )
173 } else {
174 self.chunkbuf.extend_from_slice(&data[..next_boundary]);
175 (std::mem::take(&mut self.chunkbuf).into(), next_boundary)
176 }
177 } else if is_final {
178 if self.chunkbuf.is_empty() {
179 (Bytes::copy_from_slice(data), data.len())
180 } else {
181 self.chunkbuf.extend_from_slice(data);
182 (std::mem::take(&mut self.chunkbuf).into(), data.len())
183 }
184 } else {
185 self.chunkbuf.extend_from_slice(data);
186 return (None, data.len());
187 };
188
189 if chunk_data.is_empty() {
190 return (None, 0);
191 }
192
193 (Some(Chunk::new(chunk_data)), consume)
194 }
195}
196
197/// Convenience: chunk a complete byte slice in one shot, flushing the tail.
198///
199/// This mirrors xet-core's `Chunker::next_block(&data, true)` usage and is the
200/// entry point used by the upload path.
201pub fn chunk_all(data: &[u8]) -> Vec<Chunk> {
202 let mut chunker = Chunker::default();
203 let mut ret = Vec::new();
204 let mut pos = 0;
205 loop {
206 if pos == data.len() {
207 // Flush any final partial chunk.
208 if let Some(chunk) = chunker.next(&[], true).0 {
209 ret.push(chunk);
210 }
211 return ret;
212 }
213 let (maybe_chunk, consumed) = chunker.next(&data[pos..], false);
214 if let Some(chunk) = maybe_chunk {
215 ret.push(chunk);
216 }
217 if consumed == 0 {
218 // `next` consumed nothing and emitted nothing only when the buffer
219 // is sub-minimum and not final; force progress by feeding the rest
220 // as final.
221 let (final_chunk, _) = chunker.next(&data[pos..], true);
222 if let Some(chunk) = final_chunk {
223 ret.push(chunk);
224 }
225 return ret;
226 }
227 pos += consumed;
228 }
229}
230
231#[cfg(test)]
232#[allow(clippy::unwrap_used, clippy::expect_used)]
233mod tests {
234 use super::*;
235
236 #[test]
237 fn empty_input_yields_no_chunks() {
238 assert!(chunk_all(&[]).is_empty());
239 }
240
241 #[test]
242 fn round_trip_concatenation_small() {
243 // Pseudo-random data so CDC actually cuts boundaries.
244 let mut data = Vec::with_capacity(4096);
245 let mut state: u64 = 0x9e3779b97f4a7c15;
246 for _ in 0..512 {
247 state = state.wrapping_mul(0xbf58476d1ce4e5b9) ^ (state >> 27);
248 data.extend_from_slice(&state.to_le_bytes());
249 }
250 let chunks = chunk_all(&data);
251 assert!(!chunks.is_empty());
252
253 let mut rebuilt = Vec::new();
254 for c in &chunks {
255 rebuilt.extend_from_slice(&c.data);
256 // chunk hash is BLAKE3-keyed over the chunk bytes
257 assert_eq!(c.hash, merklehash::compute_data_hash(&c.data));
258 }
259 assert_eq!(rebuilt, data);
260 }
261
262 #[test]
263 fn respects_maximum_chunk_size() {
264 // Constant bytes never trigger the gear mask, so chunks should all be
265 // the maximum size except the (final) tail.
266 let data = vec![0xA5u8; MAX_XORB_BYTES + 17];
267 let chunks = chunk_all(&data);
268 for c in &chunks {
269 assert!(c.data.len() <= TARGET_CHUNK_SIZE * MAXIMUM_CHUNK_MULTIPLIER);
270 }
271 let total: usize = chunks.iter().map(|c| c.data.len()).sum();
272 assert_eq!(total, data.len());
273 }
274
275 /// Golden test: constant data must cut at the maximum chunk boundary
276 /// (TARGET * MAXIMUM_CHUNK_MULTIPLIER = 128 KiB), matching xet-core's
277 /// `test_correctness_1mb_const_data` exactly. This proves the chunker
278 /// produces byte-identical boundaries to upstream xet-core.
279 #[test]
280 fn boundaries_match_xet_core_const_data() {
281 let data = vec![59u8; 1_000_000];
282 let chunks = chunk_all(&data);
283 let boundaries: Vec<usize> = chunks
284 .iter()
285 .scan(0, |acc, c| {
286 *acc += c.data.len();
287 Some(*acc)
288 })
289 .collect();
290 // These are the exact expected boundaries from xet-core's
291 // deduplication/src/chunking.rs::test_correctness_1mb_const_data.
292 assert_eq!(
293 boundaries,
294 vec![131072, 262144, 393216, 524288, 655360, 786432, 917504, 1_000_000]
295 );
296 }
297}