跳转到内容

std.compress.flate.Compress

标准库Zig 0.17.1官方原文
源码std/compress/flate/Compress.zig

第 1 行

静态分配约 224K:128K 查找表、96K 词元。

error.WriteFailed 始终来自底层写入器。发生 error.WriteFailed 后,.writer 变为 .failing,且不可恢复。

finish 之后,流已经结束,写入器也会变为 .failing。此行为同样适用于 Raw 和 Huffman。

字段

writer: Writer

调用 finish 后,所有虚函数表调用均产生 error.WriteFailed。

history_len: u16
history_end_unhashed: bool
bit_writer: BitWriter
buffered_tokens: struct {
    /// `TokenBufferEntryHeader` 及其尾随数据的列表。
    list: [@as(usize, block_tokens) * 3]u8,
    pos: u32,
    n: u16,
    lit_freqs: [286]u16,
    dist_freqs: [30]u16,

    pub const empty: @This() = .{
        .list = undefined,
        .pos = 0,
        .n = 0,
        .lit_freqs = @splat(0),
        .dist_freqs = @splat(0),
    };
}
lookup: struct {
    /// 索引是四字节序列的哈希。
    ///
    /// 值是具有相同哈希的前四个字节在 `chain` 中的位置。
    head: [1 << lookup_hash_bits]PackedOptionalU15,
    /// 各值表示向历史数据回溯至相同哈希所需的字节数,且该值非零。
    ///
    /// 链索引与相对最新历史字节的位置之间的关系为
    /// `chain_pos -% chain_index = history_index`。
    chain: [32768]PackedOptionalU15,
    /// `chain` 中对应历史最新字节的索引。
    chain_pos: u15,
}
container: flate.Container
hasher: flate.Container.Hasher
opts: Options

std.compress.flate.Compress.addHash

函数

第 543 行

fn addHash(c: *Compress, i: usize, h: Hash) void

参数

c: *Compress
i: usize
h: Hash

std.compress.flate.Compress.assert

别名

第 23 行

别名目标 std.debug.assert

std.compress.flate.Compress.betterMatchLen

函数

第 577 行

若匹配更短,返回值可为任意 <= old 的值。

fn betterMatchLen(old: u16, prev: []const u8, bytes: []const u8) u16

参数

old: u16
prev: []const u8
bytes: []const u8

用法示例

test betterMatchLen {
    try std.testing.fuzz({}, testFuzzedMatchLen, .{});
}

std.compress.flate.Compress.BitWriter

容器

第 85 行

字段

output: *Writer
buffered: u7
buffered_n: u3

std.compress.flate.Compress.BitWriter.byteAlign

函数

第 114 行

断言无需调整基址即可向 b.output 写入一个字节。

pub fn byteAlign(b: *BitWriter) void

参数

b: *BitWriter

std.compress.flate.Compress.BitWriter.byteAlignBlocks

函数

第 122 行

仅使用空 flate 分组进行字节对齐

pub fn byteAlignBlocks(b: *BitWriter) Writer.Error!void

参数

b: *BitWriter

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.BitWriter.init

函数

第 90 行

pub fn init(w: *Writer) BitWriter

参数

w: *Writer

std.compress.flate.Compress.BitWriter.write

函数

第 99 行

断言 bits 经过零扩展

pub fn write(b: *BitWriter, bits: u56, n: u6) Writer.Error!void

参数

b: *BitWriter
bits: u56
n: u6

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.BitWriter.writeClen

函数

第 150 行

pub fn writeClen( b: *BitWriter, hclen: u4, clen_values: []u8, clen_extra: []u8, clen_codes: [19]u16, clen_bits: [19]u4, ) Writer.Error!void

参数

b: *BitWriter
hclen: u4
clen_values: []u8
clen_extra: []u8
clen_codes: [19]u16
clen_bits: [19]u4

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.block_tokens

常量

第 191 行

输出为块之前累积的 token 数量。 最大值为 math.maxInt(u16) - 1,因为要保留一个 token 作为块结束标记。

u16

std.compress.flate.Compress.BlockHeader

容器

第 207 行

字段

final: bool
kind: enum(u2) { stored, fixed, dynamic, _ }

std.compress.flate.Compress.BlockHeader.Dynamic

容器

第 215 行

字段

regular: BlockHeader
hlit: u5
hdist: u5
hclen: u4

std.compress.flate.Compress.BlockHeader.Dynamic.int

函数

第 221 行

pub fn int(h: Dynamic) u17

参数

h: Dynamic

std.compress.flate.Compress.BlockHeader.int

函数

第 211 行

pub fn int(h: BlockHeader) u3

参数

std.compress.flate.Compress.buildClen

类型函数

第 772 行

返回值的数量,后跟额外位的位数。

fn buildClen( dyn_bits: []const u4, out_values: []u8, out_extra: []u8, out_freqs: *[19]u16, ) struct { u16, u16 }

参数

dyn_bits: []const u4
out_values: []u8
out_extra: []u8
out_freqs: *[19]u16

用法示例

test buildClen {
    // dyn_bits: []u4,
    // out_values: *[288 + 30]u8,
    // out_extra: *[288 + 30]u8,
    // out_freqs: *[19]u16,
    // struct { u16, u16 }
    var out_values: [288 + 30]u8 = undefined;
    var out_extra: [288 + 30]u8 = undefined;
    var out_freqs: [19]u16 = @splat(0);
    const len, const extra_bitsize = buildClen(&([_]u4{
        1, // A
        2, 2, // B
        3, 3, 3, // C
        4, 4, 4, 4, // D
        5, // E
        5, 5, 5, 5, 5, 5, //
        5, 5, 5, 5, 5, 5,
        5, 5,
        0, 1, // F
        0, 0, 1, // G
    } ++ @as([138 + 10]u4, @splat(0)) // H
    ), &out_values, &out_extra, &out_freqs);
    try std.testing.expectEqualSlices(u8, &.{
        1, // A
        2, 2, // B
        3, 3, 3, // C
        4, 16, // D
        5, 16, 16, 5, 5, // E
        0, 1, // F
        0, 0, 1, // G
        18, 17, // H
    }, out_values[0..len]);
    try std.testing.expectEqualSlices(u8, &.{
        0, // A
        0, 0, // B
        0, 0, 0, // C
        0, (0), // D
        0, (3), (3), 0, 0, // E
        0, 0, // F
        0, 0, 0, // G
        (127), (7), // H
    }, out_extra[0..len]);
    try std.testing.expectEqual(2 + 2 + 2 + 7 + 3, extra_bitsize);
    try std.testing.expectEqualSlices(u16, &.{
        3, 3, 2, 3, 1, 3, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        3, 1, 1,
    }, &out_freqs);
}

std.compress.flate.Compress.builtin

常量

第 19 行

std.compress.flate.Compress.clenHlen

函数

第 739 行

fn clenHlen(freqs: [19]u16) u4

参数

freqs: [19]u16

用法示例

test clenHlen {
    var freqs: [19]u16 = @splat(0);
    try std.testing.expectEqual(0, clenHlen(freqs));
    for (token.codegen_order, 1..) |i, len| {
        freqs[i] = 1;
        try std.testing.expectEqual(len -| 4, clenHlen(freqs));
        freqs[i] = 0;
    }
}

std.compress.flate.Compress.Compress

别名

第 27 行

别名目标 std.compress.flate.Compress

std.compress.flate.Compress.countVec

函数

第 1829 行

fn countVec(data: []const []const u8) usize

参数

data: []const []const u8

std.compress.flate.Compress.drain

函数

第 345 行

fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize

参数

w: *Writer
data: []const []const u8
splat: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.empty

常量

第 60 行

@This()

std.compress.flate.Compress.finish

函数

第 363 行

pub fn finish(c: *Compress) Writer.Error!void

参数

c: *Compress

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.flate

别名

第 29 行

别名目标 std.compress.flate

std.compress.flate.Compress.flush

函数

第 356 行

fn flush(w: *Writer) Writer.Error!void

参数

w: *Writer

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.FreqBufIndex

容器

第 1421 行

字段

gradient
random

std.compress.flate.Compress.fuzzedHuffmanDrainSpaceLimit

函数

第 2500 行

fn fuzzedHuffmanDrainSpaceLimit(max_drain: usize, written: usize, eos: bool) usize

参数

max_drain: usize
written: usize
eos: bool

std.compress.flate.Compress.hash

函数

第 267 行

fn hash(x: u32) Hash

参数

x: u32

std.compress.flate.Compress.Hash

类型

第 193 行

std.compress.flate.Compress.huffman

命名空间

第 1062 行

霍夫曼树构造。

