跳转到内容

std.compress.zstd.Decompress

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

第 1 行

字段

input: *Reader
reader: Reader
state: State
verify_checksum: bool
window_len: u32
err: ?Error = null

std.compress.zstd.Decompress.assert

别名

第 3 行

别名目标 std.debug.assert

std.compress.zstd.Decompress.BitReader

容器

第 1867 行

字段

bytes: []const u8
index: usize = 0
bits: u8 = 0
count: u4 = 0

std.compress.zstd.Decompress.BitReader.alignToByte

函数

第 1951 行

fn alignToByte(self: *@This()) void

参数

self: *@This()

std.compress.zstd.Decompress.BitReader.initBits

函数

第 1873 行

fn initBits(comptime T: type, out: anytype, num: u16) Bits(T)

参数

T: type
num: u16

std.compress.zstd.Decompress.BitReader.readBits

函数

第 1887 行

fn readBits(self: *@This(), comptime T: type, num: u16, out_bits: *u16) !T

参数

self: *@This()
T: type
num: u16
out_bits: *u16

std.compress.zstd.Decompress.BitReader.readBitsNoEof

函数

第 1881 行

fn readBitsNoEof(self: *@This(), comptime T: type, num: u16) !T

参数

self: *@This()
T: type
num: u16

std.compress.zstd.Decompress.BitReader.readBitsTuple

函数

第 1893 行

fn readBitsTuple(self: *@This(), comptime T: type, num: u16) !Bits(T)

参数

self: *@This()
T: type
num: u16

std.compress.zstd.Decompress.BitReader.removeBits

函数

第 1938 行

fn removeBits(self: *@This(), num: u4) u8

参数

self: *@This()
num: u4

std.compress.zstd.Decompress.BitReader.takeByte

函数

第 1931 行

fn takeByte(br: *BitReader) error{EndOfStream}!u8

参数

br: *BitReader

错误

EndOfStream

std.compress.zstd.Decompress.Bits

类型函数

第 1762 行

fn Bits(comptime T: type) type

参数

T: type

字段

T
u16

std.compress.zstd.Decompress.Decompress

别名

第 1 行

别名目标 std.compress.zstd.Decompress

std.compress.zstd.Decompress.direct_vtable

常量

第 76 行

Reader.VTable

std.compress.zstd.Decompress.discardDirect

函数

第 159 行

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

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

参数

r: *Reader
limit: std.Io.Limit

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.discardIndirect

函数

第 182 行

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

参数

r: *Reader
limit: std.Io.Limit

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.Error

错误集合

第 42 行

错误

BadMagic
BlockOversize
ChecksumFailure
ContentOversize
DictionaryIdFlagUnsupported
EndOfStream
HuffmanTreeIncomplete
InputBufferUndersize
InvalidBitStream
MalformedAccuracyLog
MalformedBlock
MalformedCompressedBlock
MalformedFrame
MalformedFseBits
MalformedFseTable
MalformedHuffmanTree
MalformedLiteralsHeader
MalformedLiteralsLength
MalformedLiteralsSection
MalformedSequence
MissingStartBit
OutputBufferUndersize
ReadFailed
RepeatModeFirst
ReservedBitSet
ReservedBlock
SequenceBufferUndersize
TreelessLiteralsFirst
UnexpectedEndOfLiteralStream
WindowOversize
WindowSizeUnknown

std.compress.zstd.Decompress.Frame

容器

第 400 行

字段

hasher_opt: ?std.hash.XxHash64
window_size: usize
has_checksum: bool
block_size_max: usize
content_size: ?usize

std.compress.zstd.Decompress.Frame.init

函数

第 926 行

验证 frame_header,并返回关联的 Frame。

pub fn init( frame_header: Frame.Zstandard.Header, window_size_max: usize, verify_checksum: bool, ) InitError!Frame

参数

frame_header: Frame.Zstandard.Header
window_size_max: usize
verify_checksum: bool

错误

ContentOversize

帧头部表示的内容大小超过 usize 的最大值。

DictionaryIdFlagUnsupported

帧使用字典。

WindowOversize

窗口大小超过 window_size_max 或 usize 最大值。

WindowSizeUnknown

帧的窗口大小无效。

std.compress.zstd.Decompress.Frame.InitError

错误集合

第 914 行

错误

ContentOversize

帧头部表示的内容大小超过 usize 的最大值。

DictionaryIdFlagUnsupported

帧使用字典。

WindowOversize

窗口大小超过 window_size_max 或 usize 最大值。

WindowSizeUnknown

帧的窗口大小无效。

std.compress.zstd.Decompress.Frame.Kind

容器

第 427 行

字段

zstandard
skippable

std.compress.zstd.Decompress.Frame.Magic

容器

第 407 行

字段

zstandard = 0xFD2FB528
_

std.compress.zstd.Decompress.Frame.Magic.isSkippable

函数

第 419 行

pub fn isSkippable(m: Magic) bool

参数

m: Magic

std.compress.zstd.Decompress.Frame.Magic.kind

函数

第 411 行

pub fn kind(m: Magic) ?Kind

参数

m: Magic

std.compress.zstd.Decompress.Frame.Skippable

命名空间

第 904 行

std.compress.zstd.Decompress.Frame.Skippable.Header

容器

第 908 行

字段

magic_number: u32
frame_size: u32

std.compress.zstd.Decompress.Frame.Skippable.magic_max

常量

第 906 行

Magic

std.compress.zstd.Decompress.Frame.Skippable.magic_min

常量

第 905 行

Magic

std.compress.zstd.Decompress.Frame.Zstandard

容器

第 429 行

字段

header: Header
data_blocks: []Block
checksum: ?u32

std.compress.zstd.Decompress.Frame.Zstandard.Block

命名空间

第 494 行

std.compress.zstd.Decompress.Frame.Zstandard.Block.Header

容器

第 495 行

字段

last: bool
type: Type
size: u21

std.compress.zstd.Decompress.Frame.Zstandard.Block.Type

容器

第 501 行

字段

raw
rle
compressed
reserved

std.compress.zstd.Decompress.Frame.Zstandard.Decode

容器

第 509 行

字段

repeat_offsets: [3]u32
offset: StateData(8)
match: StateData(9)
literal: StateData(9)
literal_fse_buffer: [zstd.table_size_max.literal]Table.Fse
match_fse_buffer: [zstd.table_size_max.match]Table.Fse
offset_fse_buffer: [zstd.table_size_max.offset]Table.Fse
fse_tables_undefined: bool
literal_stream_reader: ReverseBitReader
literal_stream_index: usize
literal_streams: LiteralsSection.Streams
literal_header: LiteralsSection.Header
huffman_tree: ?LiteralsSection.HuffmanTree
literal_written_count: usize

std.compress.zstd.Decompress.Frame.Zstandard.Decode.decodeLiterals

函数

第 843 行

将 len 字节的字面量解码到 w。

fn decodeLiterals(d: *Decode, w: *Writer, len: usize) !void

参数

d: *Decode
w: *Writer
len: usize

std.compress.zstd.Decompress.Frame.Zstandard.Decode.decodeSequence

函数

第 776 行

从 bit_reader 解码一个序列到 dest。若 last_sequence 为 false,则更新 FSE 状态。假定在尝试解码序列前, 已针对此块调用 prepare。

fn decodeSequence( decode: *Decode, dest: []u8, write_pos: usize, bit_reader: *ReverseBitReader, ) !usize

参数

decode: *Decode
dest: []u8
write_pos: usize
bit_reader: *ReverseBitReader

std.compress.zstd.Decompress.Frame.Zstandard.Decode.FseTableError

错误集合

第 668 行

错误

EndOfStream
MalformedAccuracyLog
MalformedFseTable
RepeatModeFirst

std.compress.zstd.Decompress.Frame.Zstandard.Decode.getCode

函数

第 895 行

TODO: 不要使用 @field

fn getCode(self: *Decode, comptime choice: WhichFse) u32

参数

self: *Decode
choice: WhichFse

std.compress.zstd.Decompress.Frame.Zstandard.Decode.init

常量

第 540 行

Decode

std.compress.zstd.Decompress.Frame.Zstandard.Decode.initLiteralStream

函数

第 812 行

fn initLiteralStream(self: *Decode, bytes: []const u8) error{MissingStartBit}!void

参数

self: *Decode
bytes: []const u8

错误

MissingStartBit

std.compress.zstd.Decompress.Frame.Zstandard.Decode.isLiteralStreamEmpty

函数

第 816 行

fn isLiteralStreamEmpty(self: *Decode) bool

参数

self: *Decode

std.compress.zstd.Decompress.Frame.Zstandard.Decode.LiteralBitsError

错误集合

第 823 行

错误

MissingStartBit
UnexpectedEndOfLiteralStream

std.compress.zstd.Decompress.Frame.Zstandard.Decode.nextLiteralMultiStream

函数

第 807 行

fn nextLiteralMultiStream(self: *Decode) error{MissingStartBit}!void

参数

self: *Decode

错误

MissingStartBit

std.compress.zstd.Decompress.Frame.Zstandard.Decode.nextSequence

函数

第 726 行

fn nextSequence( self: *Decode, bit_reader: *ReverseBitReader, ) error{ InvalidBitStream, EndOfStream }!Sequence

参数

self: *Decode
bit_reader: *ReverseBitReader

错误

EndOfStream
InvalidBitStream

std.compress.zstd.Decompress.Frame.Zstandard.Decode.prepare

函数

第 586 行

准备解码器以解码压缩块。 从 literals 加载字面量流和 Huffman 树,从 in 读取 FSE 表。

pub fn prepare( self: *Decode, in: *Reader, remaining: *Limit, literals: LiteralsSection, sequences_header: SequencesSection.Header, ) PrepareError!void

参数

self: *Decode
in: *Reader
remaining: *Limit
literals: LiteralsSection
sequences_header: SequencesSection.Header

错误

EndOfStream

尚未读完所有 FSE 表,输入流便已结束。

InputBufferUndersize
MalformedAccuracyLog

FSE 表的精度无效

MalformedFseTable

FSE 表解码失败

MissingStartBit

反向字面量位流的首字节没有任何置位

ReadFailed
RepeatModeFirst

若某个序列 FSE 表设置为重复模式,则在首次调用时

TreelessLiteralsFirst

literals 是无树的字面量段,且解码状态中 没有来自前一个块的霍夫曼树。

std.compress.zstd.Decompress.Frame.Zstandard.Decode.PrepareError

错误集合

第 565 行

错误

EndOfStream

尚未读完所有 FSE 表,输入流便已结束。

InputBufferUndersize
MalformedAccuracyLog

FSE 表的精度无效

MalformedFseTable

FSE 表解码失败

MissingStartBit

反向字面量位流的首字节没有任何置位

ReadFailed
RepeatModeFirst

若某个序列 FSE 表设置为重复模式,则在首次调用时

TreelessLiteralsFirst

literals 是无树的字面量段,且解码状态中 没有来自前一个块的霍夫曼树。

std.compress.zstd.Decompress.Frame.Zstandard.Decode.readInitialFseState

函数

第 623 行

读取序列解码所需的初始 FSE 状态。

pub fn readInitialFseState(self: *Decode, bit_reader: *ReverseBitReader) error{EndOfStream}!void

参数

self: *Decode
bit_reader: *ReverseBitReader

错误

EndOfStream

std.compress.zstd.Decompress.Frame.Zstandard.Decode.readLiteralsBits

函数

第 827 行

fn readLiteralsBits( self: *Decode, bit_count_to_read: u16, ) LiteralBitsError!u16

参数

self: *Decode
bit_count_to_read: u16

错误

MissingStartBit
UnexpectedEndOfLiteralStream

std.compress.zstd.Decompress.Frame.Zstandard.Decode.Sequence

容器

第 720 行

字段

literal_length: u32
match_length: u32
offset: u32

std.compress.zstd.Decompress.Frame.Zstandard.Decode.StateData

类型函数

第 530 行

fn StateData(comptime max_accuracy_log: comptime_int) type

参数

max_accuracy_log: comptime_int

字段

state: @This().State
table: Table
accuracy_log: u8

std.compress.zstd.Decompress.Frame.Zstandard.Decode.StateData.State

常量

第 536 行

std.compress.zstd.Decompress.Frame.Zstandard.Decode.updateFseTable

函数

第 676 行

TODO: 不要使用 @field

fn updateFseTable( self: *Decode, in: *Reader, remaining: *Limit, comptime choice: WhichFse, mode: SequencesSection.Header.Mode, ) !void

参数

self: *Decode
in: *Reader
remaining: *Limit
choice: WhichFse
mode: SequencesSection.Header.Mode

