graph_r/
container.rs

1// Author: spicyzhug@gmail.com
2// Copyright: lituus-io, all rights reserved
3//
4//! A checksummed, sectioned, 64-aligned file container: the one on-disk
5//! framing behind graph-r's base snapshot and every dependant's images.
6//!
7//! ```text
8//! [header 128 B][directory: 32 B × sections][sections, each 64-aligned]
9//! header:  0 magic u32 | 4 version u16 | 6 flags u16 | 8 header_len u32
10//!         12 section_count u32 | 16 total_len u64 | 24 directory xxh3 u64
11//!         32..120 owner area (88 B, the format's own fields)
12//!        120 header xxh3 u64
13//! entry:   kind u16 | flags u16 | 0 u32 | offset u64 | length u64 | xxh3 u64
14//! ```
15//!
16//! Every byte is covered by exactly one checksum — header, directory, or its
17//! section — so opening validates each byte once. Section lookup is O(1) by
18//! kind. Readers hold offsets, not borrows, so a [`Dir`] can live beside the
19//! mapping it describes. Unknown kinds are kept and ignored, so a format can
20//! grow sections without breaking older readers.
21
22use crate::bytesio::{align_up, get_u16, get_u32, get_u64, put_u16, put_u32, put_u64};
23use crate::error::{Error, Result};
24use crate::hash::xxh3_64;
25
26/// Header width.
27pub const HEADER_LEN: usize = 128;
28/// Bytes of the header that belong to the format using the container.
29pub const OWNER_LEN: usize = 88;
30/// Directory entry width.
31pub const DIR_ENTRY_LEN: usize = 32;
32/// Section alignment.
33pub const ALIGN: usize = 64;
34/// Kinds below this resolve in O(1); larger kinds by scanning.
35const FAST_KINDS: usize = 32;
36
37const OWNER_AT: usize = 32;
38const SUM_AT: usize = HEADER_LEN - 8;
39
40/// Identity of a format: its magic and the one version it reads.
41#[derive(Clone, Copy, Debug, PartialEq, Eq)]
42pub struct Format {
43    /// Four magic bytes, as a little-endian u32.
44    pub magic: u32,
45    /// The version written and accepted (strict equality).
46    pub version: u16,
47}
48
49/// Builds a container: the owner area, then sections in order.
50#[derive(Debug)]
51pub struct Writer {
52    format: Format,
53    flags: u16,
54    owner: [u8; OWNER_LEN],
55    sections: Vec<(u16, u16, Vec<u8>)>,
56}
57
58impl Writer {
59    /// A writer for `format`.
60    #[must_use]
61    pub fn new(format: Format) -> Self {
62        Self { format, flags: 0, owner: [0; OWNER_LEN], sections: Vec::new() }
63    }
64
65    /// Header flags (the format's own meaning).
66    pub fn flags(&mut self, flags: u16) -> &mut Self {
67        self.flags = flags;
68        self
69    }
70
71    /// The format's own header fields (up to [`OWNER_LEN`] bytes, rest zero).
72    pub fn owner(&mut self, bytes: &[u8]) -> &mut Self {
73        let n = bytes.len().min(OWNER_LEN);
74        self.owner[..n].copy_from_slice(&bytes[..n]);
75        self
76    }
77
78    /// Append one section (empty sections are omitted: absent reads as empty).
79    pub fn section(&mut self, kind: u16, bytes: Vec<u8>) -> &mut Self {
80        self.section_flagged(kind, 0, bytes)
81    }
82
83    /// Append one section with per-section flags (the format's own meaning,
84    /// e.g. "compressed"), read back by [`Dir::section_flags`].
85    pub fn section_flagged(&mut self, kind: u16, flags: u16, bytes: Vec<u8>) -> &mut Self {
86        if !bytes.is_empty() {
87            self.sections.push((kind, flags, bytes));
88        }
89        self
90    }
91
92    /// The finished file.
93    #[must_use]
94    pub fn finish(&self) -> Vec<u8> {
95        let dir_end = HEADER_LEN + self.sections.len() * DIR_ENTRY_LEN;
96        let mut offset = align_up(dir_end, ALIGN);
97        let mut dir = Vec::with_capacity(self.sections.len() * DIR_ENTRY_LEN);
98        for (kind, flags, bytes) in &self.sections {
99            put_u16(&mut dir, *kind);
100            put_u16(&mut dir, *flags);
101            put_u32(&mut dir, 0);
102            put_u64(&mut dir, offset as u64);
103            put_u64(&mut dir, bytes.len() as u64);
104            put_u64(&mut dir, xxh3_64(bytes));
105            offset = align_up(offset + bytes.len(), ALIGN);
106        }
107        let total = offset.max(dir_end);
108        let mut out = Vec::with_capacity(total);
109        put_u32(&mut out, self.format.magic);
110        put_u16(&mut out, self.format.version);
111        put_u16(&mut out, self.flags);
112        put_u32(&mut out, HEADER_LEN as u32);
113        put_u32(&mut out, self.sections.len() as u32);
114        put_u64(&mut out, total as u64);
115        put_u64(&mut out, xxh3_64(&dir));
116        out.extend_from_slice(&self.owner);
117        let sum = xxh3_64(&out[..SUM_AT]);
118        put_u64(&mut out, sum);
119        out.extend_from_slice(&dir);
120        for (_, _, bytes) in &self.sections {
121            out.resize(align_up(out.len(), ALIGN), 0);
122            out.extend_from_slice(bytes);
123        }
124        out.resize(total, 0);
125        out
126    }
127}
128
129/// Check only the header of `bytes` (magic, version, header checksum) and
130/// return its flags and owner area: a cheap peek at a file's identity fields.
131pub fn peek(bytes: &[u8], format: Format) -> Result<(u16, [u8; OWNER_LEN])> {
132    check_header(bytes, format)?;
133    let mut owner = [0; OWNER_LEN];
134    owner.copy_from_slice(&bytes[OWNER_AT..OWNER_AT + OWNER_LEN]);
135    Ok((get_u16(bytes, 6), owner))
136}
137
138fn check_header(bytes: &[u8], format: Format) -> Result<()> {
139    if bytes.len() < HEADER_LEN {
140        return Err(Error::format("file shorter than header"));
141    }
142    if get_u32(bytes, 0) != format.magic {
143        return Err(Error::format("bad magic"));
144    }
145    let version = get_u16(bytes, 4);
146    if version != format.version {
147        return Err(Error::Version { found: version, supported: format.version });
148    }
149    if xxh3_64(&bytes[..SUM_AT]) != get_u64(bytes, SUM_AT) {
150        return Err(Error::format("header checksum mismatch"));
151    }
152    if get_u32(bytes, 8) as usize != HEADER_LEN {
153        return Err(Error::format("unexpected header length"));
154    }
155    Ok(())
156}
157
158/// A validated container: header fields and section ranges.
159#[derive(Clone, Debug)]
160pub struct Dir {
161    /// Header flags.
162    pub flags: u16,
163    owner: [u8; OWNER_LEN],
164    fast: [(usize, usize, u16); FAST_KINDS],
165    other: Vec<(u16, usize, usize, u16)>,
166}
167
168impl Dir {
169    /// Validate `bytes` as a container of `format`: header, directory and
170    /// every section checksummed once, bounds and alignment checked. Any
171    /// input yields `Ok`, [`Error::Format`] or [`Error::Version`], never a
172    /// panic.
173    pub fn parse(bytes: &[u8], format: Format) -> Result<Self> {
174        check_header(bytes, format)?;
175        if get_u64(bytes, 16) != bytes.len() as u64 {
176            return Err(Error::format("total length does not match file size"));
177        }
178        let count = get_u32(bytes, 12) as usize;
179        let dir_end = count
180            .checked_mul(DIR_ENTRY_LEN)
181            .and_then(|l| l.checked_add(HEADER_LEN))
182            .filter(|&e| e <= bytes.len())
183            .ok_or_else(|| Error::format("directory exceeds file"))?;
184        if xxh3_64(&bytes[HEADER_LEN..dir_end]) != get_u64(bytes, 24) {
185            return Err(Error::format("directory checksum mismatch"));
186        }
187        let mut dir = Self {
188            flags: get_u16(bytes, 6),
189            owner: [0; OWNER_LEN],
190            fast: [(0, 0, 0); FAST_KINDS],
191            other: Vec::new(),
192        };
193        dir.owner.copy_from_slice(&bytes[OWNER_AT..OWNER_AT + OWNER_LEN]);
194        let mut spans: Vec<(usize, usize)> = Vec::with_capacity(count.min(64));
195        for i in 0..count {
196            let e = HEADER_LEN + i * DIR_ENTRY_LEN;
197            let (kind, sflags) = (get_u16(bytes, e), get_u16(bytes, e + 2));
198            let (offset, length) = (get_u64(bytes, e + 8), get_u64(bytes, e + 16));
199            let offset = usize::try_from(offset).map_err(|_| Error::format("section offset"))?;
200            let length = usize::try_from(length).map_err(|_| Error::format("section length"))?;
201            let end =
202                offset.checked_add(length).ok_or_else(|| Error::format("section overflow"))?;
203            if offset < dir_end || end > bytes.len() {
204                return Err(Error::format("section out of bounds"));
205            }
206            if !offset.is_multiple_of(ALIGN) {
207                return Err(Error::format("section misaligned"));
208            }
209            if xxh3_64(&bytes[offset..end]) != get_u64(bytes, e + 24) {
210                return Err(Error::format("section checksum mismatch"));
211            }
212            if dir.range(kind).is_some() {
213                return Err(Error::format("duplicate section"));
214            }
215            match dir.fast.get_mut(usize::from(kind)) {
216                Some(slot) => *slot = (offset, length, sflags),
217                None => dir.other.push((kind, offset, length, sflags)),
218            }
219            spans.push((offset, end));
220        }
221        // Alignment padding carries no data and must be zero, so every byte
222        // of a file is accounted for and the bytes of a state are unique.
223        spans.sort_unstable();
224        let mut at = dir_end;
225        for (start, end) in spans.into_iter().chain([(bytes.len(), bytes.len())]) {
226            if start < at || bytes[at..start].iter().any(|&b| b != 0) {
227                return Err(Error::format("sections overlap or padding is not zero"));
228            }
229            at = end;
230        }
231        Ok(dir)
232    }
233
234    /// The format's own header fields.
235    #[must_use]
236    pub fn owner(&self) -> &[u8; OWNER_LEN] {
237        &self.owner
238    }
239
240    /// Byte range of section `kind` (empty when absent), for owners that
241    /// keep offsets instead of slices.
242    #[must_use]
243    pub fn span(&self, kind: u16) -> std::ops::Range<usize> {
244        self.range(kind).map_or(0..0, |(o, l)| o..o + l)
245    }
246
247    fn entry(&self, kind: u16) -> Option<(usize, usize, u16)> {
248        match self.fast.get(usize::from(kind)) {
249            Some(&(o, l, f)) => (l > 0).then_some((o, l, f)),
250            None => self.other.iter().find(|e| e.0 == kind).map(|&(_, o, l, f)| (o, l, f)),
251        }
252    }
253
254    fn range(&self, kind: u16) -> Option<(usize, usize)> {
255        self.entry(kind).map(|(o, l, _)| (o, l))
256    }
257
258    /// The per-section flags of `kind` (0 when absent).
259    #[must_use]
260    pub fn section_flags(&self, kind: u16) -> u16 {
261        self.entry(kind).map_or(0, |e| e.2)
262    }
263
264    /// Whether section `kind` is present.
265    #[must_use]
266    pub fn has(&self, kind: u16) -> bool {
267        self.entry(kind).is_some()
268    }
269
270    /// Section `kind` of `bytes` (the bytes this directory was parsed from);
271    /// empty when absent.
272    #[must_use]
273    pub fn section<'a>(&self, bytes: &'a [u8], kind: u16) -> &'a [u8] {
274        self.range(kind).and_then(|(o, l)| bytes.get(o..o + l)).unwrap_or(&[])
275    }
276}
277
278#[cfg(test)]
279mod tests {
280    use super::*;
281
282    const F: Format = Format { magic: 0x5453_4554, version: 3 };
283
284    #[test]
285    fn round_trips_sections_and_owner_fields() {
286        let mut w = Writer::new(F);
287        w.flags(7).owner(&[1, 2, 3]).section(2, vec![9; 100]).section(40, b"far".to_vec());
288        w.section(5, Vec::new());
289        let bytes = w.finish();
290        assert!(bytes.len().is_multiple_of(ALIGN));
291        let d = Dir::parse(&bytes, F).unwrap();
292        assert_eq!((d.flags, &d.owner()[..4]), (7, &[1, 2, 3, 0][..]));
293        assert_eq!(d.section(&bytes, 2), &[9; 100][..]);
294        assert_eq!(d.section(&bytes, 40), b"far");
295        assert!(d.section(&bytes, 5).is_empty() && d.section(&bytes, 3).is_empty());
296        assert!(d.has(2) && !d.has(5) && d.section_flags(2) == 0);
297        let mut w = Writer::new(F);
298        w.section_flagged(1, 0b10, vec![1]).section_flagged(50, 3, vec![2]);
299        let bytes = w.finish();
300        let d = Dir::parse(&bytes, F).unwrap();
301        assert_eq!((d.section_flags(1), d.section_flags(50), d.section_flags(9)), (0b10, 3, 0));
302        let empty = Writer::new(F).finish();
303        assert_eq!(empty.len(), HEADER_LEN);
304        assert!(Dir::parse(&empty, F).is_ok());
305    }
306
307    #[test]
308    fn every_byte_is_checked() {
309        let mut w = Writer::new(F);
310        w.owner(&[5; 10]).section(1, vec![1; 70]).section(2, vec![2; 3]);
311        let bytes = w.finish();
312        for i in 0..bytes.len() {
313            let mut bad = bytes.clone();
314            bad[i] ^= 0x40;
315            assert!(Dir::parse(&bad, F).is_err(), "byte {i}");
316        }
317        assert!(Dir::parse(&bytes, Format { version: 4, ..F }).is_err());
318        assert!(Dir::parse(&bytes[..bytes.len() - 1], F).is_err());
319    }
320}
graph_r/container.rs

graph_r/
container.rs
