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