cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Network Working Group P. Deutsch cannam@89: Request for Comments: 1951 Aladdin Enterprises cannam@89: Category: Informational May 1996 cannam@89: cannam@89: cannam@89: DEFLATE Compressed Data Format Specification version 1.3 cannam@89: cannam@89: Status of This Memo cannam@89: cannam@89: This memo provides information for the Internet community. This memo cannam@89: does not specify an Internet standard of any kind. Distribution of cannam@89: this memo is unlimited. cannam@89: cannam@89: IESG Note: cannam@89: cannam@89: The IESG takes no position on the validity of any Intellectual cannam@89: Property Rights statements contained in this document. cannam@89: cannam@89: Notices cannam@89: cannam@89: Copyright (c) 1996 L. Peter Deutsch cannam@89: cannam@89: Permission is granted to copy and distribute this document for any cannam@89: purpose and without charge, including translations into other cannam@89: languages and incorporation into compilations, provided that the cannam@89: copyright notice and this notice are preserved, and that any cannam@89: substantive changes or deletions from the original are clearly cannam@89: marked. cannam@89: cannam@89: A pointer to the latest version of this and related documentation in cannam@89: HTML format can be found at the URL cannam@89: . cannam@89: cannam@89: Abstract cannam@89: cannam@89: This specification defines a lossless compressed data format that cannam@89: compresses data using a combination of the LZ77 algorithm and Huffman cannam@89: coding, with efficiency comparable to the best currently available cannam@89: general-purpose compression methods. The data can be produced or cannam@89: consumed, even for an arbitrarily long sequentially presented input cannam@89: data stream, using only an a priori bounded amount of intermediate cannam@89: storage. The format can be implemented readily in a manner not cannam@89: covered by patents. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 1] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: Table of Contents cannam@89: cannam@89: 1. Introduction ................................................... 2 cannam@89: 1.1. Purpose ................................................... 2 cannam@89: 1.2. Intended audience ......................................... 3 cannam@89: 1.3. Scope ..................................................... 3 cannam@89: 1.4. Compliance ................................................ 3 cannam@89: 1.5. Definitions of terms and conventions used ................ 3 cannam@89: 1.6. Changes from previous versions ............................ 4 cannam@89: 2. Compressed representation overview ............................. 4 cannam@89: 3. Detailed specification ......................................... 5 cannam@89: 3.1. Overall conventions ....................................... 5 cannam@89: 3.1.1. Packing into bytes .................................. 5 cannam@89: 3.2. Compressed block format ................................... 6 cannam@89: 3.2.1. Synopsis of prefix and Huffman coding ............... 6 cannam@89: 3.2.2. Use of Huffman coding in the "deflate" format ....... 7 cannam@89: 3.2.3. Details of block format ............................. 9 cannam@89: 3.2.4. Non-compressed blocks (BTYPE=00) ................... 11 cannam@89: 3.2.5. Compressed blocks (length and distance codes) ...... 11 cannam@89: 3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 12 cannam@89: 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 13 cannam@89: 3.3. Compliance ............................................... 14 cannam@89: 4. Compression algorithm details ................................. 14 cannam@89: 5. References .................................................... 16 cannam@89: 6. Security Considerations ....................................... 16 cannam@89: 7. Source code ................................................... 16 cannam@89: 8. Acknowledgements .............................................. 16 cannam@89: 9. Author's Address .............................................. 17 cannam@89: cannam@89: 1. Introduction cannam@89: cannam@89: 1.1. Purpose cannam@89: cannam@89: The purpose of this specification is to define a lossless cannam@89: compressed data format that: cannam@89: * Is independent of CPU type, operating system, file system, cannam@89: and character set, and hence can be used for interchange; cannam@89: * Can be produced or consumed, even for an arbitrarily long cannam@89: sequentially presented input data stream, using only an a cannam@89: priori bounded amount of intermediate storage, and hence cannam@89: can be used in data communications or similar structures cannam@89: such as Unix filters; cannam@89: * Compresses data with efficiency comparable to the best cannam@89: currently available general-purpose compression methods, cannam@89: and in particular considerably better than the "compress" cannam@89: program; cannam@89: * Can be implemented readily in a manner not covered by cannam@89: patents, and hence can be practiced freely; cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 2] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: * Is compatible with the file format produced by the current cannam@89: widely used gzip utility, in that conforming decompressors cannam@89: will be able to read data produced by the existing gzip cannam@89: compressor. cannam@89: cannam@89: The data format defined by this specification does not attempt to: cannam@89: cannam@89: * Allow random access to compressed data; cannam@89: * Compress specialized data (e.g., raster graphics) as well cannam@89: as the best currently available specialized algorithms. cannam@89: cannam@89: A simple counting argument shows that no lossless compression cannam@89: algorithm can compress every possible input data set. For the cannam@89: format defined here, the worst case expansion is 5 bytes per 32K- cannam@89: byte block, i.e., a size increase of 0.015% for large data sets. cannam@89: English text usually compresses by a factor of 2.5 to 3; cannam@89: executable files usually compress somewhat less; graphical data cannam@89: such as raster images may compress much more. cannam@89: cannam@89: 1.2. Intended audience cannam@89: cannam@89: This specification is intended for use by implementors of software cannam@89: to compress data into "deflate" format and/or decompress data from cannam@89: "deflate" format. cannam@89: cannam@89: The text of the specification assumes a basic background in cannam@89: programming at the level of bits and other primitive data cannam@89: representations. Familiarity with the technique of Huffman coding cannam@89: is helpful but not required. cannam@89: cannam@89: 1.3. Scope cannam@89: cannam@89: The specification specifies a method for representing a sequence cannam@89: of bytes as a (usually shorter) sequence of bits, and a method for cannam@89: packing the latter bit sequence into bytes. cannam@89: cannam@89: 1.4. Compliance cannam@89: cannam@89: Unless otherwise indicated below, a compliant decompressor must be cannam@89: able to accept and decompress any data set that conforms to all cannam@89: the specifications presented here; a compliant compressor must cannam@89: produce data sets that conform to all the specifications presented cannam@89: here. cannam@89: cannam@89: 1.5. Definitions of terms and conventions used cannam@89: cannam@89: Byte: 8 bits stored or transmitted as a unit (same as an octet). cannam@89: For this specification, a byte is exactly 8 bits, even on machines cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 3] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: which store a character on a number of bits different from eight. cannam@89: See below, for the numbering of bits within a byte. cannam@89: cannam@89: String: a sequence of arbitrary bytes. cannam@89: cannam@89: 1.6. Changes from previous versions cannam@89: cannam@89: There have been no technical changes to the deflate format since cannam@89: version 1.1 of this specification. In version 1.2, some cannam@89: terminology was changed. Version 1.3 is a conversion of the cannam@89: specification to RFC style. cannam@89: cannam@89: 2. Compressed representation overview cannam@89: cannam@89: A compressed data set consists of a series of blocks, corresponding cannam@89: to successive blocks of input data. The block sizes are arbitrary, cannam@89: except that non-compressible blocks are limited to 65,535 bytes. cannam@89: cannam@89: Each block is compressed using a combination of the LZ77 algorithm cannam@89: and Huffman coding. The Huffman trees for each block are independent cannam@89: of those for previous or subsequent blocks; the LZ77 algorithm may cannam@89: use a reference to a duplicated string occurring in a previous block, cannam@89: up to 32K input bytes before. cannam@89: cannam@89: Each block consists of two parts: a pair of Huffman code trees that cannam@89: describe the representation of the compressed data part, and a cannam@89: compressed data part. (The Huffman trees themselves are compressed cannam@89: using Huffman encoding.) The compressed data consists of a series of cannam@89: elements of two types: literal bytes (of strings that have not been cannam@89: detected as duplicated within the previous 32K input bytes), and cannam@89: pointers to duplicated strings, where a pointer is represented as a cannam@89: pair . The representation used in the cannam@89: "deflate" format limits distances to 32K bytes and lengths to 258 cannam@89: bytes, but does not limit the size of a block, except for cannam@89: uncompressible blocks, which are limited as noted above. cannam@89: cannam@89: Each type of value (literals, distances, and lengths) in the cannam@89: compressed data is represented using a Huffman code, using one code cannam@89: tree for literals and lengths and a separate code tree for distances. cannam@89: The code trees for each block appear in a compact form just before cannam@89: the compressed data for that block. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 4] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 3. Detailed specification cannam@89: cannam@89: 3.1. Overall conventions In the diagrams below, a box like this: cannam@89: cannam@89: +---+ cannam@89: | | <-- the vertical bars might be missing cannam@89: +---+ cannam@89: cannam@89: represents one byte; a box like this: cannam@89: cannam@89: +==============+ cannam@89: | | cannam@89: +==============+ cannam@89: cannam@89: represents a variable number of bytes. cannam@89: cannam@89: Bytes stored within a computer do not have a "bit order", since cannam@89: they are always treated as a unit. However, a byte considered as cannam@89: an integer between 0 and 255 does have a most- and least- cannam@89: significant bit, and since we write numbers with the most- cannam@89: significant digit on the left, we also write bytes with the most- cannam@89: significant bit on the left. In the diagrams below, we number the cannam@89: bits of a byte so that bit 0 is the least-significant bit, i.e., cannam@89: the bits are numbered: cannam@89: cannam@89: +--------+ cannam@89: |76543210| cannam@89: +--------+ cannam@89: cannam@89: Within a computer, a number may occupy multiple bytes. All cannam@89: multi-byte numbers in the format described here are stored with cannam@89: the least-significant byte first (at the lower memory address). cannam@89: For example, the decimal number 520 is stored as: cannam@89: cannam@89: 0 1 cannam@89: +--------+--------+ cannam@89: |00001000|00000010| cannam@89: +--------+--------+ cannam@89: ^ ^ cannam@89: | | cannam@89: | + more significant byte = 2 x 256 cannam@89: + less significant byte = 8 cannam@89: cannam@89: 3.1.1. Packing into bytes cannam@89: cannam@89: This document does not address the issue of the order in which cannam@89: bits of a byte are transmitted on a bit-sequential medium, cannam@89: since the final data format described here is byte- rather than cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 5] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: bit-oriented. However, we describe the compressed block format cannam@89: in below, as a sequence of data elements of various bit cannam@89: lengths, not a sequence of bytes. We must therefore specify cannam@89: how to pack these data elements into bytes to form the final cannam@89: compressed byte sequence: cannam@89: cannam@89: * Data elements are packed into bytes in order of cannam@89: increasing bit number within the byte, i.e., starting cannam@89: with the least-significant bit of the byte. cannam@89: * Data elements other than Huffman codes are packed cannam@89: starting with the least-significant bit of the data cannam@89: element. cannam@89: * Huffman codes are packed starting with the most- cannam@89: significant bit of the code. cannam@89: cannam@89: In other words, if one were to print out the compressed data as cannam@89: a sequence of bytes, starting with the first byte at the cannam@89: *right* margin and proceeding to the *left*, with the most- cannam@89: significant bit of each byte on the left as usual, one would be cannam@89: able to parse the result from right to left, with fixed-width cannam@89: elements in the correct MSB-to-LSB order and Huffman codes in cannam@89: bit-reversed order (i.e., with the first bit of the code in the cannam@89: relative LSB position). cannam@89: cannam@89: 3.2. Compressed block format cannam@89: cannam@89: 3.2.1. Synopsis of prefix and Huffman coding cannam@89: cannam@89: Prefix coding represents symbols from an a priori known cannam@89: alphabet by bit sequences (codes), one code for each symbol, in cannam@89: a manner such that different symbols may be represented by bit cannam@89: sequences of different lengths, but a parser can always parse cannam@89: an encoded string unambiguously symbol-by-symbol. cannam@89: cannam@89: We define a prefix code in terms of a binary tree in which the cannam@89: two edges descending from each non-leaf node are labeled 0 and cannam@89: 1 and in which the leaf nodes correspond one-for-one with (are cannam@89: labeled with) the symbols of the alphabet; then the code for a cannam@89: symbol is the sequence of 0's and 1's on the edges leading from cannam@89: the root to the leaf labeled with that symbol. For example: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 6] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: /\ Symbol Code cannam@89: 0 1 ------ ---- cannam@89: / \ A 00 cannam@89: /\ B B 1 cannam@89: 0 1 C 011 cannam@89: / \ D 010 cannam@89: A /\ cannam@89: 0 1 cannam@89: / \ cannam@89: D C cannam@89: cannam@89: A parser can decode the next symbol from an encoded input cannam@89: stream by walking down the tree from the root, at each step cannam@89: choosing the edge corresponding to the next input bit. cannam@89: cannam@89: Given an alphabet with known symbol frequencies, the Huffman cannam@89: algorithm allows the construction of an optimal prefix code cannam@89: (one which represents strings with those symbol frequencies cannam@89: using the fewest bits of any possible prefix codes for that cannam@89: alphabet). Such a code is called a Huffman code. (See cannam@89: reference [1] in Chapter 5, references for additional cannam@89: information on Huffman codes.) cannam@89: cannam@89: Note that in the "deflate" format, the Huffman codes for the cannam@89: various alphabets must not exceed certain maximum code lengths. cannam@89: This constraint complicates the algorithm for computing code cannam@89: lengths from symbol frequencies. Again, see Chapter 5, cannam@89: references for details. cannam@89: cannam@89: 3.2.2. Use of Huffman coding in the "deflate" format cannam@89: cannam@89: The Huffman codes used for each alphabet in the "deflate" cannam@89: format have two additional rules: cannam@89: cannam@89: * All codes of a given bit length have lexicographically cannam@89: consecutive values, in the same order as the symbols cannam@89: they represent; cannam@89: cannam@89: * Shorter codes lexicographically precede longer codes. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 7] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: We could recode the example above to follow this rule as cannam@89: follows, assuming that the order of the alphabet is ABCD: cannam@89: cannam@89: Symbol Code cannam@89: ------ ---- cannam@89: A 10 cannam@89: B 0 cannam@89: C 110 cannam@89: D 111 cannam@89: cannam@89: I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are cannam@89: lexicographically consecutive. cannam@89: cannam@89: Given this rule, we can define the Huffman code for an alphabet cannam@89: just by giving the bit lengths of the codes for each symbol of cannam@89: the alphabet in order; this is sufficient to determine the cannam@89: actual codes. In our example, the code is completely defined cannam@89: by the sequence of bit lengths (2, 1, 3, 3). The following cannam@89: algorithm generates the codes as integers, intended to be read cannam@89: from most- to least-significant bit. The code lengths are cannam@89: initially in tree[I].Len; the codes are produced in cannam@89: tree[I].Code. cannam@89: cannam@89: 1) Count the number of codes for each code length. Let cannam@89: bl_count[N] be the number of codes of length N, N >= 1. cannam@89: cannam@89: 2) Find the numerical value of the smallest code for each cannam@89: code length: cannam@89: cannam@89: code = 0; cannam@89: bl_count[0] = 0; cannam@89: for (bits = 1; bits <= MAX_BITS; bits++) { cannam@89: code = (code + bl_count[bits-1]) << 1; cannam@89: next_code[bits] = code; cannam@89: } cannam@89: cannam@89: 3) Assign numerical values to all codes, using consecutive cannam@89: values for all codes of the same length with the base cannam@89: values determined at step 2. Codes that are never used cannam@89: (which have a bit length of zero) must not be assigned a cannam@89: value. cannam@89: cannam@89: for (n = 0; n <= max_code; n++) { cannam@89: len = tree[n].Len; cannam@89: if (len != 0) { cannam@89: tree[n].Code = next_code[len]; cannam@89: next_code[len]++; cannam@89: } cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 8] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: } cannam@89: cannam@89: Example: cannam@89: cannam@89: Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, cannam@89: 3, 2, 4, 4). After step 1, we have: cannam@89: cannam@89: N bl_count[N] cannam@89: - ----------- cannam@89: 2 1 cannam@89: 3 5 cannam@89: 4 2 cannam@89: cannam@89: Step 2 computes the following next_code values: cannam@89: cannam@89: N next_code[N] cannam@89: - ------------ cannam@89: 1 0 cannam@89: 2 0 cannam@89: 3 2 cannam@89: 4 14 cannam@89: cannam@89: Step 3 produces the following code values: cannam@89: cannam@89: Symbol Length Code cannam@89: ------ ------ ---- cannam@89: A 3 010 cannam@89: B 3 011 cannam@89: C 3 100 cannam@89: D 3 101 cannam@89: E 3 110 cannam@89: F 2 00 cannam@89: G 4 1110 cannam@89: H 4 1111 cannam@89: cannam@89: 3.2.3. Details of block format cannam@89: cannam@89: Each block of compressed data begins with 3 header bits cannam@89: containing the following data: cannam@89: cannam@89: first bit BFINAL cannam@89: next 2 bits BTYPE cannam@89: cannam@89: Note that the header bits do not necessarily begin on a byte cannam@89: boundary, since a block does not necessarily occupy an integral cannam@89: number of bytes. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 9] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: BFINAL is set if and only if this is the last block of the data cannam@89: set. cannam@89: cannam@89: BTYPE specifies how the data are compressed, as follows: cannam@89: cannam@89: 00 - no compression cannam@89: 01 - compressed with fixed Huffman codes cannam@89: 10 - compressed with dynamic Huffman codes cannam@89: 11 - reserved (error) cannam@89: cannam@89: The only difference between the two compressed cases is how the cannam@89: Huffman codes for the literal/length and distance alphabets are cannam@89: defined. cannam@89: cannam@89: In all cases, the decoding algorithm for the actual data is as cannam@89: follows: cannam@89: cannam@89: do cannam@89: read block header from input stream. cannam@89: if stored with no compression cannam@89: skip any remaining bits in current partially cannam@89: processed byte cannam@89: read LEN and NLEN (see next section) cannam@89: copy LEN bytes of data to output cannam@89: otherwise cannam@89: if compressed with dynamic Huffman codes cannam@89: read representation of code trees (see cannam@89: subsection below) cannam@89: loop (until end of block code recognized) cannam@89: decode literal/length value from input stream cannam@89: if value < 256 cannam@89: copy value (literal byte) to output stream cannam@89: otherwise cannam@89: if value = end of block (256) cannam@89: break from loop cannam@89: otherwise (value = 257..285) cannam@89: decode distance from input stream cannam@89: cannam@89: move backwards distance bytes in the output cannam@89: stream, and copy length bytes from this cannam@89: position to the output stream. cannam@89: end loop cannam@89: while not last block cannam@89: cannam@89: Note that a duplicated string reference may refer to a string cannam@89: in a previous block; i.e., the backward distance may cross one cannam@89: or more block boundaries. However a distance cannot refer past cannam@89: the beginning of the output stream. (An application using a cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 10] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: preset dictionary might discard part of the output stream; a cannam@89: distance can refer to that part of the output stream anyway) cannam@89: Note also that the referenced string may overlap the current cannam@89: position; for example, if the last 2 bytes decoded have values cannam@89: X and Y, a string reference with cannam@89: adds X,Y,X,Y,X to the output stream. cannam@89: cannam@89: We now specify each compression method in turn. cannam@89: cannam@89: 3.2.4. Non-compressed blocks (BTYPE=00) cannam@89: cannam@89: Any bits of input up to the next byte boundary are ignored. cannam@89: The rest of the block consists of the following information: cannam@89: cannam@89: 0 1 2 3 4... cannam@89: +---+---+---+---+================================+ cannam@89: | LEN | NLEN |... LEN bytes of literal data...| cannam@89: +---+---+---+---+================================+ cannam@89: cannam@89: LEN is the number of data bytes in the block. NLEN is the cannam@89: one's complement of LEN. cannam@89: cannam@89: 3.2.5. Compressed blocks (length and distance codes) cannam@89: cannam@89: As noted above, encoded data blocks in the "deflate" format cannam@89: consist of sequences of symbols drawn from three conceptually cannam@89: distinct alphabets: either literal bytes, from the alphabet of cannam@89: byte values (0..255), or pairs, cannam@89: where the length is drawn from (3..258) and the distance is cannam@89: drawn from (1..32,768). In fact, the literal and length cannam@89: alphabets are merged into a single alphabet (0..285), where cannam@89: values 0..255 represent literal bytes, the value 256 indicates cannam@89: end-of-block, and values 257..285 represent length codes cannam@89: (possibly in conjunction with extra bits following the symbol cannam@89: code) as follows: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 11] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: Extra Extra Extra cannam@89: Code Bits Length(s) Code Bits Lengths Code Bits Length(s) cannam@89: ---- ---- ------ ---- ---- ------- ---- ---- ------- cannam@89: 257 0 3 267 1 15,16 277 4 67-82 cannam@89: 258 0 4 268 1 17,18 278 4 83-98 cannam@89: 259 0 5 269 2 19-22 279 4 99-114 cannam@89: 260 0 6 270 2 23-26 280 4 115-130 cannam@89: 261 0 7 271 2 27-30 281 5 131-162 cannam@89: 262 0 8 272 2 31-34 282 5 163-194 cannam@89: 263 0 9 273 3 35-42 283 5 195-226 cannam@89: 264 0 10 274 3 43-50 284 5 227-257 cannam@89: 265 1 11,12 275 3 51-58 285 0 258 cannam@89: 266 1 13,14 276 3 59-66 cannam@89: cannam@89: The extra bits should be interpreted as a machine integer cannam@89: stored with the most-significant bit first, e.g., bits 1110 cannam@89: represent the value 14. cannam@89: cannam@89: Extra Extra Extra cannam@89: Code Bits Dist Code Bits Dist Code Bits Distance cannam@89: ---- ---- ---- ---- ---- ------ ---- ---- -------- cannam@89: 0 0 1 10 4 33-48 20 9 1025-1536 cannam@89: 1 0 2 11 4 49-64 21 9 1537-2048 cannam@89: 2 0 3 12 5 65-96 22 10 2049-3072 cannam@89: 3 0 4 13 5 97-128 23 10 3073-4096 cannam@89: 4 1 5,6 14 6 129-192 24 11 4097-6144 cannam@89: 5 1 7,8 15 6 193-256 25 11 6145-8192 cannam@89: 6 2 9-12 16 7 257-384 26 12 8193-12288 cannam@89: 7 2 13-16 17 7 385-512 27 12 12289-16384 cannam@89: 8 3 17-24 18 8 513-768 28 13 16385-24576 cannam@89: 9 3 25-32 19 8 769-1024 29 13 24577-32768 cannam@89: cannam@89: 3.2.6. Compression with fixed Huffman codes (BTYPE=01) cannam@89: cannam@89: The Huffman codes for the two alphabets are fixed, and are not cannam@89: represented explicitly in the data. The Huffman code lengths cannam@89: for the literal/length alphabet are: cannam@89: cannam@89: Lit Value Bits Codes cannam@89: --------- ---- ----- cannam@89: 0 - 143 8 00110000 through cannam@89: 10111111 cannam@89: 144 - 255 9 110010000 through cannam@89: 111111111 cannam@89: 256 - 279 7 0000000 through cannam@89: 0010111 cannam@89: 280 - 287 8 11000000 through cannam@89: 11000111 cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 12] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: The code lengths are sufficient to generate the actual codes, cannam@89: as described above; we show the codes in the table for added cannam@89: clarity. Literal/length values 286-287 will never actually cannam@89: occur in the compressed data, but participate in the code cannam@89: construction. cannam@89: cannam@89: Distance codes 0-31 are represented by (fixed-length) 5-bit cannam@89: codes, with possible additional bits as shown in the table cannam@89: shown in Paragraph 3.2.5, above. Note that distance codes 30- cannam@89: 31 will never actually occur in the compressed data. cannam@89: cannam@89: 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) cannam@89: cannam@89: The Huffman codes for the two alphabets appear in the block cannam@89: immediately after the header bits and before the actual cannam@89: compressed data, first the literal/length code and then the cannam@89: distance code. Each code is defined by a sequence of code cannam@89: lengths, as discussed in Paragraph 3.2.2, above. For even cannam@89: greater compactness, the code length sequences themselves are cannam@89: compressed using a Huffman code. The alphabet for code lengths cannam@89: is as follows: cannam@89: cannam@89: 0 - 15: Represent code lengths of 0 - 15 cannam@89: 16: Copy the previous code length 3 - 6 times. cannam@89: The next 2 bits indicate repeat length cannam@89: (0 = 3, ... , 3 = 6) cannam@89: Example: Codes 8, 16 (+2 bits 11), cannam@89: 16 (+2 bits 10) will expand to cannam@89: 12 code lengths of 8 (1 + 6 + 5) cannam@89: 17: Repeat a code length of 0 for 3 - 10 times. cannam@89: (3 bits of length) cannam@89: 18: Repeat a code length of 0 for 11 - 138 times cannam@89: (7 bits of length) cannam@89: cannam@89: A code length of 0 indicates that the corresponding symbol in cannam@89: the literal/length or distance alphabet will not occur in the cannam@89: block, and should not participate in the Huffman code cannam@89: construction algorithm given earlier. If only one distance cannam@89: code is used, it is encoded using one bit, not zero bits; in cannam@89: this case there is a single code length of one, with one unused cannam@89: code. One distance code of zero bits means that there are no cannam@89: distance codes used at all (the data is all literals). cannam@89: cannam@89: We can now define the format of the block: cannam@89: cannam@89: 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286) cannam@89: 5 Bits: HDIST, # of Distance codes - 1 (1 - 32) cannam@89: 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19) cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 13] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: (HCLEN + 4) x 3 bits: code lengths for the code length cannam@89: alphabet given just above, in the order: 16, 17, 18, cannam@89: 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 cannam@89: cannam@89: These code lengths are interpreted as 3-bit integers cannam@89: (0-7); as above, a code length of 0 means the cannam@89: corresponding symbol (literal/length or distance code cannam@89: length) is not used. cannam@89: cannam@89: HLIT + 257 code lengths for the literal/length alphabet, cannam@89: encoded using the code length Huffman code cannam@89: cannam@89: HDIST + 1 code lengths for the distance alphabet, cannam@89: encoded using the code length Huffman code cannam@89: cannam@89: The actual compressed data of the block, cannam@89: encoded using the literal/length and distance Huffman cannam@89: codes cannam@89: cannam@89: The literal/length symbol 256 (end of data), cannam@89: encoded using the literal/length Huffman code cannam@89: cannam@89: The code length repeat codes can cross from HLIT + 257 to the cannam@89: HDIST + 1 code lengths. In other words, all code lengths form cannam@89: a single sequence of HLIT + HDIST + 258 values. cannam@89: cannam@89: 3.3. Compliance cannam@89: cannam@89: A compressor may limit further the ranges of values specified in cannam@89: the previous section and still be compliant; for example, it may cannam@89: limit the range of backward pointers to some value smaller than cannam@89: 32K. Similarly, a compressor may limit the size of blocks so that cannam@89: a compressible block fits in memory. cannam@89: cannam@89: A compliant decompressor must accept the full range of possible cannam@89: values defined in the previous section, and must accept blocks of cannam@89: arbitrary size. cannam@89: cannam@89: 4. Compression algorithm details cannam@89: cannam@89: While it is the intent of this document to define the "deflate" cannam@89: compressed data format without reference to any particular cannam@89: compression algorithm, the format is related to the compressed cannam@89: formats produced by LZ77 (Lempel-Ziv 1977, see reference [2] below); cannam@89: since many variations of LZ77 are patented, it is strongly cannam@89: recommended that the implementor of a compressor follow the general cannam@89: algorithm presented here, which is known not to be patented per se. cannam@89: The material in this section is not part of the definition of the cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 14] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: specification per se, and a compressor need not follow it in order to cannam@89: be compliant. cannam@89: cannam@89: The compressor terminates a block when it determines that starting a cannam@89: new block with fresh trees would be useful, or when the block size cannam@89: fills up the compressor's block buffer. cannam@89: cannam@89: The compressor uses a chained hash table to find duplicated strings, cannam@89: using a hash function that operates on 3-byte sequences. At any cannam@89: given point during compression, let XYZ be the next 3 input bytes to cannam@89: be examined (not necessarily all different, of course). First, the cannam@89: compressor examines the hash chain for XYZ. If the chain is empty, cannam@89: the compressor simply writes out X as a literal byte and advances one cannam@89: byte in the input. If the hash chain is not empty, indicating that cannam@89: the sequence XYZ (or, if we are unlucky, some other 3 bytes with the cannam@89: same hash function value) has occurred recently, the compressor cannam@89: compares all strings on the XYZ hash chain with the actual input data cannam@89: sequence starting at the current point, and selects the longest cannam@89: match. cannam@89: cannam@89: The compressor searches the hash chains starting with the most recent cannam@89: strings, to favor small distances and thus take advantage of the cannam@89: Huffman encoding. The hash chains are singly linked. There are no cannam@89: deletions from the hash chains; the algorithm simply discards matches cannam@89: that are too old. To avoid a worst-case situation, very long hash cannam@89: chains are arbitrarily truncated at a certain length, determined by a cannam@89: run-time parameter. cannam@89: cannam@89: To improve overall compression, the compressor optionally defers the cannam@89: selection of matches ("lazy matching"): after a match of length N has cannam@89: been found, the compressor searches for a longer match starting at cannam@89: the next input byte. If it finds a longer match, it truncates the cannam@89: previous match to a length of one (thus producing a single literal cannam@89: byte) and then emits the longer match. Otherwise, it emits the cannam@89: original match, and, as described above, advances N bytes before cannam@89: continuing. cannam@89: cannam@89: Run-time parameters also control this "lazy match" procedure. If cannam@89: compression ratio is most important, the compressor attempts a cannam@89: complete second search regardless of the length of the first match. cannam@89: In the normal case, if the current match is "long enough", the cannam@89: compressor reduces the search for a longer match, thus speeding up cannam@89: the process. If speed is most important, the compressor inserts new cannam@89: strings in the hash table only when no match was found, or when the cannam@89: match is not "too long". This degrades the compression ratio but cannam@89: saves time since there are both fewer insertions and fewer searches. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 15] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 5. References cannam@89: cannam@89: [1] Huffman, D. A., "A Method for the Construction of Minimum cannam@89: Redundancy Codes", Proceedings of the Institute of Radio cannam@89: Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101. cannam@89: cannam@89: [2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data cannam@89: Compression", IEEE Transactions on Information Theory, Vol. 23, cannam@89: No. 3, pp. 337-343. cannam@89: cannam@89: [3] Gailly, J.-L., and Adler, M., ZLIB documentation and sources, cannam@89: available in ftp://ftp.uu.net/pub/archiving/zip/doc/ cannam@89: cannam@89: [4] Gailly, J.-L., and Adler, M., GZIP documentation and sources, cannam@89: available as gzip-*.tar in ftp://prep.ai.mit.edu/pub/gnu/ cannam@89: cannam@89: [5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix cannam@89: encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169. cannam@89: cannam@89: [6] Hirschberg and Lelewer, "Efficient decoding of prefix codes," cannam@89: Comm. ACM, 33,4, April 1990, pp. 449-459. cannam@89: cannam@89: 6. Security Considerations cannam@89: cannam@89: Any data compression method involves the reduction of redundancy in cannam@89: the data. Consequently, any corruption of the data is likely to have cannam@89: severe effects and be difficult to correct. Uncompressed text, on cannam@89: the other hand, will probably still be readable despite the presence cannam@89: of some corrupted bytes. cannam@89: cannam@89: It is recommended that systems using this data format provide some cannam@89: means of validating the integrity of the compressed data. See cannam@89: reference [3], for example. cannam@89: cannam@89: 7. Source code cannam@89: cannam@89: Source code for a C language implementation of a "deflate" compliant cannam@89: compressor and decompressor is available within the zlib package at cannam@89: ftp://ftp.uu.net/pub/archiving/zip/zlib/. cannam@89: cannam@89: 8. Acknowledgements cannam@89: cannam@89: Trademarks cited in this document are the property of their cannam@89: respective owners. cannam@89: cannam@89: Phil Katz designed the deflate format. Jean-Loup Gailly and Mark cannam@89: Adler wrote the related software described in this specification. cannam@89: Glenn Randers-Pehrson converted this document to RFC and HTML format. cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 16] cannam@89: cannam@89: RFC 1951 DEFLATE Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 9. Author's Address cannam@89: cannam@89: L. Peter Deutsch cannam@89: Aladdin Enterprises cannam@89: 203 Santa Margarita Ave. cannam@89: Menlo Park, CA 94025 cannam@89: cannam@89: Phone: (415) 322-0103 (AM only) cannam@89: FAX: (415) 322-1734 cannam@89: EMail: cannam@89: cannam@89: Questions about the technical content of this specification can be cannam@89: sent by email to: cannam@89: cannam@89: Jean-Loup Gailly and cannam@89: Mark Adler cannam@89: cannam@89: Editorial comments on this specification can be sent by email to: cannam@89: cannam@89: L. Peter Deutsch and cannam@89: Glenn Randers-Pehrson cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch Informational [Page 17] cannam@89: