packages /

compress 0.1.0

DEFLATE (RFC 1951), its two common wrappers gzip (RFC 1952) and zlib (RFC 1950), and zip archives, in pure Auk.

files / src/lib.auk 32.7 kB · 945 lines

/// DEFLATE (RFC 1951) and its gzip (RFC 1952) and zlib (RFC 1950) wrappers, plus the CRC-32
/// and Adler-32 checksums they use. Pure: no effects. Bytes are `[int]` (0–255), as in core
/// `fs.read_bytes` and `net`.
///
/// The decoder handles every block type (stored, fixed and dynamic Huffman). The encoder
/// writes stored and fixed-Huffman blocks with LZ77 matching: its output is valid for any
/// decoder, but it compresses less than zlib (no dynamic Huffman blocks or lazy matching).

/// Why decompression failed. Every `at` is a 0-based byte offset into the input.
pub enum ZErr {
  Truncated,                     // the input ended inside the stream
  BadHeader(at: int, why: str),  // a gzip or zlib header or trailer is wrong
  BadData(at: int, why: str),    // invalid DEFLATE data near byte `at`
  BadChecksum(what: str),        // "CRC-32", "Adler-32" or "length" didn't match
}

/// A one-line description of an error, e.g. `bad deflate data at 12: distance too far back`.
pub fn message(e: ZErr): str
fn message(Truncated): str = "compressed data is truncated"
fn message(BadHeader(at, why)): str = "bad header at {at}: {why}"
fn message(BadData(at, why)): str = "bad deflate data at {at}: {why}"
fn message(BadChecksum(what)): str = "{what} check failed: the data is corrupt"

// ---- checksums ----

let MASK = 0xffffffff

fn crc_table(): [int] {
  var t: [int] = []
  for n in 0..256 {
    var c = n
    for _ in 0..8 {
      c = if (c & 1) == 1 { 0xedb88320 ^ (c >> 1) } else { c >> 1 }
    }
    t.push(c)
  }
  t
}

imprint CRC_TABLE = crc_table()

/// The CRC-32 (IEEE, as in gzip and zip) of `data`: `crc32("123456789".bytes()) == 0xcbf43926`.
pub fn crc32(data: [int]): int = crc32_update(0, data)

/// Continues a CRC-32: `crc32_update(crc32(a), b) == crc32(a + b)`.
pub fn crc32_update(crc: int, data: [int]): int {
  var c = crc ^ MASK
  for b in data { c = CRC_TABLE[(c ^ b) & 0xff] ^ (c >> 8) }
  c ^ MASK
}

/// The Adler-32 (as in zlib) of `data`: `adler32("Wikipedia".bytes()) == 0x11e60398`.
pub fn adler32(data: [int]): int {
  var a = 1
  var b = 0
  var n = 0
  for x in data {
    a += x
    b += a
    n += 1
    // a and b stay far below 2^63 for 4096 bytes, so reduce only now and then
    if n == 4096 {
      a %= 65521
      b %= 65521
      n = 0
    }
  }
  (b % 65521) << 16 | (a % 65521)
}

// ---- DEFLATE decoding (RFC 1951), after Mark Adler's puff.c ----

// Extra bits and base values for length symbols 257..285 and distance symbols 0..29 (RFC 1951
// §3.2.5): each group of four (two for distances) adds one extra bit.
fn lext(): [int] = (0..29).map(i => if i < 8 || i == 28 { 0 } else { (i - 4) / 4 })
fn dext(): [int] = (0..30).map(i => if i < 4 { 0 } else { (i - 2) / 2 })

fn bases(start: int, ext: [int]): [int] {
  var out: [int] = []
  var base = start
  for e in ext {
    out.push(base)
    base += 1 << e
  }
  out
}

imprint LEXT = lext()
imprint DEXT = dext()
// Length symbol 284 would reach 258 with its extra bits, but 285 means exactly 258.
imprint LBASE = bases(3, lext()).take(28) + [258]
imprint DBASE = bases(1, dext())
// The order code-length code lengths are sent in.
let ORDER = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]

// The input as a bit stream, read LSB first.
struct In { src: [int], pos: int, buf: int, cnt: int }

fn bits(s: var In, need: int): int!ZErr {
  var val = s.buf
  while s.cnt < need {
    if s.pos >= s.src.len() { fail(Truncated) }
    val = val | (s.src[s.pos] << s.cnt)
    s.pos += 1
    s.cnt += 8
  }
  s.buf = val >> need
  s.cnt -= need
  val & (1 << need) - 1
}

// A canonical Huffman code: how many codes have each length 0..15, and the symbols in code
// order.
struct Huff { count: [int], symbol: [int] }

fn filled(n: int, v: int): [int] {
  var xs: [int] = []
  for _ in 0..n { xs.push(v) }
  xs
}

// Builds the code for `lengths` (one per symbol, 0 = unused). The int is 0 for a complete code,
// negative for an over-subscribed one and positive for an incomplete one.
fn huff(lengths: [int]): (Huff, int) {
  var count = filled(16, 0)
  for l in lengths { count[l] += 1 }
  var symbol = filled(lengths.len(), 0)
  if count[0] == lengths.len() { return (Huff { count, symbol }, 0) }
  var left = 1
  for len in 1..16 {
    left = (left << 1) - count[len]
    if left < 0 { return (Huff { count, symbol }, left) }
  }
  var offs = filled(16, 0)
  for len in 1..15 { offs[len + 1] = offs[len] + count[len] }
  for sym in 0..lengths.len() {
    let l = lengths[sym]
    if l != 0 {
      symbol[offs[l]] = sym
      offs[l] += 1
    }
  }
  (Huff { count, symbol }, left)
}

// Reads one symbol, a bit at a time (codes are stored MSB first).
fn decode(s: var In, h: Huff): int!ZErr {
  var code = 0
  var first = 0
  var index = 0
  for len in 1..16 {
    code = code | s.bits(1)?
    let count = h.count[len]
    if code - count < first { return h.symbol[index + (code - first)] }
    index += count
    first = (first + count) << 1
    code = code << 1
  }
  fail(BadData(s.pos, "invalid Huffman code"))
}

fn stored(s: var In, out: var [int]): ()!ZErr {
  // drop the bits left in the current byte
  s.buf = 0
  s.cnt = 0
  let p = s.pos
  if p + 4 > s.src.len() { fail(Truncated) }
  let len = s.src[p] | (s.src[p + 1] << 8)
  let nlen = s.src[p + 2] | (s.src[p + 3] << 8)
  if len != (~nlen & 0xffff) { fail(BadData(p, "stored block length check failed")) }
  if p + 4 + len > s.src.len() { fail(Truncated) }
  for i in p + 4..p + 4 + len { out.push(s.src[i]) }
  s.pos = p + 4 + len
}

fn codes(s: var In, out: var [int], lens: Huff, dists: Huff): ()!ZErr {
  loop {
    let sym = s.decode(lens)?
    if sym < 256 {
      out.push(sym)
    } else if sym == 256 {
      break
    } else {
      let i = sym - 257
      if i >= 29 { fail(BadData(s.pos, "invalid length symbol {sym}")) }
      let len = LBASE[i] + s.bits(LEXT[i])?
      let d = s.decode(dists)?
      if d >= 30 { fail(BadData(s.pos, "invalid distance symbol {d}")) }
      let dist = DBASE[d] + s.bits(DEXT[d])?
      if dist > out.len() { fail(BadData(s.pos, "distance too far back")) }
      let start = out.len() - dist
      for k in 0..len { out.push(out[start + k]) }
    }
  }
}

fn fixed_lengths(): [int] {
  var ls: [int] = []
  for sym in 0..288 {
    ls.push(if sym < 144 { 8 } else if sym < 256 { 9 } else if sym < 280 { 7 } else { 8 })
  }
  ls
}

let FIXED_LENS = huff(fixed_lengths()).0
let FIXED_DISTS = huff(filled(30, 5)).0

fn dynamic(s: var In, out: var [int]): ()!ZErr {
  let at = s.pos
  let nlen = s.bits(5)? + 257
  let ndist = s.bits(5)? + 1
  let ncode = s.bits(4)? + 4
  if nlen > 286 || ndist > 30 { fail(BadData(at, "too many length or distance symbols")) }
  var cl = filled(19, 0)
  for i in 0..ncode { cl[ORDER[i]] = s.bits(3)? }
  let (clcode, cl_left) = huff(cl)
  if cl_left != 0 { fail(BadData(at, "incomplete code length code")) }
  let total = nlen + ndist
  var lengths: [int] = []
  while lengths.len() < total {
    let sym = s.decode(clcode)?
    if sym < 16 {
      lengths.push(sym)
    } else {
      let (len, n) = if sym == 16 {
        let prev = lengths.last() else fail(BadData(s.pos, "repeat with no first length"))
        (prev, 3 + s.bits(2)?)
      } else if sym == 17 {
        (0, 3 + s.bits(3)?)
      } else {
        (0, 11 + s.bits(7)?)
      }
      if lengths.len() + n > total { fail(BadData(s.pos, "too many code lengths")) }
      for _ in 0..n { lengths.push(len) }
    }
  }
  if lengths[256] == 0 { fail(BadData(at, "no end-of-block code")) }
  let (lens, l_left) = huff(lengths.take(nlen))
  if l_left < 0 || (l_left > 0 && nlen - lens.count[0] != 1) {
    fail(BadData(at, "bad literal/length code lengths"))
  }
  let (dists, d_left) = huff(lengths.skip(nlen))
  if d_left < 0 || (d_left > 0 && ndist - dists.count[0] != 1) {
    fail(BadData(at, "bad distance code lengths"))
  }
  s.codes(&out, lens, dists)?
}

// Inflates the DEFLATE stream starting at byte `from`; also returns the offset just past it.
fn inflate_at(bs: [int], from: int): ([int], int)!ZErr {
  var s = In { src: bs, pos: from, buf: 0, cnt: 0 }
  var out: [int] = []
  loop {
    let last = s.bits(1)?
    let at = s.pos
    match s.bits(2)? {
      0 => s.stored(&out)?
      1 => s.codes(&out, FIXED_LENS, FIXED_DISTS)?
      2 => s.dynamic(&out)?
      _ => fail(BadData(at, "invalid block type 3"))
    }
    if last == 1 { break (out, s.pos) }
  }
}

