LZ4压缩算法的块数据格式解析
本文是针对 LZ4 Block Format Description 的部分内容的翻译和综述，解释了 LZ4 压缩算法的块数据的格式规定。
前言
LZ4 是使用了“固定的面向字节的编码格式”的一种 LZ77 类型的压缩算法。本文介绍的是块数据（Block）的格式规定，不涉及熵编码器（Entropy Encoder）和成帧层（Framing Layer），也不涉及压缩或解压算法的具体实现。
术语
- 序列（Sequence）是组成块的基本单位。
- 字面量（Literal）是未经过压缩的原始数据。
- 匹配复制（Match Copy）是将“先前出现过的字面量”的值复制到新位置的操作。
- 标志符（Token）是序列最开头的 1 Byte。
- 偏移量（Offset）是匹配复制操作中定位“先前出现过的字面量”的依据。
- 匹配长度（Match Length）是匹配复制操作中需要复制的字面量的长度。
格式描述
每个 LZ4 压缩块由多个序列组成。每个序列是由一系列的字面量，以及一系列的匹配复制操作组成的。
序列
标识符
每个序列由一个标志符起始。标志符是 1 Byte，可被划分为 2 组 4 bits 值（0x00xF 即 0
字面量长度
标识符的高 4 位，给定了字面量的长度。如果此数值小于 15，则它代表的就是字面量的真实长度（可为 0）。如果此数值等于 15，则说明需要更多的字节来给定字面量的真实长度。此时，需要将后续的字节（0x000xFF 即 0
这样的格式规定也解释了为什么一个不可压缩的数据会导致 0.4% 的额外空间占用。
示例 1：字面量长度 48 将被表示为：
- 15：标识符的高 4 位
- 33：=48-15
示例 2：字面量长度 280 将被表示为：
- 15：标识符的高 4 位
- 255：由于 280-15>=255，所以要再增加一个字节
- 10：=280-15-255
示例 3：字面量长度 15 将被表示为：
- 15：标识符的高 4 位
- 0：=15-15，这里的 0 是不可少的
字面量
在标识符以及可能的“扩展”长度字节之后，是字面量。它的长度和刚刚解码出来的长度是一致的。需要注意，字面量的长度可以为 0，也就是没有字面量。
匹配复制的偏移量
在字面量之后，是匹配复制操作。匹配复制操作由一个偏移量起始。
偏移量是一个 2 Bytes 的数值，采用小端格式（首字节为低位字节，末尾字节为高位字节）。偏移量代表了从前面的内容中进行复制的起始位置，例如偏移量 1 表示“从当前位置的前 1 Byte 开始复制”。最大的偏移量数值是 65536。需要注意 0 是一个非法的偏移量值，它通常代表着块数据不正确。
匹配复制的匹配长度
随后是本次复制操作的匹配长度。
标识符的低 4 位，给定了匹配复制的长度的第一个值。与字面量长度类似，如果这个值是等于 15 的，那么需要向后读取若干个字节，获取完整的匹配长度（具体步骤不再赘述）。同样地，匹配长度理论上没有上限，但是具体的实现可能会对长度上限作出限制。
这样解码出来的匹配长度仍然不是最终的真实长度。我们需要在这基础上，再加上一个“最小匹配长度”（值为 4）。因此，值为 0 的匹配长度，它的真实长度应为 4，以此类推。
这样的格式规定使得最高的压缩率大约为 250。
至此，解码完匹配长度后，本序列就结束了。下一个字节将属于下一个序列。
块结束的条件
以下是 LZ4 块数据的结束条件。
- 最后一个序列仅包含字面量。也就是说这个序列在字面量之后就结束了，没有提供偏移量。
- 输入的最后 5 Bytes 总是字面量。因此，最后一个序列包含至少 5 Bytes。特别地，如果输入小于 5 Bytes，那么只有一个唯一序列，该序列包含所有字面量，甚至空的输入也可以被这样表示（它的标识符中的字面量长度为 0，并且没有匹配复制操作）。
- 最后一次匹配复制必须最晚开始于块结束的倒数 12 Bytes。最后一次匹配复制是倒数第二个序列的一部分，随后才是只包含字面量的倒数第一个序列。后果是，如果一个块是小于 12 Bytes 的，那么它无法被压缩。推论，小于 13 Bytes 的独立的块无法被压缩，应为它们必须从一个字面量作起始，随后才有匹配复制操作。
当一个块数据没有遵循上述结束条件，可以认为这个块数据是不正确的。
这些规则是为了确保最大兼容性（某些解码器会利用这些条件来实现面向速度的设计）。
实现说明
前文所述，仅仅定义了 LZ4 压缩块的格式。它并没有告诉编解码器要如何去进行具体的实现，但根据历史经验，以下有一些指导原则可供参考。
元数据
一个 LZ4 块数据需要一些额外的元数据来进行解码。通常来说，需要提供已压缩块（输入数据）的总大小和解压后数据的上限大小。或者，提供解压后的数据的总大小和输入数据的上限大小。
在块数据的规定中，并未传递这些元数据。这时就需要考虑增加一个额外的信息渠道了，毕竟在很多案例中，这些元数据已在环境中有提供。
如果你需要一种“自包含”的格式来传递必须的元数据，你可以考虑使用 LZ4 帧数据格式来代替块数据格式。
长度溢出
尽管块数据格式并没有为各种长度属性设置最大值，但在实践上，大部分的实现都会对此有限制，因为这些值通常会存储在具有固定位宽的寄存器中。
- 如果长度属性使用的是 64 位寄存器，那么可以认为事实上并没有限制，因为要达到这一限制，需要多个 PB 的单个连续块，而按照现今的标准来说，这是不合理的。
- 如果长度属性使用的是 32 位寄存器，则可能会导致溢出，但需要大小大于 16 MB 的压缩块。因此，不处理大小大于 16 MB 的压缩块的实现是安全的。不过，如果允许出现这种情况，则建议检查寄存器中是否有溢出。
- 如果长度属性使用的是 16 位寄存器，那么在压缩块小于 300 Bytes 的情况下，绝对有可能溢出此类寄存器。
设计良好的解码器应该能够检测到可能发生的长度溢出，并在此时直接报错（输入块可能并非不正确，只是本地解码器无法解码）。
请注意，为了与更大的 LZ4 生态系统兼容，建议能够将块数据的最大表示长度和最大读取长度都限制为 4 MB。这种限制与 32 位寄存器兼容，并可防止其溢出。
安全解码
如果解码器需要从不受信任的外部来源接收压缩数据，应该确保解码器对不正确的输入具有鲁棒性。要确保指示复制的字节数不会溢出输入或输出缓冲区。在读取偏移值时，还要确保复制的位置不会超出缓冲区的起始位置。这种情况可能发生在前 64 KB 的解码数据中。
请留意偏移量为 0 的情况，它是无效的，不可盲目解码。不安全的实现可能会保留目标缓冲区的内容，如果该缓冲区未初始化且仍包含隐私数据，则可能导致信息泄露。在这种情况下，可以将匹配的内容视作 0 Byte，当然也可以采用其他解决方案。
最后，请注意“重叠匹配”的情况，即匹配长度大于偏移量的情况。在这种情况下，后面要复制的一些字节还不存在，这可能会在匹配复制操作的早期阶段产生。这种情况要小心地处理。常见的情况是偏移量为 1，即最后一个字节重复了“匹配长度”的次数。
压缩技术
LZ4 压缩器的核心是检测 64 KB 以上的重复数据。该格式对压缩器在源数据块内搜索和选择匹配数据的方式不做任何假设和限制。例如，使用一种称为“全优解析”（Full Optimal Parsing）的技术，可以达到压缩率上限，但需要高昂的 CPU 和内存成本。不过，还可以考虑其他多种技术，在时间与性能的比值上加以权衡。只要遵守指定的格式，压缩的结果都可以与任何符合要求的解码器兼容，并可被正确解码。
LZ4压缩算法的块数据格式解析