std.compress.zstd.Decompress.Frame.Zstandard.Decode.updateRepeatOffset

函数

第 629 行

fn updateRepeatOffset(self: *Decode, offset: u32) void

参数

self: *Decode
offset: u32

std.compress.zstd.Decompress.Frame.Zstandard.Decode.updateState

函数

第 648 行

TODO: 不要使用 @field

fn updateState( self: *Decode, comptime choice: WhichFse, bit_reader: *ReverseBitReader, ) error{ MalformedFseBits, EndOfStream }!void

参数

self: *Decode
choice: WhichFse
bit_reader: *ReverseBitReader

错误

EndOfStream
MalformedFseBits

std.compress.zstd.Decompress.Frame.Zstandard.Decode.useRepeatOffset

函数

第 635 行

fn useRepeatOffset(self: *Decode, index: usize) u32

参数

self: *Decode
index: usize

std.compress.zstd.Decompress.Frame.Zstandard.Decode.WhichFse

容器

第 645 行

字段

offset
match
literal

std.compress.zstd.Decompress.Frame.Zstandard.Header

容器

第 436 行

字段

descriptor: Descriptor
window_descriptor: ?u8
dictionary_id: ?u32
content_size: ?u64

std.compress.zstd.Decompress.Frame.Zstandard.Header.decode

函数

第 453 行

pub fn decode(in: *Reader) DecodeError!Header

参数

in: *Reader

错误

EndOfStream Error
ReadFailed Error

详细诊断参见 Reader 的实现。

ReservedBitSet

std.compress.zstd.Decompress.Frame.Zstandard.Header.DecodeError

错误集合

第 451 行

错误

EndOfStream Error
ReadFailed Error

详细诊断参见 Reader 的实现。

ReservedBitSet

std.compress.zstd.Decompress.Frame.Zstandard.Header.Descriptor

容器

第 442 行

字段

dictionary_id_flag: u2
content_checksum_flag: bool
reserved: bool
unused: bool
single_segment_flag: bool
content_size_flag: u2

std.compress.zstd.Decompress.Frame.Zstandard.Header.windowSize

函数

第 482 行

返回解压帧所需的窗口大小;若无法确定则返回 null (表示帧头格式错误)。

pub fn windowSize(header: Header) ?u64

参数

header: Header

std.compress.zstd.Decompress.Frame.Zstandard.magic

常量

第 430 行

Magic

std.compress.zstd.Decompress.indirect_vtable

常量

第 83 行

Reader.VTable

std.compress.zstd.Decompress.init

函数

第 94 行

将 reader 连接到 Writer 时,buffer 应为空, Writer.buffer 的容量必须满足基于 Options.window_len 的要求。

否则,buffer 需满足这些要求。

pub fn init(input: *Reader, buffer: []u8, options: Options) Decompress

参数

input: *Reader
buffer: []u8
options: Options

std.compress.zstd.Decompress.initFrame

函数

第 273 行

fn initFrame(d: *Decompress, magic: Frame.Magic) !void

参数

d: *Decompress
magic: Frame.Magic

std.compress.zstd.Decompress.Limit

别名

第 5 行

别名目标 std.Io.Limit

std.compress.zstd.Decompress.LiteralsSection

容器

第 958 行

字段

header: Header
huffman_tree: ?HuffmanTree
streams: Streams

std.compress.zstd.Decompress.LiteralsSection.BlockType

容器

第 1060 行

字段

raw
rle
compressed
treeless

std.compress.zstd.Decompress.LiteralsSection.decode

函数

第 1305 行

pub fn decode(in: *Reader, remaining: *Limit, buffer: []u8) DecodeError!LiteralsSection

参数

in: *Reader
remaining: *Limit
buffer: []u8

错误

EndOfStream

字节不足以完成此节。

MalformedAccuracyLog

压缩字面量的精度无效。

MalformedFseTable

压缩字面量的 FSE 表无效。

MalformedHuffmanTree

霍夫曼树解码失败。

MalformedLiteralsHeader

头部无效。

MalformedLiteralsSection

解码错误。

MissingStartBit
ReadFailed

std.compress.zstd.Decompress.LiteralsSection.DecodeError

错误集合

第 1288 行

错误

EndOfStream

字节不足以完成此节。

MalformedAccuracyLog

压缩字面量的精度无效。

MalformedFseTable

压缩字面量的 FSE 表无效。

MalformedHuffmanTree

霍夫曼树解码失败。

MalformedLiteralsHeader

头部无效。

MalformedLiteralsSection

解码错误。

MissingStartBit
ReadFailed

std.compress.zstd.Decompress.LiteralsSection.Header

容器

第 994 行

字段

block_type: BlockType
size_format: u2
regenerated_size: u20
compressed_size: ?u18

std.compress.zstd.Decompress.LiteralsSection.Header.decode

函数

第 1001 行

解码字面量节头部。

pub fn decode(in: *Reader, remaining: *Limit) !Header

参数

in: *Reader
remaining: *Limit

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree

容器

第 1067 行

字段

max_bit_count: u4
symbol_count_minus_one: u8
nodes: [256]PrefixedSymbol

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.assignSymbols

函数

第 1198 行

fn assignSymbols(weight_sorted_prefixed_symbols: []PrefixedSymbol, weights: [256]u4) usize

参数

weight_sorted_prefixed_symbols: []PrefixedSymbol
weights: [256]u4

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.assignWeights

函数

第 1152 行

fn assignWeights( huff_bits_buffer: []const u8, accuracy_log: u16, entries: *[1 << 6]Table.Fse, weights: *[256]u4, ) !usize

参数

huff_bits_buffer: []const u8
accuracy_log: u16
entries: *[1 << 6]Table.Fse
weights: *[256]u4

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.build

函数

第 1244 行

fn build(weights: *[256]u4, symbol_count: usize) error{MalformedHuffmanTree}!HuffmanTree

参数

weights: *[256]u4
symbol_count: usize

错误

MalformedHuffmanTree

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.decode

函数

第 1108 行

pub fn decode(in: *Reader, remaining: *Limit) HuffmanTree.DecodeError!HuffmanTree

参数

in: *Reader
remaining: *Limit

错误

EndOfStream Error
MalformedAccuracyLog
MalformedFseTable
MalformedHuffmanTree
MissingStartBit
ReadFailed Error

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.decodeDirect

函数

第 1118 行

fn decodeDirect( in: *Reader, remaining: *Limit, encoded_symbol_count: usize, ) HuffmanTree.DecodeError!HuffmanTree

参数

in: *Reader
remaining: *Limit
encoded_symbol_count: usize

错误

EndOfStream Error
MalformedAccuracyLog
MalformedFseTable
MalformedHuffmanTree
MissingStartBit
ReadFailed Error

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.DecodeError

错误集合

第 1100 行

错误

EndOfStream Error
MalformedAccuracyLog
MalformedFseTable
MalformedHuffmanTree
MissingStartBit
ReadFailed Error

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.decodeFse

函数

第 1135 行

fn decodeFse( in: *Reader, remaining: *Limit, compressed_size: usize, ) HuffmanTree.DecodeError!HuffmanTree

参数

in: *Reader
remaining: *Limit
compressed_size: usize

错误

EndOfStream Error
MalformedAccuracyLog
MalformedFseTable
MalformedHuffmanTree
MissingStartBit
ReadFailed Error

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.lessThanByWeight

函数

第 1268 行

fn lessThanByWeight( weights: [256]u4, lhs: PrefixedSymbol, rhs: PrefixedSymbol, ) bool

参数

weights: [256]u4
lhs: PrefixedSymbol
rhs: PrefixedSymbol

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.PrefixedSymbol

容器

第 1072 行

字段

symbol: u8
prefix: u16
weight: u4

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.query

函数

第 1083 行

pub fn query(self: HuffmanTree, index: usize, prefix: u16) error{HuffmanTreeIncomplete}!Result

参数

self: HuffmanTree
index: usize
prefix: u16

错误

HuffmanTreeIncomplete

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.Result

容器

第 1078 行

字段

symbol: u8
index: usize

std.compress.zstd.Decompress.LiteralsSection.HuffmanTree.weightToBitCount

函数

第 1096 行

pub fn weightToBitCount(weight: u4, max_bit_count: u4) u4

参数

weight: u4
max_bit_count: u4

std.compress.zstd.Decompress.LiteralsSection.streamCount

函数

第 1281 行

pub fn streamCount(size_format: u2, block_type: BlockType) StreamCount

参数

size_format: u2
block_type: BlockType

std.compress.zstd.Decompress.LiteralsSection.StreamCount

容器

第 1280 行

字段

one
four

std.compress.zstd.Decompress.LiteralsSection.Streams

容器

第 963 行

字段

one: []const u8
four: [4][]const u8

std.compress.zstd.Decompress.LiteralsSection.Streams.decode

函数

第 967 行

fn decode(size_format: u2, stream_data: []const u8) !Streams

参数

size_format: u2
stream_data: []const u8

std.compress.zstd.Decompress.low_bit_mask

常量

第 1750 行

std.compress.zstd.Decompress.Options

容器

第 29 行

字段

verify_checksum: bool = false

尚未实现校验和验证; 若将此项设为 true,将触发 panic。

window_len: u32 = zstd.default_window_len

断言输出缓冲区的容量至少为 window_len 加上 zstd.block_size_max。

如果 window_len 过小,某些流的解压将 以 error.OutputBufferUndersize 失败。

std.compress.zstd.Decompress.Reader

别名

第 4 行

别名目标 std.Io.Reader

std.compress.zstd.Decompress.readInFrame

函数

第 292 行

fn readInFrame(d: *Decompress, w: *Writer, limit: Limit, state: *State.InFrame) !usize

参数

d: *Decompress
w: *Writer
limit: Limit
state: *State.InFrame

std.compress.zstd.Decompress.readVec

函数

第 202 行

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

参数

r: *Reader
data: [][]u8

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.rebase

函数

第 127 行

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

参数

r: *Reader
capacity: usize

std.compress.zstd.Decompress.rebaseFallible

函数

第 122 行

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

参数

r: *Reader
capacity: usize

错误

EndOfStream Error
ReadFailed Error

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.rebaseForDiscard

函数

第 142 行

按需重新设置 d.reader.buffer 基址,以执行受 limit 限制的丢弃操作

fn rebaseForDiscard(d: *Decompress, limit: std.Io.Limit) void

参数

d: *Decompress
limit: std.Io.Limit

std.compress.zstd.Decompress.ReverseBitReader

容器

第 1767 行

用于读取编码 FSE 压缩数据时使用的反向位流。

字段

bytes: []const u8
remaining: usize
bits: u8
count: u4

std.compress.zstd.Decompress.ReverseBitReader.init

函数

第 1773 行

fn init(bytes: []const u8) error{MissingStartBit}!ReverseBitReader

参数

bytes: []const u8

错误

MissingStartBit

std.compress.zstd.Decompress.ReverseBitReader.initBits

函数

第 1785 行

fn initBits(comptime T: type, out: anytype, num: u16) Bits(T)

参数

T: type
num: u16

std.compress.zstd.Decompress.ReverseBitReader.isEmpty

函数

第 1848 行

fn isEmpty(self: *const ReverseBitReader) bool

参数

self: *const ReverseBitReader

std.compress.zstd.Decompress.ReverseBitReader.readBits

函数

第 1799 行

fn readBits(self: *ReverseBitReader, comptime T: type, num: u16, out_bits: *u16) !T

参数

self: *ReverseBitReader
T: type
num: u16
out_bits: *u16

std.compress.zstd.Decompress.ReverseBitReader.readBitsNoEof

函数

第 1793 行

fn readBitsNoEof(self: *ReverseBitReader, comptime T: type, num: u16) error{EndOfStream}!T

参数

self: *ReverseBitReader
T: type
num: u16

错误

EndOfStream

std.compress.zstd.Decompress.ReverseBitReader.readBitsTuple

函数

第 1805 行

fn readBitsTuple(self: *ReverseBitReader, comptime T: type, num: u16) !Bits(T)

参数

self: *ReverseBitReader
T: type
num: u16

std.compress.zstd.Decompress.ReverseBitReader.removeBits

函数

第 1852 行

fn removeBits(self: *ReverseBitReader, num: u4) u8

参数

self: *ReverseBitReader
num: u4

std.compress.zstd.Decompress.ReverseBitReader.takeByte

函数

第 1842 行

fn takeByte(rbr: *ReverseBitReader) error{EndOfStream}!u8

参数

错误

EndOfStream

std.compress.zstd.Decompress.SequencesSection

