deflate.java

纯Java实现的ZIP文件压缩解压类库,JDK中的ZIP类库源码中有一些native方法

/* -*-mode:java; c-basic-offset:2; -*- */
/*
Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice,
     this list of conditions and the following disclaimer.

  2. Redistributions in binary form must reproduce the above copyright 
     notice, this list of conditions and the following disclaimer in 
     the documentation and/or other materials provided with the distribution.

  3. The names of the authors may not be used to endorse or promote products
     derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * This program is based on zlib-1.1.3, so all credit should go authors
 * Jean-loup Gailly([e-mail]) and Mark Adler([e-mail])
 * and contributors of zlib.
 */

package com.jcraft.jzlib;

public 
final class Deflate{

  static final private int MAX_MEM_LEVEL=9;

  static final private int Z_DEFAULT_COMPRESSION=-1;

  static final private int MAX_WBITS=15;            // 32K LZ77 window
  static final private int DEF_MEM_LEVEL=8;

  static class Config{
    int good_length; // reduce lazy search above this match length
    int max_lazy;    // do not perform lazy search above this match length
    int nice_length; // quit search above this match length
    int max_chain;
    int func;
    Config(int good_length, int max_lazy, 
	   int nice_length, int max_chain, int func){
      this.good_length=good_length;
      this.max_lazy=max_lazy;
      this.nice_length=nice_length;
      this.max_chain=max_chain;
      this.func=func;
    }
  }
  
  static final private int STORED=0;
  static final private int FAST=1;
  static final private int SLOW=2;
  static final private Config[] config_table;    
  static{
    config_table=new Config[10];
    //                         good  lazy  nice  chain
    config_table[0]=new Config(0,    0,    0,    0, STORED);
    config_table[1]=new Config(4,    4,    8,    4, FAST);
    config_table[2]=new Config(4,    5,   16,    8, FAST);
    config_table[3]=new Config(4,    6,   32,   32, FAST);

    config_table[4]=new Config(4,    4,   16,   16, SLOW);
    config_table[5]=new Config(8,   16,   32,   32, SLOW);
    config_table[6]=new Config(8,   16,  128,  128, SLOW);
    config_table[7]=new Config(8,   32,  128,  256, SLOW);
    config_table[8]=new Config(32, 128,  258, 1024, SLOW);
    config_table[9]=new Config(32, 258,  258, 4096, SLOW);
  }

  static final private String[] z_errmsg = {
    "need dictionary",     // Z_NEED_DICT       2
    "stream end",          // Z_STREAM_END      1
    "",                    // Z_OK              0
    "file error",          // Z_ERRNO         (-1)
    "stream error",        // Z_STREAM_ERROR  (-2)
    "data error",          // Z_DATA_ERROR    (-3)
    "insufficient memory", // Z_MEM_ERROR     (-4)
    "buffer error",        // Z_BUF_ERROR     (-5)
    "incompatible version",// Z_VERSION_ERROR (-6)
    ""
  };

  // block not completed, need more input or more output
  static final private int NeedMore=0; 

  // block flush performed
  static final private int BlockDone=1; 

  // finish started, need only more output at next deflate
  static final private int FinishStarted=2;

  // finish done, accept no more input or output
  static final private int FinishDone=3;

  // preset dictionary flag in zlib header
  static final private int PRESET_DICT=0x20;

  static final private int Z_FILTERED=1;
  static final private int Z_HUFFMAN_ONLY=2;
  static final private int Z_DEFAULT_STRATEGY=0;

  static final private int Z_NO_FLUSH=0;
  static final private int Z_PARTIAL_FLUSH=1;
  static final private int Z_SYNC_FLUSH=2;
  static final private int Z_FULL_FLUSH=3;
  static final private int Z_FINISH=4;

  static final private int Z_OK=0;
  static final private int Z_STREAM_END=1;
  static final private int Z_NEED_DICT=2;
  static final private int Z_ERRNO=-1;
  static final private int Z_STREAM_ERROR=-2;
  static final private int Z_DATA_ERROR=-3;
  static final private int Z_MEM_ERROR=-4;
  static final private int Z_BUF_ERROR=-5;
  static final private int Z_VERSION_ERROR=-6;

  static final private int INIT_STATE=42;
  static final private int BUSY_STATE=113;
  static final private int FINISH_STATE=666;

  // The deflate compression method
  static final private int Z_DEFLATED=8;

  static final private int STORED_BLOCK=0;
  static final private int STATIC_TREES=1;
  static final private int DYN_TREES=2;

  // The three kinds of block type
  static final private int Z_BINARY=0;
  static final private int Z_ASCII=1;
  static final private int Z_UNKNOWN=2;

