The most important design principle behind LZ4 has been simplicity. It allows for an easy code, and fast execution.
Let's start with the compressed data format.
The compressed block is composed of sequences.
Each sequence starts with a token.
The token is a one byte value, separated into two 4-bits fields (which therefore range from 0 to 15).
The first field is to indicate the length of literals. If it is 0, then there is no literal. If it is 15, then we need to add some more bytes to indicate the full length. Each additional byte then represent a value of 0 to 255, which is added to the previous value to produce a total length. When the byte value is 255, another byte is output.
There can be any number of bytes following the token. There is no "size limit". As a sidenote, here is the reason why a not-compressible input data block can be expanded by up to 0.4%.
Following the token and optional literal length bytes, are the literals themselves.
They are exactly as numerous as previously decoded in length of literals. It's possible that there are zero literal.
Following the literals is the offset. This is a 2 bytes value, between 0 and 65535. It represents the position of the match to be copied from. Note that 0 is an invalid value, never used. 1 means "current position - 1 byte". 65536 cannot be coded, so the maximum offset value is really 65535. The value is stored using "little endian" format.
Then we need to extract the matchlength. For this, we use the second token field, a 4-bits value, from 0 to 15. There is an offset to apply, which is the minimum length of a match, called minmatch. This minimum is 4. As a consequence, a 0 value means 4 bytes, and a value of 15 means 19+ bytes.
Similar to literal length, on reaching the highest possible value (15), we output additional bytes, one at a time, with values ranging from 0 to 255. They are added to total to provide the final matchlength. A 255 value means there is another byte to read and add. There is no limit to the number of optional bytes that can be output this way (This points towards a maximum achievable compression ratio of ~250).
With the offset and the matchlength, the decoder can now proceed to copy the repetitive data from the already decoded buffer. On decoding the matchlength, we reach the end of the sequence, and start another one.
Graphically, the sequence looks like this :
Click for larger display
Note that the last sequence stops right after literals field.
There are specific parsing rules to respect in order to remain compatible with assumptions made by the decoder :
1) The last 5 bytes are always literals
2) The last match cannot start within the last 12 bytes
Consequently, a file with less then 13 bytes can only be represented as literals
These rules are in place to ensure that the decoder will never read beyond the input buffer, nor write beyond the output buffer.
Regarding the way LZ4 searches and finds matches, note that there is no restriction on the method used. It could be a full search, using like MMC, BST or standard hash chains, a fast scan, a 2D hash table, well whatever. Advanced parsing can also be achieved while respecting full format compatibility.
The "fast" version of LZ4 hosted on Google Code uses a fast scan strategy, which is a single-cell wide hash table. Each position in the input data block gets "hashed", using the first 4 bytes (minmatch). Then the position is stored at the hashed position.
The size of the hash table can be modified while respecting full format compatibility. For restricted memory systems, this is an important feature, since the hash size can be reduced to 15 bits, or 12 bits, or even 10 bits (1024 positions, needing only 4K). Obviously, the smaller the table, the more collisions (false positive) we get, reducing compression power. But it nonetheless still works, and remain fully compatible with more complex and memory-hungry versions. The decoder do not care of the method used to find matches, and requires no additional memory.
PS : as a sidenote, LZ4 has been lately updated at google code, featuring OS-X, Linux 32-bits & Linux 64-bits support. Thanks to contributions, notably Erik Andersen for the 64-bits support.
I read your spec to reimplement from the description. I think it is complete, the only thing that surprised me is that the matches are allowed to overlap forwards. It might be worth mentioning. My impl was intended to experiment with vectorization but in the end it did not work.
ReplyDeleteYes, this is a classic LZ77 design.
DeleteWith matches autorised to overlap forward, it makes the equivalent of RLE (Run Length Encoding) for free, and even repeated 2-bytes / 4-bytes sequences, which are very common.
This is in contrast with LZ78 for example, which never takes advantage of overlap. Neither PPM, nor BWT, etc.
That being said, i'm not sure to understand in which way it prevented your experiment on vectorization to work.
Rgds
Thank you for creating a clear and easily understood specification.
ReplyDeleteI believe you should add a specification of the size limit of literal length and match length. As specified currently, a correct decoder must be able to process an infinite number of bytes in either field. The best would be to specify the maximum value (not length) of either field as a power of two. The maximum length can then be inferred.
There is a typographical error in your specification: "additional" is the correct spelling.
It was in the initial spirit of the specification that sizes (of literal length or match length) can be unlimited.
DeleteIn practice though, it is necessarily limited, by the maximum size that the current implementation supports, which is ~1.9 GB.
A future implementation may support larger block sizes though.
There is also a theoretical issue with limited literal length : in case of compressing an encrypted file, it is possible that the compressed output consists only of literals. In this case, the size of literal length is the same as the size of the file. Thus, it cannot be limited.
Would you mind telling why you think enforcing a limit on length would be beneficial ?
Typo corrected. Thanks for the hint.
Hello Yann, Perhaps it is pedantic, but with no limit specified, a "correct" implementation is impossible to create.
DeleteAnother concern is efficiency. To determine a length field value > 14, "we need to add some more bytes to indicate the full length. Each additional byte then represent a value of 0 to 255, which is added to the previous value to produce a total length. When the byte value is 255, another byte is output."
I understand you chose to add byte values, rather than use a compressed integer, such as the bottom 7 bits as the next most significant bits (with top bit as signal as another byte needed). I believe this was to reduce the output size when the lengths are small. However, with an unlimited length field, we can have a huge number of bytes representing the length. So it seems there must be a limit on the length or the compression becomes inefficient.
Regarding maximum size :
Deletesince block input size is currently limited to 1.9GB, what about limiting length sizes to this value too ?
Regarding length encoding :
The LZ4 format was defined years ago. Initially, it was just created to "learn" compression, so its primary design was simplicity. High speed was then a "side-effect". Since then, priorities have been a bit reversed, but the format remained "stable", a key property to build trust around it.
I can understand that different trade-off can be invented, and may seem better. And indeed, if I had to re-invent LZ4 today, I would probably change a few things, including the way "big lengthes" are encoded.
But don't expect these corner cases scenario to really make a difference in "normal" circumstances. A few people have already attempted such variant, and benched that in most circumstances, the difference is small (<1%) if only length encoding is modified.
Larger difference can be achieved by modifying the fixed 64KB frame, allowing repetitions at larger distances, but with bigger impact on performance and complexity. (You can have a look at Shrinker and LZnib for example)
"the difference is small (<1%) if only length encoding is modified": I expect this to be true if only small length values are encoded. This was why I expected a fairly small length limit: I assumed the LZ4 format was only useful in cases where lengths are small, as the length encoding is poor for large lengths. A length of (2^16, 16K) requires 65 bytes, 64K requires 257 bytes, 256K requires 2028 bytes, and so forth. I am not speaking of the algorithm to compute the literals, but simply the length representation. Whether such lengths would be computed, I don't know.
DeleteI cannot say what the best limit would be, you would have to decide, as you are the expert. Hopefully I explained why it was surprising the limit is currently infinite, and why I expected a small limit.
DeleteSure. It's possible to introduce the notion of "implementation-dependent limit".
DeleteFor example, current LZ4 reference C implementation has an implementation-limit of 1.9 GB. But other implementations could have different limits.
This seems more important for decoders. So, whenever a decoder detects a length beyond its limit, it could refuse to continue decoding, and send an error message instead.
I like to see a bigger version of the tiny picture.
ReplyDeleteWould you be so kind and upload one?
Which tiny picture are you talking about ? The first one on the top left ? It's just an illustration, taken from http://fastcompression.blogspot.fr/p/compression-benchmark.html
Delete