# inflate (RFC 1951): a raw deflate stream inflated to its bytes. Codes are read a bit at a time from their canonical
# counts (as zlib's puff.c does), so each step is the specification's. A stream that is no deflate fails its event.
record Code {
  counts: list of number                         # how many codes of each length, 0 to 15
  symbols: list of number                        # the symbols in their codes' order
}
record Lengths {
  of: list of number
}
record Inflated {
  data: bytes
}
state inflated: list of Inflated                 # the last stream's bytes (a list of one: a record is no state alone)
input inflate = message { data: bytes }

fn bit(d, at) = d[at // 8] >> at % 8 & 1

# n bits from bit at, the first the lowest.
fn take(d, at, n) {
  let v = i64(0)
  for k in 0 .. n { v = v | bit(d, at + k) << k }
  return number(v)
}

fn code(l) -> Code {
  let counts: list of number = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  let symbols: list of number
  for x in l.of { counts[x] = counts[x] + 1 }
  for n in 1 .. 16 {
    for s in 0 .. l.of.count {
      if l.of[s] == n { symbols.append(s) }
    }
  }
  return Code { counts: counts, symbols: symbols }
}

# The symbol whose code starts at bit at, and the bit after it.
fn decode(d, at, c) {
  let value, first, index = 0, 0, 0
  for n in 1 .. 16 {
    value = value + number(bit(d, at + n - 1))
    if value - first < c.counts[n] { return c.symbols[index + value - first], at + n }
    index = index + c.counts[n]
    first = (first + c.counts[n]) * 2
    value = value * 2
  }
  require false                                  # no such code
  return 0, at
}

# A block's literal and length code and its distance code, fixed (kind 1) or from bit at (kind 2), and the bit after.
fn codes(d, at, kind) -> Code, Code, number {
  let lengths: list of number
  let distances: list of number
  let both: list of number
  let order: list of number = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
  let small: list of number = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  let i = at
  if kind == 1 {
    for s in 0 .. 288 { lengths.append(if s < 144 { 8 } else if s < 256 { 9 } else if s < 280 { 7 } else { 8 }) }
    for s in 0 .. 30 { distances.append(5) }
    return code(Lengths { of: lengths }), code(Lengths { of: distances }), i
  }
  let literals = take(d, i, 5) + 257
  let count = take(d, i + 5, 5) + 1
  let n = take(d, i + 10, 4) + 4
  i = i + 14
  for k in 0 .. n { small[order[k]] = take(d, i + 3 * k, 3) }
  i = i + 3 * n
  let c = code(Lengths { of: small })
  while both.count < literals + count {
    let symbol, next = decode(d, i, c)
    i = next
    if symbol < 16 {
      both.append(symbol)
    } else if symbol == 16 {
      require both.count > 0                     # a repeat with nothing before it
      let previous = both[both.count - 1]
      for k in 0 .. 3 + take(d, i, 2) { both.append(previous) }
      i = i + 2
    } else if symbol == 17 {
      for k in 0 .. 3 + take(d, i, 3) { both.append(0) }
      i = i + 3
    } else {
      for k in 0 .. 11 + take(d, i, 7) { both.append(0) }
      i = i + 7
    }
  }
  require both.count == literals + count
  for s in 0 .. literals { lengths.append(both[s]) }
  for s in literals .. literals + count { distances.append(both[s]) }
  return code(Lengths { of: lengths }), code(Lengths { of: distances }), i
}

on inflate {
  let length_base: list of number = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99,
                                     115, 131, 163, 195, 227, 258]
  let length_extra: list of number = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0]
  let distance_base: list of number = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
                                       1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577]
  let distance_extra: list of number = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
                                        12, 12, 13, 13]
  let d = inflate.data
  let out: list of i64
  let at = 0
  let last = 0
  while last == 0 {
    last = take(d, at, 1)
    let kind = take(d, at + 1, 2)
    at = at + 3
    if kind == 0 {                               # stored: from the next byte, its length and the length's complement
      let b = (at + 7) // 8
      let size = number(d[b] | d[b + 1] << 8)
      require size == number((d[b + 2] | d[b + 3] << 8) ^ 0xffff) && b + 4 + size <= d.bytes
      for k in 0 .. size { out.append(d[b + 4 + k]) }
      at = (b + 4 + size) * 8
    } else {
      require kind != 3
      let lc, dc, next = codes(d, at, kind)
      at = next
      let symbol, then = decode(d, at, lc)
      at = then
      while symbol != 256 {
        if symbol < 256 {
          out.append(i64(symbol))
        } else {
          let s = symbol - 257
          require s < 29
          let length = length_base[s] + take(d, at, length_extra[s])
          let ds, after = decode(d, at + length_extra[s], dc)
          require ds < 30
          let distance = distance_base[ds] + take(d, after, distance_extra[ds])
          at = after + distance_extra[ds]
          require distance <= out.count            # too far back
          for k in 0 .. length { out.append(out[out.count - distance]) }
        }
        symbol, at = decode(d, at, lc)
      }
    }
  }
  if inflated.count > 0 { inflated.remove(inflated.first) }
  inflated.append(Inflated { data: bytes(out) })
}