/// Decompresses raw DEFLATE data (no header or checksum). Bytes after the final block are
/// ignored.
pub fn inflate(data: [int]): [int]!ZErr = (inflate_at(data, 0)?).0

// ---- DEFLATE encoding: LZ77 with hash chains, then stored or fixed-Huffman blocks ----

// The output as a bit stream, written LSB first.
struct Out { bytes: [int], acc: int, n: int }

fn put(o: var Out, v: int, nbits: int) {
  o.acc = o.acc | (v << o.n)
  o.n += nbits
  while o.n >= 8 {
    o.bytes.push(o.acc & 0xff)
    o.acc = o.acc >> 8
    o.n -= 8
  }
}

// Pads to a byte boundary with zero bits.
fn align(o: var Out) {
  if o.n > 0 {
    o.bytes.push(o.acc & 0xff)
    o.acc = 0
    o.n = 0
  }
}

// Huffman codes go out MSB first, so reverse the low `len` bits.
fn rev(code: int, len: int): int {
  var r = 0
  var c = code
  for _ in 0..len {
    r = (r << 1) | (c & 1)
    c = c >> 1
  }
  r
}

// The fixed literal/length code for `sym`: (code, length).
fn fixed_code(sym: int): (int, int) when sym < 144 = (0x30 + sym, 8)
fn fixed_code(sym: int): (int, int) when sym < 256 = (0x190 + sym - 144, 9)
fn fixed_code(sym: int): (int, int) when sym < 280 = (sym - 256, 7)
fn fixed_code(sym: int): (int, int) = (0xc0 + sym - 280, 8)

fn put_sym(o: var Out, sym: int) {
  let (code, len) = fixed_code(sym)
  o.put(rev(code, len), len)
}

// The index into LBASE for a match length 3..258.
fn len_index(len: int): int {
  var i = 28
  while LBASE[i] > len { i -= 1 }
  i
}

// The distance symbol for a distance 1..32768.
fn dist_index(dist: int): int {
  var i = 29
  while DBASE[i] > dist { i -= 1 }
  i
}

let WINDOW = 32768
let HASH_SIZE = 32768
let MAX_CHAIN = 64
let MAX_MATCH = 258
let BLOCK = 65535

// A token is a literal byte (0..255) or a match `(len << 16) | dist`.
fn is_match(t: int): bool = t > 255

struct Lz { head: [int], prev: [int] }

fn hash3(bs: [int], i: int): int = ((bs[i] << 10) ^ (bs[i + 1] << 5) ^ bs[i + 2]) & (HASH_SIZE - 1)

fn insert(z: var Lz, bs: [int], i: int) {
  if i + 2 < bs.len() {
    let h = hash3(bs, i)
    z.prev[i & (WINDOW - 1)] = z.head[h]
    z.head[h] = i
  }
}

// The longest earlier match for position i (not reaching past `end`): (length, distance).
fn longest(z: Lz, bs: [int], i: int, end: int): (int, int) {
  if i + 2 >= end { return (0, 0) }
  let max = if end - i < MAX_MATCH { end - i } else { MAX_MATCH }
  var best = 0
  var dist = 0
  var cand = z.head[hash3(bs, i)]
  var chain = 0
  while cand >= 0 && i - cand <= WINDOW && chain < MAX_CHAIN {
    if bs[cand + best] == bs[i + best] {
      var l = 0
      while l < max && bs[cand + l] == bs[i + l] { l += 1 }
      if l > best {
        best = l
        dist = i - cand
        if l == max { break }
      }
    }
    let next = z.prev[cand & (WINDOW - 1)]
    if next >= cand { break }  // a slot reused by a newer position: the chain ends here
    cand = next
    chain += 1
  }
  (best, dist)
}

// LZ77 tokens for bs[start..end]; matches may reach back before `start`.
fn tokens(z: var Lz, bs: [int], start: int, end: int): [int] {
  var out: [int] = []
  var i = start
  while i < end {
    let (len, dist) = longest(z, bs, i, end)
    if len >= 3 {
      out.push((len << 16) | dist)
      for k in i..i + len { z.insert(bs, k) }
      i += len
    } else {
      out.push(bs[i])
      z.insert(bs, i)
      i += 1
    }
  }
  out
}

// The size in bits of `toks` as a fixed-Huffman block (with header and end-of-block code).
fn fixed_cost(toks: [int]): int {
  var bits = 3 + 7
  for t in toks {
    if is_match(t) {
      let li = len_index(t >> 16)
      let di = dist_index(t & 0xffff)
      bits += fixed_code(257 + li).1 + LEXT[li] + 5 + DEXT[di]
    } else {
      bits += fixed_code(t).1
    }
  }
  bits
}

fn fixed_block(o: var Out, toks: [int], last: bool) {
  o.put(if last { 1 } else { 0 }, 1)
  o.put(1, 2)
  for t in toks {
    if is_match(t) {
      let len = t >> 16
      let dist = t & 0xffff
      let li = len_index(len)
      o.put_sym(257 + li)
      o.put(len - LBASE[li], LEXT[li])
      let di = dist_index(dist)
      o.put(rev(di, 5), 5)
      o.put(dist - DBASE[di], DEXT[di])
    } else {
      o.put_sym(t)
    }
  }
  o.put_sym(256)
}

fn stored_block(o: var Out, bs: [int], start: int, end: int, last: bool) {
  o.put(if last { 1 } else { 0 }, 1)
  o.put(0, 2)
  o.align()
  let n = end - start
  o.put(n, 16)
  o.put(~n & 0xffff, 16)
  for i in start..end { o.bytes.push(bs[i]) }
}

/// Compresses `data` as raw DEFLATE: LZ77 matching (hash chains over a 32 KiB window) coded
/// with the fixed Huffman code, with a stored block for any 64 KiB chunk that wouldn't shrink.
pub fn deflate(data: [int]): [int] {
  var o = Out { bytes: [], acc: 0, n: 0 }
  if data.len() == 0 {
    o.fixed_block([], true)
    o.align()
    return o.bytes
  }
  var z = Lz { head: filled(HASH_SIZE, -1), prev: filled(WINDOW, -1) }
  var start = 0
  while start < data.len() {
    let end = if data.len() - start > BLOCK { start + BLOCK } else { data.len() }
    let last = end == data.len()
    let toks = z.tokens(data, start, end)
    if fixed_cost(toks) > (end - start) * 8 + 40 {
      o.stored_block(data, start, end, last)
    } else {
      o.fixed_block(toks, last)
    }
    start = end
  }
  o.align()
  o.bytes
}

/// Wraps `data` in stored (uncompressed) DEFLATE blocks: no compression, but valid DEFLATE.
pub fn store(data: [int]): [int] {
  var o = Out { bytes: [], acc: 0, n: 0 }
  var start = 0
  loop {
    let end = if data.len() - start > BLOCK { start + BLOCK } else { data.len() }
    o.stored_block(data, start, end, end == data.len())
    start = end
    if start == data.len() { break }
  }
  o.bytes
}

// ---- gzip (RFC 1952) ----

fn le32(x: int): [int] = [x & 0xff, (x >> 8) & 0xff, (x >> 16) & 0xff, (x >> 24) & 0xff]
fn be32(x: int): [int] = [(x >> 24) & 0xff, (x >> 16) & 0xff, (x >> 8) & 0xff, x & 0xff]

fn read_le32(bs: [int], i: int): int =
  bs[i] | (bs[i + 1] << 8) | (bs[i + 2] << 16) | (bs[i + 3] << 24)

fn read_be32(bs: [int], i: int): int =
  (bs[i] << 24) | (bs[i + 1] << 16) | (bs[i + 2] << 8) | bs[i + 3]

/// Compresses `data` as a gzip member (no file name, modification time 0, OS "unknown").
pub fn gzip(data: [int]): [int] = [0x1f, 0x8b, 8, 0, 0, 0, 0, 0, 0, 255] +
  deflate(data) +
  le32(crc32(data)) +
  le32(data.len() & MASK)

/// Decompresses gzip data: every member, concatenated (as `gzip -d` does). Each member's CRC-32
/// and length are checked; the optional header fields (extra, name, comment, header CRC) are
/// read and skipped.
pub fn gunzip(data: [int]): [int]!ZErr {
  if data.len() == 0 { fail(Truncated) }
  var out: [int] = []
  var pos = 0
  while pos < data.len() {
    let start = gzip_header(data, pos)?
    let (got, end) = inflate_at(data, start)?
    if end + 8 > data.len() { fail(Truncated) }
    if read_le32(data, end) != crc32(got) { fail(BadChecksum("CRC-32")) }
    if read_le32(data, end + 4) != (got.len() & MASK) { fail(BadChecksum("length")) }
    out = out + got
    pos = end + 8
  }
  out
}

// Checks a gzip member header at `at` and returns the offset of its DEFLATE data.
fn gzip_header(bs: [int], at: int): int!ZErr {
  if at + 10 > bs.len() { fail(Truncated) }
  if bs[at] != 0x1f || bs[at + 1] != 0x8b { fail(BadHeader(at, "not gzip data")) }
  if bs[at + 2] != 8 { fail(BadHeader(at + 2, "compression method {bs[at + 2]} isn't deflate")) }
  let flags = bs[at + 3]
  if (flags & 0xe0) != 0 { fail(BadHeader(at + 3, "reserved flag bits are set")) }
  var p = at + 10
  if (flags & 4) != 0 {
    // FEXTRA: a 2-byte length, then that many bytes
    if p + 2 > bs.len() { fail(Truncated) }
    p += 2 + (bs[p] | (bs[p + 1] << 8))
  }
  if (flags & 8) != 0 { p = past_zero(bs, p)? }   // FNAME
  if (flags & 16) != 0 { p = past_zero(bs, p)? }  // FCOMMENT
  if (flags & 2) != 0 {
    // FHCRC: the low 16 bits of the CRC-32 of the header so far
    if p + 2 > bs.len() { fail(Truncated) }
    let want = bs[p] | (bs[p + 1] << 8)
    if (crc32(bs[at..p]) & 0xffff) != want { fail(BadChecksum("header CRC")) }
    p += 2
  }
  if p > bs.len() { fail(Truncated) }
  p
}

fn past_zero(bs: [int], from: int): int!ZErr {
  var i = from
  while i < bs.len() {
    if bs[i] == 0 { return i + 1 }
    i += 1
  }
  fail(Truncated)
}

