跳转到内容

std.compress.flate.Decompress

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

第 1 行

字段

input: *Reader
consumed_bits: u3
reader: Reader
container_metadata: Container.Metadata
lit_dec: LiteralDecoder
dst_dec: DistanceDecoder
final_block: bool
state: State
err: ?Error

std.compress.flate.Decompress.alignBitsForward

函数

第 577 行

fn alignBitsForward(d: *Decompress) void

参数

std.compress.flate.Decompress.assert

别名

第 2 行

别名目标 std.debug.assert

std.compress.flate.Decompress.BlockType

容器

第 27 行

字段

stored = 0
fixed = 1
dynamic = 2
invalid = 3

std.compress.flate.Decompress.CodegenDecoder

类型

第 642 行

std.compress.flate.Decompress.Container

别名

第 7 行

别名目标 std.compress.flate.Container

std.compress.flate.Decompress.decodeDistance

函数

第 197 行

fn decodeDistance(self: *Decompress, code_int: u5) !u16

参数

self: *Decompress
code_int: u5

std.compress.flate.Decompress.decodeLength

函数

第 189 行

fn decodeLength(self: *Decompress, code_int: u5) !u16

参数

self: *Decompress
code_int: u5

std.compress.flate.Decompress.decodeSymbol

函数

第 237 行

fn decodeSymbol(self: *Decompress, decoder: anytype) !u16

参数

self: *Decompress

std.compress.flate.Decompress.Decompress

别名

第 9 行

别名目标 std.compress.flate.Decompress

std.compress.flate.Decompress.direct_vtable

常量

第 67 行

Reader.VTable

std.compress.flate.Decompress.discardDirect

函数

第 121 行

可进一步改进:当丢弃的数据量包含 完整帧时,跳过该帧的解码。

fn discardDirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize

参数

r: *Reader
limit: std.Io.Limit

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.flate.Decompress.discardIndirect

函数

第 144 行

fn discardIndirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize

参数

r: *Reader
limit: std.Io.Limit

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.flate.Decompress.DistanceDecoder

类型

第 641 行

std.compress.flate.Decompress.dynamicCodeLength

函数

第 208 行

将码长符号解码为码长。从位置 pos 开始, 将解码长度写入 lens 切片。返回推进的位置数。

fn dynamicCodeLength(self: *Decompress, code: u16, lens: []u4, pos: usize) !usize

参数

self: *Decompress
code: u16
lens: []u4
pos: usize

std.compress.flate.Decompress.Error

错误集合

第 54 行

错误

BadGzipHeader Error
BadZlibHeader Error
EndOfStream
IncompleteHuffmanTree
InvalidBlockType
InvalidCode
InvalidDynamicBlockHeader
InvalidMatch
MissingEndOfBlockCode
OversubscribedHuffmanTree
ReadFailed
WrongGzipChecksum Error
WrongGzipSize Error
WrongStoredBlockNlen
WrongZlibChecksum Error

std.compress.flate.Decompress.flate

别名

第 3 行

别名目标 std.compress.flate

std.compress.flate.Decompress.HuffmanDecoder

类型函数

第 656 行

根据码长列表创建哈夫曼树编码,操作在 build 中完成。

随后 find 根据编码位查找符号。编码长度可以为 1 至 15 位。调用 find 时尚不知道查找符号 会消耗多少位。返回的符号包含 code_bits 字段, 用于确定在位流中应前进的位数。

使用查找表将 15 位整数映射到符号。同一符号会在表中 出现多次;32K 个位置最多对应 286 个符号。 小型查找表是用于加快查找的优化。 此算法是 zlib 所述算法的变体, 区别在于此处使用静态分配的数组。

fn HuffmanDecoder( comptime alphabet_size: u16, comptime max_code_bits: u4, comptime lookup_bits: u4, ) type

参数

alphabet_size: u16
max_code_bits: u4
lookup_bits: u4

字段

lookup: [1 << lookup_bits]Symbol = undefined
linked: if (lookup_bits == max_code_bits) void else [alphabet_size]struct {
    // sym.value 是 linked 中的下一个索引,当前索引会结束该链
    // 实际符号为此节点的索引
    sym: Symbol,
    code: u16,
} = undefined

std.compress.flate.Decompress.HuffmanDecoder.checkCompleteness

函数

第 742 行

给定码长列表,检查它是否表示 n 个符号的规范 霍夫曼码。

参考:https://github.com/madler/zlib/blob/5c42a230b7b468dff011f444161c0145b5efae59/contrib/puff/puff.c#L340

fn checkCompleteness(lens: []const u4) !void

参数

lens: []const u4

std.compress.flate.Decompress.HuffmanDecoder.find

函数

第 772 行

查找查找表编码对应的符号。

pub fn find(self: *Self, code: u16) !Symbol

参数

self: *Self
code: u16

std.compress.flate.Decompress.HuffmanDecoder.findLinked

函数

第 781 行

fn findLinked(self: *Self, code: u16, start: u16) !Symbol

参数

self: *Self
code: u16
start: u16

std.compress.flate.Decompress.HuffmanDecoder.generate

函数

第 683 行

根据每个符号的码长列表生成符号和查找表。

pub fn generate(self: *Self, lens: []const u4) !void

参数

self: *Self
lens: []const u4

std.compress.flate.Decompress.HuffmanDecoder.reverseIdx

函数

第 678 行

fn reverseIdx(idx: usize) u16

参数

idx: usize

std.compress.flate.Decompress.HuffmanDecoder.Self

别名

第 676 行

别名目标 std.compress.flate.Decompress.HuffmanDecoder

std.compress.flate.Decompress.indirect_vtable

常量

第 74 行

Reader.VTable

std.compress.flate.Decompress.init

函数

第 85 行

断言 input 缓冲区至少有 10 字节,或在此之前到达 EOF。

若提供 buffer,则断言容量至少为 flate.max_window_len。

pub fn init(input: *Reader, container: Container, buffer: []u8) Decompress

参数

input: *Reader
container: Container
buffer: []u8

std.compress.flate.Decompress.LiteralDecoder

类型

第 640 行

std.compress.flate.Decompress.peekBits

函数

第 546 行

fn peekBits(d: *Decompress, n: u4) !u16

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.peekBitsEnding

函数

第 555 行

fn peekBitsEnding(d: *Decompress, n: u4) !u16

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.peekBitsShort

函数

第 582 行

fn peekBitsShort(d: *Decompress, n: u4) !u16

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.peekBitsShortEnding

函数

第 591 行

fn peekBitsShortEnding(d: *Decompress, n: u4) !u16

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.peekIntBitsShort

函数

第 609 行

fn peekIntBitsShort(d: *Decompress, T: type) !T

参数

d: *Decompress
T: type

std.compress.flate.Decompress.Reader

