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