Linux 的 LZO 解压缩器所理解的 LZO 流格式¶
简介¶
这并非规范。似乎没有公开可用的 LZO 流格式规范。本文档描述了 Linux 内核中实现的 LZO 解压缩器所理解的输入格式。 本分析的文件为 lib/lzo/lzo1x_decompress_safe.c。 尽管格式似乎与标准格式匹配，但未对压缩器或任何其他实现进行分析。 本文档的目的是更好地了解代码的功能，以便为未来的错误报告提出更有效的修复方案。
描述¶
流由一系列指令、操作数和数据组成。 指令由表示操作码的几个位以及构成指令操作数的位组成，其大小和位置取决于操作码和先前指令复制的文字的数量。 操作数用于指示
从字典（过去的输出缓冲区）复制数据时的距离
长度（从字典复制的字节数）
要复制的文字的数量，该数量作为下一条指令的信息片段保留在变量“状态”中。
可选地，根据操作码和操作数，可以跟随额外的数据。 这些额外的数据可以是操作数的补充（例如：以更大的值编码的长度或距离），或者是要复制到输出缓冲区的文字。
块的第一个字节遵循与其他字节不同的编码，它似乎仅针对文字使用进行了优化，因为在该字节之前还没有字典。
长度始终以可变大小进行编码，首先是操作数中的少量位。 如果位的数量不足以表示长度，则最多可以以 255 的增量添加，方法是以最多每个额外字节 255 的速率消耗更多字节（因此压缩率不能超过 255:1 左右）。 使用 #bits 的可变长度编码始终相同
length = byte & ((1 << #bits) - 1) if (!length) { length = ((1 << #bits) - 1) length += 255*(number of zero bytes) length += first-non-zero-byte } length += constant (generally 2 or 3)对于字典的引用，距离是相对于输出指针的。 距离使用属于特定范围的极少量位进行编码，从而导致使用不同编码的多个复制指令。 某些编码涉及一个额外的字节，其他编码涉及两个额外的字节，形成一个小端 16 位数量（在下面标记为 LE16）。
在除了大型文字复制之外的任何指令之后，在开始下一条指令之前，将复制 0、1、2 或 3 个文字。 复制的文字数量可能会更改下一条指令的含义和行为。 在实践中，只有一条指令需要知道是否复制了 0 个，少于 4 个或更多文字。 这是在此实现中存储在 <state> 变量中的信息。 要复制的立即文字的数量通常编码在指令的最后两位中，但也可能从额外操作数（例如：距离）的最后两位中获取。
当看到距离为 0 的块复制时，声明流结束。 只有一条指令可以编码此距离 (0001HLLL)，它采用一个 LE16 操作数来表示距离，因此需要 3 个字节。
重要提示
在代码中，由于某些指令是在假设已经保证在解析指令之前跟随一定数量的字节的情况下调用的，因此缺少一些长度检查。 如果它们消耗了额外的字节，它们只需要“补充”此信用。 这是独立于算法或编码的实现设计选择。
版本
0: 原始版本 1: LZO-RLE
LZO 的版本 1 实现了一个扩展，用于使用游程编码对零游程进行编码。 这提高了具有许多零的数据的速度，这是 zram 的常见情况。 这以向后兼容的方式修改了位流（v1 可以正确解压缩 v0 压缩的数据，但 v0 无法读取 v1 数据）。
为了获得最大的兼容性，这两个版本都以不同的名称（lzo 和 lzo-rle）提供。 编码的差异在此文档中注明，例如：仅限版本 1。
字节序列¶
第一个字节编码
0..16 : follow regular instruction encoding, see below. It is worth noting that code 16 will represent a block copy from the dictionary which is empty, and that it will always be invalid at this place. 17 : bitstream version. If the first byte is 17, and compressed stream length is at least 5 bytes (length of shortest possible versioned bitstream), the next byte gives the bitstream version (version 1 only). Otherwise, the bitstream version is 0. 18..21 : copy 0..3 literals state = (byte - 17) = 0..3 [ copy <state> literals ] skip byte 22..255 : copy literal string length = (byte - 17) = 4..238 state = 4 [ don't copy extra literals ] skip byte指令编码
0 0 0 0 X X X X (0..15) Depends on the number of literals copied by the last instruction. If last instruction did not copy any literal (state == 0), this encoding will be a copy of 4 or more literal, and must be interpreted like this : 0 0 0 0 L L L L (0..15) : copy long literal string length = 3 + (L ?: 15 + (zero_bytes * 255) + non_zero_byte) state = 4 (no extra literals are copied) If last instruction used to copy between 1 to 3 literals (encoded in the instruction's opcode or distance), the instruction is a copy of a 2-byte block from the dictionary within a 1kB distance. It is worth noting that this instruction provides little savings since it uses 2 bytes to encode a copy of 2 other bytes but it encodes the number of following literals for free. It must be interpreted like this : 0 0 0 0 D D S S (0..15) : copy 2 bytes from <= 1kB distance length = 2 state = S (copy S literals after this block) Always followed by exactly one byte : H H H H H H H H distance = (H << 2) + D + 1 If last instruction used to copy 4 or more literals (as detected by state == 4), the instruction becomes a copy of a 3-byte block from the dictionary from a 2..3kB distance, and must be interpreted like this : 0 0 0 0 D D S S (0..15) : copy 3 bytes from 2..3 kB distance length = 3 state = S (copy S literals after this block) Always followed by exactly one byte : H H H H H H H H distance = (H << 2) + D + 2049 0 0 0 1 H L L L (16..31) Copy of a block within 16..48kB distance (preferably less than 10B) length = 2 + (L ?: 7 + (zero_bytes * 255) + non_zero_byte) Always followed by exactly one LE16 : D D D D D D D D : D D D D D D S S distance = 16384 + (H << 14) + D state = S (copy S literals after this block) End of stream is reached if distance == 16384 In version 1 only, to prevent ambiguity with the RLE case when ((distance & 0x803f) == 0x803f) && (261 <= length <= 264), the compressor must not emit block copies where distance and length meet these conditions. In version 1 only, this instruction is also used to encode a run of zeros if distance = 0xbfff, i.e. H = 1 and the D bits are all 1. In this case, it is followed by a fourth byte, X. run length = ((X << 3) | (0 0 0 0 0 L L L)) + 4 0 0 1 L L L L L (32..63) Copy of small block within 16kB distance (preferably less than 34B) length = 2 + (L ?: 31 + (zero_bytes * 255) + non_zero_byte) Always followed by exactly one LE16 : D D D D D D D D : D D D D D D S S distance = D + 1 state = S (copy S literals after this block) 0 1 L D D D S S (64..127) Copy 3-4 bytes from block within 2kB distance state = S (copy S literals after this block) length = 3 + L Always followed by exactly one byte : H H H H H H H H distance = (H << 3) + D + 1 1 L L D D D S S (128..255) Copy 5-8 bytes from block within 2kB distance state = S (copy S literals after this block) length = 5 + L Always followed by exactly one byte : H H H H H H H H distance = (H << 3) + D + 1