别名

第 6 行

别名目标 std.Io.Reader

std.compress.flate.Decompress.readFixedCode

函数

第 625 行

先读取 7 位,然后可能再读取 1 或 2 位,以取得完整的 7、8 或 9 位编码。 参考:https://datatracker.ietf.org/doc/html/rfc1951#page-12 字面量值 位数 编码


0 - 143 8 00110000 至 10111111 144 - 255 9 110010000 至 111111111 256 - 279 7 0000000 至 0010111 280 - 287 8 11000000 至 11000111

fn readFixedCode(d: *Decompress) !u16

参数

std.compress.flate.Decompress.readVec

函数

第 164 行

fn readVec(r: *Reader, data: [][]u8) Reader.Error!usize

参数

r: *Reader
data: [][]u8

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.flate.Decompress.rebase

函数

第 109 行

fn rebase(r: *Reader, capacity: usize) void

参数

r: *Reader
capacity: usize

std.compress.flate.Decompress.rebaseFallible

函数

第 105 行

fn rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void

参数

r: *Reader
capacity: usize

错误

EndOfStream Error
ReadFailed Error

详细诊断参见 Reader 的实现。

std.compress.flate.Decompress.State

容器

第 34 行

字段

protocol_header
block_header
stored_block: u16
fixed_block
fixed_block_literal: u8
fixed_block_match: struct {
    distance: u16,
    length: u16,
}
dynamic_block
dynamic_block_literal: u8
dynamic_block_match: struct {
    distance: u16,
    length: u16,
}
protocol_footer
end

std.compress.flate.Decompress.std

别名

第 1 行

别名目标 std

std.compress.flate.Decompress.streamDirect

函数

第 244 行

fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize

参数

r: *Reader
w: *Writer
limit: std.Io.Limit

错误

EndOfStream

Reader 指示流结束。此错误不会从 Writer 产生。

ReadFailed

详细诊断参见 Reader 的实现。

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Decompress.streamFallible

函数

第 256 行

fn streamFallible(d: *Decompress, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize

参数

d: *Decompress
w: *Writer
limit: std.Io.Limit

错误

EndOfStream

Reader 指示流结束。此错误不会从 Writer 产生。

ReadFailed

详细诊断参见 Reader 的实现。

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Decompress.streamIndirect

函数

第 249 行

fn streamIndirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize

参数

r: *Reader
w: *Writer
limit: std.Io.Limit

错误

EndOfStream

Reader 指示流结束。此错误不会从 Writer 产生。

ReadFailed

详细诊断参见 Reader 的实现。

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.flate.Decompress.streamIndirectInner

函数

第 170 行

fn streamIndirectInner(d: *Decompress) Reader.Error!usize

参数

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.flate.Decompress.streamInner

函数

第 276 行

fn streamInner(d: *Decompress, w: *Writer, limit: std.Io.Limit) (Error || Reader.StreamError)!usize

参数

d: *Decompress
w: *Writer
limit: std.Io.Limit

std.compress.flate.Decompress.Symbol

容器

第 635 行

字段

value: u12 = 0
code_bits: u4 = 0

std.compress.flate.Decompress.takeBits

函数

第 571 行

fn takeBits(d: *Decompress, n: u4) !u16

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.takeIntBits

函数

第 605 行

fn takeIntBits(d: *Decompress, T: type) !T

参数

d: *Decompress
T: type

std.compress.flate.Decompress.testDecompress

函数

第 1193 行

fn testDecompress(container: Container, compressed: []const u8, expected_plain: []const u8) !void

参数

container: Container
compressed: []const u8
expected_plain: []const u8

std.compress.flate.Decompress.testFailure

函数

第 1183 行

fn testFailure(container: Container, in: []const u8, expected_err: anyerror) !void

参数

container: Container
in: []const u8
expected_err: anyerror

std.compress.flate.Decompress.testing

别名

第 4 行

别名目标 std.testing

std.compress.flate.Decompress.token

别名

第 10 行

别名目标 std.compress.flate.token

std.compress.flate.Decompress.tossBits

函数

第 566 行

仅在已使用大于或等于此 n 的值调用 peekBits 之后才安全。

fn tossBits(d: *Decompress, n: u4) void

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.tossBitsShort

函数

第 600 行

fn tossBitsShort(d: *Decompress, n: u4) !void

参数

d: *Decompress
n: u4

std.compress.flate.Decompress.writeMatch

函数

第 523 行

从当前写入位置向前 distance 处开始,写入 length 字节的匹配项,即对同一数据切片的反向引用。 为支持写入部分匹配,length 可小于最小匹配长度, 但必须大于零。

fn writeMatch(w: *Writer, length: u16, distance: u16) !void

参数

w: *Writer
length: u16
distance: u16

std.compress.flate.Decompress.Writer

别名

第 5 行

别名目标 std.Io.Writer

源码

std/compress/flate/Decompress.zig

const std = @import("../../std.zig");
const assert = std.debug.assert;
const flate = std.compress.flate;
const testing = std.testing;
const Writer = std.Io.Writer;
const Reader = std.Io.Reader;
const Container = flate.Container;

const Decompress = @This();
const token = @import("token.zig");

input: *Reader,
consumed_bits: u3,

reader: Reader,

container_metadata: Container.Metadata,

lit_dec: LiteralDecoder,
dst_dec: DistanceDecoder,

final_block: bool,
state: State,

err: ?Error,

const BlockType = enum(u2) {
    stored = 0,
    fixed = 1,
    dynamic = 2,
    invalid = 3,
};

const State = union(enum) {
    protocol_header,
    block_header,
    stored_block: u16,
    fixed_block,
    fixed_block_literal: u8,
    fixed_block_match: struct {
        distance: u16,
        length: u16,
    },
    dynamic_block,
    dynamic_block_literal: u8,
    dynamic_block_match: struct {
        distance: u16,
        length: u16,
    },
    protocol_footer,
    end,
};

pub const Error = Container.Error || error{
    InvalidCode,
    InvalidMatch,
    WrongStoredBlockNlen,
    InvalidBlockType,
    InvalidDynamicBlockHeader,
    ReadFailed,
    OversubscribedHuffmanTree,
    IncompleteHuffmanTree,
    MissingEndOfBlockCode,
    EndOfStream,
};

const direct_vtable: Reader.VTable = .{
    .stream = streamDirect,
    .rebase = rebaseFallible,
    .discard = discardDirect,
    .readVec = readVec,
};

const indirect_vtable: Reader.VTable = .{
    .stream = streamIndirect,
    .rebase = rebaseFallible,
    .discard = discardIndirect,
    .readVec = readVec,
};

/// 断言 `input` 缓冲区至少有 10 字节,或在此之前到达 EOF。
///
/// 若提供 `buffer`,则断言容量至少为 `flate.max_window_len`。
///
pub fn init(input: *Reader, container: Container, buffer: []u8) Decompress {
    if (buffer.len != 0) assert(buffer.len >= flate.max_window_len);
    return .{
        .reader = .{
            .vtable = if (buffer.len == 0) &direct_vtable else &indirect_vtable,
            .buffer = buffer,
            .seek = 0,
            .end = 0,
        },
        .input = input,
        .consumed_bits = 0,
        .container_metadata = .init(container),
        .lit_dec = .{},
        .dst_dec = .{},
        .final_block = false,
        .state = .protocol_header,
        .err = null,
    };
}

fn rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void {
    rebase(r, capacity);
}

fn rebase(r: *Reader, capacity: usize) void {
    assert(capacity <= r.buffer.len - flate.history_len);
    assert(r.end + capacity > r.buffer.len);
    const discard_n = @min(r.seek, r.end - flate.history_len);
    const keep = r.buffer[discard_n..r.end];
    @memmove(r.buffer[0..keep.len], keep);
    r.end = keep.len;
    r.seek -= discard_n;
}

/// 可进一步改进:当丢弃的数据量包含
/// 完整帧时,跳过该帧的解码。
fn discardDirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
    if (r.end + flate.history_len > r.buffer.len) rebase(r, flate.history_len);
    var writer: Writer = .{
        .vtable = &.{
            .drain = std.Io.Writer.Discarding.drain,
            .sendFile = std.Io.Writer.Discarding.sendFile,
        },
        .buffer = r.buffer,
        .end = r.end,
    };
    defer {
        assert(writer.end != 0);
        r.end = writer.end;
        r.seek = r.end;
    }
    const n = r.stream(&writer, limit) catch |err| switch (err) {
        error.WriteFailed => unreachable,
        error.ReadFailed, error.EndOfStream => |e| return e,
    };
    assert(n <= @backingInt(limit));
    return n;
}