// ---- zlib (RFC 1950) ----

/// Compresses `data` as a zlib stream (header `78 01`, Adler-32 trailer).
pub fn zlib(data: [int]): [int] = [0x78, 0x01] + deflate(data) + be32(adler32(data))

/// Decompresses a zlib stream and checks its Adler-32. Preset dictionaries aren't supported,
/// and nothing may follow the stream.
pub fn unzlib(data: [int]): [int]!ZErr {
  if data.len() < 2 { fail(Truncated) }
  let cmf = data[0]
  let flg = data[1]
  if (cmf & 15) != 8 { fail(BadHeader(0, "compression method {cmf & 15} isn't deflate")) }
  if (cmf >> 4) > 7 { fail(BadHeader(0, "window size too large")) }
  if ((cmf << 8) | flg) % 31 != 0 { fail(BadHeader(1, "header check failed")) }
  if (flg & 0x20) != 0 { fail(BadHeader(1, "preset dictionaries aren't supported")) }
  let (got, end) = inflate_at(data, 2)?
  if end + 4 > data.len() { fail(Truncated) }
  if read_be32(data, end) != adler32(got) { fail(BadChecksum("Adler-32")) }
  if end + 4 != data.len() { fail(BadHeader(end + 4, "data after the end of the stream")) }
  got
}

// ---- zip archives (PKWARE APPNOTE) ----

/// One file in a zip archive. A name ending in `/` is a directory, with empty `data`.
pub struct Entry { name: str, data: [int] }

fn read_le16(bs: [int], i: int): int = bs[i] | (bs[i + 1] << 8)

fn put16(o: var [int], x: int) {
  o.push(x & 0xff)
  o.push((x >> 8) & 0xff)
}

fn put32(o: var [int], x: int) {
  o.put16(x & 0xffff)
  o.put16((x >> 16) & 0xffff)
}

let LOCAL_SIG = 0x04034b50
let CENTRAL_SIG = 0x02014b50
let END_SIG = 0x06054b50
let DOS_DATE = 0x21  // 1980-01-01, the earliest date zip can hold

/// Builds a zip archive. Each file is deflated, or stored when deflating doesn't make it
/// smaller. Names are UTF-8 (flag bit 11); every timestamp is 1980-01-01 00:00, so the same
/// entries always give the same bytes.
pub fn zip(entries: [Entry]): [int]
  requires entries.len() < 0xffff
{
  var out: [int] = []
  var central: [int] = []
  for e in entries {
    let name = e.name.bytes()
    let packed = deflate(e.data)
    let (method, body) = if packed.len() < e.data.len() { (8, packed) } else { (0, e.data) }
    let dir = e.name.ends_with("/")
    // the fields local and central headers share: version needed, flags (UTF-8), method,
    // time, date, CRC-32, sizes, name length
    var common: [int] = []
    common.put16(if method == 8 { 20 } else { 10 })
    common.put16(0x800)
    common.put16(method)
    common.put16(0)
    common.put16(DOS_DATE)
    common.put32(crc32(e.data))
    common.put32(body.len())
    common.put32(e.data.len())
    common.put16(name.len())
    central.put32(CENTRAL_SIG)
    central.put16(0x314)                          // made by Unix, so unzip applies the mode below
    central = central + common + filled(8, 0)     // extra, comment, disk, internal attributes
    let mode = if dir { 0x41ed } else { 0x81a4 }  // 0o40755, 0o100644
    central.put32((mode << 16) | if dir { 0x10 } else { 0 })
    central.put32(out.len())
    central = central + name
    out.put32(LOCAL_SIG)
    out = out + common + [0, 0] + name + body
  }
  let at = out.len()
  out = out + central
  out.put32(END_SIG)
  out.put32(0)  // disk numbers
  out.put16(entries.len())
  out.put16(entries.len())
  out.put32(central.len())
  out.put32(at)
  out.put16(0)  // comment length
  out
}

/// Reads a zip archive's files, in central-directory order, and checks each CRC-32 and size.
/// Handles stored and deflated entries and data descriptors. Encrypted entries, other methods
/// and zip64 archives are `BadHeader` errors. Names are returned as written: check them for
/// `..` and leading `/` before using them as paths.
pub fn unzip(data: [int]): [Entry]!ZErr {
  let end = find_end(data)?
  let count = read_le16(data, end + 10)
  let at = read_le32(data, end + 16)
  if count == 0xffff || at == MASK { fail(BadHeader(end, "zip64 archives aren't supported")) }
  var p = at
  var out: [Entry] = []
  for _ in 0..count {
    if p + 46 > data.len() { fail(Truncated) }
    if read_le32(data, p) != CENTRAL_SIG { fail(BadHeader(p, "bad central directory entry")) }
    let flags = read_le16(data, p + 8)
    let method = read_le16(data, p + 10)
    let crc = read_le32(data, p + 16)
    let csize = read_le32(data, p + 20)
    let size = read_le32(data, p + 24)
    let nlen = read_le16(data, p + 28)
    let local = read_le32(data, p + 42)
    if p + 46 + nlen > data.len() { fail(Truncated) }
    let name = str.from_utf8(
      data[p + 46..p + 46 + nlen],
    ) else fail(BadHeader(p + 46, "file name isn't UTF-8"))
    if (flags & 1) != 0 { fail(BadHeader(p + 8, "{name} is encrypted")) }
    if csize == MASK || size == MASK || local == MASK {
      fail(BadHeader(p + 20, "zip64 archives aren't supported"))
    }
    let bytes = entry_data(data, local, method, csize)?
    if bytes.len() != size { fail(BadChecksum("length")) }
    if crc32(bytes) != crc { fail(BadChecksum("CRC-32")) }
    out.push(Entry { name, data: bytes })
    p += 46 + nlen + read_le16(data, p + 30) + read_le16(data, p + 32)
  }
  out
}