构建霍夫曼树的方法[取自 zlib] (https://github.com/madler/zlib/blob/v1.3.1/trees.c#L625),并作了部分修改。

std.compress.flate.Compress.Huffman

容器

第 2096 行

仅对数据进行 Huffman 压缩,不执行匹配。

字段

writer: Writer

调用 finish 后,所有虚函数表调用均产生 error.WriteFailed。

bit_writer: BitWriter
hasher: flate.Container.Hasher

std.compress.flate.Compress.huffman.build

类型函数

第 1102 行

返回编码 freqs 所需的总位数,以及最后一个非零位数的索引。 freqs[i] == 0 时,out_codes[i] 未定义。 断言 out_bits 已全部置零。 断言 out_bits.len 至少为一,若允许不完整树;否则至少为二。

pub fn build( freqs: []const u16, out_codes: []u16, out_bits: []u4, max_bits: u4, incomplete_allowed: bool, ) struct { u32, u16 }

参数

freqs: []const u16
out_codes: []u16
out_bits: []u4
max_bits: u4
incomplete_allowed: bool

用法示例

test build {
    var codes: [8]u16 = undefined;
    var bits: [8]u4 = undefined;

    const regular_freqs: [8]u16 = .{ 1, 1, 0, 8, 8, 0, 2, 4 };
    // 上述频率对应的最优树为
    // 4             1   1
    //                \ /
    // 3           2   #
    //              \ /
    // 2   8   8 4   #
    //      \ /   \ /
    // 1     #     #
    //        \   /
    // 0        #
    bits = @splat(0);
    var n, var lnz = build(&regular_freqs, &codes, &bits, 15, true);
    codes[2] = 0;
    codes[5] = 0;
    try std.testing.expectEqualSlices(u4, &.{ 4, 4, 0, 2, 2, 0, 3, 2 }, &bits);
    try std.testing.expectEqualSlices(u16, &.{
        0b0111, 0b1111, 0, 0b00, 0b10, 0, 0b011, 0b01,
    }, &codes);
    try std.testing.expectEqual(54, n);
    try std.testing.expectEqual(7, lnz);
    // 限制为 3 位时,变为
    // 3        1   1 2   4
    //           \ /   \ /
    // 2   8   8  #     #
    //      \ /    \   /
    // 1     #       #
    //        \     /
    // 0         #
    bits = @splat(0);
    n, lnz = build(&regular_freqs, &codes, &bits, 3, true);
    codes[2] = 0;
    codes[5] = 0;
    try std.testing.expectEqualSlices(u4, &.{ 3, 3, 0, 2, 2, 0, 3, 3 }, &bits);
    try std.testing.expectEqualSlices(u16, &.{
        0b001, 0b101, 0, 0b00, 0b10, 0, 0b011, 0b111,
    }, &codes);
    try std.testing.expectEqual(56, n);
    try std.testing.expectEqual(7, lnz);

    // 空树。必须至少存在一个代码
    bits = @splat(0);
    n, lnz = build(&.{ 0, 0 }, codes[0..2], bits[0..2], 15, true);
    try std.testing.expectEqualSlices(u4, &.{ 1, 0 }, bits[0..2]);
    try std.testing.expectEqual(0b0, codes[0]);
    try std.testing.expectEqual(0, n);
    try std.testing.expectEqual(0, lnz);

    // 检查所有无法补全的频数均已补全
    for ([_][2]u16{ .{ 0, 0 }, .{ 0, 1 }, .{ 1, 0 } }) |incomplete| {
        // 空树。必须同时存在两个代码,以避免不完整树
        bits = @splat(0);
        n, lnz = build(&incomplete, codes[0..2], bits[0..2], 15, false);
        try std.testing.expectEqualSlices(u4, &.{ 1, 1 }, bits[0..2]);
        try std.testing.expectEqualSlices(u16, &.{ 0b0, 0b1 }, codes[0..2]);
        try std.testing.expectEqual(incomplete[0] + incomplete[1], n);
        try std.testing.expectEqual(1, lnz);
    }

    try std.testing.fuzz({}, checkFuzzedBuildFreqs, .{});
}

std.compress.flate.Compress.huffman.buildBits

函数

第 1186 行

fn buildBits( out_bits: []u4, bit_counts: *[16]u16, parent_nodes: *[max_nodes]Node.Index, sorted: []Node.Index, max_bits: u4, ) void

参数

out_bits: []u4
bit_counts: *[16]u16
parent_nodes: *[max_nodes]Node.Index
sorted: []Node.Index
max_bits: u4

std.compress.flate.Compress.huffman.buildValues

函数

第 1244 行

fn buildValues(freqs: []const u16, out_codes: []u16, bits: []u4, bit_counts: [16]u16) u32

参数

freqs: []const u16
out_codes: []u16
bits: []u4
bit_counts: [16]u16

std.compress.flate.Compress.huffman.checkFuzzedBuildFreqs

函数

第 1328 行

fn checkFuzzedBuildFreqs(_: void, smith: *std.testing.Smith) !void

参数

_: void
smith: *std.testing.Smith

std.compress.flate.Compress.Huffman.CodesBuf

容器

第 2394 行

字段

dyn_codes: [258]u16
dyn_bits: [258]u4

std.compress.flate.Compress.Huffman.CodesBuf.init

常量

第 2398 行

CodesBuf

std.compress.flate.Compress.Huffman.drain

函数

第 2126 行

fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize

参数

w: *Writer
data: []const []const u8
splat: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Huffman.finish

函数

第 2339 行

pub fn finish(h: *Huffman) Writer.Error!void

参数

h: *Huffman

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Huffman.flush

函数

第 2332 行

fn flush(w: *Writer) Writer.Error!void

参数

w: *Writer

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.huffman.heapRemoveRoot

函数

第 1092 行

fn heapRemoveRoot(nodes: []Node, heap: []Node.Index) void

参数

nodes: []Node
heap: []Node.Index

std.compress.flate.Compress.huffman.heapSiftDown

函数

第 1078 行

fn heapSiftDown(nodes: []Node, heap: []Node.Index, start: usize) void

参数

nodes: []Node
heap: []Node.Index
start: usize

std.compress.flate.Compress.Huffman.init

函数

第 2108 行

虽然没有最小缓冲区大小要求,但建议 至少为 flate.max_window_len,以改善压缩效果。

断言 output 的容量至少为 8 字节。

pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Huffman

参数

output: *Writer
buffer: []u8
container: flate.Container

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.huffman.max_leafs

常量

第 1063 行

std.compress.flate.Compress.huffman.max_nodes

常量

第 1064 行

std.compress.flate.Compress.Huffman.max_tokens

常量

第 2102 行

u16

std.compress.flate.Compress.huffman.Node

容器

第 1066 行

字段

depth: u16
freq: u16

std.compress.flate.Compress.huffman.Node.Index

类型

第 1070 行

std.compress.flate.Compress.huffman.Node.smaller

函数

第 1073 行

freq 比 depth 更重要

pub fn smaller(a: Node, b: Node) bool

参数

a: Node
b: Node

std.compress.flate.Compress.Huffman.outputBytes

函数

第 2375 行

fn outputBytes(h: *Huffman, bytes: []const u8, eos: bool) Writer.Error!void

参数

h: *Huffman
bytes: []const u8
eos: bool

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Huffman.outputHeader

函数

第 2405 行

若块为存储块则返回 null。

fn outputHeader( h: *Huffman, freqs: *const [257]u16, buf: *CodesBuf, bytes: u16, eos: bool, ) Writer.Error!?struct { codes: *const [257]u16, bits: *const [257]u4, }

参数

h: *Huffman
freqs: *const [257]u16
buf: *CodesBuf
bytes: u16
eos: bool

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Huffman.rebase

函数

第 2347 行

fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void

参数

w: *Writer
preserve: usize
capacity: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Huffman.rebaseInner

函数

第 2352 行

fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void

参数

w: *Writer
preserve: usize
capacity: usize
eos: bool

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.init

函数

第 303 行

断言 buffer 至少有 flate.max_window_len 字节。 断言 output 容量至少为 8 字节。

pub fn init( output: *Writer, buffer: []u8, container: flate.Container, opts: Options, ) Writer.Error!Compress

参数

output: *Writer
buffer: []u8
container: flate.Container
opts: Options

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Io

别名

第 24 行

别名目标 std.Io

std.compress.flate.Compress.lookup_hash_bits

常量

第 192 行

std.compress.flate.Compress.matchAndAddHash

类型函数

第 691 行

fn matchAndAddHash(c: *Compress, i: usize, h: Hash, gt: u16, max_chain: u16, good_: u16) struct { dist: u16, len: u16, }

参数

c: *Compress
i: usize
h: Hash
gt: u16
max_chain: u16
good_: u16

std.compress.flate.Compress.math

别名

第 22 行

别名目标 std.math

std.compress.flate.Compress.mem

别名

第 21 行

别名目标 std.mem

std.compress.flate.Compress.Options

容器

第 275 行

在速度与压缩后大小之间取舍。

默认参数[取自 zlib] (https://github.com/madler/zlib/blob/v1.3.1/deflate.c#L112)

字段

good: u16

找到至少达到此长度的匹配后,减少查找次数。

nice: u16

找到长度至少达到此值的匹配时停止。

lazy: u16

已找到长度至少达到此值的匹配时,不再尝试延迟匹配查找。

chain: u16

检查此前具有相同哈希的这么多个位置,以查找更长匹配。

std.compress.flate.Compress.Options.best

别名

第 298 行

别名目标 std.compress.flate.Compress.Options.level_9

std.compress.flate.Compress.Options.default

别名

第 297 行

别名目标 std.compress.flate.Compress.Options.level_6

std.compress.flate.Compress.Options.fastest

别名

第 296 行

别名目标 std.compress.flate.Compress.Options.level_1

std.compress.flate.Compress.Options.level_1

常量

第 286 行

Options

std.compress.flate.Compress.Options.level_2

常量

第 287 行

Options

std.compress.flate.Compress.Options.level_3

常量

第 288 行

Options

std.compress.flate.Compress.Options.level_4

常量

第 289 行

Options

std.compress.flate.Compress.Options.level_5

常量

第 290 行

Options

std.compress.flate.Compress.Options.level_6

常量

第 291 行

Options

std.compress.flate.Compress.Options.level_7

常量

第 292 行

Options

std.compress.flate.Compress.Options.level_8

常量

第 293 行

Options

std.compress.flate.Compress.Options.level_9

常量

第 294 行

Options

std.compress.flate.Compress.outputBytes

函数

第 244 行

fn outputBytes(c: *Compress, bytes: []const u8) Writer.Error!void

参数

c: *Compress
bytes: []const u8

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.outputMatch

函数

第 227 行

fn outputMatch(c: *Compress, dist: u15, len: u8) Writer.Error!void

参数

c: *Compress
dist: u15
len: u8

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.PackedContainer

容器

第 1477 行

字段

raw: bool
other: enum(u1) { gzip, zlib }

std.compress.flate.Compress.PackedContainer.val

函数

第 1481 行

pub fn val(c: @This()) flate.Container

参数

c: @This()

std.compress.flate.Compress.PackedOptionalU15

容器

第 36 行

在 #104 实现之前,?u15 占用 4 字节,这不可接受, 因为会使这个已相当庞大的结构体大小翻倍。

此外,没有 to/from 方法,因为 LLVM 21 不会优化掉与 ?u15 之间的双向转换。

字段

value: u15
is_null: bool

std.compress.flate.Compress.PackedOptionalU15.int

函数

第 40 行

pub fn int(p: PackedOptionalU15) u16

参数

std.compress.flate.Compress.PackedOptionalU15.null_bit

常量

第 44 行

PackedOptionalU15

std.compress.flate.Compress.Raw

容器

第 1598 行

不压缩数据

字段

writer: Writer

调用 finish 后,所有虚函数表调用均产生 error.WriteFailed。

output: *Writer
hasher: flate.Container.Hasher

std.compress.flate.Compress.Raw.drain

函数

第 1631 行

fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize

参数

w: *Writer
data: []const []const u8
splat: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Raw.finish

函数

第 1746 行

pub fn finish(r: *Raw) Writer.Error!void

参数

r: *Raw

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Raw.flush

函数

第 1741 行

fn flush(w: *Writer) Writer.Error!void

参数

w: *Writer

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Raw.full_header

常量

第 1605 行

[5]u8

std.compress.flate.Compress.Raw.init

函数

第 1615 行

虽然没有最小缓冲区大小要求,但建议至少为 flate.max_window_len,以获得最佳输出效果。

pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Raw

参数

output: *Writer
buffer: []u8
container: flate.Container

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Raw.max_block_size

常量

第 1604 行

u16

std.compress.flate.Compress.Raw.rebase

函数

第 1752 行

fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void

参数

w: *Writer
preserve: usize
capacity: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Raw.rebaseInner

函数

第 1757 行

fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void

参数

w: *Writer
preserve: usize
capacity: usize
eos: bool

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.rebase

函数

第 371 行

fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void

参数

w: *Writer
preserve: usize
capacity: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.rebase_min_preserve

别名

第 376 行

别名目标 std.compress.flate.history_len

std.compress.flate.Compress.rebase_reserved_capacity

常量

第 377 行

std.compress.flate.Compress.rebaseInner

函数

第 379 行

fn rebaseInner( w: *Writer, preserve: usize, capacity: usize, is_flush: bool, is_finish: bool, ) Writer.Error!void

参数

w: *Writer
preserve: usize
capacity: usize
is_flush: bool
is_finish: bool

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Seq

常量

第 195 行

std.compress.flate.Compress.seq_bytes

常量

第 194 行

std.compress.flate.Compress.std

别名

第 20 行

别名目标 std

std.compress.flate.Compress.testFuzzedCompressInput

函数

第 1495 行

fn testFuzzedCompressInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void

参数

fbufs: *const [2][65536]u8
smith: *std.testing.Smith

std.compress.flate.Compress.testFuzzedHuffmanInput

函数

第 2509 行

此函数源自 testFuzzedRawInput,为对 Huffman 进行模糊测试作了少量修改。

fn testFuzzedHuffmanInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void

参数

fbufs: *const [2][65536]u8
smith: *std.testing.Smith

std.compress.flate.Compress.testFuzzedHuffmanInput.add_vec_and_drain

常量

第 2536 行

@This()

std.compress.flate.Compress.testFuzzedHuffmanInput.add_vec_only

常量

第 2535 行

@This()

std.compress.flate.Compress.testFuzzedHuffmanInput.drain_and_flush

常量

第 2538 行

@This()

std.compress.flate.Compress.testFuzzedHuffmanInput.drain_and_rebase

常量

第 2537 行

@This()

std.compress.flate.Compress.testFuzzedHuffmanInput.drain_only

常量

第 2534 行

@This()

std.compress.flate.Compress.testFuzzedMatchLen

函数

第 642 行

fn testFuzzedMatchLen(_: void, smith: *std.testing.Smith) !void

参数

_: void
smith: *std.testing.Smith

std.compress.flate.Compress.testFuzzedRawInput

函数

第 1835 行

fn testFuzzedRawInput(data_buf: *const [4 * 65536]u8, smith: *std.testing.Smith) !void

参数

data_buf: *const [4 * 65536]u8
smith: *std.testing.Smith

std.compress.flate.Compress.testFuzzedRawInput.add_vec_and_drain

常量

第 1997 行

@This()

std.compress.flate.Compress.testFuzzedRawInput.add_vec_only

常量

第 1996 行

@This()

std.compress.flate.Compress.testFuzzedRawInput.drain

函数

第 1877 行

注意,此实现一定程度上依赖 Raw 的实现, 假定头部/尾部在数据元素中连续。 还假定头部与 flate.Container.header 相同, 且多个流不会拼接。

fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize

参数

w: *Writer
data: []const []const u8
splat: usize

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.testFuzzedRawInput.drain_and_flush

常量

第 1999 行

@This()

std.compress.flate.Compress.testFuzzedRawInput.drain_and_rebase

常量

第 1998 行

@This()

std.compress.flate.Compress.testFuzzedRawInput.drain_only

常量

第 1995 行

@This()

std.compress.flate.Compress.testFuzzedRawInput.flush

函数

第 1964 行

fn flush(w: *Writer) Writer.Error!void

参数

w: *Writer

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.testFuzzedRawInput.init

函数

第 1854 行

pub fn init(buf: []u8, container: flate.Container) @This()

参数

buf: []u8
container: flate.Container

std.compress.flate.Compress.testingCheckContainerHash

函数

第 1453 行

fn testingCheckContainerHash( expected_size: u32, expected_hash: flate.Container.Hasher, actual_hash: flate.Container.Hasher, actual_size: u32, actual_meta: flate.Container.Metadata, ) !void

参数

expected_size: u32
expected_hash: flate.Container.Hasher
actual_hash: flate.Container.Hasher
actual_size: u32
actual_meta: flate.Container.Metadata

std.compress.flate.Compress.testingCheckDecompressedMatches

函数

第 1423 行

fn testingCheckDecompressedMatches( flate_bytes: []const u8, expected_size: u32, expected_hash: flate.Container.Hasher, ) !void

参数

flate_bytes: []const u8
expected_size: u32
expected_hash: flate.Container.Hasher

std.compress.flate.Compress.testingFreqBufs

函数

第 1410 行

[0] 为渐变数据,其中低值的概率逐渐降低 [1] 完全随机,因此不可压缩

fn testingFreqBufs() !*[2][65536]u8

std.compress.flate.Compress.token

别名

第 28 行

别名目标 std.compress.flate.token

std.compress.flate.Compress.TokenBufferEntryHeader

容器

第 197 行

字段

kind: enum(u1) {
    /// 后接非零的 `data` 字节字面量。
    bytes,
    /// 后接以单字节表示的长度
    match,
}
data: u15

std.compress.flate.Compress.writeBlock

函数

第 880 行

fn writeBlock(c: *Compress, eos: bool) Writer.Error!void

参数

c: *Compress
eos: bool

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Compress.Writer

别名

第 25 行

别名目标 std.Io.Writer

源码

std/compress/flate/Compress.zig

//! 静态分配约 224K:128K 查找表、96K 词元。
//!
//! `error.WriteFailed` 始终来自底层写入器。发生
//! `error.WriteFailed` 后,`.writer` 变为 `.failing`,且不可恢复。
//!
//! `finish` 之后,流已经结束,写入器也会变为
//! `.failing`。此行为同样适用于 `Raw` 和 `Huffman`。

// 实现细节:
//   使用链式哈希表查找匹配。`drain` 始终保留 `flate.history_len`
//   字节作为历史,并避免对末尾字节分词,因为它们可能
//   与尚未写入的字节组成更长匹配,除非正在 `flush`。搜索的最短匹配
//   长度为 `seq_bytes`。找到匹配后,若其未达到 `Options.lazy` 阈值,
//   还会检查从下一字节开始是否存在更长匹配,即惰性匹配。
//
//   最多累积 `block_token` 个标记到 `buffered_tokens`,随后在
//   `write_block` 中输出,并确定最优的块类型和频率。

const builtin = @import("builtin");
const std = @import("std");
const mem = std.mem;
const math = std.math;
const assert = std.debug.assert;
const Io = std.Io;
const Writer = Io.Writer;

const Compress = @This();
const token = @import("token.zig");
const flate = @import("../flate.zig");

/// 在 #104 实现之前,?u15 占用 4 字节,这不可接受,
/// 因为会使这个已相当庞大的结构体大小翻倍。
///
/// 此外,没有 `to`/`from` 方法,因为 LLVM 21
/// 不会优化掉与 `?u15` 之间的双向转换。
const PackedOptionalU15 = packed struct(u16) {
    value: u15,
    is_null: bool,

    pub fn int(p: PackedOptionalU15) u16 {
        return @bitCast(p);
    }

    pub const null_bit: PackedOptionalU15 = .{ .value = 0, .is_null = true };
};

/// 调用 `finish` 后,所有虚函数表调用均产生 `error.WriteFailed`。
writer: Writer,
history_len: u16,
history_end_unhashed: bool,
bit_writer: BitWriter,
buffered_tokens: struct {
    /// `TokenBufferEntryHeader` 及其尾随数据的列表。
    list: [@as(usize, block_tokens) * 3]u8,
    pos: u32,
    n: u16,
    lit_freqs: [286]u16,
    dist_freqs: [30]u16,

    pub const empty: @This() = .{
        .list = undefined,
        .pos = 0,
        .n = 0,
        .lit_freqs = @splat(0),
        .dist_freqs = @splat(0),
    };
},
lookup: struct {
    /// 索引是四字节序列的哈希。
    ///
    /// 值是具有相同哈希的前四个字节在 `chain` 中的位置。
    head: [1 << lookup_hash_bits]PackedOptionalU15,
    /// 各值表示向历史数据回溯至相同哈希所需的字节数,且该值非零。
    ///
    /// 链索引与相对最新历史字节的位置之间的关系为
    /// `chain_pos -% chain_index = history_index`。
    chain: [32768]PackedOptionalU15,
    /// `chain` 中对应历史最新字节的索引。
    chain_pos: u15,
},
container: flate.Container,
hasher: flate.Container.Hasher,
opts: Options,

const BitWriter = struct {
    output: *Writer,
    buffered: u7,
    buffered_n: u3,

    pub fn init(w: *Writer) BitWriter {
        return .{
            .output = w,
            .buffered = 0,
            .buffered_n = 0,
        };
    }

    /// 断言 `bits` 经过零扩展
    pub fn write(b: *BitWriter, bits: u56, n: u6) Writer.Error!void {
        assert(@as(u8, b.buffered) >> b.buffered_n == 0);
        assert(@as(u57, bits) >> n == 0); // n 可能为 56,因此需要 u57
        const combined = @shlExact(@as(u64, bits), b.buffered_n) | b.buffered;
        const combined_bits = @as(u6, b.buffered_n) + n;

        const out = try b.output.writableSliceGreedy(8);
        mem.writeInt(u64, out[0..8], combined, .little);
        b.output.advance(combined_bits / 8);

        b.buffered_n = @truncate(combined_bits);
        b.buffered = @intCast(combined >> (combined_bits - b.buffered_n));
    }

    /// 断言无需调整基址即可向 `b.output` 写入一个字节。
    pub fn byteAlign(b: *BitWriter) void {
        b.output.unusedCapacitySlice()[0] = b.buffered;
        b.output.advance(@intFromBool(b.buffered_n != 0));
        b.buffered = 0;
        b.buffered_n = 0;
    }

    /// 仅使用空 flate 分组进行字节对齐
    pub fn byteAlignBlocks(b: *BitWriter) Writer.Error!void {
        if (b.buffered_n == 0) return;

        // 可用两种方法完成:
        // 1. 存储块(5 或 6 字节)
        // 2. 不断输出空的 10 位固定块,直到对齐
        //
        // 固定块每次使位对齐位置前进两位,因此仅适用于偶数,
        // 最多需要四字节(三个块 = 30 位),
        // 始终比存储块更高效。
        if (b.buffered_n & 1 == 0) {
            const splat = (8 - @as(u5, b.buffered_n)) >> 1;
            const bits = splat * 10;
            // 固定 eos 编码为 0,因此仅块头占用位。
            const pattern: u32 = BlockHeader.int(.{ .kind = .fixed, .final = false });
            const splatted = ((pattern << 20) | (pattern << 10) | pattern) >> (30 - bits);
            try b.write(splatted, bits);
        } else {
            try b.write(BlockHeader.int(.{ .kind = .stored, .final = false }), 3);
            try b.output.rebase(0, 5);
            b.byteAlign();
            b.output.writeInt(u16, 0x0000, .little) catch unreachable;
            b.output.writeInt(u16, 0xffff, .little) catch unreachable;
        }

        assert(b.buffered_n == 0);
    }

    pub fn writeClen(
        b: *BitWriter,
        hclen: u4,
        clen_values: []u8,
        clen_extra: []u8,
        clen_codes: [19]u16,
        clen_bits: [19]u4,
    ) Writer.Error!void {
        // 前四个 clen 条目始终存在,因此单独写入它们,
        // 一次性全部写入会占用过多位。
        try b.write(clen_bits[token.codegen_order[0]] |
            @shlExact(@as(u6, clen_bits[token.codegen_order[1]]), 3) |
            @shlExact(@as(u9, clen_bits[token.codegen_order[2]]), 6) |
            @shlExact(@as(u12, clen_bits[token.codegen_order[3]]), 9), 12);

        var i = hclen;
        var clen_bits_table: u45 = 0;
        while (i != 0) {
            i -= 1;
            clen_bits_table <<= 3;
            clen_bits_table |= clen_bits[token.codegen_order[4..][i]];
        }
        try b.write(clen_bits_table, @as(u6, hclen) * 3);

        for (clen_values, clen_extra) |value, extra| {
            try b.write(
                clen_codes[value] | @shlExact(@as(u16, extra), clen_bits[value]),
                clen_bits[value] + @as(u3, switch (value) {
                    0...15 => 0,
                    16 => 2,
                    17 => 3,
                    18 => 7,
                    else => unreachable,
                }),
            );
        }
    }
};

/// 输出为块之前累积的 token 数量。
/// 最大值为 `math.maxInt(u16) - 1`,因为要保留一个 token 作为块结束标记。
const block_tokens: u16 = 1 << 15;
const lookup_hash_bits = 15;
const Hash = u16; // 未使用 `@Int(.unsigned, lookup_hash_bits)`,因为其优化效果更差(使用 LLVM 21)。
const seq_bytes = 3; // 不打算更改
const Seq = @Int(.unsigned, seq_bytes * 8);

const TokenBufferEntryHeader = packed struct(u16) {
    kind: enum(u1) {
        /// 后接非零的 `data` 字节字面量。
        bytes,
        /// 后接以单字节表示的长度
        match,
    },
    data: u15,
};

const BlockHeader = packed struct(u3) {
    final: bool,
    kind: enum(u2) { stored, fixed, dynamic, _ },

    pub fn int(h: BlockHeader) u3 {
        return @bitCast(h);
    }

    pub const Dynamic = packed struct(u17) {
        regular: BlockHeader,
        hlit: u5,
        hdist: u5,
        hclen: u4,

        pub fn int(h: Dynamic) u17 {
            return @bitCast(h);
        }
    };
};

fn outputMatch(c: *Compress, dist: u15, len: u8) Writer.Error!void {
    // 必须先执行此操作。这里不保证缓冲区绝不保留完整块,
    // 而是延迟排空,以便表示流结束。
    if (c.buffered_tokens.n == block_tokens) {
        @branchHint(.unlikely); // LLVM 21 在没有额外指定时将此分支优化为更可能执行的分支
        try c.writeBlock(false);
    }
    const header: TokenBufferEntryHeader = .{ .kind = .match, .data = dist };
    c.buffered_tokens.list[c.buffered_tokens.pos..][0..2].* = @bitCast(header);
    c.buffered_tokens.list[c.buffered_tokens.pos + 2] = len;
    c.buffered_tokens.pos += 3;
    c.buffered_tokens.n += 1;

    c.buffered_tokens.lit_freqs[@as(usize, 257) + token.LenCode.fromVal(len).toInt()] += 1;
    c.buffered_tokens.dist_freqs[token.DistCode.fromVal(dist).toInt()] += 1;
}

fn outputBytes(c: *Compress, bytes: []const u8) Writer.Error!void {
    var remaining = bytes;
    while (remaining.len != 0) {
        if (c.buffered_tokens.n == block_tokens) {
            @branchHint(.unlikely); // LLVM 21 在没有额外指定时将此分支优化为更可能执行的分支
            try c.writeBlock(false);
        }

        const n = @min(remaining.len, block_tokens - c.buffered_tokens.n, math.maxInt(u15));
        assert(n != 0);
        const header: TokenBufferEntryHeader = .{ .kind = .bytes, .data = n };
        c.buffered_tokens.list[c.buffered_tokens.pos..][0..2].* = @bitCast(header);
        @memcpy(c.buffered_tokens.list[c.buffered_tokens.pos + 2 ..][0..n], remaining[0..n]);
        c.buffered_tokens.pos += @as(u32, 2) + n;
        c.buffered_tokens.n += n;

        for (remaining[0..n]) |b| {
            c.buffered_tokens.lit_freqs[b] += 1;
        }
        remaining = remaining[n..];
    }
}

fn hash(x: u32) Hash {
    return @intCast((x *% 0x9E3779B1) >> (32 - lookup_hash_bits));
}

/// 在速度与压缩后大小之间取舍。
///
/// 默认参数[取自 zlib]
/// (https://github.com/madler/zlib/blob/v1.3.1/deflate.c#L112)
pub const Options = struct {
    /// 找到至少达到此长度的匹配后,减少查找次数。
    good: u16,
    /// 找到长度至少达到此值的匹配时停止。
    nice: u16,
    /// 已找到长度至少达到此值的匹配时,不再尝试延迟匹配查找。
    lazy: u16,
    /// 检查此前具有相同哈希的这么多个位置,以查找更长匹配。
    chain: u16,

    // zig fmt: off
    pub const level_1: Options = .{ .good =  4, .nice =   8, .lazy =   0, .chain =    4 };
    pub const level_2: Options = .{ .good =  4, .nice =  16, .lazy =   0, .chain =    8 };
    pub const level_3: Options = .{ .good =  4, .nice =  32, .lazy =   0, .chain =   32 };
    pub const level_4: Options = .{ .good =  4, .nice =  16, .lazy =   4, .chain =   16 };
    pub const level_5: Options = .{ .good =  8, .nice =  32, .lazy =  16, .chain =   32 };
    pub const level_6: Options = .{ .good =  8, .nice = 128, .lazy =  16, .chain =  128 };
    pub const level_7: Options = .{ .good =  8, .nice = 128, .lazy =  32, .chain =  256 };
    pub const level_8: Options = .{ .good = 32, .nice = 258, .lazy = 128, .chain = 1024 };
    pub const level_9: Options = .{ .good = 32, .nice = 258, .lazy = 258, .chain = 4096 };
     // zig fmt: on
    pub const fastest = level_1;
    pub const default = level_6;
    pub const best = level_9;
};

/// 断言 `buffer` 至少有 `flate.max_window_len` 字节。
/// 断言 `output` 容量至少为 8 字节。
pub fn init(
    output: *Writer,
    buffer: []u8,
    container: flate.Container,
    opts: Options,
) Writer.Error!Compress {
    assert(output.buffer.len > 8);
    assert(buffer.len >= flate.max_window_len);

    // 注意,禁止其中某些形式可简化匹配逻辑
    assert(opts.chain != 0); // 使用 `Huffman`;禁止此项可简化匹配。
    assert(opts.good >= 3 and opts.nice >= 3); // 通常不会找到匹配项
    assert(opts.good <= 258 and opts.nice <= 258); // 不会找到更长的匹配项
    assert(opts.lazy <= opts.nice); // 通常找不到更长的匹配
    if (opts.good <= opts.lazy) assert(opts.chain >= 1 << 2); // 链可缩减为零

    try output.writeAll(container.header());
    return .{
        .writer = .{
            .buffer = buffer,
            .vtable = &.{
                .drain = drain,
                .flush = flush,
                .rebase = rebase,
            },
        },
        .history_len = 0,
        .history_end_unhashed = false,
        .bit_writer = .init(output),
        .buffered_tokens = .empty,
        .lookup = .{
            // 初始 `value` 为最大值,因此呈现 0xff 模式
            .head = @splat(.{ .value = math.maxInt(u15), .is_null = true }),
            .chain = undefined,
            .chain_pos = math.maxInt(u15),
        },
        .container = container,
        .opts = opts,
        .hasher = .init(container),
    };
}

fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
    errdefer w.* = .failing;
    // 缓冲区可能没有足够空间,因此写入被直接发送到此处。
    // 但为保留历史数据,要求全部数据都必须经过缓冲区。
    const data_n = w.buffer.len - w.end;
    _ = w.fixedDrain(data, splat) catch {};
    assert(w.end == w.buffer.len);
    try rebaseInner(w, 0, 1, false, false);
    return data_n;
}

fn flush(w: *Writer) Writer.Error!void {
    errdefer w.* = .failing;
    try rebaseInner(w, 0, w.buffer.len - flate.history_len, true, false);
    const c: *Compress = @fieldParentPtr("writer", w);
    try c.bit_writer.byteAlignBlocks();
}

pub fn finish(c: *Compress) Writer.Error!void {
    defer c.writer = .failing;
    try rebaseInner(&c.writer, 0, c.writer.buffer.len - flate.history_len, true, true);
    try c.bit_writer.output.rebase(0, 1);
    c.bit_writer.byteAlign();
    try c.hasher.writeFooter(c.bit_writer.output);
}

fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
    errdefer w.* = .failing;
    return rebaseInner(w, preserve, capacity, false, false);
}