fn discardIndirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    if (r.end + flate.history_len > r.buffer.len) rebase(r, flate.history_len);
    var writer: Writer = .{
        .buffer = r.buffer,
        .end = r.end,
        .vtable = &.{ .drain = Writer.unreachableDrain },
    };
    {
        defer r.end = writer.end;
        _ = streamFallible(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
            error.WriteFailed => unreachable,
            else => |e| return e,
        };
    }
    const n = limit.minInt(r.end - r.seek);
    r.seek += n;
    return n;
}

fn readVec(r: *Reader, data: [][]u8) Reader.Error!usize {
    _ = data;
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    return streamIndirectInner(d);
}

fn streamIndirectInner(d: *Decompress) Reader.Error!usize {
    const r = &d.reader;
    if (r.buffer.len - r.end < flate.history_len) rebase(r, flate.history_len);
    var writer: Writer = .{
        .buffer = r.buffer,
        .end = r.end,
        .vtable = &.{
            .drain = Writer.unreachableDrain,
            .rebase = Writer.unreachableRebase,
        },
    };
    defer r.end = writer.end;
    _ = streamFallible(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
        error.WriteFailed => unreachable,
        else => |e| return e,
    };
    return 0;
}

fn decodeLength(self: *Decompress, code_int: u5) !u16 {
    if (code_int > 28) return error.InvalidCode;
    const l: token.LenCode = .fromInt(code_int);
    const base = l.base();
    const extra = l.extraBits();
    return token.min_length + (base | try self.takeBits(extra));
}

fn decodeDistance(self: *Decompress, code_int: u5) !u16 {
    if (code_int > 29) return error.InvalidCode;
    const d: token.DistCode = .fromInt(code_int);
    const base = d.base();
    const extra = d.extraBits();
    return token.min_distance + (base | try self.takeBits(extra));
}

/// 将码长符号解码为码长。从位置 pos 开始,
/// 将解码长度写入 lens 切片。返回推进的位置数。
///
fn dynamicCodeLength(self: *Decompress, code: u16, lens: []u4, pos: usize) !usize {
    if (pos >= lens.len)
        return error.InvalidDynamicBlockHeader;

    switch (code) {
        0...15 => {
            // 表示长度为 0 到 15 的码长
            lens[pos] = @intCast(code);
            return 1;
        },
        16 => {
            // 复制前一个码长 3–6 次。
            // 接下来的 2 位表示重复长度
            const n: u8 = @as(u8, try self.takeIntBits(u2)) + 3;
            if (pos == 0 or pos + n > lens.len)
                return error.InvalidDynamicBlockHeader;
            for (0..n) |i| {
                lens[pos + i] = lens[pos + i - 1];
            }
            return n;
        },
        // 将值为 0 的码长重复 3 至 10 次。(长度占 3 位)
        17 => return @as(u8, try self.takeIntBits(u3)) + 3,
        // 将值为 0 的码长重复 11 至 138 次(长度占 7 位)
        18 => return @as(u8, try self.takeIntBits(u7)) + 11,
        else => return error.InvalidDynamicBlockHeader,
    }
}

fn decodeSymbol(self: *Decompress, decoder: anytype) !u16 {
    // 最大编码长度为 15 位。
    const sym = try decoder.find(try self.peekIntBitsShort(u15));
    try self.tossBitsShort(sym.code_bits);
    return sym.value;
}

fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    return streamFallible(d, w, limit);
}

fn streamIndirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    _ = limit;
    _ = w;
    return streamIndirectInner(d);
}

fn streamFallible(d: *Decompress, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    return streamInner(d, w, limit) catch |err| switch (err) {
        error.EndOfStream => {
            if (d.state == .end) {
                return error.EndOfStream;
            } else {
                d.err = error.EndOfStream;
                return error.ReadFailed;
            }
        },
        error.WriteFailed => |e| return e,
        else => |e| {
            // 出错时保持状态不变,以便
            // 更好地用于诊断失败。
            d.err = e;
            return error.ReadFailed;
        },
    };
}

fn streamInner(d: *Decompress, w: *Writer, limit: std.Io.Limit) (Error || Reader.StreamError)!usize {
    var remaining = @backingInt(limit);
    const in = d.input;
    sw: switch (d.state) {
        .protocol_header => switch (d.container_metadata.container()) {
            .gzip => {
                const Header = extern struct {
                    magic: u16 align(1),
                    method: u8,
                    flags: packed struct(u8) {
                        text: bool,
                        hcrc: bool,
                        extra: bool,
                        name: bool,
                        comment: bool,
                        reserved: u3,
                    },
                    mtime: u32 align(1),
                    xfl: u8,
                    os: u8,
                };
                const header = try in.takeStruct(Header, .little);
                if (header.magic != 0x8b1f or header.method != 0x08)
                    return error.BadGzipHeader;
                if (header.flags.extra) {
                    const extra_len = try in.takeInt(u16, .little);
                    try in.discardAll(extra_len);
                }
                if (header.flags.name) {
                    _ = try in.discardDelimiterInclusive(0);
                }
                if (header.flags.comment) {
                    _ = try in.discardDelimiterInclusive(0);
                }
                if (header.flags.hcrc) {
                    try in.discardAll(2);
                }
                continue :sw .block_header;
            },
            .zlib => {
                const header = try in.takeArray(2);
                const cmf: packed struct(u8) { cm: u4, cinfo: u4 } = @bitCast(header[0]);
                if (cmf.cm != 8 or cmf.cinfo > 7) return error.BadZlibHeader;
                continue :sw .block_header;
            },
            .raw => continue :sw .block_header,
        },
        .block_header => {
            d.final_block = (try d.takeIntBits(u1)) != 0;
            const block_type: BlockType = @fromBackingInt(@intCast(try d.takeIntBits(u2)));
            switch (block_type) {
                .stored => {
                    d.alignBitsForward();
                    // 存储块中此位置之后的所有内容均按字节对齐
                    const len = try in.takeInt(u16, .little);
                    const nlen = try in.takeInt(u16, .little);
                    if (len != ~nlen) return error.WrongStoredBlockNlen;
                    continue :sw .{ .stored_block = len };
                },
                .fixed => continue :sw .fixed_block,
                .dynamic => {
                    const hlit: u16 = @as(u16, try d.takeIntBits(u5)) + 257; // 存在的 ll 编码条目数 - 257
                    const hdist: u16 = @as(u16, try d.takeIntBits(u5)) + 1; // 距离码条目数减一
                    const hclen: u8 = @as(u8, try d.takeIntBits(u4)) + 4; // 编码 hclen + 4 个代码长度

                    if (hlit > 286 or hdist > 30)
                        return error.InvalidDynamicBlockHeader;

                    // 代码长度的长度
                    var cl_lens: [19]u4 = @splat(0);
                    for (token.codegen_order[0..hclen]) |i| {
                        cl_lens[i] = try d.takeIntBits(u3);
                    }
                    var cl_dec: CodegenDecoder = .{};
                    try cl_dec.generate(&cl_lens);

                    // 已解码的代码长度
                    var dec_lens: [286 + 30]u4 = @splat(0);
                    var pos: usize = 0;
                    while (pos < hlit + hdist) {
                        const peeked = try d.peekIntBitsShort(u7);
                        const sym = try cl_dec.find(peeked);
                        try d.tossBitsShort(sym.code_bits);
                        pos += try d.dynamicCodeLength(sym.value, &dec_lens, pos);
                    }
                    if (pos > hlit + hdist) {
                        return error.InvalidDynamicBlockHeader;
                    }

                    // 向字面量解码器提供字面量码长
                    try d.lit_dec.generate(dec_lens[0..hlit]);

                    // 提供给距离解码器的距离编码长度
                    try d.dst_dec.generate(dec_lens[hlit..][0..hdist]);

                    continue :sw .dynamic_block;
                },
                .invalid => return error.InvalidBlockType,
            }
        },
        .stored_block => |remaining_len| {
            const out: []u8 = if (remaining != 0)
                try w.writableSliceGreedyPreserve(flate.history_len, 1)
            else
                &.{};
            var limited_out: [1][]u8 = .{limit.min(.limited(remaining_len)).slice(out)};
            const n = try in.readVec(&limited_out);
            if (remaining_len - n == 0) {
                d.state = if (d.final_block) .protocol_footer else .block_header;
            } else {
                d.state = .{ .stored_block = @intCast(remaining_len - n) };
            }
            w.advance(n);
            return @backingInt(limit) - remaining + n;
        },
        .fixed_block => while (true) {
            // 消耗字节
            const sym = try d.readFixedCode();

            if (sym >= 256) {
                @branchHint(.unlikely);

                if (sym == 256) {
                    @branchHint(.unlikely);
                    // 结束
                    d.state = if (d.final_block) .protocol_footer else .block_header;
                    continue :sw d.state;
                }

                // 匹配
                const length = try d.decodeLength(@intCast(sym - 257));
                const distance = try d.decodeDistance(@bitReverse(try d.takeIntBits(u5)));
                continue :sw .{ .fixed_block_match = .{ .length = length, .distance = distance } };
            }

            const byte: u8 = @intCast(sym);
            if (remaining != 0) {
                @branchHint(.likely);
                remaining -= 1;
                try w.writeBytePreserve(flate.history_len, byte);
            } else {
                d.state = .{ .fixed_block_literal = byte };
                return @backingInt(limit) - remaining;
            }
        },
        .fixed_block_literal => |symbol| {
            assert(remaining != 0);
            remaining -= 1;
            try w.writeBytePreserve(flate.history_len, symbol);
            continue :sw .fixed_block;
        },
        .fixed_block_match => |match| {
            if (remaining >= match.length) {
                @branchHint(.likely);
                try writeMatch(w, match.length, match.distance);
                remaining -= match.length;
                continue :sw .fixed_block;
            } else {
                if (remaining > 0) {
                    try writeMatch(w, @intCast(remaining), match.distance);
                }
                d.state = .{ .fixed_block_match = .{
                    .distance = match.distance,
                    .length = match.length - @as(u16, @intCast(remaining)),
                } };
                return @backingInt(limit);
            }
        },
        // 较大的归档中,多数块通常是动态块,因此
        // 解压性能取决于这段逻辑。
        .dynamic_block => while (true) {
            // 消耗字节
            const sym = try d.decodeSymbol(&d.lit_dec);

            if (sym >= 256) {
                @branchHint(.unlikely);

                if (sym == 256) {
                    @branchHint(.unlikely);
                    // 结束
                    d.state = if (d.final_block) .protocol_footer else .block_header;
                    continue :sw d.state;
                }

                // 匹配
                const length = try d.decodeLength(@intCast(sym - 257));
                const dsm = try d.decodeSymbol(&d.dst_dec);
                const distance = try d.decodeDistance(@intCast(dsm));
                continue :sw .{ .dynamic_block_match = .{ .length = length, .distance = distance } };
            }

            const byte: u8 = @intCast(sym);
            if (remaining != 0) {
                @branchHint(.likely);
                remaining -= 1;
                try w.writeBytePreserve(flate.history_len, byte);
            } else {
                d.state = .{ .dynamic_block_literal = byte };
                return @backingInt(limit) - remaining;
            }
        },
        .dynamic_block_literal => |symbol| {
            assert(remaining != 0);
            remaining -= 1;
            try w.writeBytePreserve(flate.history_len, symbol);
            continue :sw .dynamic_block;
        },
        .dynamic_block_match => |match| {
            if (remaining >= match.length) {
                @branchHint(.likely);
                remaining -= match.length;
                try writeMatch(w, match.length, match.distance);
                continue :sw .dynamic_block;
            } else {
                if (remaining > 0) {
                    try writeMatch(w, @intCast(remaining), match.distance);
                }
                d.state = .{ .dynamic_block_match = .{
                    .distance = match.distance,
                    .length = match.length - @as(u16, @intCast(remaining)),
                } };
                return @backingInt(limit);
            }
        },
        .protocol_footer => {
            d.alignBitsForward();
            switch (d.container_metadata) {
                .gzip => |*gzip| {
                    gzip.crc = try in.takeInt(u32, .little);
                    gzip.count = try in.takeInt(u32, .little);
                },
                .zlib => |*zlib| {
                    zlib.adler = try in.takeInt(u32, .big);
                },
                .raw => {},
            }
            d.state = .end;
            return @backingInt(limit) - remaining;
        },
        .end => return error.EndOfStream,
    }
}

