Meg's Mirrors

zig

1	//! Allocates statically ~224K (128K lookup, 96K tokens).
2	//!
3	//! The source of an `error.WriteFailed` is always the backing writer. After an
4	//! `error.WriteFailed`, the `.writer` becomes `.failing` and is unrecoverable.
5	//!
6	//! After `finish`, the writer also becomes `.failing` since the stream has
7	//! been finished. This behavior also applies to `Raw` and `Huffman`.
8
9	// Implementation details:
10	// A chained hash table is used to find matches. `drain` always preserves `flate.history_len`
11	// bytes to use as a history and avoids tokenizing the final bytes since they can be part of
12	// a longer match with unwritten bytes (unless it is a `flush`). The minimum match searched
13	// for is of length `seq_bytes`. If a match is made, a longer match is also checked for at
14	// the next byte (lazy matching) if the last match does not meet the `Options.lazy` threshold.
15	//
16	// Up to `block_token` tokens are accumalated in `buffered_tokens` and are outputted in
17	// `write_block` which determines the optimal block type and frequencies.
18
19	const builtin = @import("builtin");
20	const std = @import("std");
21	const mem = std.mem;
22	const math = std.math;
23	const assert = std.debug.assert;
24	const Io = std.Io;
25	const Writer = Io.Writer;
26
27	const Compress = @This();
28	const token = @import("token.zig");
29	const flate = @import("../flate.zig");
30
31	/// Until #104 is implemented, a ?u15 takes 4 bytes, which is unacceptable
32	/// as it doubles the size of this already massive structure.
33	///
34	/// Also, there are no `to` / `from` methods because LLVM 21 does not
35	/// optimize away the conversion from and to `?u15`.
36	const PackedOptionalU15 = packed struct(u16) {
37	value: u15,
38	is_null: bool,
39
40	pub fn int(p: PackedOptionalU15) u16 {
41	return @bitCast(p);
42	}
43
44	pub const null_bit: PackedOptionalU15 = .{ .value = 0, .is_null = true };
45	};
46
47	/// After `finish` is called, all vtable calls with result in `error.WriteFailed`.
48	writer: Writer,
49	history_len: u16,
50	history_end_unhashed: bool,
51	bit_writer: BitWriter,
52	buffered_tokens: struct {
53	/// List of `TokenBufferEntryHeader`s and their trailing data.
54	list: [@as(usize, block_tokens) * 3]u8,
55	pos: u32,
56	n: u16,
57	lit_freqs: [286]u16,
58	dist_freqs: [30]u16,
59
60	pub const empty: @This() = .{
61	.list = undefined,
62	.pos = 0,
63	.n = 0,
64	.lit_freqs = @splat(0),
65	.dist_freqs = @splat(0),
66	};
67	},
68	lookup: struct {
69	/// Indexes are the hashes of four-bytes sequences.
70	///
71	/// Values are the positions in `chain` of the previous four bytes with the same hash.
72	head: [1 << lookup_hash_bits]PackedOptionalU15,
73	/// Values are the non-zero number of bytes backwards in the history with the same hash.
74	///
75	/// The relationship of chain indexes and bytes relative to the latest history byte is
76	/// `chain_pos -% chain_index = history_index`.
77	chain: [32768]PackedOptionalU15,
78	/// The index in `chain` which is of the newest byte of the history.
79	chain_pos: u15,
80	},
81	container: flate.Container,
82	hasher: flate.Container.Hasher,
83	opts: Options,
84
85	const BitWriter = struct {
86	output: *Writer,
87	buffered: u7,
88	buffered_n: u3,
89
90	pub fn init(w: *Writer) BitWriter {
91	return .{
92	.output = w,
93	.buffered = 0,
94	.buffered_n = 0,
95	};
96	}
97
98	/// Asserts `bits` is zero-extended
99	pub fn write(b: *BitWriter, bits: u56, n: u6) Writer.Error!void {
100	assert(@as(u8, b.buffered) >> b.buffered_n == 0);
101	assert(@as(u57, bits) >> n == 0); // n may be 56 so u57 is needed
102	const combined = @shlExact(@as(u64, bits), b.buffered_n) | b.buffered;
103	const combined_bits = @as(u6, b.buffered_n) + n;
104
105	const out = try b.output.writableSliceGreedy(8);
106	mem.writeInt(u64, out[0..8], combined, .little);
107	b.output.advance(combined_bits / 8);
108
109	b.buffered_n = @truncate(combined_bits);
110	b.buffered = @intCast(combined >> (combined_bits - b.buffered_n));
111	}
112
113	/// Asserts one byte can be written to `b.output` without rebasing.
114	pub fn byteAlign(b: *BitWriter) void {
115	b.output.unusedCapacitySlice()[0] = b.buffered;
116	b.output.advance(@intFromBool(b.buffered_n != 0));
117	b.buffered = 0;
118	b.buffered_n = 0;
119	}
120
121	/// Byte align using only empty flate blocks
122	pub fn byteAlignBlocks(b: *BitWriter) Writer.Error!void {
123	if (b.buffered_n == 0) return;
124
125	// There are two methods to do this:
126	// 1. A store block (5 or 6 bytes)
127	// 2. Outputting empty 10-bit fixed blocks until aligned
128	//
129	// Fixed blocks advance the bit alignment by two, and so can only used for even numbers
130	// requiring a maximum of four bytes (three blocks = 30 bits) to which is always more
131	// efficient than store blocks.
132	if (b.buffered_n & 1 == 0) {
133	const splat = (8 - @as(u5, b.buffered_n)) >> 1;
134	const bits = splat * 10;
135	// fixed eos code is 0, so the only bits are for the block header
136	const pattern: u32 = BlockHeader.int(.{ .kind = .fixed, .final = false });
137	const splatted = ((pattern << 20) | (pattern << 10) | pattern) >> (30 - bits);
138	try b.write(splatted, bits);
139	} else {
140	try b.write(BlockHeader.int(.{ .kind = .stored, .final = false }), 3);
141	try b.output.rebase(0, 5);
142	b.byteAlign();
143	b.output.writeInt(u16, 0x0000, .little) catch unreachable;
144	b.output.writeInt(u16, 0xffff, .little) catch unreachable;
145	}
146
147	assert(b.buffered_n == 0);
148	}
149
150	pub fn writeClen(
151	b: *BitWriter,
152	hclen: u4,
153	clen_values: []u8,
154	clen_extra: []u8,
155	clen_codes: [19]u16,
156	clen_bits: [19]u4,
157	) Writer.Error!void {
158	// Write the first four clen entries seperately since they are always present,
159	// and writing them all at once takes too many bits.
160	try b.write(clen_bits[token.codegen_order[0]] |
161	@shlExact(@as(u6, clen_bits[token.codegen_order[1]]), 3) |
162	@shlExact(@as(u9, clen_bits[token.codegen_order[2]]), 6) |
163	@shlExact(@as(u12, clen_bits[token.codegen_order[3]]), 9), 12);
164
165	var i = hclen;
166	var clen_bits_table: u45 = 0;
167	while (i != 0) {
168	i -= 1;
169	clen_bits_table <<= 3;
170	clen_bits_table |= clen_bits[token.codegen_order[4..][i]];
171	}
172	try b.write(clen_bits_table, @as(u6, hclen) * 3);
173
174	for (clen_values, clen_extra) |value, extra| {
175	try b.write(
176	clen_codes[value] | @shlExact(@as(u16, extra), clen_bits[value]),
177	clen_bits[value] + @as(u3, switch (value) {
178	0...15 => 0,
179	16 => 2,
180	17 => 3,
181	18 => 7,
182	else => unreachable,
183	}),
184	);
185	}
186	}
187	};
188
189	/// Number of tokens to accumulate before outputing as a block.
190	/// The maximum value is `math.maxInt(u16) - 1` since one token is reserved for end-of-block.
191	const block_tokens: u16 = 1 << 15;
192	const lookup_hash_bits = 15;
193	const Hash = u16; // `@Int(.unsigned, lookup_hash_bits)` is not used due to worse optimization (with LLVM 21)
194	const seq_bytes = 3; // not intended to be changed
195	const Seq = @Int(.unsigned, seq_bytes * 8);
196
197	const TokenBufferEntryHeader = packed struct(u16) {
198	kind: enum(u1) {
199	/// Followed by non-zero `data` byte literals.
200	bytes,
201	/// Followed by the length as a byte
202	match,
203	},
204	data: u15,
205	};
206
207	const BlockHeader = packed struct(u3) {
208	final: bool,
209	kind: enum(u2) { stored, fixed, dynamic, _ },
210
211	pub fn int(h: BlockHeader) u3 {
212	return @bitCast(h);
213	}
214
215	pub const Dynamic = packed struct(u17) {
216	regular: BlockHeader,
217	hlit: u5,
218	hdist: u5,
219	hclen: u4,
220
221	pub fn int(h: Dynamic) u17 {
222	return @bitCast(h);
223	}
224	};
225	};
226
227	fn outputMatch(c: *Compress, dist: u15, len: u8) Writer.Error!void {
228	// This must come first. Instead of ensuring a full block is never left buffered,
229	// draining it is defered to allow end of stream to be indicated.
230	if (c.buffered_tokens.n == block_tokens) {
231	@branchHint(.unlikely); // LLVM 21 optimizes this branch as the more likely without
232	try c.writeBlock(false);
233	}
234	const header: TokenBufferEntryHeader = .{ .kind = .match, .data = dist };
235	c.buffered_tokens.list[c.buffered_tokens.pos..][0..2].* = @bitCast(header);
236	c.buffered_tokens.list[c.buffered_tokens.pos + 2] = len;
237	c.buffered_tokens.pos += 3;
238	c.buffered_tokens.n += 1;
239
240	c.buffered_tokens.lit_freqs[@as(usize, 257) + token.LenCode.fromVal(len).toInt()] += 1;
241	c.buffered_tokens.dist_freqs[token.DistCode.fromVal(dist).toInt()] += 1;
242	}
243
244	fn outputBytes(c: *Compress, bytes: []const u8) Writer.Error!void {
245	var remaining = bytes;
246	while (remaining.len != 0) {
247	if (c.buffered_tokens.n == block_tokens) {
248	@branchHint(.unlikely); // LLVM 21 optimizes this branch as the more likely without
249	try c.writeBlock(false);
250	}
251
252	const n = @min(remaining.len, block_tokens - c.buffered_tokens.n, math.maxInt(u15));
253	assert(n != 0);
254	const header: TokenBufferEntryHeader = .{ .kind = .bytes, .data = n };
255	c.buffered_tokens.list[c.buffered_tokens.pos..][0..2].* = @bitCast(header);
256	@memcpy(c.buffered_tokens.list[c.buffered_tokens.pos + 2 ..][0..n], remaining[0..n]);
257	c.buffered_tokens.pos += @as(u32, 2) + n;
258	c.buffered_tokens.n += n;
259
260	for (remaining[0..n]) |b| {
261	c.buffered_tokens.lit_freqs[b] += 1;
262	}
263	remaining = remaining[n..];
264	}
265	}
266
267	fn hash(x: u32) Hash {
268	return @intCast((x *% 0x9E3779B1) >> (32 - lookup_hash_bits));
269	}
270
271	/// Trades between speed and compression size.
272	///
273	/// Default paramaters are [taken from zlib]
274	/// (https://github.com/madler/zlib/blob/v1.3.1/deflate.c#L112)
275	pub const Options = struct {
276	/// Perform less lookups when a match of at least this length has been found.
277	good: u16,
278	/// Stop when a match of at least this length has been found.
279	nice: u16,
280	/// Don't attempt a lazy match find when a match of at least this length has been found.
281	lazy: u16,
282	/// Check this many previous locations with the same hash for longer matches.
283	chain: u16,
284
285	// zig fmt: off
286	pub const level_1: Options = .{ .good = 4, .nice = 8, .lazy = 0, .chain = 4 };
287	pub const level_2: Options = .{ .good = 4, .nice = 16, .lazy = 0, .chain = 8 };
288	pub const level_3: Options = .{ .good = 4, .nice = 32, .lazy = 0, .chain = 32 };
289	pub const level_4: Options = .{ .good = 4, .nice = 16, .lazy = 4, .chain = 16 };
290	pub const level_5: Options = .{ .good = 8, .nice = 32, .lazy = 16, .chain = 32 };
291	pub const level_6: Options = .{ .good = 8, .nice = 128, .lazy = 16, .chain = 128 };
292	pub const level_7: Options = .{ .good = 8, .nice = 128, .lazy = 32, .chain = 256 };
293	pub const level_8: Options = .{ .good = 32, .nice = 258, .lazy = 128, .chain = 1024 };
294	pub const level_9: Options = .{ .good = 32, .nice = 258, .lazy = 258, .chain = 4096 };
295	// zig fmt: on
296	pub const fastest = level_1;
297	pub const default = level_6;
298	pub const best = level_9;
299	};
300
301	/// It is asserted `buffer` is least `flate.max_window_len` bytes.
302	/// It is asserted `output` has a capacity of at least 8 bytes.
303	pub fn init(
304	output: *Writer,
305	buffer: []u8,
306	container: flate.Container,
307	opts: Options,
308	) Writer.Error!Compress {
309	assert(output.buffer.len > 8);
310	assert(buffer.len >= flate.max_window_len);
311
312	// note that disallowing some of these simplifies matching logic
313	assert(opts.chain != 0); // use `Huffman`; disallowing this simplies matching
314	assert(opts.good >= 3 and opts.nice >= 3); // a match will (usually) not be found
315	assert(opts.good <= 258 and opts.nice <= 258); // a longer match will not be found
316	assert(opts.lazy <= opts.nice); // a longer match will (usually) not be found
317	if (opts.good <= opts.lazy) assert(opts.chain >= 1 << 2); // chain can be reduced to zero
318
319	try output.writeAll(container.header());
320	return .{
321	.writer = .{
322	.buffer = buffer,
323	.vtable = &.{
324	.drain = drain,
325	.flush = flush,
326	.rebase = rebase,
327	},
328	},
329	.history_len = 0,
330	.history_end_unhashed = false,
331	.bit_writer = .init(output),
332	.buffered_tokens = .empty,
333	.lookup = .{
334	// init `value` is max so there is 0xff pattern
335	.head = @splat(.{ .value = math.maxInt(u15), .is_null = true }),
336	.chain = undefined,
337	.chain_pos = math.maxInt(u15),
338	},
339	.container = container,
340	.opts = opts,
341	.hasher = .init(container),
342	};
343	}
344
345	fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
346	errdefer w.* = .failing;
347	// There may have not been enough space in the buffer and the write was sent directly here.
348	// However, it is required that all data goes through the buffer to keep a history.
349	const data_n = w.buffer.len - w.end;
350	_ = w.fixedDrain(data, splat) catch {};
351	assert(w.end == w.buffer.len);
352	try rebaseInner(w, 0, 1, false, false);
353	return data_n;
354	}
355
356	fn flush(w: *Writer) Writer.Error!void {
357	errdefer w.* = .failing;
358	try rebaseInner(w, 0, w.buffer.len - flate.history_len, true, false);
359	const c: *Compress = @fieldParentPtr("writer", w);
360	try c.bit_writer.byteAlignBlocks();
361	}
362
363	pub fn finish(c: *Compress) Writer.Error!void {
364	defer c.writer = .failing;
365	try rebaseInner(&c.writer, 0, c.writer.buffer.len - flate.history_len, true, true);
366	try c.bit_writer.output.rebase(0, 1);
367	c.bit_writer.byteAlign();
368	try c.hasher.writeFooter(c.bit_writer.output);
369	}
370
371	fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
372	errdefer w.* = .failing;
373	return rebaseInner(w, preserve, capacity, false, false);
374	}
375
376	pub const rebase_min_preserve = flate.history_len;
377	pub const rebase_reserved_capacity = (token.max_length + 1) + seq_bytes;
378
379	fn rebaseInner(
380	w: *Writer,
381	preserve: usize,
382	capacity: usize,
383	is_flush: bool,
384	is_finish: bool,
385	) Writer.Error!void {
386	if (!is_flush) {
387	assert(@max(preserve, rebase_min_preserve) + (capacity + rebase_reserved_capacity) <= w.buffer.len);
388	} else {
389	// Preverse is not considered for `matching_end`
390	assert(preserve == 0 and capacity == w.buffer.len - flate.history_len);
391	}
392	if (is_finish) assert(is_flush);
393
394	const c: *Compress = @fieldParentPtr("writer", w);
395	const buffered = w.buffered();
396
397	const start: usize = c.history_len;
398	const hashable_len = buffered.len -| (seq_bytes - 1);
399	const matching_end: usize = if (!is_flush)
400	buffered.len - rebase_reserved_capacity - (preserve -| flate.history_len)
401	else
402	hashable_len;
403
404	var i = start;
405	var last_unmatched = i;
406	var seq: Seq = start_seq: {
407	if (c.history_end_unhashed) {
408	@branchHint(.unlikely);
409
410	assert(i != 0);
411	i -|= seq_bytes - 1;
412	var seq: Seq = mem.readInt(
413	@Int(.unsigned, (seq_bytes - 1) * 8),
414	w.buffer[i..][0 .. seq_bytes - 1],
415	.big,
416	);
417
418	while (i < @min(start, hashable_len)) {
419	seq <<= 8;
420	seq |= buffered[i + (seq_bytes - 1)];
421	c.addHash(i, hash(seq));
422	i += 1;
423	}
424
425	if (i < start) {
426	@branchHint(.unlikely);
427	i = start;
428	assert(i >= hashable_len);
429	assert(i >= matching_end);
430	assert(is_flush);
431	break :start_seq undefined; // Unused
432	}
433
434	c.history_end_unhashed = false;
435	break :start_seq seq;
436	}
437
438	if (i >= hashable_len) {
439	@branchHint(.unlikely);
440	assert(i >= matching_end);
441	assert(is_flush);
442	break :start_seq undefined; // Unused
443	}
444
445	break :start_seq mem.readInt(
446	@Int(.unsigned, (seq_bytes - 1) * 8),
447	buffered[i..][0 .. seq_bytes - 1],
448	.big,
449	);
450	};
451
452	while (i < matching_end) {
453	var match_start = i;
454	seq <<= 8;
455	seq |= buffered[i + (seq_bytes - 1)];
456	var match = c.matchAndAddHash(i, hash(seq), token.min_length - 1, c.opts.chain, c.opts.good);
457	i += 1;
458	if (match.len < token.min_length) continue;
459
460	var match_unadded = match.len - 1;
461	lazy: {
462	if (match.len >= c.opts.lazy) break :lazy;
463	if (match.len >= c.writer.buffered()[i..].len) {
464	@branchHint(.unlikely); // Only end of stream
465	break :lazy;
466	}
467
468	var chain = c.opts.chain;
469	var good = c.opts.good;
470	if (match.len >= good) {
471	chain >>= 2;
472	good = math.maxInt(u8); // Reduce only once
473	}
474
475	seq <<= 8;
476	seq |= buffered[i + (seq_bytes - 1)];
477	const lazy = c.matchAndAddHash(i, hash(seq), match.len, chain, good);
478	match_unadded -= 1;
479	i += 1;
480
481	if (lazy.len > match.len) {
482	match_start += 1;
483	match = lazy;
484	match_unadded = match.len - 1;
485	}
486	}
487
488	assert(i + match_unadded == match_start + match.len);
489	assert(mem.eql(
490	u8,
491	buffered[match_start..][0..match.len],
492	buffered[match_start - 1 - match.dist ..][0..match.len],
493	)); // This assert also seems to help codegen.
494
495	try c.outputBytes(buffered[last_unmatched..match_start]);
496	try c.outputMatch(@intCast(match.dist), @intCast(match.len - 3));
497	last_unmatched = match_start + match.len;
498
499	while (i < hashable_len) {
500	seq <<= 8;
501	seq |= buffered[i + (seq_bytes - 1)];
502	c.addHash(i, hash(seq));
503	i += 1;
504
505	match_unadded -= 1;
506	if (match_unadded == 0) break;
507	} else {
508	@branchHint(.unlikely);
509	assert(is_flush);
510	// `c.history_end_unhashed` is set down below
511	break;
512	}
513	assert(i == match_start + match.len);
514	}
515
516	if (is_flush) {
517	try c.outputBytes(buffered[last_unmatched..]);
518	c.hasher.update(buffered[start..]);
519
520	if (is_finish) {
521	try c.writeBlock(true);
522	return; // Other state does not need updated since the writer transitions to `.failing`
523	}
524
525	i = buffered.len;
526	c.history_end_unhashed = i != 0;
527
528	if (c.buffered_tokens.n != 0) {
529	try c.writeBlock(false);
530	}
531	} else {
532	try c.outputBytes(buffered[last_unmatched..i]);
533	c.hasher.update(buffered[start..i]);
534	}
535
536	c.history_len = @min(i, flate.history_len);
537	const preserved = buffered[i - c.history_len ..];
538	if (!is_flush) assert(preserved.len >= @max(rebase_min_preserve, preserve));
539	@memmove(w.buffer[0..preserved.len], preserved);
540	w.end = preserved.len;
541	}
542
543	fn addHash(c: *Compress, i: usize, h: Hash) void {
544	assert(h == hash(mem.readInt(Seq, c.writer.buffer[i..][0..seq_bytes], .big)));
545
546	const l = &c.lookup;
547	l.chain_pos +%= 1;
548
549	// Equivilent to the below, however LLVM 21 does not optimize `@subWithOverflow` well at all.
550	// const replaced_i, const no_replace = @subWithOverflow(i, flate.history_len);
551	// if (no_replace == 0) {
552	if (i >= flate.history_len) {
553	@branchHint(.likely);
554	const replaced_i = i - flate.history_len;
555	// The following is the same as the below except uses a 32-bit load to help optimizations
556	// const replaced_seq = mem.readInt(Seq, c.writer.buffer[replaced_i..][0..seq_bytes], .big);
557	comptime assert(@sizeOf(Seq) <= @sizeOf(u32));
558	const replaced_u32 = mem.readInt(u32, c.writer.buffered()[replaced_i..][0..4], .big);
559	const replaced_seq: Seq = @intCast(replaced_u32 >> (32 - @bitSizeOf(Seq)));
560
561	const replaced_h = hash(replaced_seq);
562	// The following is equivilent to the below since LLVM 21 doesn't optimize it well.
563	// l.head[replaced_h].is_null = l.head[replaced_h].is_null or
564	// l.head[replaced_h].int() == l.chain_pos;
565	const empty_head = l.head[replaced_h].int() == l.chain_pos;
566	const null_flag = PackedOptionalU15.int(.{ .is_null = empty_head, .value = 0 });
567	l.head[replaced_h] = @bitCast(l.head[replaced_h].int() | null_flag);
568	}
569
570	const prev_chain_index = l.head[h];
571	l.chain[l.chain_pos] = @bitCast((l.chain_pos -% prev_chain_index.value) |
572	(prev_chain_index.int() & PackedOptionalU15.null_bit.int())); // Preserves null
573	l.head[h] = .{ .value = l.chain_pos, .is_null = false };
574	}
575
576	/// If the match is shorter, the returned value can be any value `<= old`.
577	fn betterMatchLen(old: u16, prev: []const u8, bytes: []const u8) u16 {
578	assert(old < @min(bytes.len, token.max_length));
579	assert(prev.len >= bytes.len);
580	assert(bytes.len >= token.min_length);
581
582	var i: u16 = 0;
583	const Block = @Int(.unsigned, @min(math.divCeil(
584	comptime_int,
585	math.ceilPowerOfTwoAssert(usize, @bitSizeOf(usize)),
586	8,
587	) catch unreachable, 256) * 8);
588
589	if (bytes.len < token.max_length) {
590	@branchHint(.unlikely); // Only end of stream
591
592	while (bytes[i..].len >= @sizeOf(Block)) {
593	const a = mem.readInt(Block, prev[i..][0..@sizeOf(Block)], .little);
594	const b = mem.readInt(Block, bytes[i..][0..@sizeOf(Block)], .little);
595	const diff = a ^ b;
596	if (diff != 0) {
597	@branchHint(.likely);
598	i += @ctz(diff) / 8;
599	return i;
600	}
601	i += @sizeOf(Block);
602	}
603
604	while (i != bytes.len and prev[i] == bytes[i]) {
605	i += 1;
606	}
607	assert(i < token.max_length);
608	return i;
609	}
610
611	if (old >= @sizeOf(Block)) {
612	// Check that a longer end is present, otherwise the match is always worse
613	const a = mem.readInt(Block, prev[old + 1 - @sizeOf(Block) ..][0..@sizeOf(Block)], .little);
614	const b = mem.readInt(Block, bytes[old + 1 - @sizeOf(Block) ..][0..@sizeOf(Block)], .little);
615	if (a != b) return i;
616	}
617
618	while (true) {
619	const a = mem.readInt(Block, prev[i..][0..@sizeOf(Block)], .little);
620	const b = mem.readInt(Block, bytes[i..][0..@sizeOf(Block)], .little);
621	const diff = a ^ b;
622	if (diff != 0) {
623	i += @ctz(diff) / 8;
624	return i;
625	}
626	i += @sizeOf(Block);
627	if (i == 256) break;
628	}
629
630	const a = mem.readInt(u16, prev[i..][0..2], .little);
631	const b = mem.readInt(u16, bytes[i..][0..2], .little);
632	const diff = a ^ b;
633	i += @ctz(diff) / 8;
634	assert(i <= token.max_length);
635	return i;
636	}
637
638	test betterMatchLen {
639	try std.testing.fuzz({}, testFuzzedMatchLen, .{});
640	}
641
642	fn testFuzzedMatchLen(_: void, smith: *std.testing.Smith) !void {
643	@disableInstrumentation();
644	var buf: [1024]u8 = undefined;
645	var w: Writer = .fixed(&buf);
646
647	while (w.unusedCapacityLen() != 0 and !smith.eosWeightedSimple(7, 1)) {
648	switch (smith.value(enum(u2) { splat, copy, insert })) {
649	.splat => w.splatByteAll(
650	smith.value(u8),
651	smith.valueRangeAtMost(u9, 1, @min(511, w.unusedCapacityLen())),
652	) catch unreachable,
653	.copy => write: {
654	if (w.buffered().len == 0) continue;
655	const start = smith.valueRangeAtMost(u10, 0, @intCast(w.buffered().len - 1));
656	const max_len = @min(w.unusedCapacityLen(), w.buffered().len - start);
657	const len = smith.valueRangeAtMost(u10, 1, @intCast(max_len));
658	break :write w.writeAll(w.buffered()[start..][0..len]) catch unreachable;
659	},
660	.insert => w.advance(smith.slice(w.unusedCapacitySlice())),
661	}
662	}
663	w.splatByteAll(0, (1 + token.min_length) -| w.buffered().len) catch unreachable;
664
665	const max_start = w.buffered().len - token.min_length;
666	const bytes_off = smith.valueRangeAtMost(u10, 1, @intCast(max_start));
667	const prev_off = smith.valueRangeAtMost(u10, 0, bytes_off - 1);
668	const prev = w.buffered()[prev_off..];
669	const bytes = w.buffered()[bytes_off..];
670	const old = smith.valueRangeLessThan(u10, 0, @min(bytes.len, token.max_length));
671
672	const diff_index = mem.findDiff(u8, prev, bytes).?; // unwrap since lengths are not same
673	const expected_len = @min(diff_index, 258);
674	errdefer std.debug.print(
675	\\prev : '{any}'
676	\\bytes: '{any}'
677	\\old : {}
678	\\expected: {?}
679	\\actual : {}
680	++ "\n", .{
681	prev, bytes, old,
682	if (old < expected_len) expected_len else null, betterMatchLen(old, prev, bytes),
683	});
684	if (old < expected_len) {
685	try std.testing.expectEqual(expected_len, betterMatchLen(old, prev, bytes));
686	} else {
687	try std.testing.expect(betterMatchLen(old, prev, bytes) <= old);
688	}
689	}
690
691	fn matchAndAddHash(c: *Compress, i: usize, h: Hash, gt: u16, max_chain: u16, good_: u16) struct {
692	dist: u16,
693	len: u16,
694	} {
695	const l = &c.lookup;
696	const buffered = c.writer.buffered();
697
698	var chain_limit = max_chain;
699	var best_dist: u16 = undefined;
700	var best_len = gt;
701	const nice = @min(c.opts.nice, buffered[i..].len);
702	var good = good_;
703
704	search: {
705	if (l.head[h].is_null) break :search;
706	// Actually a u15, but LLVM 21 does not optimize that as well (it truncates it each use).
707	var dist: u16 = l.chain_pos -% l.head[h].value;
708	while (true) {
709	chain_limit -= 1;
710
711	const match_len = betterMatchLen(best_len, buffered[i - 1 - dist ..], buffered[i..]);
712	if (match_len > best_len) {
713	best_dist = dist;
714	best_len = match_len;
715	if (best_len >= nice) break;
716	if (best_len >= good) {
717	chain_limit >>= 2;
718	good = math.maxInt(u8); // Reduce only once
719	}
720	}
721
722	if (chain_limit == 0) break;
723	const next_chain_index = l.chain_pos -% @as(u15, @intCast(dist));
724	// Equivilent to the below, however LLVM 21 optimizes the below worse.
725	// if (l.chain[next_chain_index].is_null) break;
726	// dist, const out_of_window = @addWithOverflow(dist, l.chain[next_chain_index].value);
727	// if (out_of_window == 1) break;
728	dist +%= l.chain[next_chain_index].int(); // wrapping for potential null bit
729	comptime assert(flate.history_len == PackedOptionalU15.int(.null_bit));
730	// Also, doing >= flate.history_len gives worse codegen with LLVM 21.
731	if ((dist | l.chain[next_chain_index].int()) & flate.history_len != 0) break;
732	}
733	}
734
735	c.addHash(i, h);
736	return .{ .dist = best_dist, .len = best_len };
737	}
738
739	fn clenHlen(freqs: [19]u16) u4 {
740	// Note that the first four codes (16, 17, 18, and 0) are always present.
741	if (builtin.mode != .small and (std.simd.suggestVectorLength(u16) orelse 1) >= 8) {
742	const V = @Vector(16, u16);
743	const hlen_mul: V = comptime m: {
744	var hlen_mul: [16]u16 = undefined;
745	for (token.codegen_order[3..], 0..) |i, hlen| {
746	hlen_mul[i] = hlen;
747	}
748	break :m hlen_mul;
749	};
750	const encoded = freqs[0..16].* != @as(V, @splat(0));
751	return @intCast(@reduce(.Max, @intFromBool(encoded) * hlen_mul));
752	} else {
753	var max: u4 = 0;
754	for (token.codegen_order[4..], 1..) |i, len| {
755	max = if (freqs[i] == 0) max else @intCast(len);
756	}
757	return max;
758	}
759	}
760
761	test clenHlen {
762	var freqs: [19]u16 = @splat(0);
763	try std.testing.expectEqual(0, clenHlen(freqs));
764	for (token.codegen_order, 1..) |i, len| {
765	freqs[i] = 1;
766	try std.testing.expectEqual(len -| 4, clenHlen(freqs));
767	freqs[i] = 0;
768	}
769	}
770
771	/// Returns the number of values followed by the bitsize of the extra bits.
772	fn buildClen(
773	dyn_bits: []const u4,
774	out_values: []u8,
775	out_extra: []u8,
776	out_freqs: *[19]u16,
777	) struct { u16, u16 } {
778	assert(dyn_bits.len <= out_values.len);
779	assert(out_values.len == out_extra.len);
780
781	var len: u16 = 0;
782	var extra_bitsize: u16 = 0;
783
784	var remaining_bits = dyn_bits;
785	var prev: u4 = 0;
786	while (true) {
787	const b = remaining_bits[0];
788	const n_max = @min(@as(u8, if (b != 0)
789	if (b != prev) 1 else 6
790	else
791	138), remaining_bits.len);
792	prev = b;
793
794	var n: u8 = 0;
795	while (true) {
796	remaining_bits = remaining_bits[1..];
797	n += 1;
798	if (n == n_max or remaining_bits[0] != b) break;
799	}
800	const code, const extra, const xsize = switch (n) {
801	0 => unreachable,
802	1...2 => .{ b, 0, 0 },
803	3...10 => .{
804	@as(u8, 16) + @intFromBool(b == 0),
805	n - 3,
806	@as(u8, 2) + @intFromBool(b == 0),
807	},
808	11...138 => .{ 18, n - 11, 7 },
809	else => unreachable,
810	};
811	while (true) {
812	out_values[len] = code;
813	out_extra[len] = extra;
814	out_freqs[code] += 1;
815	extra_bitsize += xsize;
816	len += 1;
817	if (n != 2) {
818	@branchHint(.likely);
819	break;
820	}
821	// Code needs outputted once more
822	n = 1;
823	}
824	if (remaining_bits.len == 0) break;
825	}
826
827	return .{ len, extra_bitsize };
828	}
829
830	test buildClen {
831	//dyn_bits: []u4,
832	//out_values: *[288 + 30]u8,
833	//out_extra: *[288 + 30]u8,
834	//out_freqs: *[19]u16,
835	//struct { u16, u16 }
836	var out_values: [288 + 30]u8 = undefined;
837	var out_extra: [288 + 30]u8 = undefined;
838	var out_freqs: [19]u16 = @splat(0);
839	const len, const extra_bitsize = buildClen(&([_]u4{
840	1, // A
841	2, 2, // B
842	3, 3, 3, // C
843	4, 4, 4, 4, // D
844	5, // E
845	5, 5, 5, 5, 5, 5, //
846	5, 5, 5, 5, 5, 5,
847	5, 5,
848	0, 1, // F
849	0, 0, 1, // G
850	} ++ @as([138 + 10]u4, @splat(0)) // H
851	), &out_values, &out_extra, &out_freqs);
852	try std.testing.expectEqualSlices(u8, &.{
853	1, // A
854	2, 2, // B
855	3, 3, 3, // C
856	4, 16, // D
857	5, 16, 16, 5, 5, // E
858	0, 1, // F
859	0, 0, 1, // G
860	18, 17, // H
861	}, out_values[0..len]);
862	try std.testing.expectEqualSlices(u8, &.{
863	0, // A
864	0, 0, // B
865	0, 0, 0, // C
866	0, (0), // D
867	0, (3), (3), 0, 0, // E
868	0, 0, // F
869	0, 0, 0, // G
870	(127), (7), // H
871	}, out_extra[0..len]);
872	try std.testing.expectEqual(2 + 2 + 2 + 7 + 3, extra_bitsize);
873	try std.testing.expectEqualSlices(u16, &.{
874	3, 3, 2, 3, 1, 3, 0, 0,
875	0, 0, 0, 0, 0, 0, 0, 0,
876	3, 1, 1,
877	}, &out_freqs);
878	}
879
880	fn writeBlock(c: *Compress, eos: bool) Writer.Error!void {
881	const toks = &c.buffered_tokens;
882	assert(toks.lit_freqs[256] == 0);
883	toks.lit_freqs[256] = 1;
884
885	var dyn_codes_buf: [286 + 30]u16 = undefined;
886	var dyn_bits_buf: [286 + 30]u4 = @splat(0);
887
888	const dyn_lit_codes_bitsize, const dyn_last_lit = huffman.build(
889	&toks.lit_freqs,
890	dyn_codes_buf[0..286],
891	dyn_bits_buf[0..286],
892	15,
893	true,
894	);
895	const dyn_lit_len = @max(257, dyn_last_lit + 1);
896
897	const dyn_dist_codes_bitsize, const dyn_last_dist = huffman.build(
898	&toks.dist_freqs,
899	dyn_codes_buf[dyn_lit_len..][0..30],
900	dyn_bits_buf[dyn_lit_len..][0..30],
901	15,
902	true,
903	);
904	const dyn_dist_len = @max(1, dyn_last_dist + 1);
905
906	var clen_values: [288 + 30]u8 = undefined;
907	var clen_extra: [288 + 30]u8 = undefined;
908	var clen_freqs: [19]u16 = @splat(0);
909	const clen_len, const clen_extra_bitsize = buildClen(
910	dyn_bits_buf[0 .. dyn_lit_len + dyn_dist_len],
911	&clen_values,
912	&clen_extra,
913	&clen_freqs,
914	);
915
916	var clen_codes: [19]u16 = undefined;
917	var clen_bits: [19]u4 = @splat(0);
918	const clen_codes_bitsize, _ = huffman.build(
919	&clen_freqs,
920	&clen_codes,
921	&clen_bits,
922	7,
923	false,
924	);
925	const hclen = clenHlen(clen_freqs);
926
927	const dynamic_bitsize = @as(u32, 14) +
928	(4 + @as(u6, hclen)) * 3 + clen_codes_bitsize + clen_extra_bitsize +
929	dyn_lit_codes_bitsize + dyn_dist_codes_bitsize;
930	const fixed_bitsize = n: {
931	const freq7 = 1; // eos
932	var freq8: u16 = 0;
933	var freq9: u16 = 0;
934	var freq12: u16 = 0; // 7 + 5 - match freqs always have corresponding 5-bit dist freq
935	var freq13: u16 = 0; // 8 + 5
936	for (toks.lit_freqs[0..144]) |f| freq8 += f;
937	for (toks.lit_freqs[144..256]) |f| freq9 += f;
938	assert(toks.lit_freqs[256] == 1);
939	for (toks.lit_freqs[257..280]) |f| freq12 += f;
940	for (toks.lit_freqs[280..286]) |f| freq13 += f;
941	break :n @as(u32, freq7) * 7 +
942	@as(u32, freq8) * 8 + @as(u32, freq9) * 9 +
943	@as(u32, freq12) * 12 + @as(u32, freq13) * 13;
944	};
945
946	stored: {
947	for (toks.dist_freqs) |n| if (n != 0) break :stored;
948	// No need to check len frequencies since they each have a corresponding dist frequency
949	assert(for (toks.lit_freqs[257..]) |f| (if (f != 0) break false) else true);
950
951	// No matches. If the stored size is smaller than the huffman-encoded version, it will be
952	// outputed in a store block. This is not done with matches since the original input would
953	// need to be stored since the window may slid, and it may also exceed 65535 bytes. This
954	// should be OK since most inputs with matches should be more compressable anyways.
955	const stored_align_bits = -%(c.bit_writer.buffered_n +% 3);
956	const stored_bitsize = stored_align_bits + @as(u32, 32) + @as(u32, toks.n) * 8;
957	if (@min(dynamic_bitsize, fixed_bitsize) < stored_bitsize) break :stored;
958
959	try c.bit_writer.write(BlockHeader.int(.{ .kind = .stored, .final = eos }), 3);
960	try c.bit_writer.output.rebase(0, 5);
961	c.bit_writer.byteAlign();
962	c.bit_writer.output.writeInt(u16, c.buffered_tokens.n, .little) catch unreachable;
963	c.bit_writer.output.writeInt(u16, ~c.buffered_tokens.n, .little) catch unreachable;
964
965	// Relatively small buffer since regular draining will
966	// always consume slightly less than 2 << 15 bytes.
967	var vec_buf: [4][]const u8 = undefined;
968	var vec_n: usize = 0;
969	var i: usize = 0;
970
971	assert(c.buffered_tokens.pos != 0);
972	while (i != c.buffered_tokens.pos) {
973	const h: TokenBufferEntryHeader = @bitCast(toks.list[i..][0..2].*);
974	assert(h.kind == .bytes);
975
976	i += 2;
977	vec_buf[vec_n] = toks.list[i..][0..h.data];
978	i += h.data;
979
980	vec_n += 1;
981	if (i == c.buffered_tokens.pos or vec_n == vec_buf.len) {
982	try c.bit_writer.output.writeVecAll(vec_buf[0..vec_n]);
983	vec_n = 0;
984	}
985	}
986
987	toks.* = .empty;
988	return;
989	}
990
991	const lit_codes, const lit_bits, const dist_codes, const dist_bits =
992	if (dynamic_bitsize < fixed_bitsize) codes: {
993	try c.bit_writer.write(BlockHeader.Dynamic.int(.{
994	.regular = .{ .final = eos, .kind = .dynamic },
995	.hlit = @intCast(dyn_lit_len - 257),
996	.hdist = @intCast(dyn_dist_len - 1),
997	.hclen = hclen,
998	}), 17);
999	try c.bit_writer.writeClen(
1000	hclen,
1001	clen_values[0..clen_len],
1002	clen_extra[0..clen_len],
1003	clen_codes,
1004	clen_bits,
1005	);
1006	break :codes .{
1007	dyn_codes_buf[0..dyn_lit_len],
1008	dyn_bits_buf[0..dyn_lit_len],
1009	dyn_codes_buf[dyn_lit_len..][0..dyn_dist_len],
1010	dyn_bits_buf[dyn_lit_len..][0..dyn_dist_len],
1011	};
1012	} else codes: {
1013	try c.bit_writer.write(BlockHeader.int(.{ .final = eos, .kind = .fixed }), 3);
1014	break :codes .{
1015	&token.fixed_lit_codes,
1016	&token.fixed_lit_bits,
1017	&token.fixed_dist_codes,
1018	&token.fixed_dist_bits,
1019	};
1020	};
1021
1022	var i: usize = 0;
1023	while (i != toks.pos) {
1024	const h: TokenBufferEntryHeader = @bitCast(toks.list[i..][0..2].*);
1025	i += 2;
1026	if (h.kind == .bytes) {
1027	for (toks.list[i..][0..h.data]) |b| {
1028	try c.bit_writer.write(lit_codes[b], lit_bits[b]);
1029	}
1030	i += h.data;
1031	} else {
1032	const dist = h.data;
1033	const len = toks.list[i];
1034	i += 1;
1035	const dist_code = token.DistCode.fromVal(dist);
1036	const len_code = token.LenCode.fromVal(len);
1037	const dist_val = dist_code.toInt();
1038	const lit_val = @as(u16, 257) + len_code.toInt();
1039
1040	var out: u48 = lit_codes[lit_val];
1041	var out_bits: u6 = lit_bits[lit_val];
1042	out |= @shlExact(@as(u20, len - len_code.base()), @intCast(out_bits));
1043	out_bits += len_code.extraBits();
1044
1045	out |= @shlExact(@as(u35, dist_codes[dist_val]), out_bits);
1046	out_bits += dist_bits[dist_val];
1047	out |= @shlExact(@as(u48, dist - dist_code.base()), out_bits);
1048	out_bits += dist_code.extraBits();
1049
1050	try c.bit_writer.write(out, out_bits);
1051	}
1052	}
1053	try c.bit_writer.write(lit_codes[256], lit_bits[256]);
1054
1055	toks.* = .empty;
1056	}
1057
1058	/// Huffman tree construction.
1059	///
1060	/// The approach for building the huffman tree is [taken from zlib]
1061	/// (https://github.com/madler/zlib/blob/v1.3.1/trees.c#L625) with some modifications.
1062	const huffman = struct {
1063	const max_leafs = 286;
1064	const max_nodes = max_leafs * 2;
1065
1066	const Node = packed struct(u32) {
1067	depth: u16,
1068	freq: u16,
1069
1070	pub const Index = u16;
1071
1072	/// `freq` is more significant than `depth`
1073	pub fn smaller(a: Node, b: Node) bool {
1074	return @as(u32, @bitCast(a)) < @as(u32, @bitCast(b));
1075	}
1076	};
1077
1078	fn heapSiftDown(nodes: []Node, heap: []Node.Index, start: usize) void {
1079	var i = start;
1080	while (true) {
1081	var min = i;
1082	const l = i * 2 + 1;
1083	const r = l + 1;
1084	min = if (l < heap.len and nodes[heap[l]].smaller(nodes[heap[min]])) l else min;
1085	min = if (r < heap.len and nodes[heap[r]].smaller(nodes[heap[min]])) r else min;
1086	if (i == min) break;
1087	mem.swap(Node.Index, &heap[i], &heap[min]);
1088	i = min;
1089	}
1090	}
1091
1092	fn heapRemoveRoot(nodes: []Node, heap: []Node.Index) void {
1093	heap[0] = heap[heap.len - 1];
1094	heapSiftDown(nodes, heap[0 .. heap.len - 1], 0);
1095	}
1096
1097	/// Returns the total bits to encode `freqs` followed by the index of the last non-zero bits.
1098	/// For `freqs[i]` == 0, `out_codes[i]` will be undefined.
1099	/// It is asserted `out_bits` is zero-filled.
1100	/// It is asserted `out_bits.len` is at least a length of
1101	/// one if ncomplete trees are allowed and two otherwise.
1102	pub fn build(
1103	freqs: []const u16,
1104	out_codes: []u16,
1105	out_bits: []u4,
1106	max_bits: u4,
1107	incomplete_allowed: bool,
1108	) struct { u32, u16 } {
1109	assert(out_codes.len - 1 >= @intFromBool(!incomplete_allowed));
1110	// freqs and out_codes are in the loop to assert they are all the same length
1111	for (freqs, out_codes, out_bits) |_, _, n| assert(n == 0);
1112	assert(out_codes.len <= @as(u16, 1) << max_bits);
1113
1114	// Indexes 0..freqs are leafs, indexes max_leafs.. are internal nodes.
1115	var tree_nodes: [max_nodes]Node = undefined;
1116	var tree_parent_nodes: [max_nodes]Node.Index = undefined;
1117	var nodes_end: u16 = max_leafs;
1118	// Dual-purpose buffer. Nodes are ordered by least frequency or when equal, least depth.
1119	// The start is a min heap of level-zero nodes.
1120	// The end is a sorted buffer of nodes with the greatest first.
1121	var node_buf: [max_nodes]Node.Index = undefined;
1122	var heap_end: u16 = 0;
1123	var sorted_start: u16 = node_buf.len;
1124
1125	for (0.., freqs) |n, freq| {
1126	tree_nodes[n] = .{ .freq = freq, .depth = 0 };
1127	node_buf[heap_end] = @intCast(n);
1128	heap_end += @intFromBool(freq != 0);
1129	}
1130
1131	// There must be at least one code at minimum,
1132	node_buf[heap_end] = 0;
1133	heap_end += @intFromBool(heap_end == 0);
1134	// and at least two if incomplete must be avoided.
1135	if (heap_end == 1 and incomplete_allowed) {
1136	@branchHint(.unlikely); // LLVM 21 optimizes this branch as the more likely without
1137
1138	// Codes must have at least one-bit, so this is a special case.
1139	out_bits[node_buf[0]] = 1;
1140	out_codes[node_buf[0]] = 0;
1141	return .{ freqs[node_buf[0]], node_buf[0] };
1142	}
1143	const last_nonzero = @max(node_buf[heap_end - 1], 1); // For heap_end > 1, last is not be 0
1144	node_buf[heap_end] = @intFromBool(node_buf[0] == 0);
1145	heap_end += @intFromBool(heap_end == 1);
1146
1147	// Heapify the array of frequencies
1148	const heapify_final = heap_end - 1;
1149	const heapify_start = (heapify_final - 1) / 2; // Parent of final node
1150	var heapify_i = heapify_start;
1151	while (true) {
1152	heapSiftDown(&tree_nodes, node_buf[0..heap_end], heapify_i);
1153	if (heapify_i == 0) break;
1154	heapify_i -= 1;
1155	}
1156
1157	// Build optimal tree. `max_bits` is not enforced yet.
1158	while (heap_end > 1) {
1159	const a = node_buf[0];
1160	heapRemoveRoot(&tree_nodes, node_buf[0..heap_end]);
1161	heap_end -= 1;
1162	const b = node_buf[0];
1163
1164	sorted_start -= 2;
1165	node_buf[sorted_start..][0..2].* = .{ b, a };
1166
1167	tree_nodes[nodes_end] = .{
1168	.freq = tree_nodes[a].freq + tree_nodes[b].freq,
1169	.depth = @max(tree_nodes[a].depth, tree_nodes[b].depth) + 1,
1170	};
1171	defer nodes_end += 1;
1172	tree_parent_nodes[a] = nodes_end;
1173	tree_parent_nodes[b] = nodes_end;
1174
1175	node_buf[0] = nodes_end;
1176	heapSiftDown(&tree_nodes, node_buf[0..heap_end], 0);
1177	}
1178	sorted_start -= 1;
1179	node_buf[sorted_start] = node_buf[0];
1180
1181	var bit_counts: [16]u16 = @splat(0);
1182	buildBits(out_bits, &bit_counts, &tree_parent_nodes, node_buf[sorted_start..], max_bits);
1183	return .{ buildValues(freqs, out_codes, out_bits, bit_counts), last_nonzero };
1184	}
1185
1186	fn buildBits(
1187	out_bits: []u4,
1188	bit_counts: *[16]u16,
1189	parent_nodes: *[max_nodes]Node.Index,
1190	sorted: []Node.Index,
1191	max_bits: u4,
1192	) void {
1193	var internal_node_bits: [max_nodes - max_leafs]u4 = undefined;
1194	var overflowed: u16 = 0;
1195
1196	internal_node_bits[sorted[0] - max_leafs] = 0; // root
1197	for (sorted[1..]) |i| {
1198	const parent_bits = internal_node_bits[parent_nodes[i] - max_leafs];
1199	overflowed += @intFromBool(parent_bits == max_bits);
1200	const bits = parent_bits + @intFromBool(parent_bits != max_bits);
1201	bit_counts[bits] += @intFromBool(i < max_leafs);
1202	(if (i >= max_leafs) &internal_node_bits[i - max_leafs] else &out_bits[i]).* = bits;
1203	}
1204
1205	if (overflowed == 0) {
1206	@branchHint(.likely);
1207	return;
1208	}
1209
1210	outer: while (true) {
1211	var deepest: u4 = max_bits - 1;
1212	while (bit_counts[deepest] == 0) deepest -= 1;
1213	while (overflowed != 0) {
1214	// Insert an internal node under the leaf and move an overflow as its sibling
1215	bit_counts[deepest] -= 1;
1216	bit_counts[deepest + 1] += 2;
1217	// Only overflow moved. Its sibling's depth is one less, however is still >= depth.
1218	bit_counts[max_bits] -= 1;
1219	overflowed -= 2;
1220
1221	if (overflowed == 0) break :outer;
1222	deepest += 1;
1223	if (deepest == max_bits) continue :outer;
1224	}
1225	}
1226
1227	// Reassign bit lengths
1228	assert(bit_counts[0] == 0);
1229	var i: usize = 0;
1230	for (1.., bit_counts[1..]) |bits, all| {
1231	var remaining = all;
1232	while (remaining != 0) {
1233	defer i += 1;
1234	if (sorted[i] >= max_leafs) continue;
1235	out_bits[sorted[i]] = @intCast(bits);
1236	remaining -= 1;
1237	}
1238	}
1239	assert(for (sorted[i..]) |n| { // all leafs consumed
1240	if (n < max_leafs) break false;
1241	} else true);
1242	}
1243
1244	fn buildValues(freqs: []const u16, out_codes: []u16, bits: []u4, bit_counts: [16]u16) u32 {
1245	var code: u16 = 0;
1246	var base: [16]u16 = undefined;
1247	assert(bit_counts[0] == 0);
1248	for (bit_counts[1..], base[1..]) |c, *b| {
1249	b.* = code;
1250	code +%= c;
1251	code <<= 1;
1252	}
1253	var freq_sums: [16]u16 = @splat(0);
1254	for (out_codes, bits, freqs) |*c, b, f| {
1255	c.* = @bitReverse(base[b]) >> -%b;
1256	base[b] += 1; // For `b == 0` this is fine since v is specified to be undefined.
1257	freq_sums[b] += f;
1258	}
1259	return @reduce(.Add, @as(@Vector(16, u32), freq_sums) * std.simd.iota(u32, 16));
1260	}
1261
1262	test build {
1263	var codes: [8]u16 = undefined;
1264	var bits: [8]u4 = undefined;
1265
1266	const regular_freqs: [8]u16 = .{ 1, 1, 0, 8, 8, 0, 2, 4 };
1267	// The optimal tree for the above frequencies is
1268	// 4 1 1
1269	// \ /
1270	// 3 2 #
1271	// \ /
1272	// 2 8 8 4 #
1273	// \ / \ /
1274	// 1 # #
1275	// \ /
1276	// 0 #
1277	bits = @splat(0);
1278	var n, var lnz = build(&regular_freqs, &codes, &bits, 15, true);
1279	codes[2] = 0;
1280	codes[5] = 0;
1281	try std.testing.expectEqualSlices(u4, &.{ 4, 4, 0, 2, 2, 0, 3, 2 }, &bits);
1282	try std.testing.expectEqualSlices(u16, &.{
1283	0b0111, 0b1111, 0, 0b00, 0b10, 0, 0b011, 0b01,
1284	}, &codes);
1285	try std.testing.expectEqual(54, n);
1286	try std.testing.expectEqual(7, lnz);
1287	// When constrained to 3 bits, it becomes
1288	// 3 1 1 2 4
1289	// \ / \ /
1290	// 2 8 8 # #
1291	// \ / \ /
1292	// 1 # #
1293	// \ /
1294	// 0 #
1295	bits = @splat(0);
1296	n, lnz = build(&regular_freqs, &codes, &bits, 3, true);
1297	codes[2] = 0;
1298	codes[5] = 0;
1299	try std.testing.expectEqualSlices(u4, &.{ 3, 3, 0, 2, 2, 0, 3, 3 }, &bits);
1300	try std.testing.expectEqualSlices(u16, &.{
1301	0b001, 0b101, 0, 0b00, 0b10, 0, 0b011, 0b111,
1302	}, &codes);
1303	try std.testing.expectEqual(56, n);
1304	try std.testing.expectEqual(7, lnz);
1305
1306	// Empty tree. At least one code should be present
1307	bits = @splat(0);
1308	n, lnz = build(&.{ 0, 0 }, codes[0..2], bits[0..2], 15, true);
1309	try std.testing.expectEqualSlices(u4, &.{ 1, 0 }, bits[0..2]);
1310	try std.testing.expectEqual(0b0, codes[0]);
1311	try std.testing.expectEqual(0, n);
1312	try std.testing.expectEqual(0, lnz);
1313
1314	// Check all incompletable frequencies are completed
1315	for ([_][2]u16{ .{ 0, 0 }, .{ 0, 1 }, .{ 1, 0 } }) |incomplete| {
1316	// Empty tree. Both codes should be present to prevent incomplete trees
1317	bits = @splat(0);
1318	n, lnz = build(&incomplete, codes[0..2], bits[0..2], 15, false);
1319	try std.testing.expectEqualSlices(u4, &.{ 1, 1 }, bits[0..2]);
1320	try std.testing.expectEqualSlices(u16, &.{ 0b0, 0b1 }, codes[0..2]);
1321	try std.testing.expectEqual(incomplete[0] + incomplete[1], n);
1322	try std.testing.expectEqual(1, lnz);
1323	}
1324
1325	try std.testing.fuzz({}, checkFuzzedBuildFreqs, .{});
1326	}
1327
1328	fn checkFuzzedBuildFreqs(_: void, smith: *std.testing.Smith) !void {
1329	@disableInstrumentation();
1330	var freqs_limit: u16 = 65535;
1331	var freqs_buf: [max_leafs]u16 = undefined;
1332	var nfreqs: u15 = 0;
1333
1334	const incomplete_allowed = smith.value(bool);
1335	while (nfreqs < @as(u8, @intFromBool(!incomplete_allowed)) + 1 or
1336	nfreqs != freqs_buf.len and freqs_limit != 0 and
1337	smith.eosWeightedSimple(15, 1))
1338	{
1339	const f = smith.valueWeighted(u16, &.{
1340	.rangeAtMost(u16, 0, @min(31, freqs_limit), @max(freqs_limit, 1)),
1341	.rangeAtMost(u16, 0, freqs_limit, 1),
1342	});
1343	freqs_buf[nfreqs] = f;
1344	freqs_limit -= f;
1345	nfreqs += 1;
1346	}
1347
1348	var codes_buf: [max_leafs]u16 = undefined;
1349	var bits_buf: [max_leafs]u4 = @splat(0);
1350	const max_bits = smith.valueRangeAtMost(u4, math.log2_int_ceil(u15, nfreqs), 15);
1351	const total_bits, const last_nonzero = build(
1352	freqs_buf[0..nfreqs],
1353	codes_buf[0..nfreqs],
1354	bits_buf[0..nfreqs],
1355	max_bits,
1356	incomplete_allowed,
1357	);
1358
1359	var has_bitlen_one: bool = false;
1360	var expected_total_bits: u32 = 0;
1361	var expected_last_nonzero: ?u16 = null;
1362	var weighted_sum: u32 = 0;
1363	for (freqs_buf[0..nfreqs], bits_buf[0..nfreqs], 0..) |f, nb, i| {
1364	has_bitlen_one = has_bitlen_one or nb == 1;
1365	weighted_sum += @shlExact(@as(u16, 1), 15 - nb) & ((1 << 15) - 1);
1366	expected_total_bits += @as(u32, f) * nb;
1367	if (nb != 0) expected_last_nonzero = @intCast(i);
1368	}
1369
1370	errdefer std.log.err(
1371	\\ incomplete_allowed: {}
1372	\\ max_bits: {}
1373	\\ freqs: {any}
1374	\\ bits: {any}
1375	\\ # freqs: {}
1376	\\ weighted sum: {}
1377	\\ has_bitlen_one: {}
1378	\\ expected/actual total bits: {}/{}
1379	\\ expected/actual last nonzero: {?}/{}
1380	++ "\n", .{
1381	incomplete_allowed,
1382	max_bits,
1383	freqs_buf[0..nfreqs],
1384	bits_buf[0..nfreqs],
1385	nfreqs,
1386	weighted_sum,
1387	has_bitlen_one,
1388	expected_total_bits,
1389	total_bits,
1390	expected_last_nonzero,
1391	last_nonzero,
1392	});
1393
1394	try std.testing.expectEqual(expected_total_bits, total_bits);
1395	try std.testing.expectEqual(expected_last_nonzero, last_nonzero);
1396	if (weighted_sum > 1 << 15)
1397	return error.OversubscribedHuffmanTree;
1398	if (weighted_sum < 1 << 15 and
1399	!(incomplete_allowed and has_bitlen_one and weighted_sum == 1 << 14))
1400	return error.IncompleteHuffmanTree;
1401	}
1402	};
1403
1404	test {
1405	_ = huffman;
1406	}
1407
1408	/// [0] is a gradient where the probability of lower values decreases across it
1409	/// [1] is completely random and hence uncompressable
1410	fn testingFreqBufs() !*[2][65536]u8 {
1411	const fbufs = try std.testing.allocator.create([2][65536]u8);
1412	var prng: std.Random.DefaultPrng = .init(std.testing.random_seed);
1413	prng.random().bytes(&fbufs[0]);
1414	prng.random().bytes(&fbufs[1]);
1415	for (0.., &fbufs[0], fbufs[1]) |i, *grad, rand| {
1416	const prob = @as(u8, @intCast(255 - i / (fbufs[0].len * 256)));
1417	grad.* /= @max(1, rand / @max(1, prob));
1418	}
1419	return fbufs;
1420	}
1421	const FreqBufIndex = enum(u1) { gradient, random };
1422
1423	fn testingCheckDecompressedMatches(
1424	flate_bytes: []const u8,
1425	expected_size: u32,
1426	expected_hash: flate.Container.Hasher,
1427	) !void {
1428	const container: flate.Container = expected_hash;
1429	var data_hash: flate.Container.Hasher = .init(container);
1430	var data_size: u32 = 0;
1431	var flate_r: Io.Reader = .fixed(flate_bytes);
1432	var deflate_buf: [flate.max_window_len]u8 = undefined;
1433	var deflate: flate.Decompress = .init(&flate_r, container, &deflate_buf);
1434
1435	while (deflate.reader.peekGreedy(1)) |bytes| {
1436	data_size += @intCast(bytes.len);
1437	data_hash.update(bytes);
1438	deflate.reader.toss(bytes.len);
1439	} else |e| switch (e) {
1440	error.ReadFailed => return deflate.err.?,
1441	error.EndOfStream => {},
1442	}
1443
1444	try testingCheckContainerHash(
1445	expected_size,
1446	expected_hash,
1447	data_hash,
1448	data_size,
1449	deflate.container_metadata,
1450	);
1451	}
1452
1453	fn testingCheckContainerHash(
1454	expected_size: u32,
1455	expected_hash: flate.Container.Hasher,
1456	actual_hash: flate.Container.Hasher,
1457	actual_size: u32,
1458	actual_meta: flate.Container.Metadata,
1459	) !void {
1460	try std.testing.expectEqual(expected_size, actual_size);
1461	switch (actual_hash) {
1462	.raw => {},
1463	.gzip => |gz| {
1464	const expected_crc = expected_hash.gzip.crc.final();
1465	try std.testing.expectEqual(expected_size, actual_meta.gzip.count);
1466	try std.testing.expectEqual(expected_crc, gz.crc.final());
1467	try std.testing.expectEqual(expected_crc, actual_meta.gzip.crc);
1468	},
1469	.zlib => |zl| {
1470	const expected_adler = expected_hash.zlib.adler;
1471	try std.testing.expectEqual(expected_adler, zl.adler);
1472	try std.testing.expectEqual(expected_adler, actual_meta.zlib.adler);
1473	},
1474	}
1475	}
1476
1477	const PackedContainer = packed struct(u2) {
1478	raw: bool,
1479	other: enum(u1) { gzip, zlib },
1480
1481	pub fn val(c: @This()) flate.Container {
1482	return if (c.raw) .raw else switch (c.other) {
1483	.gzip => .gzip,
1484	.zlib => .zlib,
1485	};
1486	}
1487	};
1488
1489	test Compress {
1490	const fbufs = try testingFreqBufs();
1491	defer std.testing.allocator.destroy(fbufs);
1492	try std.testing.fuzz(fbufs, testFuzzedCompressInput, .{});
1493	}
1494
1495	fn testFuzzedCompressInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void {
1496	@disableInstrumentation();
1497	const container = smith.value(flate.Container);
1498	const good = smith.valueRangeAtMost(u16, 3, 258);
1499	const nice = smith.valueRangeAtMost(u16, 3, 258);
1500	const lazy = smith.valueRangeAtMost(u16, 3, nice);
1501	const chain = smith.valueWeighted(u16, &.{
1502	.rangeAtMost(u16, if (good <= lazy) 4 else 1, 255, 65536),
1503	// The following weights are greatly reduced since they increasing take more time to run
1504	.rangeAtMost(u16, 256, 4095, 256),
1505	.rangeAtMost(u16, 4096, 32767 + 256, 1),
1506	});
1507	var expected_hash: flate.Container.Hasher = .init(container);
1508	var expected_size: u32 = 0;
1509
1510	var flate_buf: [128 * 1024]u8 = undefined;
1511	var flate_w: Writer = .fixed(&flate_buf);
1512	var deflate_buf: [flate.max_window_len * 2]u8 = undefined;
1513	const bufsize = smith.valueRangeAtMost(u32, flate.max_window_len, @intCast(deflate_buf.len));
1514	var deflate_w = try Compress.init(&flate_w, deflate_buf[0..bufsize], container, .{
1515	.good = good,
1516	.nice = nice,
1517	.lazy = lazy,
1518	.chain = chain,
1519	});
1520
1521	var max_output: usize = 32; // Headers / footer
1522	while (!smith.eosWeightedSimple(7, 1)) {
1523	const buffered = deflate_w.writer.buffered();
1524	// Required for repeating patterns and since writing from `buffered` is illegal
1525	var copy_buf: [512]u8 = undefined;
1526
1527	const bytes = bytes: switch (smith.valueRangeAtMost(
1528	u2,
1529	@intFromBool(buffered.len == 0),
1530	3,
1531	)) {
1532	0 => { // Copy
1533	const start = smith.valueRangeLessThan(u32, 0, @intCast(buffered.len));
1534	// Reuse the implementation's history; otherwise, our own would need maintained.
1535	const from = buffered[start..];
1536	const len = smith.valueRangeAtMost(u16, 1, copy_buf.len);
1537
1538	const history_bytes = from[0..@min(from.len, len)];
1539	@memcpy(copy_buf[0..history_bytes.len], history_bytes);
1540	const repeat_len = len - history_bytes.len;
1541	for (
1542	copy_buf[history_bytes.len..][0..repeat_len],
1543	copy_buf[0..repeat_len],
1544	) |*next, prev| {
1545	next.* = prev;
1546	}
1547	break :bytes copy_buf[0..len];
1548	},
1549	1 => { // Bytes
1550	const fbuf = &fbufs[
1551	smith.valueWeighted(u1, &.{
1552	.value(FreqBufIndex, .gradient, 3),
1553	.value(FreqBufIndex, .random, 1),
1554	})
1555	];
1556	const len = smith.valueRangeAtMost(u32, 1, fbuf.len);
1557	const off = smith.valueRangeAtMost(u32, 0, @intCast(fbuf.len - len));
1558	break :bytes fbuf[off..][0..len];
1559	},
1560	2 => { // Rebase
1561	const rebaseable = bufsize - rebase_reserved_capacity;
1562	const capacity = smith.valueRangeAtMost(u32, 1, rebaseable - rebase_min_preserve);
1563	const preserve = smith.valueRangeAtMost(u32, 0, rebaseable - capacity);
1564	const failed = deflate_w.writer.rebase(preserve, capacity);
1565	if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
1566	failed catch return; // Wrote too much data and ran out of space
1567	continue;
1568	},
1569	3 => { // Flush
1570	max_output += 8; // Alignment data
1571	const failed = deflate_w.writer.flush();
1572	if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
1573	failed catch return; // Wrote too much data and ran out of space
1574	continue;
1575	},
1576	};
1577
1578	// An overhead of 64 bytes is given for each block since the implementation does not
1579	// gaurauntee it writes store blocks when optimal. This comes from taking less than 32
1580	// bytes to write an optimal dynamic block header of mostly bitlen 8 codes and the end
1581	// of block literal plus `(65536 / 256) / 8`, which is is the maximum number of extra
1582	// bytes from bitlen 9 codes.
1583	max_output += bytes.len + ((bytes.len + flate_buf.len - 1) / block_tokens) * 64;
1584	const failed = deflate_w.writer.writeAll(bytes);
1585	if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
1586	failed catch return; // Wrote too much data and ran out of space
1587	expected_hash.update(bytes);
1588	expected_size += @intCast(bytes.len);
1589	}
1590
1591	const failed = deflate_w.finish();
1592	if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
1593	failed catch return; // Wrote too much data and ran out of space
1594	try testingCheckDecompressedMatches(flate_w.buffered(), expected_size, expected_hash);
1595	}
1596
1597	/// Does not compress data
1598	pub const Raw = struct {
1599	/// After `finish` is called, all vtable calls with result in `error.WriteFailed`.
1600	writer: Writer,
1601	output: *Writer,
1602	hasher: flate.Container.Hasher,
1603
1604	const max_block_size: u16 = 65535;
1605	const full_header: [5]u8 = .{
1606	BlockHeader.int(.{ .final = false, .kind = .stored }),
1607	255,
1608	255,
1609	0,
1610	0,
1611	};
1612
1613	/// While there is no minimum buffer size, it is recommended
1614	/// to be at least `flate.max_window_len` for optimal output.
1615	pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Raw {
1616	try output.writeAll(container.header());
1617	return .{
1618	.writer = .{
1619	.buffer = buffer,
1620	.vtable = &.{
1621	.drain = Raw.drain,
1622	.flush = Raw.flush,
1623	.rebase = Raw.rebase,
1624	},
1625	},
1626	.output = output,
1627	.hasher = .init(container),
1628	};
1629	}
1630
1631	fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
1632	errdefer w.* = .failing;
1633	const r: *Raw = @fieldParentPtr("writer", w);
1634	const min_block = @min(w.buffer.len, max_block_size);
1635	const pattern = data[data.len - 1];
1636	var partial_header: [5]u8 = undefined;
1637
1638	var vecs: [16][]const u8 = undefined;
1639	var vecs_n: usize = 0;
1640	const data_bytes = Writer.countSplat(data, splat);
1641	const total_bytes = w.end + data_bytes;
1642	var rem_bytes = total_bytes;
1643	var rem_splat = splat;
1644	var rem_data = data;
1645	var rem_data_elem: []const u8 = w.buffered();
1646
1647	assert(rem_bytes > min_block);
1648	while (rem_bytes > min_block) { // not >= to allow `min_block` blocks to be marked as final
1649	// also, it handles the case of `min_block` being zero (no buffer)
1650	const block_size: u16 = @min(rem_bytes, max_block_size);
1651	rem_bytes -= block_size;
1652
1653	if (vecs_n == vecs.len) {
1654	try r.output.writeVecAll(&vecs);
1655	vecs_n = 0;
1656	}
1657	vecs[vecs_n] = if (block_size == 65535)
1658	&full_header
1659	else header: {
1660	partial_header[0] = BlockHeader.int(.{ .final = false, .kind = .stored });
1661	mem.writeInt(u16, partial_header[1..3], block_size, .little);
1662	mem.writeInt(u16, partial_header[3..5], ~block_size, .little);
1663	break :header &partial_header;
1664	};
1665	vecs_n += 1;
1666
1667	var block_limit: Io.Limit = .limited(block_size);
1668	while (true) {
1669	if (vecs_n == vecs.len) {
1670	try r.output.writeVecAll(&vecs);
1671	vecs_n = 0;
1672	}
1673
1674	const vec = block_limit.sliceConst(rem_data_elem);
1675	vecs[vecs_n] = vec;
1676	vecs_n += 1;
1677	r.hasher.update(vec);
1678
1679	const is_pattern = rem_splat != splat and vec.len == pattern.len;
1680	if (is_pattern) assert(pattern.len != 0); // exceeded countSplat
1681
1682	if (!is_pattern or rem_splat == 0 or pattern.len > @backingInt(block_limit) / 2) {
1683	rem_data_elem = rem_data_elem[vec.len..];
1684	block_limit = block_limit.subtract(vec.len).?;
1685
1686	if (rem_data_elem.len == 0) {
1687	rem_data_elem = rem_data[0];
1688	if (rem_data.len != 1) {
1689	rem_data = rem_data[1..];
1690	} else if (rem_splat != 0) {
1691	rem_splat -= 1;
1692	} else {
1693	// All of `data` has been consumed.
1694	assert(block_limit == .nothing);
1695	assert(rem_bytes == 0);
1696	// Since `rem_bytes` and `block_limit` are zero, these won't be used.
1697	rem_data = undefined;
1698	rem_data_elem = undefined;
1699	rem_splat = undefined;
1700	}
1701	}
1702	if (block_limit == .nothing) break;
1703	} else {
1704	const out_splat = @backingInt(block_limit) / pattern.len;
1705	assert(out_splat >= 2);
1706
1707	try r.output.writeSplatAll(vecs[0..vecs_n], out_splat);
1708	for (1..out_splat) |_| r.hasher.update(vec);
1709
1710	vecs_n = 0;
1711	block_limit = block_limit.subtract(pattern.len * out_splat).?;
1712	if (rem_splat >= out_splat) {
1713	// `out_splat` contains `rem_data`, however one more needs subtracted
1714	// anyways since the next pattern is also being taken.
1715	rem_splat -= out_splat;
1716	} else {
1717	// All of `data` has been consumed.
1718	assert(block_limit == .nothing);
1719	assert(rem_bytes == 0);
1720	// Since `rem_bytes` and `block_limit` are zero, these won't be used.
1721	rem_data = undefined;
1722	rem_data_elem = undefined;
1723	rem_splat = undefined;
1724	}
1725	if (block_limit == .nothing) break;
1726	}
1727	}
1728	}
1729
1730	if (vecs_n != 0) { // can be the case if a splat was sent
1731	try r.output.writeVecAll(vecs[0..vecs_n]);
1732	}
1733
1734	if (rem_bytes > data_bytes) {
1735	assert(rem_bytes - data_bytes == rem_data_elem.len);
1736	assert(&rem_data_elem[0] == &w.buffer[total_bytes - rem_bytes]);
1737	}
1738	return w.consume(total_bytes - rem_bytes);
1739	}
1740
1741	fn flush(w: *Writer) Writer.Error!void {
1742	errdefer w.* = .failing;
1743	try Raw.rebaseInner(w, 0, w.buffer.len, false);
1744	}
1745
1746	pub fn finish(r: *Raw) Writer.Error!void {
1747	defer r.writer = .failing;
1748	try Raw.rebaseInner(&r.writer, 0, r.writer.buffer.len, true);
1749	// The footer is written in `rebaseInner` as part of the write vector
1750	}
1751
1752	fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
1753	errdefer w.* = .failing;
1754	try Raw.rebaseInner(w, preserve, capacity, false);
1755	}
1756
1757	fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void {
1758	const r: *Raw = @fieldParentPtr("writer", w);
1759	assert(preserve + capacity <= w.buffer.len);
1760	if (eos) assert(capacity == w.buffer.len);
1761
1762	var partial_header: [5]u8 = undefined;
1763	var footer_buf: [8]u8 = undefined;
1764	const preserved = @min(w.end, preserve);
1765	var remaining = w.buffer[0 .. w.end - preserved];
1766
1767	var vecs: [16][]const u8 = undefined;
1768	var vecs_n: usize = 0;
1769	while (remaining.len > max_block_size) { // not >= so there is always a block down below
1770	if (vecs_n == vecs.len) {
1771	try r.output.writeVecAll(&vecs);
1772	vecs_n = 0;
1773	}
1774	vecs[vecs_n + 0] = &full_header;
1775	vecs[vecs_n + 1] = remaining[0..max_block_size];
1776	r.hasher.update(vecs[vecs_n + 1]);
1777	vecs_n += 2;
1778	remaining = remaining[max_block_size..];
1779	}
1780
1781	// eos check required for empty block
1782	if (w.buffer.len - (remaining.len + preserved) < capacity or eos) {
1783	// A partial write is necessary to reclaim enough buffer space
1784	const block_size: u16 = @intCast(remaining.len);
1785	partial_header[0] = BlockHeader.int(.{ .final = eos, .kind = .stored });
1786	mem.writeInt(u16, partial_header[1..3], block_size, .little);
1787	mem.writeInt(u16, partial_header[3..5], ~block_size, .little);
1788
1789	if (vecs_n == vecs.len) {
1790	try r.output.writeVecAll(&vecs);
1791	vecs_n = 0;
1792	}
1793	vecs[vecs_n + 0] = &partial_header;
1794	vecs[vecs_n + 1] = remaining[0..block_size];
1795	r.hasher.update(vecs[vecs_n + 1]);
1796	vecs_n += 2;
1797	remaining = remaining[block_size..];
1798	assert(remaining.len == 0);
1799
1800	if (eos and r.hasher != .raw) {
1801	// the footer is done here instead of `flush` so it can be included in the vector
1802	var footer_w: Writer = .fixed(&footer_buf);
1803	r.hasher.writeFooter(&footer_w) catch unreachable;
1804	assert(footer_w.end != 0);
1805
1806	if (vecs_n == vecs.len) {
1807	try r.output.writeVecAll(&vecs);
1808	return r.output.writeAll(footer_w.buffered());
1809	} else {
1810	vecs[vecs_n] = footer_w.buffered();
1811	vecs_n += 1;
1812	}
1813	}
1814	}
1815
1816	try r.output.writeVecAll(vecs[0..vecs_n]);
1817	_ = w.consume(w.end - preserved - remaining.len);
1818	}
1819	};
1820
1821	test Raw {
1822	const data_buf = try std.testing.allocator.create([4 * 65536]u8);
1823	defer std.testing.allocator.destroy(data_buf);
1824	var prng: std.Random.DefaultPrng = .init(std.testing.random_seed);
1825	prng.random().bytes(data_buf);
1826	try std.testing.fuzz(data_buf, testFuzzedRawInput, .{});
1827	}
1828
1829	fn countVec(data: []const []const u8) usize {
1830	var bytes: usize = 0;
1831	for (data) |d| bytes += d.len;
1832	return bytes;
1833	}
1834
1835	fn testFuzzedRawInput(data_buf: *const [4 * 65536]u8, smith: *std.testing.Smith) !void {
1836	@disableInstrumentation();
1837	const HashedStoreWriter = struct {
1838	writer: Writer,
1839	state: enum {
1840	header,
1841	block_header,
1842	block_body,
1843	final_block_body,
1844	footer,
1845	end,
1846	},
1847	block_remaining: u16,
1848	container: flate.Container,
1849	data_hash: flate.Container.Hasher,
1850	data_size: usize,
1851	footer_hash: u32,
1852	footer_size: u32,
1853
1854	pub fn init(buf: []u8, container: flate.Container) @This() {
1855	return .{
1856	.writer = .{
1857	.vtable = &.{
1858	.drain = @This().drain,
1859	.flush = @This().flush,
1860	},
1861	.buffer = buf,
1862	},
1863	.state = .header,
1864	.block_remaining = 0,
1865	.container = container,
1866	.data_hash = .init(container),
1867	.data_size = 0,
1868	.footer_hash = undefined,
1869	.footer_size = undefined,
1870	};
1871	}
1872
1873	/// Note that this implementation is somewhat dependent on the implementation of
1874	/// `Raw` by expecting headers / footers to be continous in data elements. It
1875	/// also expects the header to be the same as `flate.Container.header` and for
1876	/// multiple streams to not be concatenated.
1877	fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
1878	errdefer w.* = .failing;
1879	var h: *@This() = @fieldParentPtr("writer", w);
1880
1881	var rem_splat = splat;
1882	var rem_data = data;
1883	var rem_data_elem: []const u8 = w.buffered();
1884
1885	data_loop: while (true) {
1886	const wanted = switch (h.state) {
1887	.header => h.container.headerSize(),
1888	.block_header => 5,
1889	.block_body, .final_block_body => h.block_remaining,
1890	.footer => h.container.footerSize(),
1891	.end => 1,
1892	};
1893
1894	if (wanted != 0) {
1895	while (rem_data_elem.len == 0) {
1896	rem_data_elem = rem_data[0];
1897	if (rem_data.len != 1) {
1898	rem_data = rem_data[1..];
1899	} else {
1900	if (rem_splat == 0) {
1901	break :data_loop;
1902	} else {
1903	rem_splat -= 1;
1904	}
1905	}
1906	}
1907	}
1908
1909	const bytes = Io.Limit.limited(wanted).sliceConst(rem_data_elem);
1910	rem_data_elem = rem_data_elem[bytes.len..];
1911
1912	switch (h.state) {
1913	.header => {
1914	if (bytes.len < wanted)
1915	return error.WriteFailed; // header eos
1916	if (!mem.eql(u8, bytes, h.container.header()))
1917	return error.WriteFailed; // wrong header
1918	h.state = .block_header;
1919	},
1920	.block_header => {
1921	if (bytes.len < wanted)
1922	return error.WriteFailed; // store block header eos
1923	const header: BlockHeader = @bitCast(@as(u3, @truncate(bytes[0])));
1924	if (header.kind != .stored)
1925	return error.WriteFailed; // non-store block
1926	const len = mem.readInt(u16, bytes[1..3], .little);
1927	const nlen = mem.readInt(u16, bytes[3..5], .little);
1928	if (nlen != ~len)
1929	return error.WriteFailed; // wrong nlen
1930	h.block_remaining = len;
1931	h.state = if (!header.final) .block_body else .final_block_body;
1932	},
1933	.block_body, .final_block_body => {
1934	h.data_hash.update(bytes);
1935	h.data_size += bytes.len;
1936	h.block_remaining -= @intCast(bytes.len);
1937	if (h.block_remaining == 0) {
1938	h.state = if (h.state != .final_block_body) .block_header else .footer;
1939	}
1940	},
1941	.footer => {
1942	if (bytes.len < wanted)
1943	return error.WriteFailed; // footer eos
1944	switch (h.container) {
1945	.raw => {},
1946	.gzip => {
1947	h.footer_hash = mem.readInt(u32, bytes[0..4], .little);
1948	h.footer_size = mem.readInt(u32, bytes[4..8], .little);
1949	},
1950	.zlib => {
1951	h.footer_hash = mem.readInt(u32, bytes[0..4], .big);
1952	},
1953	}
1954	h.state = .end;
1955	},
1956	.end => return error.WriteFailed, // data past end
1957	}
1958	}
1959
1960	w.end = 0;
1961	return Writer.countSplat(data, splat);
1962	}
1963
1964	fn flush(w: *Writer) Writer.Error!void {
1965	defer w.* = .failing; // Empties buffer even if state hasn't reached `end`
1966	_ = try @This().drain(w, &.{""}, 0);
1967	}
1968	};
1969
1970	const container = smith.value(flate.Container);
1971	var output: HashedStoreWriter = .init(&.{}, container);
1972	var expected_hash: flate.Container.Hasher = .init(container);
1973	var expected_size: u32 = 0;
1974	// 10 maximum blocks is the choosen limit since it is two more
1975	// than the maximum the implementation can output in one drain.
1976	const max_size = 10 * @as(u32, Raw.max_block_size);
1977
1978	var raw_buf: [2 * @as(usize, Raw.max_block_size)]u8 = undefined;
1979	const raw_buf_len = smith.valueWeighted(u32, &.{
1980	.value(u32, 0, @intCast(raw_buf.len)), // unbuffered
1981	.rangeAtMost(u32, 0, @intCast(raw_buf.len), 1),
1982	});
1983	var raw: Raw = try .init(&output.writer, raw_buf[0..raw_buf_len], container);
1984
1985	const data_buf_len: u32 = @intCast(data_buf.len);
1986	var vecs: [32][]const u8 = undefined;
1987	var vecs_n: usize = 0;
1988
1989	while (true) {
1990	const Op = packed struct {
1991	drain: bool = false,
1992	add_vec: bool = false,
1993	rebase: enum(u2) { none, rebase, flush } = .none,
1994
1995	pub const drain_only: @This() = .{ .drain = true };
1996	pub const add_vec_only: @This() = .{ .add_vec = true };
1997	pub const add_vec_and_drain: @This() = .{ .add_vec = true, .drain = true };
1998	pub const drain_and_rebase: @This() = .{ .drain = true, .rebase = .rebase };
1999	pub const drain_and_flush: @This() = .{ .drain = true, .rebase = .flush };
2000	};
2001
2002	const is_eos = expected_size == max_size or smith.eosWeightedSimple(7, 1);
2003	var op: Op = if (!is_eos) smith.valueWeighted(Op, &.{
2004	.value(Op, .add_vec_only, 5),
2005	.value(Op, .add_vec_and_drain, 1),
2006	.value(Op, .drain_and_rebase, 1),
2007	.value(Op, .drain_and_flush, 1),
2008	}) else .drain_only;
2009
2010	if (op.add_vec) {
2011	const max_write = max_size - expected_size;
2012	const buffered: u32 = @intCast(raw.writer.buffered().len + countVec(vecs[0..vecs_n]));
2013	const to_align = Raw.max_block_size - buffered % Raw.max_block_size;
2014	assert(to_align != 0); // otherwise, not helpful.
2015
2016	const max_data = @min(data_buf_len, max_write);
2017	const len = smith.valueWeighted(u32, &.{
2018	.rangeAtMost(u32, 0, max_data, 1),
2019	.rangeAtMost(u32, 0, @min(Raw.max_block_size, max_data), 4),
2020	.value(u32, @min(to_align, max_data), max_data), // @min 2nd arg is an edge-case
2021	});
2022	const off = smith.valueRangeAtMost(u32, 0, data_buf_len - len);
2023
2024	expected_size += len;
2025	vecs[vecs_n] = data_buf[off..][0..len];
2026	vecs_n += 1;
2027	op.drain |= vecs_n == vecs.len;
2028	}
2029
2030	op.drain |= is_eos;
2031	op.drain &= vecs_n != 0;
2032	if (op.drain) {
2033	const pattern_len: u32 = @intCast(vecs[vecs_n - 1].len);
2034	const pattern_len_z = @max(pattern_len, 1);
2035
2036	const max_write = max_size - (expected_size - pattern_len);
2037	const buffered: u32 = @intCast(raw.writer.buffered().len + countVec(vecs[0 .. vecs_n - 1]));
2038	const to_align = Raw.max_block_size - buffered % Raw.max_block_size;
2039	assert(to_align != 0); // otherwise, not helpful.
2040
2041	const max_splat = max_write / pattern_len_z;
2042	const weights: [3]std.testing.Smith.Weight = .{
2043	.rangeAtMost(u32, 0, max_splat, 1),
2044	.rangeAtMost(u32, 0, @min(
2045	Raw.max_block_size + pattern_len_z,
2046	max_write,
2047	) / pattern_len_z, 4),
2048	.value(u32, to_align / pattern_len_z, max_splat * 4),
2049	};
2050	const align_weight = to_align % pattern_len_z == 0 and to_align <= max_write;
2051	const n_weights = @as(u8, 2) + @intFromBool(align_weight);
2052	const splat = smith.valueWeighted(u32, weights[0..n_weights]);
2053
2054	expected_size = expected_size - pattern_len + pattern_len * splat; // splat may be zero
2055	for (vecs[0 .. vecs_n - 1]) |v| expected_hash.update(v);
2056	for (0..splat) |_| expected_hash.update(vecs[vecs_n - 1]);
2057	try raw.writer.writeSplatAll(vecs[0..vecs_n], splat);
2058	vecs_n = 0;
2059	}
2060
2061	switch (op.rebase) {
2062	.none => {},
2063	.rebase => {
2064	const capacity = smith.valueRangeAtMost(u32, 0, raw_buf_len);
2065	const preserve = smith.valueRangeAtMost(u32, 0, raw_buf_len - capacity);
2066	try raw.writer.rebase(preserve, capacity);
2067	},
2068	.flush => try raw.writer.flush(),
2069	}
2070
2071	if (is_eos) break;
2072	}
2073
2074	try raw.finish();
2075	try output.writer.flush();
2076
2077	try std.testing.expectEqual(.end, output.state);
2078	try std.testing.expectEqual(expected_size, output.data_size);
2079	switch (output.data_hash) {
2080	.raw => {},
2081	.gzip => |gz| {
2082	const expected_crc = expected_hash.gzip.crc.final();
2083	try std.testing.expectEqual(expected_crc, gz.crc.final());
2084	try std.testing.expectEqual(expected_crc, output.footer_hash);
2085	try std.testing.expectEqual(expected_size, output.footer_size);
2086	},
2087	.zlib => |zl| {
2088	const expected_adler = expected_hash.zlib.adler;
2089	try std.testing.expectEqual(expected_adler, zl.adler);
2090	try std.testing.expectEqual(expected_adler, output.footer_hash);
2091	},
2092	}
2093	}
2094
2095	/// Only performs huffman compression on data, does no matching.
2096	pub const Huffman = struct {
2097	/// After `finish` is called, all vtable calls with result in `error.WriteFailed`.
2098	writer: Writer,
2099	bit_writer: BitWriter,
2100	hasher: flate.Container.Hasher,
2101
2102	const max_tokens: u16 = 65535 - 1; // one is reserved for EOF
2103
2104	/// While there is no minimum buffer size, it is recommended
2105	/// to be at least `flate.max_window_len` to improve compression.
2106	///
2107	/// It is asserted `output` has a capacity of at least 8 bytes.
2108	pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Huffman {
2109	assert(output.buffer.len > 8);
2110
2111	try output.writeAll(container.header());
2112	return .{
2113	.writer = .{
2114	.buffer = buffer,
2115	.vtable = &.{
2116	.drain = Huffman.drain,
2117	.flush = Huffman.flush,
2118	.rebase = Huffman.rebase,
2119	},
2120	},
2121	.bit_writer = .init(output),
2122	.hasher = .init(container),
2123	};
2124	}
2125
2126	fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
2127	const h: *Huffman = @fieldParentPtr("writer", w);
2128	const min_block = @min(w.buffer.len, max_tokens);
2129	const pattern = data[data.len - 1];
2130
2131	const data_bytes = Writer.countSplat(data, splat);
2132	const total_bytes = w.end + data_bytes;
2133	var rem_bytes = total_bytes;
2134	var rem_splat = splat;
2135	var rem_data = data;
2136	var rem_data_elem: []const u8 = w.buffered();
2137
2138	assert(rem_bytes > min_block);
2139	while (rem_bytes > min_block) { // not >= to allow `min_block` blocks to be marked as final
2140	// also, it handles the case of `min_block` being zero (no buffer)
2141	const block_size: u16 = @min(rem_bytes, max_tokens);
2142	rem_bytes -= block_size;
2143
2144	// Count frequencies
2145	comptime assert(max_tokens != 65535);
2146	var freqs: [257]u16 = @splat(0);
2147	freqs[256] = 1;
2148
2149	const start_splat = rem_splat;
2150	const start_data = rem_data;
2151	const start_data_elem = rem_data_elem;
2152
2153	var block_limit: Io.Limit = .limited(block_size);
2154	while (true) {
2155	const bytes = block_limit.sliceConst(rem_data_elem);
2156	const is_pattern = rem_splat != splat and bytes.len == pattern.len;
2157
2158	const mul = if (!is_pattern) 1 else @backingInt(block_limit) / pattern.len;
2159	assert(mul != 0);
2160	if (is_pattern) assert(mul <= rem_splat + 1); // one more for `rem_data`
2161
2162	for (bytes) |b| freqs[b] += @intCast(mul);
2163	rem_data_elem = rem_data_elem[bytes.len..];
2164	block_limit = block_limit.subtract(bytes.len * mul).?;
2165
2166	if (rem_data_elem.len == 0) {
2167	rem_data_elem = rem_data[0];
2168	if (rem_data.len != 1) {
2169	rem_data = rem_data[1..];
2170	} else if (rem_splat >= mul) {
2171	// if the counter was not the pattern, `mul` is always one, otherwise,
2172	// `mul` contains `rem_data`, however one more needs subtracted anyways
2173	// since the next pattern is also being taken.
2174	rem_splat -= mul;
2175	} else {
2176	// All of `data` has been consumed.
2177	assert(block_limit == .nothing);
2178	assert(rem_bytes == 0);
2179	// Since `rem_bytes` and `block_limit` are zero, these won't be used.
2180	rem_data = undefined;
2181	rem_data_elem = undefined;
2182	rem_splat = undefined;
2183	}
2184	}
2185	if (block_limit == .nothing) break;
2186	}
2187
2188	// Output block
2189	rem_splat = start_splat;
2190	rem_data = start_data;
2191	rem_data_elem = start_data_elem;
2192	block_limit = .limited(block_size);
2193
2194	var codes_buf: CodesBuf = .init;
2195	if (try h.outputHeader(&freqs, &codes_buf, block_size, false)) |table| {
2196	while (true) {
2197	const bytes = block_limit.sliceConst(rem_data_elem);
2198	rem_data_elem = rem_data_elem[bytes.len..];
2199	block_limit = block_limit.subtract(bytes.len).?;
2200
2201	h.hasher.update(bytes);
2202	for (bytes) |b| {
2203	try h.bit_writer.write(table.codes[b], table.bits[b]);
2204	}
2205
2206	if (rem_data_elem.len == 0) {
2207	rem_data_elem = rem_data[0];
2208	if (rem_data.len != 1) {
2209	rem_data = rem_data[1..];
2210	} else if (rem_splat != 0) {
2211	rem_splat -= 1;
2212	} else {
2213	// All of `data` has been consumed.
2214	assert(block_limit == .nothing);
2215	assert(rem_bytes == 0);
2216	// Since `rem_bytes` and `block_limit` are zero, these won't be used.
2217	rem_data = undefined;
2218	rem_data_elem = undefined;
2219	rem_splat = undefined;
2220	}
2221	}
2222	if (block_limit == .nothing) break;
2223	}
2224	try h.bit_writer.write(table.codes[256], table.bits[256]);
2225	} else while (true) {
2226	// Store block
2227
2228	// Write data that is not a full vector element
2229	const in_pattern = rem_splat != splat;
2230	const vec_elem_i, const in_data =
2231	@subWithOverflow(data.len - (rem_data.len - @intFromBool(in_pattern)), 1);
2232	const is_elem = in_data == 0 and data[vec_elem_i].len == rem_data_elem.len;
2233
2234	if (!is_elem or rem_data_elem.len > @backingInt(block_limit)) {
2235	block_limit = block_limit.subtract(rem_data_elem.len) orelse {
2236	try h.bit_writer.output.writeAll(rem_data_elem[0..@backingInt(block_limit)]);
2237	h.hasher.update(rem_data_elem[0..@backingInt(block_limit)]);
2238	rem_data_elem = rem_data_elem[@backingInt(block_limit)..];
2239	assert(rem_data_elem.len != 0);
2240	break;
2241	};
2242	try h.bit_writer.output.writeAll(rem_data_elem);
2243	h.hasher.update(rem_data_elem);
2244	} else {
2245	// Put `rem_data_elem` back in `rem_data`
2246	if (!in_pattern) {
2247	rem_data = data[vec_elem_i..];
2248	} else {
2249	rem_splat += 1;
2250	}
2251	}
2252	rem_data_elem = undefined; // it is always updated below
2253
2254	// Send through as much of the original vector as possible
2255	var vec_n: usize = 0;
2256	var vlimit = block_limit;
2257	const vec_splat = while (rem_data[vec_n..].len != 1) {
2258	vlimit = vlimit.subtract(rem_data[vec_n].len) orelse break 1;
2259	vec_n += 1;
2260	} else vec_splat: {
2261	// For `pattern.len == 0`, the value of `vec_splat` does not matter.
2262	const vec_splat = @backingInt(vlimit) / @max(1, pattern.len);
2263	if (pattern.len != 0) assert(vec_splat <= rem_splat + 1);
2264	vlimit = vlimit.subtract(pattern.len * vec_splat).?;
2265	vec_n += 1;
2266	break :vec_splat vec_splat;
2267	};
2268
2269	const n = if (vec_n != 0) n: {
2270	assert(@backingInt(block_limit) - @backingInt(vlimit) ==
2271	Writer.countSplat(rem_data[0..vec_n], vec_splat));
2272	break :n try h.bit_writer.output.writeSplat(rem_data[0..vec_n], vec_splat);
2273	} else 0; // Still go into the case below to advance the vector
2274	block_limit = block_limit.subtract(n).?;
2275	var consumed: Io.Limit = .limited(n);
2276
2277	while (rem_data.len != 1) {
2278	const elem = rem_data[0];
2279	rem_data = rem_data[1..];
2280	consumed = consumed.subtract(elem.len) orelse {
2281	h.hasher.update(elem[0..@backingInt(consumed)]);
2282	rem_data_elem = elem[@backingInt(consumed)..];
2283	break;
2284	};
2285	h.hasher.update(elem);
2286	} else {
2287	if (pattern.len == 0) {
2288	// All of `data` has been consumed. However, the general
2289	// case below does not work since it divides by zero.
2290	assert(consumed == .nothing);
2291	assert(block_limit == .nothing);
2292	assert(rem_bytes == 0);
2293	// Since `rem_bytes` and `block_limit` are zero, these won't be used.
2294	rem_splat = undefined;
2295	rem_data = undefined;
2296	rem_data_elem = undefined;
2297	break;
2298	}
2299
2300	const splatted = @backingInt(consumed) / pattern.len;
2301	const partial = @backingInt(consumed) % pattern.len;
2302	for (0..splatted) |_| h.hasher.update(pattern);
2303	h.hasher.update(pattern[0..partial]);
2304
2305	const taken_splat = splatted + 1;
2306	if (rem_splat >= taken_splat) {
2307	rem_splat -= taken_splat;
2308	rem_data_elem = pattern[partial..];
2309	} else {
2310	// All of `data` has been consumed.
2311	assert(partial == 0);
2312	assert(block_limit == .nothing);
2313	assert(rem_bytes == 0);
2314	// Since `rem_bytes` and `block_limit` are zero, these won't be used.
2315	rem_data = undefined;
2316	rem_data_elem = undefined;
2317	rem_splat = undefined;
2318	}
2319	}
2320
2321	if (block_limit == .nothing) break;
2322	}
2323	}
2324
2325	if (rem_bytes > data_bytes) {
2326	assert(rem_bytes - data_bytes == rem_data_elem.len);
2327	assert(&rem_data_elem[0] == &w.buffer[total_bytes - rem_bytes]);
2328	}
2329	return w.consume(total_bytes - rem_bytes);
2330	}
2331
2332	fn flush(w: *Writer) Writer.Error!void {
2333	errdefer w.* = .failing;
2334	const h: *Huffman = @fieldParentPtr("writer", w);
2335	try Huffman.rebaseInner(w, 0, w.buffer.len, false);
2336	try h.bit_writer.byteAlignBlocks();
2337	}
2338
2339	pub fn finish(h: *Huffman) Writer.Error!void {
2340	defer h.writer = .failing;
2341	try Huffman.rebaseInner(&h.writer, 0, h.writer.buffer.len, true);
2342	try h.bit_writer.output.rebase(0, 1);
2343	h.bit_writer.byteAlign();
2344	try h.hasher.writeFooter(h.bit_writer.output);
2345	}
2346
2347	fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
2348	errdefer w.* = .failing;
2349	try Huffman.rebaseInner(w, preserve, capacity, false);
2350	}
2351
2352	fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void {
2353	const h: *Huffman = @fieldParentPtr("writer", w);
2354	assert(preserve + capacity <= w.buffer.len);
2355	if (eos) assert(capacity == w.buffer.len);
2356
2357	const preserved = @min(w.end, preserve);
2358	var remaining = w.buffer[0 .. w.end - preserved];
2359	while (remaining.len > max_tokens) { // not >= so there is always a block down below
2360	const bytes = remaining[0..max_tokens];
2361	remaining = remaining[max_tokens..];
2362	try h.outputBytes(bytes, false);
2363	}
2364
2365	// eos check required for empty block
2366	if (w.buffer.len - (remaining.len + preserved) < capacity or eos) {
2367	const bytes = remaining;
2368	remaining = &.{};
2369	try h.outputBytes(bytes, eos);
2370	}
2371
2372	_ = w.consume(w.end - preserved - remaining.len);
2373	}
2374
2375	fn outputBytes(h: *Huffman, bytes: []const u8, eos: bool) Writer.Error!void {
2376	comptime assert(max_tokens != 65535);
2377	assert(bytes.len <= max_tokens);
2378	var freqs: [257]u16 = @splat(0);
2379	freqs[256] = 1;
2380	for (bytes) |b| freqs[b] += 1;
2381	h.hasher.update(bytes);
2382
2383	var codes_buf: CodesBuf = .init;
2384	if (try h.outputHeader(&freqs, &codes_buf, @intCast(bytes.len), eos)) |table| {
2385	for (bytes) |b| {
2386	try h.bit_writer.write(table.codes[b], table.bits[b]);
2387	}
2388	try h.bit_writer.write(table.codes[256], table.bits[256]);
2389	} else {
2390	try h.bit_writer.output.writeAll(bytes);
2391	}
2392	}
2393
2394	const CodesBuf = struct {
2395	dyn_codes: [258]u16,
2396	dyn_bits: [258]u4,
2397
2398	pub const init: CodesBuf = .{
2399	.dyn_codes = @as([257]u16, undefined) ++ .{0},
2400	.dyn_bits = @as([257]u4, @splat(0)) ++ .{1},
2401	};
2402	};
2403
2404	/// Returns null if the block is stored.
2405	fn outputHeader(
2406	h: *Huffman,
2407	freqs: *const [257]u16,
2408	buf: *CodesBuf,
2409	bytes: u16,
2410	eos: bool,
2411	) Writer.Error!?struct {
2412	codes: *const [257]u16,
2413	bits: *const [257]u4,
2414	} {
2415	assert(freqs[256] == 1);
2416	const dyn_codes_bitsize, _ = huffman.build(
2417	freqs,
2418	buf.dyn_codes[0..257],
2419	buf.dyn_bits[0..257],
2420	15,
2421	true,
2422	);
2423
2424	var clen_values: [258]u8 = undefined;
2425	var clen_extra: [258]u8 = undefined;
2426	var clen_freqs: [19]u16 = @splat(0);
2427	const clen_len, const clen_extra_bitsize = buildClen(
2428	&buf.dyn_bits,
2429	&clen_values,
2430	&clen_extra,
2431	&clen_freqs,
2432	);
2433
2434	var clen_codes: [19]u16 = undefined;
2435	var clen_bits: [19]u4 = @splat(0);
2436	const clen_codes_bitsize, _ = huffman.build(
2437	&clen_freqs,
2438	&clen_codes,
2439	&clen_bits,
2440	7,
2441	false,
2442	);
2443	const hclen = clenHlen(clen_freqs);
2444
2445	const dynamic_bitsize = @as(u32, 14) +
2446	(4 + @as(u6, hclen)) * 3 + clen_codes_bitsize + clen_extra_bitsize +
2447	dyn_codes_bitsize;
2448	const fixed_bitsize = n: {
2449	const freq7 = 1; // eos
2450	var freq9: u16 = 0;
2451	for (freqs[144..256]) |f| freq9 += f;
2452	const freq8: u16 = bytes - freq9;
2453	break :n @as(u32, freq7) * 7 + @as(u32, freq8) * 8 + @as(u32, freq9) * 9;
2454	};
2455	const stored_bitsize = n: {
2456	const stored_align_bits = -%(h.bit_writer.buffered_n +% 3);
2457	break :n stored_align_bits + @as(u32, 32) + @as(u32, bytes) * 8;
2458	};
2459
2460	if (stored_bitsize <= @min(dynamic_bitsize, fixed_bitsize)) {
2461	try h.bit_writer.write(BlockHeader.int(.{ .kind = .stored, .final = eos }), 3);
2462	try h.bit_writer.output.rebase(0, 5);
2463	h.bit_writer.byteAlign();
2464	h.bit_writer.output.writeInt(u16, bytes, .little) catch unreachable;
2465	h.bit_writer.output.writeInt(u16, ~bytes, .little) catch unreachable;
2466	return null;
2467	}
2468
2469	if (fixed_bitsize <= dynamic_bitsize) {
2470	try h.bit_writer.write(BlockHeader.int(.{ .final = eos, .kind = .fixed }), 3);
2471	return .{
2472	.codes = token.fixed_lit_codes[0..257],
2473	.bits = token.fixed_lit_bits[0..257],
2474	};
2475	} else {
2476	try h.bit_writer.write(BlockHeader.Dynamic.int(.{
2477	.regular = .{ .final = eos, .kind = .dynamic },
2478	.hlit = 0,
2479	.hdist = 0,
2480	.hclen = hclen,
2481	}), 17);
2482	try h.bit_writer.writeClen(
2483	hclen,
2484	clen_values[0..clen_len],
2485	clen_extra[0..clen_len],
2486	clen_codes,
2487	clen_bits,
2488	);
2489	return .{ .codes = buf.dyn_codes[0..257], .bits = buf.dyn_bits[0..257] };
2490	}
2491	}
2492	};
2493
2494	test Huffman {
2495	const fbufs = try testingFreqBufs();
2496	defer std.testing.allocator.destroy(fbufs);
2497	try std.testing.fuzz(fbufs, testFuzzedHuffmanInput, .{});
2498	}
2499
2500	fn fuzzedHuffmanDrainSpaceLimit(max_drain: usize, written: usize, eos: bool) usize {
2501	var block_lim = math.divCeil(usize, max_drain, Huffman.max_tokens) catch unreachable;
2502	block_lim = @max(block_lim, @intFromBool(eos));
2503	const footer_overhead = @as(u8, 8) * @intFromBool(eos);
2504	// 6 for a raw block header (the block header may span two bytes)
2505	return written + 6 * block_lim + max_drain + footer_overhead;
2506	}
2507
2508	/// This function is derived from `testFuzzedRawInput` with a few changes for fuzzing `Huffman`.
2509	fn testFuzzedHuffmanInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void {
2510	@disableInstrumentation();
2511	const container = smith.value(flate.Container);
2512	var flate_buf: [2 * 65536]u8 = undefined;
2513	var flate_w: Writer = .fixed(&flate_buf);
2514	var expected_hash: flate.Container.Hasher = .init(container);
2515	var expected_size: u32 = 0;
2516	const max_size = 4 * @as(u32, Huffman.max_tokens);
2517
2518	var h_buf: [2 * @as(usize, Huffman.max_tokens)]u8 = undefined;
2519	const h_buf_len = smith.valueWeighted(u32, &.{
2520	.value(u32, 0, @intCast(h_buf.len)), // unbuffered
2521	.rangeAtMost(u32, 0, @intCast(h_buf.len), 1),
2522	});
2523	var h: Huffman = try .init(&flate_w, h_buf[0..h_buf_len], container);
2524
2525	var vecs: [32][]const u8 = undefined;
2526	var vecs_n: usize = 0;
2527
2528	while (true) {
2529	const Op = packed struct {
2530	drain: bool = false,
2531	add_vec: bool = false,
2532	rebase: enum(u2) { none, rebase, flush } = .none,
2533
2534	pub const drain_only: @This() = .{ .drain = true };
2535	pub const add_vec_only: @This() = .{ .add_vec = true };
2536	pub const add_vec_and_drain: @This() = .{ .add_vec = true, .drain = true };
2537	pub const drain_and_rebase: @This() = .{ .drain = true, .rebase = .rebase };
2538	pub const drain_and_flush: @This() = .{ .drain = true, .rebase = .flush };
2539	};
2540
2541	const is_eos = expected_size == max_size or smith.eosWeightedSimple(7, 1);
2542	var op: Op = if (!is_eos) smith.valueWeighted(Op, &.{
2543	.value(Op, .add_vec_only, 5),
2544	.value(Op, .add_vec_and_drain, 1),
2545	.value(Op, .drain_and_rebase, 1),
2546	.value(Op, .drain_and_flush, 1),
2547	}) else .drain_only;
2548
2549	if (op.add_vec) {
2550	const max_write = max_size - expected_size;
2551	const buffered: u32 = @intCast(h.writer.buffered().len + countVec(vecs[0..vecs_n]));
2552	const to_align = Huffman.max_tokens - buffered % Huffman.max_tokens;
2553	assert(to_align != 0); // otherwise, not helpful.
2554
2555	const data_buf = &fbufs[
2556	smith.valueWeighted(u1, &.{
2557	.value(FreqBufIndex, .gradient, 3),
2558	.value(FreqBufIndex, .random, 1),
2559	})
2560	];
2561	const data_buf_len: u32 = @intCast(data_buf.len);
2562
2563	const max_data = @min(data_buf_len, max_write);
2564	const len = smith.valueWeighted(u32, &.{
2565	.rangeAtMost(u32, 0, max_data, 1),
2566	.rangeAtMost(u32, 0, @min(Huffman.max_tokens, max_data), 4),
2567	.value(u32, @min(to_align, max_data), max_data), // @min 2nd arg is an edge-case
2568	});
2569	const off = smith.valueRangeAtMost(u32, 0, data_buf_len - len);
2570
2571	expected_size += len;
2572	vecs[vecs_n] = data_buf[off..][0..len];
2573	vecs_n += 1;
2574	op.drain |= vecs_n == vecs.len;
2575	}
2576
2577	op.drain |= is_eos;
2578	op.drain &= vecs_n != 0;
2579	if (op.drain) {
2580	const pattern_len: u32 = @intCast(vecs[vecs_n - 1].len);
2581	const pattern_len_z = @max(pattern_len, 1);
2582
2583	const max_write = max_size - (expected_size - pattern_len);
2584	const buffered: u32 = @intCast(h.writer.buffered().len + countVec(vecs[0 .. vecs_n - 1]));
2585	const to_align = Huffman.max_tokens - buffered % Huffman.max_tokens;
2586	assert(to_align != 0); // otherwise, not helpful.
2587
2588	const max_splat = max_write / pattern_len_z;
2589	const weights: [3]std.testing.Smith.Weight = .{
2590	.rangeAtMost(u32, 0, max_splat, 1),
2591	.rangeAtMost(u32, 0, @min(
2592	Huffman.max_tokens + pattern_len_z,
2593	max_write,
2594	) / pattern_len_z, 4),
2595	.value(u32, to_align / pattern_len_z, max_splat * 4),
2596	};
2597	const align_weight = to_align % pattern_len_z == 0 and to_align <= max_write;
2598	const n_weights = @as(u8, 2) + @intFromBool(align_weight);
2599	const splat = smith.valueWeighted(u32, weights[0..n_weights]);
2600
2601	expected_size = expected_size - pattern_len + pattern_len * splat; // splat may be zero
2602	for (vecs[0 .. vecs_n - 1]) |v| expected_hash.update(v);
2603	for (0..splat) |_| expected_hash.update(vecs[vecs_n - 1]);
2604
2605	const max_space = fuzzedHuffmanDrainSpaceLimit(
2606	buffered + pattern_len * splat,
2607	flate_w.buffered().len,
2608	false,
2609	);
2610	h.writer.writeSplatAll(vecs[0..vecs_n], splat) catch
2611	return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {};
2612	if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;
2613
2614	vecs_n = 0;
2615	}
2616
2617	if (op.rebase != .none) {
2618	const capacity = smith.valueRangeAtMost(u32, 0, h_buf_len);
2619	const preserve = smith.valueRangeAtMost(u32, 0, h_buf_len - capacity);
2620
2621	const max_space = fuzzedHuffmanDrainSpaceLimit(
2622	h.writer.buffered().len,
2623	flate_w.buffered().len,
2624	false,
2625	) + @as(usize, 8) * @intFromBool(op.rebase == .flush); // Overhead from byte alignment
2626	switch (op.rebase) {
2627	.none => unreachable,
2628	.rebase => h.writer.rebase(preserve, capacity) catch
2629	return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {},
2630	.flush => h.writer.flush() catch
2631	return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {},
2632	}
2633	if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;
2634	}
2635
2636	if (is_eos) break;
2637	}
2638
2639	const max_space = fuzzedHuffmanDrainSpaceLimit(
2640	h.writer.buffered().len,
2641	flate_w.buffered().len,
2642	true,
2643	);
2644	h.finish() catch return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {};
2645	if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;
2646
2647	try testingCheckDecompressedMatches(flate_w.buffered(), expected_size, expected_hash);
2648	}