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	# One member's output, the input back, and the first byte after its trailer.
618	type Member is Type:
619	  Member{out: Bytes.Bytes, src: Bytes.Bytes, next: U32}
620	
621	def 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	
628	def 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	
632	def 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	
637	def 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	
645	def 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	
653	def 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	
656	def 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.
664	def 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.
673	def 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.
677	type Gz is Type:
678	  GzMore{acc: Bytes.Bytes, src: Bytes.Bytes, at: U32}
679	  GzDone{out: Bytes.Bytes}
680	  GzBad{}
681	
682	def 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	
689	def 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.
698	def 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.
712	def 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.
717	def 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	
722	def 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	
729	def 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	
732	def 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	
739	def 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	
747	def 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	
753	def 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.
758	def 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	
765	def 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	
772	def 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	
779	def 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.
783	type Cx is Data:
784	  Cx{i: U32, base: U32, extra: U32}
785	
786	def 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	
798	def 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	
802	def 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	
806	def 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	
809	def 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).
813	type Lz is Type:
814	  Lz{src: Array<U32>, head: Array<U32>, prev: Array<U32>}
815	
816	def 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	
820	def 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	
824	def lz.drop(r: Lz & U32) -> Lz:
825	  (z, v) = r
826	  z
827	
828	def 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	
832	def 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	
836	def 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	
840	def lz.hash(z: Lz, +i: U32) -> Lz & U32:
841	  lz.h1(lz.at(z, i), i)
842	
843	def 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	
847	def 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.
853	def 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.
857	type Ml is Type:
858	  Ml{z: Lz, a: U32, b: U32, k: U32, eq: Bool}
859	
860	def 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	
864	def 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	
868	def 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.
876	def 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.
890	type 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.
894	def 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	
897	def 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	
901	def 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	
907	def 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.
921	type Es is Type:
922	  Es{z: Lz, w: Bits.Writer, i: U32, n: U32, more: Bool}
923	
924	def 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	
929	def es.lit(z: Lz, w: Bits.Writer, +i: U32, +n: U32) -> Es:
930	  es.lit.of(lz.at(z, i), w, i, n)
931	
932	def 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.
940	def 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	
947	def 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	
955	def 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.
960	def 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	
966	def 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.
974	def 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	
986	def 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.
991	def 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.
996	def deflate(b: Bytes.Bytes) -> Bytes.Bytes:
997	  Bits.Writer.finish(deflate.into(Bits.Writer.new(), b))
998	
999	def 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.
1006	def gzip(b: Bytes.Bytes) -> Bytes.Bytes:
1007	  gz.put(Hash.crc32(b))
1008	
1009	def 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.
1014	def 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.
1019	def 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	
1024	def 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	
1029	def 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	
1034	def 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	
1039	def 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	
1044	def 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	
1051	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>):
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.
1059	def 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.
1063	def 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.
1067	def 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.
1074	def 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.
1078	def 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.
1082	type Decoder is Type:
1083	  Decoder{id: U32}
1084	
1085	def dec.open(kind: U32) -> IO(Result<&1, &1, U32 & String, U32>):
1086	  import "./effs/zlib.c"
1087	  import "./effs/zlib.js"
1088	
1089	def 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	
1096	def 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	
1101	def inflate.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1102	  dec.new(0)
1103	
1104	def brotli.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1105	  dec.new(1)
1106	
1107	def zstd.new() -> IO(Result<&1, &1, U32 & String, Decoder>):
1108	  dec.new(2)
1109	
1110	def 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.
1116	def 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	
1124	def 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.
1129	def dec.finish(d: Decoder) -> IO(Result<&1, &1, U32 & String, Unit>):
1130	  Decoder{+id} = d
1131	  dec.finish.id(id)