home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 1900s / rfc1950.txt < prev    next >
Text File  |  1996-05-20  |  21KB  |  620 lines
  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.  
  620.