容器

第 1351 行

字段

header: Header
literals_length_table: Table
offset_table: Table
match_length_table: Table

std.compress.zstd.Decompress.SequencesSection.Header

容器

第 1357 行

字段

sequence_count: u24
match_lengths: Mode
offsets: Mode
literal_lengths: Mode

std.compress.zstd.Decompress.SequencesSection.Header.decode

函数

第 1376 行

pub fn decode(in: *Reader, remaining: *Limit) DecodeError!Header

参数

in: *Reader
remaining: *Limit

错误

EndOfStream
ReadFailed
ReservedBitSet

std.compress.zstd.Decompress.SequencesSection.Header.DecodeError

错误集合

第 1370 行

错误

EndOfStream
ReadFailed
ReservedBitSet

std.compress.zstd.Decompress.SequencesSection.Header.Mode

容器

第 1363 行

字段

predefined
rle
fse
repeat

std.compress.zstd.Decompress.State

容器

第 16 行

字段

new_frame
in_frame: InFrame
skipping_frame: usize

std.compress.zstd.Decompress.State.InFrame

容器

第 21 行

字段

frame: Frame
checksum: ?u32
decompressed_size: usize
decode: Frame.Zstandard.Decode

std.compress.zstd.Decompress.std

别名

第 2 行

别名目标 std

std.compress.zstd.Decompress.stream

函数

第 228 行

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

参数

d: *Decompress
w: *Writer
limit: Limit

错误

EndOfStream

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

ReadFailed

详细诊断参见 Reader 的实现。

WriteFailed

详细诊断信息见 Writer 实现。

std.compress.zstd.Decompress.streamDirect

函数

第 110 行

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.zstd.Decompress.streamIndirect

函数

第 115 行

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.zstd.Decompress.streamIndirectInner

函数

第 208 行

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

参数

错误

EndOfStream
ReadFailed

详细诊断参见 Reader 的实现。

std.compress.zstd.Decompress.Table

容器

第 1416 行

字段

fse: []const Fse
rle: u8

std.compress.zstd.Decompress.Table.build

函数

第 1490 行

pub fn build(values: []const u16, entries: []Table.Fse) !void

参数

values: []const u16
entries: []Table.Fse

用法示例

test build {
    const literals_length_default_values = [36]u16{
        5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2,
        3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2,
        0, 0, 0, 0,
    };

    const match_lengths_default_values = [53]u16{
        2, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0,
        0, 0, 0, 0, 0,
    };

    const offset_codes_default_values = [29]u16{
        2, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0,
    };

    var entries: [64]Table.Fse = undefined;
    try build(&literals_length_default_values, &entries);
    try std.testing.expectEqualSlices(Table.Fse, Table.predefined_literal.fse, &entries);

    try build(&match_lengths_default_values, &entries);
    try std.testing.expectEqualSlices(Table.Fse, Table.predefined_match.fse, &entries);

    try build(&offset_codes_default_values, entries[0..32]);
    try std.testing.expectEqualSlices(Table.Fse, Table.predefined_offset.fse, entries[0..32]);
}

std.compress.zstd.Decompress.Table.decode

函数

第 1426 行

pub fn decode( bit_reader: *BitReader, expected_symbol_count: usize, max_accuracy_log: u4, entries: []Table.Fse, ) !usize

参数

bit_reader: *BitReader
expected_symbol_count: usize
max_accuracy_log: u4
entries: []Table.Fse

std.compress.zstd.Decompress.Table.Fse

容器

第 1420 行

字段

symbol: u8
baseline: u16
bits: u8

std.compress.zstd.Decompress.Table.predefined_literal

常量

第 1574 行

Table

std.compress.zstd.Decompress.Table.predefined_match

常量

第 1643 行

Table

std.compress.zstd.Decompress.Table.predefined_offset

常量

第 1712 行

Table

std.compress.zstd.Decompress.Writer

别名

第 7 行

别名目标 std.Io.Writer

std.compress.zstd.Decompress.zstd

别名

第 6 行

别名目标 std.compress.zstd

源码

std/compress/zstd/Decompress.zig

const Decompress = @This();
const std = @import("std");
const assert = std.debug.assert;
const Reader = std.Io.Reader;
const Limit = std.Io.Limit;
const zstd = @import("../zstd.zig");
const Writer = std.Io.Writer;

input: *Reader,
reader: Reader,
state: State,
verify_checksum: bool,
window_len: u32,
err: ?Error = null,

const State = union(enum) {
    new_frame,
    in_frame: InFrame,
    skipping_frame: usize,

    const InFrame = struct {
        frame: Frame,
        checksum: ?u32,
        decompressed_size: usize,
        decode: Frame.Zstandard.Decode,
    };
};

pub const Options = struct {
    /// 尚未实现校验和验证;
    /// 若将此项设为 true,将触发 panic。
    verify_checksum: bool = false,

    /// 断言输出缓冲区的容量至少为 `window_len` 加上
    /// `zstd.block_size_max`。
    ///
    /// 如果 `window_len` 过小,某些流的解压将
    /// 以 `error.OutputBufferUndersize` 失败。
    window_len: u32 = zstd.default_window_len,
};

pub const Error = error{
    BadMagic,
    BlockOversize,
    ChecksumFailure,
    ContentOversize,
    DictionaryIdFlagUnsupported,
    EndOfStream,
    HuffmanTreeIncomplete,
    InvalidBitStream,
    MalformedAccuracyLog,
    MalformedBlock,
    MalformedCompressedBlock,
    MalformedFrame,
    MalformedFseBits,
    MalformedFseTable,
    MalformedHuffmanTree,
    MalformedLiteralsHeader,
    MalformedLiteralsLength,
    MalformedLiteralsSection,
    MalformedSequence,
    MissingStartBit,
    OutputBufferUndersize,
    InputBufferUndersize,
    ReadFailed,
    RepeatModeFirst,
    ReservedBitSet,
    ReservedBlock,
    SequenceBufferUndersize,
    TreelessLiteralsFirst,
    UnexpectedEndOfLiteralStream,
    WindowOversize,
    WindowSizeUnknown,
};

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,
};

/// 将 `reader` 连接到 `Writer` 时,`buffer` 应为空,
/// `Writer.buffer` 的容量必须满足基于 `Options.window_len` 的要求。
///
/// 否则,`buffer` 需满足这些要求。
pub fn init(input: *Reader, buffer: []u8, options: Options) Decompress {
    if (buffer.len != 0) assert(buffer.len >= options.window_len + zstd.block_size_max);
    return .{
        .input = input,
        .state = .new_frame,
        .verify_checksum = options.verify_checksum,
        .window_len = options.window_len,
        .reader = .{
            .vtable = if (buffer.len == 0) &direct_vtable else &indirect_vtable,
            .buffer = buffer,
            .seek = 0,
            .end = 0,
        },
    };
}

fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    return stream(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 rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void {
    rebase(r, capacity);
}

// 调整缓冲区基址,至少保留滑动窗口(`d.window_len` 字节)的缓冲数据。
fn rebase(r: *Reader, capacity: usize) void {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    // `capacity` 必须能与所需滑动窗口一同放入缓冲区。
    assert(capacity <= r.buffer.len - d.window_len);
    // 根据虚函数表契约,只有缓冲区的可用空间
    // 不足以容纳 `capacity` 字节时,才会调用此函数
    assert(r.end + capacity > r.buffer.len);
    const discard_n = @min(r.seek, r.end - d.window_len);
    const keep = r.buffer[discard_n..r.end];
    @memmove(r.buffer[0..keep.len], keep);
    r.end = keep.len;
    r.seek -= discard_n;
}

/// 按需重新设置 `d.reader.buffer` 基址,以执行受 `limit` 限制的丢弃操作
fn rebaseForDiscard(d: *Decompress, limit: std.Io.Limit) void {
    // 期望重新设置基址的字节数,每次至少处理 block_size
    const desire_n = limit.max(Limit.limited(zstd.block_size_max));
    // 可重定位的最大字节数
    const max_n = d.reader.buffer.len -| d.window_len;
    // 重定位的字节数
    const n = desire_n.minInt(max_n);

    // 当前缓冲区的空闲空间
    const current_cap = d.reader.buffer.len - d.reader.end;
    if (current_cap < n) {
        rebase(&d.reader, n);
    }
}

/// 可进一步改进:当丢弃的数据量包含
/// 完整帧时,跳过该帧的解码。
fn discardDirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    rebaseForDiscard(d, limit);
    var writer: Writer = .{
        .vtable = &.{
            .drain = std.Io.Writer.Discarding.drain,
            .sendFile = std.Io.Writer.Discarding.sendFile,
        },
        .buffer = r.buffer,
        .end = r.end,
    };
    defer {
        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));
    rebaseForDiscard(d, limit);
    var writer: Writer = .{
        .buffer = r.buffer,
        .end = r.end,
        .vtable = &.{ .drain = Writer.unreachableDrain },
    };
    {
        defer r.end = writer.end;
        _ = stream(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 < zstd.block_size_max) rebase(r, zstd.block_size_max);
    assert(r.buffer.len - r.end >= zstd.block_size_max);
    var writer: Writer = .{
        .buffer = r.buffer,
        .end = r.end,
        .vtable = &.{
            .drain = Writer.unreachableDrain,
            .rebase = Writer.unreachableRebase,
        },
    };
    defer r.end = writer.end;
    _ = stream(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
        error.WriteFailed => unreachable,
        else => |e| return e,
    };
    return 0;
}

fn stream(d: *Decompress, w: *Writer, limit: Limit) Reader.StreamError!usize {
    const in = d.input;

    state: switch (d.state) {
        .new_frame => {
            // 仅在帧魔数恰好剩余 0 字节时返回 EndOfStream。任何不完整魔数字节都应视为失败。
            //
            in.fill(@sizeOf(Frame.Magic)) catch |err| switch (err) {
                error.EndOfStream => {
                    if (in.bufferedLen() != 0) {
                        d.err = error.BadMagic;
                        return error.ReadFailed;
                    }
                    return err;
                },
                else => |e| return e,
            };
            const magic = try in.takeEnumNonexhaustive(Frame.Magic, .little);
            initFrame(d, magic) catch |err| {
                d.err = err;
                return error.ReadFailed;
            };
            continue :state d.state;
        },
        .in_frame => |*in_frame| {
            return readInFrame(d, w, limit, in_frame) catch |err| switch (err) {
                error.ReadFailed, error.WriteFailed => |e| return e,
                else => |e| {
                    d.err = e;
                    return error.ReadFailed;
                },
            };
        },
        .skipping_frame => |*remaining| {
            const n = in.discard(.limited(remaining.*)) catch |err| {
                d.err = err;
                return error.ReadFailed;
            };
            remaining.* -= n;
            if (remaining.* == 0) d.state = .new_frame;
            return 0;
        },
    }
}

fn initFrame(d: *Decompress, magic: Frame.Magic) !void {
    const in = d.input;
    switch (magic.kind() orelse return error.BadMagic) {
        .zstandard => {
            const header = try Frame.Zstandard.Header.decode(in);
            d.state = .{ .in_frame = .{
                .frame = try Frame.init(header, d.window_len, d.verify_checksum),
                .checksum = null,
                .decompressed_size = 0,
                .decode = .init,
            } };
        },
        .skippable => {
            const frame_size = try in.takeInt(u32, .little);
            d.state = .{ .skipping_frame = frame_size };
        },
    }
}

