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