revert between 56095 -> 55830 in arch
[AROS.git] / workbench / libs / z / doc / rfc1950.txt
blobce6428a0f2eed45691ce209b1daf36807c29b3e7
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
14          ZLIB Compressed Data Format Specification version 3.3
16 Status of This Memo
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.
22 IESG Note:
24    The IESG takes no position on the validity of any Intellectual
25    Property Rights statements contained in this document.
27 Notices
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
36    marked.
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>.
42 Abstract
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.
58 Deutsch & Gailly             Informational                      [Page 1]
60 RFC 1950       ZLIB Compressed Data Format Specification        May 1996
63 Table of Contents
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
84 1. Introduction
86    1.1. Purpose
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
98             Unix filters;
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
123       format.
125       The text of the specification assumes a basic background in
126       programming at the level of bits and other primitive data
127       representations.
129    1.3. Scope
131       The specification specifies a compressed data format that can be
132       used for in-memory compression of a sequence of arbitrary bytes.
134    1.4. Compliance
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.
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:
163          +---+
164          |   | <-- the vertical bars might be missing
165          +---+
170 Deutsch & Gailly             Informational                      [Page 3]
172 RFC 1950       ZLIB Compressed Data Format Specification        May 1996
175       represents one byte; a box like this:
177          +==============+
178          |              |
179          +==============+
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:
192          +--------+
193          |76543210|
194          +--------+
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:
201              0     1
202          +--------+--------+
203          |00000010|00001000|
204          +--------+--------+
205           ^        ^
206           |        |
207           |        + less significant byte = 8
208           + more significant byte = 2 x 256
210    2.2. Data format
212       A zlib stream has the following structure:
214            0   1
215          +---+---+
216          |CMF|FLG|   (more-->)
217          +---+---+
226 Deutsch & Gailly             Informational                      [Page 4]
228 RFC 1950       ZLIB Compressed Data Format Specification        May 1996
231       (if FLG.FDICT set)
233            0   1   2   3
234          +---+---+---+---+
235          |     DICTID    |   (more-->)
236          +---+---+---+---+
238          +=====================+---+---+---+---+
239          |...compressed data...|    ADLER32    |
240          +=====================+---+---+---+---+
242       Any data which may appear after ADLER32 are not part of the zlib
243       stream.
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
266          CM not equal to 8.
268       FLG (FLaGs)
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),
277          is a multiple of 31.
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
299          follows:
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.
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)
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
343    2.3. Compliance
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.
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.
369 3. References
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
399 4. Source code
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.
409 6. Acknowledgements
411    Trademarks cited in this document are the property of their
412    respective owners.
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
420    L. Peter Deutsch
421    Aladdin Enterprises
422    203 Santa Margarita Ave.
423    Menlo Park, CA 94025
425    Phone: (415) 322-0103 (AM only)
426    FAX:   (415) 322-1734
427    EMail: <ghost@aladdin.com>
430    Jean-Loup Gailly
432    EMail: <gzip@prep.ai.mit.edu>
434    Questions about the technical content of this specification can be
435    sent by email to
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
477       dictionaries.
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 <->
492       255.)
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.)
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
516    with these hints:
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.
527       #define BASE 65521 /* largest prime smaller than 65536 */
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.
534        Usage example:
536          unsigned long adler = 1L;
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;
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       }
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)
568       {
569         return update_adler32(1L, buf, len);
570       }
618 Deutsch & Gailly             Informational                     [Page 11]