diff options
Diffstat (limited to 'Documentation/lzo.txt')
| -rw-r--r-- | Documentation/lzo.txt | 39 |
1 files changed, 32 insertions, 7 deletions
diff --git a/Documentation/lzo.txt b/Documentation/lzo.txt index 6fa6a93d0949..f79934225d8d 100644 --- a/Documentation/lzo.txt +++ b/Documentation/lzo.txt @@ -78,16 +78,34 @@ Description is an implementation design choice independent on the algorithm or encoding. +Versions + +0: Original version +1: LZO-RLE + +Version 1 of LZO implements an extension to encode runs of zeros using run +length encoding. This improves speed for data with many zeros, which is a +common case for zram. This modifies the bitstream in a backwards compatible way +(v1 can correctly decompress v0 compressed data, but v0 cannot read v1 data). + +For maximum compatibility, both versions are available under different names +(lzo and lzo-rle). Differences in the encoding are noted in this document with +e.g.: version 1 only. + Byte sequences ============== First byte encoding:: - 0..17 : follow regular instruction encoding, see below. It is worth - noting that codes 16 and 17 will represent a block copy from - the dictionary which is empty, and that they will always be + 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, the next byte + gives the bitstream version (version 1 only). If the first byte + is not 17, the bitstream version is 0. + 18..21 : copy 0..3 literals state = (byte - 17) = 0..3 [ copy <state> literals ] skip byte @@ -140,6 +158,11 @@ Byte sequences state = S (copy S literals after this block) End of stream is reached if distance == 16384 + 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) @@ -165,7 +188,9 @@ Authors ======= This document was written by Willy Tarreau <w@1wt.eu> on 2014/07/19 during an - analysis of the decompression code available in Linux 3.16-rc5. The code is - tricky, it is possible that this document contains mistakes or that a few - corner cases were overlooked. In any case, please report any doubt, fix, or - proposed updates to the author(s) so that the document can be updated. + analysis of the decompression code available in Linux 3.16-rc5, and updated + by Dave Rodgman <dave.rodgman@arm.com> on 2018/10/30 to introduce run-length + encoding. The code is tricky, it is possible that this document contains + mistakes or that a few corner cases were overlooked. In any case, please + report any doubt, fix, or proposed updates to the author(s) so that the + document can be updated. |