zlib-1.2.8/doc/rfc1950.txt



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]

Revision:	1096
Committed:	Sat Dec 30 14:40:33 2017 UTC (7 years, 10 months ago) by s10k
Content type:	text/plain
File size:	20502 byte(s)
Log Message:	Added zlib, quazip, basicxmlsyntaxhighlighter, conditionalsemaphore and linenumberdisplay libraries. zlib and quazip are pre-compiled, but you can compile them yourself, just delete the dll files (or equivalent binary files to your OS)
#	Content
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
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
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
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
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
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
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
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
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
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
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