Linux LZO 解压程序所理解的 LZO 流格式¶
简介¶
这不是一份规范。目前似乎没有公开的 LZO 流格式规范。本文档描述了 Linux 内核中实现的 LZO 解压程序所能理解的输入格式。此分析的主题文件是 lib/lzo/lzo1x_decompress_safe.c。并未对压缩器或任何其他实现进行分析，尽管该格式很可能与标准格式一致。本文档的目的是更好地理解代码的功能，以便为未来的错误报告提出更有效的修复方案。
描述¶
该流由一系列指令、操作数和数据组成。指令由表示操作码的几个位以及构成指令操作数的位组成，其大小和位置取决于操作码以及前一条指令复制的字面量数量。操作数用于指示
从字典（之前的输出缓冲区）复制数据时的距离
一个长度（从字典中复制的字节数）
要复制的字面量数量，它被保留在变量“state”中，作为下一条指令的信息。
根据操作码和操作数，可能还会包含额外数据。这些额外数据可以是操作数的补充（例如：以更大数值编码的长度或距离），或者是将要复制到输出缓冲区的字面量。
块的第一个字节采用与其他字节不同的编码方式，它似乎专门针对字面量使用进行了优化，因为在该字节之前还没有字典。
长度总是以可变大小编码，在操作数中以少量位开始。如果位数不足以表示该长度，则可以通过消耗更多字节来以每次最多 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 实现了一个扩展，使用游程编码（run length encoding）来编码零序列。这提高了具有大量零的数据的处理速度，这在 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