// Finds the end-of-central-directory record, which may be followed by a comment.
fn find_end(bs: [int]): int!ZErr {
  if bs.len() < 22 { fail(Truncated) }
  var i = bs.len() - 22
  let stop = if bs.len() > 22 + 0xffff { bs.len() - 22 - 0xffff } else { 0 }
  while i >= stop {
    if read_le32(bs, i) == END_SIG && i + 22 + read_le16(bs, i + 20) == bs.len() { return i }
    i -= 1
  }
  fail(BadHeader(0, "not a zip archive"))
}

// Reads the data of the entry whose local header starts at `at`.
fn entry_data(bs: [int], at: int, method: int, csize: int): [int]!ZErr {
  if at + 30 > bs.len() { fail(Truncated) }
  if read_le32(bs, at) != LOCAL_SIG { fail(BadHeader(at, "bad local file header")) }
  let start = at + 30 + read_le16(bs, at + 26) + read_le16(bs, at + 28)
  if start + csize > bs.len() { fail(Truncated) }
  match method {
    0 => bs[start..start + csize]
    8 => (inflate_at(bs.take(start + csize), start)?).0
    m => fail(BadHeader(at + 8, "compression method {m} isn't supported"))
  }
}

// ---- tests ----

test "checksums" {
  assert crc32("123456789".bytes()) == 0xcbf43926
  assert crc32([]) == 0
  assert crc32_update(crc32("1234".bytes()), "56789".bytes()) == 0xcbf43926
  assert adler32("Wikipedia".bytes()) == 0x11e60398
  assert adler32([]) == 1
  var big: [int] = []
  for i in 0..10000 { big.push(255 - i % 7) }
  assert adler32(big) == 0xc0307601
}

// Test vectors are written in lower-case hex (`xxd -p`).
fn unhex(h: str): [int] = h.chars().chunks(2).map(p => digit(p[0]) * 16 + digit(p[1]))

fn digit(c: char): int = if c.is_digit() { int(c) - 48 } else { int(c) - 87 }

// These vectors were generated before the Duck → Auk rename; the literals must match the bytes.
// "hello, duck!\n" from `gzip -c -n` (no name, no time) and `gzip -c -9 hello.txt` (with both).
let GZIP_N = unhex("1f8b0800000000000003cb48cdc9c9d75148294dce56e402007a16d23b0d000000")

let GZIP_NAMED = unhex(
  "1f8b0808701b5669020368656c6c6f2e74787400cb48cdc9c9d75148294dce56e402007a16d23b0d" + "000000",
)

// python3: zlib.compress((PARA + PARA).encode(), 9), a dynamic-Huffman block.
let PARA = "Duck is statically typed and compiled to native code. Braces delimit blocks; no semicolons. A newline ends a statement unless the line ends with an operator. Effects are declared: uses fs, net, time. Packages declare their effects, and quack refuses to install a package that needs an effect your project has not allowed. "

let ZLIB_DYNAMIC = unhex(
  "78daed50cd4dc6300c5de50d50750038813eeeac1012979aa676895daa6e8f9b0f8901b8728a1cbf" +
    "5fdff6bc800de6c939a75a4ff8b951419282acebc635065748ecbf28be0a8d786e2993a150e5951d" +
    "6f55f3628f1085d1ca59ab8a8d7882d051590824c590ba09ad248e5d2a99c167c22fe0609fc317ba" +
    "514bae6dc4cb3451f6a0360ab35ce32d0fd82dbc271b42de0738af91e835e525bdf74c1d76497303" +
    "dd05865ee7730f101a4d5d203ab144a25a23d976a7072b79c8d215577ed838756fd89a7e5cc39c2c" +
    "7a3a82a7079511b7ff0bfef182dfb698e7ed",
)

test "known vectors from gzip and python zlib" {
  let hello = "hello, duck!\n".bytes()
  assert gunzip(GZIP_N)? == hello
  assert gunzip(GZIP_NAMED)? == hello
  assert gunzip(GZIP_N + GZIP_NAMED)? == hello + hello  // two members
  assert unzlib(ZLIB_DYNAMIC)? == (PARA + PARA).bytes()
  // raw DEFLATE: fixed Huffman with matches, and a stored block
  assert inflate([75, 76, 74, 78, 68, 69, 10, 25, 169, 57, 57, 249, 0])? ==
    "abcabcabcabcabcabc hello".bytes()
  assert inflate([1, 7, 0, 248, 255, 115, 116, 111, 114, 101, 100, 33])? == "stored!".bytes()
  assert str.from_utf8(gunzip(GZIP_N)?)? == "hello, duck!\n"
}

