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
2	import Base
3	import bend-kit-bytes@0.3.3.0/bytes.bend as Bytes
4	import bend-kit-bits@0.1.0.1/bits.bend as Bits
5	import bend-kit-hash@0.3.0.2/hash.bend as Hash
6	
7	def 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.
11	type Br is Type:
12	  Br{r: Bits.Reader, bad: Bool}
13	
14	def 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	
22	def 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.
27	def 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	
35	def 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.
40	def br.align(b: Br) -> Br:
41	  Br{r, bad} = b
42	  Br{Bits.Reader.align(r), bad}
43	
44	def 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	
51	def 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	
58	def 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	
69	def 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
81	def 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	
84	def 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	
87	def 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	
90	def 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
94	def 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	
97	def 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.
101	type Out is Type:
102	  Out{buf: Array<U32>, dep: U32, n: U32}
103	
104	def out.fits(+dep: U32, +want: U32) -> Bool:
105	  U32.is_le(want, U32.shln(4, bits(dep)))
106	
107	def 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	
119	def 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.
130	def 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	
135	def 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	
139	def out.size(o: Out) -> Out & U32:
140	  Out{buf, dep, +n} = o
141	  (Out{buf, dep, n}, n)
142	
143	def out.bytes(o: Out) -> Bytes.Bytes:
144	  Out{buf, dep, n} = o
145	  Bytes.Bytes{n, buf}
146	
147	type Mo is Type:
148	  MoHead{}
149	  MoCodes{lit: Bits.Huff, dist: Bits.Huff}
150	  MoDone{}
151	  MoBad{}
152	
153	type Is is Type:
154	  Is{br: Br, o: Out, mode: Mo, last: Bool}
155	
156	def inf.next(last: Bool) -> Mo:
157	  match last:
158	    case True{}:
159	      MoDone{}
160	    case False{}:
161	      MoHead{}
162	
163	def 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.
167	def sb.put(bv: Br & U32, o: Out) -> Br & Out:
168	  (b, +c) = bv
169	  (b, out.put(o, c))
170	
171	def 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	
179	def sb.done(st: Br & Out, +last: Bool) -> Is:
180	  (b, o) = st
181	  Is{b, o, inf.next(last), last}
182	
183	def 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	
190	def 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	
194	def 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	
198	def 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.
203	def 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	
206	def 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	
213	def cl.push(bv: Br & U32, acc: List<&2, U32>) -> Br & List<&2, U32>:
214	  (b, v) = bv
215	  (b, Con{v, acc})
216	
217	def cl.one(st: Br & List<&2, U32>) -> Br & List<&2, U32>:
218	  (b, acc) = st
219	  cl.push(br.take(b, 3), acc)
220	
221	def 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.
229	type Cd is Type:
230	  Cd{h: Bits.Huff, br: Br, acc: List<&2, U32>, n: U32, prev: U32, bad: Bool}
231	
232	def 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	
239	def 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	
244	def 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	
251	def 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	
258	def 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	
265	def 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	
272	def 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.
280	def 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	
283	def 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	
287	def 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.
295	def 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	
303	def 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	
310	def 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	
317	def 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	
324	def 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	
328	def 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	
335	def 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	
339	def 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	
343	def 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	
347	def dyn.hlit(bv: Br & U32) -> Br & Mo:
348	  (b, +hl) = bv
349	  dyn.hdist(br.take(b, 5), (hl + 257 : U32))
350	
351	def 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.
356	def 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	
360	def 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	
364	def 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.
372	def 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	
379	def 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	
383	def 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	
387	def 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.
395	def 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	
398	def 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	
402	def 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	
406	def 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	
414	def 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	
421	def 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.
429	def 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	
432	def 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	
436	def inf.dyn(bm: Br & Mo, o: Out, +last: Bool) -> Is:
437	  (b, m) = bm
438	  Is{b, o, m, last}
439	
440	def 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	
447	def 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	
454	def 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.
462	def 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.
468	def 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.
485	type Inflated is Type:
486	  Inflated{out: Bytes.Bytes, src: Bytes.Bytes, at: U32}
487	
488	def 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	
492	def 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	
500	def 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	
512	def 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.
521	def 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	
525	def 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.
533	def inflate(b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
534	  inflate.out(inflate.at(b, 0))
535	
536	def 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	
543	def 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	
550	def 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.
555	def 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	
563	def 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	
570	def 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	
578	def 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	
586	def 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.
594	def 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	
602	def 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	
609	def 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	def 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	
621	def 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	
626	def 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	
634	def 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	
642	def 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	
645	def 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.
653	def 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.
663	def 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.
667	def 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	
672	def 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	
679	def 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	
682	def 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	
689	def 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	
697	def 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	
703	def 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.
708	def 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	
715	def 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	
722	def 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	
729	def 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.
733	type Cx is Data:
734	  Cx{i: U32, base: U32, extra: U32}
735	
736	def 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	
748	def 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	
752	def 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	
756	def 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	
759	def 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).
763	type Lz is Type:
764	  Lz{src: Array<U32>, head: Array<U32>, prev: Array<U32>}
765	
766	def 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	
770	def 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	
774	def lz.drop(r: Lz & U32) -> Lz:
775	  (z, v) = r
776	  z
777	
778	def 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	
782	def 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	
786	def 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	
790	def lz.hash(z: Lz, +i: U32) -> Lz & U32:
791	  lz.h1(lz.at(z, i), i)
792	
793	def 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	
797	def 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.
803	def 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.
807	type Ml is Type:
808	  Ml{z: Lz, a: U32, b: U32, k: U32, eq: Bool}
809	
810	def 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	
814	def 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	
818	def 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.
826	def 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.
840	type 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.
844	def 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	
847	def 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	
851	def 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	
857	def 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.
871	type Es is Type:
872	  Es{z: Lz, w: Bits.Writer, i: U32, n: U32, more: Bool}
873	
874	def 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	
879	def es.lit(z: Lz, w: Bits.Writer, +i: U32, +n: U32) -> Es:
880	  es.lit.of(lz.at(z, i), w, i, n)
881	
882	def 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.
890	def 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	
897	def 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	
905	def 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.
910	def 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	
916	def 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.
924	def 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	
936	def 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.
941	def 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.
946	def deflate(b: Bytes.Bytes) -> Bytes.Bytes:
947	  Bits.Writer.finish(deflate.into(Bits.Writer.new(), b))
948	
949	def 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.
956	def gzip(b: Bytes.Bytes) -> Bytes.Bytes:
957	  gz.put(Hash.crc32(b))
958	
959	def 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.
964	def 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.
969	def 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	
974	def 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	
979	def 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	
984	def 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	
989	def 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	
994	def 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	
1001	def 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.
1009	def 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.
1013	def 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.
1017	def 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.
1024	def 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.
1028	def 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.
1032	type Decoder is Type:
1033	  Decoder{id: U32}
1034	
1035	def dec.open(kind: U32) -> IO(Result<&1, &1, U32 & String, U32>):
1036	  import "./effs/zlib.c"
1037	  import "./effs/zlib.js"
1038	
1039	def 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	
1046	def 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	
1051	def inflate.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1052	  dec.new(0)
1053	
1054	def brotli.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1055	  dec.new(1)
1056	
1057	def zstd.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1058	  dec.new(2)
1059	
1060	def 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.
1066	def 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	
1074	def 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.
1079	def dec.finish(d: Decoder) -> IO(Result<&1, &1, U32 & String, Unit>):
1080	  Decoder{+id} = d
1081	  dec.finish.id(id)