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
131
132
133
134
135
136
137
138
139
140
141
142
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) })
}
|
