| 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 |