test "gzip header fields: extra, comment and header CRC" {
  let body = GZIP_N.skip(10)
  // FEXTRA (4 bytes) + FCOMMENT "hi" + FHCRC
  var head = [31, 139, 8, 4 | 16 | 2, 0, 0, 0, 0, 0, 3, 4, 0, 65, 66, 1, 0, 104, 105, 0]
  let hcrc = crc32(head) & 0xffff
  head = head + [hcrc & 0xff, hcrc >> 8]
  assert gunzip(head + body)? == "hello, duck!\n".bytes()
  var bad = head
  bad[bad.len() - 1] = bad[bad.len() - 1] ^ 1
  assert gunzip(bad + body) is err(BadChecksum("header CRC"))
}

fn sample(n: int): [int] {
  // text-like data with repeats, plus some noise
  let words = ["auk", "raft", "pond", "feather", " ", "\n", "the", "a", "wing"]
  var out: [int] = []
  var x = 12345
  while out.len() < n {
    x = (x *% 1103515245 +% 12345) & 0x7fffffff
    for b in words[(x >> 8) % words.len()].bytes() { out.push(b) }
    if x % 13 == 0 { out.push((x >> 3) & 0xff) }
  }
  out.take(n)
}

test "round trips: deflate, store, gzip, zlib" {
  var noise: [int] = []
  var x = 7
  for _ in 0..3000 {
    x = x *% 6364136223846793005 +% 1442695040888963407
    noise.push((x >> 33) & 0xff)
  }
  let cases = [
    [],
    [0],
    "a".bytes(),
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".bytes(),
    "abcabcabcabcabcabc hello".bytes(),
    (PARA + PARA).bytes(),
    sample(5000),
    noise,
    filled(70000, 7),  // spans two blocks; one long run of max-length matches
    sample(140000),    // three blocks, matches across block boundaries
  ]
  for c in cases {
    assert inflate(deflate(c))? == c
    assert inflate(store(c))? == c
    assert gunzip(gzip(c))? == c
    assert unzlib(zlib(c))? == c
  }
  // it compresses: repetitive text shrinks a lot, noise is stored at about its own size
  assert deflate(sample(5000)).len() < 2000
  assert deflate((PARA + PARA).bytes()).len() < 320
  assert deflate(filled(70000, 7)).len() < 500
  assert deflate(noise).len() <= noise.len() + 10
  assert store("stored!".bytes()) == [1, 7, 0, 248, 255, 115, 116, 111, 114, 101, 100, 33]
}

test "output decodes with other decoders' framing" {
  // our gzip and zlib headers are the standard minimal ones
  let g = gzip("hello, duck!\n".bytes())
  assert g.take(4) == [31, 139, 8, 0]
  assert g.skip(g.len() - 8) == [122, 22, 210, 59, 13, 0, 0, 0]
  let z = zlib([])
  assert z.take(2) == [0x78, 0x01] && z.skip(z.len() - 4) == [0, 0, 0, 1]
}

test "corrupt input" {
  assert gunzip([]) is err(Truncated)
  assert gunzip(GZIP_N.take(20)) is err(Truncated)
  assert gunzip(GZIP_N.take(GZIP_N.len() - 3)) is err(Truncated)
  assert gunzip([31, 138] + GZIP_N.skip(2)) is err(BadHeader(0, _))
  assert gunzip([31, 139, 7] + GZIP_N.skip(3)) is err(BadHeader(2, _))
  assert gunzip([31, 139, 8, 0x20] + GZIP_N.skip(4)) is err(BadHeader(3, _))
  var crc = GZIP_N
  crc[crc.len() - 8] = crc[crc.len() - 8] ^ 0xff
  assert gunzip(crc) is err(BadChecksum("CRC-32"))
  var size = GZIP_N
  size[size.len() - 4] = 14
  assert gunzip(size) is err(BadChecksum("length"))
  assert gunzip(GZIP_N + [0]) is err(_)  // trailing garbage
  var z = ZLIB_DYNAMIC
  z[z.len() - 1] = z[z.len() - 1] ^ 1
  assert unzlib(z) is err(BadChecksum("Adler-32"))
  assert unzlib([0x78]) is err(Truncated)
  assert unzlib([0x79, 0x9c] + ZLIB_DYNAMIC.skip(2)) is err(BadHeader(0, _))
  assert unzlib([0x78, 0x9d] + ZLIB_DYNAMIC.skip(2)) is err(BadHeader(1, _))
  assert unzlib([0x78, 0xbb, 0, 0, 0, 1] + ZLIB_DYNAMIC.skip(2)) is err(BadHeader(1, _))
  assert unzlib(ZLIB_DYNAMIC + [0]) is err(BadHeader(_, _))
  assert inflate([]) is err(Truncated)
  assert inflate([7]) is err(BadData(_, "invalid block type 3"))
  assert inflate([1, 7, 0, 248, 254, 115]) is err(BadData(1, "stored block length check failed"))
  assert inflate([1, 7, 0, 248, 255, 115]) is err(Truncated)
  // fixed block: literal 'a', then length 3 at distance 1 is fine, distance 2 is too far
  var o = Out { bytes: [], acc: 0, n: 0 }
  o.put(1, 1)
  o.put(1, 2)
  o.put_sym(97)
  o.put_sym(257)
  o.put(rev(1, 5), 5)  // distance code 1 = distance 2
  o.put_sym(256)
  o.align()
  assert inflate(o.bytes) is err(BadData(_, "distance too far back"))
  // dynamic block whose code length code is over-subscribed (every length 1)
  var d = Out { bytes: [], acc: 0, n: 0 }
  d.put(1, 1)
  d.put(2, 2)
  d.put(0, 5)
  d.put(0, 5)
  d.put(15, 4)
  for _ in 0..19 { d.put(1, 3) }
  d.align()
  assert inflate(d.bytes) is err(BadData(_, "incomplete code length code"))
  // a truncated dynamic stream
  assert unzlib(ZLIB_DYNAMIC.take(100)) is err(Truncated)
  assert message(BadData(3, "x")) == "bad deflate data at 3: x"
  assert message(BadChecksum("CRC-32")) == "CRC-32 check failed: the data is corrupt"
}

