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