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
130
|
# 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: list of number
let 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)
}
|