  static final private int Buf_size=8*2;

  // repeat previous bit length 3-6 times (2 bits of repeat count)
  static final private int REP_3_6=16; 

  // repeat a zero length 3-10 times  (3 bits of repeat count)
  static final private int REPZ_3_10=17; 

  // repeat a zero length 11-138 times  (7 bits of repeat count)
  static final private int REPZ_11_138=18; 

  static final private int MIN_MATCH=3;
  static final private int MAX_MATCH=258;
  static final private int MIN_LOOKAHEAD=(MAX_MATCH+MIN_MATCH+1);

  static final private int MAX_BITS=15;
  static final private int D_CODES=30;
  static final private int BL_CODES=19;
  static final private int LENGTH_CODES=29;
  static final private int LITERALS=256;
  static final private int L_CODES=(LITERALS+1+LENGTH_CODES);
  static final private int HEAP_SIZE=(2*L_CODES+1);

  static final private int END_BLOCK=256;

  ZStream strm;         // pointer back to this zlib stream
  int status;           // as the name implies
  byte[] pending_buf;   // output still pending
  int pending_buf_size; // size of pending_buf
  int pending_out;      // next pending byte to output to the stream
  int pending;          // nb of bytes in the pending buffer
  int noheader;         // suppress zlib header and adler32
  byte data_type;       // UNKNOWN, BINARY or ASCII
  byte method;          // STORED (for zip only) or DEFLATED
  int last_flush;       // value of flush param for previous deflate call

  int w_size;           // LZ77 window size (32K by default)
  int w_bits;           // log2(w_size)  (8..16)
  int w_mask;           // w_size - 1

  byte[] window;
  // Sliding window. Input bytes are read into the second half of the window,
  // and move to the first half later to keep a dictionary of at least wSize
  // bytes. With this organization, matches are limited to a distance of
  // wSize-MAX_MATCH bytes, but this ensures that IO is always
  // performed with a length multiple of the block size. Also, it limits
  // the window size to 64K, which is quite useful on MSDOS.
  // To do: use the user input buffer as sliding window.

  int window_size;
  // Actual size of window: 2*wSize, except when the user input buffer
  // is directly used as sliding window.

  short[] prev;
  // Link to older string with same hash index. To limit the size of this
  // array to 64K, this link is maintained only for the last 32K strings.
  // An index in this array is thus a window index modulo 32K.

  short[] head; // Heads of the hash chains or NIL.

  int ins_h;          // hash index of string to be inserted
  int hash_size;      // number of elements in hash table
  int hash_bits;      // log2(hash_size)
  int hash_mask;      // hash_size-1

  // Number of bits by which ins_h must be shifted at each input
  // step. It must be such that after MIN_MATCH steps, the oldest
  // byte no longer takes part in the hash key, that is:
  // hash_shift * MIN_MATCH >= hash_bits
  int hash_shift;

  // Window position at the beginning of the current output block. Gets
  // negative when the window is moved backwards.

  int block_start;

  int match_length;           // length of best match
  int prev_match;             // previous match
  int match_available;        // set if previous match exists
  int strstart;               // start of string to insert
  int match_start;            // start of matching string
  int lookahead;              // number of valid bytes ahead in window

  // Length of the best match at previous step. Matches not greater than this
  // are discarded. This is used in the lazy match evaluation.
  int prev_length;

  // To speed up deflation, hash chains are never searched beyond this
  // length.  A higher limit improves compression ratio but degrades the speed.
  int max_chain_length;

  // Attempt to find a better match only when the current match is strictly
  // smaller than this value. This mechanism is used only for compression
  // levels >= 4.
  int max_lazy_match;

  // Insert new strings in the hash table only if the match length is not
  // greater than this length. This saves time but degrades compression.
  // max_insert_length is used only for compression levels <= 3.

  int level;    // compression level (1..9)
  int strategy; // favor or force Huffman coding

  // Use a faster search when the previous match is longer than this
  int good_match;

  // Stop searching when current match exceeds this
  int nice_match;

  short[] dyn_ltree;       // literal and length tree
  short[] dyn_dtree;       // distance tree
  short[] bl_tree;         // Huffman tree for bit lengths

  Tree l_desc=new Tree();  // desc for literal tree
  Tree d_desc=new Tree();  // desc for distance tree
  Tree bl_desc=new Tree(); // desc for bit length tree

  // number of codes at each bit length for an optimal tree
  short[] bl_count=new short[MAX_BITS+1];

  // heap used to build the Huffman trees
  int[] heap=new int[2*L_CODES+1];

  int heap_len;               // number of elements in the heap
  int heap_max;               // element of largest frequency
  // The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  // The same heap array is used to build all trees.

