1 | |
---|
2 | |
---|
3 | |
---|
4 | |
---|
5 | |
---|
6 | |
---|
7 | Network Working Group P. Deutsch |
---|
8 | Request for Comments: 1951 Aladdin Enterprises |
---|
9 | Category: Informational May 1996 |
---|
10 | |
---|
11 | |
---|
12 | DEFLATE Compressed Data Format Specification version 1.3 |
---|
13 | |
---|
14 | Status of This Memo |
---|
15 | |
---|
16 | This memo provides information for the Internet community. This memo |
---|
17 | does not specify an Internet standard of any kind. Distribution of |
---|
18 | this memo is unlimited. |
---|
19 | |
---|
20 | IESG Note: |
---|
21 | |
---|
22 | The IESG takes no position on the validity of any Intellectual |
---|
23 | Property Rights statements contained in this document. |
---|
24 | |
---|
25 | Notices |
---|
26 | |
---|
27 | Copyright (c) 1996 L. Peter Deutsch |
---|
28 | |
---|
29 | Permission is granted to copy and distribute this document for any |
---|
30 | purpose and without charge, including translations into other |
---|
31 | languages and incorporation into compilations, provided that the |
---|
32 | copyright notice and this notice are preserved, and that any |
---|
33 | substantive changes or deletions from the original are clearly |
---|
34 | marked. |
---|
35 | |
---|
36 | A pointer to the latest version of this and related documentation in |
---|
37 | HTML format can be found at the URL |
---|
38 | <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>. |
---|
39 | |
---|
40 | Abstract |
---|
41 | |
---|
42 | This specification defines a lossless compressed data format that |
---|
43 | compresses data using a combination of the LZ77 algorithm and Huffman |
---|
44 | coding, with efficiency comparable to the best currently available |
---|
45 | general-purpose compression methods. The data can be produced or |
---|
46 | consumed, even for an arbitrarily long sequentially presented input |
---|
47 | data stream, using only an a priori bounded amount of intermediate |
---|
48 | storage. The format can be implemented readily in a manner not |
---|
49 | covered by patents. |
---|
50 | |
---|
51 | |
---|
52 | |
---|
53 | |
---|
54 | |
---|
55 | |
---|
56 | |
---|
57 | |
---|
58 | Deutsch Informational [Page 1] |
---|
59 | |
---|
60 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
61 | |
---|
62 | |
---|
63 | Table of Contents |
---|
64 | |
---|
65 | 1. Introduction ................................................... 2 |
---|
66 | 1.1. Purpose ................................................... 2 |
---|
67 | 1.2. Intended audience ......................................... 3 |
---|
68 | 1.3. Scope ..................................................... 3 |
---|
69 | 1.4. Compliance ................................................ 3 |
---|
70 | 1.5. Definitions of terms and conventions used ................ 3 |
---|
71 | 1.6. Changes from previous versions ............................ 4 |
---|
72 | 2. Compressed representation overview ............................. 4 |
---|
73 | 3. Detailed specification ......................................... 5 |
---|
74 | 3.1. Overall conventions ....................................... 5 |
---|
75 | 3.1.1. Packing into bytes .................................. 5 |
---|
76 | 3.2. Compressed block format ................................... 6 |
---|
77 | 3.2.1. Synopsis of prefix and Huffman coding ............... 6 |
---|
78 | 3.2.2. Use of Huffman coding in the "deflate" format ....... 7 |
---|
79 | 3.2.3. Details of block format ............................. 9 |
---|
80 | 3.2.4. Non-compressed blocks (BTYPE=00) ................... 11 |
---|
81 | 3.2.5. Compressed blocks (length and distance codes) ...... 11 |
---|
82 | 3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 12 |
---|
83 | 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 13 |
---|
84 | 3.3. Compliance ............................................... 14 |
---|
85 | 4. Compression algorithm details ................................. 14 |
---|
86 | 5. References .................................................... 16 |
---|
87 | 6. Security Considerations ....................................... 16 |
---|
88 | 7. Source code ................................................... 16 |
---|
89 | 8. Acknowledgements .............................................. 16 |
---|
90 | 9. Author's Address .............................................. 17 |
---|
91 | |
---|
92 | 1. Introduction |
---|
93 | |
---|
94 | 1.1. Purpose |
---|
95 | |
---|
96 | The purpose of this specification is to define a lossless |
---|
97 | compressed data format that: |
---|
98 | * Is independent of CPU type, operating system, file system, |
---|
99 | and character set, and hence can be used for interchange; |
---|
100 | * Can be produced or consumed, even for an arbitrarily long |
---|
101 | sequentially presented input data stream, using only an a |
---|
102 | priori bounded amount of intermediate storage, and hence |
---|
103 | can be used in data communications or similar structures |
---|
104 | such as Unix filters; |
---|
105 | * Compresses data with efficiency comparable to the best |
---|
106 | currently available general-purpose compression methods, |
---|
107 | and in particular considerably better than the "compress" |
---|
108 | program; |
---|
109 | * Can be implemented readily in a manner not covered by |
---|
110 | patents, and hence can be practiced freely; |
---|
111 | |
---|
112 | |
---|
113 | |
---|
114 | Deutsch Informational [Page 2] |
---|
115 | |
---|
116 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
117 | |
---|
118 | |
---|
119 | * Is compatible with the file format produced by the current |
---|
120 | widely used gzip utility, in that conforming decompressors |
---|
121 | will be able to read data produced by the existing gzip |
---|
122 | compressor. |
---|
123 | |
---|
124 | The data format defined by this specification does not attempt to: |
---|
125 | |
---|
126 | * Allow random access to compressed data; |
---|
127 | * Compress specialized data (e.g., raster graphics) as well |
---|
128 | as the best currently available specialized algorithms. |
---|
129 | |
---|
130 | A simple counting argument shows that no lossless compression |
---|
131 | algorithm can compress every possible input data set. For the |
---|
132 | format defined here, the worst case expansion is 5 bytes per 32K- |
---|
133 | byte block, i.e., a size increase of 0.015% for large data sets. |
---|
134 | English text usually compresses by a factor of 2.5 to 3; |
---|
135 | executable files usually compress somewhat less; graphical data |
---|
136 | such as raster images may compress much more. |
---|
137 | |
---|
138 | 1.2. Intended audience |
---|
139 | |
---|
140 | This specification is intended for use by implementors of software |
---|
141 | to compress data into "deflate" format and/or decompress data from |
---|
142 | "deflate" format. |
---|
143 | |
---|
144 | The text of the specification assumes a basic background in |
---|
145 | programming at the level of bits and other primitive data |
---|
146 | representations. Familiarity with the technique of Huffman coding |
---|
147 | is helpful but not required. |
---|
148 | |
---|
149 | 1.3. Scope |
---|
150 | |
---|
151 | The specification specifies a method for representing a sequence |
---|
152 | of bytes as a (usually shorter) sequence of bits, and a method for |
---|
153 | packing the latter bit sequence into bytes. |
---|
154 | |
---|
155 | 1.4. Compliance |
---|
156 | |
---|
157 | Unless otherwise indicated below, a compliant decompressor must be |
---|
158 | able to accept and decompress any data set that conforms to all |
---|
159 | the specifications presented here; a compliant compressor must |
---|
160 | produce data sets that conform to all the specifications presented |
---|
161 | here. |
---|
162 | |
---|
163 | 1.5. Definitions of terms and conventions used |
---|
164 | |
---|
165 | Byte: 8 bits stored or transmitted as a unit (same as an octet). |
---|
166 | For this specification, a byte is exactly 8 bits, even on machines |
---|
167 | |
---|
168 | |
---|
169 | |
---|
170 | Deutsch Informational [Page 3] |
---|
171 | |
---|
172 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
173 | |
---|
174 | |
---|
175 | which store a character on a number of bits different from eight. |
---|
176 | See below, for the numbering of bits within a byte. |
---|
177 | |
---|
178 | String: a sequence of arbitrary bytes. |
---|
179 | |
---|
180 | 1.6. Changes from previous versions |
---|
181 | |
---|
182 | There have been no technical changes to the deflate format since |
---|
183 | version 1.1 of this specification. In version 1.2, some |
---|
184 | terminology was changed. Version 1.3 is a conversion of the |
---|
185 | specification to RFC style. |
---|
186 | |
---|
187 | 2. Compressed representation overview |
---|
188 | |
---|
189 | A compressed data set consists of a series of blocks, corresponding |
---|
190 | to successive blocks of input data. The block sizes are arbitrary, |
---|
191 | except that non-compressible blocks are limited to 65,535 bytes. |
---|
192 | |
---|
193 | Each block is compressed using a combination of the LZ77 algorithm |
---|
194 | and Huffman coding. The Huffman trees for each block are independent |
---|
195 | of those for previous or subsequent blocks; the LZ77 algorithm may |
---|
196 | use a reference to a duplicated string occurring in a previous block, |
---|
197 | up to 32K input bytes before. |
---|
198 | |
---|
199 | Each block consists of two parts: a pair of Huffman code trees that |
---|
200 | describe the representation of the compressed data part, and a |
---|
201 | compressed data part. (The Huffman trees themselves are compressed |
---|
202 | using Huffman encoding.) The compressed data consists of a series of |
---|
203 | elements of two types: literal bytes (of strings that have not been |
---|
204 | detected as duplicated within the previous 32K input bytes), and |
---|
205 | pointers to duplicated strings, where a pointer is represented as a |
---|
206 | pair <length, backward distance>. The representation used in the |
---|
207 | "deflate" format limits distances to 32K bytes and lengths to 258 |
---|
208 | bytes, but does not limit the size of a block, except for |
---|
209 | uncompressible blocks, which are limited as noted above. |
---|
210 | |
---|
211 | Each type of value (literals, distances, and lengths) in the |
---|
212 | compressed data is represented using a Huffman code, using one code |
---|
213 | tree for literals and lengths and a separate code tree for distances. |
---|
214 | The code trees for each block appear in a compact form just before |
---|
215 | the compressed data for that block. |
---|
216 | |
---|
217 | |
---|
218 | |
---|
219 | |
---|
220 | |
---|
221 | |
---|
222 | |
---|
223 | |
---|
224 | |
---|
225 | |
---|
226 | Deutsch Informational [Page 4] |
---|
227 | |
---|
228 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
229 | |
---|
230 | |
---|
231 | 3. Detailed specification |
---|
232 | |
---|
233 | 3.1. Overall conventions In the diagrams below, a box like this: |
---|
234 | |
---|
235 | +---+ |
---|
236 | | | <-- the vertical bars might be missing |
---|
237 | +---+ |
---|
238 | |
---|
239 | represents one byte; a box like this: |
---|
240 | |
---|
241 | +==============+ |
---|
242 | | | |
---|
243 | +==============+ |
---|
244 | |
---|
245 | represents a variable number of bytes. |
---|
246 | |
---|
247 | Bytes stored within a computer do not have a "bit order", since |
---|
248 | they are always treated as a unit. However, a byte considered as |
---|
249 | an integer between 0 and 255 does have a most- and least- |
---|
250 | significant bit, and since we write numbers with the most- |
---|
251 | significant digit on the left, we also write bytes with the most- |
---|
252 | significant bit on the left. In the diagrams below, we number the |
---|
253 | bits of a byte so that bit 0 is the least-significant bit, i.e., |
---|
254 | the bits are numbered: |
---|
255 | |
---|
256 | +--------+ |
---|
257 | |76543210| |
---|
258 | +--------+ |
---|
259 | |
---|
260 | Within a computer, a number may occupy multiple bytes. All |
---|
261 | multi-byte numbers in the format described here are stored with |
---|
262 | the least-significant byte first (at the lower memory address). |
---|
263 | For example, the decimal number 520 is stored as: |
---|
264 | |
---|
265 | 0 1 |
---|
266 | +--------+--------+ |
---|
267 | |00001000|00000010| |
---|
268 | +--------+--------+ |
---|
269 | ^ ^ |
---|
270 | | | |
---|
271 | | + more significant byte = 2 x 256 |
---|
272 | + less significant byte = 8 |
---|
273 | |
---|
274 | 3.1.1. Packing into bytes |
---|
275 | |
---|
276 | This document does not address the issue of the order in which |
---|
277 | bits of a byte are transmitted on a bit-sequential medium, |
---|
278 | since the final data format described here is byte- rather than |
---|
279 | |
---|
280 | |
---|
281 | |
---|
282 | Deutsch Informational [Page 5] |
---|
283 | |
---|
284 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
285 | |
---|
286 | |
---|
287 | bit-oriented. However, we describe the compressed block format |
---|
288 | in below, as a sequence of data elements of various bit |
---|
289 | lengths, not a sequence of bytes. We must therefore specify |
---|
290 | how to pack these data elements into bytes to form the final |
---|
291 | compressed byte sequence: |
---|
292 | |
---|
293 | * Data elements are packed into bytes in order of |
---|
294 | increasing bit number within the byte, i.e., starting |
---|
295 | with the least-significant bit of the byte. |
---|
296 | * Data elements other than Huffman codes are packed |
---|
297 | starting with the least-significant bit of the data |
---|
298 | element. |
---|
299 | * Huffman codes are packed starting with the most- |
---|
300 | significant bit of the code. |
---|
301 | |
---|
302 | In other words, if one were to print out the compressed data as |
---|
303 | a sequence of bytes, starting with the first byte at the |
---|
304 | *right* margin and proceeding to the *left*, with the most- |
---|
305 | significant bit of each byte on the left as usual, one would be |
---|
306 | able to parse the result from right to left, with fixed-width |
---|
307 | elements in the correct MSB-to-LSB order and Huffman codes in |
---|
308 | bit-reversed order (i.e., with the first bit of the code in the |
---|
309 | relative LSB position). |
---|
310 | |
---|
311 | 3.2. Compressed block format |
---|
312 | |
---|
313 | 3.2.1. Synopsis of prefix and Huffman coding |
---|
314 | |
---|
315 | Prefix coding represents symbols from an a priori known |
---|
316 | alphabet by bit sequences (codes), one code for each symbol, in |
---|
317 | a manner such that different symbols may be represented by bit |
---|
318 | sequences of different lengths, but a parser can always parse |
---|
319 | an encoded string unambiguously symbol-by-symbol. |
---|
320 | |
---|
321 | We define a prefix code in terms of a binary tree in which the |
---|
322 | two edges descending from each non-leaf node are labeled 0 and |
---|
323 | 1 and in which the leaf nodes correspond one-for-one with (are |
---|
324 | labeled with) the symbols of the alphabet; then the code for a |
---|
325 | symbol is the sequence of 0's and 1's on the edges leading from |
---|
326 | the root to the leaf labeled with that symbol. For example: |
---|
327 | |
---|
328 | |
---|
329 | |
---|
330 | |
---|
331 | |
---|
332 | |
---|
333 | |
---|
334 | |
---|
335 | |
---|
336 | |
---|
337 | |
---|
338 | Deutsch Informational [Page 6] |
---|
339 | |
---|
340 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
341 | |
---|
342 | |
---|
343 | /\ Symbol Code |
---|
344 | 0 1 ------ ---- |
---|
345 | / \ A 00 |
---|
346 | /\ B B 1 |
---|
347 | 0 1 C 011 |
---|
348 | / \ D 010 |
---|
349 | A /\ |
---|
350 | 0 1 |
---|
351 | / \ |
---|
352 | D C |
---|
353 | |
---|
354 | A parser can decode the next symbol from an encoded input |
---|
355 | stream by walking down the tree from the root, at each step |
---|
356 | choosing the edge corresponding to the next input bit. |
---|
357 | |
---|
358 | Given an alphabet with known symbol frequencies, the Huffman |
---|
359 | algorithm allows the construction of an optimal prefix code |
---|
360 | (one which represents strings with those symbol frequencies |
---|
361 | using the fewest bits of any possible prefix codes for that |
---|
362 | alphabet). Such a code is called a Huffman code. (See |
---|
363 | reference [1] in Chapter 5, references for additional |
---|
364 | information on Huffman codes.) |
---|
365 | |
---|
366 | Note that in the "deflate" format, the Huffman codes for the |
---|
367 | various alphabets must not exceed certain maximum code lengths. |
---|
368 | This constraint complicates the algorithm for computing code |
---|
369 | lengths from symbol frequencies. Again, see Chapter 5, |
---|
370 | references for details. |
---|
371 | |
---|
372 | 3.2.2. Use of Huffman coding in the "deflate" format |
---|
373 | |
---|
374 | The Huffman codes used for each alphabet in the "deflate" |
---|
375 | format have two additional rules: |
---|
376 | |
---|
377 | * All codes of a given bit length have lexicographically |
---|
378 | consecutive values, in the same order as the symbols |
---|
379 | they represent; |
---|
380 | |
---|
381 | * Shorter codes lexicographically precede longer codes. |
---|
382 | |
---|
383 | |
---|
384 | |
---|
385 | |
---|
386 | |
---|
387 | |
---|
388 | |
---|
389 | |
---|
390 | |
---|
391 | |
---|
392 | |
---|
393 | |
---|
394 | Deutsch Informational [Page 7] |
---|
395 | |
---|
396 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
397 | |
---|
398 | |
---|
399 | We could recode the example above to follow this rule as |
---|
400 | follows, assuming that the order of the alphabet is ABCD: |
---|
401 | |
---|
402 | Symbol Code |
---|
403 | ------ ---- |
---|
404 | A 10 |
---|
405 | B 0 |
---|
406 | C 110 |
---|
407 | D 111 |
---|
408 | |
---|
409 | I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are |
---|
410 | lexicographically consecutive. |
---|
411 | |
---|
412 | Given this rule, we can define the Huffman code for an alphabet |
---|
413 | just by giving the bit lengths of the codes for each symbol of |
---|
414 | the alphabet in order; this is sufficient to determine the |
---|
415 | actual codes. In our example, the code is completely defined |
---|
416 | by the sequence of bit lengths (2, 1, 3, 3). The following |
---|
417 | algorithm generates the codes as integers, intended to be read |
---|
418 | from most- to least-significant bit. The code lengths are |
---|
419 | initially in tree[I].Len; the codes are produced in |
---|
420 | tree[I].Code. |
---|
421 | |
---|
422 | 1) Count the number of codes for each code length. Let |
---|
423 | bl_count[N] be the number of codes of length N, N >= 1. |
---|
424 | |
---|
425 | 2) Find the numerical value of the smallest code for each |
---|
426 | code length: |
---|
427 | |
---|
428 | code = 0; |
---|
429 | bl_count[0] = 0; |
---|
430 | for (bits = 1; bits <= MAX_BITS; bits++) { |
---|
431 | code = (code + bl_count[bits-1]) << 1; |
---|
432 | next_code[bits] = code; |
---|
433 | } |
---|
434 | |
---|
435 | 3) Assign numerical values to all codes, using consecutive |
---|
436 | values for all codes of the same length with the base |
---|
437 | values determined at step 2. Codes that are never used |
---|
438 | (which have a bit length of zero) must not be assigned a |
---|
439 | value. |
---|
440 | |
---|
441 | for (n = 0; n <= max_code; n++) { |
---|
442 | len = tree[n].Len; |
---|
443 | if (len != 0) { |
---|
444 | tree[n].Code = next_code[len]; |
---|
445 | next_code[len]++; |
---|
446 | } |
---|
447 | |
---|
448 | |
---|
449 | |
---|
450 | Deutsch Informational [Page 8] |
---|
451 | |
---|
452 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
453 | |
---|
454 | |
---|
455 | } |
---|
456 | |
---|
457 | Example: |
---|
458 | |
---|
459 | Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, |
---|
460 | 3, 2, 4, 4). After step 1, we have: |
---|
461 | |
---|
462 | N bl_count[N] |
---|
463 | - ----------- |
---|
464 | 2 1 |
---|
465 | 3 5 |
---|
466 | 4 2 |
---|
467 | |
---|
468 | Step 2 computes the following next_code values: |
---|
469 | |
---|
470 | N next_code[N] |
---|
471 | - ------------ |
---|
472 | 1 0 |
---|
473 | 2 0 |
---|
474 | 3 2 |
---|
475 | 4 14 |
---|
476 | |
---|
477 | Step 3 produces the following code values: |
---|
478 | |
---|
479 | Symbol Length Code |
---|
480 | ------ ------ ---- |
---|
481 | A 3 010 |
---|
482 | B 3 011 |
---|
483 | C 3 100 |
---|
484 | D 3 101 |
---|
485 | E 3 110 |
---|
486 | F 2 00 |
---|
487 | G 4 1110 |
---|
488 | H 4 1111 |
---|
489 | |
---|
490 | 3.2.3. Details of block format |
---|
491 | |
---|
492 | Each block of compressed data begins with 3 header bits |
---|
493 | containing the following data: |
---|
494 | |
---|
495 | first bit BFINAL |
---|
496 | next 2 bits BTYPE |
---|
497 | |
---|
498 | Note that the header bits do not necessarily begin on a byte |
---|
499 | boundary, since a block does not necessarily occupy an integral |
---|
500 | number of bytes. |
---|
501 | |
---|
502 | |
---|
503 | |
---|
504 | |
---|
505 | |
---|
506 | Deutsch Informational [Page 9] |
---|
507 | |
---|
508 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
509 | |
---|
510 | |
---|
511 | BFINAL is set if and only if this is the last block of the data |
---|
512 | set. |
---|
513 | |
---|
514 | BTYPE specifies how the data are compressed, as follows: |
---|
515 | |
---|
516 | 00 - no compression |
---|
517 | 01 - compressed with fixed Huffman codes |
---|
518 | 10 - compressed with dynamic Huffman codes |
---|
519 | 11 - reserved (error) |
---|
520 | |
---|
521 | The only difference between the two compressed cases is how the |
---|
522 | Huffman codes for the literal/length and distance alphabets are |
---|
523 | defined. |
---|
524 | |
---|
525 | In all cases, the decoding algorithm for the actual data is as |
---|
526 | follows: |
---|
527 | |
---|
528 | do |
---|
529 | read block header from input stream. |
---|
530 | if stored with no compression |
---|
531 | skip any remaining bits in current partially |
---|
532 | processed byte |
---|
533 | read LEN and NLEN (see next section) |
---|
534 | copy LEN bytes of data to output |
---|
535 | otherwise |
---|
536 | if compressed with dynamic Huffman codes |
---|
537 | read representation of code trees (see |
---|
538 | subsection below) |
---|
539 | loop (until end of block code recognized) |
---|
540 | decode literal/length value from input stream |
---|
541 | if value < 256 |
---|
542 | copy value (literal byte) to output stream |
---|
543 | otherwise |
---|
544 | if value = end of block (256) |
---|
545 | break from loop |
---|
546 | otherwise (value = 257..285) |
---|
547 | decode distance from input stream |
---|
548 | |
---|
549 | move backwards distance bytes in the output |
---|
550 | stream, and copy length bytes from this |
---|
551 | position to the output stream. |
---|
552 | end loop |
---|
553 | while not last block |
---|
554 | |
---|
555 | Note that a duplicated string reference may refer to a string |
---|
556 | in a previous block; i.e., the backward distance may cross one |
---|
557 | or more block boundaries. However a distance cannot refer past |
---|
558 | the beginning of the output stream. (An application using a |
---|
559 | |
---|
560 | |
---|
561 | |
---|
562 | Deutsch Informational [Page 10] |
---|
563 | |
---|
564 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
565 | |
---|
566 | |
---|
567 | preset dictionary might discard part of the output stream; a |
---|
568 | distance can refer to that part of the output stream anyway) |
---|
569 | Note also that the referenced string may overlap the current |
---|
570 | position; for example, if the last 2 bytes decoded have values |
---|
571 | X and Y, a string reference with <length = 5, distance = 2> |
---|
572 | adds X,Y,X,Y,X to the output stream. |
---|
573 | |
---|
574 | We now specify each compression method in turn. |
---|
575 | |
---|
576 | 3.2.4. Non-compressed blocks (BTYPE=00) |
---|
577 | |
---|
578 | Any bits of input up to the next byte boundary are ignored. |
---|
579 | The rest of the block consists of the following information: |
---|
580 | |
---|
581 | 0 1 2 3 4... |
---|
582 | +---+---+---+---+================================+ |
---|
583 | | LEN | NLEN |... LEN bytes of literal data...| |
---|
584 | +---+---+---+---+================================+ |
---|
585 | |
---|
586 | LEN is the number of data bytes in the block. NLEN is the |
---|
587 | one's complement of LEN. |
---|
588 | |
---|
589 | 3.2.5. Compressed blocks (length and distance codes) |
---|
590 | |
---|
591 | As noted above, encoded data blocks in the "deflate" format |
---|
592 | consist of sequences of symbols drawn from three conceptually |
---|
593 | distinct alphabets: either literal bytes, from the alphabet of |
---|
594 | byte values (0..255), or <length, backward distance> pairs, |
---|
595 | where the length is drawn from (3..258) and the distance is |
---|
596 | drawn from (1..32,768). In fact, the literal and length |
---|
597 | alphabets are merged into a single alphabet (0..285), where |
---|
598 | values 0..255 represent literal bytes, the value 256 indicates |
---|
599 | end-of-block, and values 257..285 represent length codes |
---|
600 | (possibly in conjunction with extra bits following the symbol |
---|
601 | code) as follows: |
---|
602 | |
---|
603 | |
---|
604 | |
---|
605 | |
---|
606 | |
---|
607 | |
---|
608 | |
---|
609 | |
---|
610 | |
---|
611 | |
---|
612 | |
---|
613 | |
---|
614 | |
---|
615 | |
---|
616 | |
---|
617 | |
---|
618 | Deutsch Informational [Page 11] |
---|
619 | |
---|
620 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
621 | |
---|
622 | |
---|
623 | Extra Extra Extra |
---|
624 | Code Bits Length(s) Code Bits Lengths Code Bits Length(s) |
---|
625 | ---- ---- ------ ---- ---- ------- ---- ---- ------- |
---|
626 | 257 0 3 267 1 15,16 277 4 67-82 |
---|
627 | 258 0 4 268 1 17,18 278 4 83-98 |
---|
628 | 259 0 5 269 2 19-22 279 4 99-114 |
---|
629 | 260 0 6 270 2 23-26 280 4 115-130 |
---|
630 | 261 0 7 271 2 27-30 281 5 131-162 |
---|
631 | 262 0 8 272 2 31-34 282 5 163-194 |
---|
632 | 263 0 9 273 3 35-42 283 5 195-226 |
---|
633 | 264 0 10 274 3 43-50 284 5 227-257 |
---|
634 | 265 1 11,12 275 3 51-58 285 0 258 |
---|
635 | 266 1 13,14 276 3 59-66 |
---|
636 | |
---|
637 | The extra bits should be interpreted as a machine integer |
---|
638 | stored with the most-significant bit first, e.g., bits 1110 |
---|
639 | represent the value 14. |
---|
640 | |
---|
641 | Extra Extra Extra |
---|
642 | Code Bits Dist Code Bits Dist Code Bits Distance |
---|
643 | ---- ---- ---- ---- ---- ------ ---- ---- -------- |
---|
644 | 0 0 1 10 4 33-48 20 9 1025-1536 |
---|
645 | 1 0 2 11 4 49-64 21 9 1537-2048 |
---|
646 | 2 0 3 12 5 65-96 22 10 2049-3072 |
---|
647 | 3 0 4 13 5 97-128 23 10 3073-4096 |
---|
648 | 4 1 5,6 14 6 129-192 24 11 4097-6144 |
---|
649 | 5 1 7,8 15 6 193-256 25 11 6145-8192 |
---|
650 | 6 2 9-12 16 7 257-384 26 12 8193-12288 |
---|
651 | 7 2 13-16 17 7 385-512 27 12 12289-16384 |
---|
652 | 8 3 17-24 18 8 513-768 28 13 16385-24576 |
---|
653 | 9 3 25-32 19 8 769-1024 29 13 24577-32768 |
---|
654 | |
---|
655 | 3.2.6. Compression with fixed Huffman codes (BTYPE=01) |
---|
656 | |
---|
657 | The Huffman codes for the two alphabets are fixed, and are not |
---|
658 | represented explicitly in the data. The Huffman code lengths |
---|
659 | for the literal/length alphabet are: |
---|
660 | |
---|
661 | Lit Value Bits Codes |
---|
662 | --------- ---- ----- |
---|
663 | 0 - 143 8 00110000 through |
---|
664 | 10111111 |
---|
665 | 144 - 255 9 110010000 through |
---|
666 | 111111111 |
---|
667 | 256 - 279 7 0000000 through |
---|
668 | 0010111 |
---|
669 | 280 - 287 8 11000000 through |
---|
670 | 11000111 |
---|
671 | |
---|
672 | |
---|
673 | |
---|
674 | Deutsch Informational [Page 12] |
---|
675 | |
---|
676 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
677 | |
---|
678 | |
---|
679 | The code lengths are sufficient to generate the actual codes, |
---|
680 | as described above; we show the codes in the table for added |
---|
681 | clarity. Literal/length values 286-287 will never actually |
---|
682 | occur in the compressed data, but participate in the code |
---|
683 | construction. |
---|
684 | |
---|
685 | Distance codes 0-31 are represented by (fixed-length) 5-bit |
---|
686 | codes, with possible additional bits as shown in the table |
---|
687 | shown in Paragraph 3.2.5, above. Note that distance codes 30- |
---|
688 | 31 will never actually occur in the compressed data. |
---|
689 | |
---|
690 | 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) |
---|
691 | |
---|
692 | The Huffman codes for the two alphabets appear in the block |
---|
693 | immediately after the header bits and before the actual |
---|
694 | compressed data, first the literal/length code and then the |
---|
695 | distance code. Each code is defined by a sequence of code |
---|
696 | lengths, as discussed in Paragraph 3.2.2, above. For even |
---|
697 | greater compactness, the code length sequences themselves are |
---|
698 | compressed using a Huffman code. The alphabet for code lengths |
---|
699 | is as follows: |
---|
700 | |
---|
701 | 0 - 15: Represent code lengths of 0 - 15 |
---|
702 | 16: Copy the previous code length 3 - 6 times. |
---|
703 | The next 2 bits indicate repeat length |
---|
704 | (0 = 3, ... , 3 = 6) |
---|
705 | Example: Codes 8, 16 (+2 bits 11), |
---|
706 | 16 (+2 bits 10) will expand to |
---|
707 | 12 code lengths of 8 (1 + 6 + 5) |
---|
708 | 17: Repeat a code length of 0 for 3 - 10 times. |
---|
709 | (3 bits of length) |
---|
710 | 18: Repeat a code length of 0 for 11 - 138 times |
---|
711 | (7 bits of length) |
---|
712 | |
---|
713 | A code length of 0 indicates that the corresponding symbol in |
---|
714 | the literal/length or distance alphabet will not occur in the |
---|
715 | block, and should not participate in the Huffman code |
---|
716 | construction algorithm given earlier. If only one distance |
---|
717 | code is used, it is encoded using one bit, not zero bits; in |
---|
718 | this case there is a single code length of one, with one unused |
---|
719 | code. One distance code of zero bits means that there are no |
---|
720 | distance codes used at all (the data is all literals). |
---|
721 | |
---|
722 | We can now define the format of the block: |
---|
723 | |
---|
724 | 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286) |
---|
725 | 5 Bits: HDIST, # of Distance codes - 1 (1 - 32) |
---|
726 | 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19) |
---|
727 | |
---|
728 | |
---|
729 | |
---|
730 | Deutsch Informational [Page 13] |
---|
731 | |
---|
732 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
733 | |
---|
734 | |
---|
735 | (HCLEN + 4) x 3 bits: code lengths for the code length |
---|
736 | alphabet given just above, in the order: 16, 17, 18, |
---|
737 | 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 |
---|
738 | |
---|
739 | These code lengths are interpreted as 3-bit integers |
---|
740 | (0-7); as above, a code length of 0 means the |
---|
741 | corresponding symbol (literal/length or distance code |
---|
742 | length) is not used. |
---|
743 | |
---|
744 | HLIT + 257 code lengths for the literal/length alphabet, |
---|
745 | encoded using the code length Huffman code |
---|
746 | |
---|
747 | HDIST + 1 code lengths for the distance alphabet, |
---|
748 | encoded using the code length Huffman code |
---|
749 | |
---|
750 | The actual compressed data of the block, |
---|
751 | encoded using the literal/length and distance Huffman |
---|
752 | codes |
---|
753 | |
---|
754 | The literal/length symbol 256 (end of data), |
---|
755 | encoded using the literal/length Huffman code |
---|
756 | |
---|
757 | The code length repeat codes can cross from HLIT + 257 to the |
---|
758 | HDIST + 1 code lengths. In other words, all code lengths form |
---|
759 | a single sequence of HLIT + HDIST + 258 values. |
---|
760 | |
---|
761 | 3.3. Compliance |
---|
762 | |
---|
763 | A compressor may limit further the ranges of values specified in |
---|
764 | the previous section and still be compliant; for example, it may |
---|
765 | limit the range of backward pointers to some value smaller than |
---|
766 | 32K. Similarly, a compressor may limit the size of blocks so that |
---|
767 | a compressible block fits in memory. |
---|
768 | |
---|
769 | A compliant decompressor must accept the full range of possible |
---|
770 | values defined in the previous section, and must accept blocks of |
---|
771 | arbitrary size. |
---|
772 | |
---|
773 | 4. Compression algorithm details |
---|
774 | |
---|
775 | While it is the intent of this document to define the "deflate" |
---|
776 | compressed data format without reference to any particular |
---|
777 | compression algorithm, the format is related to the compressed |
---|
778 | formats produced by LZ77 (Lempel-Ziv 1977, see reference [2] below); |
---|
779 | since many variations of LZ77 are patented, it is strongly |
---|
780 | recommended that the implementor of a compressor follow the general |
---|
781 | algorithm presented here, which is known not to be patented per se. |
---|
782 | The material in this section is not part of the definition of the |
---|
783 | |
---|
784 | |
---|
785 | |
---|
786 | Deutsch Informational [Page 14] |
---|
787 | |
---|
788 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
789 | |
---|
790 | |
---|
791 | specification per se, and a compressor need not follow it in order to |
---|
792 | be compliant. |
---|
793 | |
---|
794 | The compressor terminates a block when it determines that starting a |
---|
795 | new block with fresh trees would be useful, or when the block size |
---|
796 | fills up the compressor's block buffer. |
---|
797 | |
---|
798 | The compressor uses a chained hash table to find duplicated strings, |
---|
799 | using a hash function that operates on 3-byte sequences. At any |
---|
800 | given point during compression, let XYZ be the next 3 input bytes to |
---|
801 | be examined (not necessarily all different, of course). First, the |
---|
802 | compressor examines the hash chain for XYZ. If the chain is empty, |
---|
803 | the compressor simply writes out X as a literal byte and advances one |
---|
804 | byte in the input. If the hash chain is not empty, indicating that |
---|
805 | the sequence XYZ (or, if we are unlucky, some other 3 bytes with the |
---|
806 | same hash function value) has occurred recently, the compressor |
---|
807 | compares all strings on the XYZ hash chain with the actual input data |
---|
808 | sequence starting at the current point, and selects the longest |
---|
809 | match. |
---|
810 | |
---|
811 | The compressor searches the hash chains starting with the most recent |
---|
812 | strings, to favor small distances and thus take advantage of the |
---|
813 | Huffman encoding. The hash chains are singly linked. There are no |
---|
814 | deletions from the hash chains; the algorithm simply discards matches |
---|
815 | that are too old. To avoid a worst-case situation, very long hash |
---|
816 | chains are arbitrarily truncated at a certain length, determined by a |
---|
817 | run-time parameter. |
---|
818 | |
---|
819 | To improve overall compression, the compressor optionally defers the |
---|
820 | selection of matches ("lazy matching"): after a match of length N has |
---|
821 | been found, the compressor searches for a longer match starting at |
---|
822 | the next input byte. If it finds a longer match, it truncates the |
---|
823 | previous match to a length of one (thus producing a single literal |
---|
824 | byte) and then emits the longer match. Otherwise, it emits the |
---|
825 | original match, and, as described above, advances N bytes before |
---|
826 | continuing. |
---|
827 | |
---|
828 | Run-time parameters also control this "lazy match" procedure. If |
---|
829 | compression ratio is most important, the compressor attempts a |
---|
830 | complete second search regardless of the length of the first match. |
---|
831 | In the normal case, if the current match is "long enough", the |
---|
832 | compressor reduces the search for a longer match, thus speeding up |
---|
833 | the process. If speed is most important, the compressor inserts new |
---|
834 | strings in the hash table only when no match was found, or when the |
---|
835 | match is not "too long". This degrades the compression ratio but |
---|
836 | saves time since there are both fewer insertions and fewer searches. |
---|
837 | |
---|
838 | |
---|
839 | |
---|
840 | |
---|
841 | |
---|
842 | Deutsch Informational [Page 15] |
---|
843 | |
---|
844 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
845 | |
---|
846 | |
---|
847 | 5. References |
---|
848 | |
---|
849 | [1] Huffman, D. A., "A Method for the Construction of Minimum |
---|
850 | Redundancy Codes", Proceedings of the Institute of Radio |
---|
851 | Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101. |
---|
852 | |
---|
853 | [2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data |
---|
854 | Compression", IEEE Transactions on Information Theory, Vol. 23, |
---|
855 | No. 3, pp. 337-343. |
---|
856 | |
---|
857 | [3] Gailly, J.-L., and Adler, M., ZLIB documentation and sources, |
---|
858 | available in ftp://ftp.uu.net/pub/archiving/zip/doc/ |
---|
859 | |
---|
860 | [4] Gailly, J.-L., and Adler, M., GZIP documentation and sources, |
---|
861 | available as gzip-*.tar in ftp://prep.ai.mit.edu/pub/gnu/ |
---|
862 | |
---|
863 | [5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix |
---|
864 | encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169. |
---|
865 | |
---|
866 | [6] Hirschberg and Lelewer, "Efficient decoding of prefix codes," |
---|
867 | Comm. ACM, 33,4, April 1990, pp. 449-459. |
---|
868 | |
---|
869 | 6. Security Considerations |
---|
870 | |
---|
871 | Any data compression method involves the reduction of redundancy in |
---|
872 | the data. Consequently, any corruption of the data is likely to have |
---|
873 | severe effects and be difficult to correct. Uncompressed text, on |
---|
874 | the other hand, will probably still be readable despite the presence |
---|
875 | of some corrupted bytes. |
---|
876 | |
---|
877 | It is recommended that systems using this data format provide some |
---|
878 | means of validating the integrity of the compressed data. See |
---|
879 | reference [3], for example. |
---|
880 | |
---|
881 | 7. Source code |
---|
882 | |
---|
883 | Source code for a C language implementation of a "deflate" compliant |
---|
884 | compressor and decompressor is available within the zlib package at |
---|
885 | ftp://ftp.uu.net/pub/archiving/zip/zlib/. |
---|
886 | |
---|
887 | 8. Acknowledgements |
---|
888 | |
---|
889 | Trademarks cited in this document are the property of their |
---|
890 | respective owners. |
---|
891 | |
---|
892 | Phil Katz designed the deflate format. Jean-Loup Gailly and Mark |
---|
893 | Adler wrote the related software described in this specification. |
---|
894 | Glenn Randers-Pehrson converted this document to RFC and HTML format. |
---|
895 | |
---|
896 | |
---|
897 | |
---|
898 | Deutsch Informational [Page 16] |
---|
899 | |
---|
900 | RFC 1951 DEFLATE Compressed Data Format Specification May 1996 |
---|
901 | |
---|
902 | |
---|
903 | 9. Author's Address |
---|
904 | |
---|
905 | L. Peter Deutsch |
---|
906 | Aladdin Enterprises |
---|
907 | 203 Santa Margarita Ave. |
---|
908 | Menlo Park, CA 94025 |
---|
909 | |
---|
910 | Phone: (415) 322-0103 (AM only) |
---|
911 | FAX: (415) 322-1734 |
---|
912 | EMail: <ghost@aladdin.com> |
---|
913 | |
---|
914 | Questions about the technical content of this specification can be |
---|
915 | sent by email to: |
---|
916 | |
---|
917 | Jean-Loup Gailly <gzip@prep.ai.mit.edu> and |
---|
918 | Mark Adler <madler@alumni.caltech.edu> |
---|
919 | |
---|
920 | Editorial comments on this specification can be sent by email to: |
---|
921 | |
---|
922 | L. Peter Deutsch <ghost@aladdin.com> and |
---|
923 | Glenn Randers-Pehrson <randeg@alumni.rpi.edu> |
---|
924 | |
---|
925 | |
---|
926 | |
---|
927 | |
---|
928 | |
---|
929 | |
---|
930 | |
---|
931 | |
---|
932 | |
---|
933 | |
---|
934 | |
---|
935 | |
---|
936 | |
---|
937 | |
---|
938 | |
---|
939 | |
---|
940 | |
---|
941 | |
---|
942 | |
---|
943 | |
---|
944 | |
---|
945 | |
---|
946 | |
---|
947 | |
---|
948 | |
---|
949 | |
---|
950 | |
---|
951 | |
---|
952 | |
---|
953 | |
---|
954 | Deutsch Informational [Page 17] |
---|
955 | |
---|