pub const rebase_min_preserve = flate.history_len;
pub const rebase_reserved_capacity = (token.max_length + 1) + seq_bytes;

fn rebaseInner(
    w: *Writer,
    preserve: usize,
    capacity: usize,
    is_flush: bool,
    is_finish: bool,
) Writer.Error!void {
    if (!is_flush) {
        assert(@max(preserve, rebase_min_preserve) + (capacity + rebase_reserved_capacity) <= w.buffer.len);
    } else {
        // `matching_end` 不考虑 Preverse
        assert(preserve == 0 and capacity == w.buffer.len - flate.history_len);
    }
    if (is_finish) assert(is_flush);

    const c: *Compress = @fieldParentPtr("writer", w);
    const buffered = w.buffered();

    const start: usize = c.history_len;
    const hashable_len = buffered.len -| (seq_bytes - 1);
    const matching_end: usize = if (!is_flush)
        buffered.len - rebase_reserved_capacity - (preserve -| flate.history_len)
    else
        hashable_len;

    var i = start;
    var last_unmatched = i;
    var seq: Seq = start_seq: {
        if (c.history_end_unhashed) {
            @branchHint(.unlikely);

            assert(i != 0);
            i -|= seq_bytes - 1;
            var seq: Seq = mem.readInt(
                @Int(.unsigned, (seq_bytes - 1) * 8),
                w.buffer[i..][0 .. seq_bytes - 1],
                .big,
            );

            while (i < @min(start, hashable_len)) {
                seq <<= 8;
                seq |= buffered[i + (seq_bytes - 1)];
                c.addHash(i, hash(seq));
                i += 1;
            }

            if (i < start) {
                @branchHint(.unlikely);
                i = start;
                assert(i >= hashable_len);
                assert(i >= matching_end);
                assert(is_flush);
                break :start_seq undefined; // 未使用
            }

            c.history_end_unhashed = false;
            break :start_seq seq;
        }

        if (i >= hashable_len) {
            @branchHint(.unlikely);
            assert(i >= matching_end);
            assert(is_flush);
            break :start_seq undefined; // 未使用
        }

        break :start_seq mem.readInt(
            @Int(.unsigned, (seq_bytes - 1) * 8),
            buffered[i..][0 .. seq_bytes - 1],
            .big,
        );
    };

    while (i < matching_end) {
        var match_start = i;
        seq <<= 8;
        seq |= buffered[i + (seq_bytes - 1)];
        var match = c.matchAndAddHash(i, hash(seq), token.min_length - 1, c.opts.chain, c.opts.good);
        i += 1;
        if (match.len < token.min_length) continue;

        var match_unadded = match.len - 1;
        lazy: {
            if (match.len >= c.opts.lazy) break :lazy;
            if (match.len >= c.writer.buffered()[i..].len) {
                @branchHint(.unlikely); // 仅流结束
                break :lazy;
            }

            var chain = c.opts.chain;
            var good = c.opts.good;
            if (match.len >= good) {
                chain >>= 2;
                good = math.maxInt(u8); // 仅约减一次
            }

            seq <<= 8;
            seq |= buffered[i + (seq_bytes - 1)];
            const lazy = c.matchAndAddHash(i, hash(seq), match.len, chain, good);
            match_unadded -= 1;
            i += 1;

            if (lazy.len > match.len) {
                match_start += 1;
                match = lazy;
                match_unadded = match.len - 1;
            }
        }

        assert(i + match_unadded == match_start + match.len);
        assert(mem.eql(
            u8,
            buffered[match_start..][0..match.len],
            buffered[match_start - 1 - match.dist ..][0..match.len],
        )); // 此断言似乎也有助于代码生成。

        try c.outputBytes(buffered[last_unmatched..match_start]);
        try c.outputMatch(@intCast(match.dist), @intCast(match.len - 3));
        last_unmatched = match_start + match.len;

        while (i < hashable_len) {
            seq <<= 8;
            seq |= buffered[i + (seq_bytes - 1)];
            c.addHash(i, hash(seq));
            i += 1;

            match_unadded -= 1;
            if (match_unadded == 0) break;
        } else {
            @branchHint(.unlikely);
            assert(is_flush);
            // `c.history_end_unhashed` 在下方设置
            break;
        }
        assert(i == match_start + match.len);
    }

    if (is_flush) {
        try c.outputBytes(buffered[last_unmatched..]);
        c.hasher.update(buffered[start..]);

        if (is_finish) {
            try c.writeBlock(true);
            return; // 无需更新其他状态,因为写入器会转换为 `.failing`
        }

        i = buffered.len;
        c.history_end_unhashed = i != 0;

        if (c.buffered_tokens.n != 0) {
            try c.writeBlock(false);
        }
    } else {
        try c.outputBytes(buffered[last_unmatched..i]);
        c.hasher.update(buffered[start..i]);
    }

    c.history_len = @min(i, flate.history_len);
    const preserved = buffered[i - c.history_len ..];
    if (!is_flush) assert(preserved.len >= @max(rebase_min_preserve, preserve));
    @memmove(w.buffer[0..preserved.len], preserved);
    w.end = preserved.len;
}

fn addHash(c: *Compress, i: usize, h: Hash) void {
    assert(h == hash(mem.readInt(Seq, c.writer.buffer[i..][0..seq_bytes], .big)));

    const l = &c.lookup;
    l.chain_pos +%= 1;

    // 等价于下列代码,但 LLVM 21 对 `@subWithOverflow` 的优化效果很差。
    // const replaced_i, const no_replace = @subWithOverflow(i, flate.history_len);
    // if (no_replace == 0) {
    if (i >= flate.history_len) {
        @branchHint(.likely);
        const replaced_i = i - flate.history_len;
        // 以下代码等同于下方代码,但使用 32 位加载以帮助优化。
        // const replaced_seq = mem.readInt(Seq, c.writer.buffer[replaced_i..][0..seq_bytes], .big);
        comptime assert(@sizeOf(Seq) <= @sizeOf(u32));
        const replaced_u32 = mem.readInt(u32, c.writer.buffered()[replaced_i..][0..4], .big);
        const replaced_seq: Seq = @intCast(replaced_u32 >> (32 - @bitSizeOf(Seq)));

        const replaced_h = hash(replaced_seq);
        // 以下操作等价于下方代码,因为 LLVM 21 无法良好优化后者。
        // l.head[replaced_h].is_null = l.head[replaced_h].is_null or
        //     l.head[replaced_h].int() == l.chain_pos;
        const empty_head = l.head[replaced_h].int() == l.chain_pos;
        const null_flag = PackedOptionalU15.int(.{ .is_null = empty_head, .value = 0 });
        l.head[replaced_h] = @bitCast(l.head[replaced_h].int() | null_flag);
    }

    const prev_chain_index = l.head[h];
    l.chain[l.chain_pos] = @bitCast((l.chain_pos -% prev_chain_index.value) |
        (prev_chain_index.int() & PackedOptionalU15.null_bit.int())); // 保留 null
    l.head[h] = .{ .value = l.chain_pos, .is_null = false };
}

/// 若匹配更短,返回值可为任意 `<= old` 的值。
fn betterMatchLen(old: u16, prev: []const u8, bytes: []const u8) u16 {
    assert(old < @min(bytes.len, token.max_length));
    assert(prev.len >= bytes.len);
    assert(bytes.len >= token.min_length);

    var i: u16 = 0;
    const Block = @Int(.unsigned, @min(math.divCeil(
        comptime_int,
        math.ceilPowerOfTwoAssert(usize, @bitSizeOf(usize)),
        8,
    ) catch unreachable, 256) * 8);

    if (bytes.len < token.max_length) {
        @branchHint(.unlikely); // 仅流结束

        while (bytes[i..].len >= @sizeOf(Block)) {
            const a = mem.readInt(Block, prev[i..][0..@sizeOf(Block)], .little);
            const b = mem.readInt(Block, bytes[i..][0..@sizeOf(Block)], .little);
            const diff = a ^ b;
            if (diff != 0) {
                @branchHint(.likely);
                i += @ctz(diff) / 8;
                return i;
            }
            i += @sizeOf(Block);
        }

        while (i != bytes.len and prev[i] == bytes[i]) {
            i += 1;
        }
        assert(i < token.max_length);
        return i;
    }

    if (old >= @sizeOf(Block)) {
        // 检查是否存在更长的结束位置,否则匹配总会更差
        const a = mem.readInt(Block, prev[old + 1 - @sizeOf(Block) ..][0..@sizeOf(Block)], .little);
        const b = mem.readInt(Block, bytes[old + 1 - @sizeOf(Block) ..][0..@sizeOf(Block)], .little);
        if (a != b) return i;
    }

    while (true) {
        const a = mem.readInt(Block, prev[i..][0..@sizeOf(Block)], .little);
        const b = mem.readInt(Block, bytes[i..][0..@sizeOf(Block)], .little);
        const diff = a ^ b;
        if (diff != 0) {
            i += @ctz(diff) / 8;
            return i;
        }
        i += @sizeOf(Block);
        if (i == 256) break;
    }

    const a = mem.readInt(u16, prev[i..][0..2], .little);
    const b = mem.readInt(u16, bytes[i..][0..2], .little);
    const diff = a ^ b;
    i += @ctz(diff) / 8;
    assert(i <= token.max_length);
    return i;
}

test betterMatchLen {
    try std.testing.fuzz({}, testFuzzedMatchLen, .{});
}

fn testFuzzedMatchLen(_: void, smith: *std.testing.Smith) !void {
    @disableInstrumentation();
    var buf: [1024]u8 = undefined;
    var w: Writer = .fixed(&buf);

    while (w.unusedCapacityLen() != 0 and !smith.eosWeightedSimple(7, 1)) {
        switch (smith.value(enum(u2) { splat, copy, insert })) {
            .splat => w.splatByteAll(
                smith.value(u8),
                smith.valueRangeAtMost(u9, 1, @min(511, w.unusedCapacityLen())),
            ) catch unreachable,
            .copy => write: {
                if (w.buffered().len == 0) continue;
                const start = smith.valueRangeAtMost(u10, 0, @intCast(w.buffered().len - 1));
                const max_len = @min(w.unusedCapacityLen(), w.buffered().len - start);
                const len = smith.valueRangeAtMost(u10, 1, @intCast(max_len));
                break :write w.writeAll(w.buffered()[start..][0..len]) catch unreachable;
            },
            .insert => w.advance(smith.slice(w.unusedCapacitySlice())),
        }
    }
    w.splatByteAll(0, (1 + token.min_length) -| w.buffered().len) catch unreachable;

    const max_start = w.buffered().len - token.min_length;
    const bytes_off = smith.valueRangeAtMost(u10, 1, @intCast(max_start));
    const prev_off = smith.valueRangeAtMost(u10, 0, bytes_off - 1);
    const prev = w.buffered()[prev_off..];
    const bytes = w.buffered()[bytes_off..];
    const old = smith.valueRangeLessThan(u10, 0, @min(bytes.len, token.max_length));

    const diff_index = mem.findDiff(u8, prev, bytes).?; // 由于长度不同而执行解包
    const expected_len = @min(diff_index, 258);
    errdefer std.debug.print(
        \\prev : '{any}'
        \\bytes: '{any}'
        \\old     : {}
        \\expected: {?}
        \\actual  : {}
    ++ "\n", .{
        prev,                                           bytes,                            old,
        if (old < expected_len) expected_len else null, betterMatchLen(old, prev, bytes),
    });
    if (old < expected_len) {
        try std.testing.expectEqual(expected_len, betterMatchLen(old, prev, bytes));
    } else {
        try std.testing.expect(betterMatchLen(old, prev, bytes) <= old);
    }
}

fn matchAndAddHash(c: *Compress, i: usize, h: Hash, gt: u16, max_chain: u16, good_: u16) struct {
    dist: u16,
    len: u16,
} {
    const l = &c.lookup;
    const buffered = c.writer.buffered();

    var chain_limit = max_chain;
    var best_dist: u16 = undefined;
    var best_len = gt;
    const nice = @min(c.opts.nice, buffered[i..].len);
    var good = good_;

    search: {
        if (l.head[h].is_null) break :search;
        // 实际上是 u15,但 LLVM 21 对其优化效果不佳(每次使用时都会截断)。
        var dist: u16 = l.chain_pos -% l.head[h].value;
        while (true) {
            chain_limit -= 1;

            const match_len = betterMatchLen(best_len, buffered[i - 1 - dist ..], buffered[i..]);
            if (match_len > best_len) {
                best_dist = dist;
                best_len = match_len;
                if (best_len >= nice) break;
                if (best_len >= good) {
                    chain_limit >>= 2;
                    good = math.maxInt(u8); // 仅约减一次
                }
            }

            if (chain_limit == 0) break;
            const next_chain_index = l.chain_pos -% @as(u15, @intCast(dist));
            // 等价于下方代码,但 LLVM 21 对下方代码的优化效果较差。
            // if (l.chain[next_chain_index].is_null) break;
            // dist, const out_of_window = @addWithOverflow(dist, l.chain[next_chain_index].value);
            // if (out_of_window == 1) break;
            dist +%= l.chain[next_chain_index].int(); // 为可能出现的空位执行环绕运算
            comptime assert(flate.history_len == PackedOptionalU15.int(.null_bit));
            // 此外,在 LLVM 21 中使用 >= flate.history_len 会导致更差的代码生成。
            if ((dist | l.chain[next_chain_index].int()) & flate.history_len != 0) break;
        }
    }

    c.addHash(i, h);
    return .{ .dist = best_dist, .len = best_len };
}

fn clenHlen(freqs: [19]u16) u4 {
    // 注意,前四个代码(16、17、18 和 0)始终存在。
    if (builtin.mode != .small and (std.simd.suggestVectorLength(u16) orelse 1) >= 8) {
        const V = @Vector(16, u16);
        const hlen_mul: V = comptime m: {
            var hlen_mul: [16]u16 = undefined;
            for (token.codegen_order[3..], 0..) |i, hlen| {
                hlen_mul[i] = hlen;
            }
            break :m hlen_mul;
        };
        const encoded = freqs[0..16].* != @as(V, @splat(0));
        return @intCast(@reduce(.Max, @intFromBool(encoded) * hlen_mul));
    } else {
        var max: u4 = 0;
        for (token.codegen_order[4..], 1..) |i, len| {
            max = if (freqs[i] == 0) max else @intCast(len);
        }
        return max;
    }
}

test clenHlen {
    var freqs: [19]u16 = @splat(0);
    try std.testing.expectEqual(0, clenHlen(freqs));
    for (token.codegen_order, 1..) |i, len| {
        freqs[i] = 1;
        try std.testing.expectEqual(len -| 4, clenHlen(freqs));
        freqs[i] = 0;
    }
}

/// 返回值的数量,后跟额外位的位数。
fn buildClen(
    dyn_bits: []const u4,
    out_values: []u8,
    out_extra: []u8,
    out_freqs: *[19]u16,
) struct { u16, u16 } {
    assert(dyn_bits.len <= out_values.len);
    assert(out_values.len == out_extra.len);

    var len: u16 = 0;
    var extra_bitsize: u16 = 0;

    var remaining_bits = dyn_bits;
    var prev: u4 = 0;
    while (true) {
        const b = remaining_bits[0];
        const n_max = @min(@as(u8, if (b != 0)
            if (b != prev) 1 else 6
        else
            138), remaining_bits.len);
        prev = b;

        var n: u8 = 0;
        while (true) {
            remaining_bits = remaining_bits[1..];
            n += 1;
            if (n == n_max or remaining_bits[0] != b) break;
        }
        const code, const extra, const xsize = switch (n) {
            0 => unreachable,
            1...2 => .{ b, 0, 0 },
            3...10 => .{
                @as(u8, 16) + @intFromBool(b == 0),
                n - 3,
                @as(u8, 2) + @intFromBool(b == 0),
            },
            11...138 => .{ 18, n - 11, 7 },
            else => unreachable,
        };
        while (true) {
            out_values[len] = code;
            out_extra[len] = extra;
            out_freqs[code] += 1;
            extra_bitsize += xsize;
            len += 1;
            if (n != 2) {
                @branchHint(.likely);
                break;
            }
            // 代码还需要再输出一次
            n = 1;
        }
        if (remaining_bits.len == 0) break;
    }

    return .{ len, extra_bitsize };
}

test buildClen {
    // dyn_bits: []u4,
    // out_values: *[288 + 30]u8,
    // out_extra: *[288 + 30]u8,
    // out_freqs: *[19]u16,
    // struct { u16, u16 }
    var out_values: [288 + 30]u8 = undefined;
    var out_extra: [288 + 30]u8 = undefined;
    var out_freqs: [19]u16 = @splat(0);
    const len, const extra_bitsize = buildClen(&([_]u4{
        1, // A
        2, 2, // B
        3, 3, 3, // C
        4, 4, 4, 4, // D
        5, // E
        5, 5, 5, 5, 5, 5, //
        5, 5, 5, 5, 5, 5,
        5, 5,
        0, 1, // F
        0, 0, 1, // G
    } ++ @as([138 + 10]u4, @splat(0)) // H
    ), &out_values, &out_extra, &out_freqs);
    try std.testing.expectEqualSlices(u8, &.{
        1, // A
        2, 2, // B
        3, 3, 3, // C
        4, 16, // D
        5, 16, 16, 5, 5, // E
        0, 1, // F
        0, 0, 1, // G
        18, 17, // H
    }, out_values[0..len]);
    try std.testing.expectEqualSlices(u8, &.{
        0, // A
        0, 0, // B
        0, 0, 0, // C
        0, (0), // D
        0, (3), (3), 0, 0, // E
        0, 0, // F
        0, 0, 0, // G
        (127), (7), // H
    }, out_extra[0..len]);
    try std.testing.expectEqual(2 + 2 + 2 + 7 + 3, extra_bitsize);
    try std.testing.expectEqualSlices(u16, &.{
        3, 3, 2, 3, 1, 3, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        3, 1, 1,
    }, &out_freqs);
}

fn writeBlock(c: *Compress, eos: bool) Writer.Error!void {
    const toks = &c.buffered_tokens;
    assert(toks.lit_freqs[256] == 0);
    toks.lit_freqs[256] = 1;

    var dyn_codes_buf: [286 + 30]u16 = undefined;
    var dyn_bits_buf: [286 + 30]u4 = @splat(0);

    const dyn_lit_codes_bitsize, const dyn_last_lit = huffman.build(
        &toks.lit_freqs,
        dyn_codes_buf[0..286],
        dyn_bits_buf[0..286],
        15,
        true,
    );
    const dyn_lit_len = @max(257, dyn_last_lit + 1);

    const dyn_dist_codes_bitsize, const dyn_last_dist = huffman.build(
        &toks.dist_freqs,
        dyn_codes_buf[dyn_lit_len..][0..30],
        dyn_bits_buf[dyn_lit_len..][0..30],
        15,
        true,
    );
    const dyn_dist_len = @max(1, dyn_last_dist + 1);

    var clen_values: [288 + 30]u8 = undefined;
    var clen_extra: [288 + 30]u8 = undefined;
    var clen_freqs: [19]u16 = @splat(0);
    const clen_len, const clen_extra_bitsize = buildClen(
        dyn_bits_buf[0 .. dyn_lit_len + dyn_dist_len],
        &clen_values,
        &clen_extra,
        &clen_freqs,
    );

    var clen_codes: [19]u16 = undefined;
    var clen_bits: [19]u4 = @splat(0);
    const clen_codes_bitsize, _ = huffman.build(
        &clen_freqs,
        &clen_codes,
        &clen_bits,
        7,
        false,
    );
    const hclen = clenHlen(clen_freqs);

    const dynamic_bitsize = @as(u32, 14) +
        (4 + @as(u6, hclen)) * 3 + clen_codes_bitsize + clen_extra_bitsize +
        dyn_lit_codes_bitsize + dyn_dist_codes_bitsize;
    const fixed_bitsize = n: {
        const freq7 = 1; // 流结束
        var freq8: u16 = 0;
        var freq9: u16 = 0;
        var freq12: u16 = 0; // 7 + 5:匹配频率始终具有相应的 5 位距离频率。
        var freq13: u16 = 0; // 8 + 5
        for (toks.lit_freqs[0..144]) |f| freq8 += f;
        for (toks.lit_freqs[144..256]) |f| freq9 += f;
        assert(toks.lit_freqs[256] == 1);
        for (toks.lit_freqs[257..280]) |f| freq12 += f;
        for (toks.lit_freqs[280..286]) |f| freq13 += f;
        break :n @as(u32, freq7) * 7 +
            @as(u32, freq8) * 8 + @as(u32, freq9) * 9 +
            @as(u32, freq12) * 12 + @as(u32, freq13) * 13;
    };

    stored: {
        for (toks.dist_freqs) |n| if (n != 0) break :stored;
        // 无需检查 len 频率,因为它们各自都有对应的 dist 频率
        assert(for (toks.lit_freqs[257..]) |f| (if (f != 0) break false) else true);

        // 没有匹配。如果直接存储的大小小于霍夫曼编码后的大小,则
        // 输出为存储块。存在匹配时不这样做,因为窗口可能已经
        // 滑动,因而需要保存原始输入,而且输入也可能超过 65535 字节。
        // 这应当没有问题,因为大多数存在匹配的输入本来就更容易压缩。
        const stored_align_bits = -%(c.bit_writer.buffered_n +% 3);
        const stored_bitsize = stored_align_bits + @as(u32, 32) + @as(u32, toks.n) * 8;
        if (@min(dynamic_bitsize, fixed_bitsize) < stored_bitsize) break :stored;

        try c.bit_writer.write(BlockHeader.int(.{ .kind = .stored, .final = eos }), 3);
        try c.bit_writer.output.rebase(0, 5);
        c.bit_writer.byteAlign();
        c.bit_writer.output.writeInt(u16, c.buffered_tokens.n, .little) catch unreachable;
        c.bit_writer.output.writeInt(u16, ~c.buffered_tokens.n, .little) catch unreachable;

        // 缓冲区相对较小,因为常规排空
        // 总是只消费略少于 2 << 15 字节。
        var vec_buf: [4][]const u8 = undefined;
        var vec_n: usize = 0;
        var i: usize = 0;

        assert(c.buffered_tokens.pos != 0);
        while (i != c.buffered_tokens.pos) {
            const h: TokenBufferEntryHeader = @bitCast(toks.list[i..][0..2].*);
            assert(h.kind == .bytes);

            i += 2;
            vec_buf[vec_n] = toks.list[i..][0..h.data];
            i += h.data;

            vec_n += 1;
            if (i == c.buffered_tokens.pos or vec_n == vec_buf.len) {
                try c.bit_writer.output.writeVecAll(vec_buf[0..vec_n]);
                vec_n = 0;
            }
        }

        toks.* = .empty;
        return;
    }

    const lit_codes, const lit_bits, const dist_codes, const dist_bits =
        if (dynamic_bitsize < fixed_bitsize) codes: {
            try c.bit_writer.write(BlockHeader.Dynamic.int(.{
                .regular = .{ .final = eos, .kind = .dynamic },
                .hlit = @intCast(dyn_lit_len - 257),
                .hdist = @intCast(dyn_dist_len - 1),
                .hclen = hclen,
            }), 17);
            try c.bit_writer.writeClen(
                hclen,
                clen_values[0..clen_len],
                clen_extra[0..clen_len],
                clen_codes,
                clen_bits,
            );
            break :codes .{
                dyn_codes_buf[0..dyn_lit_len],
                dyn_bits_buf[0..dyn_lit_len],
                dyn_codes_buf[dyn_lit_len..][0..dyn_dist_len],
                dyn_bits_buf[dyn_lit_len..][0..dyn_dist_len],
            };
        } else codes: {
            try c.bit_writer.write(BlockHeader.int(.{ .final = eos, .kind = .fixed }), 3);
            break :codes .{
                &token.fixed_lit_codes,
                &token.fixed_lit_bits,
                &token.fixed_dist_codes,
                &token.fixed_dist_bits,
            };
        };

    var i: usize = 0;
    while (i != toks.pos) {
        const h: TokenBufferEntryHeader = @bitCast(toks.list[i..][0..2].*);
        i += 2;
        if (h.kind == .bytes) {
            for (toks.list[i..][0..h.data]) |b| {
                try c.bit_writer.write(lit_codes[b], lit_bits[b]);
            }
            i += h.data;
        } else {
            const dist = h.data;
            const len = toks.list[i];
            i += 1;
            const dist_code = token.DistCode.fromVal(dist);
            const len_code = token.LenCode.fromVal(len);
            const dist_val = dist_code.toInt();
            const lit_val = @as(u16, 257) + len_code.toInt();

            var out: u48 = lit_codes[lit_val];
            var out_bits: u6 = lit_bits[lit_val];
            out |= @shlExact(@as(u20, len - len_code.base()), @intCast(out_bits));
            out_bits += len_code.extraBits();

            out |= @shlExact(@as(u35, dist_codes[dist_val]), out_bits);
            out_bits += dist_bits[dist_val];
            out |= @shlExact(@as(u48, dist - dist_code.base()), out_bits);
            out_bits += dist_code.extraBits();

            try c.bit_writer.write(out, out_bits);
        }
    }
    try c.bit_writer.write(lit_codes[256], lit_bits[256]);

    toks.* = .empty;
}

