diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2019-03-08 06:25:37 +0300 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2019-03-08 06:25:37 +0300 |
commit | b5dd0c658c31b469ccff1b637e5124851e7a4a1c (patch) | |
tree | dc0b31a5aa62bb4e1fa653a4f176c2faae51f9e0 /Documentation/lzo.txt | |
parent | 610cd4eadec4f97acd25d3108b0e50d1362b3319 (diff) | |
parent | fe0436e10c8845aed24cad3a1c719efcd6e583eb (diff) | |
download | linux-b5dd0c658c31b469ccff1b637e5124851e7a4a1c.tar.xz |
Merge branch 'akpm' (patches from Andrew)
Merge more updates from Andrew Morton:
- some of the rest of MM
- various misc things
- dynamic-debug updates
- checkpatch
- some epoll speedups
- autofs
- rapidio
- lib/, lib/lzo/ updates
* emailed patches from Andrew Morton <akpm@linux-foundation.org>: (83 commits)
samples/mic/mpssd/mpssd.h: remove duplicate header
kernel/fork.c: remove duplicated include
include/linux/relay.h: fix percpu annotation in struct rchan
arch/nios2/mm/fault.c: remove duplicate include
unicore32: stop printing the virtual memory layout
MAINTAINERS: fix GTA02 entry and mark as orphan
mm: create the new vm_fault_t type
arm, s390, unicore32: remove oneliner wrappers for memblock_alloc()
arch: simplify several early memory allocations
openrisc: simplify pte_alloc_one_kernel()
sh: prefer memblock APIs returning virtual address
microblaze: prefer memblock API returning virtual address
powerpc: prefer memblock APIs returning virtual address
lib/lzo: separate lzo-rle from lzo
lib/lzo: implement run-length encoding
lib/lzo: fast 8-byte copy on arm64
lib/lzo: 64-bit CTZ on arm64
lib/lzo: tidy-up ifdefs
ipc/sem.c: replace kvmalloc/memset with kvzalloc and use struct_size
ipc: annotate implicit fall through
...
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. |