LZ4

From WikiCoder

LZ4 is LZ77-based compression algorithm, designed for fast decompression speed in software.

LZ4 achieves high decompression speed, by:

  1. limiting amount of operations on individual bits, (smallest unit on which operations are done are nibbles = half-byte)
  2. trying to limit short offsets (<16, to allow optimized memcpys)
  3. 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;

References