Skip to main content

cas_serve/
mdb_shard.rs

1//! The XET `mdb_shard` binary reconstruction format — a faithful, minimal port
2//! of xet-core's `mdb_shard` crate.
3//!
4//! cas-serve advertises XET support, which means the reconstruction shard it
5//! returns from `GetReconstructionInfo` must be parseable by any stock xet-core
6//! client (its `MDBShardFile` reader / `FileReconstructor`). The bespoke JSON
7//! shard the original #390 commit produced is not the XET wire format. This
8//! module ports the real binary container — the `.mdb` file — so a shard built
9//! here is byte-compatible with upstream.
10//!
11//! # Why a port, not a dependency
12//!
13//! Upstream `mdb_shard` is `edition = "2024"` and pulls in `xet_config` /
14//! `xet_runtime` / `utils` (and, transitively, the libtorch-coupled tree).
15//! cas-serve deliberately stays out of that tree (no libtorch). The binary
16//! format itself is plain `Write`/`Read` + little-endian primitives, so it
17//! ports cleanly to edition 2021.
18//!
19//! # Layout (ported from `mdb_shard/src/shard_format.rs`)
20//!
21//! The on-disk shard is, in order:
22//!
23//! 1. **Header** (`MDBShardFileHeader`, 48 B): 32-byte magic tag, `version`
24//!    (u64 LE, =2), `footer_size` (u64 LE).
25//! 2. **File-Info section**: one `FileDataSequenceHeader` + N
26//!    `FileDataSequenceEntry` per file (in ascending file-hash order), then a
27//!    single bookend header. Each entry is 48 B (`[u64;4]` hash + 4×u32).
28//! 3. **CAS-Info section**: one `CASChunkSequenceHeader` + N
29//!    `CASChunkSequenceEntry` per xorb (in ascending xorb-hash order), then a
30//!    single bookend header.
31//! 4. **File lookup**: `(u64 truncated file hash, u32 index)` per file.
32//! 5. **CAS lookup**: `(u64 truncated xorb hash, u32 index)` per xorb.
33//! 6. **Chunk lookup**: `(u64 truncated chunk hash, u32 cas idx, u32 chunk
34//!    offset)` per chunk, sorted by key.
35//! 7. **Footer** (`MDBShardFileFooter`, 200 B): section offsets/counts, the
36//!    32-byte chunk-hash HMAC key, timestamps, byte totals, and
37//!    `footer_offset`.
38//!
39//! `truncate_hash(h) = h[0]` (first u64 of the 4×u64 `MerkleHash`).
40//!
41//! All multi-byte integers are little-endian, matching
42//! `utils::serialization_utils`.
43
44use std::io::{Cursor, Read, Seek, SeekFrom, Write};
45use std::mem::size_of;
46
47use merklehash::MerkleHash;
48
49use crate::chunker::Chunk;
50
51// --------------------------------------------------------------------------- //
52// Constants — match `mdb_shard/src/shard_format.rs` verbatim.                //
53// --------------------------------------------------------------------------- //
54
55/// 32-byte magic tag at the head of every shard file
56/// (`shard_format.rs::MDB_SHARD_HEADER_TAG`).
57pub const MDB_SHARD_HEADER_TAG: [u8; 32] = [
58    b'H', b'F', b'R', b'e', b'p', b'o', b'M', b'e', b't', b'a', b'D', b'a', b't', b'a', 0, 85, 105,
59    103, 69, 106, 123, 129, 87, 131, 165, 189, 217, 92, 205, 209, 74, 169,
60];
61
62const MDB_SHARD_HEADER_VERSION: u64 = 2;
63const MDB_SHARD_FOOTER_VERSION: u64 = 1;
64
65/// Every fixed-size File-Info / CAS-Info record is 48 bytes: a 32-byte hash
66/// (`[u64;4]`) plus four `u32` slots. Asserted byte-for-byte against
67/// `FileDataSequenceHeader`, `FileDataSequenceEntry`, `CASChunkSequenceHeader`,
68/// and `CASChunkSequenceEntry` below.
69pub const MDB_ENTRY_SIZE: usize = size_of::<[u64; 4]>() + 4 * size_of::<u32>();
70/// Compile-time check that every fixed-size shard record is 48 bytes.
71const _: () = const_assert_entry_size();
72
73/// Size of the footer, in bytes: 21 `u64` fields + the 32-byte HMAC key = 200.
74/// Verified against `size_of::<MDBShardFileFooter>()` upstream.
75pub const MDB_FOOTER_SIZE: u64 = 21 * size_of::<u64>() as u64 + 32;
76/// Compile-time check that the footer layout sums to 200 bytes (21×8 + 32).
77const _: () = const_assert_footer_size();
78
79/// `truncate_hash` — the first u64 of a `MerkleHash`, used as the lookup key.
80/// Matches `mdb_shard/src/utils.rs::truncate_hash`.
81#[inline]
82fn truncate_hash(h: &MerkleHash) -> u64 {
83    h[0]
84}
85
86/// Compile-time check that every fixed-size shard record is 48 bytes.
87#[allow(clippy::assertions_on_constants)]
88const fn const_assert_entry_size() {
89    assert!(MDB_ENTRY_SIZE == 48);
90}
91
92/// Compile-time check that the footer layout sums to 200 bytes (21×8 + 32).
93#[allow(clippy::assertions_on_constants)]
94const fn const_assert_footer_size() {
95    assert!(MDB_FOOTER_SIZE == 200);
96}
97
98// --------------------------------------------------------------------------- //
99// Serialization primitives — direct ports of `utils::serialization_utils`.   //
100// --------------------------------------------------------------------------- //
101//
102// `write_hash`/`read_hash` are *raw* 32-byte writes (the `MerkleHash` is a
103// transparent `[u64; 4]` and is serialized as `as_bytes()` / transmuted back;
104// on a little-endian host `h[0]` is therefore the first 8 bytes, which is what
105// makes `truncate_hash` well-defined on the wire).
106
107#[inline]
108fn write_hash<W: Write>(w: &mut W, h: &MerkleHash) -> std::io::Result<()> {
109    w.write_all(h.as_ref())
110}
111
112#[inline]
113fn write_u32<W: Write>(w: &mut W, v: u32) -> std::io::Result<()> {
114    w.write_all(&v.to_le_bytes())
115}
116
117#[inline]
118fn write_u64<W: Write>(w: &mut W, v: u64) -> std::io::Result<()> {
119    w.write_all(&v.to_le_bytes())
120}
121
122#[inline]
123fn read_u32<R: Read>(r: &mut R) -> std::io::Result<u32> {
124    let mut b = [0u8; size_of::<u32>()];
125    r.read_exact(&mut b)?;
126    Ok(u32::from_le_bytes(b))
127}
128
129#[inline]
130fn read_u64<R: Read>(r: &mut R) -> std::io::Result<u64> {
131    let mut b = [0u8; size_of::<u64>()];
132    r.read_exact(&mut b)?;
133    Ok(u64::from_le_bytes(b))
134}
135
136#[inline]
137fn read_hash<R: Read>(r: &mut R) -> std::io::Result<MerkleHash> {
138    let mut b = [0u8; 32];
139    r.read_exact(&mut b)?;
140    // The upstream reader uses `transmute::<[u8;32],[u64;4]>`; on the wire the
141    // bytes are the in-memory representation of the host that wrote them. We
142    // reconstruct via `from_slice`, which is the safe, layout-identical copy.
143    MerkleHash::from_slice(&b).map_err(|_| std::io::Error::other("32-byte hash expected"))
144}
145
146// --------------------------------------------------------------------------- //
147// File-Info / CAS-Info records (`file_structs.rs`, `cas_structs.rs`).        //
148// --------------------------------------------------------------------------- //
149//
150// Flags from `file_structs.rs`. cas-serve never emits verification entries,
151// so these are kept only to document the on-disk flag layout faithfully.
152#[allow(dead_code)]
153const MDB_FILE_FLAG_WITH_VERIFICATION: u32 = 1 << 31;
154#[allow(dead_code)]
155const MDB_FILE_FLAG_VERIFICATION_MASK: u32 = 1 << 31;
156
157/// `FileDataSequenceHeader` (48 B): the per-file record that opens its segment
158/// list. `file_hash` is the content address the shard is keyed by.
159#[derive(Clone, Debug, PartialEq)]
160pub struct FileDataSequenceHeader {
161    pub file_hash: MerkleHash,
162    pub file_flags: u32,
163    pub num_entries: u32,
164    pub _unused: u64,
165}
166
167impl FileDataSequenceHeader {
168    /// The all-ones hash marks the bookend record that terminates sequential
169    /// scans of the File-Info section.
170    fn bookend() -> Self {
171        Self {
172            file_hash: [!0u64; 4].into(),
173            file_flags: 0,
174            num_entries: 0,
175            _unused: 0,
176        }
177    }
178
179    fn is_bookend(&self) -> bool {
180        self.file_hash == [!0u64; 4].into()
181    }
182
183    /// Whether this file carries per-segment verification entries. cas-serve
184    /// never emits them, but a reader must honor the flag when parsing shards
185    /// produced by upstream xet-core clients.
186    #[allow(dead_code)]
187    fn contains_verification(&self) -> bool {
188        (self.file_flags & MDB_FILE_FLAG_VERIFICATION_MASK) != 0
189    }
190
191    fn serialize<W: Write>(&self, w: &mut W) -> std::io::Result<()> {
192        write_hash(w, &self.file_hash)?;
193        write_u32(w, self.file_flags)?;
194        write_u32(w, self.num_entries)?;
195        write_u64(w, self._unused)
196    }
197
198    fn deserialize<R: Read>(r: &mut R) -> std::io::Result<Self> {
199        Ok(Self {
200            file_hash: read_hash(r)?,
201            file_flags: read_u32(r)?,
202            num_entries: read_u32(r)?,
203            _unused: read_u64(r)?,
204        })
205    }
206}
207
208/// `FileDataSequenceEntry` (48 B): one reconstruction segment — the xorb to
209/// pull chunks from, the inclusive-start / exclusive-end chunk range, and the
210/// total unpacked byte length of that range. Concatenating the chunk bytes for
211/// every segment, in segment order, reproduces the file.
212#[derive(Clone, Debug, PartialEq)]
213pub struct FileDataSequenceEntry {
214    pub cas_hash: MerkleHash,
215    pub cas_flags: u32,
216    pub unpacked_segment_bytes: u32,
217    /// Inclusive start chunk index within the xorb.
218    pub chunk_index_start: u32,
219    /// Exclusive end chunk index within the xorb
220    /// (`chunk_index_end - chunk_index_start` = chunk count).
221    pub chunk_index_end: u32,
222}
223
224impl FileDataSequenceEntry {
225    fn serialize<W: Write>(&self, w: &mut W) -> std::io::Result<()> {
226        write_hash(w, &self.cas_hash)?;
227        write_u32(w, self.cas_flags)?;
228        write_u32(w, self.unpacked_segment_bytes)?;
229        write_u32(w, self.chunk_index_start)?;
230        write_u32(w, self.chunk_index_end)
231    }
232
233    fn deserialize<R: Read>(r: &mut R) -> std::io::Result<Self> {
234        Ok(Self {
235            cas_hash: read_hash(r)?,
236            cas_flags: read_u32(r)?,
237            unpacked_segment_bytes: read_u32(r)?,
238            chunk_index_start: read_u32(r)?,
239            chunk_index_end: read_u32(r)?,
240        })
241    }
242}
243
244/// `CASChunkSequenceHeader` (48 B): opens a xorb's chunk list.
245#[derive(Clone, Debug, PartialEq)]
246pub struct CasChunkSequenceHeader {
247    pub cas_hash: MerkleHash,
248    pub cas_flags: u32,
249    pub num_entries: u32,
250    pub num_bytes_in_cas: u32,
251    pub num_bytes_on_disk: u32,
252}
253
254impl CasChunkSequenceHeader {
255    /// All-ones hash marks the CAS-Info bookend.
256    fn bookend() -> Self {
257        Self {
258            cas_hash: [!0u64; 4].into(),
259            cas_flags: 0,
260            num_entries: 0,
261            num_bytes_in_cas: 0,
262            num_bytes_on_disk: 0,
263        }
264    }
265
266    fn is_bookend(&self) -> bool {
267        self.cas_hash == [!0u64; 4].into()
268    }
269
270    fn serialize<W: Write>(&self, w: &mut W) -> std::io::Result<()> {
271        write_hash(w, &self.cas_hash)?;
272        write_u32(w, self.cas_flags)?;
273        write_u32(w, self.num_entries)?;
274        write_u32(w, self.num_bytes_in_cas)?;
275        write_u32(w, self.num_bytes_on_disk)
276    }
277
278    fn deserialize<R: Read>(r: &mut R) -> std::io::Result<Self> {
279        Ok(Self {
280            cas_hash: read_hash(r)?,
281            cas_flags: read_u32(r)?,
282            num_entries: read_u32(r)?,
283            num_bytes_in_cas: read_u32(r)?,
284            num_bytes_on_disk: read_u32(r)?,
285        })
286    }
287}
288
289/// `CASChunkSequenceEntry` (48 B): one chunk within a xorb.
290#[derive(Clone, Debug, PartialEq)]
291pub struct CasChunkSequenceEntry {
292    pub chunk_hash: MerkleHash,
293    pub chunk_byte_range_start: u32,
294    pub unpacked_segment_bytes: u32,
295    pub flags: u32,
296    pub _unused: u32,
297}
298
299impl CasChunkSequenceEntry {
300    fn serialize<W: Write>(&self, w: &mut W) -> std::io::Result<()> {
301        write_hash(w, &self.chunk_hash)?;
302        write_u32(w, self.chunk_byte_range_start)?;
303        write_u32(w, self.unpacked_segment_bytes)?;
304        write_u32(w, self.flags)?;
305        write_u32(w, self._unused)
306    }
307
308    fn deserialize<R: Read>(r: &mut R) -> std::io::Result<Self> {
309        Ok(Self {
310            chunk_hash: read_hash(r)?,
311            chunk_byte_range_start: read_u32(r)?,
312            unpacked_segment_bytes: read_u32(r)?,
313            flags: read_u32(r)?,
314            _unused: read_u32(r)?,
315        })
316    }
317}
318
319// --------------------------------------------------------------------------- //
320// File container header / footer (`shard_format.rs`).                        //
321// --------------------------------------------------------------------------- //
322
323/// 48-byte shard header: magic tag + version + footer size.
324#[derive(Clone, Debug, PartialEq)]
325pub struct MdbShardHeader {
326    pub version: u64,
327    pub footer_size: u64,
328}
329
330impl Default for MdbShardHeader {
331    fn default() -> Self {
332        Self {
333            version: MDB_SHARD_HEADER_VERSION,
334            footer_size: MDB_FOOTER_SIZE,
335        }
336    }
337}
338
339impl MdbShardHeader {
340    fn serialize<W: Write>(&self, w: &mut W) -> std::io::Result<()> {
341        w.write_all(&MDB_SHARD_HEADER_TAG)?;
342        write_u64(w, self.version)?;
343        write_u64(w, self.footer_size)
344    }
345
346    fn deserialize<R: Read>(r: &mut R) -> std::io::Result<Self> {
347        let mut tag = [0u8; 32];
348        r.read_exact(&mut tag)?;
349        if tag != MDB_SHARD_HEADER_TAG {
350            return Err(std::io::Error::other(
351                "not an mdb_shard file (magic mismatch)",
352            ));
353        }
354        Ok(Self {
355            version: read_u64(r)?,
356            footer_size: read_u64(r)?,
357        })
358    }
359}
360
361/// 200-byte shard footer carrying the section offsets, lookup counts, HMAC
362/// key, timestamps, and byte totals. Field order matches
363/// `MDBShardFileFooter::serialize` exactly.
364#[derive(Clone, Debug, PartialEq)]
365pub struct MdbShardFooter {
366    pub version: u64,
367    pub file_info_offset: u64,
368    pub cas_info_offset: u64,
369    pub file_lookup_offset: u64,
370    pub file_lookup_num_entry: u64,
371    pub cas_lookup_offset: u64,
372    pub cas_lookup_num_entry: u64,
373    pub chunk_lookup_offset: u64,
374    pub chunk_lookup_num_entry: u64,
375    /// 32-byte chunk-hash HMAC key (all-zero = no keying). cas-serve does not
376    /// key its chunks, so this is always zero.
377    pub chunk_hash_hmac_key: [u8; 32],
378    pub shard_creation_timestamp: u64,
379    pub shard_key_expiry: u64,
380    pub _buffer: [u64; 6],
381    pub stored_bytes_on_disk: u64,
382    pub materialized_bytes: u64,
383    pub stored_bytes: u64,
384    pub footer_offset: u64,
385}
386
387impl Default for MdbShardFooter {
388    fn default() -> Self {
389        Self {
390            version: MDB_SHARD_FOOTER_VERSION,
391            file_info_offset: 0,
392            cas_info_offset: 0,
393            file_lookup_offset: 0,
394            file_lookup_num_entry: 0,
395            cas_lookup_offset: 0,
396            cas_lookup_num_entry: 0,
397            chunk_lookup_offset: 0,
398            chunk_lookup_num_entry: 0,
399            chunk_hash_hmac_key: [0u8; 32],
400            shard_creation_timestamp: 0,
401            shard_key_expiry: u64::MAX,
402            _buffer: [0u64; 6],
403            stored_bytes_on_disk: 0,
404            materialized_bytes: 0,
405            stored_bytes: 0,
406            footer_offset: 0,
407        }
408    }
409}
410
411impl MdbShardFooter {
412    fn serialize<W: Write>(&self, w: &mut W) -> std::io::Result<()> {
413        write_u64(w, self.version)?;
414        write_u64(w, self.file_info_offset)?;
415        write_u64(w, self.cas_info_offset)?;
416        write_u64(w, self.file_lookup_offset)?;
417        write_u64(w, self.file_lookup_num_entry)?;
418        write_u64(w, self.cas_lookup_offset)?;
419        write_u64(w, self.cas_lookup_num_entry)?;
420        write_u64(w, self.chunk_lookup_offset)?;
421        write_u64(w, self.chunk_lookup_num_entry)?;
422        w.write_all(&self.chunk_hash_hmac_key)?;
423        write_u64(w, self.shard_creation_timestamp)?;
424        write_u64(w, self.shard_key_expiry)?;
425        for &v in &self._buffer {
426            write_u64(w, v)?;
427        }
428        write_u64(w, self.stored_bytes_on_disk)?;
429        write_u64(w, self.materialized_bytes)?;
430        write_u64(w, self.stored_bytes)?;
431        write_u64(w, self.footer_offset)
432    }
433
434    fn deserialize<R: Read>(r: &mut R) -> std::io::Result<Self> {
435        let version = read_u64(r)?;
436        if version != MDB_SHARD_FOOTER_VERSION {
437            return Err(std::io::Error::other(format!(
438                "mdb_shard footer version mismatch: expected {MDB_SHARD_FOOTER_VERSION}, got {version}"
439            )));
440        }
441        let mut key = [0u8; 32];
442        let mut buf6 = [0u64; 6];
443        Ok(Self {
444            version,
445            file_info_offset: read_u64(r)?,
446            cas_info_offset: read_u64(r)?,
447            file_lookup_offset: read_u64(r)?,
448            file_lookup_num_entry: read_u64(r)?,
449            cas_lookup_offset: read_u64(r)?,
450            cas_lookup_num_entry: read_u64(r)?,
451            chunk_lookup_offset: read_u64(r)?,
452            chunk_lookup_num_entry: read_u64(r)?,
453            chunk_hash_hmac_key: {
454                r.read_exact(&mut key)?;
455                key
456            },
457            shard_creation_timestamp: read_u64(r)?,
458            shard_key_expiry: read_u64(r)?,
459            _buffer: {
460                for v in &mut buf6 {
461                    *v = read_u64(r)?;
462                }
463                buf6
464            },
465            stored_bytes_on_disk: read_u64(r)?,
466            materialized_bytes: read_u64(r)?,
467            stored_bytes: read_u64(r)?,
468            footer_offset: read_u64(r)?,
469        })
470    }
471}
472
473// --------------------------------------------------------------------------- //
474// In-memory shard + builder (port of `MDBInMemoryShard` / `serialize_from`). //
475// --------------------------------------------------------------------------- //
476
477/// One file's reconstruction plan: its content-address and the ordered
478/// segments that rebuild it.
479#[derive(Clone, Debug)]
480pub struct MdbFileInfo {
481    pub metadata: FileDataSequenceHeader,
482    pub segments: Vec<FileDataSequenceEntry>,
483}
484
485impl MdbFileInfo {
486    /// Total unpacked file length (sum of segment byte lengths).
487    pub fn file_size(&self) -> u64 {
488        self.segments
489            .iter()
490            .map(|s| s.unpacked_segment_bytes as u64)
491            .sum()
492    }
493}
494
495/// One xorb's content: its header + the ordered chunk entries it holds.
496#[derive(Clone, Debug)]
497pub struct MdbCasInfo {
498    pub metadata: CasChunkSequenceHeader,
499    pub chunks: Vec<CasChunkSequenceEntry>,
500}
501
502/// A builder that mirrors xet-core's `MDBInMemoryShard` — accumulate file and
503/// xorb records, then `serialize` emits the `.mdb` byte stream in exactly the
504/// order `MDBShardInfo::serialize_from` does.
505#[derive(Default)]
506pub struct MdbShardBuilder {
507    /// Files keyed by file hash (BTreeMap ⇒ ascending hash order on disk).
508    files: std::collections::BTreeMap<MerkleHash, MdbFileInfo>,
509    /// XORBs keyed by xorb hash (BTreeMap ⇒ ascending hash order on disk).
510    cas: std::collections::BTreeMap<MerkleHash, MdbCasInfo>,
511}
512
513impl MdbShardBuilder {
514    pub fn new() -> Self {
515        Self::default()
516    }
517
518    /// Add a file's reconstruction info. Overwrites any prior entry for the
519    /// same file hash.
520    pub fn add_file(&mut self, info: MdbFileInfo) {
521        self.files.insert(info.metadata.file_hash, info);
522    }
523
524    /// Add a xorb's chunk list. Overwrites any prior entry for the same xorb
525    /// hash.
526    pub fn add_cas(&mut self, info: MdbCasInfo) {
527        self.cas.insert(info.metadata.cas_hash, info);
528    }
529
530    /// Serialize the shard to a byte vector, in the canonical section order:
531    /// header → file-info → cas-info → file lookup → cas lookup → chunk lookup
532    /// → footer. Ported from `MDBShardInfo::serialize_from`.
533    pub fn serialize(&self) -> std::io::Result<Vec<u8>> {
534        let mut out: Vec<u8> = Vec::new();
535        let mut footer = MdbShardFooter::default();
536
537        // 1. Header.
538        MdbShardHeader::default().serialize(&mut out)?;
539        debug_assert_eq!(out.len() as u64, 48);
540
541        // 2. File-Info section (+ bookend). Track the file-lookup table while
542        //    we walk the files in ascending-hash order.
543        footer.file_info_offset = out.len() as u64;
544        let mut file_lookup: Vec<(u64, u32)> = Vec::with_capacity(self.files.len());
545        let mut file_index: u32 = 0;
546        for (file_hash, info) in &self.files {
547            file_lookup.push((truncate_hash(file_hash), file_index));
548            info.metadata.serialize(&mut out)?;
549            for seg in &info.segments {
550                seg.serialize(&mut out)?;
551            }
552            // Each file contributes 1 header + N segments, all 48 B records.
553            file_index += 1 + info.segments.len() as u32;
554        }
555        FileDataSequenceHeader::bookend().serialize(&mut out)?;
556
557        // 3. CAS-Info section (+ bookend). Track both the CAS lookup and the
558        //    chunk lookup.
559        footer.cas_info_offset = out.len() as u64;
560        let mut cas_lookup: Vec<(u64, u32)> = Vec::with_capacity(self.cas.len());
561        let mut chunk_lookup: Vec<(u64, u32, u32)> = Vec::new();
562        let mut cas_index: u32 = 0;
563        let mut stored_bytes_on_disk: u64 = 0;
564        let mut stored_bytes: u64 = 0;
565        for (cas_hash, info) in &self.cas {
566            cas_lookup.push((truncate_hash(cas_hash), cas_index));
567            info.metadata.serialize(&mut out)?;
568            for (i, chunk) in info.chunks.iter().enumerate() {
569                chunk.serialize(&mut out)?;
570                chunk_lookup.push((truncate_hash(&chunk.chunk_hash), cas_index, i as u32));
571            }
572            cas_index += 1 + info.chunks.len() as u32;
573            stored_bytes_on_disk += info.metadata.num_bytes_on_disk as u64;
574            stored_bytes += info.metadata.num_bytes_in_cas as u64;
575        }
576        CasChunkSequenceHeader::bookend().serialize(&mut out)?;
577
578        // 4. File lookup table (already in ascending truncated-hash order
579        //    because BTreeMap iterates in full-hash order and truncation
580        //    preserves it).
581        footer.file_lookup_offset = out.len() as u64;
582        footer.file_lookup_num_entry = file_lookup.len() as u64;
583        for &(h, idx) in &file_lookup {
584            write_u64(&mut out, h)?;
585            write_u32(&mut out, idx)?;
586        }
587
588        // 5. CAS lookup table (same ascending-order argument).
589        footer.cas_lookup_offset = out.len() as u64;
590        footer.cas_lookup_num_entry = cas_lookup.len() as u64;
591        for &(h, idx) in &cas_lookup {
592            write_u64(&mut out, h)?;
593            write_u32(&mut out, idx)?;
594        }
595
596        // 6. Chunk lookup table — MUST be sorted by truncated chunk hash
597        //    (xet-core sorts; chunk hashes are not monotone with xorb order).
598        footer.chunk_lookup_offset = out.len() as u64;
599        chunk_lookup.sort_unstable_by_key(|&(h, _, _)| h);
600        footer.chunk_lookup_num_entry = chunk_lookup.len() as u64;
601        for &(h, a, b) in &chunk_lookup {
602            write_u64(&mut out, h)?;
603            write_u32(&mut out, a)?;
604            write_u32(&mut out, b)?;
605        }
606
607        // Byte totals + footer offset, then the footer itself.
608        // `materialized_bytes` = total unpacked file bytes (sum over every
609        // file segment), matching `MDBInMemoryShard::materialized_bytes`.
610        footer.stored_bytes_on_disk = stored_bytes_on_disk;
611        footer.materialized_bytes = self
612            .files
613            .values()
614            .flat_map(|f| f.segments.iter())
615            .map(|s| s.unpacked_segment_bytes as u64)
616            .sum();
617        footer.stored_bytes = stored_bytes;
618        footer.footer_offset = out.len() as u64;
619        footer.serialize(&mut out)?;
620        Ok(out)
621    }
622}
623
624// --------------------------------------------------------------------------- //
625// Reader — port of `MDBShardFile` / `MDBShardInfo` (lookup path only).       //
626// --------------------------------------------------------------------------- //
627
628/// A parsed shard: header + footer, with helpers to seek into the byte buffer
629/// and reconstruct a file.
630pub struct MdbShard {
631    pub header: MdbShardHeader,
632    pub footer: MdbShardFooter,
633}
634
635impl MdbShard {
636    /// Parse the header and footer from a complete shard byte buffer.
637    pub fn parse(bytes: &[u8]) -> std::io::Result<Self> {
638        let mut cur = Cursor::new(bytes);
639        let header = MdbShardHeader::deserialize(&mut cur)?;
640        // Footer is the last `footer_size` bytes.
641        let footer_start = bytes.len() as i64 - header.footer_size as i64;
642        if footer_start < 0 {
643            return Err(std::io::Error::other("shard too small for footer"));
644        }
645        cur.seek(SeekFrom::Start(footer_start as u64))?;
646        let footer = MdbShardFooter::deserialize(&mut cur)?;
647        Ok(Self { header, footer })
648    }
649
650    /// Read the `MDBFileInfo` (header + segments) for `file_hash`, seeking the
651    /// file-lookup table then walking the candidate indices exactly like
652    /// `MDBShardInfo::get_file_reconstruction_info`.
653    pub fn file_info(
654        &self,
655        bytes: &[u8],
656        file_hash: &MerkleHash,
657    ) -> std::io::Result<Option<MdbFileInfo>> {
658        let mut cur = Cursor::new(bytes);
659        // Scan the file-lookup table for indices whose truncated hash matches.
660        let target = truncate_hash(file_hash);
661        cur.seek(SeekFrom::Start(self.footer.file_lookup_offset))?;
662        let mut candidates: Vec<u32> = Vec::new();
663        for _ in 0..self.footer.file_lookup_num_entry {
664            let h = read_u64(&mut cur)?;
665            let idx = read_u32(&mut cur)?;
666            if h == target {
667                candidates.push(idx);
668            }
669        }
670
671        for idx in candidates {
672            cur.seek(SeekFrom::Start(
673                self.footer.file_info_offset + MDB_ENTRY_SIZE as u64 * idx as u64,
674            ))?;
675            let header = FileDataSequenceHeader::deserialize(&mut cur)?;
676            if header.is_bookend() {
677                continue;
678            }
679            let mut segments = Vec::with_capacity(header.num_entries as usize);
680            for _ in 0..header.num_entries {
681                segments.push(FileDataSequenceEntry::deserialize(&mut cur)?);
682            }
683            if header.file_hash == *file_hash {
684                return Ok(Some(MdbFileInfo {
685                    metadata: header,
686                    segments,
687                }));
688            }
689        }
690        Ok(None)
691    }
692
693    /// Read every xorb's chunk list (used to verify/inspect a shard).
694    pub fn all_cas_blocks(&self, bytes: &[u8]) -> std::io::Result<Vec<MdbCasInfo>> {
695        let mut cur = Cursor::new(bytes);
696        cur.seek(SeekFrom::Start(self.footer.cas_info_offset))?;
697        let mut out = Vec::new();
698        loop {
699            let header = CasChunkSequenceHeader::deserialize(&mut cur)?;
700            if header.is_bookend() {
701                break;
702            }
703            let mut chunks = Vec::with_capacity(header.num_entries as usize);
704            for _ in 0..header.num_entries {
705                chunks.push(CasChunkSequenceEntry::deserialize(&mut cur)?);
706            }
707            out.push(MdbCasInfo {
708                metadata: header,
709                chunks,
710            });
711        }
712        Ok(out)
713    }
714}
715
716// --------------------------------------------------------------------------- //
717// cas-serve integration: chunk → xorb → shard builder.                       //
718// --------------------------------------------------------------------------- //
719//
720// The chunker + greedy xorb packing are unchanged from the original #390
721// commit (the golden CDC test proves they match xet-core). Only the shard
722// *container* changes: JSON → mdb_shard binary.
723
724/// Build an `MdbShardBuilder` (plus, per xorb, its hash and concatenated raw
725/// bytes) from a chunk list, packing chunks into xorbs that respect the XET
726/// `MAX_XORB_BYTES` (64 MiB) and `MAX_XORB_CHUNKS` (8192) limits.
727///
728/// Chunk → xorb aggregation, xorb hashing (`merklehash::xorb_hash`), and file
729/// hashing (`merklehash::file_hash`) all match xet-core's
730/// `RawXorbData::from_chunks`, so the hashes embedded in the produced shard
731/// are identical to an upstream client's.
732pub fn build_shard(chunks: &[Chunk]) -> (MdbShardBuilder, MerkleHash, Vec<(MerkleHash, Vec<u8>)>) {
733    build_shard_with_cap(chunks, crate::chunker::MAX_XORB_BYTES)
734}
735
736/// Like [`build_shard`], but with a custom per-xorb byte cap (tests use a tiny
737/// cap to force multi-xorb aggregation without allocating 64 MiB).
738pub fn build_shard_with_cap(
739    chunks: &[Chunk],
740    xorb_byte_cap: usize,
741) -> (MdbShardBuilder, MerkleHash, Vec<(MerkleHash, Vec<u8>)>) {
742    use crate::chunker::MAX_XORB_CHUNKS;
743
744    let mut builder = MdbShardBuilder::new();
745    let mut xorbs: Vec<(MerkleHash, Vec<u8>)> = Vec::new();
746    // One File-Info segment per xorb, accumulated in file order; the single
747    // file entry is added once the file hash is known.
748    let mut file_segments: Vec<FileDataSequenceEntry> = Vec::new();
749
750    let mut i = 0;
751    while i < chunks.len() {
752        // Greedily pack chunks into one xorb up to the byte/chunk limits.
753        let mut xorb_bytes: u64 = 0;
754        let mut xorb_chunks: Vec<&Chunk> = Vec::new();
755        let start = i;
756        while i < chunks.len() {
757            let c = &chunks[i];
758            let new_bytes = xorb_bytes + c.data.len() as u64;
759            if !xorb_chunks.is_empty()
760                && (new_bytes > xorb_byte_cap as u64 || xorb_chunks.len() >= MAX_XORB_CHUNKS)
761            {
762                break;
763            }
764            xorb_bytes = new_bytes;
765            xorb_chunks.push(c);
766            i += 1;
767        }
768        let end = i; // exclusive
769
770        // Xorb hash = Merkle root over (chunk_hash, chunk_len) — matches
771        // `merklehash::xorb_hash` / `RawXorbData::from_chunks`.
772        let hash_inputs: Vec<(MerkleHash, u64)> = xorb_chunks
773            .iter()
774            .map(|c| (c.hash, c.data.len() as u64))
775            .collect();
776        let xorb_hash = merklehash::xorb_hash(&hash_inputs);
777
778        // CAS-Info chunk entries: chunk_hash, byte_range_start, unpacked bytes.
779        let mut cas_entries = Vec::with_capacity(xorb_chunks.len());
780        let mut running_start: u32 = 0;
781        for c in &xorb_chunks {
782            let len = c.data.len() as u32;
783            cas_entries.push(CasChunkSequenceEntry {
784                chunk_hash: c.hash,
785                chunk_byte_range_start: running_start,
786                unpacked_segment_bytes: len,
787                flags: 0,
788                _unused: 0,
789            });
790            running_start = running_start.saturating_add(len);
791        }
792        builder.add_cas(MdbCasInfo {
793            metadata: CasChunkSequenceHeader {
794                cas_hash: xorb_hash,
795                cas_flags: 0,
796                num_entries: cas_entries.len() as u32,
797                num_bytes_in_cas: running_start,
798                // cas-serve stores xorbs uncompressed: on-disk == in-cas.
799                num_bytes_on_disk: running_start,
800            },
801            chunks: cas_entries,
802        });
803
804        // File-Info segment: this xorb holds the whole local chunk range
805        // `[0, xorb_chunk_count)`. Chunk indices in a `FileDataSequenceEntry`
806        // are *local to the referenced xorb* (its CAS entries are numbered
807        // `0..N`), not global file-chunk indices — matching xet-core's
808        // `FileDataSequenceEntry::from_cas_entries`. Since cas-serve packs each
809        // xorb to belong to exactly one file upload, every xorb contributes one
810        // segment spanning all of its chunks.
811        let n_local = (end - start) as u32;
812        file_segments.push(FileDataSequenceEntry {
813            cas_hash: xorb_hash,
814            cas_flags: 0,
815            unpacked_segment_bytes: running_start,
816            chunk_index_start: 0,
817            chunk_index_end: n_local,
818        });
819
820        // Xorb bytes = chunks concatenated (raw; cas-serve stores uncompressed
821        // xorbs, matching `num_bytes_on_disk == num_bytes_in_cas`).
822        let mut bytes = Vec::with_capacity(running_start as usize);
823        for c in &xorb_chunks {
824            bytes.extend_from_slice(&c.data);
825        }
826        xorbs.push((xorb_hash, bytes));
827    }
828
829    // File hash = HMAC'd aggregated node hash over all chunk (hash, len) pairs
830    // — matches `merklehash::file_hash`.
831    let file_hash_inputs: Vec<(MerkleHash, u64)> = chunks
832        .iter()
833        .map(|c| (c.hash, c.data.len() as u64))
834        .collect();
835    let file_hash = merklehash::file_hash(&file_hash_inputs);
836
837    builder.add_file(MdbFileInfo {
838        metadata: FileDataSequenceHeader {
839            file_hash,
840            file_flags: 0, // no verification, no metadata_ext
841            num_entries: file_segments.len() as u32,
842            _unused: 0,
843        },
844        segments: file_segments,
845    });
846
847    (builder, file_hash, xorbs)
848}
849
850// --------------------------------------------------------------------------- //
851// Tests: round-trip + byte-layout parity with the xet-core format.           //
852// --------------------------------------------------------------------------- //
853
854#[cfg(test)]
855#[allow(clippy::unwrap_used, clippy::expect_used)]
856mod tests {
857    use super::*;
858    use crate::chunker::chunk_all;
859
860    /// The header is exactly 48 bytes and the footer exactly 200, matching the
861    /// `size_of` assertions xet-core enforces.
862    #[test]
863    fn header_and_footer_sizes_match_xet_core() {
864        // Header = 32 (tag) + 8 (version) + 8 (footer_size).
865        assert_eq!(32 + size_of::<u64>() + size_of::<u64>(), 48);
866
867        // Footer = 21 u64 fields + 32-byte HMAC key = 200.
868        assert_eq!(MDB_FOOTER_SIZE, 200);
869        // Cross-check the explicit count.
870        let counted = 21 * size_of::<u64>() as u64 + 32;
871        assert_eq!(counted, MDB_FOOTER_SIZE);
872    }
873
874    /// A shard cas-serve builds round-trips through its own reader.
875    #[test]
876    fn build_then_parse_round_trip() {
877        let mut data = Vec::with_capacity(300_000);
878        let mut s: u64 = 42;
879        for _ in 0..37500 {
880            s = s.wrapping_mul(0x94d049bb133111eb) ^ (s >> 31);
881            data.extend_from_slice(&s.to_le_bytes());
882        }
883        let chunks = chunk_all(&data);
884        assert!(chunks.len() > 1);
885
886        let (builder, file_hash, _xorbs) = build_shard(&chunks);
887        let bytes = builder.serialize().unwrap();
888
889        // Magic + versions.
890        assert_eq!(&bytes[..32], &MDB_SHARD_HEADER_TAG);
891        assert_eq!(read_u64(&mut Cursor::new(&bytes[32..40])).unwrap(), 2);
892
893        let shard = MdbShard::parse(&bytes).unwrap();
894        assert_eq!(shard.footer.version, 1);
895        assert_eq!(shard.footer.file_lookup_num_entry, 1);
896
897        let info = shard.file_info(&bytes, &file_hash).unwrap().unwrap();
898        assert_eq!(info.metadata.file_hash, file_hash);
899        assert_eq!(info.metadata.num_entries as usize, info.segments.len());
900        assert_eq!(info.file_size(), data.len() as u64);
901    }
902
903    /// Byte-layout parity: the on-disk offsets a reader computes must land on
904    /// the exact records a writer produced. This is the field-by-field check
905    /// the prompt asks for when full xet-core cross-compilation isn't feasible.
906    #[test]
907    fn offsets_land_on_exact_records() {
908        let data = vec![0x42u8; 200_000];
909        let chunks = chunk_all(&data);
910        let (builder, file_hash, xorbs) = build_shard(&chunks);
911        let bytes = builder.serialize().unwrap();
912        let shard = MdbShard::parse(&bytes).unwrap();
913
914        // File-Info section starts right after the 48-byte header.
915        assert_eq!(shard.footer.file_info_offset, 48);
916
917        // The single file's header is the first record of the file-info section.
918        let mut cur = Cursor::new(&bytes);
919        cur.set_position(shard.footer.file_info_offset);
920        let fh = FileDataSequenceHeader::deserialize(&mut cur).unwrap();
921        assert_eq!(fh.file_hash, file_hash);
922        assert_eq!(fh.num_entries as usize, xorbs.len());
923
924        // Each segment's cas_hash must match a xorb we built.
925        for seg in shard
926            .file_info(&bytes, &file_hash)
927            .unwrap()
928            .unwrap()
929            .segments
930        {
931            assert!(xorbs.iter().any(|(h, _)| *h == seg.cas_hash));
932        }
933
934        // CAS-Info section: each xorb header is where all_cas_blocks lands.
935        let cas = shard.all_cas_blocks(&bytes).unwrap();
936        assert_eq!(cas.len(), xorbs.len());
937        for (info, (h, _)) in cas.iter().zip(&xorbs) {
938            assert_eq!(info.metadata.cas_hash, *h);
939        }
940
941        // Footer is the final 200 bytes.
942        assert_eq!(
943            shard.footer.footer_offset as usize + 200,
944            bytes.len(),
945            "footer_offset + 200 must equal total shard length"
946        );
947    }
948
949    /// Multi-xorb: a file split across several xorbs still reconstructs via the
950    /// mdb_shard binary.
951    #[test]
952    fn multi_xorb_round_trip() {
953        let mut data = Vec::with_capacity(1024 * 1024);
954        let mut s: u64 = 0xdeadbeefcafebabe;
955        for _ in 0..131072 {
956            s ^= s << 13;
957            s ^= s >> 7;
958            s ^= s << 17;
959            data.extend_from_slice(&s.to_le_bytes());
960        }
961        let chunks = chunk_all(&data);
962        let (builder, file_hash, xorbs) = build_shard_with_cap(&chunks, 256 * 1024);
963        assert!(xorbs.len() > 1, "expected multiple xorbs");
964
965        let bytes = builder.serialize().unwrap();
966        let shard = MdbShard::parse(&bytes).unwrap();
967        let info = shard.file_info(&bytes, &file_hash).unwrap().unwrap();
968        assert_eq!(info.metadata.num_entries as usize, xorbs.len());
969
970        // Reassemble exactly as GetFile does: walk segments, slice each xorb by
971        // the chunk-index range.
972        let mut rebuilt = Vec::new();
973        let cas = shard.all_cas_blocks(&bytes).unwrap();
974        for seg in &info.segments {
975            let xorb = cas
976                .iter()
977                .find(|c| c.metadata.cas_hash == seg.cas_hash)
978                .unwrap();
979            for i in seg.chunk_index_start..seg.chunk_index_end {
980                let chunk = &xorb.chunks[i as usize];
981                let start = chunk.chunk_byte_range_start as usize;
982                let end = start + chunk.unpacked_segment_bytes as usize;
983                let xorb_bytes = &xorbs.iter().find(|(h, _)| *h == seg.cas_hash).unwrap().1;
984                rebuilt.extend_from_slice(&xorb_bytes[start..end]);
985            }
986        }
987        assert_eq!(rebuilt, data);
988    }
989}