idnits 2.17.00 (12 Aug 2021) /tmp/idnits13538/draft-deutsch-deflate-spec-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2022-05-20) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 14 longer pages, the longest (page 2) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (01 Feb 1996) is 9605 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'I' is mentioned on line 350, but not defined == Missing Reference: 'N' is mentioned on line 391, but not defined -- Looks like a reference, but probably isn't: '0' on line 359 == Unused Reference: 'GZIP' is defined on line 708, but no explicit reference was found in the text == Unused Reference: 'SCHWARTZ' is defined on line 722, but no explicit reference was found in the text == Unused Reference: 'HIRSCHBERG' is defined on line 725, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'GZIP' -- Possible downref: Non-RFC (?) normative reference: ref. 'ZLIB' -- Possible downref: Non-RFC (?) normative reference: ref. 'LZ77' -- Possible downref: Non-RFC (?) normative reference: ref. 'HUFFMAN' -- Possible downref: Non-RFC (?) normative reference: ref. 'SCHWARTZ' -- Possible downref: Non-RFC (?) normative reference: ref. 'HIRSCHBERG' Summary: 8 errors (**), 0 flaws (~~), 7 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT L. P. Deutsch 2 DEFLATE 1.3 Aladdin Enterprises 3 Expires: 06 Aug 1996 01 Feb 1996 5 DEFLATE Compressed Data Format Specification version 1.3 7 File draft-deutsch-deflate-spec-00.txt 9 Status of this Memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six months 17 and may be updated, replaced, or obsoleted by other documents at any 18 time. It is inappropriate to use Internet- Drafts as reference 19 material or to cite them other than as ``work in progress.'' 21 To learn the current status of any Internet-Draft, please check the 22 ``1id-abstracts.txt'' listing contained in the Internet- Drafts 23 Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 24 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 25 ftp.isi.edu (US West Coast). 27 Distribution of this memo is unlimited. 29 Notices 31 Copyright (C) 1996 L. Peter Deutsch 33 Permission is granted to copy and distribute this document for any 34 purpose and without charge, including translations into other 35 languages and incorporation into compilations, provided that it is 36 copied as a whole (including the copyright notice and this notice) 37 and with no changes. 39 Abstract 41 This specification defines a lossless compressed data format that 42 compresses data using a combination of the LZ77 algorithm and Huffman 43 coding, with efficiency comparable to the best currently available 44 general-purpose compression methods. The data can be produced or 45 consumed, even for an arbitrarily long sequentially presented input 46 data stream, using only an a priori bounded amount of intermediate 47 storage. The format can be implemented readily in a manner not 48 covered by patents. 50 Deutsch [Page 1] 51 Table of Contents 53 1. Introduction ................................................... 2 54 1.1 Purpose .................................................... 2 55 1.2 Intended audience .......................................... 3 56 1.3 Scope ...................................................... 3 57 1.4 Compliance ................................................. 3 58 1.5 Definitions of terms and conventions used ................. 3 59 1.6 Changes from previous versions ............................. 4 60 2. Compressed representation overview ............................. 4 61 3. Detailed specification ......................................... 4 62 3.1 Overall conventions ........................................ 4 63 3.1.1. Packing into bytes .................................. 5 64 3.2 Compressed block format .................................... 6 65 3.2.1. Synopsis of prefix and Huffman coding ............... 6 66 3.2.2. Use of Huffman coding in the 'deflate' format ....... 7 67 3.2.3. Details of block format ............................. 8 68 3.2.4. Non-compressed blocks (BTYPE=00) ................... 10 69 3.2.5. Compressed blocks (length and distance codes) ...... 10 70 3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 11 71 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 11 72 3.3 Compliance ................................................ 13 73 4. Compression algorithm details ................................. 13 74 5. References .................................................... 14 75 6. Security considerations ....................................... 14 76 7. Source code ................................................... 15 77 8. Acknowledgements .............................................. 15 78 9. Author's address .............................................. 15 80 1. Introduction 82 1.1. Purpose 84 The purpose of this specification is to define a lossless 85 compressed data format that: 87 o Is independent of CPU type, operating system, file system, 88 and character set, and hence can be used for interchange; 89 o Can be produced or consumed, even for an arbitrarily long 90 sequentially presented input data stream, using only an a 91 priori bounded amount of intermediate storage, and hence can 92 be used in data communications or similar structures such as 93 Unix filters; 94 o Compresses data with efficiency comparable to the best 95 currently available general-purpose compression methods, and 96 in particular considerably better than the 'compress' 97 program; 98 o Can be implemented readily in a manner not covered by 99 patents, and hence can be practiced freely; 100 o Is compatible with the file format produced by the current 101 widely used gzip utility, in that conforming decompressors 102 will be able to read data produced by the existing gzip 104 Deutsch [Page 2] 105 compressor. 107 The data format defined by this specification does not attempt to: 109 o Allow random access to compressed data; 110 o Compress specialized data (e.g., raster graphics) as well as 111 the best currently available specialized algorithms. 113 A simple counting argument shows that no lossless compression 114 algorithm can compress every possible input data set. For the 115 format defined here, the worst case expansion is 5 bytes per 32K- 116 byte block, i.e., a size increase of 0.015% for large data sets. 117 English text usually compresses by a factor of 2.5 to 3; 118 executable files usually compress somewhat less; graphical data 119 such as raster images may compress much more. 121 1.2. Intended audience 123 This specification is intended for use by implementors of software 124 to compress data into 'deflate' format and/or decompress data from 125 'deflate' format. 127 The text of the specification assumes a basic background in 128 programming at the level of bits and other primitive data 129 representations. Familiarity with the technique of Huffman coding 130 is helpful but not required. 132 1.3. Scope 134 The specification specifies a method for representing a sequence 135 of bytes as a (usually shorter) sequence of bits, and a method for 136 packing the latter bit sequence into bytes. 138 1.4. Compliance 140 Unless otherwise indicated below, a compliant decompressor must be 141 able to accept and decompress any data set that conforms to all 142 the specifications presented here; a compliant compressor must 143 produce data sets that conform to all the specifications presented 144 here. 146 1.5. Definitions of terms and conventions used 148 byte: 8 bits stored or transmitted as a unit (same as an octet). 149 (For this specification, a byte is exactly 8 bits, even on 150 machines which store a character on a number of bits different 151 from 8.) See Section 3.1, below, for the numbering of bits within 152 a byte. 154 string: a sequence of arbitrary bytes. 156 1.6. Changes from previous versions 158 Deutsch [Page 3] 159 There have been no technical changes to the deflate format since 160 version 1.1 of this specification. In version 1.2, some 161 terminology was changed. Version 1.3 is a conversion of the 162 specification to Internet Draft style. 164 2. Compressed representation overview 166 A compressed data set consists of a series of blocks, corresponding 167 to successive blocks of input data. The block sizes are arbitrary, 168 except that non-compressible blocks are limited to 65,535 bytes. 170 Each block is compressed using a combination of the LZ77 algorithm 171 and Huffman coding. The Huffman trees for each block are independant 172 of those for previous or subsequent blocks; the LZ77 algorithm may 173 use a reference to a duplicated string occurring in a previous block, 174 up to 32K input bytes before. 176 Each block consists of two parts: a pair of Huffman code trees that 177 describe the representation of the compressed data part, and a 178 compressed data part. (The Huffman trees themselves are compressed 179 using Huffman encoding.) The compressed data consists of a series of 180 elements of two types: literal bytes (of strings that have not been 181 detected as duplicated within the previous 32K input bytes), and 182 pointers to duplicated strings, where a pointer is represented as a 183 pair . The representation used in the 184 'deflate' format limits distances to 32K bytes and lengths to 258 185 bytes, but does not limit the size of a block, except for 186 uncompressible blocks, which are limited as noted above. 188 Each type of value (literals, distances, and lengths) in the 189 compressed data is represented using a Huffman code, using one code 190 tree for literals and lengths and a separate code tree for distances. 191 The code trees for each block appear in a compact form just before 192 the compressed data for that block. 194 3. Detailed specification 196 3.1. Overall conventions In the diagrams below, a box like this: 198 +---+ 199 | | <-- the vertical bars might be missing 200 +---+ 202 represents one byte; a box like this: 204 +==============+ 205 | | 206 +==============+ 208 represents a variable number of bytes. 210 Bytes stored within a computer do not have a 'bit order', since 212 Deutsch [Page 4] 213 they are always treated as a unit. However, a byte considered as 214 an integer between 0 and 255 does have a most- and least- 215 significant bit, and since we write numbers with the most- 216 significant digit on the left, we also write bytes with the most- 217 significant bit on the left. In the diagrams below, we number the 218 bits of a byte so that bit 0 is the least-significant bit, i.e., 219 the bits are numbered: 221 +--------+ 222 |76543210| 223 +--------+ 225 Within a computer, a number may occupy multiple bytes. All 226 multi-byte numbers in the format described here are stored with 227 the least-significant byte first (at the lower memory address). 228 For example, the decimal number 520 is stored as: 230 0 1 231 +--------+--------+ 232 |00001000|00000010| 233 +--------+--------+ 234 ^ ^ 235 | | 236 | + more significant byte = 2 x 256 237 + less significant byte = 8 239 3.1.1. Packing into bytes 241 This document does not address the issue of the order in which 242 bits of a byte are transmitted on a bit-sequential medium, 243 since the final data format described here is byte- rather than 244 bit-oriented. However, we describe the compressed block format 245 in Section 3.2, below, as a sequence of data elements of 246 various bit lengths, not a sequence of bytes. We must 247 therefore specify how to pack these data elements into bytes to 248 form the final compressed byte sequence: 250 o Data elements are packed into bytes in order of 251 increasing bit number within the byte, i.e., starting 252 with the least- significant bit of the byte. 253 o Data elements other than Huffman codes are packed 254 starting with the least-significant bit of the data 255 element. 256 o Huffman codes are packed starting with the most- 257 significant bit of the code. 259 In other words, if one were to print out the compressed data as 260 a sequence of bytes, starting with the first byte at the 261 *right* margin and proceeding to the *left*, with the most- 262 significant bit of each byte on the left as usual, one would be 263 able to parse the result from right to left, with fixed-width 264 elements in the correct MSB-to-LSB order and Huffman codes in 266 Deutsch [Page 5] 267 bit-reversed order (i.e., with the first bit of the code in the 268 relative LSB position). 270 3.2. Compressed block format 272 3.2.1. Synopsis of prefix and Huffman coding 274 Prefix coding represents symbols from an a priori known 275 alphabet by bit sequences (codes), one code for each symbol, in 276 a manner such that different symbols may be represented by bit 277 sequences of different lengths, but a parser can always parse 278 an encoded string unambiguously symbol-by-symbol. 280 We define a prefix code in terms of a binary tree in which the 281 two edges descending from each non-leaf node are labeled 0 and 282 1 and in which the leaf nodes correspond one-for-one with (are 283 labeled with) the symbols of the alphabet; then the code for a 284 symbol is the sequence of 0's and 1's on the edges leading from 285 the root to the leaf labeled with that symbol. For example: 287 /\ Symbol Code 288 0 1 ------ ---- 289 / \ A 00 290 /\ B B 1 291 0 1 C 011 292 / \ D 010 293 A /\ 294 0 1 295 / \ 296 D C 298 A parser can decode the next symbol from an encoded input 299 stream by walking down the tree from the root, at each step 300 choosing the edge corresponding to the next input bit. 302 Given an alphabet with known symbol frequencies, the Huffman 303 algorithm allows the construction of an optimal prefix code 304 (one which represents strings with those symbol frequencies 305 using the fewest bits of any possible prefix codes for that 306 alphabet). Such a code is called a Huffman code. (See 307 reference [HUFFMAN] in Chapter 5, references for additional 308 information on Huffman codes.) 310 Note that in the 'deflate' format, the Huffman codes for the 311 various alphabets must not exceed certain maximum code lengths. 312 This constraint complicates the algorithm for computing code 313 lengths from symbol frequencies. Again, see Chapter 5, 314 references for details. 316 3.2.2. Use of Huffman coding in the 'deflate' format 318 The Huffman codes used for each alphabet in the 'deflate' 320 Deutsch [Page 6] 321 format have two additional rules: 323 o All codes of a given bit length have lexicographically 324 consecutive values, in the same order as the symbols they 325 represent; 327 o Shorter codes lexicographically precede longer codes. 329 We could recode the example above to follow this rule as 330 follows, assuming that the order of the alphabet is ABCD: 332 Symbol Code 333 ------ ---- 334 A 10 335 B 0 336 C 110 337 D 111 339 I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are 340 lexicographically consecutive. 342 Given this rule, we can define the Huffman code for an alphabet 343 just by giving the bit lengths of the codes for each symbol of 344 the alphabet in order; this is sufficient to determine the 345 actual codes. In our example, the code is completely defined 346 by the sequence of bit lengths (2, 1, 3, 3). The following 347 algorithm generates the codes as integers, intended to be read 348 from most- to least-significant bit. The code lengths are 349 initially in tree[I].Len; the codes are produced in 350 tree[I].Code. 352 1) Count the number of codes for each code length. Let 353 bl_count[N] be the number of codes of length N, N >= 1. 355 2) Find the numerical value of the smallest code for each code 356 length: 358 code = 0; 359 bl_count[0] = 0; 360 for (bits = 1; bits <= MAX_BITS; bits++) { 361 next_code[bits] = code 362 = (code + bl_count[bits-1]) << 1; 363 } 365 3) Assign numerical values to all codes, using consecutive 366 values for all codes of the same length with the base values 367 determined at step 2. Codes that are never used (which have a 368 bit length of zero) must not be assigned a value. 370 for (n = 0; n <= max_code; n++) { 371 len = tree[n].Len; 372 if (len == 0) continue; 374 Deutsch [Page 7] 375 tree[n].Code = next_code[len]++; 376 } 378 Example: 380 Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, 381 3, 2, 4, 4). After step 1, we have: 383 N bl_count[N] 384 - ----------- 385 2 1 386 3 5 387 4 2 389 Step 2 computes the following next_code values: 391 N next_code[N] 392 - ------------ 393 1 0 394 2 0 395 3 2 396 4 14 398 Step 3 produces the following code values: 400 Symbol Length Code 401 ------ ------ ---- 402 A 3 010 403 B 3 011 404 C 3 100 405 D 3 101 406 E 3 110 407 F 2 00 408 G 4 1110 409 H 4 1111 411 3.2.3. Details of block format 413 Each block of compressed data begins with 3 header bits 414 containing the following data: 416 first bit BFINAL 417 next 2 bits BTYPE 419 Note that the header bits do not necessarily begin on a byte 420 boundary, since a block does not necessarily occupy an integral 421 number of bytes. 423 BFINAL is set iff this is the last block of the data set. 425 Deutsch [Page 8] 426 BTYPE specifies how the data are compressed, as follows: 428 00 - no compression 429 01 - compressed with fixed Huffman codes 430 10 - compressed with dynamic Huffman codes 431 11 - reserved (error) 433 The only difference between the two compressed cases is how the 434 Huffman codes for the literal/length and distance alphabets are 435 defined. 437 In all cases, the decoding algorithm for the actual data is as 438 follows: 440 do 441 read block header from input stream. 442 if stored with no compression 443 skip any remaining bits in current partially 444 processed byte 445 read LEN and NLEN (see next section) 446 copy LEN bytes of data to output 447 otherwise 448 if compressed with dynamic Huffman codes 449 read representation of code trees (see 450 subsection below) 451 loop (until end of block code recognized) 452 decode literal/length value from input stream 453 if value < 256 454 copy value (literal byte) to output stream 455 otherwise 456 if value = end of block (256) 457 break from loop 458 otherwise (value = 257..285) 459 decode distance from input stream 461 move backwards distance bytes in the output 462 stream, and copy length bytes from this 463 position to the output stream. 464 end loop 465 while not last block 467 Note that a duplicated string reference may refer to a string 468 in a previous block; i.e., the backward distance may cross one 469 or more block boundaries. However a distance cannot refer past 470 the beginning of the output stream. Note also that the 471 referenced string may overlap the current position; for 472 example, if the last 2 bytes decoded have values X and Y, a 473 string reference with adds X,Y,X,Y,X 474 to the output stream. 476 We now specify each compression method in turn. 478 Deutsch [Page 9] 479 3.2.4. Non-compressed blocks (BTYPE=00) 481 Any bits of input up to the next byte boundary are ignored. 482 The rest of the block consists of the following information: 484 0 1 2 3 4... 485 +---+---+---+---+=================================+ 486 | LEN | NLEN |... LEN bytes of literal data...| 487 +---+---+---+---+=================================+ 489 LEN is the number of data bytes in the block. NLEN is the 490 one's complement of LEN. 492 3.2.5. Compressed blocks (length and distance codes) 494 As noted above, encoded data blocks in the 'deflate' format 495 consist of sequences of symbols drawn from three conceptually 496 distinct alphabets: either literal bytes, from the alphabet of 497 byte values (0..255), or pairs, 498 where the length is drawn from (3..258) and the distance is 499 drawn from (1..32,768). In fact, the literal and length 500 alphabets are merged into a single alphabet (0..285), where 501 values 0..255 represent literal bytes, the value 256 indicates 502 end-of-block, and values 257..285 represent length codes 503 (possibly in conjunction with extra bits following the symbol 504 code) as follows: 506 Extra Extra Extra 507 Code Bits Length(s) Code Bits Lengths Code Bits Length(s) 508 ---- ---- ------ ---- ---- ------- ---- ---- ------- 509 257 0 3 267 1 15,16 277 4 67-82 510 258 0 4 268 1 17,18 278 4 83-98 511 259 0 5 269 2 19-22 279 4 99-114 512 260 0 6 270 2 23-26 280 4 115-130 513 261 0 7 271 2 27-30 281 5 131-162 514 262 0 8 272 2 31-34 282 5 163-194 515 263 0 9 273 3 35-42 283 5 195-226 516 264 0 10 274 3 43-50 284 5 227-257 517 265 1 11,12 275 3 51-58 285 0 258 518 266 1 13,14 276 3 59-66 520 The extra bits should be interpreted as a machine integer 521 stored with the most-significant bit first, e.g., bits 1110 523 Deutsch [Page 10] 524 represent the value 14. 526 Extra Extra Extra 527 Code Bits Dist Code Bits Dist Code Bits Distance 528 ---- ---- ---- ---- ---- ------ ---- ---- -------- 529 0 0 1 10 4 33-48 20 9 1025-1536 530 1 0 2 11 4 49-64 21 9 1537-2048 531 2 0 3 12 5 65-96 22 10 2049-3072 532 3 0 4 13 5 97-128 23 10 3073-4096 533 4 1 5,6 14 6 129-192 24 11 4097-6144 534 5 1 7,8 15 6 193-256 25 11 6145-8192 535 6 2 9-12 16 7 257-384 26 12 8193-12288 536 7 2 13-16 17 7 385-512 27 12 12289-16384 537 8 3 17-24 18 8 513-768 28 13 16385-24576 538 9 3 25-32 19 8 769-1024 29 13 24577-32768 540 3.2.6. Compression with fixed Huffman codes (BTYPE=01) 542 The Huffman codes for the two alphabets are fixed, and are not 543 represented explicitly in the data. The Huffman code lengths 544 for the literal/length alphabet are: 546 Lit Value Bits Codes 547 --------- ---- ----- 548 0 - 143 8 00110000 through 549 10111111 550 144 - 255 9 110010000 through 551 111111111 552 256 - 279 7 0000000 through 553 0010111 554 280 - 287 8 11000000 through 555 11000111 557 The code lengths are sufficient to generate the actual codes, 558 as described above; we show the codes in the table for added 559 clarity. Literal/length values 286-287 will never actually 560 occur in the compressed data, but participate in the code 561 construction. 563 Distance codes 0-31 are represented by (fixed-length) 5-bit 564 codes, with possible additional bits as shown in the table 565 shown in Paragraph 3.2.5, above. Note that distance codes 30- 566 31 will never actually occur in the compressed data. 568 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) 570 The Huffman codes for the two alphabets appear in the block 571 immediately after the header bits and before the actual 572 compressed data, first the literal/length code and then the 573 distance code. Each code is defined by a sequence of code 574 lengths, as discussed in Paragraph 3.2.2, above. For even 575 greater compactness, the code length sequences themselves are 577 Deutsch [Page 11] 578 compressed using a Huffman code. The alphabet for code lengths 579 is as follows: 581 0 - 15: Represent code lengths of 0 - 15 582 16: Copy the previous code length 3 - 6 times. 583 The next 2 bits indicate repeat length 584 (0 = 3, ... , 3 = 6) 585 Example: Codes 8, 16 (+2 bits 11), 586 16 (+2 bits 10) will expand to 587 12 code lengths of 8 (1 + 6 + 5) 588 17: Repeat a code length of 0 for 3 - 10 times. 589 (3 bits of length) 590 18: Repeat a code length of 0 for 11 - 138 times 591 (7 bits of length) 593 A code length of 0 indicates that the corresponding symbol in 594 the literal/length or distance alphabet will not occur in the 595 block, and should not participate in the Huffman code 596 construction algorithm given earlier. If only one distance 597 code is used, it is encoded using one bit, not zero bits; in 598 this case there is a single code length of one, with one unused 599 code. One distance code of zero bits means that there are no 600 distance codes used at all (the data is all literals). 602 We can now define the format of the block: 604 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286) 605 5 Bits: HDIST, # of Distance codes - 1 (1 - 32) 606 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19) 608 (HCLEN + 4) x 3 bits: code lengths for the code length 609 alphabet given just above, in the order: 16, 17, 18, 610 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 612 These code lengths are interpreted as 3-bit integers 613 (0-7); as above, a code length of 0 means the 614 corresponding symbol (literal/length or distance code 615 length) is not used. 617 HLIT + 257 code lengths for the literal/length alphabet, 618 encoded using the code length Huffman code 620 HDIST + 1 code lengths for the distance alphabet, 621 encoded using the code length Huffman code 623 The actual compressed data of the block, 624 encoded using the literal/length and distance Huffman 625 codes 627 The literal/length symbol 256 (end of data), 628 encoded using the literal/length Huffman code 630 Deutsch [Page 12] 631 The code length repeat codes can cross from HLIT + 257 to the 632 HDIST + 1 code lengths. In other words, all code lengths form 633 a single sequence of HLIT + HDIST + 258 values. 635 3.3. Compliance 637 A compressor may limit further the ranges of values specified in 638 the previous section and still be compliant; for example, it may 639 limit the range of backward pointers to some value smaller than 640 32K. Similarly, a compressor may limit the size of blocks so that 641 a compressible block fits in memory. 643 A compliant decompressor must accept the full range of possible 644 values defined in the previous section, and must accept blocks of 645 arbitrary size. 647 4. Compression algorithm details 649 While it is the intent of this document to define the 'deflate' 650 compressed data format without reference to any particular 651 compression algorithm, the format is related to the compressed 652 formats produced by LZ77 (Lempel-Ziv 1977, see reference [LZ77] 653 below); since many variations of LZ77 are patented, it is strongly 654 recommended that the implementor of a compressor follow the general 655 algorithm presented here, which is known not to be patented per se. 656 The material in this section is not part of the definition of the 657 specification per se, and a compressor need not follow it in order to 658 be compliant. 660 The compressor terminates a block when it determines that starting a 661 new block with fresh trees would be useful, or when the block size 662 fills up the compressor's block buffer. 664 The compressor uses a chained hash table to find duplicated strings, 665 using a hash function that operates on 3-byte sequences. At any 666 given point during compression, let XYZ be the next 3 input bytes to 667 be examined (not necessarily all different, of course). First, the 668 compressor examines the hash chain for XYZ. If the chain is empty, 669 the compressor simply writes out X as a literal byte and advances one 670 byte in the input. If the hash chain is not empty, indicating that 671 the sequence XYZ (or, if we are unlucky, some other 3 bytes with the 672 same hash function value) has occurred recently, the compressor 673 compares all strings on the XYZ hash chain with the actual input data 674 sequence starting at the current point, and selects the longest 675 match. 677 The compressor searches the hash chains starting with the most recent 678 strings, to favor small distances and thus take advantage of the 679 Huffman encoding. The hash chains are singly linked. There are no 680 deletions from the hash chains; the algorithm simply discards matches 681 that are too old. To avoid a worst-case situation, very long hash 682 chains are arbitrarily truncated at a certain length, determined by a 684 Deutsch [Page 13] 685 run-time parameter. 687 To improve overall compression, the compressor optionally defers the 688 selection of matches ("lazy matching"): after a match of length N has 689 been found, the compressor searches for a longer match starting at 690 the next input byte. If it finds a longer match, it truncates the 691 previous match to a length of one (thus producing a single literal 692 byte) and then emits the longer match. Otherwise, it emits the 693 original match, and, as described above, advances N bytes before 694 continuing. 696 Run-time parameters also control this "lazy match" procedure. If 697 compression ratio is most important, the compressor attempts a 698 complete second search regardless of the length of the first match. 699 In the normal case, if the current match is "long enough", the 700 compressor reduces the search for a longer match, thus speeding up 701 the process. If speed is most important, the compressor inserts new 702 strings in the hash table only when no match was found, or when the 703 match is not "too long". This degrades the compression ratio but 704 saves time since there are both fewer insertions and fewer searches. 706 5. References 708 [GZIP] Gailly, J.-L., and Adler, M., gzip documentation and sources, 709 available in prep.ai.mit.edu:/pub/gnu/gzip-*.tar 711 [ZLIB] Gailly, J.-L., and Adler, M., zlib documentation and sources, 712 available in ftp.uu.net:/pub/archiving/zip/doc/zlib* 714 [LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data 715 Compression", IEEE Transactions on Information Theory", Vol. 23, No. 716 3, pp. 337-343. 718 [HUFFMAN] Huffman, D. A., 'A Method for the Construction of Minimum 719 Redundancy Codes', Proceedings of the Institute of Radio Engineers, 720 September 1952, Volume 40, Number 9, pp. 1098-1101. 722 [SCHWARTZ] Schwartz, E. S., and Kallick, B. "Generating a canonical 723 prefix encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169. 725 [HIRSCHBERG] "Efficient decoding of prefix codes", Hirschberg and 726 Lelewer, Comm. ACM, 33,4, April 1990, pp. 449-459. 728 6. Security considerations 730 Any data compression method involves the reduction of redundancy in 731 the data. Consequently, any corruption of the data is likely to have 732 severe effects and be difficult to correct. Uncompressed text, on 733 the other hand, will probably still be readable despite the presence 734 of some corrupted bytes. 736 It is recommended that systems using this data format provide some 738 Deutsch [Page 14] 739 means of validating the integrity of the compressed data. See 740 reference [ZLIB], for example. 742 7. Source code 744 Source code for a C language implementation of a 'deflate' compliant 745 compressor and decompressor is available within the zlib package at 746 ftp.uu.net:/pub/archiving/zip/zlib/zlib*. 748 8. Acknowledgements 750 Trademarks cited in this document are the property of their 751 respective owners. 753 Phil Katz designed the deflate format. Jean-Loup Gailly and Mark 754 Adler wrote the related software described in this specification. 755 Glenn Randers-Pehrson converted this document to Internet Draft and 756 HTML format. 758 9. Author's address 760 L. Peter Deutsch 762 Aladdin Enterprises 763 203 Santa Margarita Ave. 764 Menlo Park, CA 94025 766 Phone: (415) 322-0103 (AM only) 767 FAX: (415) 322-1734 768 EMail: 770 Questions about the technical content of this specification can be 771 sent by email to 773 Jean-loup Gailly and 774 Mark Adler 776 Editorial comments on this specification can be sent by email to 778 L. Peter Deutsch and 779 Glenn Randers-Pehrson 781 Deutsch [Page 15]