fn readInFrame(d: *Decompress, w: *Writer, limit: Limit, state: *State.InFrame) !usize {
    const in = d.input;
    const window_len = d.window_len;

    const block_header = try in.takeStruct(Frame.Zstandard.Block.Header, .little);
    const block_size = block_header.size;
    const frame_block_size_max = state.frame.block_size_max;
    if (frame_block_size_max < block_size) return error.BlockOversize;
    if (@backingInt(limit) < block_size) return error.OutputBufferUndersize;
    var bytes_written: usize = 0;
    switch (block_header.type) {
        .raw => {
            try in.streamExactPreserve(w, window_len, block_size);
            bytes_written = block_size;
        },
        .rle => {
            const byte = try in.takeByte();
            try w.splatBytePreserve(window_len, byte, block_size);
            bytes_written = block_size;
        },
        .compressed => {
            var literals_buffer: [zstd.block_size_max]u8 = undefined;
            var sequence_buffer: [zstd.block_size_max]u8 = undefined;
            var remaining: Limit = .limited(block_size);
            const literals = try LiteralsSection.decode(in, &remaining, &literals_buffer);
            const sequences_header = try SequencesSection.Header.decode(in, &remaining);

            const decode = &state.decode;
            try decode.prepare(in, &remaining, literals, sequences_header);

            {
                if (sequence_buffer.len < @backingInt(remaining))
                    return error.SequenceBufferUndersize;
                const seq_slice = remaining.slice(&sequence_buffer);
                try in.readSliceAll(seq_slice);
                var bit_stream = try ReverseBitReader.init(seq_slice);

                if (sequences_header.sequence_count > 0) {
                    try decode.readInitialFseState(&bit_stream);

                    // 确保后续对 `decodeSequence` 的调用不会刷新。
                    const dest = (try w.writableSliceGreedyPreserve(window_len, frame_block_size_max))[0..frame_block_size_max];
                    const write_pos = dest.ptr - w.buffer.ptr;
                    for (0..sequences_header.sequence_count - 1) |_| {
                        bytes_written += try decode.decodeSequence(w.buffer, write_pos + bytes_written, &bit_stream);
                        try decode.updateState(.literal, &bit_stream);
                        try decode.updateState(.match, &bit_stream);
                        try decode.updateState(.offset, &bit_stream);
                    }
                    bytes_written += try decode.decodeSequence(w.buffer, write_pos + bytes_written, &bit_stream);
                    if (bytes_written > dest.len) return error.MalformedSequence;
                    w.advance(bytes_written);
                }

                if (!bit_stream.isEmpty()) {
                    return error.MalformedCompressedBlock;
                }
            }

            if (decode.literal_written_count < literals.header.regenerated_size) {
                const len = literals.header.regenerated_size - decode.literal_written_count;
                try decode.decodeLiterals(w, len);
                decode.literal_written_count += len;
                bytes_written += len;
            }

            switch (decode.literal_header.block_type) {
                .treeless, .compressed => {
                    if (!decode.isLiteralStreamEmpty()) return error.MalformedCompressedBlock;
                },
                .raw, .rle => {},
            }

            if (bytes_written > frame_block_size_max) return error.BlockOversize;
        },
        .reserved => return error.ReservedBlock,
    }

    if (state.frame.hasher_opt) |*hasher| {
        if (bytes_written > 0) {
            _ = hasher;
            @panic("TODO all those bytes written needed to go through the hasher too");
        }
    }

    state.decompressed_size += bytes_written;

    if (block_header.last) {
        if (state.frame.has_checksum) {
            const expected_checksum = try in.takeInt(u32, .little);
            if (state.frame.hasher_opt) |*hasher| {
                const actual_checksum: u32 = @truncate(hasher.final());
                if (expected_checksum != actual_checksum) return error.ChecksumFailure;
            }
        }
        if (state.frame.content_size) |content_size| {
            if (content_size != state.decompressed_size) {
                return error.MalformedFrame;
            }
        }
        d.state = .new_frame;
    } else if (state.frame.content_size) |content_size| {
        if (state.decompressed_size > content_size) return error.MalformedFrame;
    }

    return bytes_written;
}

