Skip to main content

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}