use crate::{Error, Rd, Result, align, bad, latin1};
pub const ENVELOPE: usize = 0x22C;
pub const MAGIC: [u8; 4] = [0x00, 0xd1, 0xce, 0x01];
const FNV_SEED: u32 = 0x811C_9DC5;
const W: &str = "toc";
const LEAF: u32 = 0x8000_0000;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Loc {
pub patch: bool,
pub chunk: u32,
pub archive: u16,
}
impl Loc {
pub fn decode(v: u64) -> Option<Self> {
let [a0, a1, c0, c1, c2, c3, patch, top] = v.to_le_bytes();
(patch <= 1 && top == 0).then(|| Self {
patch: patch == 1,
chunk: u32::from_le_bytes([c0, c1, c2, c3]),
archive: u16::from_le_bytes([a0, a1]),
})
}
pub fn encode(self) -> u64 {
(u64::from(self.patch) << 48) | (u64::from(self.chunk) << 16) | u64::from(self.archive)
}
}
pub(crate) fn unrepresentable(id: u64) -> String {
format!(
"archive identifier {id:#018x}: expected bits 48..56 (the patch flag) to be 0 or 1 and bits 56..64 to be 0"
)
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TocChunk {
pub guid: [u8; 16],
pub file: Option<(Loc, u32, u32)>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Toc {
pub flags: u32,
pub bundles: Vec<(String, Vec<u8>)>,
pub chunks: Vec<TocChunk>,
pub bundle_hash: Vec<i32>,
pub chunk_hash: Vec<i32>,
}
struct Huffman {
words: Vec<u32>,
nodes: Vec<(u32, Option<(usize, usize)>)>,
root: Option<usize>,
}
impl Huffman {
fn read(r: &Rd, names_at: usize, names_n: usize, table_at: usize, table_n: usize) -> Result<Self> {
let words = (0..names_n)
.map(|i| r.u32be(crate::at(names_at, i, 4)))
.collect::<Result<Vec<_>>>()?;
let mut nodes: Vec<(u32, Option<(usize, usize)>)> = Vec::new();
let mut leaves = std::collections::BTreeMap::new();
let mut internal = std::collections::BTreeMap::new();
let (mut left, mut counter, mut root) = (None, 0u32, None);
for i in 0..table_n {
let at = crate::at(table_at, i, 4);
let v = r.u32be(at)?;
let node = if v & LEAF != 0 {
*leaves.entry(v).or_insert_with(|| {
nodes.push((v, None));
nodes.len().saturating_sub(1)
})
} else {
*internal.get(&v).ok_or_else(|| {
bad(
W,
at,
format!(
"Huffman entry {v:#x} is neither a character nor an internal node built before it"
),
)
})?
};
let Some(l) = left.take() else {
left = Some(node);
continue;
};
nodes.push((counter, Some((l, node))));
let parent = nodes.len().saturating_sub(1);
internal.insert(counter, parent);
root = Some(parent);
counter = counter.saturating_add(1);
}
Ok(Self { words, nodes, root })
}
fn decode(&self, mut bit: usize) -> Result<String> {
let nbits = self.words.len().saturating_mul(32);
let mut out = String::new();
let root = self
.root
.ok_or_else(|| bad(W, bit / 8, "a name in a TOC with an empty Huffman table"))?;
let node = |n: usize, bit: usize| {
self.nodes
.get(n)
.ok_or_else(|| bad(W, bit / 8, format!("Huffman node {n} of {}", self.nodes.len())))
};
while bit < nbits {
let mut n = root;
while let (_, Some((l, r))) = *node(n, bit)? {
let word = self
.words
.get(bit >> 5)
.ok_or_else(|| bad(W, bit / 8, "Huffman name runs past the data"))?;
let one = (word >> (bit & 31)) & 1 != 0;
n = if one { r } else { l };
bit = bit.saturating_add(1);
if bit > nbits {
return Err(bad(W, bit / 8, "Huffman name runs past the data"));
}
}
let ch = !node(n, bit)?.0 & 0xFFFF;
if ch == 0 {
return Ok(out);
}
out.push(char::from_u32(ch).ok_or_else(|| bad(W, bit / 8, "Huffman character is not a char"))?);
}
Err(bad(W, bit / 8, "Huffman name is unterminated"))
}
}
pub fn read(data: &[u8]) -> Result<Toc> {
match data.split_at_checked(ENVELOPE) {
Some((envelope, body)) if body.len() >= 48 && envelope.starts_with(&MAGIC) => read_body(body)
.map_err(|e| match e {
Error::Format { what, offset, detail } => Error::Format {
what,
offset: offset.saturating_add(ENVELOPE),
detail,
},
other => other,
}),
_ => Err(bad(
W,
0,
format!(
"envelope is invalid: expected the magic {MAGIC:02x?} and {} bytes at least, got {} bytes",
ENVELOPE + 48,
data.len()
),
)),
}
}
fn read_body(data: &[u8]) -> Result<Toc> {
let r = Rd::new(data, W);
let u = |i: usize| r.u32be(crate::at(0, i, 4));
let (bho, bdo, cho, cgo, nameso, cdo, flags) = (
u(0)? as usize,
u(1)? as usize,
u(3)? as usize,
u(4)? as usize,
u(8)? as usize,
u(9)? as usize,
u(11)?,
);
let count = |i: usize| -> Result<usize> {
let at = crate::at(0, i, 4);
usize::try_from(r.i32be(at)?).map_err(|_| bad(W, at, "count is negative, expected 0 or more"))
};
let (bcount, ccount, dcount) = (count(2)?, count(5)?, count(10)?);
let huffman = if flags & 4 != 0 {
let (n, t, at) = (
r.u32be(48)? as usize,
r.u32be(52)? as usize,
r.u32be(56)? as usize,
);
Some(Huffman::read(&r, nameso, n, at, t)?)
} else {
None
};
let mut toc = Toc {
flags,
bundles: Vec::new(),
chunks: Vec::new(),
bundle_hash: Vec::new(),
chunk_hash: Vec::new(),
};
toc.bundle_hash = (0..bcount)
.map(|i| r.i32be(crate::at(bho, i, 4)))
.collect::<Result<_>>()?;
for i in 0..bcount {
let at = crate::at(bdo, i, 16);
let (no, sf, ro) = (
r.u32be(at)? as usize,
r.u32be(at.saturating_add(4))?,
r.u64be(at.saturating_add(8))?,
);
if sf >> 30 != 1 {
return Err(bad(
W,
at.saturating_add(4),
format!("bundle region flags {sf:#x}: expected the inline form (bits 31..30 equal to 0b01)"),
));
}
let name = match &huffman {
Some(h) => h.decode(no)?,
None => r.cstr(nameso.saturating_add(no))?,
};
let ro = usize::try_from(ro).map_err(|_| {
bad(
W,
at.saturating_add(8),
format!("region offset {ro:#x} does not fit the address space"),
)
})?;
toc.bundles
.push((name, r.bytes(ro, (sf & 0x3FFF_FFFF) as usize)?.to_vec()));
}
if ccount != 0 {
toc.chunk_hash = (0..ccount)
.map(|i| r.i32be(crate::at(cho, i, 4)))
.collect::<Result<_>>()?;
let words = (0..dcount)
.map(|i| r.u32be(crate::at(cdo, i, 4)))
.collect::<Result<Vec<_>>>()?;
for i in 0..ccount {
let at = crate::at(cgo, i, 20);
let mut guid: [u8; 16] = r.arr(at)?;
guid.reverse();
let ref_at = at.saturating_add(16);
let enc = r.i32be(ref_at)?.cast_unsigned();
if enc == u32::MAX {
toc.chunks.push(TocChunk { guid, file: None });
continue;
}
let (flag, w) = (enc >> 24, (enc & 0xFF_FFFF) as usize);
let record = (flag == 0x80)
.then(|| words.get(w..).and_then(|rest| rest.first_chunk::<4>()))
.flatten();
let Some(&[loc_high, loc_low, offset, size]) = record else {
return Err(bad(
W,
ref_at,
format!(
"chunk data reference {enc:#010x}: expected -1 or 0x80 and the index of a 4-word record among the {} data words",
words.len()
),
));
};
let id = (u64::from(loc_high) << 32) | u64::from(loc_low);
let loc = Loc::decode(id).ok_or_else(|| bad(W, crate::at(cdo, w, 4), unrepresentable(id)))?;
toc.chunks.push(TocChunk {
guid,
file: Some((loc, offset, size)),
});
}
}
Ok(toc)
}
fn hash_with(key: &[u8], seed: u32) -> u32 {
key.iter().fold(seed, |h, &b| {
h.wrapping_mul(0x01000193) ^ (b as i8 as i32).cast_unsigned()
}) % 0x01000193
}
fn slot(key: &[u8], seed: u32, size: usize) -> usize {
usize::try_from(hash_with(key, seed))
.ok()
.and_then(|h| h.checked_rem(size))
.unwrap_or(0)
}
pub fn perfect_hash(keys: &[Vec<u8>]) -> Result<(Vec<i32>, Vec<usize>)> {
let size = keys.len();
let mut map = vec![-1i32; size];
let mut order = vec![usize::MAX; size];
if size == 0 {
return Ok((map, order));
}
let mut seen = keys.to_vec();
seen.sort();
seen.dedup();
if seen.len() != size {
return Err(bad(W, 0, "perfect-hash keys are not unique"));
}
let too_large = || {
bad(
W,
0,
format!("{size} keys do not fit the 32-bit entries of a perfect hash"),
)
};
let first: Vec<usize> = keys.iter().map(|k| slot(k, FNV_SEED, size)).collect();
let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); size];
for (i, &s) in first.iter().enumerate() {
if let Some(bucket) = buckets.get_mut(s) {
bucket.push(i);
}
}
buckets.sort_by_key(|b| std::cmp::Reverse(b.len()));
let mut used = vec![false; size];
let multi = buckets.iter().take_while(|b| b.len() > 1).count();
for bucket in buckets.iter().take(multi) {
let mut seed = 1u32;
let slots = loop {
let mut slots = Vec::with_capacity(bucket.len());
let ok = bucket.iter().all(|&m| {
let s = keys.get(m).map_or(0, |k| slot(k, seed, size));
let free = used.get(s) == Some(&false) && !slots.contains(&s);
slots.push(s);
free
});
if ok {
break slots;
}
seed = seed
.checked_add(1)
.ok_or_else(|| bad(W, 0, "no seed separates a bucket of keys"))?;
};
let head = bucket.first().and_then(|&m| first.get(m)).copied();
if let Some(entry) = head.and_then(|h| map.get_mut(h)) {
*entry = i32::try_from(seed).map_err(|_| too_large())?;
}
for (&s, &m) in slots.iter().zip(bucket) {
if let Some(o) = order.get_mut(s) {
*o = m;
}
if let Some(u) = used.get_mut(s) {
*u = true;
}
}
}
let mut free = 0usize;
for bucket in buckets.iter().skip(multi).take_while(|b| !b.is_empty()) {
while used.get(free) == Some(&true) {
free = free.saturating_add(1).checked_rem(size).unwrap_or(0);
}
let Some(&m) = bucket.first() else { break };
let entry = first.get(m).and_then(|&h| map.get_mut(h));
if let Some(entry) = entry {
*entry = !i32::try_from(free).map_err(|_| too_large())?;
}
if let Some(o) = order.get_mut(free) {
*o = m;
}
if let Some(u) = used.get_mut(free) {
*u = true;
}
free = free.saturating_add(1).checked_rem(size).unwrap_or(0);
}
Ok((map, order))
}
pub fn lookup(map: &[i32], ordered: &[Vec<u8>], key: &[u8]) -> Option<usize> {
if map.is_empty() || map.len() != ordered.len() {
return None;
}
let v = *map.get(slot(key, FNV_SEED, map.len()))?;
let i = if v < 0 {
usize::try_from(!v).ok()?
} else {
slot(key, v.cast_unsigned(), map.len())
};
(ordered.get(i)? == key).then_some(i)
}
fn bundle_key(name: &str) -> Result<Vec<u8>> {
latin1(&name.to_lowercase(), W)
}
pub fn verify(toc: &Toc) -> Result<()> {
let keys = toc
.bundles
.iter()
.map(|(n, _)| bundle_key(n))
.collect::<Result<Vec<_>>>()?;
for (i, k) in keys.iter().enumerate() {
if lookup(&toc.bundle_hash, &keys, k) != Some(i) {
return Err(bad(
W,
i,
"bundle perfect hash does not resolve: expected the name to find its own index",
));
}
}
let keys: Vec<Vec<u8>> = toc.chunks.iter().map(|c| c.guid.to_vec()).collect();
for (i, k) in keys.iter().enumerate() {
if lookup(&toc.chunk_hash, &keys, k) != Some(i) {
return Err(bad(
W,
i,
"chunk perfect hash does not resolve: expected the GUID to find its own index",
));
}
}
Ok(())
}
pub fn write(bundles: &[(String, Vec<u8>)], chunks: &[TocChunk], flags: u32) -> Result<Vec<u8>> {
if flags & 4 != 0 {
return Err(bad(W, 0, "the Patch TOC writer stores plain names"));
}
let w32 = |n: usize| crate::u32_len(W, n);
let bkeys = bundles
.iter()
.map(|(n, _)| bundle_key(n))
.collect::<Result<Vec<_>>>()?;
let (bmap, border) = perfect_hash(&bkeys)?;
let ckeys: Vec<Vec<u8>> = chunks.iter().map(|c| c.guid.to_vec()).collect();
let (cmap, corder) = perfect_hash(&ckeys)?;
let bundle_at = |src: usize| {
bundles
.get(src)
.ok_or_else(|| bad(W, src, format!("bundle {src} of {}", bundles.len())))
};
let mut names = Vec::new();
let mut name_at = Vec::with_capacity(border.len());
for &src in &border {
name_at.push(names.len());
names.extend(latin1(&bundle_at(src)?.0, W)?);
names.push(0);
}
let mut words: Vec<u32> = Vec::new();
let mut table = Vec::with_capacity(crate::at(0, chunks.len(), 20));
for &src in &corder {
let c = chunks
.get(src)
.ok_or_else(|| bad(W, src, format!("chunk {src} of {}", chunks.len())))?;
table.extend(c.guid.iter().rev());
match c.file {
None => table.extend((-1i32).to_be_bytes()),
Some((loc, off, size)) => {
table.extend(((0x80u32 << 24) | w32(words.len())?).to_be_bytes());
let [a, b, c, d, e, f, g, h] = loc.encode().to_be_bytes();
words.extend([
u32::from_be_bytes([a, b, c, d]),
u32::from_be_bytes([e, f, g, h]),
off,
size,
]);
}
}
}
let bho = 48usize;
let bdo = align(crate::at(bho, bundles.len(), 4), 8);
let cho = align(crate::at(bdo, bundles.len(), 16), 4);
let cgo = align(crate::at(cho, chunks.len(), 4), 4);
let cdo = align(cgo.saturating_add(table.len()), 4);
let nameso = crate::at(cdo, words.len(), 4);
let mut pos = align(nameso.saturating_add(names.len()), 4);
let mut region_at = Vec::with_capacity(border.len());
for &src in &border {
region_at.push(pos);
pos = align(pos.saturating_add(bundle_at(src)?.1.len()), 4);
}
let mut out = vec![0u8; ENVELOPE.saturating_add(pos)];
let (envelope, d) = out
.split_at_mut_checked(ENVELOPE)
.ok_or_else(|| bad(W, 0, "TOC larger than the address space"))?;
if let Some(magic) = envelope.get_mut(..4) {
magic.copy_from_slice(&MAGIC);
}
let put = |d: &mut [u8], at: usize, v: &[u8]| -> Result<()> {
d.get_mut(at..at.saturating_add(v.len()))
.ok_or_else(|| bad(W, at, "internal layout error: write past the TOC"))?
.copy_from_slice(v);
Ok(())
};
let has_chunks = !chunks.is_empty();
let head = [
w32(bho)?,
w32(bdo)?,
w32(bundles.len())?,
if has_chunks { w32(cho)? } else { 0 },
if has_chunks { w32(cgo)? } else { 0 },
w32(chunks.len())?,
w32(cdo)?,
w32(cdo)?,
w32(nameso)?,
w32(cdo)?,
w32(words.len())?,
flags,
];
for (i, v) in head.iter().enumerate() {
put(d, crate::at(0, i, 4), &v.to_be_bytes())?;
}
for (i, v) in bmap.iter().enumerate() {
put(d, crate::at(bho, i, 4), &v.to_be_bytes())?;
}
for (i, &src) in border.iter().enumerate() {
let region = &bundle_at(src)?.1;
if region.len() > 0x3FFF_FFFF {
return Err(bad(W, i, "bundle region exceeds 30 bits"));
}
let (name, at) = (
name_at.get(i).copied().unwrap_or(0),
region_at.get(i).copied().unwrap_or(0),
);
let entry = crate::at(bdo, i, 16);
put(d, entry, &w32(name)?.to_be_bytes())?;
put(
d,
entry.saturating_add(4),
&((1u32 << 30) | w32(region.len())?).to_be_bytes(),
)?;
put(d, entry.saturating_add(8), &(at as u64).to_be_bytes())?;
put(d, at, region)?;
}
if has_chunks {
for (i, v) in cmap.iter().enumerate() {
put(d, crate::at(cho, i, 4), &v.to_be_bytes())?;
}
put(d, cgo, &table)?;
for (i, w) in words.iter().enumerate() {
put(d, crate::at(cdo, i, 4), &w.to_be_bytes())?;
}
}
put(d, nameso, &names)?;
Ok(out)
}
#[cfg(test)]
mod tests {
#[test]
fn toc_hash_reference_values() {
assert_eq!(super::hash_with(&[0, 127, 128, 255], 0x811c9dc5), 0x529916);
assert_eq!(super::hash_with(b"levels/test", 0x811c9dc5), 0xb97702);
}
}
#[cfg(test)]
mod huffman_tests {
use super::*;
fn huffman(entries: &[u32], bits: u32) -> Result<Huffman> {
let mut data = bits.to_be_bytes().to_vec();
for e in entries {
data.extend(e.to_be_bytes());
}
let r = Rd::new(&data, W);
Huffman::read(&r, 0, 1, 4, entries.len())
}
#[test]
fn a_name_decodes_through_its_table() {
let h = huffman(&[!u32::from(b'a'), !0], 0b10).unwrap();
assert_eq!(h.decode(0).unwrap(), "a");
}
#[test]
fn an_internal_node_is_named_by_its_counter() {
let table = [!u32::from(b'a'), !0, 0, !u32::from(b'b')];
let h = huffman(&table, 0b101).unwrap();
assert_eq!(h.decode(0).unwrap(), "b");
}
#[test]
fn a_value_that_is_neither_a_character_nor_a_built_node_is_refused() {
let e = huffman(&[0, !0], 0).err().unwrap().to_string();
assert!(e.contains("neither a character nor an internal node"), "{e}");
let e = huffman(&[!u32::from(b'a'), !0, 1, !0], 0)
.err()
.unwrap()
.to_string();
assert!(e.contains("0x1"), "{e}");
}
}