pub const Frame = struct {
    hasher_opt: ?std.hash.XxHash64,
    window_size: usize,
    has_checksum: bool,
    block_size_max: usize,
    content_size: ?usize,

    pub const Magic = enum(u32) {
        zstandard = 0xFD2FB528,
        _,

        pub fn kind(m: Magic) ?Kind {
            return switch (@backingInt(m)) {
                @backingInt(Magic.zstandard) => .zstandard,
                @backingInt(Skippable.magic_min)...@backingInt(Skippable.magic_max) => .skippable,
                else => null,
            };
        }

        pub fn isSkippable(m: Magic) bool {
            return switch (@backingInt(m)) {
                @backingInt(Skippable.magic_min)...@backingInt(Skippable.magic_max) => true,
                else => false,
            };
        }
    };

    pub const Kind = enum { zstandard, skippable };

    pub const Zstandard = struct {
        pub const magic: Magic = .zstandard;

        header: Header,
        data_blocks: []Block,
        checksum: ?u32,

        pub const Header = struct {
            descriptor: Descriptor,
            window_descriptor: ?u8,
            dictionary_id: ?u32,
            content_size: ?u64,

            pub const Descriptor = packed struct {
                dictionary_id_flag: u2,
                content_checksum_flag: bool,
                reserved: bool,
                unused: bool,
                single_segment_flag: bool,
                content_size_flag: u2,
            };

            pub const DecodeError = Reader.Error || error{ReservedBitSet};

            pub fn decode(in: *Reader) DecodeError!Header {
                const descriptor: Descriptor = @bitCast(try in.takeByte());

                if (descriptor.reserved) return error.ReservedBitSet;

                const window_descriptor: ?u8 = if (descriptor.single_segment_flag) null else try in.takeByte();

                const dictionary_id: ?u32 = if (descriptor.dictionary_id_flag > 0) d: {
                    // 若 flag 为 3,则 field_size = 4;否则 field_size = flag
                    const field_size = (@as(u4, 1) << descriptor.dictionary_id_flag) >> 1;
                    break :d try in.takeVarInt(u32, .little, field_size);
                } else null;

                const content_size: ?u64 = if (descriptor.single_segment_flag or descriptor.content_size_flag > 0) c: {
                    const field_size = @as(u4, 1) << descriptor.content_size_flag;
                    const content_size = try in.takeVarInt(u64, .little, field_size);
                    break :c if (field_size == 2) content_size + 256 else content_size;
                } else null;

                return .{
                    .descriptor = descriptor,
                    .window_descriptor = window_descriptor,
                    .dictionary_id = dictionary_id,
                    .content_size = content_size,
                };
            }

            /// 返回解压帧所需的窗口大小;若无法确定则返回 `null`
            /// (表示帧头格式错误)。
            pub fn windowSize(header: Header) ?u64 {
                if (header.window_descriptor) |descriptor| {
                    const exponent = (descriptor & 0b11111000) >> 3;
                    const mantissa = descriptor & 0b00000111;
                    const window_log = 10 + exponent;
                    const window_base = @as(u64, 1) << @as(u6, @intCast(window_log));
                    const window_add = (window_base / 8) * mantissa;
                    return window_base + window_add;
                } else return header.content_size;
            }
        };

        pub const Block = struct {
            pub const Header = packed struct(u24) {
                last: bool,
                type: Type,
                size: u21,
            };

            pub const Type = enum(u2) {
                raw,
                rle,
                compressed,
                reserved,
            };
        };

        pub const Decode = struct {
            repeat_offsets: [3]u32,

            offset: StateData(8),
            match: StateData(9),
            literal: StateData(9),

            literal_fse_buffer: [zstd.table_size_max.literal]Table.Fse,
            match_fse_buffer: [zstd.table_size_max.match]Table.Fse,
            offset_fse_buffer: [zstd.table_size_max.offset]Table.Fse,

            fse_tables_undefined: bool,

            literal_stream_reader: ReverseBitReader,
            literal_stream_index: usize,
            literal_streams: LiteralsSection.Streams,
            literal_header: LiteralsSection.Header,
            huffman_tree: ?LiteralsSection.HuffmanTree,

            literal_written_count: usize,

            fn StateData(comptime max_accuracy_log: comptime_int) type {
                return struct {
                    state: @This().State,
                    table: Table,
                    accuracy_log: u8,

                    const State = @Int(.unsigned, max_accuracy_log);
                };
            }

            const init: Decode = .{
                .repeat_offsets = .{
                    zstd.start_repeated_offset_1,
                    zstd.start_repeated_offset_2,
                    zstd.start_repeated_offset_3,
                },

                .offset = undefined,
                .match = undefined,
                .literal = undefined,

                .literal_fse_buffer = undefined,
                .match_fse_buffer = undefined,
                .offset_fse_buffer = undefined,

                .fse_tables_undefined = true,

                .literal_written_count = 0,
                .literal_header = undefined,
                .literal_streams = undefined,
                .literal_stream_reader = undefined,
                .literal_stream_index = undefined,
                .huffman_tree = null,
            };

            pub const PrepareError = error{
                /// 反向字面量位流的首字节没有任何置位
                MissingStartBit,
                /// `literals` 是无树的字面量段,且解码状态中
                /// 没有来自前一个块的霍夫曼树。
                TreelessLiteralsFirst,
                /// 若某个序列 FSE 表设置为重复模式,则在首次调用时
                RepeatModeFirst,
                /// FSE 表的精度无效
                MalformedAccuracyLog,
                /// FSE 表解码失败
                MalformedFseTable,
                /// 尚未读完所有 FSE 表,输入流便已结束。
                EndOfStream,
                ReadFailed,
                InputBufferUndersize,
            };

            /// 准备解码器以解码压缩块。
            /// 从 `literals` 加载字面量流和 Huffman 树,从 `in` 读取 FSE 表。
            ///
            pub fn prepare(
                self: *Decode,
                in: *Reader,
                remaining: *Limit,
                literals: LiteralsSection,
                sequences_header: SequencesSection.Header,
            ) PrepareError!void {
                self.literal_written_count = 0;
                self.literal_header = literals.header;
                self.literal_streams = literals.streams;

                if (literals.huffman_tree) |tree| {
                    self.huffman_tree = tree;
                } else if (literals.header.block_type == .treeless and self.huffman_tree == null) {
                    return error.TreelessLiteralsFirst;
                }

                switch (literals.header.block_type) {
                    .raw, .rle => {},
                    .compressed, .treeless => {
                        self.literal_stream_index = 0;
                        switch (literals.streams) {
                            .one => |slice| try self.initLiteralStream(slice),
                            .four => |streams| try self.initLiteralStream(streams[0]),
                        }
                    },
                }

                if (sequences_header.sequence_count > 0) {
                    try self.updateFseTable(in, remaining, .literal, sequences_header.literal_lengths);
                    try self.updateFseTable(in, remaining, .offset, sequences_header.offsets);
                    try self.updateFseTable(in, remaining, .match, sequences_header.match_lengths);
                    self.fse_tables_undefined = false;
                }
            }

            /// 读取序列解码所需的初始 FSE 状态。
            pub fn readInitialFseState(self: *Decode, bit_reader: *ReverseBitReader) error{EndOfStream}!void {
                self.literal.state = try bit_reader.readBitsNoEof(u9, self.literal.accuracy_log);
                self.offset.state = try bit_reader.readBitsNoEof(u8, self.offset.accuracy_log);
                self.match.state = try bit_reader.readBitsNoEof(u9, self.match.accuracy_log);
            }

            fn updateRepeatOffset(self: *Decode, offset: u32) void {
                self.repeat_offsets[2] = self.repeat_offsets[1];
                self.repeat_offsets[1] = self.repeat_offsets[0];
                self.repeat_offsets[0] = offset;
            }

            fn useRepeatOffset(self: *Decode, index: usize) u32 {
                if (index == 1)
                    std.mem.swap(u32, &self.repeat_offsets[0], &self.repeat_offsets[1])
                else if (index == 2) {
                    std.mem.swap(u32, &self.repeat_offsets[0], &self.repeat_offsets[2]);
                    std.mem.swap(u32, &self.repeat_offsets[1], &self.repeat_offsets[2]);
                }
                return self.repeat_offsets[0];
            }

            const WhichFse = enum { offset, match, literal };

            /// TODO: 不要使用 `@field`
            fn updateState(
                self: *Decode,
                comptime choice: WhichFse,
                bit_reader: *ReverseBitReader,
            ) error{ MalformedFseBits, EndOfStream }!void {
                switch (@field(self, @tagName(choice)).table) {
                    .rle => {},
                    .fse => |table| {
                        const data = table[@field(self, @tagName(choice)).state];
                        const T = @TypeOf(@field(self, @tagName(choice))).State;
                        const bits_summand = try bit_reader.readBitsNoEof(T, data.bits);
                        const next_state = std.math.cast(
                            @TypeOf(@field(self, @tagName(choice))).State,
                            data.baseline + bits_summand,
                        ) orelse return error.MalformedFseBits;
                        @field(self, @tagName(choice)).state = next_state;
                    },
                }
            }

            const FseTableError = error{
                MalformedFseTable,
                MalformedAccuracyLog,
                RepeatModeFirst,
                EndOfStream,
            };

            /// TODO: 不要使用 `@field`
            fn updateFseTable(
                self: *Decode,
                in: *Reader,
                remaining: *Limit,
                comptime choice: WhichFse,
                mode: SequencesSection.Header.Mode,
            ) !void {
                const field_name = @tagName(choice);
                switch (mode) {
                    .predefined => {
                        @field(self, field_name).accuracy_log =
                            @field(zstd.default_accuracy_log, field_name);

                        @field(self, field_name).table =
                            @field(Table, "predefined_" ++ field_name);
                    },
                    .rle => {
                        @field(self, field_name).accuracy_log = 0;
                        remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
                        @field(self, field_name).table = .{ .rle = try in.takeByte() };
                    },
                    .fse => {
                        const max_table_size = 2048;
                        const peek_len: usize = remaining.minInt(max_table_size);
                        if (in.buffer.len < peek_len) return error.InputBufferUndersize;
                        const limited_buffer = try in.peek(peek_len);
                        var bit_reader: BitReader = .{ .bytes = limited_buffer };
                        const table_size = try Table.decode(
                            &bit_reader,
                            @field(zstd.table_symbol_count_max, field_name),
                            @field(zstd.table_accuracy_log_max, field_name),
                            &@field(self, field_name ++ "_fse_buffer"),
                        );
                        @field(self, field_name).table = .{
                            .fse = (&@field(self, field_name ++ "_fse_buffer"))[0..table_size],
                        };
                        @field(self, field_name).accuracy_log = std.math.log2_int_ceil(usize, table_size);
                        in.toss(bit_reader.index);
                        remaining.* = remaining.subtract(bit_reader.index).?;
                    },
                    .repeat => if (self.fse_tables_undefined) return error.RepeatModeFirst,
                }
            }

            const Sequence = struct {
                literal_length: u32,
                match_length: u32,
                offset: u32,
            };

            fn nextSequence(
                self: *Decode,
                bit_reader: *ReverseBitReader,
            ) error{ InvalidBitStream, EndOfStream }!Sequence {
                const raw_code = self.getCode(.offset);
                const offset_code = std.math.cast(u5, raw_code) orelse {
                    return error.InvalidBitStream;
                };
                const offset_value = (@as(u32, 1) << offset_code) + try bit_reader.readBitsNoEof(u32, offset_code);

                const match_code = self.getCode(.match);
                if (match_code >= zstd.match_length_code_table.len)
                    return error.InvalidBitStream;
                const match = zstd.match_length_code_table[match_code];
                const match_length = match[0] + try bit_reader.readBitsNoEof(u32, match[1]);

                const literal_code = self.getCode(.literal);
                if (literal_code >= zstd.literals_length_code_table.len)
                    return error.InvalidBitStream;
                const literal = zstd.literals_length_code_table[literal_code];
                const literal_length = literal[0] + try bit_reader.readBitsNoEof(u32, literal[1]);

                const offset = if (offset_value > 3) offset: {
                    const offset = offset_value - 3;
                    self.updateRepeatOffset(offset);
                    break :offset offset;
                } else offset: {
                    if (literal_length == 0) {
                        if (offset_value == 3) {
                            const offset = self.repeat_offsets[0] - 1;
                            self.updateRepeatOffset(offset);
                            break :offset offset;
                        }
                        break :offset self.useRepeatOffset(offset_value);
                    }
                    break :offset self.useRepeatOffset(offset_value - 1);
                };

                if (offset == 0) return error.InvalidBitStream;

                return .{
                    .literal_length = literal_length,
                    .match_length = match_length,
                    .offset = offset,
                };
            }

            /// 从 `bit_reader` 解码一个序列到 `dest`。若 `last_sequence`
            /// 为 `false`,则更新 FSE 状态。假定在尝试解码序列前,
            /// 已针对此块调用 `prepare`。
            fn decodeSequence(
                decode: *Decode,
                dest: []u8,
                write_pos: usize,
                bit_reader: *ReverseBitReader,
            ) !usize {
                const sequence = try decode.nextSequence(bit_reader);
                const literal_length: usize = sequence.literal_length;
                const match_length: usize = sequence.match_length;
                const sequence_length = literal_length + match_length;

                if (sequence_length > dest[write_pos..].len)
                    return error.MalformedSequence;

                const copy_start = std.math.sub(usize, write_pos + sequence.literal_length, sequence.offset) catch
                    return error.MalformedSequence;

                if (decode.literal_written_count + literal_length > decode.literal_header.regenerated_size)
                    return error.MalformedLiteralsLength;
                var sub_bw: Writer = .fixed(dest[write_pos..]);
                try decodeLiterals(decode, &sub_bw, literal_length);
                decode.literal_written_count += literal_length;
                // 这不是 @memmove;这里有意重复
                // 逐字节迭代产生的模式。
                for (
                    dest[write_pos + literal_length ..][0..match_length],
                    dest[copy_start..][0..match_length],
                ) |*d, s| d.* = s;
                return sequence_length;
            }

            fn nextLiteralMultiStream(self: *Decode) error{MissingStartBit}!void {
                self.literal_stream_index += 1;
                try self.initLiteralStream(self.literal_streams.four[self.literal_stream_index]);
            }

            fn initLiteralStream(self: *Decode, bytes: []const u8) error{MissingStartBit}!void {
                self.literal_stream_reader = try ReverseBitReader.init(bytes);
            }

            fn isLiteralStreamEmpty(self: *Decode) bool {
                switch (self.literal_streams) {
                    .one => return self.literal_stream_reader.isEmpty(),
                    .four => return self.literal_stream_index == 3 and self.literal_stream_reader.isEmpty(),
                }
            }

            const LiteralBitsError = error{
                MissingStartBit,
                UnexpectedEndOfLiteralStream,
            };
            fn readLiteralsBits(
                self: *Decode,
                bit_count_to_read: u16,
            ) LiteralBitsError!u16 {
                return self.literal_stream_reader.readBitsNoEof(u16, bit_count_to_read) catch bits: {
                    if (self.literal_streams == .four and self.literal_stream_index < 3) {
                        try self.nextLiteralMultiStream();
                        break :bits self.literal_stream_reader.readBitsNoEof(u16, bit_count_to_read) catch
                            return error.UnexpectedEndOfLiteralStream;
                    } else {
                        return error.UnexpectedEndOfLiteralStream;
                    }
                };
            }

            /// 将 `len` 字节的字面量解码到 `w`。
            fn decodeLiterals(d: *Decode, w: *Writer, len: usize) !void {
                switch (d.literal_header.block_type) {
                    .raw => {
                        try w.writeAll(d.literal_streams.one[d.literal_written_count..][0..len]);
                    },
                    .rle => {
                        try w.splatByteAll(d.literal_streams.one[0], len);
                    },
                    .compressed, .treeless => {
                        const buf = try w.writableSlice(len);
                        const huffman_tree = d.huffman_tree.?;
                        const max_bit_count = huffman_tree.max_bit_count;
                        const starting_bit_count = LiteralsSection.HuffmanTree.weightToBitCount(
                            huffman_tree.nodes[huffman_tree.symbol_count_minus_one].weight,
                            max_bit_count,
                        );
                        var bits_read: u4 = 0;
                        var huffman_tree_index: usize = huffman_tree.symbol_count_minus_one;
                        var bit_count_to_read: u4 = starting_bit_count;
                        for (buf) |*out| {
                            var prefix: u16 = 0;
                            while (true) {
                                const new_bits = try d.readLiteralsBits(bit_count_to_read);
                                prefix <<= bit_count_to_read;
                                prefix |= new_bits;
                                bits_read += bit_count_to_read;
                                const result = try huffman_tree.query(huffman_tree_index, prefix);

                                switch (result) {
                                    .symbol => |sym| {
                                        out.* = sym;
                                        bit_count_to_read = starting_bit_count;
                                        bits_read = 0;
                                        huffman_tree_index = huffman_tree.symbol_count_minus_one;
                                        break;
                                    },
                                    .index => |index| {
                                        huffman_tree_index = index;
                                        const bit_count = LiteralsSection.HuffmanTree.weightToBitCount(
                                            huffman_tree.nodes[index].weight,
                                            max_bit_count,
                                        );
                                        bit_count_to_read = bit_count - bits_read;
                                    },
                                }
                            }
                        }
                    },
                }
            }

            /// TODO: 不要使用 `@field`
            fn getCode(self: *Decode, comptime choice: WhichFse) u32 {
                return switch (@field(self, @tagName(choice)).table) {
                    .rle => |value| value,
                    .fse => |table| table[@field(self, @tagName(choice)).state].symbol,
                };
            }
        };
    };

    pub const Skippable = struct {
        pub const magic_min: Magic = @fromBackingInt(@intCast(0x184D2A50));
        pub const magic_max: Magic = @fromBackingInt(@intCast(0x184D2A5F));

        pub const Header = struct {
            magic_number: u32,
            frame_size: u32,
        };
    };

    const InitError = error{
        /// 帧使用字典。
        DictionaryIdFlagUnsupported,
        /// 帧的窗口大小无效。
        WindowSizeUnknown,
        /// 窗口大小超过 `window_size_max` 或 `usize` 最大值。
        WindowOversize,
        /// 帧头部表示的内容大小超过 `usize` 的最大值。
        ContentOversize,
    };

    /// 验证 `frame_header`,并返回关联的 `Frame`。
    pub fn init(
        frame_header: Frame.Zstandard.Header,
        window_size_max: usize,
        verify_checksum: bool,
    ) InitError!Frame {
        if (frame_header.descriptor.dictionary_id_flag != 0)
            return error.DictionaryIdFlagUnsupported;

        const window_size_raw = frame_header.windowSize() orelse return error.WindowSizeUnknown;
        const window_size = if (window_size_raw > window_size_max)
            return error.WindowOversize
        else
            std.math.cast(usize, window_size_raw) orelse return error.WindowOversize;

        const should_compute_checksum =
            frame_header.descriptor.content_checksum_flag and verify_checksum;

        const content_size = if (frame_header.content_size) |size|
            std.math.cast(usize, size) orelse return error.ContentOversize
        else
            null;

        return .{
            .hasher_opt = if (should_compute_checksum) std.hash.XxHash64.init(0) else null,
            .window_size = window_size,
            .has_checksum = frame_header.descriptor.content_checksum_flag,
            .block_size_max = @min(zstd.block_size_max, window_size),
            .content_size = content_size,
        };
    }
};

