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