Network Working Group                                         P. Deutsch
Request for Comments: 1951                           Aladdin Enterprises
Category: Informational                                         May 1996


        DEFLATE Compressed Data Format Specification version 1.3

Status of This Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

IESG Note:

   The IESG takes no position on the validity of any Intellectual
   Property Rights statements contained in this document.

Notices

   Copyright (c) 1996 L. Peter Deutsch

   Permission is granted to copy and distribute this document for any
   purpose and without charge, including translations into other
   languages and incorporation into compilations, provided that the
   copyright notice and this notice are preserved, and that any
   substantive changes or deletions from the original are clearly
   marked.

   A pointer to the latest version of this and related documentation in
   HTML format can be found at the URL
   <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.

Abstract

   This specification defines a lossless compressed data format 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.









 
RFC 1951      DEFLATE Compressed Data Format Specification      May 1996


Table of Contents

   1. Introduction ................................................... 2
      1.1. Purpose ................................................... 2
      1.2. Intended audience ......................................... 3
      1.3. Scope ..................................................... 3
      1.4. Compliance ................................................ 3
      1.5.  Definitions of terms and conventions used ................ 3
      1.6. Changes from previous versions ............................ 4
   2. Compressed representation overview ............................. 4
   3. Detailed specification ......................................... 5
      3.1. Overall conventions ....................................... 5
          3.1.1. Packing into bytes .................................. 5
      3.2. Compressed block format ................................... 6
          3.2.1. Synopsis of prefix and Huffman coding ............... 6
          3.2.2. Use of Huffman coding in the "deflate" format ....... 7
          3.2.3. Details of block format ............................. 9
          3.2.4. Non-compressed blocks (BTYPE=00) ................... 11
          3.2.5. Compressed blocks (length and distance codes) ...... 11
          3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 12
          3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 13
      3.3. Compliance ............................................... 14
   4. Compression algorithm details ................................. 14
   5. References .................................................... 16
   6. Security Considerations ....................................... 16
   7. Source code ................................................... 16
   8. Acknowledgements .............................................. 16
   9. Author's Address .............................................. 17

1. Introduction

   1.1. Purpose

      The purpose of this specification is to define a lossless
      compressed data format that:
          * Is independent of CPU type, operating system, file system,
            and character set, and hence can be used for interchange;
          * Can be produced or consumed, even for an arbitrarily long