pub const LiteralsSection = struct {
    header: Header,
    huffman_tree: ?HuffmanTree,
    streams: Streams,

    pub const Streams = union(enum) {
        one: []const u8,
        four: [4][]const u8,

        fn decode(size_format: u2, stream_data: []const u8) !Streams {
            if (size_format == 0) {
                return .{ .one = stream_data };
            }

            if (stream_data.len < 6) return error.MalformedLiteralsSection;

            const stream_1_length: usize = std.mem.readInt(u16, stream_data[0..2], .little);
            const stream_2_length: usize = std.mem.readInt(u16, stream_data[2..4], .little);
            const stream_3_length: usize = std.mem.readInt(u16, stream_data[4..6], .little);

            const stream_1_start = 6;
            const stream_2_start = stream_1_start + stream_1_length;
            const stream_3_start = stream_2_start + stream_2_length;
            const stream_4_start = stream_3_start + stream_3_length;

            if (stream_data.len < stream_4_start) return error.MalformedLiteralsSection;

            return .{ .four = .{
                stream_data[stream_1_start .. stream_1_start + stream_1_length],
                stream_data[stream_2_start .. stream_2_start + stream_2_length],
                stream_data[stream_3_start .. stream_3_start + stream_3_length],
                stream_data[stream_4_start..],
            } };
        }
    };

    pub const Header = struct {
        block_type: BlockType,
        size_format: u2,
        regenerated_size: u20,
        compressed_size: ?u18,

        /// 解码字面量节头部。
        pub fn decode(in: *Reader, remaining: *Limit) !Header {
            remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
            const byte0 = try in.takeByte();
            const block_type: BlockType = @fromBackingInt(@intCast(byte0 & 0b11));
            const size_format: u2 = @intCast((byte0 & 0b1100) >> 2);
            var regenerated_size: u20 = undefined;
            var compressed_size: ?u18 = null;
            switch (block_type) {
                .raw, .rle => {
                    switch (size_format) {
                        0, 2 => {
                            regenerated_size = byte0 >> 3;
                        },
                        1 => {
                            remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
                            regenerated_size = (byte0 >> 4) + (@as(u20, try in.takeByte()) << 4);
                        },
                        3 => {
                            remaining.* = remaining.subtract(2) orelse return error.EndOfStream;
                            regenerated_size = (byte0 >> 4) +
                                (@as(u20, try in.takeByte()) << 4) +
                                (@as(u20, try in.takeByte()) << 12);
                        },
                    }
                },
                .compressed, .treeless => {
                    remaining.* = remaining.subtract(2) orelse return error.EndOfStream;
                    const byte1 = try in.takeByte();
                    const byte2 = try in.takeByte();
                    switch (size_format) {
                        0, 1 => {
                            regenerated_size = (byte0 >> 4) + ((@as(u20, byte1) & 0b00111111) << 4);
                            compressed_size = ((byte1 & 0b11000000) >> 6) + (@as(u18, byte2) << 2);
                        },
                        2 => {
                            remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
                            const byte3 = try in.takeByte();
                            regenerated_size = (byte0 >> 4) + (@as(u20, byte1) << 4) + ((@as(u20, byte2) & 0b00000011) << 12);
                            compressed_size = ((byte2 & 0b11111100) >> 2) + (@as(u18, byte3) << 6);
                        },
                        3 => {
                            remaining.* = remaining.subtract(2) orelse return error.EndOfStream;
                            const byte3 = try in.takeByte();
                            const byte4 = try in.takeByte();
                            regenerated_size = (byte0 >> 4) + (@as(u20, byte1) << 4) + ((@as(u20, byte2) & 0b00111111) << 12);
                            compressed_size = ((byte2 & 0b11000000) >> 6) + (@as(u18, byte3) << 2) + (@as(u18, byte4) << 10);
                        },
                    }
                },
            }
            return .{
                .block_type = block_type,
                .size_format = size_format,
                .regenerated_size = regenerated_size,
                .compressed_size = compressed_size,
            };
        }
    };

    pub const BlockType = enum(u2) {
        raw,
        rle,
        compressed,
        treeless,
    };

    pub const HuffmanTree = struct {
        max_bit_count: u4,
        symbol_count_minus_one: u8,
        nodes: [256]PrefixedSymbol,

        pub const PrefixedSymbol = struct {
            symbol: u8,
            prefix: u16,
            weight: u4,
        };

        pub const Result = union(enum) {
            symbol: u8,
            index: usize,
        };

        pub fn query(self: HuffmanTree, index: usize, prefix: u16) error{HuffmanTreeIncomplete}!Result {
            var node = self.nodes[index];
            const weight = node.weight;
            var i: usize = index;
            while (node.weight == weight) {
                if (node.prefix == prefix) return .{ .symbol = node.symbol };
                if (i == 0) return error.HuffmanTreeIncomplete;
                i -= 1;
                node = self.nodes[i];
            }
            return .{ .index = i };
        }

        pub fn weightToBitCount(weight: u4, max_bit_count: u4) u4 {
            return if (weight == 0) 0 else ((max_bit_count + 1) - weight);
        }

        pub const DecodeError = Reader.Error || error{
            MalformedHuffmanTree,
            MalformedFseTable,
            MalformedAccuracyLog,
            EndOfStream,
            MissingStartBit,
        };

        pub fn decode(in: *Reader, remaining: *Limit) HuffmanTree.DecodeError!HuffmanTree {
            remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
            const header = try in.takeByte();
            if (header < 128) {
                return decodeFse(in, remaining, header);
            } else {
                return decodeDirect(in, remaining, header - 127);
            }
        }

        fn decodeDirect(
            in: *Reader,
            remaining: *Limit,
            encoded_symbol_count: usize,
        ) HuffmanTree.DecodeError!HuffmanTree {
            var weights: [256]u4 = undefined;
            const weights_byte_count = (encoded_symbol_count + 1) / 2;
            remaining.* = remaining.subtract(weights_byte_count) orelse return error.EndOfStream;
            for (0..weights_byte_count) |i| {
                const byte = try in.takeByte();
                weights[2 * i] = @as(u4, @intCast(byte >> 4));
                weights[2 * i + 1] = @as(u4, @intCast(byte & 0xF));
            }
            const symbol_count = encoded_symbol_count + 1;
            return build(&weights, symbol_count);
        }

        fn decodeFse(
            in: *Reader,
            remaining: *Limit,
            compressed_size: usize,
        ) HuffmanTree.DecodeError!HuffmanTree {
            var weights: [256]u4 = undefined;
            remaining.* = remaining.subtract(compressed_size) orelse return error.EndOfStream;
            const compressed_buffer = try in.take(compressed_size);
            var bit_reader: BitReader = .{ .bytes = compressed_buffer };
            var entries: [1 << 6]Table.Fse = undefined;
            const table_size = try Table.decode(&bit_reader, 256, 6, &entries);
            const accuracy_log = std.math.log2_int_ceil(usize, table_size);
            const remaining_buffer = bit_reader.bytes[bit_reader.index..];
            const symbol_count = try assignWeights(remaining_buffer, accuracy_log, &entries, &weights);
            return build(&weights, symbol_count);
        }

        fn assignWeights(
            huff_bits_buffer: []const u8,
            accuracy_log: u16,
            entries: *[1 << 6]Table.Fse,
            weights: *[256]u4,
        ) !usize {
            var huff_bits = try ReverseBitReader.init(huff_bits_buffer);

            var i: usize = 0;
            var even_state: u32 = try huff_bits.readBitsNoEof(u32, accuracy_log);
            var odd_state: u32 = try huff_bits.readBitsNoEof(u32, accuracy_log);

            while (i < 254) {
                const even_data = entries[even_state];
                var read_bits: u16 = 0;
                const even_bits = huff_bits.readBits(u32, even_data.bits, &read_bits) catch unreachable;
                weights[i] = std.math.cast(u4, even_data.symbol) orelse return error.MalformedHuffmanTree;
                i += 1;
                if (read_bits < even_data.bits) {
                    weights[i] = std.math.cast(u4, entries[odd_state].symbol) orelse return error.MalformedHuffmanTree;
                    i += 1;
                    break;
                }
                even_state = even_data.baseline + even_bits;

                read_bits = 0;
                const odd_data = entries[odd_state];
                const odd_bits = huff_bits.readBits(u32, odd_data.bits, &read_bits) catch unreachable;
                weights[i] = std.math.cast(u4, odd_data.symbol) orelse return error.MalformedHuffmanTree;
                i += 1;
                if (read_bits < odd_data.bits) {
                    if (i == 255) return error.MalformedHuffmanTree;
                    weights[i] = std.math.cast(u4, entries[even_state].symbol) orelse return error.MalformedHuffmanTree;
                    i += 1;
                    break;
                }
                odd_state = odd_data.baseline + odd_bits;
            } else return error.MalformedHuffmanTree;

            if (!huff_bits.isEmpty()) {
                return error.MalformedHuffmanTree;
            }

            return i + 1; // 流包含除最后一个以外的所有符号
        }

        fn assignSymbols(weight_sorted_prefixed_symbols: []PrefixedSymbol, weights: [256]u4) usize {
            for (0..weight_sorted_prefixed_symbols.len) |i| {
                weight_sorted_prefixed_symbols[i] = .{
                    .symbol = @as(u8, @intCast(i)),
                    .weight = undefined,
                    .prefix = undefined,
                };
            }

            std.mem.sort(
                PrefixedSymbol,
                weight_sorted_prefixed_symbols,
                weights,
                lessThanByWeight,
            );

            var prefix: u16 = 0;
            var prefixed_symbol_count: usize = 0;
            var sorted_index: usize = 0;
            const symbol_count = weight_sorted_prefixed_symbols.len;
            while (sorted_index < symbol_count) {
                var symbol = weight_sorted_prefixed_symbols[sorted_index].symbol;
                const weight = weights[symbol];
                if (weight == 0) {
                    sorted_index += 1;
                    continue;
                }

                while (sorted_index < symbol_count) : ({
                    sorted_index += 1;
                    prefixed_symbol_count += 1;
                    prefix += 1;
                }) {
                    symbol = weight_sorted_prefixed_symbols[sorted_index].symbol;
                    if (weights[symbol] != weight) {
                        prefix = ((prefix - 1) >> (weights[symbol] - weight)) + 1;
                        break;
                    }
                    weight_sorted_prefixed_symbols[prefixed_symbol_count].symbol = symbol;
                    weight_sorted_prefixed_symbols[prefixed_symbol_count].prefix = prefix;
                    weight_sorted_prefixed_symbols[prefixed_symbol_count].weight = weight;
                }
            }
            return prefixed_symbol_count;
        }

        fn build(weights: *[256]u4, symbol_count: usize) error{MalformedHuffmanTree}!HuffmanTree {
            var weight_power_sum_big: u32 = 0;
            for (weights[0 .. symbol_count - 1]) |value| {
                weight_power_sum_big += (@as(u16, 1) << value) >> 1;
            }
            if (weight_power_sum_big >= 1 << 11) return error.MalformedHuffmanTree;
            const weight_power_sum = @as(u16, @intCast(weight_power_sum_big));

            // 前进到下一个 2 的幂(即使 weight_power_sum 本身已是 2 的幂)
            // TODO: weight_power_sum == 0 是否有效?
            const max_number_of_bits = if (weight_power_sum == 0) 1 else std.math.log2_int(u16, weight_power_sum) + 1;
            const next_power_of_two = @as(u16, 1) << max_number_of_bits;
            weights[symbol_count - 1] = std.math.log2_int(u16, next_power_of_two - weight_power_sum) + 1;

            var weight_sorted_prefixed_symbols: [256]PrefixedSymbol = undefined;
            const prefixed_symbol_count = assignSymbols(weight_sorted_prefixed_symbols[0..symbol_count], weights.*);
            const tree: HuffmanTree = .{
                .max_bit_count = max_number_of_bits,
                .symbol_count_minus_one = @as(u8, @intCast(prefixed_symbol_count - 1)),
                .nodes = weight_sorted_prefixed_symbols,
            };
            return tree;
        }

        fn lessThanByWeight(
            weights: [256]u4,
            lhs: PrefixedSymbol,
            rhs: PrefixedSymbol,
        ) bool {
            // 注意:此函数依赖稳定排序算法;
            //       否则应添加特殊情况:if (weights[lhs] == weights[rhs]) return lhs < rhs;
            //       以处理相同权重。
            return weights[lhs.symbol] < weights[rhs.symbol];
        }
    };

    pub const StreamCount = enum { one, four };
    pub fn streamCount(size_format: u2, block_type: BlockType) StreamCount {
        return switch (block_type) {
            .raw, .rle => .one,
            .compressed, .treeless => if (size_format == 0) .one else .four,
        };
    }

    pub const DecodeError = error{
        /// 头部无效。
        MalformedLiteralsHeader,
        /// 解码错误。
        MalformedLiteralsSection,
        /// 压缩字面量的精度无效。
        MalformedAccuracyLog,
        /// 压缩字面量的 FSE 表无效。
        MalformedFseTable,
        /// 霍夫曼树解码失败。
        MalformedHuffmanTree,
        /// 字节不足以完成此节。
        EndOfStream,
        ReadFailed,
        MissingStartBit,
    };

    pub fn decode(in: *Reader, remaining: *Limit, buffer: []u8) DecodeError!LiteralsSection {
        const header = try Header.decode(in, remaining);
        switch (header.block_type) {
            .raw => {
                if (buffer.len < header.regenerated_size) return error.MalformedLiteralsSection;
                remaining.* = remaining.subtract(header.regenerated_size) orelse return error.EndOfStream;
                try in.readSliceAll(buffer[0..header.regenerated_size]);
                return .{
                    .header = header,
                    .huffman_tree = null,
                    .streams = .{ .one = buffer },
                };
            },
            .rle => {
                remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
                buffer[0] = try in.takeByte();
                return .{
                    .header = header,
                    .huffman_tree = null,
                    .streams = .{ .one = buffer[0..1] },
                };
            },
            .compressed, .treeless => {
                const before_remaining = remaining.*;
                const huffman_tree = if (header.block_type == .compressed)
                    try HuffmanTree.decode(in, remaining)
                else
                    null;
                const huffman_tree_size = @backingInt(before_remaining) - @backingInt(remaining.*);
                const total_streams_size = std.math.sub(usize, header.compressed_size.?, huffman_tree_size) catch
                    return error.MalformedLiteralsSection;
                if (total_streams_size > buffer.len) return error.MalformedLiteralsSection;
                remaining.* = remaining.subtract(total_streams_size) orelse return error.EndOfStream;
                try in.readSliceAll(buffer[0..total_streams_size]);
                const stream_data = buffer[0..total_streams_size];
                const streams = try Streams.decode(header.size_format, stream_data);
                return .{
                    .header = header,
                    .huffman_tree = huffman_tree,
                    .streams = streams,
                };
            },
        }
    }
};

