b24e7fce |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |
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 | \f |