pure-zlib 0.6 → 0.6.1
raw patch · 21 files changed
+2825/−5 lines, 21 filesdep ~pure-zlibdep ~timebinary-addedPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: pure-zlib, time
API changes (from Hackage documentation)
Files
- pure-zlib.cabal +7/−5
- test/test-cases/randtest1.gold binary
- test/test-cases/randtest1.z binary
- test/test-cases/randtest2.gold binary
- test/test-cases/randtest2.z binary
- test/test-cases/randtest3.gold binary
- test/test-cases/randtest3.z binary
- test/test-cases/rfctest1.gold +808/−0
- test/test-cases/rfctest1.z binary
- test/test-cases/rfctest2.gold +1146/−0
- test/test-cases/rfctest2.z binary
- test/test-cases/rfctest3.gold +864/−0
- test/test-cases/rfctest3.z binary
- test/test-cases/tor-list.gold too large to diff
- test/test-cases/tor-list.z too large to diff
- test/test-cases/zerotest1.gold binary
- test/test-cases/zerotest1.z binary
- test/test-cases/zerotest2.gold binary
- test/test-cases/zerotest2.z binary
- test/test-cases/zerotest3.gold binary
- test/test-cases/zerotest3.z binary
pure-zlib.cabal view
@@ -1,5 +1,5 @@ name: pure-zlib-version: 0.6+version: 0.6.1 synopsis: A Haskell-only implementation of zlib / DEFLATE homepage: http://github.com/GaloisInc/pure-zlib license: BSD3@@ -12,6 +12,8 @@ description: A Haskell-only implementation of the zlib / DEFLATE protocol. Currently only implements the decompression algorithm.+extra-source-files: test/test-cases/*.z,+ test/test-cases/*.gold library default-language: Haskell2010@@ -47,7 +49,7 @@ base >= 4.6 && < 5.0, base-compat >= 0.9.1 && < 0.11, bytestring >= 0.10 && < 0.11,- pure-zlib >= 0.5 && < 0.8+ pure-zlib test-suite test-zlib type: exitcode-stdio-1.0@@ -63,7 +65,7 @@ filepath >= 1.4.1 && < 1.6, HUnit >= 1.2 && < 1.4, QuickCheck >= 2.7 && < 2.9,- pure-zlib >= 0.5 && < 0.8,+ pure-zlib, tasty >= 0.11.0.4 && < 0.13, tasty-hunit >= 0.9.2 && < 0.11, tasty-quickcheck >= 0.8.4 && < 0.11@@ -77,8 +79,8 @@ base >= 4.6 && < 5.0, base-compat >= 0.9.1 && < 0.11, bytestring >= 0.10 && < 0.11,- pure-zlib >= 0.5 && < 0.8,- time >= 1.4.2 && < 1.8+ pure-zlib,+ time >= 1.4.2 && < 1.9 source-repository head type: git
+ test/test-cases/randtest1.gold view
binary file changed (absent → 4096 bytes)
+ test/test-cases/randtest1.z view
binary file changed (absent → 4107 bytes)
+ test/test-cases/randtest2.gold view
binary file changed (absent → 8192 bytes)
+ test/test-cases/randtest2.z view
binary file changed (absent → 8203 bytes)
+ test/test-cases/randtest3.gold view
binary file changed (absent → 12288 bytes)
+ test/test-cases/randtest3.z view
binary file changed (absent → 12299 bytes)
+ test/test-cases/rfctest1.gold view
@@ -0,0 +1,808 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">+<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />+ <meta name="robots" content="index,follow" />+ <meta name="creator" content="rfcmarkup version 1.119" />+ <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />+<meta name="DC.Identifier" content="urn:ietf:rfc:1950" />+<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format. This+memo provides information for the Internet community. This memo does+not specify an Internet standard of any kind." />+<meta name="DC.Creator" content="Gailly, J-L." />+<meta name="DC.Creator" content="Deutsch, P." />+<meta name="DC.Date.Issued" content="May, 1996" />+<meta name="DC.Title" content="ZLIB Compressed Data Format Specification version 3.3" />++ <link rel="icon" href="/images/rfc.png" type="image/png" />+ <link rel="shortcut icon" href="/images/rfc.png" type="image/png" />+ <title>RFC 1950 - ZLIB Compressed Data Format Specification version 3.3</title>+ + + <style type="text/css">+ @media only screen + and (min-width: 992px)+ and (max-width: 1199px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 768px)+ and (max-width: 991px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 480px)+ and (max-width: 767px) {+ body { font-size: 11pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (max-width: 479px) {+ body { font-size: 8pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-device-width : 375px) + and (max-device-width : 667px) {+ body { font-size: 9.5pt; }+ div.content { width: 96ex; margin: 0 1px; }+ }+ @media only screen + and (min-device-width: 1200px) {+ body { font-size: 10pt; margin: 0 4em; }+ div.content { width: 96ex; margin: 0; }+ }+ h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {+ font-weight: bold;+ line-height: 0pt;+ display: inline;+ white-space: pre;+ font-family: monospace;+ font-size: 1em;+ font-weight: bold;+ }+ pre {+ font-size: 1em;+ margin-top: 0px;+ margin-bottom: 0px;+ }+ .pre {+ white-space: pre;+ font-family: monospace;+ }+ .header{+ font-weight: bold;+ }+ .newpage {+ page-break-before: always;+ }+ .invisible {+ text-decoration: none;+ color: white;+ }+ a.selflink {+ color: black;+ text-decoration: none;+ }+ @media print {+ body {+ font-family: monospace;+ font-size: 10.5pt;+ }+ h1, h2, h3, h4, h5, h6 {+ font-size: 1em;+ }+ + a:link, a:visited {+ color: inherit;+ text-decoration: none;+ }+ .noprint {+ display: none;+ }+ }+ @media screen {+ .grey, .grey a:link, .grey a:visited {+ color: #777;+ }+ .docinfo {+ background-color: #EEE;+ }+ .top {+ border-top: 7px solid #EEE;+ }+ .bgwhite { background-color: white; }+ .bgred { background-color: #F44; }+ .bggrey { background-color: #666; }+ .bgbrown { background-color: #840; } + .bgorange { background-color: #FA0; }+ .bgyellow { background-color: #EE0; }+ .bgmagenta{ background-color: #F4F; }+ .bgblue { background-color: #66F; }+ .bgcyan { background-color: #4DD; }+ .bggreen { background-color: #4F4; }++ .legend { font-size: 90%; }+ .cplate { font-size: 70%; border: solid grey 1px; }+ }+ </style>+ <!--[if IE]>+ <style>+ body {+ font-size: 13px;+ margin: 10px 10px;+ }+ </style>+ <![endif]-->++ <script type="text/javascript"><!--+ function addHeaderTags() {+ var spans = document.getElementsByTagName("span");+ for (var i=0; i < spans.length; i++) {+ var elem = spans[i];+ if (elem) {+ var level = elem.getAttribute("class");+ if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {+ elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">"; + }+ }+ }+ }+ var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";+ function showElem(id) {+ var elem = document.getElementById(id);+ elem.innerHTML = eval(id+"_html");+ elem.style.visibility='visible';+ }+ function hideElem(id) {+ var elem = document.getElementById(id);+ elem.style.visibility='hidden'; + elem.innerHTML = "";+ }+ // -->+ </script>+</head>+<body onload="addHeaderTags()">+ <div class="content">+ <div style="height: 13px;">+ <div onmouseover="this.style.cursor='pointer';"+ onclick="showElem('legend');"+ onmouseout="hideElem('legend')"+ style="height: 6px; position: absolute;"+ class="pre noprint docinfo bgorange"+ title="Click for colour legend." > </div>+ <div id="legend"+ class="docinfo noprint pre legend"+ style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "+ onmouseover="showElem('legend');"+ onmouseout="hideElem('legend');">+ </div>+ </div>+<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="/rfc/rfc1950.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/rfc1950" title="PDF version of this document">pdf</a>] [<a href="./draft-deutsch-zlib-spec" title="draft-deutsch-zlib-spec">draft-deutsch-zli...</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=rfc1950" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=rfc1950" title="Side-by-side diff">Diff2</a>] </span><br />+<span class="pre noprint docinfo"> </span><br />+<span class="pre noprint docinfo"> INFORMATIONAL</span><br />+<span class="pre noprint docinfo"> </span><br />+<pre>+Network Working Group P. Deutsch+Request for Comments: 1950 Aladdin Enterprises+Category: Informational J-L. Gailly+ Info-ZIP+ May 1996+++ <span class="h1">ZLIB Compressed Data Format Specification version 3.3</span>++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+ <<a href="ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html">ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html</a>>.++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.+++++<span class="grey">Deutsch & Gailly Informational [Page 1]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++Table of Contents++ <a href="#section-1">1</a>. Introduction ................................................... <a href="#page-2">2</a>+ <a href="#section-1.1">1.1</a>. Purpose ................................................... <a href="#page-2">2</a>+ <a href="#section-1.2">1.2</a>. Intended audience ......................................... <a href="#page-3">3</a>+ <a href="#section-1.3">1.3</a>. Scope ..................................................... <a href="#page-3">3</a>+ <a href="#section-1.4">1.4</a>. Compliance ................................................ <a href="#page-3">3</a>+ <a href="#section-1.5">1.5</a>. Definitions of terms and conventions used ................ <a href="#page-3">3</a>+ <a href="#section-1.6">1.6</a>. Changes from previous versions ............................ <a href="#page-3">3</a>+ <a href="#section-2">2</a>. Detailed specification ......................................... <a href="#page-3">3</a>+ <a href="#section-2.1">2.1</a>. Overall conventions ....................................... <a href="#page-3">3</a>+ <a href="#section-2.2">2.2</a>. Data format ............................................... <a href="#page-4">4</a>+ <a href="#section-2.3">2.3</a>. Compliance ................................................ <a href="#page-7">7</a>+ <a href="#section-3">3</a>. References ..................................................... <a href="#page-7">7</a>+ <a href="#section-4">4</a>. Source code .................................................... <a href="#page-8">8</a>+ <a href="#section-5">5</a>. Security Considerations ........................................ <a href="#page-8">8</a>+ <a href="#section-6">6</a>. Acknowledgements ............................................... <a href="#page-8">8</a>+ <a href="#section-7">7</a>. Authors' Addresses ............................................. <a href="#page-8">8</a>+ <a href="#section-8">8</a>. Appendix: Rationale ............................................ <a href="#page-9">9</a>+ <a href="#section-9">9</a>. Appendix: Sample code ..........................................<a href="#page-10">10</a>++<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>++ 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.++++++++<span class="grey">Deutsch & Gailly Informational [Page 2]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ 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.++<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Detailed specification</span>++ 2.1. Overall conventions++ In the diagrams below, a box like this:++ +---++ | | <-- the vertical bars might be missing+ +---++++++<span class="grey">Deutsch & Gailly Informational [Page 3]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ 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-->)+ +---+---++++++++++<span class="grey">Deutsch & Gailly Informational [Page 4]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ (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 [<a href="#ref-1" title=""GZIP Compressed Data Format Specification"">1</a>] and [<a href="#ref-2" title=""PNG (Portable Network Graphics) specification"">2</a>] 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.+++++<span class="grey">Deutsch & Gailly Informational [Page 5]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ 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 [<a href="#ref-3" title=""DEFLATE Compressed Data Format Specification"">3</a>] 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 [<a href="#ref-4" title=""An Arithmetic Checksum for Serial Transmissions,"">4</a>] and [<a href="#ref-5" title=""Checksum Algorithms,"">5</a>] 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.+++++++++<span class="grey">Deutsch & Gailly Informational [Page 6]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ 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.++<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. References</span>++ [<a name="ref-1" id="ref-1">1</a>] Deutsch, L.P.,"GZIP Compressed Data Format Specification",+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-2" id="ref-2">2</a>] Thomas Boutell, "PNG (Portable Network Graphics) specification",+ available in <a href="ftp://ftp.uu.net/graphics/png/documents/">ftp://ftp.uu.net/graphics/png/documents/</a>++ [<a name="ref-3" id="ref-3">3</a>] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification",+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-4" id="ref-4">4</a>] Fletcher, J. G., "An Arithmetic Checksum for Serial+ Transmissions," IEEE Transactions on Communications, Vol. COM-30,+ No. 1, January 1982, pp. 247-252.++ [<a name="ref-5" id="ref-5">5</a>] 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.++++++++<span class="grey">Deutsch & Gailly Informational [Page 7]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Source code</span>++ Source code for a C language implementation of a "zlib" compliant+ library is available at <a href="ftp://ftp.uu.net/pub/archiving/zip/zlib/">ftp://ftp.uu.net/pub/archiving/zip/zlib/</a>.++<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. Security Considerations</span>++ A decoder that fails to check the ADLER32 checksum value may be+ subject to undetected data corruption.++<span class="h2"><a class="selflink" name="section-6" href="#section-6">6</a>. Acknowledgements</span>++ 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.++<span class="h2"><a class="selflink" name="section-7" href="#section-7">7</a>. Authors' Addresses</span>++ 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>+++++++<span class="grey">Deutsch & Gailly Informational [Page 8]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-8" href="#section-8">8</a>. Appendix: Rationale</span>++ 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.)+++++++++<span class="grey">Deutsch & Gailly Informational [Page 9]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-9" href="#section-9">9</a>. Appendix: Sample code</span>++ 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] */+++++<span class="grey">Deutsch & Gailly Informational [Page 10]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ unsigned long adler32(unsigned char *buf, int len)+ {+ return update_adler32(1L, buf, len);+ }++++++++++++++++++++++++++++++++++++++++++++++++Deutsch & Gailly Informational [Page 11]++</pre><br />+ <span class="noprint"><small><small>Html markup produced by rfcmarkup 1.119, available from+ <a href="https://tools.ietf.org/tools/rfcmarkup/">https://tools.ietf.org/tools/rfcmarkup/</a>+ </small></small></span>+ </div>+</body>+</html>
+ test/test-cases/rfctest1.z view
binary file changed (absent → 9358 bytes)
+ test/test-cases/rfctest2.gold view
@@ -0,0 +1,1146 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">+<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />+ <meta name="robots" content="index,follow" />+ <meta name="creator" content="rfcmarkup version 1.119" />+ <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />+<meta name="DC.Identifier" content="urn:ietf:rfc:1951" />+<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format that+compresses data using a combination of the LZ77 algorithm and Huffman+coding, with efficiency comparable to the best currently available+general-purpose compression methods. This memo provides information+for the Internet community. This memo does not specify an Internet+standard of any kind." />+<meta name="DC.Creator" content="L. Peter Deutsch <ghost@aladdin.com>" />+<meta name="DC.Date.Issued" content="May, 1996" />+<meta name="DC.Title" content="DEFLATE Compressed Data Format Specification version 1.3" />++ <link rel="icon" href="/images/rfc.png" type="image/png" />+ <link rel="shortcut icon" href="/images/rfc.png" type="image/png" />+ <title>RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3</title>+ + + <style type="text/css">+ @media only screen + and (min-width: 992px)+ and (max-width: 1199px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 768px)+ and (max-width: 991px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 480px)+ and (max-width: 767px) {+ body { font-size: 11pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (max-width: 479px) {+ body { font-size: 8pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-device-width : 375px) + and (max-device-width : 667px) {+ body { font-size: 9.5pt; }+ div.content { width: 96ex; margin: 0 1px; }+ }+ @media only screen + and (min-device-width: 1200px) {+ body { font-size: 10pt; margin: 0 4em; }+ div.content { width: 96ex; margin: 0; }+ }+ h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {+ font-weight: bold;+ line-height: 0pt;+ display: inline;+ white-space: pre;+ font-family: monospace;+ font-size: 1em;+ font-weight: bold;+ }+ pre {+ font-size: 1em;+ margin-top: 0px;+ margin-bottom: 0px;+ }+ .pre {+ white-space: pre;+ font-family: monospace;+ }+ .header{+ font-weight: bold;+ }+ .newpage {+ page-break-before: always;+ }+ .invisible {+ text-decoration: none;+ color: white;+ }+ a.selflink {+ color: black;+ text-decoration: none;+ }+ @media print {+ body {+ font-family: monospace;+ font-size: 10.5pt;+ }+ h1, h2, h3, h4, h5, h6 {+ font-size: 1em;+ }+ + a:link, a:visited {+ color: inherit;+ text-decoration: none;+ }+ .noprint {+ display: none;+ }+ }+ @media screen {+ .grey, .grey a:link, .grey a:visited {+ color: #777;+ }+ .docinfo {+ background-color: #EEE;+ }+ .top {+ border-top: 7px solid #EEE;+ }+ .bgwhite { background-color: white; }+ .bgred { background-color: #F44; }+ .bggrey { background-color: #666; }+ .bgbrown { background-color: #840; } + .bgorange { background-color: #FA0; }+ .bgyellow { background-color: #EE0; }+ .bgmagenta{ background-color: #F4F; }+ .bgblue { background-color: #66F; }+ .bgcyan { background-color: #4DD; }+ .bggreen { background-color: #4F4; }++ .legend { font-size: 90%; }+ .cplate { font-size: 70%; border: solid grey 1px; }+ }+ </style>+ <!--[if IE]>+ <style>+ body {+ font-size: 13px;+ margin: 10px 10px;+ }+ </style>+ <![endif]-->++ <script type="text/javascript"><!--+ function addHeaderTags() {+ var spans = document.getElementsByTagName("span");+ for (var i=0; i < spans.length; i++) {+ var elem = spans[i];+ if (elem) {+ var level = elem.getAttribute("class");+ if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {+ elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">"; + }+ }+ }+ }+ var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";+ function showElem(id) {+ var elem = document.getElementById(id);+ elem.innerHTML = eval(id+"_html");+ elem.style.visibility='visible';+ }+ function hideElem(id) {+ var elem = document.getElementById(id);+ elem.style.visibility='hidden'; + elem.innerHTML = "";+ }+ // -->+ </script>+</head>+<body onload="addHeaderTags()">+ <div class="content">+ <div style="height: 13px;">+ <div onmouseover="this.style.cursor='pointer';"+ onclick="showElem('legend');"+ onmouseout="hideElem('legend')"+ style="height: 6px; position: absolute;"+ class="pre noprint docinfo bgorange"+ title="Click for colour legend." > </div>+ <div id="legend"+ class="docinfo noprint pre legend"+ style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "+ onmouseover="showElem('legend');"+ onmouseout="hideElem('legend');">+ </div>+ </div>+<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="/rfc/rfc1951.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/rfc1951" title="PDF version of this document">pdf</a>] [<a href="./draft-deutsch-deflate-spec" title="draft-deutsch-deflate-spec">draft-deutsch-def...</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=rfc1951" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=rfc1951" title="Side-by-side diff">Diff2</a>] </span><br />+<span class="pre noprint docinfo"> </span><br />+<span class="pre noprint docinfo"> INFORMATIONAL</span><br />+<span class="pre noprint docinfo"> </span><br />+<pre>+Network Working Group P. Deutsch+Request for Comments: 1951 Aladdin Enterprises+Category: Informational May 1996+++ <span class="h1">DEFLATE Compressed Data Format Specification version 1.3</span>++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++ 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+ <<a href="ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html">ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html</a>>.++Abstract++ This specification defines a lossless compressed data format that+ compresses data using a combination of the LZ77 algorithm and Huffman+ coding, with efficiency comparable to the best currently available+ general-purpose compression methods. 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 can be implemented readily in a manner not+ covered by patents.+++++++++<span class="grey">Deutsch Informational [Page 1]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++Table of Contents++ <a href="#section-1">1</a>. Introduction ................................................... <a href="#page-2">2</a>+ <a href="#section-1.1">1.1</a>. Purpose ................................................... <a href="#page-2">2</a>+ <a href="#section-1.2">1.2</a>. Intended audience ......................................... <a href="#page-3">3</a>+ <a href="#section-1.3">1.3</a>. Scope ..................................................... <a href="#page-3">3</a>+ <a href="#section-1.4">1.4</a>. Compliance ................................................ <a href="#page-3">3</a>+ <a href="#section-1.5">1.5</a>. Definitions of terms and conventions used ................ <a href="#page-3">3</a>+ <a href="#section-1.6">1.6</a>. Changes from previous versions ............................ <a href="#page-4">4</a>+ <a href="#section-2">2</a>. Compressed representation overview ............................. <a href="#page-4">4</a>+ <a href="#section-3">3</a>. Detailed specification ......................................... <a href="#page-5">5</a>+ <a href="#section-3.1">3.1</a>. Overall conventions ....................................... <a href="#page-5">5</a>+ <a href="#section-3.1.1">3.1.1</a>. Packing into bytes .................................. <a href="#page-5">5</a>+ <a href="#section-3.2">3.2</a>. Compressed block format ................................... <a href="#page-6">6</a>+ <a href="#section-3.2.1">3.2.1</a>. Synopsis of prefix and Huffman coding ............... <a href="#page-6">6</a>+ <a href="#section-3.2.2">3.2.2</a>. Use of Huffman coding in the "deflate" format ....... <a href="#page-7">7</a>+ <a href="#section-3.2.3">3.2.3</a>. Details of block format ............................. <a href="#page-9">9</a>+ <a href="#section-3.2.4">3.2.4</a>. Non-compressed blocks (BTYPE=00) ................... <a href="#page-11">11</a>+ <a href="#section-3.2.5">3.2.5</a>. Compressed blocks (length and distance codes) ...... <a href="#page-11">11</a>+ <a href="#section-3.2.6">3.2.6</a>. Compression with fixed Huffman codes (BTYPE=01) .... <a href="#page-12">12</a>+ <a href="#section-3.2.7">3.2.7</a>. Compression with dynamic Huffman codes (BTYPE=10) .. <a href="#page-13">13</a>+ <a href="#section-3.3">3.3</a>. Compliance ............................................... <a href="#page-14">14</a>+ <a href="#section-4">4</a>. Compression algorithm details ................................. <a href="#page-14">14</a>+ <a href="#section-5">5</a>. References .................................................... <a href="#page-16">16</a>+ <a href="#section-6">6</a>. Security Considerations ....................................... <a href="#page-16">16</a>+ <a href="#section-7">7</a>. Source code ................................................... <a href="#page-16">16</a>+ <a href="#section-8">8</a>. Acknowledgements .............................................. <a href="#page-16">16</a>+ <a href="#section-9">9</a>. Author's Address .............................................. <a href="#page-17">17</a>++<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>++ 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;+ * Compresses data with efficiency comparable to the best+ currently available general-purpose compression methods,+ and in particular considerably better than the "compress"+ program;+ * Can be implemented readily in a manner not covered by+ patents, and hence can be practiced freely;++++<span class="grey">Deutsch Informational [Page 2]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ * Is compatible with the file format produced by the current+ widely used gzip utility, in that conforming decompressors+ will be able to read data produced by the existing gzip+ compressor.++ The data format defined by this specification does not attempt to:++ * Allow random access to compressed data;+ * Compress specialized data (e.g., raster graphics) as well+ as the best currently available specialized algorithms.++ A simple counting argument shows that no lossless compression+ algorithm can compress every possible input data set. For the+ format defined here, the worst case expansion is 5 bytes per 32K-+ byte block, i.e., a size increase of 0.015% for large data sets.+ English text usually compresses by a factor of 2.5 to 3;+ executable files usually compress somewhat less; graphical data+ such as raster images may compress much more.++ 1.2. Intended audience++ This specification is intended for use by implementors of software+ to compress data into "deflate" format and/or decompress data from+ "deflate" format.++ The text of the specification assumes a basic background in+ programming at the level of bits and other primitive data+ representations. Familiarity with the technique of Huffman coding+ is helpful but not required.++ 1.3. Scope++ The specification specifies a method for representing a sequence+ of bytes as a (usually shorter) sequence of bits, and a method for+ packing the latter bit sequence into 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++++<span class="grey">Deutsch Informational [Page 3]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ which store a character on a number of bits different from eight.+ See below, for the numbering of bits within a byte.++ String: a sequence of arbitrary bytes.++ 1.6. Changes from previous versions++ There have been no technical changes to the deflate format since+ version 1.1 of this specification. In version 1.2, some+ terminology was changed. Version 1.3 is a conversion of the+ specification to RFC style.++<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Compressed representation overview</span>++ A compressed data set consists of a series of blocks, corresponding+ to successive blocks of input data. The block sizes are arbitrary,+ except that non-compressible blocks are limited to 65,535 bytes.++ Each block is compressed using a combination of the LZ77 algorithm+ and Huffman coding. The Huffman trees for each block are independent+ of those for previous or subsequent blocks; the LZ77 algorithm may+ use a reference to a duplicated string occurring in a previous block,+ up to 32K input bytes before.++ Each block consists of two parts: a pair of Huffman code trees that+ describe the representation of the compressed data part, and a+ compressed data part. (The Huffman trees themselves are compressed+ using Huffman encoding.) The compressed data consists of a series of+ elements of two types: literal bytes (of strings that have not been+ detected as duplicated within the previous 32K input bytes), and+ pointers to duplicated strings, where a pointer is represented as a+ pair <length, backward distance>. The representation used in the+ "deflate" format limits distances to 32K bytes and lengths to 258+ bytes, but does not limit the size of a block, except for+ uncompressible blocks, which are limited as noted above.++ Each type of value (literals, distances, and lengths) in the+ compressed data is represented using a Huffman code, using one code+ tree for literals and lengths and a separate code tree for distances.+ The code trees for each block appear in a compact form just before+ the compressed data for that block.+++++++++++<span class="grey">Deutsch Informational [Page 4]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. Detailed specification</span>++ 3.1. Overall conventions In the diagrams below, a box like this:++ +---++ | | <-- the vertical bars might be missing+ +---+++ 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 least-significant byte first (at the lower memory address).+ For example, the decimal number 520 is stored as:++ 0 1+ +--------+--------++ |00001000|00000010|+ +--------+--------++ ^ ^+ | |+ | + more significant byte = 2 x 256+ + less significant byte = 8++ 3.1.1. Packing into bytes++ This document does not address the issue of the order in which+ bits of a byte are transmitted on a bit-sequential medium,+ since the final data format described here is byte- rather than++++<span class="grey">Deutsch Informational [Page 5]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ bit-oriented. However, we describe the compressed block format+ in below, as a sequence of data elements of various bit+ lengths, not a sequence of bytes. We must therefore specify+ how to pack these data elements into bytes to form the final+ compressed byte sequence:++ * Data elements are packed into bytes in order of+ increasing bit number within the byte, i.e., starting+ with the least-significant bit of the byte.+ * Data elements other than Huffman codes are packed+ starting with the least-significant bit of the data+ element.+ * Huffman codes are packed starting with the most-+ significant bit of the code.++ In other words, if one were to print out the compressed data as+ a sequence of bytes, starting with the first byte at the+ *right* margin and proceeding to the *left*, with the most-+ significant bit of each byte on the left as usual, one would be+ able to parse the result from right to left, with fixed-width+ elements in the correct MSB-to-LSB order and Huffman codes in+ bit-reversed order (i.e., with the first bit of the code in the+ relative LSB position).++ 3.2. Compressed block format++ 3.2.1. Synopsis of prefix and Huffman coding++ Prefix coding represents symbols from an a priori known+ alphabet by bit sequences (codes), one code for each symbol, in+ a manner such that different symbols may be represented by bit+ sequences of different lengths, but a parser can always parse+ an encoded string unambiguously symbol-by-symbol.++ We define a prefix code in terms of a binary tree in which the+ two edges descending from each non-leaf node are labeled 0 and+ 1 and in which the leaf nodes correspond one-for-one with (are+ labeled with) the symbols of the alphabet; then the code for a+ symbol is the sequence of 0's and 1's on the edges leading from+ the root to the leaf labeled with that symbol. For example:++++++++++++<span class="grey">Deutsch Informational [Page 6]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ /\ Symbol Code+ 0 1 ------ ----+ / \ A 00+ /\ B B 1+ 0 1 C 011+ / \ D 010+ A /\+ 0 1+ / \+ D C++ A parser can decode the next symbol from an encoded input+ stream by walking down the tree from the root, at each step+ choosing the edge corresponding to the next input bit.++ Given an alphabet with known symbol frequencies, the Huffman+ algorithm allows the construction of an optimal prefix code+ (one which represents strings with those symbol frequencies+ using the fewest bits of any possible prefix codes for that+ alphabet). Such a code is called a Huffman code. (See+ reference [<a href="#ref-1" title=""A Method for the Construction of Minimum Redundancy Codes"">1</a>] in Chapter 5, references for additional+ information on Huffman codes.)++ Note that in the "deflate" format, the Huffman codes for the+ various alphabets must not exceed certain maximum code lengths.+ This constraint complicates the algorithm for computing code+ lengths from symbol frequencies. Again, see Chapter 5,+ references for details.++ 3.2.2. Use of Huffman coding in the "deflate" format++ The Huffman codes used for each alphabet in the "deflate"+ format have two additional rules:++ * All codes of a given bit length have lexicographically+ consecutive values, in the same order as the symbols+ they represent;++ * Shorter codes lexicographically precede longer codes.+++++++++++++<span class="grey">Deutsch Informational [Page 7]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ We could recode the example above to follow this rule as+ follows, assuming that the order of the alphabet is ABCD:++ Symbol Code+ ------ ----+ A 10+ B 0+ C 110+ D 111++ I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are+ lexicographically consecutive.++ Given this rule, we can define the Huffman code for an alphabet+ just by giving the bit lengths of the codes for each symbol of+ the alphabet in order; this is sufficient to determine the+ actual codes. In our example, the code is completely defined+ by the sequence of bit lengths (2, 1, 3, 3). The following+ algorithm generates the codes as integers, intended to be read+ from most- to least-significant bit. The code lengths are+ initially in tree[I].Len; the codes are produced in+ tree[I].Code.++ 1) Count the number of codes for each code length. Let+ bl_count[N] be the number of codes of length N, N >= 1.++ 2) Find the numerical value of the smallest code for each+ code length:++ code = 0;+ bl_count[0] = 0;+ for (bits = 1; bits <= MAX_BITS; bits++) {+ code = (code + bl_count[bits-1]) << 1;+ next_code[bits] = code;+ }++ 3) Assign numerical values to all codes, using consecutive+ values for all codes of the same length with the base+ values determined at step 2. Codes that are never used+ (which have a bit length of zero) must not be assigned a+ value.++ for (n = 0; n <= max_code; n++) {+ len = tree[n].Len;+ if (len != 0) {+ tree[n].Code = next_code[len];+ next_code[len]++;+ }++++<span class="grey">Deutsch Informational [Page 8]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ }++ Example:++ Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3,+ 3, 2, 4, 4). After step 1, we have:++ N bl_count[N]+ - -----------+ 2 1+ 3 5+ 4 2++ Step 2 computes the following next_code values:++ N next_code[N]+ - ------------+ 1 0+ 2 0+ 3 2+ 4 14++ Step 3 produces the following code values:++ Symbol Length Code+ ------ ------ ----+ A 3 010+ B 3 011+ C 3 100+ D 3 101+ E 3 110+ F 2 00+ G 4 1110+ H 4 1111++ 3.2.3. Details of block format++ Each block of compressed data begins with 3 header bits+ containing the following data:++ first bit BFINAL+ next 2 bits BTYPE++ Note that the header bits do not necessarily begin on a byte+ boundary, since a block does not necessarily occupy an integral+ number of bytes.++++++<span class="grey">Deutsch Informational [Page 9]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ BFINAL is set if and only if this is the last block of the data+ set.++ BTYPE specifies how the data are compressed, as follows:++ 00 - no compression+ 01 - compressed with fixed Huffman codes+ 10 - compressed with dynamic Huffman codes+ 11 - reserved (error)++ The only difference between the two compressed cases is how the+ Huffman codes for the literal/length and distance alphabets are+ defined.++ In all cases, the decoding algorithm for the actual data is as+ follows:++ do+ read block header from input stream.+ if stored with no compression+ skip any remaining bits in current partially+ processed byte+ read LEN and NLEN (see next section)+ copy LEN bytes of data to output+ otherwise+ if compressed with dynamic Huffman codes+ read representation of code trees (see+ subsection below)+ loop (until end of block code recognized)+ decode literal/length value from input stream+ if value < 256+ copy value (literal byte) to output stream+ otherwise+ if value = end of block (256)+ break from loop+ otherwise (value = 257..285)+ decode distance from input stream++ move backwards distance bytes in the output+ stream, and copy length bytes from this+ position to the output stream.+ end loop+ while not last block++ Note that a duplicated string reference may refer to a string+ in a previous block; i.e., the backward distance may cross one+ or more block boundaries. However a distance cannot refer past+ the beginning of the output stream. (An application using a++++<span class="grey">Deutsch Informational [Page 10]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ preset dictionary might discard part of the output stream; a+ distance can refer to that part of the output stream anyway)+ Note also that the referenced string may overlap the current+ position; for example, if the last 2 bytes decoded have values+ X and Y, a string reference with <length = 5, distance = 2>+ adds X,Y,X,Y,X to the output stream.++ We now specify each compression method in turn.++ 3.2.4. Non-compressed blocks (BTYPE=00)++ Any bits of input up to the next byte boundary are ignored.+ The rest of the block consists of the following information:++ 0 1 2 3 4...+ +---+---+---+---+================================++ | LEN | NLEN |... LEN bytes of literal data...|+ +---+---+---+---+================================+++ LEN is the number of data bytes in the block. NLEN is the+ one's complement of LEN.++ 3.2.5. Compressed blocks (length and distance codes)++ As noted above, encoded data blocks in the "deflate" format+ consist of sequences of symbols drawn from three conceptually+ distinct alphabets: either literal bytes, from the alphabet of+ byte values (0..255), or <length, backward distance> pairs,+ where the length is drawn from (3..258) and the distance is+ drawn from (1..32,768). In fact, the literal and length+ alphabets are merged into a single alphabet (0..285), where+ values 0..255 represent literal bytes, the value 256 indicates+ end-of-block, and values 257..285 represent length codes+ (possibly in conjunction with extra bits following the symbol+ code) as follows:+++++++++++++++++<span class="grey">Deutsch Informational [Page 11]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-12" id="page-12" href="#page-12" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ Extra Extra Extra+ Code Bits Length(s) Code Bits Lengths Code Bits Length(s)+ ---- ---- ------ ---- ---- ------- ---- ---- -------+ 257 0 3 267 1 15,16 277 4 67-82+ 258 0 4 268 1 17,18 278 4 83-98+ 259 0 5 269 2 19-22 279 4 99-114+ 260 0 6 270 2 23-26 280 4 115-130+ 261 0 7 271 2 27-30 281 5 131-162+ 262 0 8 272 2 31-34 282 5 163-194+ 263 0 9 273 3 35-42 283 5 195-226+ 264 0 10 274 3 43-50 284 5 227-257+ 265 1 11,12 275 3 51-58 285 0 258+ 266 1 13,14 276 3 59-66++ The extra bits should be interpreted as a machine integer+ stored with the most-significant bit first, e.g., bits 1110+ represent the value 14.++ Extra Extra Extra+ Code Bits Dist Code Bits Dist Code Bits Distance+ ---- ---- ---- ---- ---- ------ ---- ---- --------+ 0 0 1 10 4 33-48 20 9 1025-1536+ 1 0 2 11 4 49-64 21 9 1537-2048+ 2 0 3 12 5 65-96 22 10 2049-3072+ 3 0 4 13 5 97-128 23 10 3073-4096+ 4 1 5,6 14 6 129-192 24 11 4097-6144+ 5 1 7,8 15 6 193-256 25 11 6145-8192+ 6 2 9-12 16 7 257-384 26 12 8193-12288+ 7 2 13-16 17 7 385-512 27 12 12289-16384+ 8 3 17-24 18 8 513-768 28 13 16385-24576+ 9 3 25-32 19 8 769-1024 29 13 24577-32768++ 3.2.6. Compression with fixed Huffman codes (BTYPE=01)++ The Huffman codes for the two alphabets are fixed, and are not+ represented explicitly in the data. The Huffman code lengths+ for the literal/length alphabet are:++ Lit Value Bits Codes+ --------- ---- -----+ 0 - 143 8 00110000 through+ 10111111+ 144 - 255 9 110010000 through+ 111111111+ 256 - 279 7 0000000 through+ 0010111+ 280 - 287 8 11000000 through+ 11000111++++<span class="grey">Deutsch Informational [Page 12]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-13" id="page-13" href="#page-13" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ The code lengths are sufficient to generate the actual codes,+ as described above; we show the codes in the table for added+ clarity. Literal/length values 286-287 will never actually+ occur in the compressed data, but participate in the code+ construction.++ Distance codes 0-31 are represented by (fixed-length) 5-bit+ codes, with possible additional bits as shown in the table+ shown in Paragraph 3.2.5, above. Note that distance codes 30-+ 31 will never actually occur in the compressed data.++ 3.2.7. Compression with dynamic Huffman codes (BTYPE=10)++ The Huffman codes for the two alphabets appear in the block+ immediately after the header bits and before the actual+ compressed data, first the literal/length code and then the+ distance code. Each code is defined by a sequence of code+ lengths, as discussed in Paragraph 3.2.2, above. For even+ greater compactness, the code length sequences themselves are+ compressed using a Huffman code. The alphabet for code lengths+ is as follows:++ 0 - 15: Represent code lengths of 0 - 15+ 16: Copy the previous code length 3 - 6 times.+ The next 2 bits indicate repeat length+ (0 = 3, ... , 3 = 6)+ Example: Codes 8, 16 (+2 bits 11),+ 16 (+2 bits 10) will expand to+ 12 code lengths of 8 (1 + 6 + 5)+ 17: Repeat a code length of 0 for 3 - 10 times.+ (3 bits of length)+ 18: Repeat a code length of 0 for 11 - 138 times+ (7 bits of length)++ A code length of 0 indicates that the corresponding symbol in+ the literal/length or distance alphabet will not occur in the+ block, and should not participate in the Huffman code+ construction algorithm given earlier. If only one distance+ code is used, it is encoded using one bit, not zero bits; in+ this case there is a single code length of one, with one unused+ code. One distance code of zero bits means that there are no+ distance codes used at all (the data is all literals).++ We can now define the format of the block:++ 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)+ 5 Bits: HDIST, # of Distance codes - 1 (1 - 32)+ 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)++++<span class="grey">Deutsch Informational [Page 13]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-14" id="page-14" href="#page-14" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ (HCLEN + 4) x 3 bits: code lengths for the code length+ alphabet given just above, in the order: 16, 17, 18,+ 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15++ These code lengths are interpreted as 3-bit integers+ (0-7); as above, a code length of 0 means the+ corresponding symbol (literal/length or distance code+ length) is not used.++ HLIT + 257 code lengths for the literal/length alphabet,+ encoded using the code length Huffman code++ HDIST + 1 code lengths for the distance alphabet,+ encoded using the code length Huffman code++ The actual compressed data of the block,+ encoded using the literal/length and distance Huffman+ codes++ The literal/length symbol 256 (end of data),+ encoded using the literal/length Huffman code++ The code length repeat codes can cross from HLIT + 257 to the+ HDIST + 1 code lengths. In other words, all code lengths form+ a single sequence of HLIT + HDIST + 258 values.++ 3.3. Compliance++ A compressor may limit further the ranges of values specified in+ the previous section and still be compliant; for example, it may+ limit the range of backward pointers to some value smaller than+ 32K. Similarly, a compressor may limit the size of blocks so that+ a compressible block fits in memory.++ A compliant decompressor must accept the full range of possible+ values defined in the previous section, and must accept blocks of+ arbitrary size.++<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Compression algorithm details</span>++ While it is the intent of this document to define the "deflate"+ compressed data format without reference to any particular+ compression algorithm, the format is related to the compressed+ formats produced by LZ77 (Lempel-Ziv 1977, see reference [<a href="#ref-2" title=""A Universal Algorithm for Sequential Data Compression"">2</a>] below);+ since many variations of LZ77 are patented, it is strongly+ recommended that the implementor of a compressor follow the general+ algorithm presented here, which is known not to be patented per se.+ The material in this section is not part of the definition of the++++<span class="grey">Deutsch Informational [Page 14]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-15" id="page-15" href="#page-15" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ specification per se, and a compressor need not follow it in order to+ be compliant.++ The compressor terminates a block when it determines that starting a+ new block with fresh trees would be useful, or when the block size+ fills up the compressor's block buffer.++ The compressor uses a chained hash table to find duplicated strings,+ using a hash function that operates on 3-byte sequences. At any+ given point during compression, let XYZ be the next 3 input bytes to+ be examined (not necessarily all different, of course). First, the+ compressor examines the hash chain for XYZ. If the chain is empty,+ the compressor simply writes out X as a literal byte and advances one+ byte in the input. If the hash chain is not empty, indicating that+ the sequence XYZ (or, if we are unlucky, some other 3 bytes with the+ same hash function value) has occurred recently, the compressor+ compares all strings on the XYZ hash chain with the actual input data+ sequence starting at the current point, and selects the longest+ match.++ The compressor searches the hash chains starting with the most recent+ strings, to favor small distances and thus take advantage of the+ Huffman encoding. The hash chains are singly linked. There are no+ deletions from the hash chains; the algorithm simply discards matches+ that are too old. To avoid a worst-case situation, very long hash+ chains are arbitrarily truncated at a certain length, determined by a+ run-time parameter.++ To improve overall compression, the compressor optionally defers the+ selection of matches ("lazy matching"): after a match of length N has+ been found, the compressor searches for a longer match starting at+ the next input byte. If it finds a longer match, it truncates the+ previous match to a length of one (thus producing a single literal+ byte) and then emits the longer match. Otherwise, it emits the+ original match, and, as described above, advances N bytes before+ continuing.++ Run-time parameters also control this "lazy match" procedure. If+ compression ratio is most important, the compressor attempts a+ complete second search regardless of the length of the first match.+ In the normal case, if the current match is "long enough", the+ compressor reduces the search for a longer match, thus speeding up+ the process. If speed is most important, the compressor inserts new+ strings in the hash table only when no match was found, or when the+ match is not "too long". This degrades the compression ratio but+ saves time since there are both fewer insertions and fewer searches.++++++<span class="grey">Deutsch Informational [Page 15]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-16" id="page-16" href="#page-16" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. References</span>++ [<a name="ref-1" id="ref-1">1</a>] Huffman, D. A., "A Method for the Construction of Minimum+ Redundancy Codes", Proceedings of the Institute of Radio+ Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.++ [<a name="ref-2" id="ref-2">2</a>] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data+ Compression", IEEE Transactions on Information Theory, Vol. 23,+ No. 3, pp. 337-343.++ [<a name="ref-3" id="ref-3">3</a>] Gailly, J.-L., and Adler, M., ZLIB documentation and sources,+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-4" id="ref-4">4</a>] Gailly, J.-L., and Adler, M., GZIP documentation and sources,+ available as gzip-*.tar in <a href="ftp://prep.ai.mit.edu/pub/gnu/">ftp://prep.ai.mit.edu/pub/gnu/</a>++ [<a name="ref-5" id="ref-5">5</a>] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix+ encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169.++ [<a name="ref-6" id="ref-6">6</a>] Hirschberg and Lelewer, "Efficient decoding of prefix codes,"+ Comm. ACM, 33,4, April 1990, pp. 449-459.++<span class="h2"><a class="selflink" name="section-6" href="#section-6">6</a>. Security Considerations</span>++ Any data compression method involves the reduction of redundancy in+ the data. Consequently, any corruption of the data is likely to have+ severe effects and be difficult to correct. Uncompressed text, on+ the other hand, will probably still be readable despite the presence+ of some corrupted bytes.++ It is recommended that systems using this data format provide some+ means of validating the integrity of the compressed data. See+ reference [<a href="#ref-3" title="ZLIB documentation and sources">3</a>], for example.++<span class="h2"><a class="selflink" name="section-7" href="#section-7">7</a>. Source code</span>++ Source code for a C language implementation of a "deflate" compliant+ compressor and decompressor is available within the zlib package at+ <a href="ftp://ftp.uu.net/pub/archiving/zip/zlib/">ftp://ftp.uu.net/pub/archiving/zip/zlib/</a>.++<span class="h2"><a class="selflink" name="section-8" href="#section-8">8</a>. Acknowledgements</span>++ Trademarks cited in this document are the property of their+ respective owners.++ Phil Katz designed the deflate format. Jean-Loup Gailly and Mark+ Adler wrote the related software described in this specification.+ Glenn Randers-Pehrson converted this document to RFC and HTML format.++++<span class="grey">Deutsch Informational [Page 16]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-17" id="page-17" href="#page-17" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-9" href="#section-9">9</a>. Author's Address</span>++ 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>++ 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 Informational [Page 17]++</pre><br />+ <span class="noprint"><small><small>Html markup produced by rfcmarkup 1.119, available from+ <a href="https://tools.ietf.org/tools/rfcmarkup/">https://tools.ietf.org/tools/rfcmarkup/</a>+ </small></small></span>+ </div>+</body>+</html>
+ test/test-cases/rfctest2.z view
binary file changed (absent → 14275 bytes)
+ test/test-cases/rfctest3.gold view
@@ -0,0 +1,864 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">+<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />+ <meta name="robots" content="index,follow" />+ <meta name="creator" content="rfcmarkup version 1.119" />+ <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />+<meta name="DC.Identifier" content="urn:ietf:rfc:1952" />+<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format that is+compatible with the widely used GZIP utility. This memo provides+information for the Internet community. This memo does not specify an+Internet standard of any kind." />+<meta name="DC.Creator" content="L. Peter Deutsch <ghost@aladdin.com>" />+<meta name="DC.Date.Issued" content="May, 1996" />+<meta name="DC.Title" content="GZIP file format specification version 4.3" />++ <link rel="icon" href="/images/rfc.png" type="image/png" />+ <link rel="shortcut icon" href="/images/rfc.png" type="image/png" />+ <title>RFC 1952 - GZIP file format specification version 4.3</title>+ + + <style type="text/css">+ @media only screen + and (min-width: 992px)+ and (max-width: 1199px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 768px)+ and (max-width: 991px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 480px)+ and (max-width: 767px) {+ body { font-size: 11pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (max-width: 479px) {+ body { font-size: 8pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-device-width : 375px) + and (max-device-width : 667px) {+ body { font-size: 9.5pt; }+ div.content { width: 96ex; margin: 0 1px; }+ }+ @media only screen + and (min-device-width: 1200px) {+ body { font-size: 10pt; margin: 0 4em; }+ div.content { width: 96ex; margin: 0; }+ }+ h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {+ font-weight: bold;+ line-height: 0pt;+ display: inline;+ white-space: pre;+ font-family: monospace;+ font-size: 1em;+ font-weight: bold;+ }+ pre {+ font-size: 1em;+ margin-top: 0px;+ margin-bottom: 0px;+ }+ .pre {+ white-space: pre;+ font-family: monospace;+ }+ .header{+ font-weight: bold;+ }+ .newpage {+ page-break-before: always;+ }+ .invisible {+ text-decoration: none;+ color: white;+ }+ a.selflink {+ color: black;+ text-decoration: none;+ }+ @media print {+ body {+ font-family: monospace;+ font-size: 10.5pt;+ }+ h1, h2, h3, h4, h5, h6 {+ font-size: 1em;+ }+ + a:link, a:visited {+ color: inherit;+ text-decoration: none;+ }+ .noprint {+ display: none;+ }+ }+ @media screen {+ .grey, .grey a:link, .grey a:visited {+ color: #777;+ }+ .docinfo {+ background-color: #EEE;+ }+ .top {+ border-top: 7px solid #EEE;+ }+ .bgwhite { background-color: white; }+ .bgred { background-color: #F44; }+ .bggrey { background-color: #666; }+ .bgbrown { background-color: #840; } + .bgorange { background-color: #FA0; }+ .bgyellow { background-color: #EE0; }+ .bgmagenta{ background-color: #F4F; }+ .bgblue { background-color: #66F; }+ .bgcyan { background-color: #4DD; }+ .bggreen { background-color: #4F4; }++ .legend { font-size: 90%; }+ .cplate { font-size: 70%; border: solid grey 1px; }+ }+ </style>+ <!--[if IE]>+ <style>+ body {+ font-size: 13px;+ margin: 10px 10px;+ }+ </style>+ <![endif]-->++ <script type="text/javascript"><!--+ function addHeaderTags() {+ var spans = document.getElementsByTagName("span");+ for (var i=0; i < spans.length; i++) {+ var elem = spans[i];+ if (elem) {+ var level = elem.getAttribute("class");+ if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {+ elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">"; + }+ }+ }+ }+ var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";+ function showElem(id) {+ var elem = document.getElementById(id);+ elem.innerHTML = eval(id+"_html");+ elem.style.visibility='visible';+ }+ function hideElem(id) {+ var elem = document.getElementById(id);+ elem.style.visibility='hidden'; + elem.innerHTML = "";+ }+ // -->+ </script>+</head>+<body onload="addHeaderTags()">+ <div class="content">+ <div style="height: 13px;">+ <div onmouseover="this.style.cursor='pointer';"+ onclick="showElem('legend');"+ onmouseout="hideElem('legend')"+ style="height: 6px; position: absolute;"+ class="pre noprint docinfo bgorange"+ title="Click for colour legend." > </div>+ <div id="legend"+ class="docinfo noprint pre legend"+ style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "+ onmouseover="showElem('legend');"+ onmouseout="hideElem('legend');">+ </div>+ </div>+<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="/rfc/rfc1952.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/rfc1952" title="PDF version of this document">pdf</a>] [<a href="./draft-deutsch-gzip-spec" title="draft-deutsch-gzip-spec">draft-deutsch-gzi...</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=rfc1952" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=rfc1952" title="Side-by-side diff">Diff2</a>] </span><br />+<span class="pre noprint docinfo"> </span><br />+<span class="pre noprint docinfo"> INFORMATIONAL</span><br />+<span class="pre noprint docinfo"> </span><br />+<pre>+Network Working Group P. Deutsch+Request for Comments: 1952 Aladdin Enterprises+Category: Informational May 1996+++ <span class="h1">GZIP file format specification version 4.3</span>++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++ 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+ <<a href="ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html">ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html</a>>.++Abstract++ This specification defines a lossless compressed data format that is+ compatible with the widely used GZIP utility. The format includes a+ cyclic redundancy check value for detecting data corruption. The+ format presently uses the DEFLATE method of compression but can be+ easily extended to use other compression methods. The format can be+ implemented readily in a manner not covered by patents.+++++++++++<span class="grey">Deutsch Informational [Page 1]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++Table of Contents++ <a href="#section-1">1</a>. Introduction ................................................... <a href="#page-2">2</a>+ <a href="#section-1.1">1.1</a>. Purpose ................................................... <a href="#page-2">2</a>+ <a href="#section-1.2">1.2</a>. Intended audience ......................................... <a href="#page-3">3</a>+ <a href="#section-1.3">1.3</a>. Scope ..................................................... <a href="#page-3">3</a>+ <a href="#section-1.4">1.4</a>. Compliance ................................................ <a href="#page-3">3</a>+ <a href="#section-1.5">1.5</a>. Definitions of terms and conventions used ................. <a href="#page-3">3</a>+ <a href="#section-1.6">1.6</a>. Changes from previous versions ............................ <a href="#page-3">3</a>+ <a href="#section-2">2</a>. Detailed specification ......................................... <a href="#page-4">4</a>+ <a href="#section-2.1">2.1</a>. Overall conventions ....................................... <a href="#page-4">4</a>+ <a href="#section-2.2">2.2</a>. File format ............................................... <a href="#page-5">5</a>+ <a href="#section-2.3">2.3</a>. Member format ............................................. <a href="#page-5">5</a>+ <a href="#section-2.3.1">2.3.1</a>. Member header and trailer ........................... <a href="#page-6">6</a>+ <a href="#section-2.3.1.1">2.3.1.1</a>. Extra field ................................... <a href="#page-8">8</a>+ <a href="#section-2.3.1.2">2.3.1.2</a>. Compliance .................................... <a href="#page-9">9</a>+ <a href="#section-3">3</a>. References .................................................. <a href="#page-9">9</a>+ <a href="#section-4">4</a>. Security Considerations .................................... <a href="#page-10">10</a>+ <a href="#section-5">5</a>. Acknowledgements ........................................... <a href="#page-10">10</a>+ <a href="#section-6">6</a>. Author's Address ........................................... <a href="#page-10">10</a>+ <a href="#section-7">7</a>. Appendix: Jean-Loup Gailly's gzip utility .................. <a href="#page-11">11</a>+ <a href="#section-8">8</a>. Appendix: Sample CRC Code .................................. <a href="#page-11">11</a>++<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>++ 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 compress or decompress a data stream (as opposed to a+ randomly accessible file) to produce another 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;+ * Compresses data with efficiency comparable to the best+ currently available general-purpose compression methods,+ and in particular considerably better than the "compress"+ program;+ * Can be implemented readily in a manner not covered by+ patents, and hence can be practiced freely;+ * Is compatible with the file format produced by the current+ widely used gzip utility, in that conforming decompressors+ will be able to read data produced by the existing gzip+ compressor.+++++<span class="grey">Deutsch Informational [Page 2]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ The data format defined by this specification does not attempt to:++ * Provide random access to compressed data;+ * Compress specialized data (e.g., raster graphics) as well as+ the best currently available specialized algorithms.++ 1.2. Intended audience++ This specification is intended for use by implementors of software+ to compress data into gzip format and/or decompress data from gzip+ 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 compression method and a file format+ (the latter assuming only that a file can store a sequence of+ arbitrary bytes). It does not specify any particular interface to+ a file system or anything about character sets or encodings+ (except for file names and comments, which are optional).++ 1.4. Compliance++ Unless otherwise indicated below, a compliant decompressor must be+ able to accept and decompress any file that conforms to all the+ specifications presented here; a compliant compressor must produce+ files that conform to all the specifications presented here. The+ material in the appendices is not part of the specification per se+ and is not relevant to compliance.++ 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++ There have been no technical changes to the gzip format since+ version 4.1 of this specification. In version 4.2, some+ terminology was changed, and the sample CRC code was rewritten for+ clarity and to eliminate the requirement for the caller to do pre-+ and post-conditioning. Version 4.3 is a conversion of the+ specification to RFC style.++++<span class="grey">Deutsch Informational [Page 3]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Detailed specification</span>++ 2.1. Overall conventions++ In the diagrams below, a box like this:++ +---++ | | <-- the vertical bars might be missing+ +---+++ 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|+ +--------+++ This document does not address the issue of the order in which+ bits of a byte are transmitted on a bit-sequential medium, since+ the data format described here is byte- rather than bit-oriented.++ Within a computer, a number may occupy multiple bytes. All+ multi-byte numbers in the format described here are stored with+ the least-significant byte first (at the lower memory address).+ For example, the decimal number 520 is stored as:++ 0 1+ +--------+--------++ |00001000|00000010|+ +--------+--------++ ^ ^+ | |+ | + more significant byte = 2 x 256+ + less significant byte = 8++++<span class="grey">Deutsch Informational [Page 4]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ 2.2. File format++ A gzip file consists of a series of "members" (compressed data+ sets). The format of each member is specified in the following+ section. The members simply appear one after another in the file,+ with no additional information before, between, or after them.++ 2.3. Member format++ Each member has the following structure:++ +---+---+---+---+---+---+---+---+---+---++ |ID1|ID2|CM |FLG| MTIME |XFL|OS | (more-->)+ +---+---+---+---+---+---+---+---+---+---+++ (if FLG.FEXTRA set)++ +---+---+=================================++ | XLEN |...XLEN bytes of "extra field"...| (more-->)+ +---+---+=================================+++ (if FLG.FNAME set)++ +=========================================++ |...original file name, zero-terminated...| (more-->)+ +=========================================+++ (if FLG.FCOMMENT set)++ +===================================++ |...file comment, zero-terminated...| (more-->)+ +===================================+++ (if FLG.FHCRC set)++ +---+---++ | CRC16 |+ +---+---+++ +=======================++ |...compressed blocks...| (more-->)+ +=======================+++ 0 1 2 3 4 5 6 7+ +---+---+---+---+---+---+---+---++ | CRC32 | ISIZE |+ +---+---+---+---+---+---+---+---++++++<span class="grey">Deutsch Informational [Page 5]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ 2.3.1. Member header and trailer++ ID1 (IDentification 1)+ ID2 (IDentification 2)+ These have the fixed values ID1 = 31 (0x1f, \037), ID2 = 139+ (0x8b, \213), to identify the file as being in gzip format.++ CM (Compression Method)+ This identifies the compression method used in the file. CM+ = 0-7 are reserved. CM = 8 denotes the "deflate"+ compression method, which is the one customarily used by+ gzip and which is documented elsewhere.++ FLG (FLaGs)+ This flag byte is divided into individual bits as follows:++ bit 0 FTEXT+ bit 1 FHCRC+ bit 2 FEXTRA+ bit 3 FNAME+ bit 4 FCOMMENT+ bit 5 reserved+ bit 6 reserved+ bit 7 reserved++ If FTEXT is set, the file is probably ASCII text. This is+ an optional indication, which the compressor may set by+ checking a small amount of the input data to see whether any+ non-ASCII characters are present. In case of doubt, FTEXT+ is cleared, indicating binary data. For systems which have+ different file formats for ascii text and binary data, the+ decompressor can use FTEXT to choose the appropriate format.+ We deliberately do not specify the algorithm used to set+ this bit, since a compressor always has the option of+ leaving it cleared and a decompressor always has the option+ of ignoring it and letting some other program handle issues+ of data conversion.++ If FHCRC is set, a CRC16 for the gzip header is present,+ immediately before the compressed data. The CRC16 consists+ of the two least significant bytes of the CRC32 for all+ bytes of the gzip header up to and not including the CRC16.+ [The FHCRC bit was never set by versions of gzip up to+ 1.2.4, even though it was documented with a different+ meaning in gzip 1.2.4.]++ If FEXTRA is set, optional extra fields are present, as+ described in a following section.++++<span class="grey">Deutsch Informational [Page 6]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ If FNAME is set, an original file name is present,+ terminated by a zero byte. The name must consist of ISO+ 8859-1 (LATIN-1) characters; on operating systems using+ EBCDIC or any other character set for file names, the name+ must be translated to the ISO LATIN-1 character set. This+ is the original name of the file being compressed, with any+ directory components removed, and, if the file being+ compressed is on a file system with case insensitive names,+ forced to lower case. There is no original file name if the+ data was compressed from a source other than a named file;+ for example, if the source was stdin on a Unix system, there+ is no file name.++ If FCOMMENT is set, a zero-terminated file comment is+ present. This comment is not interpreted; it is only+ intended for human consumption. The comment must consist of+ ISO 8859-1 (LATIN-1) characters. Line breaks should be+ denoted by a single line feed character (10 decimal).++ Reserved FLG bits must be zero.++ MTIME (Modification TIME)+ This gives the most recent modification time of the original+ file being compressed. The time is in Unix format, i.e.,+ seconds since 00:00:00 GMT, Jan. 1, 1970. (Note that this+ may cause problems for MS-DOS and other systems that use+ local rather than Universal time.) If the compressed data+ did not come from a file, MTIME is set to the time at which+ compression started. MTIME = 0 means no time stamp is+ available.++ XFL (eXtra FLags)+ These flags are available for use by specific compression+ methods. The "deflate" method (CM = 8) sets these flags as+ follows:++ XFL = 2 - compressor used maximum compression,+ slowest algorithm+ XFL = 4 - compressor used fastest algorithm++ OS (Operating System)+ This identifies the type of file system on which compression+ took place. This may be useful in determining end-of-line+ convention for text files. The currently defined values are+ as follows:+++++++<span class="grey">Deutsch Informational [Page 7]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ 0 - FAT filesystem (MS-DOS, OS/2, NT/Win32)+ 1 - Amiga+ 2 - VMS (or OpenVMS)+ 3 - Unix+ 4 - VM/CMS+ 5 - Atari TOS+ 6 - HPFS filesystem (OS/2, NT)+ 7 - Macintosh+ 8 - Z-System+ 9 - CP/M+ 10 - TOPS-20+ 11 - NTFS filesystem (NT)+ 12 - QDOS+ 13 - Acorn RISCOS+ 255 - unknown++ XLEN (eXtra LENgth)+ If FLG.FEXTRA is set, this gives the length of the optional+ extra field. See below for details.++ CRC32 (CRC-32)+ This contains a Cyclic Redundancy Check value of the+ uncompressed data computed according to CRC-32 algorithm+ used in the ISO 3309 standard and in <a href="#section-8.1.1.6.2">section 8.1.1.6.2</a> of+ ITU-T recommendation V.42. (See <a href="http://www.iso.ch">http://www.iso.ch</a> for+ ordering ISO documents. See gopher://info.itu.ch for an+ online version of ITU-T V.42.)++ ISIZE (Input SIZE)+ This contains the size of the original (uncompressed) input+ data modulo 2^32.++ 2.3.1.1. Extra field++ If the FLG.FEXTRA bit is set, an "extra field" is present in+ the header, with total length XLEN bytes. It consists of a+ series of subfields, each of the form:++ +---+---+---+---+==================================++ |SI1|SI2| LEN |... LEN bytes of subfield data ...|+ +---+---+---+---+==================================+++ SI1 and SI2 provide a subfield ID, typically two ASCII letters+ with some mnemonic value. Jean-Loup Gailly+ <gzip@prep.ai.mit.edu> is maintaining a registry of subfield+ IDs; please send him any subfield ID you wish to use. Subfield+ IDs with SI2 = 0 are reserved for future use. The following+ IDs are currently defined:++++<span class="grey">Deutsch Informational [Page 8]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ SI1 SI2 Data+ ---------- ---------- ----+ 0x41 ('A') 0x70 ('P') Apollo file type information++ LEN gives the length of the subfield data, excluding the 4+ initial bytes.++ 2.3.1.2. Compliance++ A compliant compressor must produce files with correct ID1,+ ID2, CM, CRC32, and ISIZE, but may set all the other fields in+ the fixed-length part of the header to default values (255 for+ OS, 0 for all others). The compressor must set all reserved+ bits to zero.++ A compliant decompressor must check ID1, ID2, and CM, and+ provide an error indication if any of these have incorrect+ values. It must examine FEXTRA/XLEN, FNAME, FCOMMENT and FHCRC+ at least so it can skip over the optional fields if they are+ present. It need not examine any other part of the header or+ trailer; in particular, a decompressor may ignore FTEXT and OS+ and always produce binary output, and still be compliant. A+ compliant decompressor must give an error indication if any+ reserved bit is non-zero, since such a bit could indicate the+ presence of a new field that would cause subsequent data to be+ interpreted incorrectly.++<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. References</span>++ [<a name="ref-1" id="ref-1">1</a>] "Information Processing - 8-bit single-byte coded graphic+ character sets - Part 1: Latin alphabet No.1" (ISO 8859-1:1987).+ The ISO 8859-1 (Latin-1) character set is a superset of 7-bit+ ASCII. Files defining this character set are available as+ iso_8859-1.* in <a href="ftp://ftp.uu.net/graphics/png/documents/">ftp://ftp.uu.net/graphics/png/documents/</a>++ [<a name="ref-2" id="ref-2">2</a>] ISO 3309++ [<a name="ref-3" id="ref-3">3</a>] ITU-T recommendation V.42++ [<a name="ref-4" id="ref-4">4</a>] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification",+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-5" id="ref-5">5</a>] Gailly, J.-L., GZIP documentation, available as gzip-*.tar in+ <a href="ftp://prep.ai.mit.edu/pub/gnu/">ftp://prep.ai.mit.edu/pub/gnu/</a>++ [<a name="ref-6" id="ref-6">6</a>] Sarwate, D.V., "Computation of Cyclic Redundancy Checks via Table+ Look-Up", Communications of the ACM, 31(8), pp.1008-1013.+++++<span class="grey">Deutsch Informational [Page 9]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ [<a name="ref-7" id="ref-7">7</a>] Schwaderer, W.D., "CRC Calculation", April 85 PC Tech Journal,+ pp.118-133.++ [<a name="ref-8" id="ref-8">8</a>] <a href="ftp://ftp.adelaide.edu.au/pub/rocksoft/papers/crc_v3.txt">ftp://ftp.adelaide.edu.au/pub/rocksoft/papers/crc_v3.txt</a>,+ describing the CRC concept.++<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Security Considerations</span>++ Any data compression method involves the reduction of redundancy in+ the data. Consequently, any corruption of the data is likely to have+ severe effects and be difficult to correct. Uncompressed text, on+ the other hand, will probably still be readable despite the presence+ of some corrupted bytes.++ It is recommended that systems using this data format provide some+ means of validating the integrity of the compressed data, such as by+ setting and checking the CRC-32 check value.++<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. Acknowledgements</span>++ Trademarks cited in this document are the property of their+ respective owners.++ Jean-Loup Gailly designed the gzip format and wrote, with Mark Adler,+ the related software described in this specification. Glenn+ Randers-Pehrson converted this document to RFC and HTML format.++<span class="h2"><a class="selflink" name="section-6" href="#section-6">6</a>. Author's Address</span>++ 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>++ 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>++++<span class="grey">Deutsch Informational [Page 10]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-7" href="#section-7">7</a>. Appendix: Jean-Loup Gailly's gzip utility</span>++ The most widely used implementation of gzip compression, and the+ original documentation on which this specification is based, were+ created by Jean-Loup Gailly <gzip@prep.ai.mit.edu>. Since this+ implementation is a de facto standard, we mention some more of its+ features here. Again, the material in this section is not part of+ the specification per se, and implementations need not follow it to+ be compliant.++ When compressing or decompressing a file, gzip preserves the+ protection, ownership, and modification time attributes on the local+ file system, since there is no provision for representing protection+ attributes in the gzip file format itself. Since the file format+ includes a modification time, the gzip decompressor provides a+ command line switch that assigns the modification time from the file,+ rather than the local modification time of the compressed input, to+ the decompressed output.++<span class="h2"><a class="selflink" name="section-8" href="#section-8">8</a>. Appendix: Sample CRC Code</span>++ The following sample code represents a practical implementation of+ the CRC (Cyclic Redundancy Check). (See also ISO 3309 and ITU-T V.42+ for a formal specification.)++ 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 exclusive-OR operator.+ >> Bitwise right shift operator. When applied to an+ unsigned quantity, as here, right shift inserts zero+ bit(s) at the left.+ ! Logical NOT operator.+ ++ "n++" increments the variable n.+ 0xNNN 0x introduces a hexadecimal (base 16) constant.+ Suffix L indicates a long value (at least 32 bits).++ /* Table of CRCs of all 8-bit messages. */+ unsigned long crc_table[256];++ /* Flag: has the table been computed? Initially false. */+ int crc_table_computed = 0;++ /* Make the table for a fast CRC. */+ void make_crc_table(void)+ {+ unsigned long c;++++<span class="grey">Deutsch Informational [Page 11]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-12" id="page-12" href="#page-12" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ int n, k;+ for (n = 0; n < 256; n++) {+ c = (unsigned long) n;+ for (k = 0; k < 8; k++) {+ if (c & 1) {+ c = 0xedb88320L ^ (c >> 1);+ } else {+ c = c >> 1;+ }+ }+ crc_table[n] = c;+ }+ crc_table_computed = 1;+ }++ /*+ Update a running crc with the bytes buf[0..len-1] and return+ the updated crc. The crc should be initialized to zero. Pre- and+ post-conditioning (one's complement) is performed within this+ function so it shouldn't be done by the caller. Usage example:++ unsigned long crc = 0L;++ while (read_buffer(buffer, length) != EOF) {+ crc = update_crc(crc, buffer, length);+ }+ if (crc != original_crc) error();+ */+ unsigned long update_crc(unsigned long crc,+ unsigned char *buf, int len)+ {+ unsigned long c = crc ^ 0xffffffffL;+ int n;++ if (!crc_table_computed)+ make_crc_table();+ for (n = 0; n < len; n++) {+ c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);+ }+ return c ^ 0xffffffffL;+ }++ /* Return the CRC of the bytes buf[0..len-1]. */+ unsigned long crc(unsigned char *buf, int len)+ {+ return update_crc(0L, buf, len);+ }+++++Deutsch Informational [Page 12]++</pre><br />+ <span class="noprint"><small><small>Html markup produced by rfcmarkup 1.119, available from+ <a href="https://tools.ietf.org/tools/rfcmarkup/">https://tools.ietf.org/tools/rfcmarkup/</a>+ </small></small></span>+ </div>+</body>+</html>
+ test/test-cases/rfctest3.z view
binary file changed (absent → 10928 bytes)
+ test/test-cases/tor-list.gold view
file too large to diff
+ test/test-cases/tor-list.z view
file too large to diff
+ test/test-cases/zerotest1.gold view
binary file changed (absent → 4096 bytes)
+ test/test-cases/zerotest1.z view
binary file changed (absent → 26 bytes)
+ test/test-cases/zerotest2.gold view
binary file changed (absent → 65536 bytes)
+ test/test-cases/zerotest2.z view
binary file changed (absent → 84 bytes)
+ test/test-cases/zerotest3.gold view
binary file changed (absent → 1048576 bytes)
+ test/test-cases/zerotest3.z view
binary file changed (absent → 1039 bytes)