pub const SequencesSection = struct {
    header: Header,
    literals_length_table: Table,
    offset_table: Table,
    match_length_table: Table,

    pub const Header = struct {
        sequence_count: u24,
        match_lengths: Mode,
        offsets: Mode,
        literal_lengths: Mode,

        pub const Mode = enum(u2) {
            predefined,
            rle,
            fse,
            repeat,
        };

        pub const DecodeError = error{
            ReservedBitSet,
            EndOfStream,
            ReadFailed,
        };

        pub fn decode(in: *Reader, remaining: *Limit) DecodeError!Header {
            var sequence_count: u24 = undefined;

            remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
            const byte0 = try in.takeByte();
            if (byte0 == 0) {
                return .{
                    .sequence_count = 0,
                    .offsets = undefined,
                    .match_lengths = undefined,
                    .literal_lengths = undefined,
                };
            } else if (byte0 < 128) {
                remaining.* = remaining.subtract(1) orelse return error.EndOfStream;
                sequence_count = byte0;
            } else if (byte0 < 255) {
                remaining.* = remaining.subtract(2) orelse return error.EndOfStream;
                sequence_count = (@as(u24, (byte0 - 128)) << 8) + try in.takeByte();
            } else {
                remaining.* = remaining.subtract(3) orelse return error.EndOfStream;
                sequence_count = (try in.takeByte()) + (@as(u24, try in.takeByte()) << 8) + 0x7F00;
            }

            const compression_modes = try in.takeByte();

            const matches_mode: Header.Mode = @fromBackingInt(@intCast((compression_modes & 0b00001100) >> 2));
            const offsets_mode: Header.Mode = @fromBackingInt(@intCast((compression_modes & 0b00110000) >> 4));
            const literal_mode: Header.Mode = @fromBackingInt(@intCast((compression_modes & 0b11000000) >> 6));
            if (compression_modes & 0b11 != 0) return error.ReservedBitSet;

            return .{
                .sequence_count = sequence_count,
                .offsets = offsets_mode,
                .match_lengths = matches_mode,
                .literal_lengths = literal_mode,
            };
        }
    };
};

pub const Table = union(enum) {
    fse: []const Fse,
    rle: u8,

    pub const Fse = struct {
        symbol: u8,
        baseline: u16,
        bits: u8,
    };

    pub fn decode(
        bit_reader: *BitReader,
        expected_symbol_count: usize,
        max_accuracy_log: u4,
        entries: []Table.Fse,
    ) !usize {
        const accuracy_log_biased = try bit_reader.readBitsNoEof(u4, 4);
        if (accuracy_log_biased > max_accuracy_log -| 5) return error.MalformedAccuracyLog;
        const accuracy_log = accuracy_log_biased + 5;

        var values: [256]u16 = undefined;
        var value_count: usize = 0;

        const total_probability = @as(u16, 1) << accuracy_log;
        var accumulated_probability: u16 = 0;

        while (accumulated_probability < total_probability) {
            // 警告:RFC 措辞不清,似乎表示此处应使用 std.math.log2_int_ceil,
            //          但当剩余概率数加 1 为 2 的幂时,所需最大位数还要增加 1。
            const max_bits = std.math.log2_int(u16, total_probability - accumulated_probability + 1) + 1;
            const small = try bit_reader.readBitsNoEof(u16, max_bits - 1);

            const cutoff = (@as(u16, 1) << max_bits) - 1 - (total_probability - accumulated_probability + 1);

            const value = if (small < cutoff)
                small
            else value: {
                const value_read = small + (try bit_reader.readBitsNoEof(u16, 1) << (max_bits - 1));
                break :value if (value_read < @as(u16, 1) << (max_bits - 1))
                    value_read
                else
                    value_read - cutoff;
            };

            accumulated_probability += if (value != 0) value - 1 else 1;

            values[value_count] = value;
            value_count += 1;

            if (value == 1) {
                while (true) {
                    const repeat_flag = try bit_reader.readBitsNoEof(u2, 2);
                    if (repeat_flag + value_count > 256) return error.MalformedFseTable;
                    for (0..repeat_flag) |_| {
                        values[value_count] = 1;
                        value_count += 1;
                    }
                    if (repeat_flag < 3) break;
                }
            }
            if (value_count == 256) break;
        }
        bit_reader.alignToByte();

        if (value_count < 2) return error.MalformedFseTable;
        if (accumulated_probability != total_probability) return error.MalformedFseTable;
        if (value_count > expected_symbol_count) return error.MalformedFseTable;

        const table_size = total_probability;

        try build(values[0..value_count], entries[0..table_size]);
        return table_size;
    }

    pub fn build(values: []const u16, entries: []Table.Fse) !void {
        const total_probability = @as(u16, @intCast(entries.len));
        const accuracy_log = std.math.log2_int(u16, total_probability);
        assert(total_probability <= 1 << 9);

        var less_than_one_count: usize = 0;
        for (values, 0..) |value, i| {
            if (value == 0) {
                entries[entries.len - 1 - less_than_one_count] = Table.Fse{
                    .symbol = @as(u8, @intCast(i)),
                    .baseline = 0,
                    .bits = accuracy_log,
                };
                less_than_one_count += 1;
            }
        }

        var position: usize = 0;
        var temp_states: [1 << 9]u16 = undefined;
        for (values, 0..) |value, symbol| {
            if (value == 0 or value == 1) continue;
            const probability = value - 1;

            const state_share_dividend = std.math.ceilPowerOfTwo(u16, probability) catch
                return error.MalformedFseTable;
            const share_size = @divExact(total_probability, state_share_dividend);
            const double_state_count = state_share_dividend - probability;
            const single_state_count = probability - double_state_count;
            const share_size_log = std.math.log2_int(u16, share_size);

            for (0..probability) |i| {
                temp_states[i] = @as(u16, @intCast(position));
                position += (entries.len >> 1) + (entries.len >> 3) + 3;
                position &= entries.len - 1;
                while (position >= entries.len - less_than_one_count) {
                    position += (entries.len >> 1) + (entries.len >> 3) + 3;
                    position &= entries.len - 1;
                }
            }
            std.mem.sort(u16, temp_states[0..probability], {}, std.sort.asc(u16));
            for (0..probability) |i| {
                entries[temp_states[i]] = if (i < double_state_count) Table.Fse{
                    .symbol = @as(u8, @intCast(symbol)),
                    .bits = share_size_log + 1,
                    .baseline = single_state_count * share_size + @as(u16, @intCast(i)) * 2 * share_size,
                } else Table.Fse{
                    .symbol = @as(u8, @intCast(symbol)),
                    .bits = share_size_log,
                    .baseline = (@as(u16, @intCast(i)) - double_state_count) * share_size,
                };
            }
        }
    }

    test build {
        const literals_length_default_values = [36]u16{
            5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2,
            0, 0, 0, 0,
        };

        const match_lengths_default_values = [53]u16{
            2, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0,
            0, 0, 0, 0, 0,
        };

        const offset_codes_default_values = [29]u16{
            2, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0,
        };

        var entries: [64]Table.Fse = undefined;
        try build(&literals_length_default_values, &entries);
        try std.testing.expectEqualSlices(Table.Fse, Table.predefined_literal.fse, &entries);

        try build(&match_lengths_default_values, &entries);
        try std.testing.expectEqualSlices(Table.Fse, Table.predefined_match.fse, &entries);

        try build(&offset_codes_default_values, entries[0..32]);
        try std.testing.expectEqualSlices(Table.Fse, Table.predefined_offset.fse, entries[0..32]);
    }

    pub const predefined_literal: Table = .{
        .fse = &[64]Table.Fse{
            .{ .symbol = 0, .bits = 4, .baseline = 0 },
            .{ .symbol = 0, .bits = 4, .baseline = 16 },
            .{ .symbol = 1, .bits = 5, .baseline = 32 },
            .{ .symbol = 3, .bits = 5, .baseline = 0 },
            .{ .symbol = 4, .bits = 5, .baseline = 0 },
            .{ .symbol = 6, .bits = 5, .baseline = 0 },
            .{ .symbol = 7, .bits = 5, .baseline = 0 },
            .{ .symbol = 9, .bits = 5, .baseline = 0 },
            .{ .symbol = 10, .bits = 5, .baseline = 0 },
            .{ .symbol = 12, .bits = 5, .baseline = 0 },
            .{ .symbol = 14, .bits = 6, .baseline = 0 },
            .{ .symbol = 16, .bits = 5, .baseline = 0 },
            .{ .symbol = 18, .bits = 5, .baseline = 0 },
            .{ .symbol = 19, .bits = 5, .baseline = 0 },
            .{ .symbol = 21, .bits = 5, .baseline = 0 },
            .{ .symbol = 22, .bits = 5, .baseline = 0 },
            .{ .symbol = 24, .bits = 5, .baseline = 0 },
            .{ .symbol = 25, .bits = 5, .baseline = 32 },
            .{ .symbol = 26, .bits = 5, .baseline = 0 },
            .{ .symbol = 27, .bits = 6, .baseline = 0 },
            .{ .symbol = 29, .bits = 6, .baseline = 0 },
            .{ .symbol = 31, .bits = 6, .baseline = 0 },
            .{ .symbol = 0, .bits = 4, .baseline = 32 },
            .{ .symbol = 1, .bits = 4, .baseline = 0 },
            .{ .symbol = 2, .bits = 5, .baseline = 0 },
            .{ .symbol = 4, .bits = 5, .baseline = 32 },
            .{ .symbol = 5, .bits = 5, .baseline = 0 },
            .{ .symbol = 7, .bits = 5, .baseline = 32 },
            .{ .symbol = 8, .bits = 5, .baseline = 0 },
            .{ .symbol = 10, .bits = 5, .baseline = 32 },
            .{ .symbol = 11, .bits = 5, .baseline = 0 },
            .{ .symbol = 13, .bits = 6, .baseline = 0 },
            .{ .symbol = 16, .bits = 5, .baseline = 32 },
            .{ .symbol = 17, .bits = 5, .baseline = 0 },
            .{ .symbol = 19, .bits = 5, .baseline = 32 },
            .{ .symbol = 20, .bits = 5, .baseline = 0 },
            .{ .symbol = 22, .bits = 5, .baseline = 32 },
            .{ .symbol = 23, .bits = 5, .baseline = 0 },
            .{ .symbol = 25, .bits = 4, .baseline = 0 },
            .{ .symbol = 25, .bits = 4, .baseline = 16 },
            .{ .symbol = 26, .bits = 5, .baseline = 32 },
            .{ .symbol = 28, .bits = 6, .baseline = 0 },
            .{ .symbol = 30, .bits = 6, .baseline = 0 },
            .{ .symbol = 0, .bits = 4, .baseline = 48 },
            .{ .symbol = 1, .bits = 4, .baseline = 16 },
            .{ .symbol = 2, .bits = 5, .baseline = 32 },
            .{ .symbol = 3, .bits = 5, .baseline = 32 },
            .{ .symbol = 5, .bits = 5, .baseline = 32 },
            .{ .symbol = 6, .bits = 5, .baseline = 32 },
            .{ .symbol = 8, .bits = 5, .baseline = 32 },
            .{ .symbol = 9, .bits = 5, .baseline = 32 },
            .{ .symbol = 11, .bits = 5, .baseline = 32 },
            .{ .symbol = 12, .bits = 5, .baseline = 32 },
            .{ .symbol = 15, .bits = 6, .baseline = 0 },
            .{ .symbol = 17, .bits = 5, .baseline = 32 },
            .{ .symbol = 18, .bits = 5, .baseline = 32 },
            .{ .symbol = 20, .bits = 5, .baseline = 32 },
            .{ .symbol = 21, .bits = 5, .baseline = 32 },
            .{ .symbol = 23, .bits = 5, .baseline = 32 },
            .{ .symbol = 24, .bits = 5, .baseline = 32 },
            .{ .symbol = 35, .bits = 6, .baseline = 0 },
            .{ .symbol = 34, .bits = 6, .baseline = 0 },
            .{ .symbol = 33, .bits = 6, .baseline = 0 },
            .{ .symbol = 32, .bits = 6, .baseline = 0 },
        },
    };

    pub const predefined_match: Table = .{
        .fse = &[64]Table.Fse{
            .{ .symbol = 0, .bits = 6, .baseline = 0 },
            .{ .symbol = 1, .bits = 4, .baseline = 0 },
            .{ .symbol = 2, .bits = 5, .baseline = 32 },
            .{ .symbol = 3, .bits = 5, .baseline = 0 },
            .{ .symbol = 5, .bits = 5, .baseline = 0 },
            .{ .symbol = 6, .bits = 5, .baseline = 0 },
            .{ .symbol = 8, .bits = 5, .baseline = 0 },
            .{ .symbol = 10, .bits = 6, .baseline = 0 },
            .{ .symbol = 13, .bits = 6, .baseline = 0 },
            .{ .symbol = 16, .bits = 6, .baseline = 0 },
            .{ .symbol = 19, .bits = 6, .baseline = 0 },
            .{ .symbol = 22, .bits = 6, .baseline = 0 },
            .{ .symbol = 25, .bits = 6, .baseline = 0 },
            .{ .symbol = 28, .bits = 6, .baseline = 0 },
            .{ .symbol = 31, .bits = 6, .baseline = 0 },
            .{ .symbol = 33, .bits = 6, .baseline = 0 },
            .{ .symbol = 35, .bits = 6, .baseline = 0 },
            .{ .symbol = 37, .bits = 6, .baseline = 0 },
            .{ .symbol = 39, .bits = 6, .baseline = 0 },
            .{ .symbol = 41, .bits = 6, .baseline = 0 },
            .{ .symbol = 43, .bits = 6, .baseline = 0 },
            .{ .symbol = 45, .bits = 6, .baseline = 0 },
            .{ .symbol = 1, .bits = 4, .baseline = 16 },
            .{ .symbol = 2, .bits = 4, .baseline = 0 },
            .{ .symbol = 3, .bits = 5, .baseline = 32 },
            .{ .symbol = 4, .bits = 5, .baseline = 0 },
            .{ .symbol = 6, .bits = 5, .baseline = 32 },
            .{ .symbol = 7, .bits = 5, .baseline = 0 },
            .{ .symbol = 9, .bits = 6, .baseline = 0 },
            .{ .symbol = 12, .bits = 6, .baseline = 0 },
            .{ .symbol = 15, .bits = 6, .baseline = 0 },
            .{ .symbol = 18, .bits = 6, .baseline = 0 },
            .{ .symbol = 21, .bits = 6, .baseline = 0 },
            .{ .symbol = 24, .bits = 6, .baseline = 0 },
            .{ .symbol = 27, .bits = 6, .baseline = 0 },
            .{ .symbol = 30, .bits = 6, .baseline = 0 },
            .{ .symbol = 32, .bits = 6, .baseline = 0 },
            .{ .symbol = 34, .bits = 6, .baseline = 0 },
            .{ .symbol = 36, .bits = 6, .baseline = 0 },
            .{ .symbol = 38, .bits = 6, .baseline = 0 },
            .{ .symbol = 40, .bits = 6, .baseline = 0 },
            .{ .symbol = 42, .bits = 6, .baseline = 0 },
            .{ .symbol = 44, .bits = 6, .baseline = 0 },
            .{ .symbol = 1, .bits = 4, .baseline = 32 },
            .{ .symbol = 1, .bits = 4, .baseline = 48 },
            .{ .symbol = 2, .bits = 4, .baseline = 16 },
            .{ .symbol = 4, .bits = 5, .baseline = 32 },
            .{ .symbol = 5, .bits = 5, .baseline = 32 },
            .{ .symbol = 7, .bits = 5, .baseline = 32 },
            .{ .symbol = 8, .bits = 5, .baseline = 32 },
            .{ .symbol = 11, .bits = 6, .baseline = 0 },
            .{ .symbol = 14, .bits = 6, .baseline = 0 },
            .{ .symbol = 17, .bits = 6, .baseline = 0 },
            .{ .symbol = 20, .bits = 6, .baseline = 0 },
            .{ .symbol = 23, .bits = 6, .baseline = 0 },
            .{ .symbol = 26, .bits = 6, .baseline = 0 },
            .{ .symbol = 29, .bits = 6, .baseline = 0 },
            .{ .symbol = 52, .bits = 6, .baseline = 0 },
            .{ .symbol = 51, .bits = 6, .baseline = 0 },
            .{ .symbol = 50, .bits = 6, .baseline = 0 },
            .{ .symbol = 49, .bits = 6, .baseline = 0 },
            .{ .symbol = 48, .bits = 6, .baseline = 0 },
            .{ .symbol = 47, .bits = 6, .baseline = 0 },
            .{ .symbol = 46, .bits = 6, .baseline = 0 },
        },
    };

    pub const predefined_offset: Table = .{
        .fse = &[32]Table.Fse{
            .{ .symbol = 0, .bits = 5, .baseline = 0 },
            .{ .symbol = 6, .bits = 4, .baseline = 0 },
            .{ .symbol = 9, .bits = 5, .baseline = 0 },
            .{ .symbol = 15, .bits = 5, .baseline = 0 },
            .{ .symbol = 21, .bits = 5, .baseline = 0 },
            .{ .symbol = 3, .bits = 5, .baseline = 0 },
            .{ .symbol = 7, .bits = 4, .baseline = 0 },
            .{ .symbol = 12, .bits = 5, .baseline = 0 },
            .{ .symbol = 18, .bits = 5, .baseline = 0 },
            .{ .symbol = 23, .bits = 5, .baseline = 0 },
            .{ .symbol = 5, .bits = 5, .baseline = 0 },
            .{ .symbol = 8, .bits = 4, .baseline = 0 },
            .{ .symbol = 14, .bits = 5, .baseline = 0 },
            .{ .symbol = 20, .bits = 5, .baseline = 0 },
            .{ .symbol = 2, .bits = 5, .baseline = 0 },
            .{ .symbol = 7, .bits = 4, .baseline = 16 },
            .{ .symbol = 11, .bits = 5, .baseline = 0 },
            .{ .symbol = 17, .bits = 5, .baseline = 0 },
            .{ .symbol = 22, .bits = 5, .baseline = 0 },
            .{ .symbol = 4, .bits = 5, .baseline = 0 },
            .{ .symbol = 8, .bits = 4, .baseline = 16 },
            .{ .symbol = 13, .bits = 5, .baseline = 0 },
            .{ .symbol = 19, .bits = 5, .baseline = 0 },
            .{ .symbol = 1, .bits = 5, .baseline = 0 },
            .{ .symbol = 6, .bits = 4, .baseline = 16 },
            .{ .symbol = 10, .bits = 5, .baseline = 0 },
            .{ .symbol = 16, .bits = 5, .baseline = 0 },
            .{ .symbol = 28, .bits = 5, .baseline = 0 },
            .{ .symbol = 27, .bits = 5, .baseline = 0 },
            .{ .symbol = 26, .bits = 5, .baseline = 0 },
            .{ .symbol = 25, .bits = 5, .baseline = 0 },
            .{ .symbol = 24, .bits = 5, .baseline = 0 },
        },
    };
};