// `zip -rX -z small.zip a.txt d` (Info-ZIP 3.0): stored files, a directory and a comment "hi".
let ZIP_CLI = unhex(
  "504b03040a0000000000175e5e5d7a16d23b0d0000000d00000005000000612e74787468656c6c6f" +
    "2c206475636b210a504b03040a0000000000175e5e5d00000000000000000000000002000000642f" +
    "504b0304140000000800175e5e5d37bae58a0c0000002400000007000000642f712e7478742b2c4d" +
    "4cce5628c447720100504b01021e030a0000000000175e5e5d7a16d23b0d0000000d000000050000" +
    "000000000001000000a48100000000612e747874504b01021e030a0000000000175e5e5d00000000" +
    "0000000000000000020000000000000000001000ed4130000000642f504b01021e03140000000800" +
    "175e5e5d37bae58a0c00000024000000070000000000000001000000a48150000000642f712e7478" +
    "74504b05060000000003000300980000008100000002006869",
)

// python3 zipfile writing to an unseekable stream: deflated, sizes in data descriptors.
let ZIP_STREAMED = unhex(
  "504b0304140008000800000021000000000000000000000000000c00000073747265616d65642e74" +
    "7874edc6211100400800b02a547b81c4c0f73f52e036b5f99dafa232c6cccccccccccccccccc8eb6" +
    "504b0708c0a4d2632600000088130000504b0304140008000800125e5e5d00000000000000000000" +
    "000009000000706c61696e2e747874cbc80400504b0708ac2a93d80400000002000000504b010214" +
    "0314000800080000002100c0a4d26326000000881300000c00000000000000000000008001000000" +
    "0073747265616d65642e747874504b01021403140008000800125e5e5dac2a93d804000000020000" +
    "00090000000000000000000000800160000000706c61696e2e747874504b05060000000002000200" +
    "710000009b0000000000",
)

test "unzip archives from zip and python" {
  let es = unzip(ZIP_CLI)?
  assert es.map(e => e.name) == ["a.txt", "d/", "d/q.txt"]
  assert es[0].data == "hello, duck!\n".bytes()
  assert es[1].data == []
  assert es[2].data == "quack quack quack quack quack quack\n".bytes()
  let st = unzip(ZIP_STREAMED)?
  assert st.map(e => e.name) == ["streamed.txt", "plain.txt"]
  assert st[0].data == "stream me ".repeat(500).bytes()
  assert st[1].data == "hi".bytes()
}

test "zip round trips and is deterministic" {
  let es = [
    Entry { name: "a.txt", data: "hello, auk!\n".bytes() },
    Entry { name: "dir/", data: [] },
    Entry { name: "dir/big.txt", data: sample(20000) },
    Entry { name: "dir/ünï.bin", data: [0, 255, 7] },
    Entry { name: "empty", data: [] },
  ]
  let z = zip(es)
  assert unzip(z)? == es
  assert zip(es) == z
  assert z.len() < 20000 / 2  // big.txt was deflated
  assert unzip(zip([]))? == []
  assert zip([]) == [80, 75, 5, 6] + filled(18, 0)
}

test "corrupt zip archives" {
  assert unzip([]) is err(Truncated)
  assert unzip(GZIP_N) is err(BadHeader(0, "not a zip archive"))
  assert unzip(ZIP_CLI.take(ZIP_CLI.len() - 1)) is err(BadHeader(0, _))  // comment cut short
  var crc = ZIP_CLI
  crc[35] = crc[35] ^ 1  // the first file's data: "hello" becomes "iello"
  assert unzip(crc) is err(BadChecksum("CRC-32"))
  var method = ZIP_STREAMED
  method[0x9b + 10] = 12  // bzip2 in the first central entry
  assert unzip(method) is err(BadHeader(_, "compression method 12 isn't supported"))
  var locked = ZIP_STREAMED
  locked[0x9b + 8] = locked[0x9b + 8] | 1
  assert unzip(locked) is err(BadHeader(_, "streamed.txt is encrypted"))
  var moved = ZIP_CLI
  moved[0x81 + 42] = 1  // the first central entry's local header offset
  assert unzip(moved) is err(BadHeader(1, "bad local file header"))
  // the central directory (0x98 bytes at 0x81) is missing
  assert unzip(ZIP_CLI.take(0x81) + ZIP_CLI.skip(0x81 + 0x98)) is err(Truncated)
}