b24e7fce |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | Network Working Group P. Deutsch |
8 | Request for Comments: 1950 Aladdin Enterprises |
9 | Category: Informational J-L. Gailly |
10 | Info-ZIP |
11 | May 1996 |
12 | |
13 | |
14 | ZLIB Compressed Data Format Specification version 3.3 |
15 | |
16 | Status 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 | |
22 | IESG Note: |
23 | |
24 | The IESG takes no position on the validity of any Intellectual |
25 | Property Rights statements contained in this document. |
26 | |
27 | Notices |
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 | |
42 | Abstract |
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 | |
58 | Deutsch & Gailly Informational [Page 1] |
59 | \f |
60 | RFC 1950 ZLIB Compressed Data Format Specification May 1996 |
61 | |
62 | |
63 | Table 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 | |
84 | 1. 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 | |
114 | Deutsch & Gailly Informational [Page 2] |
115 | \f |
116 | RFC 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 | |
157 | 2. 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 | |
170 | Deutsch & Gailly Informational [Page 3] |
171 | \f |
172 | RFC 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 | |
226 | Deutsch & Gailly Informational [Page 4] |
227 | \f |
228 | RFC 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 | |
282 | Deutsch & Gailly Informational [Page 5] |
283 | \f |
284 | RFC 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 | |
338 | Deutsch & Gailly Informational [Page 6] |
339 | \f |
340 | RFC 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 | |
369 | 3. 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 | |
394 | Deutsch & Gailly Informational [Page 7] |
395 | \f |
396 | RFC 1950 ZLIB Compressed Data Format Specification May 1996 |
397 | |
398 | |
399 | 4. 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 | |
404 | 5. Security Considerations |
405 | |
406 | A decoder that fails to check the ADLER32 checksum value may be |
407 | subject to undetected data corruption. |
408 | |
409 | 6. 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 | |
418 | 7. 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 | |
450 | Deutsch & Gailly Informational [Page 8] |
451 | \f |
452 | RFC 1950 ZLIB Compressed Data Format Specification May 1996 |
453 | |
454 | |
455 | 8. 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 | |
506 | Deutsch & Gailly Informational [Page 9] |
507 | \f |
508 | RFC 1950 ZLIB Compressed Data Format Specification May 1996 |
509 | |
510 | |
511 | 9. 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 | |
562 | Deutsch & Gailly Informational [Page 10] |
563 | \f |
564 | RFC 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 | |
618 | Deutsch & Gailly Informational [Page 11] |
619 | \f |