zlib.bend

bend-kit-zlib@0.5.1.0 · 1,131 lines · 196 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.1/bits.bend as Bits
5import bend-kit-hash@0.3.0.2/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
617# One member's output, the input back, and the first byte after its trailer.
618type Member is Type:
619  Member{out: Bytes.Bytes, src: Bytes.Bytes, next: U32}
620
621def gz.keep(ok: Bool, out: Bytes.Bytes, src: Bytes.Bytes, +next: U32) -> Maybe<&1, Member>:
622  match ok:
623    case True{}:
624      Some{Member{out, src, next}}
625    case False{}:
626      None{}
627
628def gz.isize(+ok: Bool, +n: U32, +next: U32, out: Bytes.Bytes, r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Member>:
629  (src, z) = r
630  gz.keep(Bool.and(ok, holds(z, n)), out, src, next)
631
632def gz.crc(r: Bytes.Bytes & U32, +n: U32, +at: U32, c: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Member>:
633  (out, +crc) = r
634  (src, m) = c
635  gz.isize(holds(m, crc), n, (at + 8 : U32), out, Bytes.get.u32le(src, (at + 4 : U32)))
636
637def gz.trail(m: Maybe<&1, Inflated>) -> Maybe<&1, Member>:
638  match m:
639    case None{}:
640      None{}
641    case Some{Inflated{out, src, +at}}:
642      Bytes.Bytes{+n, buf} = out
643      gz.crc(Hash.crc32(Bytes.Bytes{n, buf}), n, at, Bytes.get.u32le(src, at))
644
645def gz.body(r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Member>:
646  (b, m) = r
647  match m:
648    case None{}:
649      None{}
650    case Some{+off}:
651      gz.trail(inflate.at(b, off))
652
653def gz.flags(+f: U32, +p: U32, b: Bytes.Bytes) -> Maybe<&1, Member>:
654  gz.body(gz.fhcrc(flag(f, 2), gz.fstr(flag(f, 16), gz.fstr(flag(f, 8), gz.fextra(flag(f, 4), (b, Some{(p + 10 : U32)}))))))
655
656def gz.magic(ok: Bool, +f: U32, +p: U32, b: Bytes.Bytes) -> Maybe<&1, Member>:
657  match ok:
658    case True{}:
659      gz.flags(f, p, b)
660    case False{}:
661      None{}
662
663# ID1 31, ID2 139, CM 8 (DEFLATE), then FLG.
664def gz.head(+p: U32, r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Member>:
665  (b, m) = r
666  match m:
667    case None{}:
668      None{}
669    case Some{+w}:
670      gz.magic(U32.is_eq(U32.and(w, 16777215), 559903), U32.shrn(w, 24n), p, b)
671
672# The member that starts at byte p.
673def gz.member(b: Bytes.Bytes, +p: U32) -> Maybe<&1, Member>:
674  gz.head(p, Bytes.get.u32le(b, p))
675
676# RFC 1952 §2.2: members follow each other until the input ends.
677type Gz is Type:
678  GzMore{acc: Bytes.Bytes, src: Bytes.Bytes, at: U32}
679  GzDone{out: Bytes.Bytes}
680  GzBad{}
681
682def gz.more(more: Bool, acc: Bytes.Bytes, src: Bytes.Bytes, +at: U32) -> Gz:
683  match more:
684    case True{}:
685      GzMore{acc, src, at}
686    case False{}:
687      GzDone{acc}
688
689def gz.step(m: Maybe<&1, Member>, acc: Bytes.Bytes) -> Gz:
690  match m:
691    case None{}:
692      GzBad{}
693    case Some{Member{out, src, +next}}:
694      Bytes.Bytes{+len, buf} = src
695      gz.more(U32.is_lt(next, len), Bytes.append(acc, out), Bytes.Bytes{len, buf}, next)
696
697# Each member takes at least 18 bytes, so one step per byte suffices.
698def gz.go(k: Nat, st: Gz) -> Maybe<&1, Bytes.Bytes>:
699  match k:
700    case 0n:
701      None{}
702    case 1n+f:
703      match st:
704        case GzMore{acc, src, +at}:
705          gz.go(f, gz.step(gz.member(src, at), acc))
706        case GzDone{out}:
707          Some{out}
708        case GzBad{}:
709          None{}
710
711# Every gzip member, concatenated; each CRC-32 and ISIZE must match. None: malformed, cut short, corrupt, or junk after a member.
712def gunzip(b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
713  Bytes.Bytes{+len, buf} = b
714  gz.go(Nat.add(bits(len), 1n), GzMore{Bytes.Bytes{0, Array.new(U32, 0n, 0)}, Bytes.Bytes{len, buf}, 0})
715
716# RFC 1950: CMF and FLG, then DEFLATE, then Adler-32, big-endian.
717def zl.sum(r: Bytes.Bytes & U32, c: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
718  (out, +a) = r
719  (src, m) = c
720  keep(holds(m, a), out)
721
722def zl.trail(m: Maybe<&1, Inflated>) -> Maybe<&1, Bytes.Bytes>:
723  match m:
724    case None{}:
725      None{}
726    case Some{Inflated{out, src, +at}}:
727      zl.sum(Hash.adler32(out), Bytes.get.u32be(src, at))
728
729def zl.ok(+cmf: U32, +flg: U32) -> Bool:
730  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))))
731
732def zl.go(ok: Bool, b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
733  match ok:
734    case True{}:
735      zl.trail(inflate.at(b, 2))
736    case False{}:
737      None{}
738
739def zl.head(r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
740  (b, m) = r
741  match m:
742    case None{}:
743      None{}
744    case Some{+h}:
745      zl.go(zl.ok(U32.shrn(h, 8n), U32.and(h, 255)), b)
746
747def unzlib(b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
748  zl.head(Bytes.get.u16be(b, 0))
749
750# DEFLATE encoding: LZ77 over hash chains, then one final fixed-Huffman block (RFC 1951 §3.2.6).
751# ponytail: fixed Huffman only; dynamic trees would cut text output further.
752
753def bw.code(w: Bits.Writer, cl: U32 & U32) -> Bits.Writer:
754  (+c, +l) = cl
755  Bits.Writer.lsb(w, l, Bits.rev(bits(l), c, 0))
756
757# RFC 1951 §3.2.6: the fixed code of literal/length symbol s, and its length.
758def fx.hi(+s: U32, lo: Bool) -> U32 & U32:
759  match lo:
760    case True{}:
761      ((s - 256 : U32), 7)
762    case False{}:
763      ((s - 88 : U32), 8)
764
765def fx.mid(+s: U32, lo: Bool) -> U32 & U32:
766  match lo:
767    case True{}:
768      ((s + 256 : U32), 9)
769    case False{}:
770      fx.hi(s, U32.is_lt(s, 280))
771
772def fx.low(+s: U32, lo: Bool) -> U32 & U32:
773  match lo:
774    case True{}:
775      ((s + 48 : U32), 8)
776    case False{}:
777      fx.mid(s, U32.is_lt(s, 256))
778
779def fx.lit(+s: U32) -> U32 & U32:
780  fx.low(s, U32.is_lt(s, 144))
781
782# The last index whose base is at most v, with that base and its extra-bit count; bases ascend.
783type Cx is Data:
784  Cx{i: U32, base: U32, extra: U32}
785
786def cx.go(bs: List<&2, U32>, es: List<&2, U32>, +v: U32, +i: U32, +best: Cx) -> Cx:
787  match bs:
788    case Nil{}:
789      best
790    case Con{+b, bt}:
791      match es:
792        case Nil{}:
793          best
794        case Con{+e, et}:
795          cx.go(bt, et, v, (i + 1 : U32), Bool.pick(Cx, U32.is_le(b, v), Cx{i, b, e}, best))
796
797
798def em.len(w: Bits.Writer, +len: U32, c: Cx) -> Bits.Writer:
799  Cx{+i, +b, +e} = c
800  Bits.Writer.lsb(bw.code(w, fx.lit((i + 257 : U32))), e, (len - b : U32))
801
802def em.dist(w: Bits.Writer, +d: U32, c: Cx) -> Bits.Writer:
803  Cx{+i, +b, +e} = c
804  Bits.Writer.lsb(Bits.Writer.lsb(w, 5, Bits.rev(5n, i, 0)), e, (d - b : U32))
805
806def em.match(w: Bits.Writer, +len: U32, +d: U32) -> Bits.Writer:
807  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}))
808
809def em.lit(w: Bits.Writer, +c: U32) -> Bits.Writer:
810  bw.code(w, fx.lit(c))
811
812# Match finder: the input bytes, packed, the newest position + 1 per hash, and per position the previous one with its hash (0: none).
813type Lz is Type:
814  Lz{src: Array<U32>, head: Array<U32>, prev: Array<U32>}
815
816def lz.at.of(r: Array<U32> & U32, head: Array<U32>, prev: Array<U32>) -> Lz & U32:
817  (src, v) = r
818  (Lz{src, head, prev}, v)
819
820def lz.at(z: Lz, +i: U32) -> Lz & U32:
821  Lz{src, head, prev} = z
822  lz.at.of(Bytes.peek(src, i), head, prev)
823
824def lz.drop(r: Lz & U32) -> Lz:
825  (z, v) = r
826  z
827
828def lz.h3(r: Lz & U32, +a: U32, +b: U32) -> Lz & U32:
829  (z, +c) = r
830  (z, U32.and(U32.xor(U32.xor(U32.shln(a, 10n), U32.shln(b, 5n)), c), 32767))
831
832def lz.h2(r: Lz & U32, +i: U32, +a: U32) -> Lz & U32:
833  (z, +b) = r
834  lz.h3(lz.at(z, (i + 2 : U32)), a, b)
835
836def lz.h1(r: Lz & U32, +i: U32) -> Lz & U32:
837  (z, +a) = r
838  lz.h2(lz.at(z, (i + 1 : U32)), i, a)
839
840def lz.hash(z: Lz, +i: U32) -> Lz & U32:
841  lz.h1(lz.at(z, i), i)
842
843def lz.link(r: Array<U32> & U32, +i: U32, +h: U32, src: Array<U32>, prev: Array<U32>) -> Lz & U32:
844  (head, +old) = r
845  (Lz{src, Array.set(U32, head, h, (i + 1 : U32)), Array.set(U32, prev, U32.and(i, 32767), old)}, old)
846
847def lz.ins.of(r: Lz & U32, +i: U32) -> Lz & U32:
848  (z, +h) = r
849  Lz{src, head, prev} = z
850  lz.link(Array.get(U32, head, h), i, h, src, prev)
851
852# Links position i into the chain for its next three bytes; answers the chain's previous head.
853def lz.insert(z: Lz, +i: U32) -> Lz & U32:
854  lz.ins.of(lz.hash(z, i), i)
855
856# Match length: bytes at a + k and b + k compared so far, and whether the last pair was equal.
857type Ml is Type:
858  Ml{z: Lz, a: U32, b: U32, k: U32, eq: Bool}
859
860def ml.cmp(r: Lz & U32, +a: U32, +b: U32, +k: U32, +x: U32) -> Ml:
861  (z, +y) = r
862  Ml{z, a, b, (k + 1 : U32), U32.is_eq(x, y)}
863
864def ml.read(r: Lz & U32, +a: U32, +b: U32, +k: U32) -> Ml:
865  (z, +x) = r
866  ml.cmp(lz.at(z, (b + k : U32)), a, b, k, x)
867
868def ml.len(+k: U32, eq: Bool) -> U32:
869  match eq:
870    case True{}:
871      k
872    case False{}:
873      (k - 1 : U32)
874
875# Counts equal bytes from a and from b, up to fuel.
876def ml.go(fuel: Nat, st: Ml) -> Lz & U32:
877  match fuel:
878    case 0n:
879      Ml{z, a, b, +k, eq} = st
880      (z, ml.len(k, eq))
881    case 1n+f:
882      Ml{z, +a, +b, +k, eq} = st
883      match eq:
884        case True{}:
885          ml.go(f, ml.read(lz.at(z, (a + k : U32)), a, b, k))
886        case False{}:
887          (z, (k - 1 : U32))
888
889# Chain walk at i: candidate c (position + 1), the longest match so far, and whether to go on.
890type Ch is Type:
891  Ch{z: Lz, i: U32, c: U32, max: U32, blen: U32, bdist: U32, go: Bool}
892
893# RFC 1951 §3.2.5: a distance is at most 32768.
894def ch.ok(+i: U32, +c: U32, +max: U32, +blen: U32) -> Bool:
895  Bool.and(Bool.and(U32.is_lt(0, c), U32.is_lt((i - c : U32), 32768)), U32.is_lt(blen, max))
896
897def ch.next(r: Array<U32> & U32, src: Array<U32>, head: Array<U32>, +i: U32, +max: U32, +blen: U32, +bdist: U32) -> Ch:
898  (prev, +c) = r
899  Ch{Lz{src, head, prev}, i, c, max, blen, bdist, ch.ok(i, c, max, blen)}
900
901def ch.best(r: Lz & U32, +i: U32, +p: U32, +max: U32, +blen: U32, +bdist: U32) -> Ch:
902  (z, +len) = r
903  Lz{src, head, prev} = z
904  +more = U32.is_lt(blen, len)
905  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))
906
907def ch.go(fuel: Nat, st: Ch) -> Ch:
908  match fuel:
909    case 0n:
910      st
911    case 1n+f:
912      Ch{z, +i, +c, +max, +blen, +bdist, go} = st
913      match go:
914        case True{}:
915          +p = (c - 1 : U32)
916          ch.go(f, ch.best(ml.go(bits(max), Ml{z, i, p, 0, True{}}), i, p, max, blen, bdist))
917        case False{}:
918          Ch{z, i, c, max, blen, bdist, False{}}
919
920# Encoder: match finder, bit writer, position, input length, and whether bytes are left.
921type Es is Type:
922  Es{z: Lz, w: Bits.Writer, i: U32, n: U32, more: Bool}
923
924def es.lit.of(r: Lz & U32, w: Bits.Writer, +i: U32, +n: U32) -> Es:
925  (z, +c) = r
926  +j = (i + 1 : U32)
927  Es{z, em.lit(w, c), j, n, U32.is_lt(j, n)}
928
929def es.lit(z: Lz, w: Bits.Writer, +i: U32, +n: U32) -> Es:
930  es.lit.of(lz.at(z, i), w, i, n)
931
932def ins.one(ok: Bool, z: Lz, +j: U32) -> Lz:
933  match ok:
934    case True{}:
935      lz.drop(lz.insert(z, j))
936    case False{}:
937      z
938
939# Positions inside a match join their chains too, when three bytes remain.
940def ins.go(k: Nat, z: Lz, +j: U32, +n: U32) -> Lz:
941  match k:
942    case 0n:
943      z
944    case 1n+f:
945      ins.go(f, ins.one(U32.is_le((j + 3 : U32), n), z, j), (j + 1 : U32), n)
946
947def es.emit(hit: Bool, z: Lz, w: Bits.Writer, +i: U32, +n: U32, +blen: U32, +bdist: U32) -> Es:
948  match hit:
949    case True{}:
950      +j = (i + blen : U32)
951      Es{ins.go(bits((blen - 1 : U32)), z, (i + 1 : U32), n), em.match(w, blen, bdist), j, n, U32.is_lt(j, n)}
952    case False{}:
953      es.lit(z, w, i, n)
954
955def es.pick(st: Ch, w: Bits.Writer, +n: U32) -> Es:
956  Ch{z, +i, c, max, +blen, +bdist, go} = st
957  es.emit(U32.is_le(3, blen), z, w, i, n, blen, bdist)
958
959# ponytail: greedy parse, 32 chain steps; lazy matching would compress text further.
960def es.chain(r: Lz & U32, w: Bits.Writer, +i: U32, +n: U32) -> Es:
961  (z, +c) = r
962  +room = (n - i : U32)
963  +max = Bool.pick(U32, U32.is_lt(room, 258), room, 258)
964  es.pick(ch.go(32n, Ch{z, i, c, max, 0, 0, ch.ok(i, c, max, 0)}), w, n)
965
966def es.find(short: Bool, z: Lz, w: Bits.Writer, +i: U32, +n: U32) -> Es:
967  match short:
968    case True{}:
969      es.lit(z, w, i, n)
970    case False{}:
971      es.chain(lz.insert(z, i), w, i, n)
972
973# Each step consumes at least one byte, so n steps finish.
974def es.go(fuel: Nat, st: Es) -> Es:
975  match fuel:
976    case 0n:
977      st
978    case 1n+f:
979      Es{z, w, +i, +n, more} = st
980      match more:
981        case True{}:
982          es.go(f, es.find(U32.is_lt((n - i : U32), 3), z, w, i, n))
983        case False{}:
984          Es{z, w, i, n, False{}}
985
986def es.out(st: Es) -> Bits.Writer:
987  Es{z, w, i, n, more} = st
988  Bits.Writer.align(em.lit(w, 256))
989
990# One final fixed-Huffman block (BFINAL = 1, BTYPE = 01) after what w holds, padded to a byte.
991def deflate.into(w: Bits.Writer, b: Bytes.Bytes) -> Bits.Writer:
992  Bytes.Bytes{+n, src} = b
993  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)}))
994
995# Raw DEFLATE.
996def deflate(b: Bytes.Bytes) -> Bytes.Bytes:
997  Bits.Writer.finish(deflate.into(Bits.Writer.new(), b))
998
999def gz.put(r: Bytes.Bytes & U32) -> Bytes.Bytes:
1000  (b, +crc) = r
1001  Bytes.Bytes{+n, buf} = b
1002  head = Bits.Writer.lsb(Bits.Writer.lsb(Bits.Writer.lsb(Bits.Writer.new(), 32, 559903), 32, 0), 16, 65280)
1003  Bits.Writer.finish(Bits.Writer.lsb(Bits.Writer.lsb(deflate.into(head, Bytes.Bytes{n, buf}), 32, crc), 32, n))
1004
1005# One gzip member (RFC 1952): no flags, mtime 0, OS unknown.
1006def gzip(b: Bytes.Bytes) -> Bytes.Bytes:
1007  gz.put(Hash.crc32(b))
1008
1009def zl.put(r: Bytes.Bytes & U32) -> Bytes.Bytes:
1010  (b, +a) = r
1011  Bits.Writer.finish(Bits.Writer.lsb(deflate.into(Bits.Writer.lsb(Bits.Writer.new(), 16, 376), b), 32, Bytes.bswap(a)))
1012
1013# RFC 1950: CMF 0x78 (32 KiB window), FLG 0x01 (fastest), then DEFLATE, then Adler-32, big-endian.
1014def zlib(b: Bytes.Bytes) -> Bytes.Bytes:
1015  zl.put(Hash.adler32(b))
1016
1017
1018# The C libraries, through packed words at the effect boundary. Call the Bytes wrappers below.
1019def zstd.words(max: U32, len: U32, words: Array<U32>) ->
1020  IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1021  import "./effs/zlib.c"
1022  import "./effs/zlib.js"
1023
1024def inflate.words(max: U32, len: U32, words: Array<U32>) ->
1025  IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1026  import "./effs/zlib.c"
1027  import "./effs/zlib.js"
1028
1029def inflate.raw.words(max: U32, len: U32, words: Array<U32>) ->
1030  IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1031  import "./effs/zlib.c"
1032  import "./effs/zlib.js"
1033
1034def gzip.words(len: U32, words: Array<U32>) ->
1035  IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1036  import "./effs/zlib.c"
1037  import "./effs/zlib.js"
1038
1039def brotli.words(max: U32, len: U32, words: Array<U32>) ->
1040  IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1041  import "./effs/zlib.c"
1042  import "./effs/zlib.js"
1043
1044def words.got(r: Result<&1, &1, U32 & String, U32 & Array<U32>>) -> Result<&1, &1, U32 & String, Bytes.Bytes>:
1045  match r:
1046    case Fail{e}:
1047      Fail{e}
1048    case Done{(+len, buf)}:
1049      Done{Bytes.Bytes{len, buf}}
1050
1051def 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>):
1052  Bytes.Bytes{+len, buf} = b
1053  do IO<Result<&1, &1, U32 & String, Bytes.Bytes>>:
1054    r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- eff(max, len, buf)
1055    return words.got(r)
1056
1057# 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.
1058# Each decoder fails with EFBIG when the output passes max bytes, and ENOENT without its library.
1059def libz.inflate(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1060  words.run(~inflate.words, max, b)
1061
1062# One raw DEFLATE stream through libz. Trailing bytes, truncated input and output above max fail.
1063def libz.inflate.raw(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1064  words.run(~inflate.raw.words, max, b)
1065
1066# One gzip member at level 6 through libz.
1067def libz.gzip(b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1068  Bytes.Bytes{+len, buf} = b
1069  do IO<Result<&1, &1, U32 & String, Bytes.Bytes>>:
1070    r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- gzip.words(len, buf)
1071    return words.got(r)
1072
1073# Zstandard frames (RFC 8878) through libzstd.
1074def zstd(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1075  words.run(~zstd.words, max, b)
1076
1077# Brotli (RFC 7932) through libbrotlidec.
1078def brotli(max: U32, b: Bytes.Bytes) -> IO(Result<&1, &1, U32 & String, Bytes.Bytes>):
1079  words.run(~brotli.words, max, b)
1080
1081# A live native decoder. Call dec.finish even after a failed feed to release it.
1082type Decoder is Type:
1083  Decoder{id: U32}
1084
1085def dec.open(kind: U32) -> IO(Result<&1, &1, U32 & String, U32>):
1086  import "./effs/zlib.c"
1087  import "./effs/zlib.js"
1088
1089def dec.new.got(r: Result<&1, &1, U32 & String, U32>) -> Result<&1, &1, U32 & String, Decoder>:
1090  match r:
1091    case Fail{e}:
1092      Fail{e}
1093    case Done{+id}:
1094      Done{Decoder{id}}
1095
1096def dec.new(+kind: U32) -> IO(Result<&1, &1, U32 & String, Decoder>):
1097  do IO<Result<&1, &1, U32 & String, Decoder>>:
1098    r : Result<&1, &1, U32 & String, U32> <- dec.open(kind)
1099    return dec.new.got(r)
1100
1101def inflate.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1102  dec.new(0)
1103
1104def brotli.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1105  dec.new(1)
1106
1107def zstd.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1108  dec.new(2)
1109
1110def dec.feed(id: U32, max: U32, len: U32, words: Array<U32>) ->
1111  IO(Result<&1, &1, U32 & String, U32 & Array<U32>>):
1112  import "./effs/zlib.c"
1113  import "./effs/zlib.js"
1114
1115# The output of one chunk of input. max caps this call, not the total output of the stream.
1116def dec.push(d: Decoder, max: U32, b: Bytes.Bytes) ->
1117  IO(Decoder & Result<&1, &1, U32 & String, Bytes.Bytes>):
1118  Decoder{+id} = d
1119  Bytes.Bytes{+len, buf} = b
1120  do IO<Decoder & Result<&1, &1, U32 & String, Bytes.Bytes>>:
1121    r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- dec.feed(id, max, len, buf)
1122    return (Decoder{id}, words.got(r))
1123
1124def dec.finish.id(id: U32) -> IO(Result<&1, &1, U32 & String, Unit>):
1125  import "./effs/zlib.c"
1126  import "./effs/zlib.js"
1127
1128# Finish validates the end marker and always releases the decoder.
1129def dec.finish(d: Decoder) -> IO(Result<&1, &1, U32 & String, Unit>):
1130  Decoder{+id} = d
1131  dec.finish.id(id)