source: rtems/cpukit/zlib/doc/rfc1950.txt @ d101e748

4.104.114.84.95
Last change on this file since d101e748 was ad50f41b, checked in by Ralf Corsepius <ralf.corsepius@…>, on 05/21/96 at 20:18:57

Import from zlib-1.2.4

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