const low_bit_mask = [9]u8{
    0b00000000,
    0b00000001,
    0b00000011,
    0b00000111,
    0b00001111,
    0b00011111,
    0b00111111,
    0b01111111,
    0b11111111,
};

fn Bits(comptime T: type) type {
    return struct { T, u16 };
}

/// 用于读取编码 FSE 压缩数据时使用的反向位流。
const ReverseBitReader = struct {
    bytes: []const u8,
    remaining: usize,
    bits: u8,
    count: u4,

    fn init(bytes: []const u8) error{MissingStartBit}!ReverseBitReader {
        var result: ReverseBitReader = .{
            .bytes = bytes,
            .remaining = bytes.len,
            .bits = 0,
            .count = 0,
        };
        if (bytes.len == 0) return result;
        for (0..8) |_| if (0 != (result.readBitsNoEof(u1, 1) catch unreachable)) return result;
        return error.MissingStartBit;
    }

    fn initBits(comptime T: type, out: anytype, num: u16) Bits(T) {
        const UT = @Int(.unsigned, @bitSizeOf(T));
        return .{
            @bitCast(@as(UT, @intCast(out))),
            num,
        };
    }

    fn readBitsNoEof(self: *ReverseBitReader, comptime T: type, num: u16) error{EndOfStream}!T {
        const b, const c = try self.readBitsTuple(T, num);
        if (c < num) return error.EndOfStream;
        return b;
    }

    fn readBits(self: *ReverseBitReader, comptime T: type, num: u16, out_bits: *u16) !T {
        const b, const c = try self.readBitsTuple(T, num);
        out_bits.* = c;
        return b;
    }

    fn readBitsTuple(self: *ReverseBitReader, comptime T: type, num: u16) !Bits(T) {
        const UT = @Int(.unsigned, @bitSizeOf(T));
        const U = if (@bitSizeOf(T) < 8) u8 else UT;

        if (num <= self.count) return initBits(T, self.removeBits(@intCast(num)), num);

        var out_count: u16 = self.count;
        var out: U = self.removeBits(self.count);

        const full_bytes_left = (num - out_count) / 8;

        for (0..full_bytes_left) |_| {
            const byte = takeByte(self) catch |err| switch (err) {
                error.EndOfStream => return initBits(T, out, out_count),
            };
            if (U == u8) out = 0 else out <<= 8;
            out |= byte;
            out_count += 8;
        }

        const bits_left = num - out_count;
        const keep = 8 - bits_left;

        if (bits_left == 0) return initBits(T, out, out_count);

        const final_byte = takeByte(self) catch |err| switch (err) {
            error.EndOfStream => return initBits(T, out, out_count),
        };

        out <<= @intCast(bits_left);
        out |= final_byte >> @intCast(keep);
        self.bits = final_byte & low_bit_mask[keep];

        self.count = @intCast(keep);
        return initBits(T, out, num);
    }

    fn takeByte(rbr: *ReverseBitReader) error{EndOfStream}!u8 {
        if (rbr.remaining == 0) return error.EndOfStream;
        rbr.remaining -= 1;
        return rbr.bytes[rbr.remaining];
    }

    fn isEmpty(self: *const ReverseBitReader) bool {
        return self.remaining == 0 and self.count == 0;
    }

    fn removeBits(self: *ReverseBitReader, num: u4) u8 {
        if (num == 8) {
            self.count = 0;
            return self.bits;
        }

        const keep = self.count - num;
        const bits = self.bits >> @intCast(keep);
        self.bits &= low_bit_mask[keep];

        self.count = keep;
        return bits;
    }
};

const BitReader = struct {
    bytes: []const u8,
    index: usize = 0,
    bits: u8 = 0,
    count: u4 = 0,

    fn initBits(comptime T: type, out: anytype, num: u16) Bits(T) {
        const UT = @Int(.unsigned, @bitSizeOf(T));
        return .{
            @bitCast(@as(UT, @intCast(out))),
            num,
        };
    }

    fn readBitsNoEof(self: *@This(), comptime T: type, num: u16) !T {
        const b, const c = try self.readBitsTuple(T, num);
        if (c < num) return error.EndOfStream;
        return b;
    }

    fn readBits(self: *@This(), comptime T: type, num: u16, out_bits: *u16) !T {
        const b, const c = try self.readBitsTuple(T, num);
        out_bits.* = c;
        return b;
    }

    fn readBitsTuple(self: *@This(), comptime T: type, num: u16) !Bits(T) {
        const UT = @Int(.unsigned, @bitSizeOf(T));
        const U = if (@bitSizeOf(T) < 8) u8 else UT;

        if (num <= self.count) return initBits(T, self.removeBits(@intCast(num)), num);

        var out_count: u16 = self.count;
        var out: U = self.removeBits(self.count);

        const full_bytes_left = (num - out_count) / 8;

        for (0..full_bytes_left) |_| {
            const byte = takeByte(self) catch |err| switch (err) {
                error.EndOfStream => return initBits(T, out, out_count),
            };

            const pos = @as(U, byte) << @intCast(out_count);
            out |= pos;
            out_count += 8;
        }

        const bits_left = num - out_count;
        const keep = 8 - bits_left;

        if (bits_left == 0) return initBits(T, out, out_count);

        const final_byte = takeByte(self) catch |err| switch (err) {
            error.EndOfStream => return initBits(T, out, out_count),
        };

        const pos = @as(U, final_byte & low_bit_mask[bits_left]) << @intCast(out_count);
        out |= pos;
        self.bits = final_byte >> @intCast(bits_left);

        self.count = @intCast(keep);
        return initBits(T, out, num);
    }

    fn takeByte(br: *BitReader) error{EndOfStream}!u8 {
        if (br.bytes.len - br.index == 0) return error.EndOfStream;
        const result = br.bytes[br.index];
        br.index += 1;
        return result;
    }

    fn removeBits(self: *@This(), num: u4) u8 {
        if (num == 8) {
            self.count = 0;
            return self.bits;
        }

        const keep = self.count - num;
        const bits = self.bits & low_bit_mask[num];
        self.bits >>= @intCast(num);
        self.count = keep;
        return bits;
    }

    fn alignToByte(self: *@This()) void {
        self.bits = 0;
        self.count = 0;
    }
};

test {
    _ = Table;
}