/// 霍夫曼树构造。
///
/// 构建霍夫曼树的方法[取自 zlib]
/// (https://github.com/madler/zlib/blob/v1.3.1/trees.c#L625),并作了部分修改。
const huffman = struct {
    const max_leafs = 286;
    const max_nodes = max_leafs * 2;

    const Node = packed struct(u32) {
        depth: u16,
        freq: u16,

        pub const Index = u16;

        /// `freq` 比 `depth` 更重要
        pub fn smaller(a: Node, b: Node) bool {
            return @as(u32, @bitCast(a)) < @as(u32, @bitCast(b));
        }
    };

    fn heapSiftDown(nodes: []Node, heap: []Node.Index, start: usize) void {
        var i = start;
        while (true) {
            var min = i;
            const l = i * 2 + 1;
            const r = l + 1;
            min = if (l < heap.len and nodes[heap[l]].smaller(nodes[heap[min]])) l else min;
            min = if (r < heap.len and nodes[heap[r]].smaller(nodes[heap[min]])) r else min;
            if (i == min) break;
            mem.swap(Node.Index, &heap[i], &heap[min]);
            i = min;
        }
    }

    fn heapRemoveRoot(nodes: []Node, heap: []Node.Index) void {
        heap[0] = heap[heap.len - 1];
        heapSiftDown(nodes, heap[0 .. heap.len - 1], 0);
    }

    /// 返回编码 `freqs` 所需的总位数,以及最后一个非零位数的索引。
    /// `freqs[i]` == 0 时,`out_codes[i]` 未定义。
    /// 断言 `out_bits` 已全部置零。
    /// 断言 `out_bits.len` 至少为一,若允许不完整树;否则至少为二。
    ///
    pub fn build(
        freqs: []const u16,
        out_codes: []u16,
        out_bits: []u4,
        max_bits: u4,
        incomplete_allowed: bool,
    ) struct { u32, u16 } {
        assert(out_codes.len - 1 >= @intFromBool(!incomplete_allowed));
        // 将 freqs 和 out_codes 纳入循环,以断言它们的长度均相同。
        for (freqs, out_codes, out_bits) |_, _, n| assert(n == 0);
        assert(out_codes.len <= @as(u16, 1) << max_bits);

        // 索引 0..freqs 为叶节点,索引 max_leafs.. 为内部节点。
        var tree_nodes: [max_nodes]Node = undefined;
        var tree_parent_nodes: [max_nodes]Node.Index = undefined;
        var nodes_end: u16 = max_leafs;
        // 双用途缓冲区。节点按频率从小到大排序;频率相同时,深度较小者优先。
        // 起始部分是零层节点的最小堆。
        // 末尾是最大节点在前的已排序节点缓冲区。
        var node_buf: [max_nodes]Node.Index = undefined;
        var heap_end: u16 = 0;
        var sorted_start: u16 = node_buf.len;

        for (0.., freqs) |n, freq| {
            tree_nodes[n] = .{ .freq = freq, .depth = 0 };
            node_buf[heap_end] = @intCast(n);
            heap_end += @intFromBool(freq != 0);
        }

        // 至少必须有一个编码,
        node_buf[heap_end] = 0;
        heap_end += @intFromBool(heap_end == 0);
        // 如果必须避免不完整情况,则至少需要两个。
        if (heap_end == 1 and incomplete_allowed) {
            @branchHint(.unlikely); // LLVM 21 在没有额外指定时将此分支优化为更可能执行的分支

            // 编码必须至少占一位,因此这是特殊情况。
            out_bits[node_buf[0]] = 1;
            out_codes[node_buf[0]] = 0;
            return .{ freqs[node_buf[0]], node_buf[0] };
        }
        const last_nonzero = @max(node_buf[heap_end - 1], 1); // 当 heap_end > 1 时,last 不为 0
        node_buf[heap_end] = @intFromBool(node_buf[0] == 0);
        heap_end += @intFromBool(heap_end == 1);

        // 将频率数组堆化
        const heapify_final = heap_end - 1;
        const heapify_start = (heapify_final - 1) / 2; // 最终节点的父节点
        var heapify_i = heapify_start;
        while (true) {
            heapSiftDown(&tree_nodes, node_buf[0..heap_end], heapify_i);
            if (heapify_i == 0) break;
            heapify_i -= 1;
        }

        // 构建最优树。尚未强制执行 `max_bits` 限制。
        while (heap_end > 1) {
            const a = node_buf[0];
            heapRemoveRoot(&tree_nodes, node_buf[0..heap_end]);
            heap_end -= 1;
            const b = node_buf[0];

            sorted_start -= 2;
            node_buf[sorted_start..][0..2].* = .{ b, a };

            tree_nodes[nodes_end] = .{
                .freq = tree_nodes[a].freq + tree_nodes[b].freq,
                .depth = @max(tree_nodes[a].depth, tree_nodes[b].depth) + 1,
            };
            defer nodes_end += 1;
            tree_parent_nodes[a] = nodes_end;
            tree_parent_nodes[b] = nodes_end;

            node_buf[0] = nodes_end;
            heapSiftDown(&tree_nodes, node_buf[0..heap_end], 0);
        }
        sorted_start -= 1;
        node_buf[sorted_start] = node_buf[0];

        var bit_counts: [16]u16 = @splat(0);
        buildBits(out_bits, &bit_counts, &tree_parent_nodes, node_buf[sorted_start..], max_bits);
        return .{ buildValues(freqs, out_codes, out_bits, bit_counts), last_nonzero };
    }

    fn buildBits(
        out_bits: []u4,
        bit_counts: *[16]u16,
        parent_nodes: *[max_nodes]Node.Index,
        sorted: []Node.Index,
        max_bits: u4,
    ) void {
        var internal_node_bits: [max_nodes - max_leafs]u4 = undefined;
        var overflowed: u16 = 0;

        internal_node_bits[sorted[0] - max_leafs] = 0; // 根
        for (sorted[1..]) |i| {
            const parent_bits = internal_node_bits[parent_nodes[i] - max_leafs];
            overflowed += @intFromBool(parent_bits == max_bits);
            const bits = parent_bits + @intFromBool(parent_bits != max_bits);
            bit_counts[bits] += @intFromBool(i < max_leafs);
            (if (i >= max_leafs) &internal_node_bits[i - max_leafs] else &out_bits[i]).* = bits;
        }

        if (overflowed == 0) {
            @branchHint(.likely);
            return;
        }

        outer: while (true) {
            var deepest: u4 = max_bits - 1;
            while (bit_counts[deepest] == 0) deepest -= 1;
            while (overflowed != 0) {
                // 在叶节点下插入内部节点,并将溢出节点移为其兄弟节点
                bit_counts[deepest] -= 1;
                bit_counts[deepest + 1] += 2;
                // 仅移动了溢出部分。其兄弟节点深度小一,但仍 >= depth。
                bit_counts[max_bits] -= 1;
                overflowed -= 2;

                if (overflowed == 0) break :outer;
                deepest += 1;
                if (deepest == max_bits) continue :outer;
            }
        }

        // 重新分配位长度
        assert(bit_counts[0] == 0);
        var i: usize = 0;
        for (1.., bit_counts[1..]) |bits, all| {
            var remaining = all;
            while (remaining != 0) {
                defer i += 1;
                if (sorted[i] >= max_leafs) continue;
                out_bits[sorted[i]] = @intCast(bits);
                remaining -= 1;
            }
        }
        assert(for (sorted[i..]) |n| { // 所有叶节点已消耗
            if (n < max_leafs) break false;
        } else true);
    }

    fn buildValues(freqs: []const u16, out_codes: []u16, bits: []u4, bit_counts: [16]u16) u32 {
        var code: u16 = 0;
        var base: [16]u16 = undefined;
        assert(bit_counts[0] == 0);
        for (bit_counts[1..], base[1..]) |c, *b| {
            b.* = code;
            code +%= c;
            code <<= 1;
        }
        var freq_sums: [16]u16 = @splat(0);
        for (out_codes, bits, freqs) |*c, b, f| {
            c.* = @bitReverse(base[b]) >> -%b;
            base[b] += 1; // `b == 0` 时没有问题,因为 v 被规定为未定义。
            freq_sums[b] += f;
        }
        return @reduce(.Add, @as(@Vector(16, u32), freq_sums) * std.simd.iota(u32, 16));
    }

    test build {
        var codes: [8]u16 = undefined;
        var bits: [8]u4 = undefined;

        const regular_freqs: [8]u16 = .{ 1, 1, 0, 8, 8, 0, 2, 4 };
        // 上述频率对应的最优树为
        // 4             1   1
        //                \ /
        // 3           2   #
        //              \ /
        // 2   8   8 4   #
        //      \ /   \ /
        // 1     #     #
        //        \   /
        // 0        #
        bits = @splat(0);
        var n, var lnz = build(&regular_freqs, &codes, &bits, 15, true);
        codes[2] = 0;
        codes[5] = 0;
        try std.testing.expectEqualSlices(u4, &.{ 4, 4, 0, 2, 2, 0, 3, 2 }, &bits);
        try std.testing.expectEqualSlices(u16, &.{
            0b0111, 0b1111, 0, 0b00, 0b10, 0, 0b011, 0b01,
        }, &codes);
        try std.testing.expectEqual(54, n);
        try std.testing.expectEqual(7, lnz);
        // 限制为 3 位时,变为
        // 3        1   1 2   4
        //           \ /   \ /
        // 2   8   8  #     #
        //      \ /    \   /
        // 1     #       #
        //        \     /
        // 0         #
        bits = @splat(0);
        n, lnz = build(&regular_freqs, &codes, &bits, 3, true);
        codes[2] = 0;
        codes[5] = 0;
        try std.testing.expectEqualSlices(u4, &.{ 3, 3, 0, 2, 2, 0, 3, 3 }, &bits);
        try std.testing.expectEqualSlices(u16, &.{
            0b001, 0b101, 0, 0b00, 0b10, 0, 0b011, 0b111,
        }, &codes);
        try std.testing.expectEqual(56, n);
        try std.testing.expectEqual(7, lnz);

        // 空树。必须至少存在一个代码
        bits = @splat(0);
        n, lnz = build(&.{ 0, 0 }, codes[0..2], bits[0..2], 15, true);
        try std.testing.expectEqualSlices(u4, &.{ 1, 0 }, bits[0..2]);
        try std.testing.expectEqual(0b0, codes[0]);
        try std.testing.expectEqual(0, n);
        try std.testing.expectEqual(0, lnz);

        // 检查所有无法补全的频数均已补全
        for ([_][2]u16{ .{ 0, 0 }, .{ 0, 1 }, .{ 1, 0 } }) |incomplete| {
            // 空树。必须同时存在两个代码,以避免不完整树
            bits = @splat(0);
            n, lnz = build(&incomplete, codes[0..2], bits[0..2], 15, false);
            try std.testing.expectEqualSlices(u4, &.{ 1, 1 }, bits[0..2]);
            try std.testing.expectEqualSlices(u16, &.{ 0b0, 0b1 }, codes[0..2]);
            try std.testing.expectEqual(incomplete[0] + incomplete[1], n);
            try std.testing.expectEqual(1, lnz);
        }

        try std.testing.fuzz({}, checkFuzzedBuildFreqs, .{});
    }

    fn checkFuzzedBuildFreqs(_: void, smith: *std.testing.Smith) !void {
        @disableInstrumentation();
        var freqs_limit: u16 = 65535;
        var freqs_buf: [max_leafs]u16 = undefined;
        var nfreqs: u15 = 0;

        const incomplete_allowed = smith.value(bool);
        while (nfreqs < @as(u8, @intFromBool(!incomplete_allowed)) + 1 or
            nfreqs != freqs_buf.len and freqs_limit != 0 and
                smith.eosWeightedSimple(15, 1))
        {
            const f = smith.valueWeighted(u16, &.{
                .rangeAtMost(u16, 0, @min(31, freqs_limit), @max(freqs_limit, 1)),
                .rangeAtMost(u16, 0, freqs_limit, 1),
            });
            freqs_buf[nfreqs] = f;
            freqs_limit -= f;
            nfreqs += 1;
        }

        var codes_buf: [max_leafs]u16 = undefined;
        var bits_buf: [max_leafs]u4 = @splat(0);
        const max_bits = smith.valueRangeAtMost(u4, math.log2_int_ceil(u15, nfreqs), 15);
        const total_bits, const last_nonzero = build(
            freqs_buf[0..nfreqs],
            codes_buf[0..nfreqs],
            bits_buf[0..nfreqs],
            max_bits,
            incomplete_allowed,
        );

        var has_bitlen_one: bool = false;
        var expected_total_bits: u32 = 0;
        var expected_last_nonzero: ?u16 = null;
        var weighted_sum: u32 = 0;
        for (freqs_buf[0..nfreqs], bits_buf[0..nfreqs], 0..) |f, nb, i| {
            has_bitlen_one = has_bitlen_one or nb == 1;
            weighted_sum += @shlExact(@as(u16, 1), 15 - nb) & ((1 << 15) - 1);
            expected_total_bits += @as(u32, f) * nb;
            if (nb != 0) expected_last_nonzero = @intCast(i);
        }

        errdefer std.log.err(
            \\ incomplete_allowed: {}
            \\ max_bits: {}
            \\ freqs: {any}
            \\ bits: {any}
            \\ # freqs: {}
            \\ weighted sum: {}
            \\ has_bitlen_one: {}
            \\ expected/actual total bits: {}/{}
            \\ expected/actual last nonzero: {?}/{}
        ++ "\n", .{
            incomplete_allowed,
            max_bits,
            freqs_buf[0..nfreqs],
            bits_buf[0..nfreqs],
            nfreqs,
            weighted_sum,
            has_bitlen_one,
            expected_total_bits,
            total_bits,
            expected_last_nonzero,
            last_nonzero,
        });

        try std.testing.expectEqual(expected_total_bits, total_bits);
        try std.testing.expectEqual(expected_last_nonzero, last_nonzero);
        if (weighted_sum > 1 << 15)
            return error.OversubscribedHuffmanTree;
        if (weighted_sum < 1 << 15 and
            !(incomplete_allowed and has_bitlen_one and weighted_sum == 1 << 14))
            return error.IncompleteHuffmanTree;
    }
};

test {
    _ = huffman;
}

/// [0] 为渐变数据,其中低值的概率逐渐降低
/// [1] 完全随机,因此不可压缩
fn testingFreqBufs() !*[2][65536]u8 {
    const fbufs = try std.testing.allocator.create([2][65536]u8);
    var prng: std.Random.DefaultPrng = .init(std.testing.random_seed);
    prng.random().bytes(&fbufs[0]);
    prng.random().bytes(&fbufs[1]);
    for (0.., &fbufs[0], fbufs[1]) |i, *grad, rand| {
        const prob = @as(u8, @intCast(255 - i / (fbufs[0].len * 256)));
        grad.* /= @max(1, rand / @max(1, prob));
    }
    return fbufs;
}
const FreqBufIndex = enum(u1) { gradient, random };

fn testingCheckDecompressedMatches(
    flate_bytes: []const u8,
    expected_size: u32,
    expected_hash: flate.Container.Hasher,
) !void {
    const container: flate.Container = expected_hash;
    var data_hash: flate.Container.Hasher = .init(container);
    var data_size: u32 = 0;
    var flate_r: Io.Reader = .fixed(flate_bytes);
    var deflate_buf: [flate.max_window_len]u8 = undefined;
    var deflate: flate.Decompress = .init(&flate_r, container, &deflate_buf);

    while (deflate.reader.peekGreedy(1)) |bytes| {
        data_size += @intCast(bytes.len);
        data_hash.update(bytes);
        deflate.reader.toss(bytes.len);
    } else |e| switch (e) {
        error.ReadFailed => return deflate.err.?,
        error.EndOfStream => {},
    }

    try testingCheckContainerHash(
        expected_size,
        expected_hash,
        data_hash,
        data_size,
        deflate.container_metadata,
    );
}

fn testingCheckContainerHash(
    expected_size: u32,
    expected_hash: flate.Container.Hasher,
    actual_hash: flate.Container.Hasher,
    actual_size: u32,
    actual_meta: flate.Container.Metadata,
) !void {
    try std.testing.expectEqual(expected_size, actual_size);
    switch (actual_hash) {
        .raw => {},
        .gzip => |gz| {
            const expected_crc = expected_hash.gzip.crc.final();
            try std.testing.expectEqual(expected_size, actual_meta.gzip.count);
            try std.testing.expectEqual(expected_crc, gz.crc.final());
            try std.testing.expectEqual(expected_crc, actual_meta.gzip.crc);
        },
        .zlib => |zl| {
            const expected_adler = expected_hash.zlib.adler;
            try std.testing.expectEqual(expected_adler, zl.adler);
            try std.testing.expectEqual(expected_adler, actual_meta.zlib.adler);
        },
    }
}

const PackedContainer = packed struct(u2) {
    raw: bool,
    other: enum(u1) { gzip, zlib },

    pub fn val(c: @This()) flate.Container {
        return if (c.raw) .raw else switch (c.other) {
            .gzip => .gzip,
            .zlib => .zlib,
        };
    }
};

test Compress {
    const fbufs = try testingFreqBufs();
    defer std.testing.allocator.destroy(fbufs);
    try std.testing.fuzz(fbufs, testFuzzedCompressInput, .{});
}

fn testFuzzedCompressInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void {
    @disableInstrumentation();
    const container = smith.value(flate.Container);
    const good = smith.valueRangeAtMost(u16, 3, 258);
    const nice = smith.valueRangeAtMost(u16, 3, 258);
    const lazy = smith.valueRangeAtMost(u16, 3, nice);
    const chain = smith.valueWeighted(u16, &.{
        .rangeAtMost(u16, if (good <= lazy) 4 else 1, 255, 65536),
        // 大幅降低以下权重,因为它们会耗费越来越多的运行时间
        .rangeAtMost(u16, 256, 4095, 256),
        .rangeAtMost(u16, 4096, 32767 + 256, 1),
    });
    var expected_hash: flate.Container.Hasher = .init(container);
    var expected_size: u32 = 0;

    var flate_buf: [128 * 1024]u8 = undefined;
    var flate_w: Writer = .fixed(&flate_buf);
    var deflate_buf: [flate.max_window_len * 2]u8 = undefined;
    const bufsize = smith.valueRangeAtMost(u32, flate.max_window_len, @intCast(deflate_buf.len));
    var deflate_w = try Compress.init(&flate_w, deflate_buf[0..bufsize], container, .{
        .good = good,
        .nice = nice,
        .lazy = lazy,
        .chain = chain,
    });

    var max_output: usize = 32; // 头部 / 尾部
    while (!smith.eosWeightedSimple(7, 1)) {
        const buffered = deflate_w.writer.buffered();
        // 重复模式需要此操作,而且从 `buffered` 写入属于非法操作。
        var copy_buf: [512]u8 = undefined;

        const bytes = bytes: switch (smith.valueRangeAtMost(
            u2,
            @intFromBool(buffered.len == 0),
            3,
        )) {
            0 => { // 复制
                const start = smith.valueRangeLessThan(u32, 0, @intCast(buffered.len));
                // 复用实现的历史记录;否则需要自行维护历史记录。
                const from = buffered[start..];
                const len = smith.valueRangeAtMost(u16, 1, copy_buf.len);

                const history_bytes = from[0..@min(from.len, len)];
                @memcpy(copy_buf[0..history_bytes.len], history_bytes);
                const repeat_len = len - history_bytes.len;
                for (
                    copy_buf[history_bytes.len..][0..repeat_len],
                    copy_buf[0..repeat_len],
                ) |*next, prev| {
                    next.* = prev;
                }
                break :bytes copy_buf[0..len];
            },
            1 => { // 字节
                const fbuf = &fbufs[
                    smith.valueWeighted(u1, &.{
                        .value(FreqBufIndex, .gradient, 3),
                        .value(FreqBufIndex, .random, 1),
                    })
                ];
                const len = smith.valueRangeAtMost(u32, 1, fbuf.len);
                const off = smith.valueRangeAtMost(u32, 0, @intCast(fbuf.len - len));
                break :bytes fbuf[off..][0..len];
            },
            2 => { // 重设基址
                const rebaseable = bufsize - rebase_reserved_capacity;
                const capacity = smith.valueRangeAtMost(u32, 1, rebaseable - rebase_min_preserve);
                const preserve = smith.valueRangeAtMost(u32, 0, rebaseable - capacity);
                const failed = deflate_w.writer.rebase(preserve, capacity);
                if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
                failed catch return; // 写入数据过多,空间耗尽
                continue;
            },
            3 => { // 刷新
                max_output += 8; // 对齐数据
                const failed = deflate_w.writer.flush();
                if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
                failed catch return; // 写入数据过多,空间耗尽
                continue;
            },
        };

        // 为每个块预留 64 字节开销,因为此实现不保证在最优时机写入存储块。
        // 该值来自两部分:主要由位长 8 的编码构成的最优动态块头及块结束字面量所需空间少于 32 字节,再加上 `(65536 / 256) / 8`,即位长 9 的编码最多带来的额外字节数。
        //
        //
        //
        max_output += bytes.len + ((bytes.len + flate_buf.len - 1) / block_tokens) * 64;
        const failed = deflate_w.writer.writeAll(bytes);
        if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
        failed catch return; // 写入数据过多,空间耗尽
        expected_hash.update(bytes);
        expected_size += @intCast(bytes.len);
    }

    const failed = deflate_w.finish();
    if (flate_w.buffered().len > max_output) return error.OverheadTooLarge;
    failed catch return; // 写入数据过多,空间耗尽
    try testingCheckDecompressedMatches(flate_w.buffered(), expected_size, expected_hash);
}

/// 不压缩数据
pub const Raw = struct {
    /// 调用 `finish` 后,所有虚函数表调用均产生 `error.WriteFailed`。
    writer: Writer,
    output: *Writer,
    hasher: flate.Container.Hasher,

    const max_block_size: u16 = 65535;
    const full_header: [5]u8 = .{
        BlockHeader.int(.{ .final = false, .kind = .stored }),
        255,
        255,
        0,
        0,
    };

    /// 虽然没有最小缓冲区大小要求,但建议至少为
    /// `flate.max_window_len`,以获得最佳输出效果。
    pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Raw {
        try output.writeAll(container.header());
        return .{
            .writer = .{
                .buffer = buffer,
                .vtable = &.{
                    .drain = Raw.drain,
                    .flush = Raw.flush,
                    .rebase = Raw.rebase,
                },
            },
            .output = output,
            .hasher = .init(container),
        };
    }

    fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
        errdefer w.* = .failing;
        const r: *Raw = @fieldParentPtr("writer", w);
        const min_block = @min(w.buffer.len, max_block_size);
        const pattern = data[data.len - 1];
        var partial_header: [5]u8 = undefined;

        var vecs: [16][]const u8 = undefined;
        var vecs_n: usize = 0;
        const data_bytes = Writer.countSplat(data, splat);
        const total_bytes = w.end + data_bytes;
        var rem_bytes = total_bytes;
        var rem_splat = splat;
        var rem_data = data;
        var rem_data_elem: []const u8 = w.buffered();

        assert(rem_bytes > min_block);
        while (rem_bytes > min_block) { // 不使用 >=,以允许 `min_block` 大小的块标记为最终块
            // 同时处理 `min_block` 为零(无缓冲区)的情况
            const block_size: u16 = @min(rem_bytes, max_block_size);
            rem_bytes -= block_size;

            if (vecs_n == vecs.len) {
                try r.output.writeVecAll(&vecs);
                vecs_n = 0;
            }
            vecs[vecs_n] = if (block_size == 65535)
                &full_header
            else header: {
                partial_header[0] = BlockHeader.int(.{ .final = false, .kind = .stored });
                mem.writeInt(u16, partial_header[1..3], block_size, .little);
                mem.writeInt(u16, partial_header[3..5], ~block_size, .little);
                break :header &partial_header;
            };
            vecs_n += 1;

            var block_limit: Io.Limit = .limited(block_size);
            while (true) {
                if (vecs_n == vecs.len) {
                    try r.output.writeVecAll(&vecs);
                    vecs_n = 0;
                }

                const vec = block_limit.sliceConst(rem_data_elem);
                vecs[vecs_n] = vec;
                vecs_n += 1;
                r.hasher.update(vec);

                const is_pattern = rem_splat != splat and vec.len == pattern.len;
                if (is_pattern) assert(pattern.len != 0); // 超过 countSplat

                if (!is_pattern or rem_splat == 0 or pattern.len > @backingInt(block_limit) / 2) {
                    rem_data_elem = rem_data_elem[vec.len..];
                    block_limit = block_limit.subtract(vec.len).?;

                    if (rem_data_elem.len == 0) {
                        rem_data_elem = rem_data[0];
                        if (rem_data.len != 1) {
                            rem_data = rem_data[1..];
                        } else if (rem_splat != 0) {
                            rem_splat -= 1;
                        } else {
                            // 已消耗全部 `data`。
                            assert(block_limit == .nothing);
                            assert(rem_bytes == 0);
                            // 由于 `rem_bytes` 和 `block_limit` 为零,这些值不会被使用。
                            rem_data = undefined;
                            rem_data_elem = undefined;
                            rem_splat = undefined;
                        }
                    }
                    if (block_limit == .nothing) break;
                } else {
                    const out_splat = @backingInt(block_limit) / pattern.len;
                    assert(out_splat >= 2);

                    try r.output.writeSplatAll(vecs[0..vecs_n], out_splat);
                    for (1..out_splat) |_| r.hasher.update(vec);

                    vecs_n = 0;
                    block_limit = block_limit.subtract(pattern.len * out_splat).?;
                    if (rem_splat >= out_splat) {
                        // `out_splat` 包含 `rem_data`,不过由于还会取下一个模式,
                        // 仍须再减去一个。
                        rem_splat -= out_splat;
                    } else {
                        // 已消耗全部 `data`。
                        assert(block_limit == .nothing);
                        assert(rem_bytes == 0);
                        // 由于 `rem_bytes` 和 `block_limit` 为零,这些值不会被使用。
                        rem_data = undefined;
                        rem_data_elem = undefined;
                        rem_splat = undefined;
                    }
                    if (block_limit == .nothing) break;
                }
            }
        }

        if (vecs_n != 0) { // 若发送了 splat,可能会出现这种情况
            try r.output.writeVecAll(vecs[0..vecs_n]);
        }

        if (rem_bytes > data_bytes) {
            assert(rem_bytes - data_bytes == rem_data_elem.len);
            assert(&rem_data_elem[0] == &w.buffer[total_bytes - rem_bytes]);
        }
        return w.consume(total_bytes - rem_bytes);
    }

    fn flush(w: *Writer) Writer.Error!void {
        errdefer w.* = .failing;
        try Raw.rebaseInner(w, 0, w.buffer.len, false);
    }

    pub fn finish(r: *Raw) Writer.Error!void {
        defer r.writer = .failing;
        try Raw.rebaseInner(&r.writer, 0, r.writer.buffer.len, true);
        // 尾部在 `rebaseInner` 中作为写入向量的一部分写入
    }

    fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
        errdefer w.* = .failing;
        try Raw.rebaseInner(w, preserve, capacity, false);
    }

    fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void {
        const r: *Raw = @fieldParentPtr("writer", w);
        assert(preserve + capacity <= w.buffer.len);
        if (eos) assert(capacity == w.buffer.len);

        var partial_header: [5]u8 = undefined;
        var footer_buf: [8]u8 = undefined;
        const preserved = @min(w.end, preserve);
        var remaining = w.buffer[0 .. w.end - preserved];

        var vecs: [16][]const u8 = undefined;
        var vecs_n: usize = 0;
        while (remaining.len > max_block_size) { // 不使用 >=,以确保下方始终保留一个块
            if (vecs_n == vecs.len) {
                try r.output.writeVecAll(&vecs);
                vecs_n = 0;
            }
            vecs[vecs_n + 0] = &full_header;
            vecs[vecs_n + 1] = remaining[0..max_block_size];
            r.hasher.update(vecs[vecs_n + 1]);
            vecs_n += 2;
            remaining = remaining[max_block_size..];
        }

        // 空分组需要进行 eos 检查
        if (w.buffer.len - (remaining.len + preserved) < capacity or eos) {
            // 必须进行部分写入,才能回收足够的缓冲区空间
            const block_size: u16 = @intCast(remaining.len);
            partial_header[0] = BlockHeader.int(.{ .final = eos, .kind = .stored });
            mem.writeInt(u16, partial_header[1..3], block_size, .little);
            mem.writeInt(u16, partial_header[3..5], ~block_size, .little);

            if (vecs_n == vecs.len) {
                try r.output.writeVecAll(&vecs);
                vecs_n = 0;
            }
            vecs[vecs_n + 0] = &partial_header;
            vecs[vecs_n + 1] = remaining[0..block_size];
            r.hasher.update(vecs[vecs_n + 1]);
            vecs_n += 2;
            remaining = remaining[block_size..];
            assert(remaining.len == 0);

            if (eos and r.hasher != .raw) {
                // 在此处而非 `flush` 中写入尾部,使其可包含在向量中
                var footer_w: Writer = .fixed(&footer_buf);
                r.hasher.writeFooter(&footer_w) catch unreachable;
                assert(footer_w.end != 0);

                if (vecs_n == vecs.len) {
                    try r.output.writeVecAll(&vecs);
                    return r.output.writeAll(footer_w.buffered());
                } else {
                    vecs[vecs_n] = footer_w.buffered();
                    vecs_n += 1;
                }
            }
        }

        try r.output.writeVecAll(vecs[0..vecs_n]);
        _ = w.consume(w.end - preserved - remaining.len);
    }
};

test Raw {
    const data_buf = try std.testing.allocator.create([4 * 65536]u8);
    defer std.testing.allocator.destroy(data_buf);
    var prng: std.Random.DefaultPrng = .init(std.testing.random_seed);
    prng.random().bytes(data_buf);
    try std.testing.fuzz(data_buf, testFuzzedRawInput, .{});
}

fn countVec(data: []const []const u8) usize {
    var bytes: usize = 0;
    for (data) |d| bytes += d.len;
    return bytes;
}

fn testFuzzedRawInput(data_buf: *const [4 * 65536]u8, smith: *std.testing.Smith) !void {
    @disableInstrumentation();
    const HashedStoreWriter = struct {
        writer: Writer,
        state: enum {
            header,
            block_header,
            block_body,
            final_block_body,
            footer,
            end,
        },
        block_remaining: u16,
        container: flate.Container,
        data_hash: flate.Container.Hasher,
        data_size: usize,
        footer_hash: u32,
        footer_size: u32,

        pub fn init(buf: []u8, container: flate.Container) @This() {
            return .{
                .writer = .{
                    .vtable = &.{
                        .drain = @This().drain,
                        .flush = @This().flush,
                    },
                    .buffer = buf,
                },
                .state = .header,
                .block_remaining = 0,
                .container = container,
                .data_hash = .init(container),
                .data_size = 0,
                .footer_hash = undefined,
                .footer_size = undefined,
            };
        }

        /// 注意,此实现一定程度上依赖 `Raw` 的实现,
        /// 假定头部/尾部在数据元素中连续。
        /// 还假定头部与 `flate.Container.header` 相同,
        /// 且多个流不会拼接。
        fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
            errdefer w.* = .failing;
            var h: *@This() = @fieldParentPtr("writer", w);

            var rem_splat = splat;
            var rem_data = data;
            var rem_data_elem: []const u8 = w.buffered();

            data_loop: while (true) {
                const wanted = switch (h.state) {
                    .header => h.container.headerSize(),
                    .block_header => 5,
                    .block_body, .final_block_body => h.block_remaining,
                    .footer => h.container.footerSize(),
                    .end => 1,
                };

                if (wanted != 0) {
                    while (rem_data_elem.len == 0) {
                        rem_data_elem = rem_data[0];
                        if (rem_data.len != 1) {
                            rem_data = rem_data[1..];
                        } else {
                            if (rem_splat == 0) {
                                break :data_loop;
                            } else {
                                rem_splat -= 1;
                            }
                        }
                    }
                }

                const bytes = Io.Limit.limited(wanted).sliceConst(rem_data_elem);
                rem_data_elem = rem_data_elem[bytes.len..];

                switch (h.state) {
                    .header => {
                        if (bytes.len < wanted)
                            return error.WriteFailed; // 头部流结束
                        if (!mem.eql(u8, bytes, h.container.header()))
                            return error.WriteFailed; // 头部错误
                        h.state = .block_header;
                    },
                    .block_header => {
                        if (bytes.len < wanted)
                            return error.WriteFailed; // 存储块头 eos
                        const header: BlockHeader = @bitCast(@as(u3, @truncate(bytes[0])));
                        if (header.kind != .stored)
                            return error.WriteFailed; // 非存储块
                        const len = mem.readInt(u16, bytes[1..3], .little);
                        const nlen = mem.readInt(u16, bytes[3..5], .little);
                        if (nlen != ~len)
                            return error.WriteFailed; // 错误的 nlen
                        h.block_remaining = len;
                        h.state = if (!header.final) .block_body else .final_block_body;
                    },
                    .block_body, .final_block_body => {
                        h.data_hash.update(bytes);
                        h.data_size += bytes.len;
                        h.block_remaining -= @intCast(bytes.len);
                        if (h.block_remaining == 0) {
                            h.state = if (h.state != .final_block_body) .block_header else .footer;
                        }
                    },
                    .footer => {
                        if (bytes.len < wanted)
                            return error.WriteFailed; // 尾部流结束
                        switch (h.container) {
                            .raw => {},
                            .gzip => {
                                h.footer_hash = mem.readInt(u32, bytes[0..4], .little);
                                h.footer_size = mem.readInt(u32, bytes[4..8], .little);
                            },
                            .zlib => {
                                h.footer_hash = mem.readInt(u32, bytes[0..4], .big);
                            },
                        }
                        h.state = .end;
                    },
                    .end => return error.WriteFailed, // 数据超出末尾
                }
            }

            w.end = 0;
            return Writer.countSplat(data, splat);
        }

        fn flush(w: *Writer) Writer.Error!void {
            defer w.* = .failing; // 即使状态尚未到达 `end`,也会清空缓冲区
            _ = try @This().drain(w, &.{""}, 0);
        }
    };

    const container = smith.value(flate.Container);
    var output: HashedStoreWriter = .init(&.{}, container);
    var expected_hash: flate.Container.Hasher = .init(container);
    var expected_size: u32 = 0;
    // 选择最多 10 个块作为限制,因为这比
    // 实现一次 drain 最多输出的块数多两个。
    const max_size = 10 * @as(u32, Raw.max_block_size);

    var raw_buf: [2 * @as(usize, Raw.max_block_size)]u8 = undefined;
    const raw_buf_len = smith.valueWeighted(u32, &.{
        .value(u32, 0, @intCast(raw_buf.len)), // 无缓冲
        .rangeAtMost(u32, 0, @intCast(raw_buf.len), 1),
    });
    var raw: Raw = try .init(&output.writer, raw_buf[0..raw_buf_len], container);

    const data_buf_len: u32 = @intCast(data_buf.len);
    var vecs: [32][]const u8 = undefined;
    var vecs_n: usize = 0;

    while (true) {
        const Op = packed struct {
            drain: bool = false,
            add_vec: bool = false,
            rebase: enum(u2) { none, rebase, flush } = .none,

            pub const drain_only: @This() = .{ .drain = true };
            pub const add_vec_only: @This() = .{ .add_vec = true };
            pub const add_vec_and_drain: @This() = .{ .add_vec = true, .drain = true };
            pub const drain_and_rebase: @This() = .{ .drain = true, .rebase = .rebase };
            pub const drain_and_flush: @This() = .{ .drain = true, .rebase = .flush };
        };

        const is_eos = expected_size == max_size or smith.eosWeightedSimple(7, 1);
        var op: Op = if (!is_eos) smith.valueWeighted(Op, &.{
            .value(Op, .add_vec_only, 5),
            .value(Op, .add_vec_and_drain, 1),
            .value(Op, .drain_and_rebase, 1),
            .value(Op, .drain_and_flush, 1),
        }) else .drain_only;

        if (op.add_vec) {
            const max_write = max_size - expected_size;
            const buffered: u32 = @intCast(raw.writer.buffered().len + countVec(vecs[0..vecs_n]));
            const to_align = Raw.max_block_size - buffered % Raw.max_block_size;
            assert(to_align != 0); // 否则没有帮助。

            const max_data = @min(data_buf_len, max_write);
            const len = smith.valueWeighted(u32, &.{
                .rangeAtMost(u32, 0, max_data, 1),
                .rangeAtMost(u32, 0, @min(Raw.max_block_size, max_data), 4),
                .value(u32, @min(to_align, max_data), max_data), // @min 的第二个参数是边界情况
            });
            const off = smith.valueRangeAtMost(u32, 0, data_buf_len - len);

            expected_size += len;
            vecs[vecs_n] = data_buf[off..][0..len];
            vecs_n += 1;
            op.drain |= vecs_n == vecs.len;
        }

        op.drain |= is_eos;
        op.drain &= vecs_n != 0;
        if (op.drain) {
            const pattern_len: u32 = @intCast(vecs[vecs_n - 1].len);
            const pattern_len_z = @max(pattern_len, 1);

            const max_write = max_size - (expected_size - pattern_len);
            const buffered: u32 = @intCast(raw.writer.buffered().len + countVec(vecs[0 .. vecs_n - 1]));
            const to_align = Raw.max_block_size - buffered % Raw.max_block_size;
            assert(to_align != 0); // 否则没有帮助。

            const max_splat = max_write / pattern_len_z;
            const weights: [3]std.testing.Smith.Weight = .{
                .rangeAtMost(u32, 0, max_splat, 1),
                .rangeAtMost(u32, 0, @min(
                    Raw.max_block_size + pattern_len_z,
                    max_write,
                ) / pattern_len_z, 4),
                .value(u32, to_align / pattern_len_z, max_splat * 4),
            };
            const align_weight = to_align % pattern_len_z == 0 and to_align <= max_write;
            const n_weights = @as(u8, 2) + @intFromBool(align_weight);
            const splat = smith.valueWeighted(u32, weights[0..n_weights]);

            expected_size = expected_size - pattern_len + pattern_len * splat; // splat 可以为零
            for (vecs[0 .. vecs_n - 1]) |v| expected_hash.update(v);
            for (0..splat) |_| expected_hash.update(vecs[vecs_n - 1]);
            try raw.writer.writeSplatAll(vecs[0..vecs_n], splat);
            vecs_n = 0;
        }

        switch (op.rebase) {
            .none => {},
            .rebase => {
                const capacity = smith.valueRangeAtMost(u32, 0, raw_buf_len);
                const preserve = smith.valueRangeAtMost(u32, 0, raw_buf_len - capacity);
                try raw.writer.rebase(preserve, capacity);
            },
            .flush => try raw.writer.flush(),
        }

        if (is_eos) break;
    }

    try raw.finish();
    try output.writer.flush();

    try std.testing.expectEqual(.end, output.state);
    try std.testing.expectEqual(expected_size, output.data_size);
    switch (output.data_hash) {
        .raw => {},
        .gzip => |gz| {
            const expected_crc = expected_hash.gzip.crc.final();
            try std.testing.expectEqual(expected_crc, gz.crc.final());
            try std.testing.expectEqual(expected_crc, output.footer_hash);
            try std.testing.expectEqual(expected_size, output.footer_size);
        },
        .zlib => |zl| {
            const expected_adler = expected_hash.zlib.adler;
            try std.testing.expectEqual(expected_adler, zl.adler);
            try std.testing.expectEqual(expected_adler, output.footer_hash);
        },
    }
}