/// 从当前写入位置向前 `distance` 处开始,写入
/// `length` 字节的匹配项,即对同一数据切片的反向引用。
/// 为支持写入部分匹配,`length` 可小于最小匹配长度,
/// 但必须大于零。
fn writeMatch(w: *Writer, length: u16, distance: u16) !void {
    if (w.end < distance) return error.InvalidMatch;
    assert(length > 0);
    assert(length <= token.max_length);
    assert(distance >= token.min_distance);
    assert(distance <= token.max_distance);

    // 这不是 @memmove;这里有意重复
    // 逐字节迭代产生的模式。
    const dest = try w.writableSlicePreserve(flate.history_len, length);
    const end = dest.ptr - w.buffer.ptr;
    const src = w.buffer[end - distance ..][0..length];
    if (distance >= length) {
        @memcpy(dest, src);
    } else if (distance == 1) {
        // 重复复制单个字节
        @memset(dest, src[0]);
    } else {
        // 重复复制多个字节
        for (dest, src) |*d, s| d.* = s;
    }
}

fn peekBits(d: *Decompress, n: u4) !u16 {
    const bits = d.input.peekInt(u32, .little) catch |e| return switch (e) {
        error.ReadFailed => error.ReadFailed,
        error.EndOfStream => d.peekBitsEnding(n),
    };
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

fn peekBitsEnding(d: *Decompress, n: u4) !u16 {
    @branchHint(.unlikely);

    const left = d.input.buffered();
    if (left.len * 8 - d.consumed_bits < n) return error.EndOfStream;
    const bits = std.mem.readVarInt(u32, left, .little);
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

/// 仅在已使用大于或等于此 `n` 的值调用 `peekBits` 之后才安全。
fn tossBits(d: *Decompress, n: u4) void {
    d.input.toss((@as(u8, n) + d.consumed_bits) / 8);
    d.consumed_bits +%= @truncate(n);
}

fn takeBits(d: *Decompress, n: u4) !u16 {
    const bits = try d.peekBits(n);
    d.tossBits(n);
    return bits;
}

fn alignBitsForward(d: *Decompress) void {
    d.input.toss(@intFromBool(d.consumed_bits != 0));
    d.consumed_bits = 0;
}

fn peekBitsShort(d: *Decompress, n: u4) !u16 {
    const bits = d.input.peekInt(u32, .little) catch |e| return switch (e) {
        error.ReadFailed => error.ReadFailed,
        error.EndOfStream => d.peekBitsShortEnding(n),
    };
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

fn peekBitsShortEnding(d: *Decompress, n: u4) !u16 {
    @branchHint(.unlikely);

    const left = d.input.buffered();
    const bits = std.mem.readVarInt(u32, left, .little);
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

fn tossBitsShort(d: *Decompress, n: u4) !void {
    if (d.input.bufferedLen() * 8 - d.consumed_bits < n) return error.EndOfStream;
    d.tossBits(n);
}

fn takeIntBits(d: *Decompress, T: type) !T {
    return @intCast(try d.takeBits(@bitSizeOf(T)));
}

fn peekIntBitsShort(d: *Decompress, T: type) !T {
    return @intCast(try d.peekBitsShort(@bitSizeOf(T)));
}

/// 先读取 7 位,然后可能再读取 1 或 2 位,以取得完整的 7、8 或 9 位编码。
/// 参考:https://datatracker.ietf.org/doc/html/rfc1951#page-12
///         字面量值       位数        编码
///          ---------    ----        -----
///            0 - 143     8          00110000 至
///                                   10111111
///          144 - 255     9          110010000 至
///                                   111111111
///          256 - 279     7          0000000 至
///                                   0010111
///          280 - 287     8          11000000 至
///                                   11000111
fn readFixedCode(d: *Decompress) !u16 {
    const code7 = @bitReverse(try d.takeIntBits(u7));
    return switch (code7) {
        0...0b0010_111 => @as(u16, code7) + 256,
        0b0010_111 + 1...0b1011_111 => (@as(u16, code7) << 1) + @as(u16, try d.takeIntBits(u1)) - 0b0011_0000,
        0b1011_111 + 1...0b1100_011 => (@as(u16, code7 - 0b1100000) << 1) + try d.takeIntBits(u1) + 280,
        else => (@as(u16, code7 - 0b1100_100) << 2) + @as(u16, @bitReverse(try d.takeIntBits(u2))) + 144,
    };
}

pub const Symbol = packed struct(u16) {
    value: u12 = 0,
    code_bits: u4 = 0, // 编码 0–15 中的位数
};

pub const LiteralDecoder = HuffmanDecoder(286, 15, 9);
pub const DistanceDecoder = HuffmanDecoder(30, 15, 9);
pub const CodegenDecoder = HuffmanDecoder(19, 7, 7);

/// 根据码长列表创建哈夫曼树编码,操作在 `build` 中完成。
///
/// 随后 `find` 根据编码位查找符号。编码长度可以为 1 至
/// 15 位。调用 `find` 时尚不知道查找符号
/// 会消耗多少位。返回的符号包含 code_bits 字段,
/// 用于确定在位流中应前进的位数。
///
/// 使用查找表将 15 位整数映射到符号。同一符号会在表中
/// 出现多次;32K 个位置最多对应 286 个符号。
/// 小型查找表是用于加快查找的优化。
/// 此算法是 [zlib](https://github.com/madler/zlib/blob/643e17b7498d12ab8d15565662880579692f769d/doc/algorithm.txt#L92) 所述算法的变体,
/// 区别在于此处使用静态分配的数组。
fn HuffmanDecoder(
    comptime alphabet_size: u16,
    comptime max_code_bits: u4,
    comptime lookup_bits: u4,
) type {
    const lookup_shift = max_code_bits - lookup_bits;
    const lookup_mask = (1 << lookup_bits) - 1;

    return struct {
        // 查找表 code -> symbol。
        // 对于 code_bits == 0 的值,symbol 为 linked 中第一个节点的索引。
        // 若首节点索引为 0xfff,则为无效编码。
        lookup: [1 << lookup_bits]Symbol = undefined,
        linked: if (lookup_bits == max_code_bits) void else [alphabet_size]struct {
            // sym.value 是 linked 中的下一个索引,当前索引会结束该链
            // 实际符号为此节点的索引
            sym: Symbol,
            code: u16,
        } = undefined,

        const Self = @This();

        fn reverseIdx(idx: usize) u16 {
            return @bitReverse(@as(@Int(.unsigned, lookup_bits), @intCast(idx)));
        }

        /// 根据每个符号的码长列表生成符号和查找表。
        pub fn generate(self: *Self, lens: []const u4) !void {
            try checkCompleteness(lens);

            var buckets: [1 + @as(usize, max_code_bits)][alphabet_size]Symbol = undefined;
            var bucket_len: [buckets.len]u16 = @splat(0);
            for (0.., lens) |symbol, bits| {
                buckets[bits][bucket_len[bits]] = .{
                    .value = @intCast(symbol),
                    .code_bits = bits,
                };
                bucket_len[bits] += 1;
            }

            var code: u16 = 0;
            var idx: u16 = 0;
            for (1..lookup_bits + 1) |bits| {
                const inc = @as(u16, 1) << @intCast(max_code_bits - bits);
                for (buckets[bits][0..bucket_len[bits]]) |lookup_sym| {
                    const next_code = code + inc;
                    const next_idx = next_code >> lookup_shift;
                    for (idx..next_idx) |i| {
                        self.lookup[reverseIdx(i)] = lookup_sym;
                    }
                    code = next_code;
                    idx = next_idx;
                }
            }
            for (lookup_bits + 1..buckets.len) |bits| {
                const inc = @as(u16, 1) << @intCast(max_code_bits - bits);
                for (buckets[bits][0..bucket_len[bits]]) |linked_sym| {
                    const next_code = code + inc;
                    const next_idx = next_code >> lookup_shift;

                    const ri = reverseIdx(idx);
                    const next: Symbol = .{
                        .value = self.lookup[ri].value,
                        .code_bits = linked_sym.code_bits,
                    };
                    self.linked[linked_sym.value] = .{
                        .sym = next,
                        .code = @bitReverse(@as(@Int(.unsigned, max_code_bits), @intCast(code))),
                    };
                    self.lookup[ri] = .{ .value = linked_sym.value, .code_bits = 0 };

                    code = next_code;
                    idx = next_idx;
                }
            }

            // 无效编码
            for (idx..self.lookup.len) |i| {
                self.lookup[reverseIdx(i)] = .{ .value = 0xfff, .code_bits = 0 };
            }
        }

        /// 给定码长列表,检查它是否表示 n 个符号的规范
        /// 霍夫曼码。
        ///
        /// 参考:https://github.com/madler/zlib/blob/5c42a230b7b468dff011f444161c0145b5efae59/contrib/puff/puff.c#L340
        fn checkCompleteness(lens: []const u4) !void {
            if (alphabet_size == 286)
                if (lens[256] == 0) return error.MissingEndOfBlockCode;

            var count: [@as(usize, max_code_bits) + 1]u16 = @splat(0);
            var max: usize = 0;
            for (lens) |n| {
                if (n == 0) continue;
                if (n > max) max = n;
                count[n] += 1;
            }
            if (max == 0) // 空树
                return;

            // 检查码长集合是否过度分配或不完整。
            var left: usize = 1; // 一种可能的零长度编码
            for (1..count.len) |len| {
                left <<= 1; // 再增加一位,剩余编码数翻倍
                if (count[len] > left)
                    return error.OversubscribedHuffmanTree;
                left -= count[len]; // 从可能的代码中扣除计数
            }
            if (left > 0) { // left > 0 表示不完整
                // 仅当只有一个长度为 1 的代码时才允许代码不完整
                if (max_code_bits > 7 and max == count[0] + count[1]) return;
                return error.IncompleteHuffmanTree;
            }
        }

        /// 查找查找表编码对应的符号。
        pub fn find(self: *Self, code: u16) !Symbol {
            // 尝试在查找表中查找
            const idx = code & lookup_mask;
            const sym = self.lookup[idx];
            if (sym.code_bits != 0) return sym;
            // 否则使用具有相同前缀的符号链表
            return self.findLinked(code, sym.value);
        }

        fn findLinked(self: *Self, code: u16, start: u16) !Symbol {
            if (start == 0xfff) return error.InvalidCode;
            if (lookup_bits == max_code_bits) unreachable;
            var pos = start;
            while (true) {
                const node = self.linked[pos];
                const shift = -%node.sym.code_bits;
                // 比较最高的 code_bits 个位
                if ((code ^ node.code) << shift == 0)
                    return .{ .value = @intCast(pos), .code_bits = node.sym.code_bits };
                pos = node.sym.value;
            }
        }
    };
}

test "init/find" {
    // 示例数据来自:https://youtu.be/SJPvNi4HrWQ?t=8423
    const code_lens = [_]u4{ 4, 3, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 3, 2 };
    var h: CodegenDecoder = .{};
    try h.generate(&code_lens);

    // 每个符号所有可能的码。
    // 查找表具有 126 个元素,覆盖所有可能的 7 位码。
    for (0b0000_000..0b0100_000) |c| // 0..32 (32)
        try testing.expectEqual(
            Symbol{ .value = 3, .code_bits = 2 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b0100_000..0b1000_000) |c| // 32..64 (32)
        try testing.expectEqual(
            Symbol{ .value = 18, .code_bits = 2 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1000_000..0b1010_000) |c| // 64..80 (16)
        try testing.expectEqual(
            Symbol{ .value = 1, .code_bits = 3 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1010_000..0b1100_000) |c| // 80..96 (16)
        try testing.expectEqual(
            Symbol{ .value = 4, .code_bits = 3 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1100_000..0b1110_000) |c| // 96..112 (16)
        try testing.expectEqual(
            Symbol{ .value = 17, .code_bits = 3 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1110_000..0b1111_000) |c| // 112..120 (8)
        try testing.expectEqual(
            Symbol{ .value = 0, .code_bits = 4 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1111_000..0b1_0000_000) |c| // 120...128 (8)
        try testing.expectEqual(
            Symbol{ .value = 16, .code_bits = 4 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );
}

test "encode/decode literals" {
    // 检查 RFC 1951 第 3.2.2 节的示例能否运行(再添加若干零)
    const max_bits = 5;
    var decoder: HuffmanDecoder(16, max_bits, 3) = .{};
    try decoder.generate(&.{ 3, 3, 3, 3, 0, 0, 3, 2, 4, 4 });

    inline for (0.., .{
        @as(u3, 0b010),
        @as(u3, 0b011),
        @as(u3, 0b100),
        @as(u3, 0b101),
        @as(u0, 0),
        @as(u0, 0),
        @as(u3, 0b110),
        @as(u2, 0b00),
        @as(u4, 0b1110),
        @as(u4, 0b1111),
    }) |i, code| {
        const bits = @bitSizeOf(@TypeOf(code));
        if (bits == 0) continue;
        for (0..1 << (max_bits - bits)) |extra| {
            const full = (@as(u16, code) << (max_bits - bits)) | @as(u16, @intCast(extra));
            const symbol = try decoder.find(@bitReverse(@as(u5, @intCast(full))));
            try testing.expectEqual(i, symbol.value);
            try testing.expectEqual(bits, symbol.code_bits);
        }
    }
}

test "non compressed block (type 0)" {
    try testDecompress(.raw, &[_]u8{
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate 固定缓冲区头部的 len、nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // 未压缩数据
    }, "Hello world\n");
}

test "fixed code block (type 1)" {
    try testDecompress(.raw, &[_]u8{
        0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate 数据块类型 1
        0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
    }, "Hello world\n");
}

test "dynamic block (type 2)" {
    try testDecompress(.raw, &[_]u8{
        0x3d, 0xc6, 0x39, 0x11, 0x00, 0x00, 0x0c, 0x02, // deflate 数据块类型 2
        0x30, 0x2b, 0xb5, 0x52, 0x1e, 0xff, 0x96, 0x38,
        0x16, 0x96, 0x5c, 0x1e, 0x94, 0xcb, 0x6d, 0x01,
    }, "ABCDEABCD ABCDEABCD");
}

test "gzip non compressed block (type 0)" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, // gzip 头部(10 字节)
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate 固定缓冲区头部的 len、nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // 未压缩数据
        0xd5, 0xe0, 0x39, 0xb7, // gzip 尾部:校验和
        0x0c, 0x00, 0x00, 0x00, // gzip 尾部:大小
    }, "Hello world\n");
}

test "gzip fixed code block (type 1)" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x03, // gzip 头部(10 字节)
        0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate 数据块类型 1
        0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
        0xd5, 0xe0, 0x39, 0xb7, 0x0c, 0x00, 0x00, 0x00, // gzip 尾部(校验和、长度)
    }, "Hello world\n");
}

test "gzip dynamic block (type 2)" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, // gzip 头部(10 字节)
        0x3d, 0xc6, 0x39, 0x11, 0x00, 0x00, 0x0c, 0x02, // deflate 数据块类型 2
        0x30, 0x2b, 0xb5, 0x52, 0x1e, 0xff, 0x96, 0x38,
        0x16, 0x96, 0x5c, 0x1e, 0x94, 0xcb, 0x6d, 0x01,
        0x17, 0x1c, 0x39, 0xb4, 0x13, 0x00, 0x00, 0x00, // gzip 尾部(校验和、长度)
    }, "ABCDEABCD ABCDEABCD");
}

test "gzip header with name" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x08, 0xe5, 0x70, 0xb1, 0x65, 0x00, 0x03, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x2e,
        0x74, 0x78, 0x74, 0x00, 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, 0x2f, 0xca, 0x49, 0xe1,
        0x02, 0x00, 0xd5, 0xe0, 0x39, 0xb7, 0x0c, 0x00, 0x00, 0x00,
    }, "Hello world\n");
}

