1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
# 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
}
state inflated: bytes # the last stream's bytes
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(lengths) -> 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 lengths { counts[x] = counts[x] + 1 }
for n in 1 .. 16 {
for s in 0 .. lengths.count {
if lengths[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
}
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 order: list of number = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
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 lengths, distances: list of number
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) }
} else {
let literals = take(d, at, 5) + 257
let count = take(d, at + 5, 5) + 1
let n = take(d, at + 10, 4) + 4
at = at + 14
let small: list of number = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for k in 0 .. n { small[order[k]] = take(d, at + 3 * k, 3) }
at = at + 3 * n
let c = code(small)
let both: list of number
while both.count < literals + count {
let symbol, next = decode(d, at, c)
at = 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, at, 2) { both.append(previous) }
at = at + 2
} else if symbol == 17 {
for k in 0 .. 3 + take(d, at, 3) { both.append(0) }
at = at + 3
} else {
for k in 0 .. 11 + take(d, at, 7) { both.append(0) }
at = at + 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]) }
}
let lc = code(lengths)
let dc = code(distances)
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)
}
}
}
inflated = bytes(out)
}
|
