9. 压缩数据格式
- 压缩数据格式
本节基于前面各节描述的单个数据项格式, 描述压缩数据集的格式.
9.1. 流头部格式
流头部只有以下一个字段:
1..7 bits: WBITS, 范围为 10..24 的值, 使用以下变长码编码
(按其在压缩数据中的出现形式, 其中位从右到左解析):
Value Bit Pattern
----- -----------
10 0100001
11 0110001
12 1000001
13 1010001
14 1100001
15 1110001
16 0
17 0000001
18 0011
19 0101
20 0111
21 1001
22 1011
23 1101
24 1111
注意, 位模式 0010001 无效且不得使用.
滑动窗口的大小, 即任意非字典引用向后距离的最大值, 由以下公式给出:
window size = (1 << WBITS) - 16
9.2. 元块头部格式
合规的压缩数据集至少包含一个元块. 每个元块包含一个头部, 其中有关于该元块未压缩长度的信息, 以及一个指示该元块是否为最后一个元块的位. 元块头部格式如下:
1 bit: ISLAST, 如果这是最后一个元块则置为 1
1 bit: ISLASTEMPTY, 如果置为 1, 则元块为空. 该字段仅在 ISLAST 位被置位时出现 -- 如果它为 1, 则元块和 Brotli 流在该位处结束, 压缩流最后一个字节中的任何剩余位用零填充 (如果填充位不为零, 则应将该流拒绝为无效)
2 bits: MNIBBLES, 表示未压缩长度所用的半字节数量, 使用以下定长码编码:
Value Bit Pattern
----- -----------
0 11
4 00
5 01
6 10
如果 MNIBBLES 为 0, 则元块为空, 即它不生成任何未压缩数据. 在这种情况下, 元块其余部分具有以下格式:
1 bit: 保留位, 必须为零
2 bits: MSKIPBYTES, 表示元数据长度所用的字节数
MSKIPBYTES * 8 bits: MSKIPLEN - 1, 其中 MSKIPLEN 是
元数据字节数. 该字段仅在 MSKIPBYTES 为正时出现.
否则, MSKIPLEN 为 0 (如果 MSKIPBYTES
大于 1, 且最后一个字节全为零, 则应将该流拒绝为
无效)
0..7 bits: 到下一个字节边界为止的填充位,
必须全为零
MSKIPLEN 字节的元数据, 不属于未压缩数据或滑动窗口
MNIBBLES * 4 bits: MLEN - 1, 其中 MLEN 是元块未压缩数据的长度,
单位为字节 (如果 MNIBBLES 大于 4, 且最后一个半字节全为零,
则应将该流拒绝为无效)
1 bit: ISUNCOMPRESSED, 如果置为 1, 则直到下一个字节边界的所有压缩数据位都会被忽略,
元块其余部分包含 MLEN 字节的字面量数据. 该字段仅在 ISLAST
位未置位时出现 (如果被忽略的位不全为零, 则应将该流拒绝为无效)
1..11 bits: NBLTYPESL, 字面量块类型数量, 使用以下变长码编码
(按其在压缩数据中的出现形式, 其中位从右到左解析, 因此
0110111 的值为 12):
Value Bit Pattern
----- -----------
1 0
2 0001
3..4 x0011
5..8 xx0101
9..16 xxx0111
17..32 xxxx1001
33..64 xxxxx1011
65..128 xxxxxx1101
129..256 xxxxxxx1111
字面量块类型的块类型码字母表上的前缀码, 仅在 NBLTYPESL >= 2 时出现
字面量块计数的块计数码字母表上的前缀码, 仅在 NBLTYPESL >= 2 时出现
第一个字面量块计数的块计数码 + 额外位, 仅在 NBLTYPESL >= 2 时出现
1..11 bits: NBLTYPESI, 插入和复制块类型数量, 使用与上面相同的变长码编码
插入和复制块类型的块类型码字母表上的前缀码, 仅在 NBLTYPESI >= 2 时出现
插入和复制块计数的块计数码字母表上的前缀码, 仅在 NBLTYPESI >= 2 时出现
第一个插入和复制块计数的块计数码 + 额外位, 仅在 NBLTYPESI >= 2 时出现
1..11 bits: NBLTYPESD, 距离块类型数量, 使用与上面相同的变长码编码
距离块类型的块类型码字母表上的前缀码, 仅在 NBLTYPESD >= 2 时出现
距离块计数的块计数码字母表上的前缀码, 仅在 NBLTYPESD >= 2 时出现
第一个距离块计数的块计数码 + 额外位, 仅在 NBLTYPESD >= 2 时出现
2 bits: NPOSTFIX, 距离编码中使用的参数
4 bits: NDIRECT 的四个最高有效位. 要得到参数 NDIRECT 的实际值,
将这个四位数左移 NPOSTFIX 位
NBLTYPESL * 2 bits: 每个字面量块类型的上下文模式
1..11 bits: NTREESL, 字面量前缀树数量, 使用与 NBLTYPESL 相同的变长码编码
字面量上下文映射, 按第 7.3 节所述编码, 仅在 NTREESL >= 2 时出现.
否则, 上下文映射只有零值
1..11 bits: NTREESD, 距离前缀树数量, 使用与 NBLTYPESD 相同的变长码编码
距离上下文映射, 按第 7.3 节所述编码, 仅在 NTREESD >= 2 时出现.
否则, 上下文映射只有零值
用于字面量的 NTREESL 个前缀码
用于插入和复制长度的 NBLTYPESI 个前缀码
用于距离的 NTREESD 个前缀码
9.3. 元块数据格式
元块的压缩数据部分由一系列命令组成. 每个命令具有以下格式:
下一个插入和复制块类型的块类型码, 仅在 NBLTYPESI >= 2 且前一个插入和复制块计数为零时出现
下一个插入和复制块计数的块计数码 + 额外位, 仅在 NBLTYPESI >= 2 且前一个插入和复制块计数为零时出现
插入和复制长度, 按第 5 节编码, 使用当前插入和复制块类型索引对应的插入和复制长度前缀码
插入长度数量的字面量, 格式如下:
下一个字面量块类型的块类型码, 仅在 NBLTYPESL >= 2 且前一个字面量块计数为零时出现
下一个字面量块计数的块计数码 + 额外位, 仅在 NBLTYPESL >= 2 且前一个字面量块计数为零时出现
未压缩数据的下一个字节, 使用字面量前缀码编码. 如第 7.3 节所述, 该前缀码的索引由未压缩数据的前两个字节, 当前字面量块类型和上下文映射确定
下一个距离块类型的块类型码, 仅在 NBLTYPESD >= 2 且前一个距离块计数为零时出现
下一个距离块计数的块计数码 + 额外位, 仅在 NBLTYPESD >= 2 且前一个距离块计数为零时出现
距离码, 按第 4 节编码, 使用距离前缀码. 如第 7.3 节所述, 该前缀码的索引由复制长度, 当前距离块类型和距离上下文映射确定. 仅当插入和复制长度码表明距离码不是隐式 0 时出现
元块中的命令数量应使所有命令产生的未压缩字节总和 (即插入的字面量数量加上从过去数据复制或从静态字典生成的字节数) 等于元块头部中编码的未压缩长度 MLEN.
如果最后一条命令的插入部分之后产生的未压缩字节总数等于 MLEN, 则最后一条命令的复制长度会被忽略, 且不会产生任何未压缩输出. 在这种情况下, 最后一条命令的复制长度可以为任意值. 在任何其他情况下, 如果要插入的字面量数量, 复制长度或得到的字典词长度会导致超过 MLEN, 则应将该流拒绝为无效.
如果最后一个非空元块的最后一条命令未在字节边界结束, 则最后一个字节中的未使用位必须为零.
Source: RFC 7932
Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt