< draft-deutsch-deflate-spec-01.txt   draft-deutsch-deflate-spec-02.txt >
INTERNET-DRAFT L. P. Deutsch INTERNET-DRAFT L. Peter Deutsch
DEFLATE 1.3 Aladdin Enterprises DEFLATE 1.3 Aladdin Enterprises
Expires: 17 Aug 1996 12 Feb 1996 Expires: 16 Sep 1996 11 Mar 1996
DEFLATE Compressed Data Format Specification version 1.3 DEFLATE Compressed Data Format Specification version 1.3
File draft-deutsch-deflate-spec-01.txt File draft-deutsch-deflate-spec-02.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
skipping to change at line 30 skipping to change at line 30
material or to cite them other than as ``work in progress.'' material or to cite them other than as ``work in progress.''
To learn the current status of any Internet-Draft, please check the To learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the Internet- Drafts ``1id-abstracts.txt'' listing contained in the Internet- Drafts
Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast). ftp.isi.edu (US West Coast).
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
Notices Notices
Copyright (C) 1996 L. Peter Deutsch Copyright (c) 1996 L. Peter Deutsch
Permission is granted to copy and distribute this document for any Permission is granted to copy and distribute this document for any
purpose and without charge, including translations into other purpose and without charge, including translations into other
languages and incorporation into compilations, provided that it is languages and incorporation into compilations, provided that it is
copied as a whole (including the copyright notice and this notice) copied as a whole (including the copyright notice and this notice)
and with no changes. and with no changes.
Deutsch [Page 1]
Abstract Abstract
This specification defines a lossless compressed data format that This specification defines a lossless compressed data format that
compresses data using a combination of the LZ77 algorithm and Huffman compresses data using a combination of the LZ77 algorithm and Huffman
coding, with efficiency comparable to the best currently available coding, with efficiency comparable to the best currently available
general-purpose compression methods. The data can be produced or general-purpose compression methods. The data can be produced or
consumed, even for an arbitrarily long sequentially presented input consumed, even for an arbitrarily long sequentially presented input
data stream, using only an a priori bounded amount of intermediate data stream, using only an a priori bounded amount of intermediate
storage. The format can be implemented readily in a manner not storage. The format can be implemented readily in a manner not
covered by patents. covered by patents.
Deutsch [Page 1]
Table of Contents Table of Contents
1. Introduction ................................................... 2 1. Introduction ................................................... 2
1.1 Purpose .................................................... 2 1.1. Purpose ................................................... 3
1.2 Intended audience .......................................... 3 1.2. Intended audience ......................................... 3
1.3 Scope ...................................................... 3 1.3. Scope ..................................................... 3
1.4 Compliance ................................................. 3 1.4. Compliance ................................................ 4
1.5 Definitions of terms and conventions used ................. 3 1.5. Definitions of terms and conventions used ................ 4
1.6 Changes from previous versions ............................. 4 1.6. Changes from previous versions ............................ 4
2. Compressed representation overview ............................. 4 2. Compressed representation overview ............................. 4
3. Detailed specification ......................................... 4 3. Detailed specification ......................................... 5
3.1 Overall conventions ........................................ 4 3.1. Overall conventions ....................................... 5
3.1.1. Packing into bytes .................................. 5 3.1.1. Packing into bytes .................................. 5
3.2 Compressed block format .................................... 6 3.2. Compressed block format ................................... 6
3.2.1. Synopsis of prefix and Huffman coding ............... 6 3.2.1. Synopsis of prefix and Huffman coding ............... 6
3.2.2. Use of Huffman coding in the 'deflate' format ....... 7 3.2.2. Use of Huffman coding in the 'deflate' format ....... 7
3.2.3. Details of block format ............................. 8 3.2.3. Details of block format ............................. 9
3.2.4. Non-compressed blocks (BTYPE=00) ................... 10 3.2.4. Non-compressed blocks (BTYPE=00) ................... 10
3.2.5. Compressed blocks (length and distance codes) ...... 10 3.2.5. Compressed blocks (length and distance codes) ...... 11
3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 11 3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 11
3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 11 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 12
3.3 Compliance ................................................ 13 3.3. Compliance ............................................... 13
4. Compression algorithm details ................................. 13 4. Compression algorithm details ................................. 14
5. References .................................................... 14 5. References .................................................... 15
6. Security considerations ....................................... 14 6. Security considerations ....................................... 15
7. Source code ................................................... 15 7. Source code ................................................... 15
8. Acknowledgements .............................................. 15 8. Acknowledgements .............................................. 16
9. Author's address .............................................. 15 9. Author's address .............................................. 16
1. Introduction 1. Introduction
Deutsch [Page 2]
1.1. Purpose 1.1. Purpose
The purpose of this specification is to define a lossless The purpose of this specification is to define a lossless
compressed data format that: compressed data format that:
o Is independent of CPU type, operating system, file system, * Is independent of CPU type, operating system, file system,
and character set, and hence can be used for interchange; and character set, and hence can be used for interchange;
o Can be produced or consumed, even for an arbitrarily long * Can be produced or consumed, even for an arbitrarily long
sequentially presented input data stream, using only an a sequentially presented input data stream, using only an a
priori bounded amount of intermediate storage, and hence can priori bounded amount of intermediate storage, and hence can
be used in data communications or similar structures such as be used in data communications or similar structures such as
Unix filters; Unix filters;
o Compresses data with efficiency comparable to the best * Compresses data with efficiency comparable to the best
currently available general-purpose compression methods, and currently available general-purpose compression methods, and
in particular considerably better than the 'compress' in particular considerably better than the 'compress'
program; program;
o Can be implemented readily in a manner not covered by * Can be implemented readily in a manner not covered by
patents, and hence can be practiced freely; patents, and hence can be practiced freely;
o Is compatible with the file format produced by the current * Is compatible with the file format produced by the current
widely used gzip utility, in that conforming decompressors widely used gzip utility, in that conforming decompressors
will be able to read data produced by the existing gzip will be able to read data produced by the existing gzip
Deutsch [Page 2]
compressor. compressor.
The data format defined by this specification does not attempt to: The data format defined by this specification does not attempt to:
o Allow random access to compressed data; * Allow random access to compressed data;
o Compress specialized data (e.g., raster graphics) as well as * Compress specialized data (e.g., raster graphics) as well as
the best currently available specialized algorithms. the best currently available specialized algorithms.
A simple counting argument shows that no lossless compression A simple counting argument shows that no lossless compression
algorithm can compress every possible input data set. For the algorithm can compress every possible input data set. For the
format defined here, the worst case expansion is 5 bytes per 32K- format defined here, the worst case expansion is 5 bytes per 32K-
byte block, i.e., a size increase of 0.015% for large data sets. byte block, i.e., a size increase of 0.015% for large data sets.
English text usually compresses by a factor of 2.5 to 3; English text usually compresses by a factor of 2.5 to 3;
executable files usually compress somewhat less; graphical data executable files usually compress somewhat less; graphical data
such as raster images may compress much more. such as raster images may compress much more.
skipping to change at line 137 skipping to change at line 136
The text of the specification assumes a basic background in The text of the specification assumes a basic background in
programming at the level of bits and other primitive data programming at the level of bits and other primitive data
representations. Familiarity with the technique of Huffman coding representations. Familiarity with the technique of Huffman coding
is helpful but not required. is helpful but not required.
1.3. Scope 1.3. Scope
The specification specifies a method for representing a sequence The specification specifies a method for representing a sequence
of bytes as a (usually shorter) sequence of bits, and a method for of bytes as a (usually shorter) sequence of bits, and a method for
Deutsch [Page 3]
packing the latter bit sequence into bytes. packing the latter bit sequence into bytes.
1.4. Compliance 1.4. Compliance
Unless otherwise indicated below, a compliant decompressor must be Unless otherwise indicated below, a compliant decompressor must be
able to accept and decompress any data set that conforms to all able to accept and decompress any data set that conforms to all
the specifications presented here; a compliant compressor must the specifications presented here; a compliant compressor must
produce data sets that conform to all the specifications presented produce data sets that conform to all the specifications presented
here. here.
1.5. Definitions of terms and conventions used 1.5. Definitions of terms and conventions used
byte: 8 bits stored or transmitted as a unit (same as an octet). Byte: 8 bits stored or transmitted as a unit (same as an octet).
(For this specification, a byte is exactly 8 bits, even on For this specification, a byte is exactly 8 bits, even on machines
machines which store a character on a number of bits different which store a character on a number of bits different from eight.
from 8.) See Section 3.1, below, for the numbering of bits within See below, for the numbering of bits within a byte.
a byte.
string: a sequence of arbitrary bytes. String: a sequence of arbitrary bytes.
1.6. Changes from previous versions 1.6. Changes from previous versions
Deutsch [Page 3]
There have been no technical changes to the deflate format since There have been no technical changes to the deflate format since
version 1.1 of this specification. In version 1.2, some version 1.1 of this specification. In version 1.2, some
terminology was changed. Version 1.3 is a conversion of the terminology was changed. Version 1.3 is a conversion of the
specification to Internet Draft style. specification to Internet Draft style.
2. Compressed representation overview 2. Compressed representation overview
A compressed data set consists of a series of blocks, corresponding A compressed data set consists of a series of blocks, corresponding
to successive blocks of input data. The block sizes are arbitrary, to successive blocks of input data. The block sizes are arbitrary,
except that non-compressible blocks are limited to 65,535 bytes. except that non-compressible blocks are limited to 65,535 bytes.
skipping to change at line 191 skipping to change at line 190
elements of two types: literal bytes (of strings that have not been elements of two types: literal bytes (of strings that have not been
detected as duplicated within the previous 32K input bytes), and detected as duplicated within the previous 32K input bytes), and
pointers to duplicated strings, where a pointer is represented as a pointers to duplicated strings, where a pointer is represented as a
pair <length, backward distance>. The representation used in the pair <length, backward distance>. The representation used in the
'deflate' format limits distances to 32K bytes and lengths to 258 'deflate' format limits distances to 32K bytes and lengths to 258
bytes, but does not limit the size of a block, except for bytes, but does not limit the size of a block, except for
uncompressible blocks, which are limited as noted above. uncompressible blocks, which are limited as noted above.
Each type of value (literals, distances, and lengths) in the Each type of value (literals, distances, and lengths) in the
compressed data is represented using a Huffman code, using one code compressed data is represented using a Huffman code, using one code
Deutsch [Page 4]
tree for literals and lengths and a separate code tree for distances. tree for literals and lengths and a separate code tree for distances.
The code trees for each block appear in a compact form just before The code trees for each block appear in a compact form just before
the compressed data for that block. the compressed data for that block.
3. Detailed specification 3. Detailed specification
3.1. Overall conventions In the diagrams below, a box like this: 3.1. Overall conventions In the diagrams below, a box like this:
+---+ +---+
| | <-- the vertical bars might be missing | | <-- the vertical bars might be missing
skipping to change at line 212 skipping to change at line 213
represents one byte; a box like this: represents one byte; a box like this:
+==============+ +==============+
| | | |
+==============+ +==============+
represents a variable number of bytes. represents a variable number of bytes.
Bytes stored within a computer do not have a 'bit order', since Bytes stored within a computer do not have a 'bit order', since
Deutsch [Page 4]
they are always treated as a unit. However, a byte considered as they are always treated as a unit. However, a byte considered as
an integer between 0 and 255 does have a most- and least- an integer between 0 and 255 does have a most- and least-
significant bit, and since we write numbers with the most- significant bit, and since we write numbers with the most-
significant digit on the left, we also write bytes with the most- significant digit on the left, we also write bytes with the most-
significant bit on the left. In the diagrams below, we number the significant bit on the left. In the diagrams below, we number the
bits of a byte so that bit 0 is the least-significant bit, i.e., bits of a byte so that bit 0 is the least-significant bit, i.e.,
the bits are numbered: the bits are numbered:
+--------+ +--------+
|76543210| |76543210|
skipping to change at line 245 skipping to change at line 244
^ ^ ^ ^
| | | |
| + more significant byte = 2 x 256 | + more significant byte = 2 x 256
+ less significant byte = 8 + less significant byte = 8
3.1.1. Packing into bytes 3.1.1. Packing into bytes
This document does not address the issue of the order in which This document does not address the issue of the order in which
bits of a byte are transmitted on a bit-sequential medium, bits of a byte are transmitted on a bit-sequential medium,
since the final data format described here is byte- rather than since the final data format described here is byte- rather than
Deutsch [Page 5]
bit-oriented. However, we describe the compressed block format bit-oriented. However, we describe the compressed block format
in Section 3.2, below, as a sequence of data elements of in below, as a sequence of data elements of various bit
various bit lengths, not a sequence of bytes. We must lengths, not a sequence of bytes. We must therefore specify
therefore specify how to pack these data elements into bytes to how to pack these data elements into bytes to form the final
form the final compressed byte sequence: compressed byte sequence:
o Data elements are packed into bytes in order of * Data elements are packed into bytes in order of
increasing bit number within the byte, i.e., starting increasing bit number within the byte, i.e., starting
with the least- significant bit of the byte. with the least- significant bit of the byte.
o Data elements other than Huffman codes are packed * Data elements other than Huffman codes are packed
starting with the least-significant bit of the data starting with the least-significant bit of the data
element. element.
o Huffman codes are packed starting with the most- * Huffman codes are packed starting with the most-
significant bit of the code. significant bit of the code.
In other words, if one were to print out the compressed data as In other words, if one were to print out the compressed data as
a sequence of bytes, starting with the first byte at the a sequence of bytes, starting with the first byte at the
*right* margin and proceeding to the *left*, with the most- *right* margin and proceeding to the *left*, with the most-
significant bit of each byte on the left as usual, one would be significant bit of each byte on the left as usual, one would be
able to parse the result from right to left, with fixed-width able to parse the result from right to left, with fixed-width
elements in the correct MSB-to-LSB order and Huffman codes in elements in the correct MSB-to-LSB order and Huffman codes in
Deutsch [Page 5]
bit-reversed order (i.e., with the first bit of the code in the bit-reversed order (i.e., with the first bit of the code in the
relative LSB position). relative LSB position).
3.2. Compressed block format 3.2. Compressed block format
3.2.1. Synopsis of prefix and Huffman coding 3.2.1. Synopsis of prefix and Huffman coding
Prefix coding represents symbols from an a priori known Prefix coding represents symbols from an a priori known
alphabet by bit sequences (codes), one code for each symbol, in alphabet by bit sequences (codes), one code for each symbol, in
a manner such that different symbols may be represented by bit a manner such that different symbols may be represented by bit
skipping to change at line 299 skipping to change at line 298
0 1 ------ ---- 0 1 ------ ----
/ \ A 00 / \ A 00
/\ B B 1 /\ B B 1
0 1 C 011 0 1 C 011
/ \ D 010 / \ D 010
A /\ A /\
0 1 0 1
/ \ / \
D C D C
Deutsch [Page 6]
A parser can decode the next symbol from an encoded input A parser can decode the next symbol from an encoded input
stream by walking down the tree from the root, at each step stream by walking down the tree from the root, at each step
choosing the edge corresponding to the next input bit. choosing the edge corresponding to the next input bit.
Given an alphabet with known symbol frequencies, the Huffman Given an alphabet with known symbol frequencies, the Huffman
algorithm allows the construction of an optimal prefix code algorithm allows the construction of an optimal prefix code
(one which represents strings with those symbol frequencies (one which represents strings with those symbol frequencies
using the fewest bits of any possible prefix codes for that using the fewest bits of any possible prefix codes for that
alphabet). Such a code is called a Huffman code. (See alphabet). Such a code is called a Huffman code. (See
reference [1] in Chapter 5, references for additional reference [1] in Chapter 5, references for additional
skipping to change at line 320 skipping to change at line 320
Note that in the 'deflate' format, the Huffman codes for the Note that in the 'deflate' format, the Huffman codes for the
various alphabets must not exceed certain maximum code lengths. various alphabets must not exceed certain maximum code lengths.
This constraint complicates the algorithm for computing code This constraint complicates the algorithm for computing code
lengths from symbol frequencies. Again, see Chapter 5, lengths from symbol frequencies. Again, see Chapter 5,
references for details. references for details.
3.2.2. Use of Huffman coding in the 'deflate' format 3.2.2. Use of Huffman coding in the 'deflate' format
The Huffman codes used for each alphabet in the 'deflate' The Huffman codes used for each alphabet in the 'deflate'
Deutsch [Page 6]
format have two additional rules: format have two additional rules:
o All codes of a given bit length have lexicographically * All codes of a given bit length have lexicographically
consecutive values, in the same order as the symbols they consecutive values, in the same order as the symbols they
represent; represent;
o Shorter codes lexicographically precede longer codes. * Shorter codes lexicographically precede longer codes.
We could recode the example above to follow this rule as We could recode the example above to follow this rule as
follows, assuming that the order of the alphabet is ABCD: follows, assuming that the order of the alphabet is ABCD:
Symbol Code Symbol Code
------ ---- ------ ----
A 10 A 10
B 0 B 0
C 110 C 110
D 111 D 111
skipping to change at line 353 skipping to change at line 351
Given this rule, we can define the Huffman code for an alphabet Given this rule, we can define the Huffman code for an alphabet
just by giving the bit lengths of the codes for each symbol of just by giving the bit lengths of the codes for each symbol of
the alphabet in order; this is sufficient to determine the the alphabet in order; this is sufficient to determine the
actual codes. In our example, the code is completely defined actual codes. In our example, the code is completely defined
by the sequence of bit lengths (2, 1, 3, 3). The following by the sequence of bit lengths (2, 1, 3, 3). The following
algorithm generates the codes as integers, intended to be read algorithm generates the codes as integers, intended to be read
from most- to least-significant bit. The code lengths are from most- to least-significant bit. The code lengths are
initially in tree[I].Len; the codes are produced in initially in tree[I].Len; the codes are produced in
tree[I].Code. tree[I].Code.
Deutsch [Page 7]
1) Count the number of codes for each code length. Let 1) Count the number of codes for each code length. Let
bl_count[N] be the number of codes of length N, N >= 1. bl_count[N] be the number of codes of length N, N >= 1.
2) Find the numerical value of the smallest code for each code 2) Find the numerical value of the smallest code for each code
length: length:
code = 0; code = 0;
bl_count[0] = 0; bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) { for (bits = 1; bits <= MAX_BITS; bits++) {
next_code[bits] = code next_code[bits] = code
skipping to change at line 374 skipping to change at line 373
} }
3) Assign numerical values to all codes, using consecutive 3) Assign numerical values to all codes, using consecutive
values for all codes of the same length with the base values values for all codes of the same length with the base values
determined at step 2. Codes that are never used (which have a determined at step 2. Codes that are never used (which have a
bit length of zero) must not be assigned a value. bit length of zero) must not be assigned a value.
for (n = 0; n <= max_code; n++) { for (n = 0; n <= max_code; n++) {
len = tree[n].Len; len = tree[n].Len;
if (len == 0) continue; if (len == 0) continue;
Deutsch [Page 7]
tree[n].Code = next_code[len]++; tree[n].Code = next_code[len]++;
} }
Example: Example:
Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3,
3, 2, 4, 4). After step 1, we have: 3, 2, 4, 4). After step 1, we have:
N bl_count[N] N bl_count[N]
- ----------- - -----------
skipping to change at line 401 skipping to change at line 398
N next_code[N] N next_code[N]
- ------------ - ------------
1 0 1 0
2 0 2 0
3 2 3 2
4 14 4 14
Step 3 produces the following code values: Step 3 produces the following code values:
Deutsch [Page 8]
Symbol Length Code Symbol Length Code
------ ------ ---- ------ ------ ----
A 3 010 A 3 010
B 3 011 B 3 011
C 3 100 C 3 100
D 3 101 D 3 101
E 3 110 E 3 110
F 2 00 F 2 00
G 4 1110 G 4 1110
H 4 1111 H 4 1111
skipping to change at line 426 skipping to change at line 424
first bit BFINAL first bit BFINAL
next 2 bits BTYPE next 2 bits BTYPE
Note that the header bits do not necessarily begin on a byte Note that the header bits do not necessarily begin on a byte
boundary, since a block does not necessarily occupy an integral boundary, since a block does not necessarily occupy an integral
number of bytes. number of bytes.
BFINAL is set iff this is the last block of the data set. BFINAL is set iff this is the last block of the data set.
Deutsch [Page 8]
BTYPE specifies how the data are compressed, as follows: BTYPE specifies how the data are compressed, as follows:
00 - no compression 00 - no compression
01 - compressed with fixed Huffman codes 01 - compressed with fixed Huffman codes
10 - compressed with dynamic Huffman codes 10 - compressed with dynamic Huffman codes
11 - reserved (error) 11 - reserved (error)
The only difference between the two compressed cases is how the The only difference between the two compressed cases is how the
Huffman codes for the literal/length and distance alphabets are Huffman codes for the literal/length and distance alphabets are
defined. defined.
In all cases, the decoding algorithm for the actual data is as In all cases, the decoding algorithm for the actual data is as
follows: follows:
Deutsch [Page 9]
do do
read block header from input stream. read block header from input stream.
if stored with no compression if stored with no compression
skip any remaining bits in current partially skip any remaining bits in current partially
processed byte processed byte
read LEN and NLEN (see next section) read LEN and NLEN (see next section)
copy LEN bytes of data to output copy LEN bytes of data to output
otherwise otherwise
if compressed with dynamic Huffman codes if compressed with dynamic Huffman codes
read representation of code trees (see read representation of code trees (see
skipping to change at line 479 skipping to change at line 477
in a previous block; i.e., the backward distance may cross one in a previous block; i.e., the backward distance may cross one
or more block boundaries. However a distance cannot refer past or more block boundaries. However a distance cannot refer past
the beginning of the output stream. (An application using a the beginning of the output stream. (An application using a
preset dictionary might discard part of the output stream; a preset dictionary might discard part of the output stream; a
distance can refer to that part of the output stream anyway) distance can refer to that part of the output stream anyway)
Note also that the referenced string may overlap the current Note also that the referenced string may overlap the current
position; for example, if the last 2 bytes decoded have values position; for example, if the last 2 bytes decoded have values
X and Y, a string reference with <length = 5, distance = 2> X and Y, a string reference with <length = 5, distance = 2>
adds X,Y,X,Y,X to the output stream. adds X,Y,X,Y,X to the output stream.
Deutsch [Page 9]
We now specify each compression method in turn. We now specify each compression method in turn.
3.2.4. Non-compressed blocks (BTYPE=00) 3.2.4. Non-compressed blocks (BTYPE=00)
Any bits of input up to the next byte boundary are ignored. Any bits of input up to the next byte boundary are ignored.
The rest of the block consists of the following information: The rest of the block consists of the following information:
0 1 2 3 4... 0 1 2 3 4...
+---+---+---+---+=================================+ +---+---+---+---+=================================+
| LEN | NLEN |... LEN bytes of literal data...| | LEN | NLEN |... LEN bytes of literal data...|
+---+---+---+---+=================================+ +---+---+---+---+=================================+
LEN is the number of data bytes in the block. NLEN is the LEN is the number of data bytes in the block. NLEN is the
one's complement of LEN. one's complement of LEN.
Deutsch [Page 10]
3.2.5. Compressed blocks (length and distance codes) 3.2.5. Compressed blocks (length and distance codes)
As noted above, encoded data blocks in the 'deflate' format As noted above, encoded data blocks in the 'deflate' format
consist of sequences of symbols drawn from three conceptually consist of sequences of symbols drawn from three conceptually
distinct alphabets: either literal bytes, from the alphabet of distinct alphabets: either literal bytes, from the alphabet of
byte values (0..255), or <length, backward distance> pairs, byte values (0..255), or <length, backward distance> pairs,
where the length is drawn from (3..258) and the distance is where the length is drawn from (3..258) and the distance is
drawn from (1..32,768). In fact, the literal and length drawn from (1..32,768). In fact, the literal and length
alphabets are merged into a single alphabet (0..285), where alphabets are merged into a single alphabet (0..285), where
values 0..255 represent literal bytes, the value 256 indicates values 0..255 represent literal bytes, the value 256 indicates
skipping to change at line 525 skipping to change at line 523
260 0 6 270 2 23-26 280 4 115-130 260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162 261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194 262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226 263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257 264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258 265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66 266 1 13,14 276 3 59-66
The extra bits should be interpreted as a machine integer The extra bits should be interpreted as a machine integer
stored with the most-significant bit first, e.g., bits 1110 stored with the most-significant bit first, e.g., bits 1110
Deutsch [Page 10]
represent the value 14. represent the value 14.
Extra Extra Extra Extra Extra Extra
Code Bits Dist Code Bits Dist Code Bits Distance Code Bits Dist Code Bits Dist Code Bits Distance
---- ---- ---- ---- ---- ------ ---- ---- -------- ---- ---- ---- ---- ---- ------ ---- ---- --------
0 0 1 10 4 33-48 20 9 1025-1536 0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048 1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072 2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096 3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144 4 1 5,6 14 6 129-192 24 11 4097-6144
skipping to change at line 549 skipping to change at line 545
7 2 13-16 17 7 385-512 27 12 12289-16384 7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576 8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768 9 3 25-32 19 8 769-1024 29 13 24577-32768
3.2.6. Compression with fixed Huffman codes (BTYPE=01) 3.2.6. Compression with fixed Huffman codes (BTYPE=01)
The Huffman codes for the two alphabets are fixed, and are not The Huffman codes for the two alphabets are fixed, and are not
represented explicitly in the data. The Huffman code lengths represented explicitly in the data. The Huffman code lengths
for the literal/length alphabet are: for the literal/length alphabet are:
Deutsch [Page 11]
Lit Value Bits Codes Lit Value Bits Codes
--------- ---- ----- --------- ---- -----
0 - 143 8 00110000 through 0 - 143 8 00110000 through
10111111 10111111
144 - 255 9 110010000 through 144 - 255 9 110010000 through
111111111 111111111
256 - 279 7 0000000 through 256 - 279 7 0000000 through
0010111 0010111
280 - 287 8 11000000 through 280 - 287 8 11000000 through
11000111 11000111
skipping to change at line 579 skipping to change at line 576
31 will never actually occur in the compressed data. 31 will never actually occur in the compressed data.
3.2.7. Compression with dynamic Huffman codes (BTYPE=10) 3.2.7. Compression with dynamic Huffman codes (BTYPE=10)
The Huffman codes for the two alphabets appear in the block The Huffman codes for the two alphabets appear in the block
immediately after the header bits and before the actual immediately after the header bits and before the actual
compressed data, first the literal/length code and then the compressed data, first the literal/length code and then the
distance code. Each code is defined by a sequence of code distance code. Each code is defined by a sequence of code
lengths, as discussed in Paragraph 3.2.2, above. For even lengths, as discussed in Paragraph 3.2.2, above. For even
greater compactness, the code length sequences themselves are greater compactness, the code length sequences themselves are
Deutsch [Page 11]
compressed using a Huffman code. The alphabet for code lengths compressed using a Huffman code. The alphabet for code lengths
is as follows: is as follows:
0 - 15: Represent code lengths of 0 - 15 0 - 15: Represent code lengths of 0 - 15
16: Copy the previous code length 3 - 6 times. 16: Copy the previous code length 3 - 6 times.
The next 2 bits indicate repeat length The next 2 bits indicate repeat length
(0 = 3, ... , 3 = 6) (0 = 3, ... , 3 = 6)
Example: Codes 8, 16 (+2 bits 11), Example: Codes 8, 16 (+2 bits 11),
16 (+2 bits 10) will expand to 16 (+2 bits 10) will expand to
12 code lengths of 8 (1 + 6 + 5) 12 code lengths of 8 (1 + 6 + 5)
skipping to change at line 603 skipping to change at line 598
18: Repeat a code length of 0 for 11 - 138 times 18: Repeat a code length of 0 for 11 - 138 times
(7 bits of length) (7 bits of length)
A code length of 0 indicates that the corresponding symbol in A code length of 0 indicates that the corresponding symbol in
the literal/length or distance alphabet will not occur in the the literal/length or distance alphabet will not occur in the
block, and should not participate in the Huffman code block, and should not participate in the Huffman code
construction algorithm given earlier. If only one distance construction algorithm given earlier. If only one distance
code is used, it is encoded using one bit, not zero bits; in code is used, it is encoded using one bit, not zero bits; in
this case there is a single code length of one, with one unused this case there is a single code length of one, with one unused
code. One distance code of zero bits means that there are no code. One distance code of zero bits means that there are no
Deutsch [Page 12]
distance codes used at all (the data is all literals). distance codes used at all (the data is all literals).
We can now define the format of the block: We can now define the format of the block:
5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286) 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
5 Bits: HDIST, # of Distance codes - 1 (1 - 32) 5 Bits: HDIST, # of Distance codes - 1 (1 - 32)
4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19) 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)
(HCLEN + 4) x 3 bits: code lengths for the code length (HCLEN + 4) x 3 bits: code lengths for the code length
alphabet given just above, in the order: 16, 17, 18, alphabet given just above, in the order: 16, 17, 18,
skipping to change at line 633 skipping to change at line 630
HDIST + 1 code lengths for the distance alphabet, HDIST + 1 code lengths for the distance alphabet,
encoded using the code length Huffman code encoded using the code length Huffman code
The actual compressed data of the block, The actual compressed data of the block,
encoded using the literal/length and distance Huffman encoded using the literal/length and distance Huffman
codes codes
The literal/length symbol 256 (end of data), The literal/length symbol 256 (end of data),
encoded using the literal/length Huffman code encoded using the literal/length Huffman code
Deutsch [Page 12]
The code length repeat codes can cross from HLIT + 257 to the The code length repeat codes can cross from HLIT + 257 to the
HDIST + 1 code lengths. In other words, all code lengths form HDIST + 1 code lengths. In other words, all code lengths form
a single sequence of HLIT + HDIST + 258 values. a single sequence of HLIT + HDIST + 258 values.
3.3. Compliance 3.3. Compliance
A compressor may limit further the ranges of values specified in A compressor may limit further the ranges of values specified in
the previous section and still be compliant; for example, it may the previous section and still be compliant; for example, it may
limit the range of backward pointers to some value smaller than limit the range of backward pointers to some value smaller than
32K. Similarly, a compressor may limit the size of blocks so that 32K. Similarly, a compressor may limit the size of blocks so that
a compressible block fits in memory. a compressible block fits in memory.
A compliant decompressor must accept the full range of possible A compliant decompressor must accept the full range of possible
values defined in the previous section, and must accept blocks of values defined in the previous section, and must accept blocks of
arbitrary size. arbitrary size.
Deutsch [Page 13]
4. Compression algorithm details 4. Compression algorithm details
While it is the intent of this document to define the 'deflate' While it is the intent of this document to define the 'deflate'
compressed data format without reference to any particular compressed data format without reference to any particular
compression algorithm, the format is related to the compressed compression algorithm, the format is related to the compressed
formats produced by LZ77 (Lempel-Ziv 1977, see reference [2] below); formats produced by LZ77 (Lempel-Ziv 1977, see reference [2] below);
since many variations of LZ77 are patented, it is strongly since many variations of LZ77 are patented, it is strongly
recommended that the implementor of a compressor follow the general recommended that the implementor of a compressor follow the general
algorithm presented here, which is known not to be patented per se. algorithm presented here, which is known not to be patented per se.
The material in this section is not part of the definition of the The material in this section is not part of the definition of the
skipping to change at line 686 skipping to change at line 683
compares all strings on the XYZ hash chain with the actual input data compares all strings on the XYZ hash chain with the actual input data
sequence starting at the current point, and selects the longest sequence starting at the current point, and selects the longest
match. match.
The compressor searches the hash chains starting with the most recent The compressor searches the hash chains starting with the most recent
strings, to favor small distances and thus take advantage of the strings, to favor small distances and thus take advantage of the
Huffman encoding. The hash chains are singly linked. There are no Huffman encoding. The hash chains are singly linked. There are no
deletions from the hash chains; the algorithm simply discards matches deletions from the hash chains; the algorithm simply discards matches
that are too old. To avoid a worst-case situation, very long hash that are too old. To avoid a worst-case situation, very long hash
chains are arbitrarily truncated at a certain length, determined by a chains are arbitrarily truncated at a certain length, determined by a
Deutsch [Page 13]
run-time parameter. run-time parameter.
To improve overall compression, the compressor optionally defers the To improve overall compression, the compressor optionally defers the
selection of matches ("lazy matching"): after a match of length N has selection of matches ("lazy matching"): after a match of length N has
been found, the compressor searches for a longer match starting at been found, the compressor searches for a longer match starting at
the next input byte. If it finds a longer match, it truncates the the next input byte. If it finds a longer match, it truncates the
previous match to a length of one (thus producing a single literal previous match to a length of one (thus producing a single literal
byte) and then emits the longer match. Otherwise, it emits the byte) and then emits the longer match. Otherwise, it emits the
original match, and, as described above, advances N bytes before original match, and, as described above, advances N bytes before
continuing. continuing.
Run-time parameters also control this "lazy match" procedure. If Run-time parameters also control this "lazy match" procedure. If
compression ratio is most important, the compressor attempts a compression ratio is most important, the compressor attempts a
complete second search regardless of the length of the first match. complete second search regardless of the length of the first match.
In the normal case, if the current match is "long enough", the In the normal case, if the current match is "long enough", the
compressor reduces the search for a longer match, thus speeding up compressor reduces the search for a longer match, thus speeding up
Deutsch [Page 14]
the process. If speed is most important, the compressor inserts new the process. If speed is most important, the compressor inserts new
strings in the hash table only when no match was found, or when the strings in the hash table only when no match was found, or when the
match is not "too long". This degrades the compression ratio but match is not "too long". This degrades the compression ratio but
saves time since there are both fewer insertions and fewer searches. saves time since there are both fewer insertions and fewer searches.
5. References 5. References
[1] Huffman, D. A., "A Method for the Construction of Minimum [1] Huffman, D. A., "A Method for the Construction of Minimum
Redundancy Codes", Proceedings of the Institute of Radio Engineers, Redundancy Codes", Proceedings of the Institute of Radio
September 1952, Volume 40, Number 9, pp. 1098-1101. Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.
[2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data [2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
Compression", IEEE Transactions on Information Theory", Vol. 23, No. Compression", IEEE Transactions on Information Theory, Vol. 23,
3, pp. 337-343. No. 3, pp. 337-343.
[3] Gailly, J.-L., and Adler, M., zlib documentation and sources, [3] Gailly, J.-L., and Adler, M., zlib documentation and sources,
available in ftp.uu.net:/pub/archiving/zip/doc/zlib* available in ftp.uu.net:/pub/archiving/zip/doc/zlib*
[4] Gailly, J.-L., and Adler, M., gzip documentation and sources, [4] Gailly, J.-L., and Adler, M., gzip documentation and sources,
available in prep.ai.mit.edu:/pub/gnu/gzip-*.tar available in prep.ai.mit.edu:/pub/gnu/gzip-*.tar
[5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix [5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix
encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169. encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169.
[6] "Efficient decoding of prefix codes", Hirschberg and Lelewer, [6] "Efficient decoding of prefix codes", Hirschberg and Lelewer,
Comm. ACM, 33,4, April 1990, pp. 449-459. Comm. ACM, 33,4, April 1990, pp. 449-459.
6. Security considerations 6. Security considerations
Any data compression method involves the reduction of redundancy in Any data compression method involves the reduction of redundancy in
the data. Consequently, any corruption of the data is likely to have the data. Consequently, any corruption of the data is likely to have
severe effects and be difficult to correct. Uncompressed text, on severe effects and be difficult to correct. Uncompressed text, on
the other hand, will probably still be readable despite the presence the other hand, will probably still be readable despite the presence
of some corrupted bytes. of some corrupted bytes.
It is recommended that systems using this data format provide some It is recommended that systems using this data format provide some
Deutsch [Page 14]
means of validating the integrity of the compressed data. See means of validating the integrity of the compressed data. See
reference [3], for example. reference [3], for example.
7. Source code 7. Source code
Source code for a C language implementation of a 'deflate' compliant Source code for a C language implementation of a 'deflate' compliant
compressor and decompressor is available within the zlib package at compressor and decompressor is available within the zlib package at
ftp.uu.net:/pub/archiving/zip/zlib/zlib*. ftp.uu.net:/pub/archiving/zip/zlib/zlib*.
Deutsch [Page 15]
8. Acknowledgements 8. Acknowledgements
Trademarks cited in this document are the property of their Trademarks cited in this document are the property of their
respective owners. respective owners.
Phil Katz designed the deflate format. Jean-Loup Gailly and Mark Phil Katz designed the deflate format. Jean-Loup Gailly and Mark
Adler wrote the related software described in this specification. Adler wrote the related software described in this specification.
Glenn Randers-Pehrson converted this document to Internet Draft and Glenn Randers-Pehrson converted this document to Internet Draft and
HTML format. HTML format.
skipping to change at line 784 skipping to change at line 780
sent by email to sent by email to
Jean-loup Gailly <gzip@prep.ai.mit.edu> and Jean-loup Gailly <gzip@prep.ai.mit.edu> and
Mark Adler <madler@alumni.caltech.edu> Mark Adler <madler@alumni.caltech.edu>
Editorial comments on this specification can be sent by email to Editorial comments on this specification can be sent by email to
L. Peter Deutsch <ghost@aladdin.com> and L. Peter Deutsch <ghost@aladdin.com> and
Glenn Randers-Pehrson <randeg@alumni.rpi.edu> Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
Deutsch [Page 15] Deutsch [Page 16]
 End of changes. 62 change blocks. 
76 lines changed or deleted 72 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/