7
Network Working Group P. Deutsch
8
Request for Comments: 1950 Aladdin Enterprises
9
Category: Informational J-L. Gailly
14
ZLIB Compressed Data Format Specification version 3.3
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.
24
The IESG takes no position on the validity of any Intellectual
25
Property Rights statements contained in this document.
29
Copyright (c) 1996 L. Peter Deutsch and Jean-Loup Gailly
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
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>.
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
58
Deutsch & Gailly Informational [Page 1]
60
RFC 1950 ZLIB Compressed Data Format Specification May 1996
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
88
The purpose of this specification is to define a lossless
89
compressed data format that:
91
* Is independent of CPU type, operating system, file system,
92
and character set, and hence can be used for interchange;
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
100
* Can use a number of different compression methods;
102
* Can be implemented readily in a manner not covered by
103
patents, and hence can be practiced freely.
105
The data format defined by this specification does not attempt to
106
allow random access to compressed data.
114
Deutsch & Gailly Informational [Page 2]
116
RFC 1950 ZLIB Compressed Data Format Specification May 1996
119
1.2. Intended audience
121
This specification is intended for use by implementors of software
122
to compress data into zlib format and/or decompress data from zlib
125
The text of the specification assumes a basic background in
126
programming at the level of bits and other primitive data
131
The specification specifies a compressed data format that can be
132
used for in-memory compression of a sequence of arbitrary bytes.
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
142
1.5. Definitions of terms and conventions used
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.
149
1.6. Changes from previous versions
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.
157
2. Detailed specification
159
2.1. Overall conventions
161
In the diagrams below, a box like this:
164
| | <-- the vertical bars might be missing
170
Deutsch & Gailly Informational [Page 3]
172
RFC 1950 ZLIB Compressed Data Format Specification May 1996
175
represents one byte; a box like this:
181
represents a variable number of bytes.
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:
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:
207
| + less significant byte = 8
208
+ more significant byte = 2 x 256
212
A zlib stream has the following structure:
226
Deutsch & Gailly Informational [Page 4]
228
RFC 1950 ZLIB Compressed Data Format Specification May 1996
238
+=====================+---+---+---+---+
239
|...compressed data...| ADLER32 |
240
+=====================+---+---+---+---+
242
Any data which may appear after ADLER32 are not part of the zlib
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.
249
bits 0 to 3 CM Compression method
250
bits 4 to 7 CINFO Compression info
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.
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
269
This flag byte is divided as follows:
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)
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),
282
Deutsch & Gailly Informational [Page 5]
284
RFC 1950 ZLIB Compressed Data Format Specification May 1996
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.
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
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
306
The information in FLEVEL is not needed for decompression; it
307
is there to indicate if recompression might be worthwhile.
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)
315
Other compressed data formats are not specified in this version
316
of the zlib specification.
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)
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.
338
Deutsch & Gailly Informational [Page 6]
340
RFC 1950 ZLIB Compressed Data Format Specification May 1996
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
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.
371
[1] Deutsch, L.P.,"GZIP Compressed Data Format Specification",
372
available in ftp://ftp.uu.net/pub/archiving/zip/doc/
374
[2] Thomas Boutell, "PNG (Portable Network Graphics) specification",
375
available in ftp://ftp.uu.net/graphics/png/documents/
377
[3] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification",
378
available in ftp://ftp.uu.net/pub/archiving/zip/doc/
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.
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.
394
Deutsch & Gailly Informational [Page 7]
396
RFC 1950 ZLIB Compressed Data Format Specification May 1996
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/.
404
5. Security Considerations
406
A decoder that fails to check the ADLER32 checksum value may be
407
subject to undetected data corruption.
411
Trademarks cited in this document are the property of their
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.
418
7. Authors' Addresses
422
203 Santa Margarita Ave.
425
Phone: (415) 322-0103 (AM only)
427
EMail: <ghost@aladdin.com>
432
EMail: <gzip@prep.ai.mit.edu>
434
Questions about the technical content of this specification can be
437
Jean-Loup Gailly <gzip@prep.ai.mit.edu> and
438
Mark Adler <madler@alumni.caltech.edu>
440
Editorial comments on this specification can be sent by email to
442
L. Peter Deutsch <ghost@aladdin.com> and
443
Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
450
Deutsch & Gailly Informational [Page 8]
452
RFC 1950 ZLIB Compressed Data Format Specification May 1996
455
8. Appendix: Rationale
457
8.1. Preset dictionaries
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.
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
479
8.2. The Adler-32 algorithm
481
The Adler-32 algorithm is much faster than the CRC32 algorithm yet
482
still provides an extremely low probability of undetected errors.
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 <->
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
506
Deutsch & Gailly Informational [Page 9]
508
RFC 1950 ZLIB Compressed Data Format Specification May 1996
511
9. Appendix: Sample code
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
518
& Bitwise AND operator.
519
>> Bitwise right shift operator. When applied to an
520
unsigned quantity, as here, right shift inserts zero bit(s)
522
<< Bitwise left shift operator. Left shift inserts zero
524
++ "n++" increments the variable n.
525
% modulo operator: a % b is the remainder of a divided by b.
527
#define BASE 65521 /* largest prime smaller than 65536 */
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
536
unsigned long adler = 1L;
538
while (read_buffer(buffer, length) != EOF) {
539
adler = update_adler32(adler, buffer, length);
541
if (adler != original_adler) error();
543
unsigned long update_adler32(unsigned long adler,
544
unsigned char *buf, int len)
546
unsigned long s1 = adler & 0xffff;
547
unsigned long s2 = (adler >> 16) & 0xffff;
550
for (n = 0; n < len; n++) {
551
s1 = (s1 + buf[n]) % BASE;
552
s2 = (s2 + s1) % BASE;
554
return (s2 << 16) + s1;
557
/* Return the adler32 of the bytes buf[0..len-1] */
562
Deutsch & Gailly Informational [Page 10]
564
RFC 1950 ZLIB Compressed Data Format Specification May 1996
567
unsigned long adler32(unsigned char *buf, int len)
569
return update_adler32(1L, buf, len);
618
Deutsch & Gailly Informational [Page 11]
added
removed
zlib-1.2.6/doc/rfc1950.txt
