Skip to main content

frostbite_formats/
toc.rs

1//! Superbundle TOC (`*.toc`): a 0x22C-byte envelope, then a big-endian header, the bundles (name, inline region)
2//! and the chunk table, each found through a perfect hash over its keys (lowercase bundle names, chunk GUIDs).
3//! Base-game TOCs store names Huffman-coded (flag 4); Patch TOCs (the ones in a folder of added or replaced files,
4//! as ReSkate Studio writes it beside the game's `Data`) store them as plain strings, which is what [`write()`] writes.
5
6use crate::{Error, Rd, Result, align, bad, latin1};
7
8/// Length of the envelope that precedes a TOC's (or `layout.toc`'s) own data.
9pub const ENVELOPE: usize = 0x22C;
10/// The four bytes an envelope starts with.
11pub const MAGIC: [u8; 4] = [0x00, 0xd1, 0xce, 0x01];
12const FNV_SEED: u32 = 0x811C_9DC5;
13const W: &str = "toc";
14/// A Huffman table entry with this bit set is a leaf (`!char`); one without it names an internal node by its counter.
15const LEAF: u32 = 0x8000_0000;
16
17/// The bits of a TOC's flags word (header word 11).
18pub mod flags {
19    /// The base game's TOC of the same superbundle has bundles this one does not list: [`merge`](super::merge) takes them.
20    /// Set, with [`HAS_BASE_CHUNKS`], in 199 of the 245 TOCs of the installed mods (flags word 3; the other 46 are 0, and
21    /// 30 of the 199 have no base TOC in the stock data); the stock TOCs hold 4.
22    pub const HAS_BASE_BUNDLES: u32 = 1;
23    /// The base game's TOC has chunks this one does not list.
24    pub const HAS_BASE_CHUNKS: u32 = 2;
25    /// Bundle names are Huffman coded (the base game's TOCs).
26    pub const HUFFMAN_NAMES: u32 = 4;
27}
28
29/// Where a file lives: (patch folder or base game, install chunk, archive number).
30#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
31pub struct Loc {
32    /// Whether the file is in a Patch folder (the added or replaced files) rather than the base game: bits 48..56 of
33    /// the stored identifier, 1 for the Patch folder and 0 for the base game.
34    pub patch: bool,
35    /// Install chunk number: bits 16..48 of the stored identifier.
36    pub chunk: u32,
37    /// Archive number within the chunk: the low 16 bits of the stored identifier.
38    pub archive: u16,
39}
40
41impl Loc {
42    /// A `Loc` from the 64-bit identifier a TOC or region stores, or `None` when the identifier holds something a
43    /// `Loc` can't represent (bits 48..56 other than 0 or 1, or any of bits 56..64 set), so that
44    /// [`encode`](Self::encode) gives back exactly the stored identifier.
45    pub fn decode(v: u64) -> Option<Self> {
46        let [a0, a1, c0, c1, c2, c3, patch, top] = v.to_le_bytes();
47        (patch <= 1 && top == 0).then(|| Self {
48            patch: patch == 1,
49            chunk: u32::from_le_bytes([c0, c1, c2, c3]),
50            archive: u16::from_le_bytes([a0, a1]),
51        })
52    }
53    /// The 64-bit identifier a TOC or region stores for this `Loc`.
54    pub fn encode(self) -> u64 {
55        (u64::from(self.patch) << 48) | (u64::from(self.chunk) << 16) | u64::from(self.archive)
56    }
57}
58
59/// The refusal text for an archive identifier [`Loc::decode`] can't represent.
60pub(crate) fn unrepresentable(id: u64) -> String {
61    format!(
62        "archive identifier {id:#018x}: expected bits 48..56 (the patch flag) to be 0 or 1 and bits 56..64 to be 0"
63    )
64}
65
66/// A chunk row of a TOC: GUID (as stored in bundles: little endian) and its file, or removed.
67#[derive(Clone, Debug, PartialEq, Eq)]
68pub struct TocChunk {
69    /// The chunk's GUID in the byte order bundle manifests use (the TOC stores it reversed).
70    pub guid: [u8; 16],
71    /// `None` for a removed chunk.
72    pub file: Option<(Loc, u32, u32)>,
73}
74
75/// A superbundle TOC as stored: its flags, its bundles (name and inline region bytes), its chunk table and the
76/// perfect-hash maps over the bundle names and chunk GUIDs.
77#[derive(Clone, Debug, Default, PartialEq, Eq)]
78pub struct Toc {
79    /// The TOC's flags word (header word 11). Bit 2 (value 4) means names are Huffman-coded, as in base-game TOCs; the rest are kept as stored.
80    pub flags: u32,
81    /// (name, inline bundle region bytes), in file order.
82    pub bundles: Vec<(String, Vec<u8>)>,
83    /// Where each chunk lives, in the order the TOC lists them; `None` for a removed chunk (stored as `-1`).
84    pub chunks: Vec<TocChunk>,
85    /// The perfect-hash table over the lowercased bundle names: one `i32` per bundle, a positive seed or `!slot` (see [`perfect_hash`]).
86    pub bundle_hash: Vec<i32>,
87    /// The perfect-hash table over the chunk GUIDs, in the same form; empty when the TOC lists no chunks.
88    pub chunk_hash: Vec<i32>,
89}
90
91impl Toc {
92    /// Whether the flags word says the base game's TOC lists bundles this one lacks ([`flags::HAS_BASE_BUNDLES`]).
93    pub fn has_base_bundles(&self) -> bool {
94        self.flags & flags::HAS_BASE_BUNDLES != 0
95    }
96    /// Whether the flags word says the base game's TOC lists chunks this one lacks ([`flags::HAS_BASE_CHUNKS`]).
97    pub fn has_base_chunks(&self) -> bool {
98        self.flags & flags::HAS_BASE_CHUNKS != 0
99    }
100}
101
102/// The TOC a patch TOC describes together with the base TOC it builds on: what the game sees of the superbundle.
103///
104/// - With [`flags::HAS_BASE_BUNDLES`] the base's bundles stay, except those the patch lists again (matched by lowercase
105///   name: the patch's replaces the base's, wherever it stood); the patch's follow. Without it only the patch's bundles
106///   are kept.
107/// - With [`flags::HAS_BASE_CHUNKS`] the base's chunks stay, except those the patch lists again (matched by GUID); a
108///   patch chunk stored as removed (`None`) drops the base's and is not listed; the patch's others follow. Without it
109///   the patch's chunks are kept as they are.
110///
111/// The merged TOC keeps the patch's flags word minus the base bits and the Huffman bit, so it reads as a TOC that
112/// stands alone. Its entries are in the order of the perfect hash [`write`] lays out ([`perfect_hash`] over the merged
113/// keys), so [`verify`] holds and the TOC writes and reads back as it is. An error when the
114/// merged keys are not unique (a duplicate name that differs only in case within the patch or the base).
115pub fn merge(base: &Toc, patch: &Toc) -> Result<Toc> {
116    let key = |name: &str| name.to_lowercase();
117    let mut bundles: Vec<(String, Vec<u8>)> = Vec::new();
118    if patch.has_base_bundles() {
119        let replaced: std::collections::BTreeSet<String> =
120            patch.bundles.iter().map(|(n, _)| key(n)).collect();
121        bundles.extend(
122            base.bundles
123                .iter()
124                .filter(|(n, _)| !replaced.contains(&key(n)))
125                .cloned(),
126        );
127    }
128    bundles.extend(patch.bundles.iter().cloned());
129    let mut chunks: Vec<TocChunk> = Vec::new();
130    if patch.has_base_chunks() {
131        let overridden: std::collections::BTreeSet<[u8; 16]> = patch.chunks.iter().map(|c| c.guid).collect();
132        chunks.extend(
133            base.chunks
134                .iter()
135                .filter(|c| !overridden.contains(&c.guid))
136                .cloned(),
137        );
138    }
139    chunks.extend(
140        patch
141            .chunks
142            .iter()
143            .filter(|c| c.file.is_some() || !patch.has_base_chunks())
144            .cloned(),
145    );
146    let bkeys = bundles
147        .iter()
148        .map(|(n, _)| bundle_key(n))
149        .collect::<Result<Vec<_>>>()?;
150    let ckeys: Vec<Vec<u8>> = chunks.iter().map(|c| c.guid.to_vec()).collect();
151    let (bundle_hash, border) = perfect_hash(&bkeys)?;
152    let (chunk_hash, corder) = perfect_hash(&ckeys)?;
153    // a TOC lists its entries in the order of the perfect hash's slots: the stored tables index that order
154    let in_order = |order: &[usize], n: usize| -> Result<Vec<usize>> {
155        (order.len() == n && order.iter().all(|&i| i < n))
156            .then(|| order.to_vec())
157            .ok_or_else(|| bad(W, 0, "perfect-hash order does not cover the merged entries"))
158    };
159    let (border, corder) = (
160        in_order(&border, bundles.len())?,
161        in_order(&corder, chunks.len())?,
162    );
163    let merged = Toc {
164        flags: patch.flags & !(flags::HAS_BASE_BUNDLES | flags::HAS_BASE_CHUNKS | flags::HUFFMAN_NAMES),
165        bundle_hash,
166        chunk_hash,
167        bundles: border.iter().filter_map(|&i| bundles.get(i).cloned()).collect(),
168        chunks: corder.iter().filter_map(|&i| chunks.get(i).cloned()).collect(),
169    };
170    Ok(merged)
171}
172
173/// Huffman-coded names: leaves are `!char` values (top bit set), internal nodes counters, read in pairs (left, right).
174struct Huffman {
175    words: Vec<u32>,
176    nodes: Vec<(u32, Option<(usize, usize)>)>,
177    /// `None` for an empty table (a TOC without names).
178    root: Option<usize>,
179}
180
181impl Huffman {
182    fn read(r: &Rd, names_at: usize, names_n: usize, table_at: usize, table_n: usize) -> Result<Self> {
183        let words = (0..names_n)
184            .map(|i| r.u32be(crate::at(names_at, i, 4)))
185            .collect::<Result<Vec<_>>>()?;
186        let mut nodes: Vec<(u32, Option<(usize, usize)>)> = Vec::new();
187        // A table entry is a leaf (`!char`: the top bit set) or the counter of an internal node built before it, so the two
188        // kinds of value are disjoint and each has its own map: a stray small value cannot become a leaf that shadows an
189        // internal node of the same number.
190        let mut leaves = std::collections::BTreeMap::new();
191        let mut internal = std::collections::BTreeMap::new();
192        let (mut left, mut counter, mut root) = (None, 0u32, None);
193        for i in 0..table_n {
194            let at = crate::at(table_at, i, 4);
195            let v = r.u32be(at)?;
196            let node = if v & LEAF != 0 {
197                *leaves.entry(v).or_insert_with(|| {
198                    nodes.push((v, None));
199                    nodes.len().saturating_sub(1)
200                })
201            } else {
202                *internal.get(&v).ok_or_else(|| {
203                    bad(
204                        W,
205                        at,
206                        format!(
207                            "Huffman entry {v:#x} is neither a character nor an internal node built before it"
208                        ),
209                    )
210                })?
211            };
212            let Some(l) = left.take() else {
213                left = Some(node);
214                continue;
215            };
216            nodes.push((counter, Some((l, node))));
217            let parent = nodes.len().saturating_sub(1);
218            internal.insert(counter, parent);
219            root = Some(parent);
220            counter = counter.saturating_add(1);
221        }
222        Ok(Self { words, nodes, root })
223    }
224
225    /// The name whose code starts at bit `bit` of the name words.
226    fn decode(&self, mut bit: usize) -> Result<String> {
227        let nbits = self.words.len().saturating_mul(32);
228        let mut out = String::new();
229        let root = self
230            .root
231            .ok_or_else(|| bad(W, bit / 8, "a name in a TOC with an empty Huffman table"))?;
232        let node = |n: usize, bit: usize| {
233            self.nodes
234                .get(n)
235                .ok_or_else(|| bad(W, bit / 8, format!("Huffman node {n} of {}", self.nodes.len())))
236        };
237        while bit < nbits {
238            let mut n = root;
239            while let (_, Some((l, r))) = *node(n, bit)? {
240                let word = self
241                    .words
242                    .get(bit >> 5)
243                    .ok_or_else(|| bad(W, bit / 8, "Huffman name runs past the data"))?;
244                let one = (word >> (bit & 31)) & 1 != 0;
245                n = if one { r } else { l };
246                bit = bit.saturating_add(1);
247                if bit > nbits {
248                    return Err(bad(W, bit / 8, "Huffman name runs past the data"));
249                }
250            }
251            let ch = !node(n, bit)?.0 & 0xFFFF;
252            if ch == 0 {
253                return Ok(out);
254            }
255            out.push(char::from_u32(ch).ok_or_else(|| bad(W, bit / 8, "Huffman character is not a char"))?);
256        }
257        Err(bad(W, bit / 8, "Huffman name is unterminated"))
258    }
259}
260
261/// Read a TOC (envelope included). Refused: a wrong envelope, a negative count, a table or string outside the
262/// file, a bundle region that is not inline, a Huffman table or name that does not decode, a chunk reference that
263/// does not resolve. An error's offset is into `data`, the envelope included.
264pub fn read(data: &[u8]) -> Result<Toc> {
265    match data.split_at_checked(ENVELOPE) {
266        Some((envelope, body)) if body.len() >= 48 && envelope.starts_with(&MAGIC) => read_body(body)
267            .map_err(|e| match e {
268                Error::Format { what, offset, detail } => Error::Format {
269                    what,
270                    offset: offset.saturating_add(ENVELOPE),
271                    detail,
272                },
273                other => other,
274            }),
275        _ => Err(bad(
276            W,
277            0,
278            format!(
279                "envelope is invalid: expected the magic {MAGIC:02x?} and {} bytes at least, got {} bytes",
280                ENVELOPE + 48,
281                data.len()
282            ),
283        )),
284    }
285}
286
287/// The TOC after its envelope; error offsets are into `data`.
288fn read_body(data: &[u8]) -> Result<Toc> {
289    let r = Rd::new(data, W);
290    let u = |i: usize| r.u32be(crate::at(0, i, 4));
291    let (bho, bdo, cho, cgo, nameso, cdo, flags) = (
292        u(0)? as usize,
293        u(1)? as usize,
294        u(3)? as usize,
295        u(4)? as usize,
296        u(8)? as usize,
297        u(9)? as usize,
298        u(11)?,
299    );
300    let count = |i: usize| -> Result<usize> {
301        let at = crate::at(0, i, 4);
302        usize::try_from(r.i32be(at)?).map_err(|_| bad(W, at, "count is negative, expected 0 or more"))
303    };
304    let (bcount, ccount, dcount) = (count(2)?, count(5)?, count(10)?);
305    let huffman = if flags & 4 != 0 {
306        let (n, t, at) = (
307            r.u32be(48)? as usize,
308            r.u32be(52)? as usize,
309            r.u32be(56)? as usize,
310        );
311        Some(Huffman::read(&r, nameso, n, at, t)?)
312    } else {
313        None
314    };
315    let mut toc = Toc {
316        flags,
317        bundles: Vec::new(),
318        chunks: Vec::new(),
319        bundle_hash: Vec::new(),
320        chunk_hash: Vec::new(),
321    };
322    toc.bundle_hash = (0..bcount)
323        .map(|i| r.i32be(crate::at(bho, i, 4)))
324        .collect::<Result<_>>()?;
325    for i in 0..bcount {
326        let at = crate::at(bdo, i, 16);
327        let (no, sf, ro) = (
328            r.u32be(at)? as usize,
329            r.u32be(at.saturating_add(4))?,
330            r.u64be(at.saturating_add(8))?,
331        );
332        if sf >> 30 != 1 {
333            return Err(bad(
334                W,
335                at.saturating_add(4),
336                format!("bundle region flags {sf:#x}: expected the inline form (bits 31..30 equal to 0b01)"),
337            ));
338        }
339        let name = match &huffman {
340            Some(h) => h.decode(no)?,
341            None => r.cstr(nameso.saturating_add(no))?,
342        };
343        let ro = usize::try_from(ro).map_err(|_| {
344            bad(
345                W,
346                at.saturating_add(8),
347                format!("region offset {ro:#x} does not fit the address space"),
348            )
349        })?;
350        toc.bundles
351            .push((name, r.bytes(ro, (sf & 0x3FFF_FFFF) as usize)?.to_vec()));
352    }
353    if ccount != 0 {
354        toc.chunk_hash = (0..ccount)
355            .map(|i| r.i32be(crate::at(cho, i, 4)))
356            .collect::<Result<_>>()?;
357        let words = (0..dcount)
358            .map(|i| r.u32be(crate::at(cdo, i, 4)))
359            .collect::<Result<Vec<_>>>()?;
360        for i in 0..ccount {
361            let at = crate::at(cgo, i, 20);
362            let mut guid: [u8; 16] = r.arr(at)?;
363            guid.reverse();
364            let ref_at = at.saturating_add(16);
365            let enc = r.i32be(ref_at)?.cast_unsigned();
366            if enc == u32::MAX {
367                toc.chunks.push(TocChunk { guid, file: None });
368                continue;
369            }
370            let (flag, w) = (enc >> 24, (enc & 0xFF_FFFF) as usize);
371            let record = (flag == 0x80)
372                .then(|| words.get(w..).and_then(|rest| rest.first_chunk::<4>()))
373                .flatten();
374            let Some(&[loc_high, loc_low, offset, size]) = record else {
375                return Err(bad(
376                    W,
377                    ref_at,
378                    format!(
379                        "chunk data reference {enc:#010x}: expected -1 or 0x80 and the index of a 4-word record among the {} data words",
380                        words.len()
381                    ),
382                ));
383            };
384            let id = (u64::from(loc_high) << 32) | u64::from(loc_low);
385            let loc = Loc::decode(id).ok_or_else(|| bad(W, crate::at(cdo, w, 4), unrepresentable(id)))?;
386            toc.chunks.push(TocChunk {
387                guid,
388                file: Some((loc, offset, size)),
389            });
390        }
391    }
392    Ok(toc)
393}
394
395/// The TOC's FNV-1: multiply by 0x01000193, xor the sign-extended byte, wrapping; reduced modulo 0x01000193 once at
396/// the end. The tables' default seed is 0x811C9DC5.
397fn hash_with(key: &[u8], seed: u32) -> u32 {
398    key.iter().fold(seed, |h, &b| {
399        h.wrapping_mul(0x01000193) ^ (b as i8 as i32).cast_unsigned()
400    }) % 0x01000193
401}
402
403/// The slot of `key` among `size` (not 0) under `seed`: its hash modulo the size.
404fn slot(key: &[u8], seed: u32, size: usize) -> usize {
405    usize::try_from(hash_with(key, seed))
406        .ok()
407        .and_then(|h| h.checked_rem(size))
408        .unwrap_or(0)
409}
410
411/// The perfect hash the TOC stores over `keys`: (hash map, key index per slot). Mirrors the game tools: buckets by
412/// first hash, the multi-key buckets largest first (stable) get a seed that separates them, single keys fill free
413/// slots in order, encoded as `-slot - 1`. An error when the keys are not unique, or when the table is too large for
414/// the 32-bit entries it is stored in.
415pub fn perfect_hash(keys: &[Vec<u8>]) -> Result<(Vec<i32>, Vec<usize>)> {
416    let size = keys.len();
417    let mut map = vec![-1i32; size];
418    let mut order = vec![usize::MAX; size];
419    if size == 0 {
420        return Ok((map, order));
421    }
422    let mut seen = keys.to_vec();
423    seen.sort();
424    seen.dedup();
425    if seen.len() != size {
426        return Err(bad(W, 0, "perfect-hash keys are not unique"));
427    }
428    let too_large = || {
429        bad(
430            W,
431            0,
432            format!("{size} keys do not fit the 32-bit entries of a perfect hash"),
433        )
434    };
435    let first: Vec<usize> = keys.iter().map(|k| slot(k, FNV_SEED, size)).collect();
436    let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); size];
437    for (i, &s) in first.iter().enumerate() {
438        if let Some(bucket) = buckets.get_mut(s) {
439            bucket.push(i);
440        }
441    }
442    buckets.sort_by_key(|b| std::cmp::Reverse(b.len()));
443    let mut used = vec![false; size];
444    let multi = buckets.iter().take_while(|b| b.len() > 1).count();
445    for bucket in buckets.iter().take(multi) {
446        let mut seed = 1u32;
447        let slots = loop {
448            let mut slots = Vec::with_capacity(bucket.len());
449            let ok = bucket.iter().all(|&m| {
450                let s = keys.get(m).map_or(0, |k| slot(k, seed, size));
451                let free = used.get(s) == Some(&false) && !slots.contains(&s);
452                slots.push(s);
453                free
454            });
455            if ok {
456                break slots;
457            }
458            seed = seed
459                .checked_add(1)
460                .ok_or_else(|| bad(W, 0, "no seed separates a bucket of keys"))?;
461        };
462        let head = bucket.first().and_then(|&m| first.get(m)).copied();
463        if let Some(entry) = head.and_then(|h| map.get_mut(h)) {
464            *entry = i32::try_from(seed).map_err(|_| too_large())?;
465        }
466        for (&s, &m) in slots.iter().zip(bucket) {
467            if let Some(o) = order.get_mut(s) {
468                *o = m;
469            }
470            if let Some(u) = used.get_mut(s) {
471                *u = true;
472            }
473        }
474    }
475    let mut free = 0usize;
476    for bucket in buckets.iter().skip(multi).take_while(|b| !b.is_empty()) {
477        while used.get(free) == Some(&true) {
478            free = free.saturating_add(1).checked_rem(size).unwrap_or(0);
479        }
480        let Some(&m) = bucket.first() else { break };
481        let entry = first.get(m).and_then(|&h| map.get_mut(h));
482        if let Some(entry) = entry {
483            *entry = !i32::try_from(free).map_err(|_| too_large())?;
484        }
485        if let Some(o) = order.get_mut(free) {
486            *o = m;
487        }
488        if let Some(u) = used.get_mut(free) {
489            *u = true;
490        }
491        free = free.saturating_add(1).checked_rem(size).unwrap_or(0);
492    }
493    Ok((map, order))
494}
495
496/// Index of `key` in `ordered` through the stored hash map, as the game looks it up.
497pub fn lookup(map: &[i32], ordered: &[Vec<u8>], key: &[u8]) -> Option<usize> {
498    if map.is_empty() || map.len() != ordered.len() {
499        return None;
500    }
501    let v = *map.get(slot(key, FNV_SEED, map.len()))?;
502    let i = if v < 0 {
503        // the stored slot is `-slot - 1`, which is `!v`; no negation, so `i32::MIN` names the absent slot 2^31 - 1
504        usize::try_from(!v).ok()?
505    } else {
506        slot(key, v.cast_unsigned(), map.len())
507    };
508    (ordered.get(i)? == key).then_some(i)
509}
510
511fn bundle_key(name: &str) -> Result<Vec<u8>> {
512    latin1(&name.to_lowercase(), W)
513}
514
515/// Every bundle and chunk resolves through the stored perfect hashes. The offset of an error is the index of the
516/// bundle or chunk that does not.
517pub fn verify(toc: &Toc) -> Result<()> {
518    let keys = toc
519        .bundles
520        .iter()
521        .map(|(n, _)| bundle_key(n))
522        .collect::<Result<Vec<_>>>()?;
523    for (i, k) in keys.iter().enumerate() {
524        if lookup(&toc.bundle_hash, &keys, k) != Some(i) {
525            return Err(bad(
526                W,
527                i,
528                "bundle perfect hash does not resolve: expected the name to find its own index",
529            ));
530        }
531    }
532    let keys: Vec<Vec<u8>> = toc.chunks.iter().map(|c| c.guid.to_vec()).collect();
533    for (i, k) in keys.iter().enumerate() {
534        if lookup(&toc.chunk_hash, &keys, k) != Some(i) {
535            return Err(bad(
536                W,
537                i,
538                "chunk perfect hash does not resolve: expected the GUID to find its own index",
539            ));
540        }
541    }
542    Ok(())
543}
544
545/// A Patch TOC (plain names): bundles and chunks are laid out in perfect-hash order. `flags` must not ask for
546/// Huffman names. An error when a size or offset does not fit the 32 bits it is stored in.
547pub fn write(bundles: &[(String, Vec<u8>)], chunks: &[TocChunk], flags: u32) -> Result<Vec<u8>> {
548    if flags & 4 != 0 {
549        return Err(bad(W, 0, "the Patch TOC writer stores plain names"));
550    }
551    let w32 = |n: usize| crate::u32_len(W, n);
552    let bkeys = bundles
553        .iter()
554        .map(|(n, _)| bundle_key(n))
555        .collect::<Result<Vec<_>>>()?;
556    let (bmap, border) = perfect_hash(&bkeys)?;
557    let ckeys: Vec<Vec<u8>> = chunks.iter().map(|c| c.guid.to_vec()).collect();
558    let (cmap, corder) = perfect_hash(&ckeys)?;
559    let bundle_at = |src: usize| {
560        bundles
561            .get(src)
562            .ok_or_else(|| bad(W, src, format!("bundle {src} of {}", bundles.len())))
563    };
564    let mut names = Vec::new();
565    let mut name_at = Vec::with_capacity(border.len());
566    for &src in &border {
567        name_at.push(names.len());
568        names.extend(latin1(&bundle_at(src)?.0, W)?);
569        names.push(0);
570    }
571    let mut words: Vec<u32> = Vec::new();
572    let mut table = Vec::with_capacity(crate::at(0, chunks.len(), 20));
573    for &src in &corder {
574        let c = chunks
575            .get(src)
576            .ok_or_else(|| bad(W, src, format!("chunk {src} of {}", chunks.len())))?;
577        table.extend(c.guid.iter().rev());
578        match c.file {
579            None => table.extend((-1i32).to_be_bytes()),
580            Some((loc, off, size)) => {
581                table.extend(((0x80u32 << 24) | w32(words.len())?).to_be_bytes());
582                let [a, b, c, d, e, f, g, h] = loc.encode().to_be_bytes();
583                words.extend([
584                    u32::from_be_bytes([a, b, c, d]),
585                    u32::from_be_bytes([e, f, g, h]),
586                    off,
587                    size,
588                ]);
589            }
590        }
591    }
592    let bho = 48usize;
593    let bdo = align(crate::at(bho, bundles.len(), 4), 8);
594    let cho = align(crate::at(bdo, bundles.len(), 16), 4);
595    let cgo = align(crate::at(cho, chunks.len(), 4), 4);
596    let cdo = align(cgo.saturating_add(table.len()), 4);
597    let nameso = crate::at(cdo, words.len(), 4);
598    let mut pos = align(nameso.saturating_add(names.len()), 4);
599    let mut region_at = Vec::with_capacity(border.len());
600    for &src in &border {
601        region_at.push(pos);
602        pos = align(pos.saturating_add(bundle_at(src)?.1.len()), 4);
603    }
604    let mut out = vec![0u8; ENVELOPE.saturating_add(pos)];
605    let (envelope, d) = out
606        .split_at_mut_checked(ENVELOPE)
607        .ok_or_else(|| bad(W, 0, "TOC larger than the address space"))?;
608    if let Some(magic) = envelope.get_mut(..4) {
609        magic.copy_from_slice(&MAGIC);
610    }
611    // every write lies inside `d`, which is sized from the same offsets
612    let put = |d: &mut [u8], at: usize, v: &[u8]| -> Result<()> {
613        d.get_mut(at..at.saturating_add(v.len()))
614            .ok_or_else(|| bad(W, at, "internal layout error: write past the TOC"))?
615            .copy_from_slice(v);
616        Ok(())
617    };
618    let has_chunks = !chunks.is_empty();
619    let head = [
620        w32(bho)?,
621        w32(bdo)?,
622        w32(bundles.len())?,
623        if has_chunks { w32(cho)? } else { 0 },
624        if has_chunks { w32(cgo)? } else { 0 },
625        w32(chunks.len())?,
626        w32(cdo)?,
627        w32(cdo)?,
628        w32(nameso)?,
629        w32(cdo)?,
630        w32(words.len())?,
631        flags,
632    ];
633    for (i, v) in head.iter().enumerate() {
634        put(d, crate::at(0, i, 4), &v.to_be_bytes())?;
635    }
636    for (i, v) in bmap.iter().enumerate() {
637        put(d, crate::at(bho, i, 4), &v.to_be_bytes())?;
638    }
639    for (i, &src) in border.iter().enumerate() {
640        let region = &bundle_at(src)?.1;
641        if region.len() > 0x3FFF_FFFF {
642            return Err(bad(W, i, "bundle region exceeds 30 bits"));
643        }
644        let (name, at) = (
645            name_at.get(i).copied().unwrap_or(0),
646            region_at.get(i).copied().unwrap_or(0),
647        );
648        let entry = crate::at(bdo, i, 16);
649        put(d, entry, &w32(name)?.to_be_bytes())?;
650        put(
651            d,
652            entry.saturating_add(4),
653            &((1u32 << 30) | w32(region.len())?).to_be_bytes(),
654        )?;
655        put(d, entry.saturating_add(8), &(at as u64).to_be_bytes())?;
656        put(d, at, region)?;
657    }
658    if has_chunks {
659        for (i, v) in cmap.iter().enumerate() {
660            put(d, crate::at(cho, i, 4), &v.to_be_bytes())?;
661        }
662        put(d, cgo, &table)?;
663        for (i, w) in words.iter().enumerate() {
664            put(d, crate::at(cdo, i, 4), &w.to_be_bytes())?;
665        }
666    }
667    put(d, nameso, &names)?;
668    Ok(out)
669}
670
671#[cfg(test)]
672mod tests {
673    /// Reference values of the TOC hash (independent Python TOC hashing).
674    #[test]
675    fn toc_hash_reference_values() {
676        assert_eq!(super::hash_with(&[0, 127, 128, 255], 0x811c9dc5), 0x529916);
677        assert_eq!(super::hash_with(b"levels/test", 0x811c9dc5), 0xb97702);
678    }
679}
680
681#[cfg(test)]
682mod huffman_tests {
683    use super::*;
684
685    /// The table `entries` (big-endian words) and the code `bits` (bit 0 first, in one word) as a Huffman reader's input.
686    fn huffman(entries: &[u32], bits: u32) -> Result<Huffman> {
687        let mut data = bits.to_be_bytes().to_vec();
688        for e in entries {
689            data.extend(e.to_be_bytes());
690        }
691        let r = Rd::new(&data, W);
692        Huffman::read(&r, 0, 1, 4, entries.len())
693    }
694
695    /// One internal node: bit 0 is the character 'a', bit 1 the terminator; "a" is the bits 0 then 1.
696    #[test]
697    fn a_name_decodes_through_its_table() {
698        let h = huffman(&[!u32::from(b'a'), !0], 0b10).unwrap();
699        assert_eq!(h.decode(0).unwrap(), "a");
700    }
701
702    /// Two levels: the first pair is internal node 0, the second pair (node 0, 'b') is node 1, the root.
703    #[test]
704    fn an_internal_node_is_named_by_its_counter() {
705        let table = [!u32::from(b'a'), !0, 0, !u32::from(b'b')];
706        // root: bit 0 -> node 0 ('a' on 0, end on 1), bit 1 -> 'b'. "b" then the end: 1, then 0, 1.
707        let h = huffman(&table, 0b101).unwrap();
708        assert_eq!(h.decode(0).unwrap(), "b");
709    }
710
711    /// A small value is no character: it used to become a leaf of that number, shadowing the internal node the same number
712    /// would name once built (one map held both). It is refused where it stands, and so is a counter not built yet.
713    #[test]
714    fn a_value_that_is_neither_a_character_nor_a_built_node_is_refused() {
715        let e = huffman(&[0, !0], 0).err().unwrap().to_string();
716        assert!(e.contains("neither a character nor an internal node"), "{e}");
717        let e = huffman(&[!u32::from(b'a'), !0, 1, !0], 0)
718            .err()
719            .unwrap()
720            .to_string();
721        assert!(e.contains("0x1"), "{e}");
722    }
723}