数据格式
DEFLATE 描述压缩后的字节。zlib 格式和 gzip 格式在这些字节外面加上头部和校验和。
本指南解释 inflate 必须解读、deflate 必须产生的数据。
本页陈述的是义务,并不声称实现满足这些义务。
哪些目标已完成,见进度。
先读分层和位序,再读块和符号的规则。讲封装的两节解释字典和校验和。 模型参考把这些规则对应到 Lean。 缓冲区管理、返回码和合法的调用序列属于流 API。
格式的依据是:DEFLATE 的 RFC 1951、
zlib 的 RFC 1950 和
gzip 的 RFC 1952。
下面的规则把 zlib 接受的变体和 zlib 加的限制都明确写出。
F-* 名称标识规格和证明文档用到的各项义务。
分层与流的边界
flowchart LR
ZH["zlib 头部<br/>可选的字典 ID"] --> ZD["DEFLATE 块"] --> ZT["Adler-32 尾部"]
GH["gzip 头部<br/>可选字段"] --> GD["DEFLATE 块"] --> GT["CRC-32 与长度尾部"]
RD["裸 DEFLATE 块"]
裸 DEFLATE 没有封装的校验和,也没有字典标识。一个 zlib 流有一个 DEFLATE 载荷。
一个 gzip 成员有一个 DEFLATE 载荷;一个 gzip 文件可以由多个成员拼接而成。
windowBits 选择 API 读写哪一层。
完整的流在最后一个块及其封装尾部(如果有)之后结束。
最后一个 DEFLATE 字节中没有用到的位可以是任意值。多出来的字节是另外的尾随部分。
精确流关系要求尾随部分为空;前缀关系则把它记录下来。
一次 inflate 调用到达 Z_STREAM_END 时,调用者的缓冲区里可以还有字节。
这并不使那些字节成为已完成的流的一部分。
位与块
位从每个字节的最低有效位开始向上依次放入。普通的数值字段(包括额外位的值)先放最低有效位。 Huffman 码占用同一串字节内的位位置,但先放码字的最高有效位。
例如,值为 6(二进制 110)的三位普通字段,发送的位依次是 0、1、1:最低有效位在前。
码字的各位为 110 的 Huffman 码,发送的位依次是 1、1、0:码字的第一位在前。
两者按同样的顺序占用字节中的位位置;不同的只是读回数值的方式。
F-bit-order:解码器把字节追加到位缓冲区的高端,从低端消费位。
要得到一个 l 位 Huffman 码的规范数值,须把缓冲区接下来的 l 个低位反转。
这种反转只用于 Huffman 码,不用于普通字段。
每个块以一个 BFINAL 位和一个两位的数 BTYPE 开始。BFINAL = 1 标记最后一个块。
否则后面紧跟另一个块;块的边界不必是字节边界。
BTYPE |
块体 |
|---|---|
| 0 | 存储的字节 |
| 1 | 用固定 Huffman 码编码的符号 |
| 2 | 码的描述,后面是用这些动态 Huffman 码编码的符号 |
| 3 | 无效 |
F-block-type-3:块类型 3 被拒绝(invalid block type)。
存储块
存储块先跳到下一个字节边界。被跳过的位可以是任意值。
然后是两个小端 16 位字段 LEN 和 NLEN,后面恰好是 LEN 个未压缩的字节。
F-stored-complement:NLEN = 65535 - LEN。不相符时被拒绝
(invalid stored block lengths)。长度为零的存储块是允许的。
规范 Huffman 码
码的描述给每个符号一个长度。长度为零表示这个符号没有用到。 对字面量/长度字母表和距离字母表,非零长度至多为 15。 规范码由这些长度和符号的顺序决定;它的位模式不需要传输。
设 count[l] 为长度为 l 的符号个数,code_start[l] 为分给长度为 l 的第一个符号的值:
code_start[1] = 0
code_start[l] = (code_start[l - 1] + count[l - 1]) * 2 for l >= 2
对一个固定的长度 l,按符号递增的顺序,从 code_start[l] 开始分配连续的值。
每个值恰好写成 l 位。例如,符号 0、1、2 的长度为 1、2、2 时,
code_start[1] = 0,code_start[2] = (0 + 1) * 2 = 2,所以三个码是 0、10 和 11。
F-code-fits:对 1 到 15 的每个 l,code_start[l] + count[l] ≤ 2^l。
等价的说法是:对所有用到的符号,2^(-length) 之和至多为 1;
一个长度为 l 的码占去码空间的 2^(-l)。长度 1、2、2 分别占去 1/2、1/4 和 1/4,正好占满。
和超过 1 就是超额分配。
F-code-complete:这个和等于 1 时码是完整的,小于 1 时是不完整的。
zlib 的建表函数采用下面的接受规则:
| 长度集合 | 是否接受 |
|---|---|
| 超额分配 | 拒绝 |
| 完整 | 接受 |
| 不完整,恰好用到一个符号,其长度为 1 | 对字面量/长度码和距离码接受;对码长码拒绝 |
| 所有长度都为零 | 作为空表接受;每次试图解码符号都会失败 |
| 其他不完整的集合 | 拒绝 |
接受一张空表,不等于接受一个无法解码的块。动态的字面量/长度表还必须含有块结束符号。 空的距离表可以用于没有匹配的块。空的码长表无法解码后面必须有的那些长度。 距离码的单符号例外是 RFC 描述的;zlib 对字面量/长度码也允许这一例外。
固定码
F-fixed-lengths:固定块使用下面的字面量/长度码长:
| 符号 | 长度 |
|---|---|
| 0–143 | 8 |
| 144–255 | 9 |
| 256–279 | 7 |
| 280–287 | 8 |
全部 32 个距离符号的长度都是 5。这些表里有保留符号:
解码出字面量/长度 286 或 287,或者距离 30 或 31,是错误
(invalid literal/length code 或 invalid distance code)。
它们出现在固定表中,并不表示可以使用。
动态码
动态块描述三套码:码长码、字面量/长度码和距离码。紧跟在块头之后,依次读取:
- 5 位的
HLIT:字面量/长度字母表有HLIT + 257项。 - 5 位的
HDIST:距离字母表有HDIST + 1项。 - 4 位的
HCLEN:后面有HCLEN + 4个码长项。 - 这些项,每项 3 位,按下面的符号顺序排列:
16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15。 没有发送的码长项为零,所以这套码的长度至多为 7。 - 合在一起的字面量/长度码长和距离码长,用上面那套码长码解码。
合在一起的列表先是全部字面量/长度项,然后是全部距离项。码长符号按下表展开:
| 符号 | 展开 |
|---|---|
| 0–15 | 一项,长度就是这个数 |
| 16 | 把前一个长度重复 3 + x 次;x 读自 2 个额外位 |
| 17 | 追加 3 + x 个零;读 3 个额外位 |
| 18 | 追加 11 + x 个零;读 7 个额外位 |
F-dynamic-limits:zlib 要求 HLIT + 257 ≤ 286 且 HDIST + 1 ≤ 30。
这两个字段能表示更大的个数;zlib 拒绝它们(too many length or distance symbols)。
F-dynamic-repeat:符号 16 之前必须已有一项。任何重复都不得超出合在一起的总项数
(invalid bit length repeat)。重复可以跨过两个字母表的分界。
F-dynamic-eob:字面量/长度符号 256 的长度必须不为零
(invalid code -- missing end-of-block)。
F-dynamic-valid:三套码各自必须满足上面的接受规则。失败时报告为
invalid code lengths set、invalid literal/lengths set 或 invalid distances set。
字面量、匹配与历史
在 Huffman 块内,一个字面量/长度符号有三种含义之一:
| 符号 | 含义 |
|---|---|
| 0–255 | 把这个字节追加到输出 |
| 256 | 结束这个块 |
| 257–285 | 读长度的额外位、一个距离符号和距离的额外位;然后复制一个匹配 |
对每个表项,把额外位的数值加到它的基值上。额外位采用普通的最低有效位在前的顺序。
F-length-table:
| 符号 | 额外位 | 长度范围,按符号顺序 |
|---|---|---|
| 257–264 | 0 | 3, 4, 5, 6, 7, 8, 9, 10 |
| 265–268 | 1 | 11–12, 13–14, 15–16, 17–18 |
| 269–272 | 2 | 19–22, 23–26, 27–30, 31–34 |
| 273–276 | 3 | 35–42, 43–50, 51–58, 59–66 |
| 277–280 | 4 | 67–82, 83–98, 99–114, 115–130 |
| 281–284 | 5 | 131–162, 163–194, 195–226, 227–257;例外见下文 |
| 285 | 0 | 258 |
F-length-284:zlib 还接受符号 284 配额外值 31,作为长度 258。
RFC 的表把长度 258 分给符号 285,而没有用到这个组合。格式模型保留 zlib 接受的这个组合。
在真实的 C 库上运行:先是字面量 a,然后是符号 284 配额外值 31 和距离 1,得到 259 个字节。
这是忠实性的证据,不是对翻译后的解码器的证明。
F-distance-table:
| 符号 | 额外位 | 距离范围,按符号顺序 |
|---|---|---|
| 0–3 | 0 | 1, 2, 3, 4 |
| 4, 5 | 1 | 5–6, 7–8 |
| 6, 7 | 2 | 9–12, 13–16 |
| 8, 9 | 3 | 17–24, 25–32 |
| 10, 11 | 4 | 33–48, 49–64 |
| 12, 13 | 5 | 65–96, 97–128 |
| 14, 15 | 6 | 129–192, 193–256 |
| 16, 17 | 7 | 257–384, 385–512 |
| 18, 19 | 8 | 513–768, 769–1024 |
| 20, 21 | 9 | 1025–1536, 1537–2048 |
| 22, 23 | 10 | 2049–3072, 3073–4096 |
| 24, 25 | 11 | 4097–6144, 6145–8192 |
| 26, 27 | 12 | 8193–12288, 12289–16384 |
| 28, 29 | 13 | 16385–24576, 24577–32768 |
F-match-copy:长度为 L、距离为 D 的匹配,从往回 D 个字节的位置起,一次复制一个字节。
每个字节在下一次复制之前就加入历史。所以 L 可以大于 D:距离 1 把最近的那个字节重复 L 次。
预置字典在这段历史中排在输出之前,它本身不是输出。
F-distance-bound:匹配之前必须有足够的历史。声明式的模型使用
D ≤ length(dictionary ++ output_so_far);距离表还保证 D ≤ 32768。
执行中的解码器则需要被引用的字节在它保存的窗口里,或在本次调用的输出里。
取不到的距离是 invalid distance too far back。
配置的窗口较小时,这两个条件并不相同。默认的 C 路径可以在当前输出缓冲区内往回复制得更远,
超出保存的窗口在两次调用之间能留住的范围。INFLATE_STRICT 另外加上一项检查,对照 zlib 头声明的上限。
这些条件跨输出缓冲区边界的完整细化尚未由证明确认;
格式关系并不保证缓冲区怎样切分都会接受同一个流。
见模型的选择和 inflate API。
zlib 封装
各字段按下面的顺序出现:
| 字段 | 编码与规则 |
|---|---|
CMF |
一个字节:低四位 CM = 8;高四位 CINFO ≤ 7,声明窗口大小为 2^(CINFO + 8) |
FLG |
一个字节:(CMF * 256 + FLG) mod 31 = 0;第 5 位是 FDICT;第 6–7 位是仅供参考的 FLEVEL |
DICTID |
仅当有 FDICT 时:整个预置字典的 Adler-32,四字节大端 |
| 载荷 | DEFLATE 块,在被忽略的填充位之后结束于字节边界 |
ADLER32 |
未压缩输出的 Adler-32,四字节大端 |
F-zlib-header:头部校验、方法字段和窗口字段必须合法。对应的错误是
incorrect header check、unknown compression method 和 invalid window size。
API 还会把声明的窗口与它配置的上限作比较。
有 FDICT 时,调用者提供一个字典,其 Adler-32 与 DICTID 相符。
只有它最后的 2^(CINFO + 8) 个字节可以用作初始历史。校验和仍然针对所提供的整个字典。
FDICT 未置位时,格式关系的字典参数被忽略。空字典的标识是 1。
F-zlib-check:尾部必须等于只对输出字节计算的 Adler-32。不相符是 incorrect data check。
字典不计入这个校验和。返回 Z_NEED_DICT 以及随后的字典调用属于 API 行为。
gzip 封装
下面的字段描述一个成员:
| 字段 | 编码与规则 |
|---|---|
ID1、ID2、CM |
字节 31、139、8 |
FLG |
一个字节:第 0 位 FTEXT,第 1 位 FHCRC,第 2 位 FEXTRA,第 3 位 FNAME,第 4 位 FCOMMENT;第 5–7 位必须为零 |
MTIME、XFL、OS |
四字节小端的时间,然后额外标志和操作系统各一个字节 |
| extra 字段 | 有 FEXTRA 时:两字节小端的长度,后面是这么多个字节 |
| 名称 | 有 FNAME 时:以零结尾的字节串 |
| 注释 | 有 FCOMMENT 时:以零结尾的字节串 |
| 头部 CRC | 有 FHCRC 时:此前全部头部字节的 CRC-32 的低 16 位,小端 |
| 载荷 | DEFLATE 块,在被忽略的填充位之后结束于字节边界 |
CRC32 |
未压缩输出的 CRC-32,四字节小端 |
ISIZE |
输出长度模 2^32,四字节小端 |
可选字段按表中的顺序出现。FTEXT、MTIME、XFL 和 OS 不影响解码。
保留标志被拒绝(unknown header flags set)。gzip 不带预置字典的标识。
F-gzip-check:尾部的 CRC 和长度必须相符。CRC 不对是 incorrect data check;
长度不对是 incorrect length check。可选的头部 CRC 另行检查。
读多个成员、透明输入和文件错误属于 gzip 文件 API。
校验和的数学定义
Adler-32 从 s1 = 1 和 s2 = 0 开始。对每个字节 b,按下面的顺序更新:
s1 = (s1 + b) mod 65521
s2 = (s2 + s1) mod 65521
adler = s2 * 65536 + s1
空序列的 Adler-32 是 1。F-adler-incremental:从一个片段的校验和出发接着处理下一个片段,
结果等于对两个片段的拼接计算校验和。
CRC-32 使用反射多项式 0xEDB88320。它的内部寄存器从 0xFFFFFFFF 开始。
每个字节按最低有效位在前的顺序处理,最后把寄存器与 0xFFFFFFFF 异或。
空序列的 CRC-32 是 0。F-crc-incremental:从已公布的校验和出发接着处理另一个片段,
结果同样等于对拼接一次算出的校验和。
初始化、更新和组合这几种调用由校验和 API规定。
压缩器必须确立什么
F-deflate-valid:把一段一直进行到 Z_FINISH 的完整压缩调用序列的输出收集起来。
它必须是所选那一层的合法的流,并且用相符的字典解码它,必须恰好得到输入。
这是针对完整的流的往返要求,封装和校验和也在其中。
F-deflate-matches:发出的匹配长度为 3–258,距离为 1 到 w_size - 262,
其中 w_size 是压缩器的窗口大小,以字节计。262 就是 MIN_LOOKAHEAD
(deflate.h 中的 MAX_MATCH + MIN_MATCH + 1),即压缩器希望备好的预读量;
窗口为 32768 字节时,最大的距离是 32506。
这个距离上界是 zlib 的算法选择,比格式的最大值 32768 更严。
F-deflate-flush:完成 Z_SYNC_FLUSH 或 Z_FULL_FLUSH,会发出一串完整的块,以一个空的存储块结尾。
这时解码器可以产生到这次刷新为止所提供的全部输入。
输出空间不够的调用者必须继续调用,直到刷新完成;单独一次调用不一定发出这个边界。
deflate API描述这个协议,以及完全刷新额外做的历史重置。
这些义务没有规定压缩后的字节是什么。不同的合法编码器可以为同一个输入选择不同的块、码和匹配。 它们必须保留输入,并满足格式、安全性和 API 的要求。