QuickLZ, for Really Fast Lossless Compression
Posted by Sachin Garg on 10th October 2006 | Permanent Link
Lasse Reinhold recently released alpha version of QuickLZ, a very fast lossless compression algorithm coded in 386 compatible assembly (code is inline C, so you can readily use it in C/C++ projects). To quote Werner Bergmans, “QuickLZ is now the fastest command line compression program ever tested on maximum compression”.
For more details, you can also check this comp.compression thread.
It uses a LZ77 based algorithm and is GPL licensed:
The current implementation is using LZ77 encoding with a 16 Kbyte window, a maximum matchlength of 72 bytes and separate handling of RLE sequences.
LZ matches are stored as an offset (values 3…17476) and a matchlength, both in form of bitfields of variable length so that small values, which are frequent in LZ compression, have shorter bitfields. RLE sequences are stored as a runlength followed by the byte to be repeated with the runlength (values 3…588) being a variable sized bitfield. Literals (uncompressed bytes) are prefixed by a 0 bit followed by the uncompressed byte.
A hash table of 2048 entries is used to find LZ matches. The has table is updated on each uncompressed byte, on each byte following an LZ match and on each byte following an RLE sequence. If we name that byte Bi and the following two bytes Bi+1and Bi+2, we can call D = Bi | (Bi+1 << 8) | (Bi+2 << 16). The hash table is now updated such that hash[((D >> 13) ^ D) && 0x7ff] = O where O is the offset of Bi.
Code doesn’t yet uses any MMX/SSE2 features and Lasse is planning some further optimizations in algorithm. I was almost holding my breath to see how much further this will go.
Anyway, next version will probably deserve another post for itself.