--- /dev/null
+LZ4 Format Description\r
+Last revised: 2012-02-27\r
+Author : Y. Collet\r
+\r
+\r
+\r
+This small specification intents to provide enough information\r
+to anyone willing to produce LZ4-compatible compressed streams\r
+using any programming language.\r
+\r
+LZ4 is an LZ77-type compressor with a fixed, byte-oriented encoding.\r
+The most important design principle behind LZ4 is simplicity.\r
+It helps to create an easy to read and maintain source code.\r
+It also helps later on for optimisations, compactness, and speed.\r
+There is no entropy encoder backend nor framing layer.\r
+The latter is assumed to be handled by other parts of the system.\r
+\r
+This document only describes the format,\r
+not how the LZ4 compressor nor decompressor actually work.\r
+The correctness of the decompressor should not depend\r
+on implementation details of the compressor, and vice versa.\r
+\r
+\r
+\r
+-- Compressed stream format --\r
+\r
+An LZ4 compressed stream is composed of sequences.\r
+Schematically, a sequence is a suite of literals, followed by a match copy.\r
+\r
+Each sequence starts with a token.\r
+The token is a one byte value, separated into two 4-bits fields.\r
+Therefore each field ranges from 0 to 15.\r
+\r
+\r
+The first field uses the 4 high-bits of the token.\r
+It provides the length of literals to follow.\r
+(Note : a literal is a not-compressed byte).\r
+If the field value is 0, then there is no literal.\r
+If it is 15, then we need to add some more bytes to indicate the full length.\r
+Each additionnal byte then represent a value from 0 to 255,\r
+which is added to the previous value to produce a total length.\r
+When the byte value is 255, another byte is output.\r
+There can be any number of bytes following the token. There is no "size limit".\r
+(Sidenote this is why a not-compressible input stream is expanded by 0.4%).\r
+\r
+Example 1 : A length of 48 will be represented as :\r
+- 15 : value for the 4-bits High field\r
+- 33 : (=48-15) remaining length to reach 48\r
+\r
+Example 2 : A length of 280 will be represented as :\r
+- 15 : value for the 4-bits High field\r
+- 255 : following byte is maxed, since 280-15 >= 255\r
+- 10 : (=280 - 15 - 255) ) remaining length to reach 280\r
+\r
+Example 3 : A length of 15 will be represented as :\r
+- 15 : value for the 4-bits High field\r
+- 0 : (=15-15) yes, the zero must be output\r
+\r
+Following the token and optional length bytes, are the literals themselves.\r
+They are exactly as numerous as previously decoded (length of literals).\r
+It's possible that there are zero literal.\r
+\r
+\r
+Following the literals is the match copy operation.\r
+\r
+It starts by the offset.\r
+This is a 2 bytes value, in little endian format :\r
+the lower byte is the first one in the stream.\r
+\r
+The offset represents the position of the match to be copied from.\r
+1 means "current position - 1 byte".\r
+The maximum offset value is 65535, 65536 cannot be coded.\r
+Note that 0 is an invalid value, not used. \r
+\r
+Then we need to extract the match length.\r
+For this, we use the second token field, the low 4-bits.\r
+Value, obviously, ranges from 0 to 15.\r
+However here, 0 means that the copy operation will be minimal.\r
+The minimum length of a match, called minmatch, is 4. \r
+As a consequence, a 0 value means 4 bytes, and a value of 15 means 19+ bytes.\r
+Similar to literal length, on reaching the highest possible value (15), \r
+we output additional bytes, one at a time, with values ranging from 0 to 255.\r
+They are added to total to provide the final match length.\r
+A 255 value means there is another byte to read and add.\r
+There is no limit to the number of optional bytes that can be output this way.\r
+(This points towards a maximum achievable compression ratio of ~250).\r
+\r
+With the offset and the matchlength,\r
+the decoder can now proceed to copy the data from the already decoded buffer.\r
+On decoding the matchlength, we reach the end of the compressed sequence,\r
+and therefore start another one.\r
+\r
+\r
+-- Parsing restrictions --\r
+\r
+There are specific parsing rules to respect in order to remain compatible\r
+with assumptions made by the decoder :\r
+1) The last 5 bytes are always literals\r
+2) The last match must start at least 12 bytes before end of stream\r
+Consequently, a file with less than 13 bytes cannot be compressed.\r
+These rules are in place to ensure that the decoder\r
+will never read beyond the input buffer, nor write beyond the output buffer.\r
+\r
+Note that the last sequence is also incomplete,\r
+and stops right after literals.\r
+\r
+\r
+-- Additional notes --\r
+\r
+There is no assumption nor limits to the way the compressor\r
+searches and selects matches within the source stream.\r
+It could be a fast scan, a multi-probe, a full search using BST,\r
+standard hash chains or MMC, well whatever.\r
+\r
+Advanced parsing strategies can also be implemented, such as lazy match,\r
+or full optimal parsing.\r
+\r
+All these trade-off offer distinctive speed/memory/compression advantages.\r
+Whatever the method used by the compressor, its result will be decodable\r
+by any LZ4 decoder if it follows the format specification described above.\r
+\r
Code Review / simantics / platform.git / blobdiff