test "zlib decompress non compressed block (type 0)" {
    try testDecompress(.zlib, &[_]u8{
        0x78, 0b10_0_11100, // zlib 头部(2 字节)
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate 固定缓冲区头部的 len、nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // 未压缩数据
        0x1c, 0xf2, 0x04, 0x47, // zlib 尾部:校验和
    }, "Hello world\n");
}

test "failing end-of-stream" {
    try testFailure(.raw, @embedFile("testdata/fuzz/end-of-stream.input"), error.EndOfStream);
}
test "failing invalid-distance" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-distance.input"), error.InvalidMatch);
}
test "failing invalid-tree01" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree01.input"), error.IncompleteHuffmanTree);
}
test "failing invalid-tree02" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree02.input"), error.IncompleteHuffmanTree);
}
test "failing invalid-tree03" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree03.input"), error.IncompleteHuffmanTree);
}
test "failing lengths-overflow" {
    try testFailure(.raw, @embedFile("testdata/fuzz/lengths-overflow.input"), error.InvalidDynamicBlockHeader);
}
test "failing out-of-codes" {
    try testFailure(.raw, @embedFile("testdata/fuzz/out-of-codes.input"), error.InvalidCode);
}
test "failing puff01" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff01.input"), error.WrongStoredBlockNlen);
}
test "failing puff02" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff02.input"), error.EndOfStream);
}
test "failing puff04" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff04.input"), error.InvalidCode);
}
test "failing puff05" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff05.input"), error.EndOfStream);
}
test "failing puff06" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff06.input"), error.EndOfStream);
}
test "failing puff08" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff08.input"), error.InvalidCode);
}
test "failing puff10" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff10.input"), error.InvalidCode);
}
test "failing puff11" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff11.input"), error.InvalidMatch);
}
test "failing puff12" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff12.input"), error.InvalidDynamicBlockHeader);
}
test "failing puff13" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff13.input"), error.IncompleteHuffmanTree);
}
test "failing puff14" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff14.input"), error.EndOfStream);
}
test "failing puff15" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff15.input"), error.IncompleteHuffmanTree);
}
test "failing puff16" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff16.input"), error.InvalidDynamicBlockHeader);
}
test "failing puff17" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff17.input"), error.MissingEndOfBlockCode);
}
test "failing fuzz1" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz1.input"), error.InvalidDynamicBlockHeader);
}
test "failing fuzz2" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz2.input"), error.InvalidDynamicBlockHeader);
}
test "failing fuzz3" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz3.input"), error.InvalidMatch);
}
test "failing fuzz4" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz4.input"), error.OversubscribedHuffmanTree);
}
test "failing puff18" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff18.input"), error.OversubscribedHuffmanTree);
}
test "failing puff19" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff19.input"), error.OversubscribedHuffmanTree);
}
test "failing puff20" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff20.input"), error.OversubscribedHuffmanTree);
}
test "failing puff21" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff21.input"), error.OversubscribedHuffmanTree);
}
test "failing puff22" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff22.input"), error.OversubscribedHuffmanTree);
}
test "failing puff23" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff23.input"), error.OversubscribedHuffmanTree);
}
test "failing puff24" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff24.input"), error.IncompleteHuffmanTree);
}
test "failing puff25" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff25.input"), error.OversubscribedHuffmanTree);
}
test "failing puff26" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff26.input"), error.InvalidDynamicBlockHeader);
}
test "failing puff27" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff27.input"), error.InvalidDynamicBlockHeader);
}

