1 2 3 4 5 6 7Network Working Group P. Deutsch 8Request for Comments: 1950 Aladdin Enterprises 9Category: Informational J-L. Gailly 10 Info-ZIP 11 May 1996 12 13 14 ZLIB Compressed Data Format Specification version 3.3 15 16Status of This Memo 17 18 This memo provides information for the Internet community. This memo 19 does not specify an Internet standard of any kind. Distribution of 20 this memo is unlimited. 21 22IESG Note: 23 24 The IESG takes no position on the validity of any Intellectual 25 Property Rights statements contained in this document. 26 27Notices 28 29 Copyright (c) 1996 L. Peter Deutsch and Jean-Loup Gailly 30 31 Permission is granted to copy and distribute this document for any 32 purpose and without charge, including translations into other 33 languages and incorporation into compilations, provided that the 34 copyright notice and this notice are preserved, and that any 35 substantive changes or deletions from the original are clearly 36 marked. 37 38 A pointer to the latest version of this and related documentation in 39 HTML format can be found at the URL 40 <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>. 41 42Abstract 43 44 This specification defines a lossless compressed data format. The 45 data can be produced or consumed, even for an arbitrarily long 46 sequentially presented input data stream, using only an a priori 47 bounded amount of intermediate storage. The format presently uses 48 the DEFLATE compression method but can be easily extended to use 49 other compression methods. It can be implemented readily in a manner 50 not covered by patents. This specification also defines the ADLER-32 51 checksum (an extension and improvement of the Fletcher checksum), 52 used for detection of data corruption, and provides an algorithm for 53 computing it. 54 55 56 57 58Deutsch & Gailly Informational [Page 1] 59 60RFC 1950 ZLIB Compressed Data Format Specification May 1996 61 62 63Table 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 ............................ 3 72 2. Detailed specification ......................................... 3 73 2.1. Overall conventions ....................................... 3 74 2.2. Data format ............................................... 4 75 2.3. Compliance ................................................ 7 76 3. References ..................................................... 7 77 4. Source code .................................................... 8 78 5. Security Considerations ........................................ 8 79 6. Acknowledgements ............................................... 8 80 7. Authors' Addresses ............................................. 8 81 8. Appendix: Rationale ............................................ 9 82 9. Appendix: Sample code ..........................................10 83 841. Introduction 85 86 1.1. Purpose 87 88 The purpose of this specification is to define a lossless 89 compressed data format that: 90 91 * Is independent of CPU type, operating system, file system, 92 and character set, and hence can be used for interchange; 93 94 * Can be produced or consumed, even for an arbitrarily long 95 sequentially presented input data stream, using only an a 96 priori bounded amount of intermediate storage, and hence can 97 be used in data communications or similar structures such as 98 Unix filters; 99 100 * Can use a number of different compression methods; 101 102 * Can be implemented readily in a manner not covered by 103 patents, and hence can be practiced freely. 104 105 The data format defined by this specification does not attempt to 106 allow random access to compressed data. 107 108 109 110 111 112 113 114Deutsch & Gailly Informational [Page 2] 115 116RFC 1950 ZLIB Compressed Data Format Specification May 1996 117 118 119 1.2. Intended audience 120 121 This specification is intended for use by implementors of software 122 to compress data into zlib format and/or decompress data from zlib 123 format. 124 125 The text of the specification assumes a basic background in 126 programming at the level of bits and other primitive data 127 representations. 128 129 1.3. Scope 130 131 The specification specifies a compressed data format that can be 132 used for in-memory compression of a sequence of arbitrary bytes. 133 134 1.4. Compliance 135 136 Unless otherwise indicated below, a compliant decompressor must be 137 able to accept and decompress any data set that conforms to all 138 the specifications presented here; a compliant compressor must 139 produce data sets that conform to all the specifications presented 140 here. 141 142 1.5. Definitions of terms and conventions used 143 144 byte: 8 bits stored or transmitted as a unit (same as an octet). 145 (For this specification, a byte is exactly 8 bits, even on 146 machines which store a character on a number of bits different 147 from 8.) See below, for the numbering of bits within a byte. 148 149 1.6. Changes from previous versions 150 151 Version 3.1 was the first public release of this specification. 152 In version 3.2, some terminology was changed and the Adler-32 153 sample code was rewritten for clarity. In version 3.3, the 154 support for a preset dictionary was introduced, and the 155 specification was converted to RFC style. 156 1572. Detailed specification 158 159 2.1. Overall conventions 160 161 In the diagrams below, a box like this: 162 163 +---+ 164 | | <-- the vertical bars might be missing 165 +---+ 166 167 168 169 170Deutsch & Gailly Informational [Page 3] 171 172RFC 1950 ZLIB Compressed Data Format Specification May 1996 173 174 175 represents one byte; a box like this: 176 177 +==============+ 178 | | 179 +==============+ 180 181 represents a variable number of bytes. 182 183 Bytes stored within a computer do not have a "bit order", since 184 they are always treated as a unit. However, a byte considered as 185 an integer between 0 and 255 does have a most- and least- 186 significant bit, and since we write numbers with the most- 187 significant digit on the left, we also write bytes with the most- 188 significant bit on the left. In the diagrams below, we number the 189 bits of a byte so that bit 0 is the least-significant bit, i.e., 190 the bits are numbered: 191 192 +--------+ 193 |76543210| 194 +--------+ 195 196 Within a computer, a number may occupy multiple bytes. All 197 multi-byte numbers in the format described here are stored with 198 the MOST-significant byte first (at the lower memory address). 199 For example, the decimal number 520 is stored as: 200 201 0 1 202 +--------+--------+ 203 |00000010|00001000| 204 +--------+--------+ 205 ^ ^ 206 | | 207 | + less significant byte = 8 208 + more significant byte = 2 x 256 209 210 2.2. Data format 211 212 A zlib stream has the following structure: 213 214 0 1 215 +---+---+ 216 |CMF|FLG| (more-->) 217 +---+---+ 218 219 220 221 222 223 224 225 226Deutsch & Gailly Informational [Page 4] 227 228RFC 1950 ZLIB Compressed Data Format Specification May 1996 229 230 231 (if FLG.FDICT set) 232 233 0 1 2 3 234 +---+---+---+---+ 235 | DICTID | (more-->) 236 +---+---+---+---+ 237 238 +=====================+---+---+---+---+ 239 |...compressed data...| ADLER32 | 240 +=====================+---+---+---+---+ 241 242 Any data which may appear after ADLER32 are not part of the zlib 243 stream. 244 245 CMF (Compression Method and flags) 246 This byte is divided into a 4-bit compression method and a 4- 247 bit information field depending on the compression method. 248 249 bits 0 to 3 CM Compression method 250 bits 4 to 7 CINFO Compression info 251 252 CM (Compression method) 253 This identifies the compression method used in the file. CM = 8 254 denotes the "deflate" compression method with a window size up 255 to 32K. This is the method used by gzip and PNG (see 256 references [1] and [2] in Chapter 3, below, for the reference 257 documents). CM = 15 is reserved. It might be used in a future 258 version of this specification to indicate the presence of an 259 extra field before the compressed data. 260 261 CINFO (Compression info) 262 For CM = 8, CINFO is the base-2 logarithm of the LZ77 window 263 size, minus eight (CINFO=7 indicates a 32K window size). Values 264 of CINFO above 7 are not allowed in this version of the 265 specification. CINFO is not defined in this specification for 266 CM not equal to 8. 267 268 FLG (FLaGs) 269 This flag byte is divided as follows: 270 271 bits 0 to 4 FCHECK (check bits for CMF and FLG) 272 bit 5 FDICT (preset dictionary) 273 bits 6 to 7 FLEVEL (compression level) 274 275 The FCHECK value must be such that CMF and FLG, when viewed as 276 a 16-bit unsigned integer stored in MSB order (CMF*256 + FLG), 277 is a multiple of 31. 278 279 280 281 282Deutsch & Gailly Informational [Page 5] 283 284RFC 1950 ZLIB Compressed Data Format Specification May 1996 285 286 287 FDICT (Preset dictionary) 288 If FDICT is set, a DICT dictionary identifier is present 289 immediately after the FLG byte. The dictionary is a sequence of 290 bytes which are initially fed to the compressor without 291 producing any compressed output. DICT is the Adler-32 checksum 292 of this sequence of bytes (see the definition of ADLER32 293 below). The decompressor can use this identifier to determine 294 which dictionary has been used by the compressor. 295 296 FLEVEL (Compression level) 297 These flags are available for use by specific compression 298 methods. The "deflate" method (CM = 8) sets these flags as 299 follows: 300 301 0 - compressor used fastest algorithm 302 1 - compressor used fast algorithm 303 2 - compressor used default algorithm 304 3 - compressor used maximum compression, slowest algorithm 305 306 The information in FLEVEL is not needed for decompression; it 307 is there to indicate if recompression might be worthwhile. 308 309 compressed data 310 For compression method 8, the compressed data is stored in the 311 deflate compressed data format as described in the document 312 "DEFLATE Compressed Data Format Specification" by L. Peter 313 Deutsch. (See reference [3] in Chapter 3, below) 314 315 Other compressed data formats are not specified in this version 316 of the zlib specification. 317 318 ADLER32 (Adler-32 checksum) 319 This contains a checksum value of the uncompressed data 320 (excluding any dictionary data) computed according to Adler-32 321 algorithm. This algorithm is a 32-bit extension and improvement 322 of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073 323 standard. See references [4] and [5] in Chapter 3, below) 324 325 Adler-32 is composed of two sums accumulated per byte: s1 is 326 the sum of all bytes, s2 is the sum of all s1 values. Both sums 327 are done modulo 65521. s1 is initialized to 1, s2 to zero. The 328 Adler-32 checksum is stored as s2*65536 + s1 in most- 329 significant-byte first (network) order. 330 331 332 333 334 335 336 337 338Deutsch & Gailly Informational [Page 6] 339 340RFC 1950 ZLIB Compressed Data Format Specification May 1996 341 342 343 2.3. Compliance 344 345 A compliant compressor must produce streams with correct CMF, FLG 346 and ADLER32, but need not support preset dictionaries. When the 347 zlib data format is used as part of another standard data format, 348 the compressor may use only preset dictionaries that are specified 349 by this other data format. If this other format does not use the 350 preset dictionary feature, the compressor must not set the FDICT 351 flag. 352 353 A compliant decompressor must check CMF, FLG, and ADLER32, and 354 provide an error indication if any of these have incorrect values. 355 A compliant decompressor must give an error indication if CM is 356 not one of the values defined in this specification (only the 357 value 8 is permitted in this version), since another value could 358 indicate the presence of new features that would cause subsequent 359 data to be interpreted incorrectly. A compliant decompressor must 360 give an error indication if FDICT is set and DICTID is not the 361 identifier of a known preset dictionary. A decompressor may 362 ignore FLEVEL and still be compliant. When the zlib data format 363 is being used as a part of another standard format, a compliant 364 decompressor must support all the preset dictionaries specified by 365 the other format. When the other format does not use the preset 366 dictionary feature, a compliant decompressor must reject any 367 stream in which the FDICT flag is set. 368 3693. References 370 371 [1] Deutsch, L.P.,"GZIP Compressed Data Format Specification", 372 available in ftp://ftp.uu.net/pub/archiving/zip/doc/ 373 374 [2] Thomas Boutell, "PNG (Portable Network Graphics) specification", 375 available in ftp://ftp.uu.net/graphics/png/documents/ 376 377 [3] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification", 378 available in ftp://ftp.uu.net/pub/archiving/zip/doc/ 379 380 [4] Fletcher, J. G., "An Arithmetic Checksum for Serial 381 Transmissions," IEEE Transactions on Communications, Vol. COM-30, 382 No. 1, January 1982, pp. 247-252. 383 384 [5] ITU-T Recommendation X.224, Annex D, "Checksum Algorithms," 385 November, 1993, pp. 144, 145. (Available from 386 gopher://info.itu.ch). ITU-T X.244 is also the same as ISO 8073. 387 388 389 390 391 392 393 394Deutsch & Gailly Informational [Page 7] 395 396RFC 1950 ZLIB Compressed Data Format Specification May 1996 397 398 3994. Source code 400 401 Source code for a C language implementation of a "zlib" compliant 402 library is available at ftp://ftp.uu.net/pub/archiving/zip/zlib/. 403 4045. Security Considerations 405 406 A decoder that fails to check the ADLER32 checksum value may be 407 subject to undetected data corruption. 408 4096. Acknowledgements 410 411 Trademarks cited in this document are the property of their 412 respective owners. 413 414 Jean-Loup Gailly and Mark Adler designed the zlib format and wrote 415 the related software described in this specification. Glenn 416 Randers-Pehrson converted this document to RFC and HTML format. 417 4187. Authors' Addresses 419 420 L. Peter Deutsch 421 Aladdin Enterprises 422 203 Santa Margarita Ave. 423 Menlo Park, CA 94025 424 425 Phone: (415) 322-0103 (AM only) 426 FAX: (415) 322-1734 427 EMail: <ghost@aladdin.com> 428 429 430 Jean-Loup Gailly 431 432 EMail: <gzip@prep.ai.mit.edu> 433 434 Questions about the technical content of this specification can be 435 sent by email to 436 437 Jean-Loup Gailly <gzip@prep.ai.mit.edu> and 438 Mark Adler <madler@alumni.caltech.edu> 439 440 Editorial comments on this specification can be sent by email to 441 442 L. Peter Deutsch <ghost@aladdin.com> and 443 Glenn Randers-Pehrson <randeg@alumni.rpi.edu> 444 445 446 447 448 449 450Deutsch & Gailly Informational [Page 8] 451 452RFC 1950 ZLIB Compressed Data Format Specification May 1996 453 454 4558. Appendix: Rationale 456 457 8.1. Preset dictionaries 458 459 A preset dictionary is specially useful to compress short input 460 sequences. The compressor can take advantage of the dictionary 461 context to encode the input in a more compact manner. The 462 decompressor can be initialized with the appropriate context by 463 virtually decompressing a compressed version of the dictionary 464 without producing any output. However for certain compression 465 algorithms such as the deflate algorithm this operation can be 466 achieved without actually performing any decompression. 467 468 The compressor and the decompressor must use exactly the same 469 dictionary. The dictionary may be fixed or may be chosen among a 470 certain number of predefined dictionaries, according to the kind 471 of input data. The decompressor can determine which dictionary has 472 been chosen by the compressor by checking the dictionary 473 identifier. This document does not specify the contents of 474 predefined dictionaries, since the optimal dictionaries are 475 application specific. Standard data formats using this feature of 476 the zlib specification must precisely define the allowed 477 dictionaries. 478 479 8.2. The Adler-32 algorithm 480 481 The Adler-32 algorithm is much faster than the CRC32 algorithm yet 482 still provides an extremely low probability of undetected errors. 483 484 The modulo on unsigned long accumulators can be delayed for 5552 485 bytes, so the modulo operation time is negligible. If the bytes 486 are a, b, c, the second sum is 3a + 2b + c + 3, and so is position 487 and order sensitive, unlike the first sum, which is just a 488 checksum. That 65521 is prime is important to avoid a possible 489 large class of two-byte errors that leave the check unchanged. 490 (The Fletcher checksum uses 255, which is not prime and which also 491 makes the Fletcher check insensitive to single byte changes 0 <-> 492 255.) 493 494 The sum s1 is initialized to 1 instead of zero to make the length 495 of the sequence part of s2, so that the length does not have to be 496 checked separately. (Any sequence of zeroes has a Fletcher 497 checksum of zero.) 498 499 500 501 502 503 504 505 506Deutsch & Gailly Informational [Page 9] 507 508RFC 1950 ZLIB Compressed Data Format Specification May 1996 509 510 5119. Appendix: Sample code 512 513 The following C code computes the Adler-32 checksum of a data buffer. 514 It is written for clarity, not for speed. The sample code is in the 515 ANSI C programming language. Non C users may find it easier to read 516 with these hints: 517 518 & Bitwise AND operator. 519 >> Bitwise right shift operator. When applied to an 520 unsigned quantity, as here, right shift inserts zero bit(s) 521 at the left. 522 << Bitwise left shift operator. Left shift inserts zero 523 bit(s) at the right. 524 ++ "n++" increments the variable n. 525 % modulo operator: a % b is the remainder of a divided by b. 526 527 #define BASE 65521 /* largest prime smaller than 65536 */ 528 529 /* 530 Update a running Adler-32 checksum with the bytes buf[0..len-1] 531 and return the updated checksum. The Adler-32 checksum should be 532 initialized to 1. 533 534 Usage example: 535 536 unsigned long adler = 1L; 537 538 while (read_buffer(buffer, length) != EOF) { 539 adler = update_adler32(adler, buffer, length); 540 } 541 if (adler != original_adler) error(); 542 */ 543 unsigned long update_adler32(unsigned long adler, 544 unsigned char *buf, int len) 545 { 546 unsigned long s1 = adler & 0xffff; 547 unsigned long s2 = (adler >> 16) & 0xffff; 548 int n; 549 550 for (n = 0; n < len; n++) { 551 s1 = (s1 + buf[n]) % BASE; 552 s2 = (s2 + s1) % BASE; 553 } 554 return (s2 << 16) + s1; 555 } 556 557 /* Return the adler32 of the bytes buf[0..len-1] */ 558 559 560 561 562Deutsch & Gailly Informational [Page 10] 563 564RFC 1950 ZLIB Compressed Data Format Specification May 1996 565 566 567 unsigned long adler32(unsigned char *buf, int len) 568 { 569 return update_adler32(1L, buf, len); 570 } 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618Deutsch & Gailly Informational [Page 11] 619 620