  // Depth of each subtree used as tie breaker for trees of equal frequency
  byte[] depth=new byte[2*L_CODES+1];

  int l_buf;               // index for literals or lengths */

  // Size of match buffer for literals/lengths.  There are 4 reasons for
  // limiting lit_bufsize to 64K:
  //   - frequencies can be kept in 16 bit counters
  //   - if compression is not successful for the first block, all input
  //     data is still in the window so we can still emit a stored block even
  //     when input comes from standard input.  (This can also be done for
  //     all blocks if lit_bufsize is not greater than 32K.)
  //   - if compression is not successful for a file smaller than 64K, we can
  //     even emit a stored file instead of a stored block (saving 5 bytes).
  //     This is applicable only for zip (not gzip or zlib).
  //   - creating new Huffman trees less frequently may not provide fast
  //     adaptation to changes in the input data statistics. (Take for
  //     example a binary file with poorly compressible code followed by
  //     a highly compressible string table.) Smaller buffer sizes give
  //     fast adaptation but have of course the overhead of transmitting
  //     trees more frequently.
  //   - I can't count above 4
  int lit_bufsize;

  int last_lit;      // running index in l_buf

  // Buffer for distances. To simplify the code, d_buf and l_buf have
  // the same number of elements. To use different lengths, an extra flag
  // array would be necessary.

  int d_buf;         // index of pendig_buf

  int opt_len;        // bit length of current block with optimal trees
  int static_len;     // bit length of current block with static trees
  int matches;        // number of string matches in current block
  int last_eob_len;   // bit length of EOB code for last block

  // Output buffer. bits are inserted starting at the bottom (least
  // significant bits).
  short bi_buf;

  // Number of valid bits in bi_buf.  All bits above the last valid bit
  // are always zero.
  int bi_valid;

  Deflate(){
    dyn_ltree=new short[HEAP_SIZE*2];
    dyn_dtree=new short[(2*D_CODES+1)*2]; // distance tree
    bl_tree=new short[(2*BL_CODES+1)*2];  // Huffman tree for bit lengths
  }

  void lm_init() {
    window_size=2*w_size;

    head[hash_size-1]=0;
    for(int i=0; i<hash_size-1; i++){
      head[i]=0;
    }

    // Set the default configuration parameters:
    max_lazy_match   = Deflate.config_table[level].max_lazy;
    good_match       = Deflate.config_table[level].good_length;
    nice_match       = Deflate.config_table[level].nice_length;
    max_chain_length = Deflate.config_table[level].max_chain;

    strstart = 0;
    block_start = 0;
    lookahead = 0;
    match_length = prev_length = MIN_MATCH-1;
    match_available = 0;
    ins_h = 0;
  }

  // Initialize the tree data structures for a new zlib stream.
  void tr_init(){

    l_desc.dyn_tree = dyn_ltree;
    l_desc.stat_desc = StaticTree.static_l_desc;

    d_desc.dyn_tree = dyn_dtree;
    d_desc.stat_desc = StaticTree.static_d_desc;

    bl_desc.dyn_tree = bl_tree;
    bl_desc.stat_desc = StaticTree.static_bl_desc;

    bi_buf = 0;
    bi_valid = 0;
    last_eob_len = 8; // enough lookahead for inflate

    // Initialize the first block of the first file:
    init_block();
  }

  void init_block(){
    // Initialize the trees.
    for(int i = 0; i < L_CODES; i++) dyn_ltree[i*2] = 0;
    for(int i= 0; i < D_CODES; i++) dyn_dtree[i*2] = 0;
    for(int i= 0; i < BL_CODES; i++) bl_tree[i*2] = 0;

    dyn_ltree[END_BLOCK*2] = 1;
    opt_len = static_len = 0;
    last_lit = matches = 0;
  }

  // Restore the heap property by moving down the tree starting at node k,
  // exchanging a node with the smallest of its two sons if necessary, stopping
  // when the heap property is re-established (each father smaller than its
  // two sons).
  void pqdownheap(short[] tree,  // the tree to restore
		  int k          // node to move down
		  ){
    int v = heap[k];
    int j = k << 1;  // left son of k
    while (j <= heap_len) {
      // Set j to the smallest of the two sons:
      if (j < heap_len &&
	  smaller(tree, heap[j+1], heap[j], depth)){
	j++;
      }
      // Exit if v is smaller than both sons
      if(smaller(tree, v, heap[j], depth)) break;

      // Exchange v with the smallest son
      heap[k]=heap[j];  k = j;
      // And continue down the tree, setting j to the left son of k
      j <<= 1;
    }
    heap[k] = v;
  }

  static boolean smaller(short[] tree, int n, int m, byte[] depth){
    short tn2=tree[n*2];