< draft-deutsch-zlib-spec-00.txt   draft-deutsch-zlib-spec-01.txt >
INTERNET-DRAFT L. Peter Deutsch INTERNET-DRAFT L. Peter Deutsch
ZLIB 3.3 Aladdin Enterprises ZLIB 3.3 Aladdin Enterprises
Expires: 06 Aug 1996 Jean-Loup Gailly Expires: 17 Aug 1996 Jean-Loup Gailly
Info-Zip Info-Zip
01 Feb 1996 12 Feb 1996
ZLIB Compressed Data Format Specification version 3.3 ZLIB Compressed Data Format Specification version 3.3
File draft-deutsch-zlib-spec-00.txt File draft-deutsch-zlib-spec-01.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
skipping to change at line 225 skipping to change at line 225
bit information field depending on the compression method. bit information field depending on the compression method.
bits 0 to 3 CM Compression method bits 0 to 3 CM Compression method
bits 4 to 7 CINFO Compression info bits 4 to 7 CINFO Compression info
CM (Compression method) CM (Compression method)
This identifies the compression method used in the file. CM = 8 This identifies the compression method used in the file. CM = 8
denotes the 'deflate' compression method with a window size up denotes the 'deflate' compression method with a window size up
to 32K. This is the method used by gzip and PNG (see to 32K. This is the method used by gzip and PNG (see
references [GZIP] and [PNG] in Chapter 3, below, for the references [1] and [2] in Chapter 3, below, for the reference
reference documents). CM = 15 is reserved. It might be used documents). CM = 15 is reserved. It might be used in a future
in a future version of this specification to indicate the version of this specification to indicate the presence of an
presence of an extra field before the compressed data. extra field before the compressed data.
CINFO (Compression info) CINFO (Compression info)
For CM = 8, CINFO is the base-2 logarithm of the LZ77 window For CM = 8, CINFO is the base-2 logarithm of the LZ77 window
size, minus eight (CINFO=7 indicates a 32K window size). Values size, minus eight (CINFO=7 indicates a 32K window size). Values
of CINFO above 7 are not allowed in this version of the of CINFO above 7 are not allowed in this version of the
specification. CINFO is not defined in this specification for specification. CINFO is not defined in this specification for
CM not equal to 8. CM not equal to 8.
FLG (FLaGs) FLG (FLaGs)
skipping to change at line 281 skipping to change at line 281
3 - compressor used maximum compression, slowest algorithm 3 - compressor used maximum compression, slowest algorithm
The information in FLEVEL is not needed for decompression; it The information in FLEVEL is not needed for decompression; it
is there to indicate if recompression might be worthwhile. is there to indicate if recompression might be worthwhile.
compressed data compressed data
For compression method 8, the compressed data is stored in the For compression method 8, the compressed data is stored in the
deflate compressed data format as described in the document deflate compressed data format as described in the document
"'Deflate' Compressed Data Format Specification" by L. Peter "'Deflate' Compressed Data Format Specification" by L. Peter
Deutsch. (See reference [DEFLATE] in Chapter 3, below) Deutsch. (See reference [3] in Chapter 3, below)
Other compressed data formats are not specified in this version Other compressed data formats are not specified in this version
of the zlib specification. of the zlib specification.
ADLER32 (Adler-32 checksum) ADLER32 (Adler-32 checksum)
This contains a checksum value of the uncompressed data This contains a checksum value of the uncompressed data
(excluding any dictionary data) computed according to Adler-32 (excluding any dictionary data) computed according to Adler-32
algorithm. This algorithm is a 32-bit extension and improvement algorithm. This algorithm is a 32-bit extension and improvement
of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073 of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073
standard. See references [FLETCHER] and [ITU-T] in Chapter 3, standard. See references [4] and [5] in Chapter 3, below)
below)
Adler-32 is composed of two sums accumulated per byte: s1 is 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 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 are done modulo 65521. s1 is initialized to 1, s2 to zero. The
Adler-32 checksum is stored as s2*65536 + s1 in most- Adler-32 checksum is stored as s2*65536 + s1 in most-
significant-byte first (network) order. significant-byte first (network) order.
2.3. Compliance 2.3. Compliance
A compliant compressor must produce streams with correct CMF, FLG A compliant compressor must produce streams with correct CMF, FLG
skipping to change at line 318 skipping to change at line 317
preset dictionary feature, the compressor must not set the FDICT preset dictionary feature, the compressor must not set the FDICT
flag. flag.
A compliant decompressor must check CMF, FLG, and ADLER32, and A compliant decompressor must check CMF, FLG, and ADLER32, and
provide an error indication if any of these have incorrect values. provide an error indication if any of these have incorrect values.
A compliant decompressor must give an error indication if CM is A compliant decompressor must give an error indication if CM is
not one of the values defined in this specification (only the not one of the values defined in this specification (only the
value 8 is permitted in this version), since another value could value 8 is permitted in this version), since another value could
indicate the presence of new features that would cause subsequent indicate the presence of new features that would cause subsequent
data to be interpreted incorrectly. A compliant decompressor must data to be interpreted incorrectly. A compliant decompressor must
give an error indication if FDICT is set and DICTID is not the
Deutsch and Gailly [Page 6] Deutsch and Gailly [Page 6]
give an error indication if FDICT is set and DICTID is not the
identifier of a known preset dictionary. A decompressor may identifier of a known preset dictionary. A decompressor may
ignore FLEVEL and still be compliant. When the zlib data format ignore FLEVEL and still be compliant. When the zlib data format
is being used as a part of another standard format, a compliant is being used as a part of another standard format, a compliant
decompressor must support all the preset dictionaries specified by decompressor must support all the preset dictionaries specified by
the other format. When the other format does not use the preset the other format. When the other format does not use the preset
dictionary feature, a compliant decompressor must reject any dictionary feature, a compliant decompressor must reject any
stream in which the FDICT flag is set. stream in which the FDICT flag is set.
3. References 3. References
[GZIP] Deutsch, L.P.,"'Gzip' Compressed Data Format Specification". [1] Deutsch, L.P.,"'Gzip' Compressed Data Format Specification".
available in ftp.uu.net:/pub/archiving/zip/doc/gzip-*.doc available in ftp.uu.net:/pub/archiving/zip/doc/gzip-*.doc
[DEFLATE] Deutsch, L.P.,"'Deflate' Compressed Data Format [2] Thomas Boutell, "PNG (Portable Network Graphics) specification".
Specification". available in available in ftp://ftp.uu.net/graphics/png/png*
ftp.uu.net:/pub/archiving/zip/doc/deflate-*.doc
[PNG] Thomas Boutell, "PNG (Portable Network Graphics) [3] Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
specification". available in ftp://ftp.uu.net/graphics/png/png* available in ftp.uu.net:/pub/archiving/zip/doc/deflate-*.doc
[FLETCHER] Fletcher, J. G., "An Arithmetic Checksum for Serial [4] Fletcher, J. G., "An Arithmetic Checksum for Serial
Transmissions," IEEE Transactions on Communications, Vol. COM-30, No. Transmissions," IEEE Transactions on Communications, Vol. COM-30, No.
1, January 1982, pp. 247-252. 1, January 1982, pp. 247-252.
[ITU-T] ITU-T Recommendation X.224, Annex D, "Checksum Algorithms," [5] ITU-T Recommendation X.224, Annex D, "Checksum Algorithms,"
November, 1993, pp. 144, 145. (Available from gopher://info.itu.ch). November, 1993, pp. 144, 145. (Available from gopher://info.itu.ch).
ITU-T X.244 is also the same as ISO 8073. ITU-T X.244 is also the same as ISO 8073.
4. Source code 4. Source code
Source code for a C language implementation of a 'zlib' compliant Source code for a C language implementation of a 'zlib' compliant
library is available at ftp.uu.net:/pub/archiving/zip/zlib/zlib*. library is available at ftp.uu.net:/pub/archiving/zip/zlib/zlib*.
5. Security considerations 5. Security considerations
skipping to change at line 372 skipping to change at line 370
respective owners. respective owners.
Jean-Loup Gailly and Mark Adler designed the zlib format and wrote Jean-Loup Gailly and Mark Adler designed the zlib format and wrote
the related software described in this specification. Glenn the related software described in this specification. Glenn
Randers-Pehrson converted this document to Internet Draft and HTML Randers-Pehrson converted this document to Internet Draft and HTML
format. format.
7. Authors' addresses L. Peter Deutsch 7. Authors' addresses L. Peter Deutsch
Aladdin Enterprises Aladdin Enterprises
Deutsch and Gailly [Page 7]
203 Santa Margarita Ave. 203 Santa Margarita Ave.
Menlo Park, CA 94025 Menlo Park, CA 94025
Deutsch and Gailly [Page 7]
Phone: (415) 322-0103 (AM only) Phone: (415) 322-0103 (AM only)
FAX: (415) 322-1734 FAX: (415) 322-1734
EMail: <ghost@aladdin.com> EMail: <ghost@aladdin.com>
Jean-loup Gailly Jean-loup Gailly
EMail: <gzip@prep.ai.mit.edu> EMail: <gzip@prep.ai.mit.edu>
Questions about the technical content of this specification can be Questions about the technical content of this specification can be
sent by email to sent by email to
Jean-loup Gailly <gzip@prep.ai.mit.edu> and Jean-loup Gailly <gzip@prep.ai.mit.edu> and
Mark Adler <madler@alumni.caltech.edu> Mark Adler <madler@alumni.caltech.edu>
Editorial comments on this specification can be sent by email to Editorial comments on this specification can be sent by email to
L. Peter Deutsch <ghost@aladdin.com> and L. Peter Deutsch <ghost@aladdin.com> and
Glenn Randers-Pehrson <glennrp@arl.mil> Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
8. Appendix: Rationale 8. Appendix: Rationale
8.1. Preset dictionaries 8.1. Preset dictionaries
A preset dictionary is specially useful to compress short input A preset dictionary is specially useful to compress short input
sequences. The compressor can take advantage of the dictionary sequences. The compressor can take advantage of the dictionary
context to encode the input in a more compact manner. The context to encode the input in a more compact manner. The
decompressor can be initialized with the appropriate context by decompressor can be initialized with the appropriate context by
virtually decompressing a compressed version of the dictionary virtually decompressing a compressed version of the dictionary
skipping to change at line 426 skipping to change at line 424
the zlib specification must precisely define the allowed the zlib specification must precisely define the allowed
dictionaries. dictionaries.
8.2. The Adler-32 algorithm 8.2. The Adler-32 algorithm
The Adler-32 algorithm is much faster than the CRC32 algorithm yet The Adler-32 algorithm is much faster than the CRC32 algorithm yet
still provides an extremely low probability of undetected errors. still provides an extremely low probability of undetected errors.
The modulo on unsigned long accumulators can be delayed for 5552 The modulo on unsigned long accumulators can be delayed for 5552
bytes, so the modulo operation time is negligible. If the bytes bytes, so the modulo operation time is negligible. If the bytes
Deutsch and Gailly [Page 8]
are a, b, c, the second sum is 3a + 2b + c + 3, and so is position 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 and order sensitive, unlike the first sum, which is just a
Deutsch and Gailly [Page 8]
checksum. That 65521 is prime is important to avoid a possible checksum. That 65521 is prime is important to avoid a possible
large class of two-byte errors that leave the check unchanged. large class of two-byte errors that leave the check unchanged.
(The Fletcher checksum uses 255, which is not prime and which also (The Fletcher checksum uses 255, which is not prime and which also
makes the Fletcher check insensitive to single byte changes 0 makes the Fletcher check insensitive to single byte changes 0
255.) 255.)
The sum s1 is initialized to 1 instead of zero to make the length 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 of the sequence part of s2, so that the length does not have to be
checked separately. (Any sequence of zeroes has a Fletcher checked separately. (Any sequence of zeroes has a Fletcher
checksum of zero.) checksum of zero.)
skipping to change at line 480 skipping to change at line 478
} }
if (adler != original_adler) error(); if (adler != original_adler) error();
*/ */
unsigned long update_adler32(unsigned long adler, unsigned long update_adler32(unsigned long adler,
unsigned char *buf, int len) unsigned char *buf, int len)
{ {
unsigned long s1 = adler & 0xffff; unsigned long s1 = adler & 0xffff;
unsigned long s2 = (adler >> 16) & 0xffff; unsigned long s2 = (adler >> 16) & 0xffff;
int n; int n;
Deutsch and Gailly [Page 9]
for (n = 0; n < len; n++) { for (n = 0; n < len; n++) {
s1 = (s1 + buf[n]) % BASE; s1 = (s1 + buf[n]) % BASE;
Deutsch and Gailly [Page 9]
s2 = (s2 + s1) % BASE; s2 = (s2 + s1) % BASE;
} }
return (s2 << 16) + s1; return (s2 << 16) + s1;
} }
/* Return the adler32 of the bytes buf[0..len-1] */ /* Return the adler32 of the bytes buf[0..len-1] */
unsigned long adler32(unsigned char *buf, int len) unsigned long adler32(unsigned char *buf, int len)
{ {
return update_adler32(1L, buf, len); return update_adler32(1L, buf, len);
 End of changes. 21 change blocks. 
26 lines changed or deleted 25 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/