+++ /dev/null
-1. Compression algorithm (deflate)\r
-\r
-The deflation algorithm used by gzip (also zip and zlib) is a variation of\r
-LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in\r
-the input data. The second occurrence of a string is replaced by a\r
-pointer to the previous string, in the form of a pair (distance,\r
-length). Distances are limited to 32K bytes, and lengths are limited\r
-to 258 bytes. When a string does not occur anywhere in the previous\r
-32K bytes, it is emitted as a sequence of literal bytes. (In this\r
-description, `string' must be taken as an arbitrary sequence of bytes,\r
-and is not restricted to printable characters.)\r
-\r
-Literals or match lengths are compressed with one Huffman tree, and\r
-match distances are compressed with another tree. The trees are stored\r
-in a compact form at the start of each block. The blocks can have any\r
-size (except that the compressed data for one block must fit in\r
-available memory). A block is terminated when deflate() determines that\r
-it would be useful to start another block with fresh trees. (This is\r
-somewhat similar to the behavior of LZW-based _compress_.)\r
-\r
-Duplicated strings are found using a hash table. All input strings of\r
-length 3 are inserted in the hash table. A hash index is computed for\r
-the next 3 bytes. If the hash chain for this index is not empty, all\r
-strings in the chain are compared with the current input string, and\r
-the longest match is selected.\r
-\r
-The hash chains are searched starting with the most recent strings, to\r
-favor small distances and thus take advantage of the Huffman encoding.\r
-The hash chains are singly linked. There are no deletions from the\r
-hash chains, the algorithm simply discards matches that are too old.\r
-\r
-To avoid a worst-case situation, very long hash chains are arbitrarily\r
-truncated at a certain length, determined by a runtime option (level\r
-parameter of deflateInit). So deflate() does not always find the longest\r
-possible match but generally finds a match which is long enough.\r
-\r
-deflate() also defers the selection of matches with a lazy evaluation\r
-mechanism. After a match of length N has been found, deflate() searches for\r
-a longer match at the next input byte. If a longer match is found, the\r
-previous match is truncated to a length of one (thus producing a single\r
-literal byte) and the process of lazy evaluation begins again. Otherwise,\r
-the original match is kept, and the next match search is attempted only N\r
-steps later.\r
-\r
-The lazy match evaluation is also subject to a runtime parameter. If\r
-the current match is long enough, deflate() reduces the search for a longer\r
-match, thus speeding up the whole process. If compression ratio is more\r
-important than speed, deflate() attempts a complete second search even if\r
-the first match is already long enough.\r
-\r
-The lazy match evaluation is not performed for the fastest compression\r
-modes (level parameter 1 to 3). For these fast modes, new strings\r
-are inserted in the hash table only when no match was found, or\r
-when the match is not too long. This degrades the compression ratio\r
-but saves time since there are both fewer insertions and fewer searches.\r
-\r
-\r
-2. Decompression algorithm (inflate)\r
-\r
-2.1 Introduction\r
-\r
-The key question is how to represent a Huffman code (or any prefix code) so\r
-that you can decode fast. The most important characteristic is that shorter\r
-codes are much more common than longer codes, so pay attention to decoding the\r
-short codes fast, and let the long codes take longer to decode.\r
-\r
-inflate() sets up a first level table that covers some number of bits of\r
-input less than the length of longest code. It gets that many bits from the\r
-stream, and looks it up in the table. The table will tell if the next\r
-code is that many bits or less and how many, and if it is, it will tell\r
-the value, else it will point to the next level table for which inflate()\r
-grabs more bits and tries to decode a longer code.\r
-\r
-How many bits to make the first lookup is a tradeoff between the time it\r
-takes to decode and the time it takes to build the table. If building the\r
-table took no time (and if you had infinite memory), then there would only\r
-be a first level table to cover all the way to the longest code. However,\r
-building the table ends up taking a lot longer for more bits since short\r
-codes are replicated many times in such a table. What inflate() does is\r
-simply to make the number of bits in the first table a variable, and then\r
-to set that variable for the maximum speed.\r
-\r
-For inflate, which has 286 possible codes for the literal/length tree, the size\r
-of the first table is nine bits. Also the distance trees have 30 possible\r
-values, and the size of the first table is six bits. Note that for each of\r
-those cases, the table ended up one bit longer than the ``average'' code\r
-length, i.e. the code length of an approximately flat code which would be a\r
-little more than eight bits for 286 symbols and a little less than five bits\r
-for 30 symbols.\r
-\r
-\r
-2.2 More details on the inflate table lookup\r
-\r
-Ok, you want to know what this cleverly obfuscated inflate tree actually\r
-looks like. You are correct that it's not a Huffman tree. It is simply a\r
-lookup table for the first, let's say, nine bits of a Huffman symbol. The\r
-symbol could be as short as one bit or as long as 15 bits. If a particular\r
-symbol is shorter than nine bits, then that symbol's translation is duplicated\r
-in all those entries that start with that symbol's bits. For example, if the\r
-symbol is four bits, then it's duplicated 32 times in a nine-bit table. If a\r
-symbol is nine bits long, it appears in the table once.\r
-\r
-If the symbol is longer than nine bits, then that entry in the table points\r
-to another similar table for the remaining bits. Again, there are duplicated\r
-entries as needed. The idea is that most of the time the symbol will be short\r
-and there will only be one table look up. (That's whole idea behind data\r
-compression in the first place.) For the less frequent long symbols, there\r
-will be two lookups. If you had a compression method with really long\r
-symbols, you could have as many levels of lookups as is efficient. For\r
-inflate, two is enough.\r
-\r
-So a table entry either points to another table (in which case nine bits in\r
-the above example are gobbled), or it contains the translation for the symbol\r
-and the number of bits to gobble. Then you start again with the next\r
-ungobbled bit.\r
-\r
-You may wonder: why not just have one lookup table for how ever many bits the\r
-longest symbol is? The reason is that if you do that, you end up spending\r
-more time filling in duplicate symbol entries than you do actually decoding.\r
-At least for deflate's output that generates new trees every several 10's of\r
-kbytes. You can imagine that filling in a 2^15 entry table for a 15-bit code\r
-would take too long if you're only decoding several thousand symbols. At the\r
-other extreme, you could make a new table for every bit in the code. In fact,\r
-that's essentially a Huffman tree. But then you spend too much time\r
-traversing the tree while decoding, even for short symbols.\r
-\r
-So the number of bits for the first lookup table is a trade of the time to\r
-fill out the table vs. the time spent looking at the second level and above of\r
-the table.\r
-\r
-Here is an example, scaled down:\r
-\r
-The code being decoded, with 10 symbols, from 1 to 6 bits long:\r
-\r
-A: 0\r
-B: 10\r
-C: 1100\r
-D: 11010\r
-E: 11011\r
-F: 11100\r
-G: 11101\r
-H: 11110\r
-I: 111110\r
-J: 111111\r
-\r
-Let's make the first table three bits long (eight entries):\r
-\r
-000: A,1\r
-001: A,1\r
-010: A,1\r
-011: A,1\r
-100: B,2\r
-101: B,2\r
-110: -> table X (gobble 3 bits)\r
-111: -> table Y (gobble 3 bits)\r
-\r
-Each entry is what the bits decode as and how many bits that is, i.e. how\r
-many bits to gobble. Or the entry points to another table, with the number of\r
-bits to gobble implicit in the size of the table.\r
-\r
-Table X is two bits long since the longest code starting with 110 is five bits\r
-long:\r
-\r
-00: C,1\r
-01: C,1\r
-10: D,2\r
-11: E,2\r
-\r
-Table Y is three bits long since the longest code starting with 111 is six\r
-bits long:\r
-\r
-000: F,2\r
-001: F,2\r
-010: G,2\r
-011: G,2\r
-100: H,2\r
-101: H,2\r
-110: I,3\r
-111: J,3\r
-\r
-So what we have here are three tables with a total of 20 entries that had to\r
-be constructed. That's compared to 64 entries for a single table. Or\r
-compared to 16 entries for a Huffman tree (six two entry tables and one four\r
-entry table). Assuming that the code ideally represents the probability of\r
-the symbols, it takes on the average 1.25 lookups per symbol. That's compared\r
-to one lookup for the single table, or 1.66 lookups per symbol for the\r
-Huffman tree.\r
-\r
-There, I think that gives you a picture of what's going on. For inflate, the\r
-meaning of a particular symbol is often more than just a letter. It can be a\r
-byte (a "literal"), or it can be either a length or a distance which\r
-indicates a base value and a number of bits to fetch after the code that is\r
-added to the base value. Or it might be the special end-of-block code. The\r
-data structures created in inftrees.c try to encode all that information\r
-compactly in the tables.\r
-\r
-\r
-Jean-loup Gailly Mark Adler\r
-jloup@gzip.org madler@alumni.caltech.edu\r
-\r
-\r
-References:\r
-\r
-[LZ77] Ziv J., Lempel A., ``A Universal Algorithm for Sequential Data\r
-Compression,'' IEEE Transactions on Information Theory, Vol. 23, No. 3,\r
-pp. 337-343.\r
-\r
-``DEFLATE Compressed Data Format Specification'' available in\r
-http://tools.ietf.org/html/rfc1951\r
projects / mirror_edk2.git / blobdiff