cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Network Working Group P. Deutsch cannam@89: Request for Comments: 1950 Aladdin Enterprises cannam@89: Category: Informational J-L. Gailly cannam@89: Info-ZIP cannam@89: May 1996 cannam@89: cannam@89: cannam@89: ZLIB Compressed Data Format Specification version 3.3 cannam@89: cannam@89: Status of This Memo cannam@89: cannam@89: This memo provides information for the Internet community. This memo cannam@89: does not specify an Internet standard of any kind. Distribution of cannam@89: this memo is unlimited. cannam@89: cannam@89: IESG Note: cannam@89: cannam@89: The IESG takes no position on the validity of any Intellectual cannam@89: Property Rights statements contained in this document. cannam@89: cannam@89: Notices cannam@89: cannam@89: Copyright (c) 1996 L. Peter Deutsch and Jean-Loup Gailly cannam@89: cannam@89: Permission is granted to copy and distribute this document for any cannam@89: purpose and without charge, including translations into other cannam@89: languages and incorporation into compilations, provided that the cannam@89: copyright notice and this notice are preserved, and that any cannam@89: substantive changes or deletions from the original are clearly cannam@89: marked. cannam@89: cannam@89: A pointer to the latest version of this and related documentation in cannam@89: HTML format can be found at the URL cannam@89: . cannam@89: cannam@89: Abstract cannam@89: cannam@89: This specification defines a lossless compressed data format. The cannam@89: data can be produced or consumed, even for an arbitrarily long cannam@89: sequentially presented input data stream, using only an a priori cannam@89: bounded amount of intermediate storage. The format presently uses cannam@89: the DEFLATE compression method but can be easily extended to use cannam@89: other compression methods. It can be implemented readily in a manner cannam@89: not covered by patents. This specification also defines the ADLER-32 cannam@89: checksum (an extension and improvement of the Fletcher checksum), cannam@89: used for detection of data corruption, and provides an algorithm for cannam@89: computing it. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 1] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: Table of Contents cannam@89: cannam@89: 1. Introduction ................................................... 2 cannam@89: 1.1. Purpose ................................................... 2 cannam@89: 1.2. Intended audience ......................................... 3 cannam@89: 1.3. Scope ..................................................... 3 cannam@89: 1.4. Compliance ................................................ 3 cannam@89: 1.5. Definitions of terms and conventions used ................ 3 cannam@89: 1.6. Changes from previous versions ............................ 3 cannam@89: 2. Detailed specification ......................................... 3 cannam@89: 2.1. Overall conventions ....................................... 3 cannam@89: 2.2. Data format ............................................... 4 cannam@89: 2.3. Compliance ................................................ 7 cannam@89: 3. References ..................................................... 7 cannam@89: 4. Source code .................................................... 8 cannam@89: 5. Security Considerations ........................................ 8 cannam@89: 6. Acknowledgements ............................................... 8 cannam@89: 7. Authors' Addresses ............................................. 8 cannam@89: 8. Appendix: Rationale ............................................ 9 cannam@89: 9. Appendix: Sample code ..........................................10 cannam@89: cannam@89: 1. Introduction cannam@89: cannam@89: 1.1. Purpose cannam@89: cannam@89: The purpose of this specification is to define a lossless cannam@89: compressed data format that: cannam@89: cannam@89: * Is independent of CPU type, operating system, file system, cannam@89: and character set, and hence can be used for interchange; cannam@89: cannam@89: * Can be produced or consumed, even for an arbitrarily long cannam@89: sequentially presented input data stream, using only an a cannam@89: priori bounded amount of intermediate storage, and hence can cannam@89: be used in data communications or similar structures such as cannam@89: Unix filters; cannam@89: cannam@89: * Can use a number of different compression methods; cannam@89: cannam@89: * Can be implemented readily in a manner not covered by cannam@89: patents, and hence can be practiced freely. cannam@89: cannam@89: The data format defined by this specification does not attempt to cannam@89: allow random access to compressed data. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 2] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 1.2. Intended audience cannam@89: cannam@89: This specification is intended for use by implementors of software cannam@89: to compress data into zlib format and/or decompress data from zlib cannam@89: format. cannam@89: cannam@89: The text of the specification assumes a basic background in cannam@89: programming at the level of bits and other primitive data cannam@89: representations. cannam@89: cannam@89: 1.3. Scope cannam@89: cannam@89: The specification specifies a compressed data format that can be cannam@89: used for in-memory compression of a sequence of arbitrary bytes. cannam@89: cannam@89: 1.4. Compliance cannam@89: cannam@89: Unless otherwise indicated below, a compliant decompressor must be cannam@89: able to accept and decompress any data set that conforms to all cannam@89: the specifications presented here; a compliant compressor must cannam@89: produce data sets that conform to all the specifications presented cannam@89: here. cannam@89: cannam@89: 1.5. Definitions of terms and conventions used cannam@89: cannam@89: byte: 8 bits stored or transmitted as a unit (same as an octet). cannam@89: (For this specification, a byte is exactly 8 bits, even on cannam@89: machines which store a character on a number of bits different cannam@89: from 8.) See below, for the numbering of bits within a byte. cannam@89: cannam@89: 1.6. Changes from previous versions cannam@89: cannam@89: Version 3.1 was the first public release of this specification. cannam@89: In version 3.2, some terminology was changed and the Adler-32 cannam@89: sample code was rewritten for clarity. In version 3.3, the cannam@89: support for a preset dictionary was introduced, and the cannam@89: specification was converted to RFC style. cannam@89: cannam@89: 2. Detailed specification cannam@89: cannam@89: 2.1. Overall conventions cannam@89: cannam@89: In the diagrams below, a box like this: cannam@89: cannam@89: +---+ cannam@89: | | <-- the vertical bars might be missing cannam@89: +---+ cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 3] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: represents one byte; a box like this: cannam@89: cannam@89: +==============+ cannam@89: | | cannam@89: +==============+ cannam@89: cannam@89: represents a variable number of bytes. cannam@89: cannam@89: Bytes stored within a computer do not have a "bit order", since cannam@89: they are always treated as a unit. However, a byte considered as cannam@89: an integer between 0 and 255 does have a most- and least- cannam@89: significant bit, and since we write numbers with the most- cannam@89: significant digit on the left, we also write bytes with the most- cannam@89: significant bit on the left. In the diagrams below, we number the cannam@89: bits of a byte so that bit 0 is the least-significant bit, i.e., cannam@89: the bits are numbered: cannam@89: cannam@89: +--------+ cannam@89: |76543210| cannam@89: +--------+ cannam@89: cannam@89: Within a computer, a number may occupy multiple bytes. All cannam@89: multi-byte numbers in the format described here are stored with cannam@89: the MOST-significant byte first (at the lower memory address). cannam@89: For example, the decimal number 520 is stored as: cannam@89: cannam@89: 0 1 cannam@89: +--------+--------+ cannam@89: |00000010|00001000| cannam@89: +--------+--------+ cannam@89: ^ ^ cannam@89: | | cannam@89: | + less significant byte = 8 cannam@89: + more significant byte = 2 x 256 cannam@89: cannam@89: 2.2. Data format cannam@89: cannam@89: A zlib stream has the following structure: cannam@89: cannam@89: 0 1 cannam@89: +---+---+ cannam@89: |CMF|FLG| (more-->) cannam@89: +---+---+ cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 4] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: (if FLG.FDICT set) cannam@89: cannam@89: 0 1 2 3 cannam@89: +---+---+---+---+ cannam@89: | DICTID | (more-->) cannam@89: +---+---+---+---+ cannam@89: cannam@89: +=====================+---+---+---+---+ cannam@89: |...compressed data...| ADLER32 | cannam@89: +=====================+---+---+---+---+ cannam@89: cannam@89: Any data which may appear after ADLER32 are not part of the zlib cannam@89: stream. cannam@89: cannam@89: CMF (Compression Method and flags) cannam@89: This byte is divided into a 4-bit compression method and a 4- cannam@89: bit information field depending on the compression method. cannam@89: cannam@89: bits 0 to 3 CM Compression method cannam@89: bits 4 to 7 CINFO Compression info cannam@89: cannam@89: CM (Compression method) cannam@89: This identifies the compression method used in the file. CM = 8 cannam@89: denotes the "deflate" compression method with a window size up cannam@89: to 32K. This is the method used by gzip and PNG (see cannam@89: references [1] and [2] in Chapter 3, below, for the reference cannam@89: documents). CM = 15 is reserved. It might be used in a future cannam@89: version of this specification to indicate the presence of an cannam@89: extra field before the compressed data. cannam@89: cannam@89: CINFO (Compression info) cannam@89: For CM = 8, CINFO is the base-2 logarithm of the LZ77 window cannam@89: size, minus eight (CINFO=7 indicates a 32K window size). Values cannam@89: of CINFO above 7 are not allowed in this version of the cannam@89: specification. CINFO is not defined in this specification for cannam@89: CM not equal to 8. cannam@89: cannam@89: FLG (FLaGs) cannam@89: This flag byte is divided as follows: cannam@89: cannam@89: bits 0 to 4 FCHECK (check bits for CMF and FLG) cannam@89: bit 5 FDICT (preset dictionary) cannam@89: bits 6 to 7 FLEVEL (compression level) cannam@89: cannam@89: The FCHECK value must be such that CMF and FLG, when viewed as cannam@89: a 16-bit unsigned integer stored in MSB order (CMF*256 + FLG), cannam@89: is a multiple of 31. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 5] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: FDICT (Preset dictionary) cannam@89: If FDICT is set, a DICT dictionary identifier is present cannam@89: immediately after the FLG byte. The dictionary is a sequence of cannam@89: bytes which are initially fed to the compressor without cannam@89: producing any compressed output. DICT is the Adler-32 checksum cannam@89: of this sequence of bytes (see the definition of ADLER32 cannam@89: below). The decompressor can use this identifier to determine cannam@89: which dictionary has been used by the compressor. cannam@89: cannam@89: FLEVEL (Compression level) cannam@89: These flags are available for use by specific compression cannam@89: methods. The "deflate" method (CM = 8) sets these flags as cannam@89: follows: cannam@89: cannam@89: 0 - compressor used fastest algorithm cannam@89: 1 - compressor used fast algorithm cannam@89: 2 - compressor used default algorithm cannam@89: 3 - compressor used maximum compression, slowest algorithm cannam@89: cannam@89: The information in FLEVEL is not needed for decompression; it cannam@89: is there to indicate if recompression might be worthwhile. cannam@89: cannam@89: compressed data cannam@89: For compression method 8, the compressed data is stored in the cannam@89: deflate compressed data format as described in the document cannam@89: "DEFLATE Compressed Data Format Specification" by L. Peter cannam@89: Deutsch. (See reference [3] in Chapter 3, below) cannam@89: cannam@89: Other compressed data formats are not specified in this version cannam@89: of the zlib specification. cannam@89: cannam@89: ADLER32 (Adler-32 checksum) cannam@89: This contains a checksum value of the uncompressed data cannam@89: (excluding any dictionary data) computed according to Adler-32 cannam@89: algorithm. This algorithm is a 32-bit extension and improvement cannam@89: of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073 cannam@89: standard. See references [4] and [5] in Chapter 3, below) cannam@89: cannam@89: Adler-32 is composed of two sums accumulated per byte: s1 is cannam@89: the sum of all bytes, s2 is the sum of all s1 values. Both sums cannam@89: are done modulo 65521. s1 is initialized to 1, s2 to zero. The cannam@89: Adler-32 checksum is stored as s2*65536 + s1 in most- cannam@89: significant-byte first (network) order. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 6] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 2.3. Compliance cannam@89: cannam@89: A compliant compressor must produce streams with correct CMF, FLG cannam@89: and ADLER32, but need not support preset dictionaries. When the cannam@89: zlib data format is used as part of another standard data format, cannam@89: the compressor may use only preset dictionaries that are specified cannam@89: by this other data format. If this other format does not use the cannam@89: preset dictionary feature, the compressor must not set the FDICT cannam@89: flag. cannam@89: cannam@89: A compliant decompressor must check CMF, FLG, and ADLER32, and cannam@89: provide an error indication if any of these have incorrect values. cannam@89: A compliant decompressor must give an error indication if CM is cannam@89: not one of the values defined in this specification (only the cannam@89: value 8 is permitted in this version), since another value could cannam@89: indicate the presence of new features that would cause subsequent cannam@89: data to be interpreted incorrectly. A compliant decompressor must cannam@89: give an error indication if FDICT is set and DICTID is not the cannam@89: identifier of a known preset dictionary. A decompressor may cannam@89: ignore FLEVEL and still be compliant. When the zlib data format cannam@89: is being used as a part of another standard format, a compliant cannam@89: decompressor must support all the preset dictionaries specified by cannam@89: the other format. When the other format does not use the preset cannam@89: dictionary feature, a compliant decompressor must reject any cannam@89: stream in which the FDICT flag is set. cannam@89: cannam@89: 3. References cannam@89: cannam@89: [1] Deutsch, L.P.,"GZIP Compressed Data Format Specification", cannam@89: available in ftp://ftp.uu.net/pub/archiving/zip/doc/ cannam@89: cannam@89: [2] Thomas Boutell, "PNG (Portable Network Graphics) specification", cannam@89: available in ftp://ftp.uu.net/graphics/png/documents/ cannam@89: cannam@89: [3] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification", cannam@89: available in ftp://ftp.uu.net/pub/archiving/zip/doc/ cannam@89: cannam@89: [4] Fletcher, J. G., "An Arithmetic Checksum for Serial cannam@89: Transmissions," IEEE Transactions on Communications, Vol. COM-30, cannam@89: No. 1, January 1982, pp. 247-252. cannam@89: cannam@89: [5] ITU-T Recommendation X.224, Annex D, "Checksum Algorithms," cannam@89: November, 1993, pp. 144, 145. (Available from cannam@89: gopher://info.itu.ch). ITU-T X.244 is also the same as ISO 8073. cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 7] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 4. Source code cannam@89: cannam@89: Source code for a C language implementation of a "zlib" compliant cannam@89: library is available at ftp://ftp.uu.net/pub/archiving/zip/zlib/. cannam@89: cannam@89: 5. Security Considerations cannam@89: cannam@89: A decoder that fails to check the ADLER32 checksum value may be cannam@89: subject to undetected data corruption. cannam@89: cannam@89: 6. Acknowledgements cannam@89: cannam@89: Trademarks cited in this document are the property of their cannam@89: respective owners. cannam@89: cannam@89: Jean-Loup Gailly and Mark Adler designed the zlib format and wrote cannam@89: the related software described in this specification. Glenn cannam@89: Randers-Pehrson converted this document to RFC and HTML format. cannam@89: cannam@89: 7. Authors' Addresses cannam@89: cannam@89: L. Peter Deutsch cannam@89: Aladdin Enterprises cannam@89: 203 Santa Margarita Ave. cannam@89: Menlo Park, CA 94025 cannam@89: cannam@89: Phone: (415) 322-0103 (AM only) cannam@89: FAX: (415) 322-1734 cannam@89: EMail: cannam@89: cannam@89: cannam@89: Jean-Loup Gailly cannam@89: cannam@89: EMail: cannam@89: cannam@89: Questions about the technical content of this specification can be cannam@89: sent by email to cannam@89: cannam@89: Jean-Loup Gailly and cannam@89: Mark Adler cannam@89: cannam@89: Editorial comments on this specification can be sent by email to cannam@89: cannam@89: L. Peter Deutsch and cannam@89: Glenn Randers-Pehrson cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 8] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 8. Appendix: Rationale cannam@89: cannam@89: 8.1. Preset dictionaries cannam@89: cannam@89: A preset dictionary is specially useful to compress short input cannam@89: sequences. The compressor can take advantage of the dictionary cannam@89: context to encode the input in a more compact manner. The cannam@89: decompressor can be initialized with the appropriate context by cannam@89: virtually decompressing a compressed version of the dictionary cannam@89: without producing any output. However for certain compression cannam@89: algorithms such as the deflate algorithm this operation can be cannam@89: achieved without actually performing any decompression. cannam@89: cannam@89: The compressor and the decompressor must use exactly the same cannam@89: dictionary. The dictionary may be fixed or may be chosen among a cannam@89: certain number of predefined dictionaries, according to the kind cannam@89: of input data. The decompressor can determine which dictionary has cannam@89: been chosen by the compressor by checking the dictionary cannam@89: identifier. This document does not specify the contents of cannam@89: predefined dictionaries, since the optimal dictionaries are cannam@89: application specific. Standard data formats using this feature of cannam@89: the zlib specification must precisely define the allowed cannam@89: dictionaries. cannam@89: cannam@89: 8.2. The Adler-32 algorithm cannam@89: cannam@89: The Adler-32 algorithm is much faster than the CRC32 algorithm yet cannam@89: still provides an extremely low probability of undetected errors. cannam@89: cannam@89: The modulo on unsigned long accumulators can be delayed for 5552 cannam@89: bytes, so the modulo operation time is negligible. If the bytes cannam@89: are a, b, c, the second sum is 3a + 2b + c + 3, and so is position cannam@89: and order sensitive, unlike the first sum, which is just a cannam@89: checksum. That 65521 is prime is important to avoid a possible cannam@89: large class of two-byte errors that leave the check unchanged. cannam@89: (The Fletcher checksum uses 255, which is not prime and which also cannam@89: makes the Fletcher check insensitive to single byte changes 0 <-> cannam@89: 255.) cannam@89: cannam@89: The sum s1 is initialized to 1 instead of zero to make the length cannam@89: of the sequence part of s2, so that the length does not have to be cannam@89: checked separately. (Any sequence of zeroes has a Fletcher cannam@89: checksum of zero.) cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 9] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: 9. Appendix: Sample code cannam@89: cannam@89: The following C code computes the Adler-32 checksum of a data buffer. cannam@89: It is written for clarity, not for speed. The sample code is in the cannam@89: ANSI C programming language. Non C users may find it easier to read cannam@89: with these hints: cannam@89: cannam@89: & Bitwise AND operator. cannam@89: >> Bitwise right shift operator. When applied to an cannam@89: unsigned quantity, as here, right shift inserts zero bit(s) cannam@89: at the left. cannam@89: << Bitwise left shift operator. Left shift inserts zero cannam@89: bit(s) at the right. cannam@89: ++ "n++" increments the variable n. cannam@89: % modulo operator: a % b is the remainder of a divided by b. cannam@89: cannam@89: #define BASE 65521 /* largest prime smaller than 65536 */ cannam@89: cannam@89: /* cannam@89: Update a running Adler-32 checksum with the bytes buf[0..len-1] cannam@89: and return the updated checksum. The Adler-32 checksum should be cannam@89: initialized to 1. cannam@89: cannam@89: Usage example: cannam@89: cannam@89: unsigned long adler = 1L; cannam@89: cannam@89: while (read_buffer(buffer, length) != EOF) { cannam@89: adler = update_adler32(adler, buffer, length); cannam@89: } cannam@89: if (adler != original_adler) error(); cannam@89: */ cannam@89: unsigned long update_adler32(unsigned long adler, cannam@89: unsigned char *buf, int len) cannam@89: { cannam@89: unsigned long s1 = adler & 0xffff; cannam@89: unsigned long s2 = (adler >> 16) & 0xffff; cannam@89: int n; cannam@89: cannam@89: for (n = 0; n < len; n++) { cannam@89: s1 = (s1 + buf[n]) % BASE; cannam@89: s2 = (s2 + s1) % BASE; cannam@89: } cannam@89: return (s2 << 16) + s1; cannam@89: } cannam@89: cannam@89: /* Return the adler32 of the bytes buf[0..len-1] */ cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 10] cannam@89: cannam@89: RFC 1950 ZLIB Compressed Data Format Specification May 1996 cannam@89: cannam@89: cannam@89: unsigned long adler32(unsigned char *buf, int len) cannam@89: { cannam@89: return update_adler32(1L, buf, len); cannam@89: } cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: cannam@89: Deutsch & Gailly Informational [Page 11] cannam@89: