]> git.jsancho.org Git - lugaru.git/blob - Dependencies/zlib/doc/rfc1950.txt
Maybe fix some MSVC build issues.
[lugaru.git] / Dependencies / zlib / doc / rfc1950.txt
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