From 899572480735ac212219f8be4d91a0e4c2a46949 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 19 Oct 2026 02:26:52 +0100 Subject: 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 --- examples/inflate.aup | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 143 insertions(+) create mode 100644 examples/inflate.aup (limited to 'examples/inflate.aup') 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) }) +} -- cgit v1.2.3