/
fflate.ts
303 lines (282 loc) · 9.39 KB
/
fflate.ts
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
/* eslint-disable */
type InflateState = {
// lmap
l?: Uint16Array | undefined;
// dmap
d?: Uint16Array | undefined;
// lbits
m?: number | undefined;
// dbits
n?: number | undefined;
// final
f?: number;
// pos
p?: number;
// byte
b?: number;
// lstchk
i?: boolean;
};
const u8 = Uint8Array, u16 = Uint16Array, u32 = Uint32Array;
const clim = new u8([16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]);
const fleb = new u8([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, /* unused */ 0, 0, /* impossible */ 0]);
const fdeb = new u8([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, /* unused */ 0, 0]);
const freb = (eb: Uint8Array, start: number) => {
const b = new u16(31);
for (let i = 0; i < 31; ++i) {
b[i] = start += 1 << eb[i - 1];
}
// numbers here are at max 18 bits
const r = new u32(b[30]);
for (let i = 1; i < 30; ++i) {
for (let j = b[i]; j < b[i + 1]; ++j) {
r[j] = ((j - b[i]) << 5) | i;
}
}
return [b, r] as const;
}
const [fl, revfl] = freb(fleb, 2);
fl[28] = 258, revfl[258] = 28;
const [fd] = freb(fdeb, 0);
const rev = new u16(32768);
for (let i = 0; i < 32768; ++i) {
// reverse table algorithm from SO
let x = ((i & 0xAAAA) >>> 1) | ((i & 0x5555) << 1);
x = ((x & 0xCCCC) >>> 2) | ((x & 0x3333) << 2);
x = ((x & 0xF0F0) >>> 4) | ((x & 0x0F0F) << 4);
rev[i] = (((x & 0xFF00) >>> 8) | ((x & 0x00FF) << 8)) >>> 1;
}
const hMap = ((cd: Uint8Array, mb: number, r: 0 | 1) => {
const s = cd.length;
// index
let i = 0;
// u16 "map": index -> # of codes with bit length = index
const l = new u16(mb);
// length of cd must be 288 (total # of codes)
for (; i < s; ++i) ++l[cd[i] - 1];
// u16 "map": index -> minimum code for bit length = index
const le = new u16(mb);
for (i = 0; i < mb; ++i) {
le[i] = (le[i - 1] + l[i - 1]) << 1;
}
let co: Uint16Array;
if (r) {
// u16 "map": index -> number of actual bits, symbol for code
co = new u16(1 << mb);
// bits to remove for reverser
const rvb = 15 - mb;
for (i = 0; i < s; ++i) {
// ignore 0 lengths
if (cd[i]) {
// num encoding both symbol and bits read
const sv = (i << 4) | cd[i];
// free bits
const r = mb - cd[i];
// start value
let v = le[cd[i] - 1]++ << r;
// m is end value
for (const m = v | ((1 << r) - 1); v <= m; ++v) {
// every 16 bit value starting with the code yields the same result
co[rev[v] >>> rvb] = sv;
}
}
}
} else {
co = new u16(s);
for (i = 0; i < s; ++i) co[i] = rev[le[cd[i] - 1]++] >>> (15 - cd[i]);
}
return co;
});
const flt = new u8(288);
for (let i = 0; i < 144; ++i) flt[i] = 8;
for (let i = 144; i < 256; ++i) flt[i] = 9;
for (let i = 256; i < 280; ++i) flt[i] = 7;
for (let i = 280; i < 288; ++i) flt[i] = 8;
const fdt = new u8(32);
for (let i = 0; i < 32; ++i) fdt[i] = 5;
const flrm = hMap(flt, 9, 1);
const fdrm = hMap(fdt, 5, 1);
const bits = (d: Uint8Array, p: number, m: number) => {
const o = p >>> 3;
return ((d[o] | (d[o + 1] << 8)) >>> (p & 7)) & m;
}
const bits16 = (d: Uint8Array, p: number) => {
const o = p >>> 3;
return ((d[o] | (d[o + 1] << 8) | (d[o + 2] << 16)) >>> (p & 7));
}
const shft = (p: number) => (p >>> 3) + (p & 7 && 1);
const slc = <T extends Uint8Array | Uint16Array | Uint32Array>(v: T, s: number, e?: number): T => {
if (s == null || s < 0) s = 0;
if (e == null || e > v.length) e = v.length;
// can't use .constructor in case user-supplied
const n = new (v instanceof u16 ? u16 : v instanceof u32 ? u32 : u8)(e - s) as T;
n.set(v.subarray(s, e));
return n;
}
const max = (a: Uint8Array | number[]) => {
let m = a[0];
for (let i = 1, count = a.length; i < count; ++i) {
if (a[i] > m) m = a[i];
}
return m;
};
const inflt = (dat: Uint8Array, buf?: Uint8Array, st?: InflateState) => {
const noSt = !st || st.i;
if (!st) st = {};
// source length
const sl = dat.length;
// have to estimate size
const noBuf = !buf || !noSt;
// Assumes roughly 33% compression ratio average
if (!buf) buf = new u8(sl * 3);
// ensure buffer can fit at least l elements
const cbuf = (l: number) => {
let bl = buf!.length;
// need to increase size to fit
if (l > bl) {
// Double or set to necessary, whichever is greater
const nbuf = new u8(Math.max(bl << 1, l));
nbuf.set(buf!);
buf = nbuf;
}
};
// last chunk bitpos bytes
let final = st.f || 0, pos = st.p || 0, bt = st.b || 0, lm = st.l, dm = st.d, lbt = st.m, dbt = st.n;
if (final && !lm) return buf;
// total bits
const tbts = sl << 3;
do {
if (!lm) {
// BFINAL - this is only 1 when last chunk is next
st.f = final = bits(dat, pos, 1);
// type: 0 = no compression, 1 = fixed huffman, 2 = dynamic huffman
const type = bits(dat, pos + 1, 3);
pos += 3;
if (!type) {
// go to end of byte boundary
const s = shft(pos) + 4, l = dat[s - 4] | (dat[s - 3] << 8), t = s + l;
if (t > sl) {
if (noSt) throw 'unexpected EOF';
break;
}
// ensure size
if (noBuf) cbuf(bt + l);
// Copy over uncompressed data
buf.set(dat.subarray(s, t), bt);
// Get new bitpos, update byte count
st.b = bt += l, st.p = pos = t << 3;
continue;
}
else if (type == 1) lm = flrm, dm = fdrm, lbt = 9, dbt = 5;
else if (type == 2) {
// literal lengths
const hLit = bits(dat, pos, 31) + 257, hcLen = bits(dat, pos + 10, 15) + 4;
const tl = hLit + bits(dat, pos + 5, 31) + 1;
pos += 14;
// length+distance tree
const ldt = new u8(tl);
// code length tree
const clt = new u8(19);
for (let i = 0; i < hcLen; ++i) {
// use index map to get real code
clt[clim[i]] = bits(dat, pos + i * 3, 7);
}
pos += hcLen * 3;
// code lengths bits
const clb = max(clt), clbmsk = (1 << clb) - 1;
if (!noSt && pos + tl * (clb + 7) > tbts) break;
// code lengths map
const clm = hMap(clt, clb, 1);
for (let i = 0; i < tl;) {
const r = clm[bits(dat, pos, clbmsk)];
// bits read
pos += r & 15;
// symbol
const s = r >>> 4;
// code length to copy
if (s < 16) {
ldt[i++] = s;
} else {
// copy count
let c = 0, n = 0;
if (s == 16) n = 3 + bits(dat, pos, 3), pos += 2, c = ldt[i - 1];
else if (s == 17) n = 3 + bits(dat, pos, 7), pos += 3;
else if (s == 18) n = 11 + bits(dat, pos, 127), pos += 7;
while (n--) ldt[i++] = c;
}
}
// length tree distance tree
const lt = ldt.subarray(0, hLit), dt = ldt.subarray(hLit);
// max length bits
lbt = max(lt);
// max dist bits
dbt = max(dt);
lm = hMap(lt, lbt, 1);
dm = hMap(dt, dbt, 1);
} else throw 'invalid block type';
if (pos > tbts) throw 'unexpected EOF';
}
// Make sure the buffer can hold this + the largest possible addition
// maximum chunk size (practically, theoretically infinite) is 2^17;
if (noBuf) cbuf(bt + 131072);
const lms = (1 << lbt!) - 1, dms = (1 << dbt!) - 1;
const mxa = lbt! + dbt! + 18;
while (noSt || pos + mxa < tbts) {
// bits read, code
const c = lm[bits16(dat, pos) & lms], sym = c >>> 4;
pos += c & 15;
if (pos > tbts) throw 'unexpected EOF';
if (!c) throw 'invalid length/literal';
if (sym < 256) buf[bt++] = sym;
else if (sym == 256) {
lm = undefined;
break;
}
else {
let add = sym - 254;
// no extra bits needed if less
if (sym > 264) {
// index
const i = sym - 257, b = fleb[i];
add = bits(dat, pos, (1 << b) - 1) + fl[i];
pos += b;
}
// dist
const d = dm![bits16(dat, pos) & dms], dsym = d >>> 4;
if (!d) throw 'invalid distance';
pos += d & 15;
let dt = fd[dsym];
if (dsym > 3) {
const b = fdeb[dsym];
dt += bits16(dat, pos) & ((1 << b) - 1), pos += b;
}
if (pos > tbts) throw 'unexpected EOF';
if (noBuf) cbuf(bt + 131072);
const end = bt + add;
for (; bt < end; bt += 4) {
buf[bt] = buf[bt - dt];
buf[bt + 1] = buf[bt + 1 - dt];
buf[bt + 2] = buf[bt + 2 - dt];
buf[bt + 3] = buf[bt + 3 - dt];
}
bt = end;
}
}
st.l = lm, st.p = pos, st.b = bt;
if (lm) final = 1, st.m = lbt, st.d = dm, st.n = dbt;
} while (!final);
return bt == buf.length ? buf : slc(buf, 0, bt);
}
const zlv = (d: Uint8Array) => {
if ((d[0] & 15) != 8 || (d[0] >>> 4) > 7 || ((d[0] << 8 | d[1]) % 31)) throw 'invalid zlib data';
if (d[1] & 32) throw 'invalid zlib data: preset dictionaries not supported';
}
/**
* Expands Zlib data
* @param data The data to decompress
* @param out Where to write the data. Saves memory if you know the decompressed size and provide an output buffer of that length.
* @returns The decompressed version of the data
*/
export function unzlibSync(data: Uint8Array, out?: Uint8Array) {
return inflt((zlv(data), data.subarray(2, -4)), out);
}