zlib.bend
bend-kit-zlib@0.5.0.0 · 1,081 lines · 0 definitions
1# DEFLATE, gzip, and zlib encoding and decoding (RFC 1951, 1952, 1950) over Bytes, plus gzip, zstd, and brotli through the C libraries. Source: https://github.com/paymog/bend-kit/tree/main/zlib
2import Base
3import bend-kit-bytes@0.3.3.0/bytes.bend as Bytes
4import bend-kit-bits@0.1.0.0/bits.bend as Bits
5import bend-kit-hash@0.3.0.1/hash.bend as Hash
6
7def bits(+n: U32) -> Nat:
8 U32.to_nat(n)
9
10# Bit reader. bad: a read ran past the end, so the input was cut short.
11type Br is Type:
12 Br{r: Bits.Reader, bad: Bool}
13
14def br.got(+bad: Bool, rm: Bits.Reader & Maybe<&2, U32>) -> Br & U32:
15 (r, m) = rm
16 match m:
17 case None{}:
18 (Br{r, True{}}, 0)
19 case Some{v}:
20 (Br{r, bad}, v)
21
22def br.take(b: Br, +n: U32) -> Br & U32:
23 Br{r, +bad} = b
24 br.got(bad, Bits.Reader.lsb(r, n))
25
26# No code: 9999, never a symbol.
27def br.sym.got(+bad: Bool, r: Bits.Huff & Bits.Reader & Maybe<&2, U32>) -> Bits.Huff & Br & U32:
28 (h, rd, m) = r
29 match m:
30 case None{}:
31 (h, Br{rd, True{}}, 9999)
32 case Some{v}:
33 (h, Br{rd, bad}, v)
34
35def br.sym(h: Bits.Huff, b: Br) -> Bits.Huff & Br & U32:
36 Br{r, +bad} = b
37 br.sym.got(bad, Bits.Huff.decode(h, r))
38
39# RFC 1951 §3.2.4: a stored block starts on a byte boundary.
40def br.align(b: Br) -> Br:
41 Br{r, bad} = b
42 Br{Bits.Reader.align(r), bad}
43
44def nth(xs: List<&2, U32>, +i: U32) -> U32:
45 match xs:
46 case Nil{}:
47 0
48 case Con{h, t}:
49 Bool.pick(U32, U32.is_zero(i), h, nth(t, (i - 1 : U32)))
50
51def rep(k: Nat, +v: U32, acc: List<&2, U32>) -> List<&2, U32>:
52 match k:
53 case 0n:
54 acc
55 case 1n+p:
56 rep(p, v, Con{v, acc})
57
58def take.n(k: Nat, xs: List<&2, U32>) -> List<&2, U32>:
59 match k:
60 case 0n:
61 Nil{}
62 case 1n+p:
63 match xs:
64 case Nil{}:
65 Nil{}
66 case Con{h, t}:
67 Con{h, take.n(p, t)}
68
69def drop.n(k: Nat, xs: List<&2, U32>) -> List<&2, U32>:
70 match k:
71 case 0n:
72 xs
73 case 1n+p:
74 match xs:
75 case Nil{}:
76 Nil{}
77 case Con{h, t}:
78 drop.n(p, t)
79
80# RFC 1951 §3.2.5
81def len.base() -> List<&2, U32>:
82 [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]
83
84def len.extra() -> List<&2, U32>:
85 [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]
86
87def dist.base() -> List<&2, U32>:
88 [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]
89
90def dist.extra() -> List<&2, U32>:
91 [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]
92
93# RFC 1951 §3.2.6
94def fixed.lit() -> Maybe<&1, Bits.Huff>:
95 Bits.Huff.from_lens(False{}, rep(144n, 8, rep(112n, 9, rep(24n, 7, rep(8n, 8, Nil{})))))
96
97def fixed.dist() -> Maybe<&1, Bits.Huff>:
98 Bits.Huff.from_lens(False{}, rep(30n, 5, Nil{}))
99
100# Output: 2^dep words of packed bytes, n of them written. Matches copy from the output itself.
101type Out is Type:
102 Out{buf: Array<U32>, dep: U32, n: U32}
103
104def out.fits(+dep: U32, +want: U32) -> Bool:
105 U32.is_le(want, U32.shln(4, bits(dep)))
106
107def out.dep(f: Nat, fits: Bool, +dep: U32, +want: U32) -> U32:
108 match f:
109 case 0n:
110 dep
111 case 1n+p:
112 match fits:
113 case True{}:
114 dep
115 case False{}:
116 +d = (dep + 1 : U32)
117 out.dep(p, out.fits(d, want), d, want)
118
119def out.grow(fits: Bool, o: Out, +want: U32) -> Out:
120 match fits:
121 case True{}:
122 o
123 case False{}:
124 Out{buf, +dep, +n} = o
125 +d = out.dep(28n, False{}, dep, want)
126 Out{Bytes.dst(Bytes.copy(n, buf, Array.new(U32, bits(d), 0), 0, 0)), d, n}
127
128# The buffer doubles until k more bytes fit, so output is O(total), and it ends as the
129# fewest 2^dep words that hold n, as Bytes expects.
130def out.room(o: Out, +k: U32) -> Out:
131 Out{buf, +dep, +n} = o
132 +want = (n + k : U32)
133 out.grow(out.fits(dep, want), Out{buf, dep, n}, want)
134
135def out.put(o: Out, +c: U32) -> Out:
136 Out{buf, dep, +n} = o
137 Out{Bytes.poke(buf, n, c), dep, (n + 1 : U32)}
138
139def out.size(o: Out) -> Out & U32:
140 Out{buf, dep, +n} = o
141 (Out{buf, dep, n}, n)
142
143def out.bytes(o: Out) -> Bytes.Bytes:
144 Out{buf, dep, n} = o
145 Bytes.Bytes{n, buf}
146
147type Mo is Type:
148 MoHead{}
149 MoCodes{lit: Bits.Huff, dist: Bits.Huff}
150 MoDone{}
151 MoBad{}
152
153type Is is Type:
154 Is{br: Br, o: Out, mode: Mo, last: Bool}
155
156def inf.next(last: Bool) -> Mo:
157 match last:
158 case True{}:
159 MoDone{}
160 case False{}:
161 MoHead{}
162
163def inf.bad(b: Br, o: Out) -> Is:
164 Is{b, o, MoBad{}, True{}}
165
166# Stored block (§3.2.4): LEN, then NLEN (its complement), then LEN raw bytes.
167def sb.put(bv: Br & U32, o: Out) -> Br & Out:
168 (b, +c) = bv
169 (b, out.put(o, c))
170
171def sb.go(k: Nat, st: Br & Out) -> Br & Out:
172 match k:
173 case 0n:
174 st
175 case 1n+f:
176 (b, o) = st
177 sb.go(f, sb.put(br.take(b, 8), o))
178
179def sb.done(st: Br & Out, +last: Bool) -> Is:
180 (b, o) = st
181 Is{b, o, inf.next(last), last}
182
183def sb.ok(ok: Bool, b: Br, +len: U32, o: Out, +last: Bool) -> Is:
184 match ok:
185 case False{}:
186 inf.bad(b, o)
187 case True{}:
188 sb.done(sb.go(bits(len), (b, out.room(o, len))), last)
189
190def sb.nlen(bv: Br & U32, +len: U32, o: Out, +last: Bool) -> Is:
191 (b, +nlen) = bv
192 sb.ok(U32.is_eq(U32.xor(len, 65535), nlen), b, len, o, last)
193
194def sb.len(bv: Br & U32, o: Out, +last: Bool) -> Is:
195 (b, +len) = bv
196 sb.nlen(br.take(b, 16), len, o, last)
197
198def inf.stored(b: Br, o: Out, +last: Bool) -> Is:
199 sb.len(br.take(br.align(b), 16), o, last)
200
201# Dynamic block (§3.2.7): code lengths for the code-length code, then the lengths themselves.
202# cl.slot[i]: where symbol i's length sits in the order the stream sends them.
203def cl.slot() -> List<&2, U32>:
204 [3, 17, 15, 13, 11, 9, 7, 5, 4, 6, 8, 10, 12, 14, 16, 18, 0, 1, 2]
205
206def cl.place(xs: List<&2, U32>, +vals: List<&2, U32>) -> List<&2, U32>:
207 match xs:
208 case Nil{}:
209 Nil{}
210 case Con{+i, t}:
211 Con{nth(vals, i), cl.place(t, vals)}
212
213def cl.push(bv: Br & U32, acc: List<&2, U32>) -> Br & List<&2, U32>:
214 (b, v) = bv
215 (b, Con{v, acc})
216
217def cl.one(st: Br & List<&2, U32>) -> Br & List<&2, U32>:
218 (b, acc) = st
219 cl.push(br.take(b, 3), acc)
220
221def cl.read(k: Nat, st: Br & List<&2, U32>) -> Br & List<&2, U32>:
222 match k:
223 case 0n:
224 st
225 case 1n+f:
226 cl.read(f, cl.one(st))
227
228# The code-length code, lengths so far (reversed), how many, the last one (for code 16), and whether it went wrong.
229type Cd is Type:
230 Cd{h: Bits.Huff, br: Br, acc: List<&2, U32>, n: U32, prev: U32, bad: Bool}
231
232def cd.fill(over: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +v: U32, +cnt: U32) -> Cd:
233 match over:
234 case True{}:
235 Cd{h, b, acc, n, v, True{}}
236 case False{}:
237 Cd{h, b, rep(bits(cnt), v, acc), (n + cnt : U32), v, False{}}
238
239def cd.rep(h: Bits.Huff, bv: Br & U32, +v: U32, +base: U32, acc: List<&2, U32>, +n: U32, +total: U32) -> Cd:
240 (b, +e) = bv
241 +cnt = (base + e : U32)
242 cd.fill(U32.is_lt(total, (n + cnt : U32)), h, b, acc, n, v, cnt)
243
244def cd.prev(ok: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +prev: U32, +total: U32) -> Cd:
245 match ok:
246 case False{}:
247 Cd{h, b, acc, n, prev, True{}}
248 case True{}:
249 cd.rep(h, br.take(b, 2), prev, 3, acc, n, total)
250
251def cd.z18(ok: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +total: U32) -> Cd:
252 match ok:
253 case True{}:
254 cd.rep(h, br.take(b, 7), 0, 11, acc, n, total)
255 case False{}:
256 Cd{h, b, acc, n, 0, True{}}
257
258def cd.z17(ok: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +s: U32, +total: U32) -> Cd:
259 match ok:
260 case True{}:
261 cd.rep(h, br.take(b, 3), 0, 3, acc, n, total)
262 case False{}:
263 cd.z18(U32.is_eq(s, 18), h, b, acc, n, total)
264
265def cd.c16(ok: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +prev: U32, +s: U32, +total: U32) -> Cd:
266 match ok:
267 case True{}:
268 cd.prev(U32.is_lt(0, n), h, b, acc, n, prev, total)
269 case False{}:
270 cd.z17(U32.is_eq(s, 17), h, b, acc, n, s, total)
271
272def cd.lit(ok: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +prev: U32, +s: U32, +total: U32) -> Cd:
273 match ok:
274 case True{}:
275 Cd{h, b, Con{s, acc}, (n + 1 : U32), s, False{}}
276 case False{}:
277 cd.c16(U32.is_eq(s, 16), h, b, acc, n, prev, s, total)
278
279# A + binder in a nested tuple does not check (bendlang/bend#1077), so a helper takes it.
280def cd.sym.at(h: Bits.Huff, b: Br, +s: U32, acc: List<&2, U32>, +n: U32, +prev: U32, +total: U32) -> Cd:
281 cd.lit(U32.is_lt(s, 16), h, b, acc, n, prev, s, total)
282
283def cd.sym(r: Bits.Huff & Br & U32, acc: List<&2, U32>, +n: U32, +prev: U32, +total: U32) -> Cd:
284 (h, b, s) = r
285 cd.sym.at(h, b, s, acc, n, prev, total)
286
287def cd.step(stop: Bool, h: Bits.Huff, b: Br, acc: List<&2, U32>, +n: U32, +prev: U32, +bad: Bool, +total: U32) -> Cd:
288 match stop:
289 case True{}:
290 Cd{h, b, acc, n, prev, bad}
291 case False{}:
292 cd.sym(br.sym(h, b), acc, n, prev, total)
293
294# Each step adds at least one length, so total steps suffice.
295def cd.go(k: Nat, +total: U32, st: Cd) -> Cd:
296 match k:
297 case 0n:
298 st
299 case 1n+f:
300 Cd{h, b, acc, +n, +prev, +bad} = st
301 cd.go(f, total, cd.step(Bool.or(bad, U32.is_le(total, n)), h, b, acc, n, prev, bad, total))
302
303def dyn.dist(lit: Bits.Huff, m: Maybe<&1, Bits.Huff>) -> Mo:
304 match m:
305 case None{}:
306 MoBad{}
307 case Some{dist}:
308 MoCodes{lit, dist}
309
310def dyn.mo(l: Maybe<&1, Bits.Huff>, d: Maybe<&1, Bits.Huff>) -> Mo:
311 match l:
312 case None{}:
313 MoBad{}
314 case Some{lit}:
315 dyn.dist(lit, d)
316
317def dyn.tables(bad: Bool, b: Br, +lens: List<&2, U32>, +hlit: U32) -> Br & Mo:
318 match bad:
319 case True{}:
320 (b, MoBad{})
321 case False{}:
322 (b, dyn.mo(Bits.Huff.from_lens(False{}, take.n(bits(hlit), lens)), Bits.Huff.from_lens(False{}, drop.n(bits(hlit), lens))))
323
324def dyn.done(st: Cd, +hlit: U32, +total: U32) -> Br & Mo:
325 Cd{h, b, acc, +n, prev, +bad} = st
326 dyn.tables(Bool.or(bad, Bool.not(U32.is_eq(n, total))), b, List.reverse(&2, U32, acc), hlit)
327
328def dyn.cl(m: Maybe<&1, Bits.Huff>, b: Br, +hlit: U32, +total: U32) -> Br & Mo:
329 match m:
330 case None{}:
331 (b, MoBad{})
332 case Some{h}:
333 dyn.done(cd.go(bits(total), total, Cd{h, b, Nil{}, 0, 0, False{}}), hlit, total)
334
335def dyn.lens(st: Br & List<&2, U32>, +hlit: U32, +hdist: U32) -> Br & Mo:
336 (b, acc) = st
337 dyn.cl(Bits.Huff.from_lens(False{}, cl.place(cl.slot(), List.reverse(&2, U32, acc))), b, hlit, (hlit + hdist : U32))
338
339def dyn.clen(bv: Br & U32, +hlit: U32, +hdist: U32) -> Br & Mo:
340 (b, +hclen) = bv
341 dyn.lens(cl.read(bits((hclen + 4 : U32)), (b, Nil{})), hlit, hdist)
342
343def dyn.hdist(bv: Br & U32, +hlit: U32) -> Br & Mo:
344 (b, +hd) = bv
345 dyn.clen(br.take(b, 4), hlit, (hd + 1 : U32))
346
347def dyn.hlit(bv: Br & U32) -> Br & Mo:
348 (b, +hl) = bv
349 dyn.hdist(br.take(b, 5), (hl + 257 : U32))
350
351def dyn.read(b: Br) -> Br & Mo:
352 dyn.hlit(br.take(b, 5))
353
354# A match copies len bytes from d back in the output, one at a time, so it may overlap itself.
355# ponytail: byte-at-a-time copy; use Bytes.copy when d >= len if long matches dominate.
356def cp.of(+dep: U32, +n: U32, r: Array<U32> & U32) -> Out:
357 (a, +c) = r
358 Out{Bytes.poke(a, n, c), dep, (n + 1 : U32)}
359
360def cp.one(+d: U32, o: Out) -> Out:
361 Out{buf, +dep, +n} = o
362 cp.of(dep, n, Bytes.peek(buf, (n - d : U32)))
363
364def cp.go(k: Nat, +d: U32, o: Out) -> Out:
365 match k:
366 case 0n:
367 o
368 case 1n+f:
369 cp.go(f, d, cp.one(d, o))
370
371# RFC 1951 §3.2.5: a distance may not reach before the first byte out.
372def inf.far(ok: Bool, lit: Bits.Huff, dist: Bits.Huff, b: Br, +len: U32, +d: U32, o: Out, +last: Bool) -> Is:
373 match ok:
374 case False{}:
375 inf.bad(b, o)
376 case True{}:
377 Is{b, cp.go(bits(len), d, out.room(o, len)), MoCodes{lit, dist}, last}
378
379def inf.dn(lit: Bits.Huff, dist: Bits.Huff, b: Br, +len: U32, +d: U32, r: Out & U32, +last: Bool) -> Is:
380 (o, +n) = r
381 inf.far(U32.is_le(d, n), lit, dist, b, len, d, o, last)
382
383def inf.dx(bv: Br & U32, +db: U32, +len: U32, lit: Bits.Huff, dist: Bits.Huff, o: Out, +last: Bool) -> Is:
384 (b, +e) = bv
385 inf.dn(lit, dist, b, len, (db + e : U32), out.size(o), last)
386
387def inf.ds(ok: Bool, lit: Bits.Huff, dist: Bits.Huff, b: Br, +ds: U32, +len: U32, o: Out, +last: Bool) -> Is:
388 match ok:
389 case False{}:
390 inf.bad(b, o)
391 case True{}:
392 inf.dx(br.take(b, nth(dist.extra(), ds)), nth(dist.base(), ds), len, lit, dist, o, last)
393
394# A + binder in a nested tuple does not check (bendlang/bend#1077), so a helper takes it.
395def inf.d.at(dist: Bits.Huff, b: Br, +ds: U32, +len: U32, lit: Bits.Huff, o: Out, +last: Bool) -> Is:
396 inf.ds(U32.is_lt(ds, 30), lit, dist, b, ds, len, o, last)
397
398def inf.d(r: Bits.Huff & Br & U32, +len: U32, lit: Bits.Huff, o: Out, +last: Bool) -> Is:
399 (dist, b, ds) = r
400 inf.d.at(dist, b, ds, len, lit, o, last)
401
402def inf.lx(bv: Br & U32, +lb: U32, lit: Bits.Huff, dist: Bits.Huff, o: Out, +last: Bool) -> Is:
403 (b, +e) = bv
404 inf.d(br.sym(dist, b), (lb + e : U32), lit, o, last)
405
406def inf.ls(ok: Bool, lit: Bits.Huff, dist: Bits.Huff, b: Br, +s: U32, o: Out, +last: Bool) -> Is:
407 match ok:
408 case False{}:
409 inf.bad(b, o)
410 case True{}:
411 +i = (s - 257 : U32)
412 inf.lx(br.take(b, nth(len.extra(), i)), nth(len.base(), i), lit, dist, o, last)
413
414def inf.end(eob: Bool, lit: Bits.Huff, dist: Bits.Huff, b: Br, +s: U32, o: Out, +last: Bool) -> Is:
415 match eob:
416 case True{}:
417 Is{b, o, inf.next(last), last}
418 case False{}:
419 inf.ls(U32.is_le(s, 285), lit, dist, b, s, o, last)
420
421def inf.lit(ok: Bool, lit: Bits.Huff, dist: Bits.Huff, b: Br, +s: U32, o: Out, +last: Bool) -> Is:
422 match ok:
423 case True{}:
424 Is{b, out.put(out.room(o, 1), s), MoCodes{lit, dist}, last}
425 case False{}:
426 inf.end(U32.is_eq(s, 256), lit, dist, b, s, o, last)
427
428# A + binder in a nested tuple does not check (bendlang/bend#1077), so a helper takes it.
429def inf.sym.at(lit: Bits.Huff, b: Br, +s: U32, dist: Bits.Huff, o: Out, +last: Bool) -> Is:
430 inf.lit(U32.is_lt(s, 256), lit, dist, b, s, o, last)
431
432def inf.sym(r: Bits.Huff & Br & U32, dist: Bits.Huff, o: Out, +last: Bool) -> Is:
433 (lit, b, s) = r
434 inf.sym.at(lit, b, s, dist, o, last)
435
436def inf.dyn(bm: Br & Mo, o: Out, +last: Bool) -> Is:
437 (b, m) = bm
438 Is{b, o, m, last}
439
440def inf.t2(is2: Bool, b: Br, o: Out, +last: Bool) -> Is:
441 match is2:
442 case True{}:
443 inf.dyn(dyn.read(b), o, last)
444 case False{}:
445 inf.bad(b, o)
446
447def inf.t1(is1: Bool, b: Br, o: Out, +last: Bool, +t: U32) -> Is:
448 match is1:
449 case True{}:
450 Is{b, o, dyn.mo(fixed.lit(), fixed.dist()), last}
451 case False{}:
452 inf.t2(U32.is_eq(t, 2), b, o, last)
453
454def inf.t0(is0: Bool, b: Br, o: Out, +last: Bool, +t: U32) -> Is:
455 match is0:
456 case True{}:
457 inf.stored(b, o, last)
458 case False{}:
459 inf.t1(U32.is_eq(t, 1), b, o, last, t)
460
461# §3.2.3: BFINAL, then BTYPE.
462def inf.head(bv: Br & U32, o: Out) -> Is:
463 (b, +v) = bv
464 +t = U32.shr(v)
465 inf.t0(U32.is_zero(t), b, o, U32.is_eq(U32.and(v, 1), 1), t)
466
467# Every step reads at least one bit or fails, so 8 steps per input byte always finish a valid stream.
468def inf.go(k: Nat, st: Is) -> Is:
469 match k:
470 case 0n:
471 st
472 case 1n+f:
473 Is{b, o, mode, +last} = st
474 match mode:
475 case MoHead{}:
476 inf.go(f, inf.head(br.take(b, 3), o))
477 case MoCodes{lit, dist}:
478 inf.go(f, inf.sym(br.sym(lit, b), dist, o, last))
479 case MoDone{}:
480 Is{b, o, MoDone{}, last}
481 case MoBad{}:
482 Is{b, o, MoBad{}, last}
483
484# out: the bytes; src: the input back; at: the first byte after the stream.
485type Inflated is Type:
486 Inflated{out: Bytes.Bytes, src: Bytes.Bytes, at: U32}
487
488def inf.done(r: Bytes.Bytes & U32, o: Out) -> Maybe<&1, Inflated>:
489 (src, +pos) = r
490 Some{Inflated{out.bytes(o), src, ((pos + 7) >> 3n : U32)}}
491
492def inf.fin(b: Br, o: Out) -> Maybe<&1, Inflated>:
493 Br{r, bad} = b
494 match bad:
495 case True{}:
496 None{}
497 case False{}:
498 inf.done(Bits.Reader.finish(r), o)
499
500def inf.result(st: Is) -> Maybe<&1, Inflated>:
501 Is{b, o, mode, last} = st
502 match mode:
503 case MoDone{}:
504 inf.fin(b, o)
505 case MoHead{}:
506 None{}
507 case MoCodes{l, d}:
508 None{}
509 case MoBad{}:
510 None{}
511
512def inf.start(ok: Bool, +len: U32, buf: Array<U32>, +at: U32) -> Maybe<&1, Inflated>:
513 match ok:
514 case False{}:
515 None{}
516 case True{}:
517 +fuel = Nat.add(Nat.mul(bits((len - at : U32)), 8n), 8n)
518 inf.result(inf.go(fuel, Is{Br{Bits.Reader{len, buf, (at << 3n : U32)}, False{}}, Out{Array.new(U32, 0n, 0), 0, 0}, MoHead{}, False{}}))
519
520# A raw DEFLATE stream that starts at byte at.
521def inflate.at(b: Bytes.Bytes, +at: U32) -> Maybe<&1, Inflated>:
522 Bytes.Bytes{+len, buf} = b
523 inf.start(U32.is_le(at, len), len, buf, at)
524
525def inflate.out(m: Maybe<&1, Inflated>) -> Maybe<&1, Bytes.Bytes>:
526 match m:
527 case None{}:
528 None{}
529 case Some{Inflated{out, src, at}}:
530 Some{out}
531
532# Raw DEFLATE. None: malformed or cut short.
533def inflate(b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
534 inflate.out(inflate.at(b, 0))
535
536def holds(m: Maybe<&2, U32>, +v: U32) -> Bool:
537 match m:
538 case None{}:
539 False{}
540 case Some{+x}:
541 U32.is_eq(x, v)
542
543def keep(ok: Bool, b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
544 match ok:
545 case True{}:
546 Some{b}
547 case False{}:
548 None{}
549
550def flag(+f: U32, +bit: U32) -> Bool:
551 Bool.not(U32.is_zero(U32.and(f, bit)))
552
553# RFC 1952 §2.3: after the fixed 10 bytes, optional FEXTRA, FNAME, FCOMMENT, FHCRC.
554# Each step takes the buffer and the offset so far; None once a field runs past the end.
555def gz.xlen(+off: U32, r: Bytes.Bytes & Maybe<&2, U32>) -> Bytes.Bytes & Maybe<&2, U32>:
556 (b, m) = r
557 match m:
558 case None{}:
559 (b, None{})
560 case Some{+x}:
561 (b, Some{(off + 2 + x : U32)})
562
563def gz.fextra.at(m: Maybe<&2, U32>, b: Bytes.Bytes) -> Bytes.Bytes & Maybe<&2, U32>:
564 match m:
565 case None{}:
566 (b, None{})
567 case Some{+off}:
568 gz.xlen(off, Bytes.get.u16le(b, off))
569
570def gz.fextra(on: Bool, r: Bytes.Bytes & Maybe<&2, U32>) -> Bytes.Bytes & Maybe<&2, U32>:
571 match on:
572 case False{}:
573 r
574 case True{}:
575 (b, m) = r
576 gz.fextra.at(m, b)
577
578def gz.zero(r: Bytes.Bytes & Maybe<&2, U32>) -> Bytes.Bytes & Maybe<&2, U32>:
579 (b, m) = r
580 match m:
581 case None{}:
582 (b, None{})
583 case Some{+i}:
584 (b, Some{(i + 1 : U32)})
585
586def gz.fstr.at(m: Maybe<&2, U32>, b: Bytes.Bytes) -> Bytes.Bytes & Maybe<&2, U32>:
587 match m:
588 case None{}:
589 (b, None{})
590 case Some{+off}:
591 gz.zero(Bytes.find.from(b, SCon{Chr{0}, SNil{}}, off))
592
593# A zero-terminated FNAME or FCOMMENT.
594def gz.fstr(on: Bool, r: Bytes.Bytes & Maybe<&2, U32>) -> Bytes.Bytes & Maybe<&2, U32>:
595 match on:
596 case False{}:
597 r
598 case True{}:
599 (b, m) = r
600 gz.fstr.at(m, b)
601
602def gz.fhcrc.at(m: Maybe<&2, U32>, b: Bytes.Bytes) -> Bytes.Bytes & Maybe<&2, U32>:
603 match m:
604 case None{}:
605 (b, None{})
606 case Some{+off}:
607 (b, Some{(off + 2 : U32)})
608
609def gz.fhcrc(on: Bool, r: Bytes.Bytes & Maybe<&2, U32>) -> Bytes.Bytes & Maybe<&2, U32>:
610 match on:
611 case False{}:
612 r
613 case True{}:
614 (b, m) = r
615 gz.fhcrc.at(m, b)
616
617def gz.isize(+ok: Bool, +n: U32, out: Bytes.Bytes, r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
618 (src, z) = r
619 keep(Bool.and(ok, holds(z, n)), out)
620
621def gz.crc(r: Bytes.Bytes & U32, +n: U32, +at: U32, c: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
622 (out, +crc) = r
623 (src, m) = c
624 gz.isize(holds(m, crc), n, out, Bytes.get.u32le(src, (at + 4 : U32)))
625
626def gz.trail(m: Maybe<&1, Inflated>) -> Maybe<&1, Bytes.Bytes>:
627 match m:
628 case None{}:
629 None{}
630 case Some{Inflated{out, src, +at}}:
631 Bytes.Bytes{+n, buf} = out
632 gz.crc(Hash.crc32(Bytes.Bytes{n, buf}), n, at, Bytes.get.u32le(src, at))
633
634def gz.body(r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
635 (b, m) = r
636 match m:
637 case None{}:
638 None{}
639 case Some{+off}:
640 gz.trail(inflate.at(b, off))
641
642def gz.flags(+f: U32, b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
643 gz.body(gz.fhcrc(flag(f, 2), gz.fstr(flag(f, 16), gz.fstr(flag(f, 8), gz.fextra(flag(f, 4), (b, Some{10}))))))
644
645def gz.magic(ok: Bool, +f: U32, b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
646 match ok:
647 case True{}:
648 gz.flags(f, b)
649 case False{}:
650 None{}
651
652# ID1 31, ID2 139, CM 8 (DEFLATE), then FLG.
653def gz.head(r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
654 (b, m) = r
655 match m:
656 case None{}:
657 None{}
658 case Some{+w}:
659 gz.magic(U32.is_eq(U32.and(w, 16777215), 559903), U32.shrn(w, 24n), b)
660
661# One gzip member; the CRC-32 and ISIZE must match. None: malformed, cut short, or corrupt.
662# ponytail: bytes after the first member are ignored; loop over members if a server concatenates them.
663def gunzip(b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
664 gz.head(Bytes.get.u32le(b, 0))
665
666# RFC 1950: CMF and FLG, then DEFLATE, then Adler-32, big-endian.
667def zl.sum(r: Bytes.Bytes & U32, c: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
668 (out, +a) = r
669 (src, m) = c
670 keep(holds(m, a), out)
671
672def zl.trail(m: Maybe<&1, Inflated>) -> Maybe<&1, Bytes.Bytes>:
673 match m:
674 case None{}:
675 None{}
676 case Some{Inflated{out, src, +at}}:
677 zl.sum(Hash.adler32(out), Bytes.get.u32be(src, at))
678
679def zl.ok(+cmf: U32, +flg: U32) -> Bool:
680 Bool.and(Bool.and(U32.is_eq(U32.and(cmf, 15), 8), U32.is_le(U32.shrn(cmf, 4n), 7)), Bool.and(U32.is_zero(U32.mod((cmf * 256 + flg : U32), 31)), Bool.not(flag(flg, 32))))
681
682def zl.go(ok: Bool, b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
683 match ok:
684 case True{}:
685 zl.trail(inflate.at(b, 2))
686 case False{}:
687 None{}
688
689def zl.head(r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
690 (b, m) = r
691 match m:
692 case None{}:
693 None{}
694 case Some{+h}:
695 zl.go(zl.ok(U32.shrn(h, 8n), U32.and(h, 255)), b)
696
697def unzlib(b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
698 zl.head(Bytes.get.u16be(b, 0))
699
700# DEFLATE encoding: LZ77 over hash chains, then one final fixed-Huffman block (RFC 1951 §3.2.6).
701# ponytail: fixed Huffman only; dynamic trees would cut text output further.
702
703def bw.code(w: Bits.Writer, cl: U32 & U32) -> Bits.Writer:
704 (+c, +l) = cl
705 Bits.Writer.lsb(w, l, Bits.rev(bits(l), c, 0))
706
707# RFC 1951 §3.2.6: the fixed code of literal/length symbol s, and its length.
708def fx.hi(+s: U32, lo: Bool) -> U32 & U32:
709 match lo:
710 case True{}:
711 ((s - 256 : U32), 7)
712 case False{}:
713 ((s - 88 : U32), 8)
714
715def fx.mid(+s: U32, lo: Bool) -> U32 & U32:
716 match lo:
717 case True{}:
718 ((s + 256 : U32), 9)
719 case False{}:
720 fx.hi(s, U32.is_lt(s, 280))
721
722def fx.low(+s: U32, lo: Bool) -> U32 & U32:
723 match lo:
724 case True{}:
725 ((s + 48 : U32), 8)
726 case False{}:
727 fx.mid(s, U32.is_lt(s, 256))
728
729def fx.lit(+s: U32) -> U32 & U32:
730 fx.low(s, U32.is_lt(s, 144))
731
732# The last index whose base is at most v, with that base and its extra-bit count; bases ascend.
733type Cx is Data:
734 Cx{i: U32, base: U32, extra: U32}
735
736def cx.go(bs: List<&2, U32>, es: List<&2, U32>, +v: U32, +i: U32, +best: Cx) -> Cx:
737 match bs:
738 case Nil{}:
739 best
740 case Con{+b, bt}:
741 match es:
742 case Nil{}:
743 best
744 case Con{+e, et}:
745 cx.go(bt, et, v, (i + 1 : U32), Bool.pick(Cx, U32.is_le(b, v), Cx{i, b, e}, best))
746
747
748def em.len(w: Bits.Writer, +len: U32, c: Cx) -> Bits.Writer:
749 Cx{+i, +b, +e} = c
750 Bits.Writer.lsb(bw.code(w, fx.lit((i + 257 : U32))), e, (len - b : U32))
751
752def em.dist(w: Bits.Writer, +d: U32, c: Cx) -> Bits.Writer:
753 Cx{+i, +b, +e} = c
754 Bits.Writer.lsb(Bits.Writer.lsb(w, 5, Bits.rev(5n, i, 0)), e, (d - b : U32))
755
756def em.match(w: Bits.Writer, +len: U32, +d: U32) -> Bits.Writer:
757 em.dist(em.len(w, len, cx.go(len.base(), len.extra(), len, 0, Cx{0, 3, 0})), d, cx.go(dist.base(), dist.extra(), d, 0, Cx{0, 1, 0}))
758
759def em.lit(w: Bits.Writer, +c: U32) -> Bits.Writer:
760 bw.code(w, fx.lit(c))
761
762# Match finder: the input bytes, packed, the newest position + 1 per hash, and per position the previous one with its hash (0: none).
763type Lz is Type:
764 Lz{src: Array<U32>, head: Array<U32>, prev: Array<U32>}
765
766def lz.at.of(r: Array<U32> & U32, head: Array<U32>, prev: Array<U32>) -> Lz & U32:
767 (src, v) = r
768 (Lz{src, head, prev}, v)
769
770def lz.at(z: Lz, +i: U32) -> Lz & U32:
771 Lz{src, head, prev} = z
772 lz.at.of(Bytes.peek(src, i), head, prev)
773
774def lz.drop(r: Lz & U32) -> Lz:
775 (z, v) = r
776 z
777
778def lz.h3(r: Lz & U32, +a: U32, +b: U32) -> Lz & U32:
779 (z, +c) = r
780 (z, U32.and(U32.xor(U32.xor(U32.shln(a, 10n), U32.shln(b, 5n)), c), 32767))
781
782def lz.h2(r: Lz & U32, +i: U32, +a: U32) -> Lz & U32:
783 (z, +b) = r
784 lz.h3(lz.at(z, (i + 2 : U32)), a, b)
785
786def lz.h1(r: Lz & U32, +i: U32) -> Lz & U32:
787 (z, +a) = r
788 lz.h2(lz.at(z, (i + 1 : U32)), i, a)
789
790def lz.hash(z: Lz, +i: U32) -> Lz & U32:
791 lz.h1(lz.at(z, i), i)
792
793def lz.link(r: Array<U32> & U32, +i: U32, +h: U32, src: Array<U32>, prev: Array<U32>) -> Lz & U32:
794 (head, +old) = r
795 (Lz{src, Array.set(U32, head, h, (i + 1 : U32)), Array.set(U32, prev, U32.and(i, 32767), old)}, old)
796
797def lz.ins.of(r: Lz & U32, +i: U32) -> Lz & U32:
798 (z, +h) = r
799 Lz{src, head, prev} = z
800 lz.link(Array.get(U32, head, h), i, h, src, prev)
801
802# Links position i into the chain for its next three bytes; answers the chain's previous head.
803def lz.insert(z: Lz, +i: U32) -> Lz & U32:
804 lz.ins.of(lz.hash(z, i), i)
805
806# Match length: bytes at a + k and b + k compared so far, and whether the last pair was equal.
807type Ml is Type:
808 Ml{z: Lz, a: U32, b: U32, k: U32, eq: Bool}
809
810def ml.cmp(r: Lz & U32, +a: U32, +b: U32, +k: U32, +x: U32) -> Ml:
811 (z, +y) = r
812 Ml{z, a, b, (k + 1 : U32), U32.is_eq(x, y)}
813
814def ml.read(r: Lz & U32, +a: U32, +b: U32, +k: U32) -> Ml:
815 (z, +x) = r
816 ml.cmp(lz.at(z, (b + k : U32)), a, b, k, x)
817
818def ml.len(+k: U32, eq: Bool) -> U32:
819 match eq:
820 case True{}:
821 k
822 case False{}:
823 (k - 1 : U32)
824
825# Counts equal bytes from a and from b, up to fuel.
826def ml.go(fuel: Nat, st: Ml) -> Lz & U32:
827 match fuel:
828 case 0n:
829 Ml{z, a, b, +k, eq} = st
830 (z, ml.len(k, eq))
831 case 1n+f:
832 Ml{z, +a, +b, +k, eq} = st
833 match eq:
834 case True{}:
835 ml.go(f, ml.read(lz.at(z, (a + k : U32)), a, b, k))
836 case False{}:
837 (z, (k - 1 : U32))
838
839# Chain walk at i: candidate c (position + 1), the longest match so far, and whether to go on.
840type Ch is Type:
841 Ch{z: Lz, i: U32, c: U32, max: U32, blen: U32, bdist: U32, go: Bool}
842
843# RFC 1951 §3.2.5: a distance is at most 32768.
844def ch.ok(+i: U32, +c: U32, +max: U32, +blen: U32) -> Bool:
845 Bool.and(Bool.and(U32.is_lt(0, c), U32.is_lt((i - c : U32), 32768)), U32.is_lt(blen, max))
846
847def ch.next(r: Array<U32> & U32, src: Array<U32>, head: Array<U32>, +i: U32, +max: U32, +blen: U32, +bdist: U32) -> Ch:
848 (prev, +c) = r
849 Ch{Lz{src, head, prev}, i, c, max, blen, bdist, ch.ok(i, c, max, blen)}
850
851def ch.best(r: Lz & U32, +i: U32, +p: U32, +max: U32, +blen: U32, +bdist: U32) -> Ch:
852 (z, +len) = r
853 Lz{src, head, prev} = z
854 +more = U32.is_lt(blen, len)
855 ch.next(Array.get(U32, prev, U32.and(p, 32767)), src, head, i, max, Bool.pick(U32, more, len, blen), Bool.pick(U32, more, (i - p : U32), bdist))
856
857def ch.go(fuel: Nat, st: Ch) -> Ch:
858 match fuel:
859 case 0n:
860 st
861 case 1n+f:
862 Ch{z, +i, +c, +max, +blen, +bdist, go} = st
863 match go:
864 case True{}:
865 +p = (c - 1 : U32)
866 ch.go(f, ch.best(ml.go(bits(max), Ml{z, i, p, 0, True{}}), i, p, max, blen, bdist))
867 case False{}:
868 Ch{z, i, c, max, blen, bdist, False{}}
869
870# Encoder: match finder, bit writer, position, input length, and whether bytes are left.
871type Es is Type:
872 Es{z: Lz, w: Bits.Writer, i: U32, n: U32, more: Bool}
873
874def es.lit.of(r: Lz & U32, w: Bits.Writer, +i: U32, +n: U32) -> Es:
875 (z, +c) = r
876 +j = (i + 1 : U32)
877 Es{z, em.lit(w, c), j, n, U32.is_lt(j, n)}
878
879def es.lit(z: Lz, w: Bits.Writer, +i: U32, +n: U32) -> Es:
880 es.lit.of(lz.at(z, i), w, i, n)
881
882def ins.one(ok: Bool, z: Lz, +j: U32) -> Lz:
883 match ok:
884 case True{}:
885 lz.drop(lz.insert(z, j))
886 case False{}:
887 z
888
889# Positions inside a match join their chains too, when three bytes remain.
890def ins.go(k: Nat, z: Lz, +j: U32, +n: U32) -> Lz:
891 match k:
892 case 0n:
893 z
894 case 1n+f:
895 ins.go(f, ins.one(U32.is_le((j + 3 : U32), n), z, j), (j + 1 : U32), n)
896
897def es.emit(hit: Bool, z: Lz, w: Bits.Writer, +i: U32, +n: U32, +blen: U32, +bdist: U32) -> Es:
898 match hit:
899 case True{}:
900 +j = (i + blen : U32)
901 Es{ins.go(bits((blen - 1 : U32)), z, (i + 1 : U32), n), em.match(w, blen, bdist), j, n, U32.is_lt(j, n)}
902 case False{}:
903 es.lit(z, w, i, n)
904
905def es.pick(st: Ch, w: Bits.Writer, +n: U32) -> Es:
906 Ch{z, +i, c, max, +blen, +bdist, go} = st
907 es.emit(U32.is_le(3, blen), z, w, i, n, blen, bdist)
908
909# ponytail: greedy parse, 32 chain steps; lazy matching would compress text further.
910def es.chain(r: Lz & U32, w: Bits.Writer, +i: U32, +n: U32) -> Es:
911 (z, +c) = r
912 +room = (n - i : U32)
913 +max = Bool.pick(U32, U32.is_lt(room, 258), room, 258)
914 es.pick(ch.go(32n, Ch{z, i, c, max, 0, 0, ch.ok(i, c, max, 0)}), w, n)
915
916def es.find(short: Bool, z: Lz, w: Bits.Writer, +i: U32, +n: U32) -> Es:
917 match short:
918 case True{}:
919 es.lit(z, w, i, n)
920 case False{}:
921 es.chain(lz.insert(z, i), w, i, n)
922
923# Each step consumes at least one byte, so n steps finish.
924def es.go(fuel: Nat, st: Es) -> Es:
925 match fuel:
926 case 0n:
927 st
928 case 1n+f:
929 Es{z, w, +i, +n, more} = st
930 match more:
931 case True{}:
932 es.go(f, es.find(U32.is_lt((n - i : U32), 3), z, w, i, n))
933 case False{}:
934 Es{z, w, i, n, False{}}
935
936def es.out(st: Es) -> Bits.Writer:
937 Es{z, w, i, n, more} = st
938 Bits.Writer.align(em.lit(w, 256))
939
940# One final fixed-Huffman block (BFINAL = 1, BTYPE = 01) after what w holds, padded to a byte.
941def deflate.into(w: Bits.Writer, b: Bytes.Bytes) -> Bits.Writer:
942 Bytes.Bytes{+n, src} = b
943 es.out(es.go(bits(n), Es{Lz{src, Array.new(U32, 15n, 0), Array.new(U32, 15n, 0)}, Bits.Writer.lsb(w, 3, 3), 0, n, U32.is_lt(0, n)}))
944
945# Raw DEFLATE.
946def deflate(b: Bytes.Bytes) -> Bytes.Bytes:
947 Bits.Writer.finish(deflate.into(Bits.Writer.new(), b))
948
949def gz.put(r: Bytes.Bytes & U32) -> Bytes.Bytes:
950 (b, +crc) = r
951 Bytes.Bytes{+n, buf} = b
952 head = Bits.Writer.lsb(Bits.Writer.lsb(Bits.Writer.lsb(Bits.Writer.new(), 32, 559903), 32, 0), 16, 65280)
953 Bits.Writer.finish(Bits.Writer.lsb(Bits.Writer.lsb(deflate.into(head, Bytes.Bytes{n, buf}), 32, crc), 32, n))
954
955# One gzip member (RFC 1952): no flags, mtime 0, OS unknown.
956def gzip(b: Bytes.Bytes) -> Bytes.Bytes:
957 gz.put(Hash.crc32(b))
958
959def zl.put(r: Bytes.Bytes & U32) -> Bytes.Bytes:
960 (b, +a) = r
961 Bits.Writer.finish(Bits.Writer.lsb(deflate.into(Bits.Writer.lsb(Bits.Writer.new(), 16, 376), b), 32, Bytes.bswap(a)))
962
963# RFC 1950: CMF 0x78 (32 KiB window), FLG 0x01 (fastest), then DEFLATE, then Adler-32, big-endian.
964def zlib(b: Bytes.Bytes) -> Bytes.Bytes:
965 zl.put(Hash.adler32(b))
966
967
968# The C libraries, through packed words at the effect boundary. Call the Bytes wrappers below.
969def zstd.words(max: U32, len: U32, words: Array<U32>) ->
970 IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
971 import "./effs/zlib.c"
972 import "./effs/zlib.js"
973
974def inflate.words(max: U32, len: U32, words: Array<U32>) ->
975 IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
976 import "./effs/zlib.c"
977 import "./effs/zlib.js"
978
979def inflate.raw.words(max: U32, len: U32, words: Array<U32>) ->
980 IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
981 import "./effs/zlib.c"
982 import "./effs/zlib.js"
983
984def gzip.words(len: U32, words: Array<U32>) ->
985 IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
986 import "./effs/zlib.c"
987 import "./effs/zlib.js"
988
989def brotli.words(max: U32, len: U32, words: Array<U32>) ->
990 IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
991 import "./effs/zlib.c"
992 import "./effs/zlib.js"
993
994def words.got(r: Result<&1, &1, U32 & String, U32 & Array<U32>>) -> Result<&1, &1, U32 & String, Bytes.Bytes>:
995 match r:
996 case Fail{e}:
997 Fail{e}
998 case Done{(+len, buf)}:
999 Done{Bytes.Bytes{len, buf}}
1000
1001def words.run(~eff: U32 -> U32 -> Array<U32> -> IO(Result<&1, &1, U32 & String, U32 & Array<U32>>), max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1002 Bytes.Bytes{+len, buf} = b
1003 do IO<Result<&1, &1, U32 & String, Bytes.Bytes>>:
1004 r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- eff(max, len, buf)
1005 return words.got(r)
1006
1007# gzip, zlib, or raw DEFLATE data through libz, selected from the first two bytes. Every gzip member is decoded in turn, as gzip -d does.
1008# Each decoder fails with EFBIG when the output passes max bytes, and ENOENT without its library.
1009def libz.inflate(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1010 words.run(~inflate.words, max, b)
1011
1012# One raw DEFLATE stream through libz. Trailing bytes, truncated input and output above max fail.
1013def libz.inflate.raw(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1014 words.run(~inflate.raw.words, max, b)
1015
1016# One gzip member at level 6 through libz.
1017def libz.gzip(b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1018 Bytes.Bytes{+len, buf} = b
1019 do IO<Result<&1, &1, U32 & String, Bytes.Bytes>>:
1020 r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- gzip.words(len, buf)
1021 return words.got(r)
1022
1023# Zstandard frames (RFC 8878) through libzstd.
1024def zstd(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1025 words.run(~zstd.words, max, b)
1026
1027# Brotli (RFC 7932) through libbrotlidec.
1028def brotli(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1029 words.run(~brotli.words, max, b)
1030
1031# A live native decoder. Call dec.finish even after a failed feed to release it.
1032type Decoder is Type:
1033 Decoder{id: U32}
1034
1035def dec.open(kind: U32) -> IO(Result<&1, &1, U32 & String, U32>):
1036 import "./effs/zlib.c"
1037 import "./effs/zlib.js"
1038
1039def dec.new.got(r: Result<&1, &1, U32 & String, U32>) -> Result<&1, &1, U32 & String, Decoder>:
1040 match r:
1041 case Fail{e}:
1042 Fail{e}
1043 case Done{+id}:
1044 Done{Decoder{id}}
1045
1046def dec.new(+kind: U32) -> IO(Result<&1, &1, U32 & String, Decoder>):
1047 do IO<Result<&1, &1, U32 & String, Decoder>>:
1048 r : Result<&1, &1, U32 & String, U32> <- dec.open(kind)
1049 return dec.new.got(r)
1050
1051def inflate.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1052 dec.new(0)
1053
1054def brotli.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1055 dec.new(1)
1056
1057def zstd.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1058 dec.new(2)
1059
1060def dec.feed(id: U32, max: U32, len: U32, words: Array<U32>) ->
1061 IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1062 import "./effs/zlib.c"
1063 import "./effs/zlib.js"
1064
1065# The output of one chunk of input. max caps this call, not the total output of the stream.
1066def dec.push(d: Decoder, max: U32, b: Bytes.Bytes) ->
1067 IO(Decoder & Result<&1, &1, U32 & String, Bytes.Bytes>):
1068 Decoder{+id} = d
1069 Bytes.Bytes{+len, buf} = b
1070 do IO<Decoder & Result<&1, &1, U32 & String, Bytes.Bytes>>:
1071 r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- dec.feed(id, max, len, buf)
1072 return (Decoder{id}, words.got(r))
1073
1074def dec.finish.id(id: U32) -> IO(Result<&1, &1, U32 & String, Unit>):
1075 import "./effs/zlib.c"
1076 import "./effs/zlib.js"
1077
1078# Finish validates the end marker and always releases the decoder.
1079def dec.finish(d: Decoder) -> IO(Result<&1, &1, U32 & String, Unit>):
1080 Decoder{+id} = d
1081 dec.finish.id(id)