620 lines
20 KiB
Plaintext
620 lines
20 KiB
Plaintext
|
||
|
||
|
||
|
||
|
||
|
||
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]
|
||
|