test "deflate-stream" {
    try testDecompress(
        .raw,
        @embedFile("testdata/fuzz/deflate-stream.input"),
        @embedFile("testdata/fuzz/deflate-stream.expect"),
    );
}

test "empty-distance-alphabet01" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/empty-distance-alphabet01.input"), "");
}

test "empty-distance-alphabet02" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/empty-distance-alphabet02.input"), "");
}

test "puff03" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/puff03.input"), &.{0xa});
}

test "puff09" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/puff09.input"), "P");
}

test "invalid block type" {
    try testFailure(.raw, &[_]u8{0b110}, error.InvalidBlockType);
}

test "bug 18966" {
    try testDecompress(
        .gzip,
        @embedFile("testdata/fuzz/bug_18966.input"),
        @embedFile("testdata/fuzz/bug_18966.expect"),
    );
}

test "truncated input ending when reading dynamic length bits" {
    try testFailure(.raw, &[_]u8{
        0x15, 0xd5, 0x07, 0x3b, 0x16, 0x0c, 0x03, 0x86,
        0x61, 0x2b, 0xa3, 0xec, 0xec, 0x15, 0x95, 0x6c,
        0x92, 0x4d, 0x19, 0x95, 0x4a, 0xb6, 0x22, 0x23,
        0xc9,
    }, error.EndOfStream);
}

test "reading into empty buffer" {
    // 灵感来自 https://github.com/ziglang/zig/issues/19895
    const input = &[_]u8{
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate 固定缓冲区头部的 len、nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // 未压缩数据
    };
    var in: Reader = .fixed(input);
    var decomp: Decompress = .init(&in, .raw, &.{});
    const r = &decomp.reader;
    var bufs: [1][]u8 = .{&.{}};
    try testing.expectEqual(0, try r.readVec(&bufs));
}

test "zlib header" {
    // 截断的头部
    try testFailure(.zlib, &[_]u8{0x78}, error.EndOfStream);

    // CM 错误
    try testFailure(.zlib, &[_]u8{ 0x79, 0x94 }, error.BadZlibHeader);

    // CINFO 错误
    try testFailure(.zlib, &[_]u8{ 0x88, 0x98 }, error.BadZlibHeader);

    // 截断的校验和
    try testFailure(.zlib, &[_]u8{ 0x78, 0xda, 0x03, 0x00, 0x00 }, error.EndOfStream);
}

test "gzip header" {
    // 截断的头部
    try testFailure(.gzip, &[_]u8{ 0x1f, 0x8B }, error.EndOfStream);

    // CM 错误
    try testFailure(.gzip, &[_]u8{
        0x1f, 0x8b, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x03,
    }, error.BadGzipHeader);

    // 截断的校验和
    try testFailure(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x00,
    }, error.EndOfStream);

    // 初始大小字段被截断
    try testFailure(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00,
    }, error.EndOfStream);

    try testDecompress(.gzip, &[_]u8{
        // GZIP 头部
        0x1f, 0x8b, 0x08, 0x12, 0x00, 0x09, 0x6e, 0x88, 0x00, 0xff, 0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x00,
        // header.FHCRC(应覆盖整个头部)
        0x99, 0xd6,
        // GZIP 数据
        0x01, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    }, "");
}

test "zlib should not overshoot" {
    // 末尾额外带 4 字节的 zlib 压缩数据。
    const data = [_]u8{
        0x78, 0x9c, 0x73, 0xce, 0x2f, 0xa8, 0x2c, 0xca, 0x4c, 0xcf, 0x28, 0x51, 0x08, 0xcf, 0xcc, 0xc9,
        0x49, 0xcd, 0x55, 0x28, 0x4b, 0xcc, 0x53, 0x08, 0x4e, 0xce, 0x48, 0xcc, 0xcc, 0xd6, 0x51, 0x08,
        0xce, 0xcc, 0x4b, 0x4f, 0x2c, 0xc8, 0x2f, 0x4a, 0x55, 0x30, 0xb4, 0xb4, 0x34, 0xd5, 0xb5, 0x34,
        0x03, 0x00, 0x8b, 0x61, 0x0f, 0xa4, 0x52, 0x5a, 0x94, 0x12,
    };

    var reader: std.Io.Reader = .fixed(&data);

    var decompress_buffer: [flate.max_window_len]u8 = undefined;
    var decompress: Decompress = .init(&reader, .zlib, &decompress_buffer);
    var out: [128]u8 = undefined;

    {
        const n = try decompress.reader.readSliceShort(&out);
        try std.testing.expectEqual(46, n);
        try std.testing.expectEqualStrings("Copyright Willem van Schaik, Singapore 1995-96", out[0..n]);
    }

    // 读取器中可获取压缩块后的 4 个字节。
    const n = try reader.readSliceShort(&out);
    try std.testing.expectEqual(n, 4);
    try std.testing.expectEqualSlices(u8, data[data.len - 4 .. data.len], out[0..n]);
}

fn testFailure(container: Container, in: []const u8, expected_err: anyerror) !void {
    var reader: Reader = .fixed(in);
    var aw: Writer.Allocating = .init(testing.allocator);
    defer aw.deinit();

    var decompress: Decompress = .init(&reader, container, &.{});
    try testing.expectError(error.ReadFailed, decompress.reader.streamRemaining(&aw.writer));
    try testing.expectEqual(expected_err, decompress.err orelse return error.TestFailed);
}

fn testDecompress(container: Container, compressed: []const u8, expected_plain: []const u8) !void {
    var aw: std.Io.Writer.Allocating = .init(testing.allocator);
    defer aw.deinit();

    // 使用常规方法解压一次。
    {
        var in: std.Io.Reader = .fixed(compressed);
        var decompress: Decompress = .init(&in, container, &.{});
        const decompressed_len = try decompress.reader.streamRemaining(&aw.writer);
        try testing.expectEqual(expected_plain.len, decompressed_len);
        try testing.expectEqualSlices(u8, expected_plain, aw.written());
    }

    // 再次逐字节流式解压,检查写入部分匹配项等操作
    // 是否存在问题。
    aw.clearRetainingCapacity();
    {
        var in: std.Io.Reader = .fixed(compressed);
        var decompress: Decompress = .init(&in, container, &.{});
        var decompressed_len: usize = 0;
        while (true) {
            decompressed_len += decompress.reader.stream(&aw.writer, .limited(1)) catch |err| switch (err) {
                error.EndOfStream => break,
                else => |e| return e,
            };
        }
        try testing.expectEqual(expected_plain.len, decompressed_len);
        try testing.expectEqualSlices(u8, expected_plain, aw.written());
    }
}