GDeflate#
GDeflate 是一种新的压缩流格式，它与 DEFLATE 格式非常相似。关键区别在于压缩比特流中位的存储方式。GDeflate 流本质上是任何 DEFLATE 格式的位元置换版本。GDeflate 流本质上是任何 DEFLATE 流的位元置换版本，其中置换以特定方式完成，以提取 32 路并行性。这意味着 GDeflate 可以在 GPU 上获得非常高的解压缩吞吐量，同时仍然保持与 DEFLATE 完全相同的压缩率（关于结束效应有一些小的注意事项）。
DEFLATE 快速入门#
DEFLATE 是一种压缩格式，它使用 LZ77 压缩，并使用 Huffman 编码进一步压缩。字面量和匹配复制长度使用单个 Huffman 树，匹配复制距离使用单独的 Huffman 树。DEFLATE 允许使用构成流的三种数据块类型
动态 Huffman 压缩数据块，其中 Huffman 树是压缩流的一部分
静态 Huffman 压缩块，其中 Huffman 树在 RFC 中定义，因此不需要包含在压缩流中，以及
存储块，其中数据未压缩。
解压缩 DEFLATE 流首先需要解码 Huffman 编码的比特流。由于流中每个符号的代码长度事先未知，因此必须串行解码流，并且很难并行化此解码过程。这是 GDeflate 要解决的问题。
有关 DEFLATE 压缩格式的完整描述，请参阅 RFC 1951。
GDeflate 流定义#
GDeflate 通过基于状态转换思想置换比特流中的位，从 DEFLATE 流中提取并行性。最终流是 32 个独立子流的序列化，允许在解压缩期间实现高达 32 路的并行性。常规 DEFLATE 流的字面量或长度+距离位在 32 个子流中以组为单位交错。每个组具有 <= 32 个字面量或长度+距离代码。如果子流在组 N 中被分配了长度+距离代码，则它不会在组 N+1 中被分配任何位。单个匹配复制（长度 + 距离）所需的所有位始终分配给同一个子流。
这些子流的序列化由解压缩状态定义。当使用多个线程解压缩流时，每个线程维护一个 64 位状态，该状态保存其子流中的下一个位。当线程解码一个符号时，已使用的位将从线程的状态中失效。当线程的状态中剩余 <= 32 个有效位时，线程以 32 位/4 字节的块加载新数据。此加载条件以及子流定义然后给出了最终 GDeflate 流的序列化顺序。当解压缩流时，线程从其本地状态读取数据并解码 Huffman 符号。然后所有线程都使已使用的位失效。然后，剩余 <= 32 个有效位的线程按照线程编号的顺序（线程 j 在线程 i 之后，对于 j > i）从流中以 4 字节块加载数据。
下图显示了 DEFLATE 块如何置换以获得 GDeflate 块的示意图。为了使示意图更具可读性，此置换思想以 4 路并行性而不是 32 路并行性显示。
这种置换思想也扩展到描述动态 Huffman 块的标头中 Huffman 树的数据以及代码长度字母表的代码长度。以下部分更详细地描述了这一点。
GDeflate 置换顺序#
初始化#
在初始化时，每个线程从流中加载 4 个字节的数据，并填充其 64 位状态的 32 位。
块标头#
每个块包含一个 3 位标头。这些位始终分配给线程 0。
动态 Huffman 压缩块#
14 位标头#
动态 Huffman 压缩块具有额外的 14 位标头。这些位始终分配给线程 0。这些位定义了整数 HLIT、HDIST 和 HCLEN。
代码长度字母表的代码长度#
代码长度字母表的代码长度均为 3 位，数量为 HCLEN+4，并以轮询方式分配给 32 个线程，从线程 0 开始。此分配按照 DEFLATE 定义的顺序：16、17、18、0、8、7、9、6、10、5、11、4、12、3、13、2、14、1、15。
代码长度#
有 (HLIT + 257) + (HDIST + 1) 个代码长度定义了字面量/长度和距离 Huffman 树。这些是可变长度的 Huffman 编码代码本身，并以轮询方式分配给 32 个线程，从线程 0 开始。由于代码长度是行程长度编码的，因此代码的数量可能少于代码长度的总数。
字面量、长度和距离符号#
符号的位分配顺序以轮次描述。在每个轮次中，每个线程解码字面量/长度符号或距离符号。
在第一轮中，每个线程都被分配一个字面量/长度代码，从线程 0 开始。
如果一个线程获得一个长度代码，则相应的距离代码被安排在下一轮中，而不是为其分配新的字面量/长度代码。
所有未获得长度代码的线程都在下一轮中被分配一个新的字面量/长度代码。
符号 256 结束字面量/长度代码。
在遇到块结束符号 (256) 后，还有最后一轮来处理待处理的距离代码。
下表显示了示意图中示例的每个线程解码的符号。L 表示字面量/长度符号，D 表示距离符号。
轮次 |
T0 |
T1 |
T2 |
T3 |
|---|---|---|---|---|
0 |
L |
L |
L |
L |
1 |
L |
D |
L |
D |
2 |
L |
L |
D |
L |
3 |
D |
静态 Huffman 压缩块#
静态 Huffman 压缩块具有预定义的 Huffman 树，如 DEFLATE 所述。线程只需要从流中读取字面量、长度和距离符号，并且格式与动态 Huffman 压缩块相同。
存储块#
标头#
存储块具有 4 字节标头，该标头是字节对齐的，并定义块中的字节数。此标头始终分配给线程 0，并且在线程 0 的子流中也是字节对齐的。所有其他线程都不需要任何对齐条件。
数据#
存储块中的数据只是单个字节，这些字节以轮询方式分配给线程，从线程 0 开始。
结束流#
GDeflate 流需要在流的末尾进行零填充，以保证线程不会读取超出可能损坏 Huffman 解码过程的最后一个有效位的数据。这最容易通过用 128 字节的零填充流来完成，但如果可能，可以使其更紧凑。