deflate-1.3.doc

This is a resource based on j2me embedded,if you dont understand,you can connection with me .

INTERNET-DRAFT                                             L. P. Deutsch
DEFLATE 1.3                                          Aladdin Enterprises
Expires: 24 July 1996                                        24 Jan 1996

DEFLATE Compressed Data Format Specification version 1.3

File draft-deutsch-deflate-1.3-00.txt

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet- Drafts as reference
   material or to cite them other than as ``work in progress.''

   To learn the current status of any Internet-Draft, please check the
   ``1id-abstracts.txt'' listing contained in the Internet- Drafts
   Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).

   Distribution of this memo is unlimited.

 Notices

   Copyright (C) 1995 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 it is
   copied as a whole (including the copyright notice and this notice)
   and with no changes.

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.



Deutsch                                                        [Page  1]

Internet DraftDEFLATE Compressed Data Format Specification   24 Jan 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 ................. 4
      1.6 Changes from previous versions ............................. 4
   2. Compressed representation overview ............................. 4
   3. Detailed specification ......................................... 4
      3.1 Overall conventions ........................................ 4
          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) ................... 10
          3.2.5. Compressed blocks (length and distance codes) ...... 10
          3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 11
          3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 11
      3.3 Compliance ................................................ 13
   4. Compression algorithm details ................................. 13
   5. References .................................................... 14
   6. Security considerations ....................................... 14
   7. Source code ................................................... 15
   8. Acknowledgements .............................................. 15
   9. Author's address .............................................. 15

1. Introduction

   1.1. Purpose

      The purpose of this specification is to define a lossless
      compressed data format that:

          o Is independent of CPU type, operating system, file system,
            and character set, and hence can be used for interchange;
          o 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;
          o Compresses data with efficiency comparable to the best
            currently available general-purpose compression methods, and
            in particular considerably better than the 'compress'
            program;
          o Can be implemented readily in a manner not covered by
            patents, and hence can be practiced freely;
          o 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


Deutsch                                                        [Page  2]

Internet DraftDEFLATE Compressed Data Format Specification   24 Jan 1996


            compressor.

      The data format defined by this specification does not attempt to:

          o Allow random access to compressed data;
          o 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 which store a character on a number of bits different
      from 8.) See Section 3.1, below, for the numbering of bits within
      a byte.

      string: a sequence of arbitrary bytes.

   1.6. Changes from previous versions


Deutsch                                                        [Page  3]

Internet DraftDEFLATE Compressed Data Format Specification   24 Jan 1996


      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 Internet Draft style.

2. Compressed representation overview

   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 independant
   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.

3. Detailed specification

   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


Deutsch                                                        [Page  4]

Internet DraftDEFLATE Compressed Data Format Specification   24 Jan 1996


      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
         bit-oriented.  However, we describe the compressed block format
         in Section 3.2, 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:

             o 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.
             o Data elements other than Huffman codes are packed
               starting with the least-significant bit of the data
               element.
             o 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


Deutsch                                                        [Page  5]

Internet DraftDEFLATE Compressed Data Format Specification   24 Jan 1996


         bit-reversed order (i.e., with the first bit of the code in the