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