LZ4 is LZ77-based compression algorithm, designed for fast decompression speed in software.
LZ4 achieves high decompression speed, by:
- limiting amount of operations on individual bits, (smallest unit on which operations are done are nibbles = half-byte)
- trying to limit short offsets (<16, to allow optimized memcpys)
- trying to use fast 16-byte copying operations
Decompression always have two phases copying literals followed by coping repetition from a sliding window.
only decompression pseudo-code is given below.
decompress(in_ptr, out_ptr) token = *in_ptr++; literal_length = token >> 4; if (literal_length == 0xF) decode further length bytes copy_literals_from(in_ptr, out_ptr, literal_length); offset = readLowEndian16(in_ptr); in_ptr += 2; match_length = token & 0xF; if (match_length == 0xF) decode further length bytes; // note that memmove is used, but actual implementation, // goes to great lenghts to use non-overlapping memcpys memmove(out_ptr, in_ptr - offset, match_length); in_ptr += match_length;