Pure 140's inflate (RFC 1951): examples/inflate.aup, a raw deflate stream inflated to its bytes, codes read a bit at a time from their canonical counts (as zlib's puff.c), stored, fixed and dynamic blocks, a stream that is none failing its event; no new form: the code tables passed in a record (a fn takes no list), the output a list of one item (a bytes value is no state), a block's tables built in a fn (a let's list lives in the handler's own block); 132 lines against Python's 81

1 files changed, 143 insertions, 0 deletions

diff --git a/examples/inflate.aup b/examples/inflate.aup
new file mode 100644
index 0000000..4516411
--- /dev/null
+++ b/examples/inflate.aup
@@ -0,0 +1,143 @@
+# 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) })
+}