/// 仅对数据进行 Huffman 压缩,不执行匹配。
pub const Huffman = struct {
    /// 调用 `finish` 后,所有虚函数表调用均产生 `error.WriteFailed`。
    writer: Writer,
    bit_writer: BitWriter,
    hasher: flate.Container.Hasher,

    const max_tokens: u16 = 65535 - 1; // 其中一个值保留给 EOF

    /// 虽然没有最小缓冲区大小要求,但建议
    /// 至少为 `flate.max_window_len`,以改善压缩效果。
    ///
    /// 断言 `output` 的容量至少为 8 字节。
    pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Huffman {
        assert(output.buffer.len > 8);

        try output.writeAll(container.header());
        return .{
            .writer = .{
                .buffer = buffer,
                .vtable = &.{
                    .drain = Huffman.drain,
                    .flush = Huffman.flush,
                    .rebase = Huffman.rebase,
                },
            },
            .bit_writer = .init(output),
            .hasher = .init(container),
        };
    }

    fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
        const h: *Huffman = @fieldParentPtr("writer", w);
        const min_block = @min(w.buffer.len, max_tokens);
        const pattern = data[data.len - 1];

        const data_bytes = Writer.countSplat(data, splat);
        const total_bytes = w.end + data_bytes;
        var rem_bytes = total_bytes;
        var rem_splat = splat;
        var rem_data = data;
        var rem_data_elem: []const u8 = w.buffered();

        assert(rem_bytes > min_block);
        while (rem_bytes > min_block) { // 不使用 >=,以允许 `min_block` 大小的块标记为最终块
            // 同时处理 `min_block` 为零(无缓冲区)的情况
            const block_size: u16 = @min(rem_bytes, max_tokens);
            rem_bytes -= block_size;

            // 统计频率
            comptime assert(max_tokens != 65535);
            var freqs: [257]u16 = @splat(0);
            freqs[256] = 1;

            const start_splat = rem_splat;
            const start_data = rem_data;
            const start_data_elem = rem_data_elem;

            var block_limit: Io.Limit = .limited(block_size);
            while (true) {
                const bytes = block_limit.sliceConst(rem_data_elem);
                const is_pattern = rem_splat != splat and bytes.len == pattern.len;

                const mul = if (!is_pattern) 1 else @backingInt(block_limit) / pattern.len;
                assert(mul != 0);
                if (is_pattern) assert(mul <= rem_splat + 1); // 为 `rem_data` 再增加一个

                for (bytes) |b| freqs[b] += @intCast(mul);
                rem_data_elem = rem_data_elem[bytes.len..];
                block_limit = block_limit.subtract(bytes.len * mul).?;

                if (rem_data_elem.len == 0) {
                    rem_data_elem = rem_data[0];
                    if (rem_data.len != 1) {
                        rem_data = rem_data[1..];
                    } else if (rem_splat >= mul) {
                        // 若计数器并非模式,`mul` 始终为一;否则
                        // `mul` 包含 `rem_data`,但无论如何还需再减一,
                        // 因为也会取走下一个模式。
                        rem_splat -= mul;
                    } else {
                        // 已消耗全部 `data`。
                        assert(block_limit == .nothing);
                        assert(rem_bytes == 0);
                        // 由于 `rem_bytes` 和 `block_limit` 为零,这些值不会被使用。
                        rem_data = undefined;
                        rem_data_elem = undefined;
                        rem_splat = undefined;
                    }
                }
                if (block_limit == .nothing) break;
            }

            // 输出数据块
            rem_splat = start_splat;
            rem_data = start_data;
            rem_data_elem = start_data_elem;
            block_limit = .limited(block_size);

            var codes_buf: CodesBuf = .init;
            if (try h.outputHeader(&freqs, &codes_buf, block_size, false)) |table| {
                while (true) {
                    const bytes = block_limit.sliceConst(rem_data_elem);
                    rem_data_elem = rem_data_elem[bytes.len..];
                    block_limit = block_limit.subtract(bytes.len).?;

                    h.hasher.update(bytes);
                    for (bytes) |b| {
                        try h.bit_writer.write(table.codes[b], table.bits[b]);
                    }

                    if (rem_data_elem.len == 0) {
                        rem_data_elem = rem_data[0];
                        if (rem_data.len != 1) {
                            rem_data = rem_data[1..];
                        } else if (rem_splat != 0) {
                            rem_splat -= 1;
                        } else {
                            // 已消耗全部 `data`。
                            assert(block_limit == .nothing);
                            assert(rem_bytes == 0);
                            // 由于 `rem_bytes` 和 `block_limit` 为零,这些值不会被使用。
                            rem_data = undefined;
                            rem_data_elem = undefined;
                            rem_splat = undefined;
                        }
                    }
                    if (block_limit == .nothing) break;
                }
                try h.bit_writer.write(table.codes[256], table.bits[256]);
            } else while (true) {
                // 存储块

                // 写入不足一个完整向量元素的数据
                const in_pattern = rem_splat != splat;
                const vec_elem_i, const in_data =
                    @subWithOverflow(data.len - (rem_data.len - @intFromBool(in_pattern)), 1);
                const is_elem = in_data == 0 and data[vec_elem_i].len == rem_data_elem.len;

                if (!is_elem or rem_data_elem.len > @backingInt(block_limit)) {
                    block_limit = block_limit.subtract(rem_data_elem.len) orelse {
                        try h.bit_writer.output.writeAll(rem_data_elem[0..@backingInt(block_limit)]);
                        h.hasher.update(rem_data_elem[0..@backingInt(block_limit)]);
                        rem_data_elem = rem_data_elem[@backingInt(block_limit)..];
                        assert(rem_data_elem.len != 0);
                        break;
                    };
                    try h.bit_writer.output.writeAll(rem_data_elem);
                    h.hasher.update(rem_data_elem);
                } else {
                    // 将 `rem_data_elem` 放回 `rem_data`
                    if (!in_pattern) {
                        rem_data = data[vec_elem_i..];
                    } else {
                        rem_splat += 1;
                    }
                }
                rem_data_elem = undefined; // 它始终会在下方更新

                // 尽可能传递原始向量中的更多部分
                var vec_n: usize = 0;
                var vlimit = block_limit;
                const vec_splat = while (rem_data[vec_n..].len != 1) {
                    vlimit = vlimit.subtract(rem_data[vec_n].len) orelse break 1;
                    vec_n += 1;
                } else vec_splat: {
                    // 当 `pattern.len == 0` 时,`vec_splat` 的值无关紧要。
                    const vec_splat = @backingInt(vlimit) / @max(1, pattern.len);
                    if (pattern.len != 0) assert(vec_splat <= rem_splat + 1);
                    vlimit = vlimit.subtract(pattern.len * vec_splat).?;
                    vec_n += 1;
                    break :vec_splat vec_splat;
                };

                const n = if (vec_n != 0) n: {
                    assert(@backingInt(block_limit) - @backingInt(vlimit) ==
                        Writer.countSplat(rem_data[0..vec_n], vec_splat));
                    break :n try h.bit_writer.output.writeSplat(rem_data[0..vec_n], vec_splat);
                } else 0; // 仍进入下方分支,以推进向量。
                block_limit = block_limit.subtract(n).?;
                var consumed: Io.Limit = .limited(n);

                while (rem_data.len != 1) {
                    const elem = rem_data[0];
                    rem_data = rem_data[1..];
                    consumed = consumed.subtract(elem.len) orelse {
                        h.hasher.update(elem[0..@backingInt(consumed)]);
                        rem_data_elem = elem[@backingInt(consumed)..];
                        break;
                    };
                    h.hasher.update(elem);
                } else {
                    if (pattern.len == 0) {
                        // `data` 已全部消费。不过,下方的一般
                        // 情况处理会除以零,因而不适用于此。
                        assert(consumed == .nothing);
                        assert(block_limit == .nothing);
                        assert(rem_bytes == 0);
                        // 由于 `rem_bytes` 和 `block_limit` 为零,这些值不会被使用。
                        rem_splat = undefined;
                        rem_data = undefined;
                        rem_data_elem = undefined;
                        break;
                    }

                    const splatted = @backingInt(consumed) / pattern.len;
                    const partial = @backingInt(consumed) % pattern.len;
                    for (0..splatted) |_| h.hasher.update(pattern);
                    h.hasher.update(pattern[0..partial]);

                    const taken_splat = splatted + 1;
                    if (rem_splat >= taken_splat) {
                        rem_splat -= taken_splat;
                        rem_data_elem = pattern[partial..];
                    } else {
                        // 已消耗全部 `data`。
                        assert(partial == 0);
                        assert(block_limit == .nothing);
                        assert(rem_bytes == 0);
                        // 由于 `rem_bytes` 和 `block_limit` 为零,这些值不会被使用。
                        rem_data = undefined;
                        rem_data_elem = undefined;
                        rem_splat = undefined;
                    }
                }

                if (block_limit == .nothing) break;
            }
        }

        if (rem_bytes > data_bytes) {
            assert(rem_bytes - data_bytes == rem_data_elem.len);
            assert(&rem_data_elem[0] == &w.buffer[total_bytes - rem_bytes]);
        }
        return w.consume(total_bytes - rem_bytes);
    }

    fn flush(w: *Writer) Writer.Error!void {
        errdefer w.* = .failing;
        const h: *Huffman = @fieldParentPtr("writer", w);
        try Huffman.rebaseInner(w, 0, w.buffer.len, false);
        try h.bit_writer.byteAlignBlocks();
    }

    pub fn finish(h: *Huffman) Writer.Error!void {
        defer h.writer = .failing;
        try Huffman.rebaseInner(&h.writer, 0, h.writer.buffer.len, true);
        try h.bit_writer.output.rebase(0, 1);
        h.bit_writer.byteAlign();
        try h.hasher.writeFooter(h.bit_writer.output);
    }

    fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
        errdefer w.* = .failing;
        try Huffman.rebaseInner(w, preserve, capacity, false);
    }

    fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void {
        const h: *Huffman = @fieldParentPtr("writer", w);
        assert(preserve + capacity <= w.buffer.len);
        if (eos) assert(capacity == w.buffer.len);

        const preserved = @min(w.end, preserve);
        var remaining = w.buffer[0 .. w.end - preserved];
        while (remaining.len > max_tokens) { // 不使用 >=,以确保下方始终保留一个块
            const bytes = remaining[0..max_tokens];
            remaining = remaining[max_tokens..];
            try h.outputBytes(bytes, false);
        }

        // 空分组需要进行 eos 检查
        if (w.buffer.len - (remaining.len + preserved) < capacity or eos) {
            const bytes = remaining;
            remaining = &.{};
            try h.outputBytes(bytes, eos);
        }

        _ = w.consume(w.end - preserved - remaining.len);
    }

    fn outputBytes(h: *Huffman, bytes: []const u8, eos: bool) Writer.Error!void {
        comptime assert(max_tokens != 65535);
        assert(bytes.len <= max_tokens);
        var freqs: [257]u16 = @splat(0);
        freqs[256] = 1;
        for (bytes) |b| freqs[b] += 1;
        h.hasher.update(bytes);

        var codes_buf: CodesBuf = .init;
        if (try h.outputHeader(&freqs, &codes_buf, @intCast(bytes.len), eos)) |table| {
            for (bytes) |b| {
                try h.bit_writer.write(table.codes[b], table.bits[b]);
            }
            try h.bit_writer.write(table.codes[256], table.bits[256]);
        } else {
            try h.bit_writer.output.writeAll(bytes);
        }
    }

    const CodesBuf = struct {
        dyn_codes: [258]u16,
        dyn_bits: [258]u4,

        pub const init: CodesBuf = .{
            .dyn_codes = @as([257]u16, undefined) ++ .{0},
            .dyn_bits = @as([257]u4, @splat(0)) ++ .{1},
        };
    };

    /// 若块为存储块则返回 null。
    fn outputHeader(
        h: *Huffman,
        freqs: *const [257]u16,
        buf: *CodesBuf,
        bytes: u16,
        eos: bool,
    ) Writer.Error!?struct {
        codes: *const [257]u16,
        bits: *const [257]u4,
    } {
        assert(freqs[256] == 1);
        const dyn_codes_bitsize, _ = huffman.build(
            freqs,
            buf.dyn_codes[0..257],
            buf.dyn_bits[0..257],
            15,
            true,
        );

        var clen_values: [258]u8 = undefined;
        var clen_extra: [258]u8 = undefined;
        var clen_freqs: [19]u16 = @splat(0);
        const clen_len, const clen_extra_bitsize = buildClen(
            &buf.dyn_bits,
            &clen_values,
            &clen_extra,
            &clen_freqs,
        );

        var clen_codes: [19]u16 = undefined;
        var clen_bits: [19]u4 = @splat(0);
        const clen_codes_bitsize, _ = huffman.build(
            &clen_freqs,
            &clen_codes,
            &clen_bits,
            7,
            false,
        );
        const hclen = clenHlen(clen_freqs);

        const dynamic_bitsize = @as(u32, 14) +
            (4 + @as(u6, hclen)) * 3 + clen_codes_bitsize + clen_extra_bitsize +
            dyn_codes_bitsize;
        const fixed_bitsize = n: {
            const freq7 = 1; // 流结束
            var freq9: u16 = 0;
            for (freqs[144..256]) |f| freq9 += f;
            const freq8: u16 = bytes - freq9;
            break :n @as(u32, freq7) * 7 + @as(u32, freq8) * 8 + @as(u32, freq9) * 9;
        };
        const stored_bitsize = n: {
            const stored_align_bits = -%(h.bit_writer.buffered_n +% 3);
            break :n stored_align_bits + @as(u32, 32) + @as(u32, bytes) * 8;
        };

        if (stored_bitsize <= @min(dynamic_bitsize, fixed_bitsize)) {
            try h.bit_writer.write(BlockHeader.int(.{ .kind = .stored, .final = eos }), 3);
            try h.bit_writer.output.rebase(0, 5);
            h.bit_writer.byteAlign();
            h.bit_writer.output.writeInt(u16, bytes, .little) catch unreachable;
            h.bit_writer.output.writeInt(u16, ~bytes, .little) catch unreachable;
            return null;
        }

        if (fixed_bitsize <= dynamic_bitsize) {
            try h.bit_writer.write(BlockHeader.int(.{ .final = eos, .kind = .fixed }), 3);
            return .{
                .codes = token.fixed_lit_codes[0..257],
                .bits = token.fixed_lit_bits[0..257],
            };
        } else {
            try h.bit_writer.write(BlockHeader.Dynamic.int(.{
                .regular = .{ .final = eos, .kind = .dynamic },
                .hlit = 0,
                .hdist = 0,
                .hclen = hclen,
            }), 17);
            try h.bit_writer.writeClen(
                hclen,
                clen_values[0..clen_len],
                clen_extra[0..clen_len],
                clen_codes,
                clen_bits,
            );
            return .{ .codes = buf.dyn_codes[0..257], .bits = buf.dyn_bits[0..257] };
        }
    }
};

test Huffman {
    const fbufs = try testingFreqBufs();
    defer std.testing.allocator.destroy(fbufs);
    try std.testing.fuzz(fbufs, testFuzzedHuffmanInput, .{});
}

fn fuzzedHuffmanDrainSpaceLimit(max_drain: usize, written: usize, eos: bool) usize {
    var block_lim = math.divCeil(usize, max_drain, Huffman.max_tokens) catch unreachable;
    block_lim = @max(block_lim, @intFromBool(eos));
    const footer_overhead = @as(u8, 8) * @intFromBool(eos);
    // 原始块头为 6(块头可能跨两个字节)
    return written + 6 * block_lim + max_drain + footer_overhead;
}

/// 此函数源自 `testFuzzedRawInput`,为对 `Huffman` 进行模糊测试作了少量修改。
fn testFuzzedHuffmanInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void {
    @disableInstrumentation();
    const container = smith.value(flate.Container);
    var flate_buf: [2 * 65536]u8 = undefined;
    var flate_w: Writer = .fixed(&flate_buf);
    var expected_hash: flate.Container.Hasher = .init(container);
    var expected_size: u32 = 0;
    const max_size = 4 * @as(u32, Huffman.max_tokens);

    var h_buf: [2 * @as(usize, Huffman.max_tokens)]u8 = undefined;
    const h_buf_len = smith.valueWeighted(u32, &.{
        .value(u32, 0, @intCast(h_buf.len)), // 无缓冲
        .rangeAtMost(u32, 0, @intCast(h_buf.len), 1),
    });
    var h: Huffman = try .init(&flate_w, h_buf[0..h_buf_len], container);

    var vecs: [32][]const u8 = undefined;
    var vecs_n: usize = 0;

    while (true) {
        const Op = packed struct {
            drain: bool = false,
            add_vec: bool = false,
            rebase: enum(u2) { none, rebase, flush } = .none,

            pub const drain_only: @This() = .{ .drain = true };
            pub const add_vec_only: @This() = .{ .add_vec = true };
            pub const add_vec_and_drain: @This() = .{ .add_vec = true, .drain = true };
            pub const drain_and_rebase: @This() = .{ .drain = true, .rebase = .rebase };
            pub const drain_and_flush: @This() = .{ .drain = true, .rebase = .flush };
        };

        const is_eos = expected_size == max_size or smith.eosWeightedSimple(7, 1);
        var op: Op = if (!is_eos) smith.valueWeighted(Op, &.{
            .value(Op, .add_vec_only, 5),
            .value(Op, .add_vec_and_drain, 1),
            .value(Op, .drain_and_rebase, 1),
            .value(Op, .drain_and_flush, 1),
        }) else .drain_only;

        if (op.add_vec) {
            const max_write = max_size - expected_size;
            const buffered: u32 = @intCast(h.writer.buffered().len + countVec(vecs[0..vecs_n]));
            const to_align = Huffman.max_tokens - buffered % Huffman.max_tokens;
            assert(to_align != 0); // 否则没有帮助。

            const data_buf = &fbufs[
                smith.valueWeighted(u1, &.{
                    .value(FreqBufIndex, .gradient, 3),
                    .value(FreqBufIndex, .random, 1),
                })
            ];
            const data_buf_len: u32 = @intCast(data_buf.len);

            const max_data = @min(data_buf_len, max_write);
            const len = smith.valueWeighted(u32, &.{
                .rangeAtMost(u32, 0, max_data, 1),
                .rangeAtMost(u32, 0, @min(Huffman.max_tokens, max_data), 4),
                .value(u32, @min(to_align, max_data), max_data), // @min 的第二个参数是边界情况
            });
            const off = smith.valueRangeAtMost(u32, 0, data_buf_len - len);

            expected_size += len;
            vecs[vecs_n] = data_buf[off..][0..len];
            vecs_n += 1;
            op.drain |= vecs_n == vecs.len;
        }

        op.drain |= is_eos;
        op.drain &= vecs_n != 0;
        if (op.drain) {
            const pattern_len: u32 = @intCast(vecs[vecs_n - 1].len);
            const pattern_len_z = @max(pattern_len, 1);

            const max_write = max_size - (expected_size - pattern_len);
            const buffered: u32 = @intCast(h.writer.buffered().len + countVec(vecs[0 .. vecs_n - 1]));
            const to_align = Huffman.max_tokens - buffered % Huffman.max_tokens;
            assert(to_align != 0); // 否则没有帮助。

            const max_splat = max_write / pattern_len_z;
            const weights: [3]std.testing.Smith.Weight = .{
                .rangeAtMost(u32, 0, max_splat, 1),
                .rangeAtMost(u32, 0, @min(
                    Huffman.max_tokens + pattern_len_z,
                    max_write,
                ) / pattern_len_z, 4),
                .value(u32, to_align / pattern_len_z, max_splat * 4),
            };
            const align_weight = to_align % pattern_len_z == 0 and to_align <= max_write;
            const n_weights = @as(u8, 2) + @intFromBool(align_weight);
            const splat = smith.valueWeighted(u32, weights[0..n_weights]);

            expected_size = expected_size - pattern_len + pattern_len * splat; // splat 可以为零
            for (vecs[0 .. vecs_n - 1]) |v| expected_hash.update(v);
            for (0..splat) |_| expected_hash.update(vecs[vecs_n - 1]);

            const max_space = fuzzedHuffmanDrainSpaceLimit(
                buffered + pattern_len * splat,
                flate_w.buffered().len,
                false,
            );
            h.writer.writeSplatAll(vecs[0..vecs_n], splat) catch
                return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {};
            if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;

            vecs_n = 0;
        }

        if (op.rebase != .none) {
            const capacity = smith.valueRangeAtMost(u32, 0, h_buf_len);
            const preserve = smith.valueRangeAtMost(u32, 0, h_buf_len - capacity);

            const max_space = fuzzedHuffmanDrainSpaceLimit(
                h.writer.buffered().len,
                flate_w.buffered().len,
                false,
            ) + @as(usize, 8) * @intFromBool(op.rebase == .flush); // 字节对齐产生的开销
            switch (op.rebase) {
                .none => unreachable,
                .rebase => h.writer.rebase(preserve, capacity) catch
                    return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {},
                .flush => h.writer.flush() catch
                    return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {},
            }
            if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;
        }

        if (is_eos) break;
    }

    const max_space = fuzzedHuffmanDrainSpaceLimit(
        h.writer.buffered().len,
        flate_w.buffered().len,
        true,
    );
    h.finish() catch return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {};
    if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;

    try testingCheckDecompressedMatches(flate_w.buffered(), expected_size, expected_hash);
}