summaryrefslogtreecommitdiffstats
path: root/compat/zlib/doc/rfc1950.txt
diff options
context:
space:
mode:
Diffstat (limited to 'compat/zlib/doc/rfc1950.txt')
-rw-r--r--compat/zlib/doc/rfc1950.txt619
1 files changed, 0 insertions, 619 deletions
diff --git a/compat/zlib/doc/rfc1950.txt b/compat/zlib/doc/rfc1950.txt
deleted file mode 100644
index ce6428a..0000000
--- a/compat/zlib/doc/rfc1950.txt
+++ /dev/null
@@ -1,619 +0,0 @@
-
-
-
-
-
-
-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]
-