Lean 中的格式模型
格式模型描述压缩后的字节怎样决定未压缩的字节。它没有堆,也没有指针。 它是一份有待细化的规格,不是流 API 的实现。 规则见格式指南,调用、缓冲区和返回值见 API 模型。 哪些目标已完成,见进度。
下面的定义都在命名空间 ZlibF.Spec 中,
只有局部的记号关系在 ZlibF.Spec.Token 中。
模型的各部分
| 内容 | Lean 源文件 |
|---|---|
数值读取函数、大端和小端的字节编码。字节到位的顺序(byteBits、bytesToBits)在 Common/Bits.lean 中 |
Bits.lean |
| 逐字节的 Adler-32 和 CRC-32、更新函数和追加定律 | Checksum.lean |
| 规范码、被接受的长度集合、固定码、长度表和距离表 | Huffman.lean |
| 符号关系和块关系、裸流的前缀关系和精确流关系 | Deflate.lean |
| zlib 和 gzip 的头部、尾部和精确流关系 | Wrapper.lean |
| 单个记号的解码与拒绝,以及把它们与块语法联系起来的义务 | Token.lean |
| 接受和拒绝的具体例子 | Examples.lean |
从字节到输出
flowchart TD
B["bytesToBits:字节转成位"] --> K["Blocks:块头与块体"]
K --> S["Body.stored:对齐的字节"]
K --> F["Body.fixed:固定码"]
K --> D["Body.dynamic:长度与码"]
D --> C["CodeLens:展开码长符号"]
F --> Y["Symbols:字面量、复制、结束"]
D --> Y
S --> P["Deflate.Prefix:末尾填充与尾随字节"]
Y --> P
P --> R["Deflate.Decodes:尾随部分为空"]
P --> Z["Zlib.Decodes:Adler-32 尾部"]
P --> G["Gzip.Decodes:CRC-32 与长度尾部"]
readBits、readBytes 和 decodeSym 这类读取函数要么返回 none,要么返回一个值连同剩下的位。
关系的构造子要求相应的读取等式成立。
无效的块类型、保留的长度符号或距离符号,都没有构造子。
这些关系共用同一组参数。dict 是预置字典,h 是到这一点为止已经产生的输出,不含字典。
inp 是尚未读取的位序列,rest 是关系结束时它剩下的部分。
out 是那时的全部输出:h 后接新产生的字节。
L 和 D 分别给出每个字面量/长度符号和每个距离符号的码长,以位计。
Symbols L D dict h inp rest out 从历史 h 开始,使用字面量/长度码长 L 和距离码长 D,
到块结束符号为止。它把 inp 消费到只剩 rest,留下输出 out。
copyBack 每复制一个字节就先把它追加上去,再读下一个,
所以自相重叠的匹配具有通常的逐字节含义。
Blocks dict h inp rest out 把块体一个接一个组合起来,直到一个 BFINAL = 1 的块。
块语法使用的位来自整数个输入字节。在这个入口条件下,inp.length % 8 就是到下一个字节边界之前还剩的位数;
存储块的块体丢掉这么多位。例如,一个存储块的三个块头位是某个字节的头三位时,
这个字节还剩五位;块体丢掉它们,从下一个字节读 LEN。
公开的格式关系的区别,在于它们对最后一个块之后的要求:
| 关系 | 含义 |
|---|---|
Deflate.Prefix dict stream tail out |
从 stream 的开头解码各块;忽略最后一个字节的填充;要求余下的字节等于 tail |
Deflate.Decodes dict stream out |
同一个关系,取 tail = [] |
Zlib.Decodes dict stream out |
恰好一个 zlib 流,带有经过检查的头部、可选的字典 ID 和 Adler-32 尾部 |
Gzip.Decodes stream out |
恰好一个 gzip 成员,带有可选的头部 CRC 和 CRC-32/长度尾部 |
两种封装使用 Deflate.Prefix,把必须出现的尾部字节作为它的 tail。
它们描述的仍然是精确的流:尾部之后的字节被排除在外。
关于 Z_STREAM_END 之后剩余输入的 API 定理,需要另外一条关于已消费前缀的命题。
规则对照
F-* 规则在格式指南中定义。
本表指出每条规则对应的形式化定义,但不对实现的正确性作任何断言。
| 规则 | 定义或义务 |
|---|---|
F-bit-order |
byteBits、bytesToBits、readBits、natToBitsMSB |
F-block-type-3 |
Body 没有类型 3 的构造子 |
F-stored-complement |
Body.stored:nlen = 65535 - len |
F-code-fits |
count、codeStart、codeOf、Fits |
F-code-complete |
Complete、CodeKind、Acceptable |
F-fixed-lengths |
fixedLitLens、fixedDistLens、Body.fixed;Symbols.copy 限制长度符号和距离符号 |
F-dynamic-limits |
DynamicCountsOK,是 Body.dynamic 的要求 |
F-dynamic-repeat |
CodeLens.rep16、.rep17、.rep18;关于前一项和总项数的前提 |
F-dynamic-eob |
HasEndOfBlock,是 Body.dynamic 的要求 |
F-dynamic-valid |
Acceptable .codeLength、.litLen、.dist,是 Body.dynamic 的要求 |
| 动态块头的顺序 | Body.dynamic、clOrder、readCodeLenLens |
F-length-table、F-length-284 |
lengthBases、lengthExtras、Symbols.copy;基值 227 加额外值 31 仍是 258 |
F-distance-table |
distBases、distExtras、Symbols.copy |
F-match-copy |
copyBack |
F-distance-bound |
Symbols.copy 要求距离至多为 (dict ++ h).length |
| 块的顺序与最后一块 | Blocks.more、Blocks.last |
F-zlib-header |
Zlib.HeaderOK、Zlib.windowSize、Zlib.Decodes |
F-zlib-check |
Zlib.Decodes 要求尾随部分为 be32 (adler32 out).toNat |
| gzip 头部 | Gzip.header,以及 Gzip.Decodes 中对头部的约束 |
F-gzip-check |
Gzip.Decodes 要求尾随部分为 le32 (crc32 out).toNat ++ le32 (out.length % 2^32) |
F-adler-incremental |
adler32Update、adler32Update_append |
F-crc-incremental |
crc32Update、crc32Update_append |
F-deflate-valid |
Deflate.Valid、Zlib.Valid、Zlib.ValidWith、Gzip.Valid |
F-deflate-matches |
压缩器的义务;格式语法中没有额外的限制 |
F-deflate-flush |
流调用序列的义务;一次完成的刷新不是一个完整的最终流 |
各个 Valid 谓词把 Decodes 的重点反过来:压缩后的那个参数必须解码成所给的输入。
它们不指定唯一的一种编码。Zlib.ValidWith 带有预置字典;表中其他的 Valid 谓词不用字典。
模型的选择与边界
历史与小窗口。 Symbols.copy 使用完整的历史 dict ++ h,而不是一个显式的“保存的窗口”状态。
距离表把引用限制在 32768 以内。zlib 头的窗口字段限制初始字典取多长的后缀,
但没有给 Symbols.copy 增加关于距离的前提。
默认的解码可以使用本次调用的输出中超出较小的保存窗口的部分,
而之后的调用可能已经没有这些字节。C 另有一项单独的 INFLATE_STRICT 检查。
对所有配置窗口和输出缓冲区边界的细化尚未由证明确认。
单凭声明式的关系,不能确立每一种切分在运行时都被接受。
字典。 有 FDICT 时,Zlib.Decodes dict 检查所提供的整个字典的 Adler-32,
但只把它最后的 Zlib.windowSize cmf 个字节传给 DEFLATE 关系。
没有 FDICT 时,它传 [],忽略 dict。Adler-32 为 1 的字典可以是空的。
裸流的 Deflate.Decodes 直接取它的字典作为历史。gzip 从空历史开始。
表的接受。 Acceptable 对三种码都允许全零的长度集合。这样的集合解不出任何符号。
只用到一个长度为 1 的符号的集合,只对字面量/长度码和距离码允许。
HasEndOfBlock 另外排除空的动态字面量/长度码。
表被接受也好,局部的一个记号解码成功也好,都不蕴含整个块合法。
填充。 存储块的对齐和最后一个字节的填充丢掉一些位,不要求它们为零。
多出来的完整字节由显式的 tail 处理,不算填充。
gzip 元数据。 Gzip.Decodes 要求 MTIME 是四个字节、保留标志位为零、
extra 字段的长度小于 2^16,以及所取的名称和注释中不含零字节。
除此之外,FTEXT、MTIME、XFL 和 OS 不受约束。
标志未置位的可选字段,其见证不贡献任何字节;空的见证就能满足它们的约束。
一个关系覆盖一个成员,不是整个拼接而成的 gzip 文件。
局部解码。 Token.Step 描述一个字面量、一个匹配或一个块结束,不假设后面的输入合法。
Token.Rejected 描述无法挽回的情况:无效的码,或取不到的历史。
目标 step_composes_symbols、symbols_exposes_step 和 rejected_has_no_symbols
把这些局部关系与原来的 Symbols 语法联系起来。
这条边界防止把“后面的输入将来能合法地补全”当作假设,用来为 API 调用已经返回的输出辩护。
哪些内容不属于格式关系
| 事项 | 规格的边界 |
|---|---|
错误码、诊断字符串、Z_NEED_DICT 和字典调用的顺序 |
Inflate API |
| 缓冲区大小、不完整的输入、封装的自动检测、位预置和恢复 | 流 API和 API 模型 |
| 压缩时匹配的选择、刷新的完成和输出上界 | Deflate API |
| 拼接的成员、透明读取和文件错误 | Gzip 文件 API |
| 校验和组合的各个入口 | 校验和 API |
解码表的分配和 ENOUGH 容量上界 |
表的证明指南 |
| 翻译后的实现的内存安全、所有权和终止 | 安全性和证明方法 |
模型附有具体的正面例子和反面例子
(Examples.lean)。
这些例子的证明使用内核求值,以及关系的构造子或反演。
这些例子有助于审查定义;它们不能确立定义与 RFC 的每一种情况相符,也不能确立定义与翻译后的实现相符。
差分测试同样只是忠实性的证据,不是证明。
关于实现的哪些目标已完成,见进度。