deflate.java

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

    short tm2=tree[m*2];
    return (tn2<tm2 ||
	    (tn2==tm2 && depth[n] <= depth[m]));
  }

  // Scan a literal or distance tree to determine the frequencies of the codes
  // in the bit length tree.
  void scan_tree (short[] tree,// the tree to be scanned
		  int max_code // and its largest code of non zero frequency
		  ){
    int n;                     // iterates over all tree elements
    int prevlen = -1;          // last emitted length
    int curlen;                // length of current code
    int nextlen = tree[0*2+1]; // length of next code
    int count = 0;             // repeat count of the current code
    int max_count = 7;         // max repeat count
    int min_count = 4;         // min repeat count

    if (nextlen == 0){ max_count = 138; min_count = 3; }
    tree[(max_code+1)*2+1] = (short)0xffff; // guard

    for(n = 0; n <= max_code; n++) {
      curlen = nextlen; nextlen = tree[(n+1)*2+1];
      if(++count < max_count && curlen == nextlen) {
	continue;
      }
      else if(count < min_count) {
	bl_tree[curlen*2] += count;
      }
      else if(curlen != 0) {
	if(curlen != prevlen) bl_tree[curlen*2]++;
	bl_tree[REP_3_6*2]++;
      }
      else if(count <= 10) {
	bl_tree[REPZ_3_10*2]++;
      }
      else{
	bl_tree[REPZ_11_138*2]++;
      }
      count = 0; prevlen = curlen;
      if(nextlen == 0) {
	max_count = 138; min_count = 3;
      }
      else if(curlen == nextlen) {
	max_count = 6; min_count = 3;
      }
      else{
	max_count = 7; min_count = 4;
      }
    }
  }

  // Construct the Huffman tree for the bit lengths and return the index in
  // bl_order of the last bit length code to send.
  int build_bl_tree(){
    int max_blindex;  // index of last bit length code of non zero freq

    // Determine the bit length frequencies for literal and distance trees
    scan_tree(dyn_ltree, l_desc.max_code);
    scan_tree(dyn_dtree, d_desc.max_code);

    // Build the bit length tree:
    bl_desc.build_tree(this);
    // opt_len now includes the length of the tree representations, except
    // the lengths of the bit lengths codes and the 5+5+4 bits for the counts.

    // Determine the number of bit length codes to send. The pkzip format
    // requires that at least 4 bit length codes be sent. (appnote.txt says
    // 3 but the actual value used is 4.)
    for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
      if (bl_tree[Tree.bl_order[max_blindex]*2+1] != 0) break;
    }
    // Update opt_len to include the bit length tree and counts
    opt_len += 3*(max_blindex+1) + 5+5+4;

    return max_blindex;
  }


  // Send the header for a block using dynamic Huffman trees: the counts, the
  // lengths of the bit length codes, the literal tree and the distance tree.
  // IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
  void send_all_trees(int lcodes, int dcodes, int blcodes){
    int rank;                    // index in bl_order

    send_bits(lcodes-257, 5); // not +255 as stated in appnote.txt
    send_bits(dcodes-1,   5);
    send_bits(blcodes-4,  4); // not -3 as stated in appnote.txt
    for (rank = 0; rank < blcodes; rank++) {
      send_bits(bl_tree[Tree.bl_order[rank]*2+1], 3);
    }
    send_tree(dyn_ltree, lcodes-1); // literal tree
    send_tree(dyn_dtree, dcodes-1); // distance tree
  }

  // Send a literal or distance tree in compressed form, using the codes in
  // bl_tree.
  void send_tree (short[] tree,// the tree to be sent
		  int max_code // and its largest code of non zero frequency
		  ){
    int n;                     // iterates over all tree elements
    int prevlen = -1;          // last emitted length
    int curlen;                // length of current code
    int nextlen = tree[0*2+1]; // length of next code
    int count = 0;             // repeat count of the current code
    int max_count = 7;         // max repeat count
    int min_count = 4;         // min repeat count

    if (nextlen == 0){ max_count = 138; min_count = 3; }

    for (n = 0; n <= max_code; n++) {
      curlen = nextlen; nextlen = tree[(n+1)*2+1];
      if(++count < max_count && curlen == nextlen) {
	continue;
      }
      else if(count < min_count) {
	do { send_code(curlen, bl_tree); } while (--count != 0);
      }
      else if(curlen != 0){
	if(curlen != prevlen){
	  send_code(curlen, bl_tree); count--;
	}
	send_code(REP_3_6, bl_tree); 
	send_bits(count-3, 2);
      }
      else if(count <= 10){
	send_code(REPZ_3_10, bl_tree); 
	send_bits(count-3, 3);
      }
      else{
	send_code(REPZ_11_138, bl_tree);
	send_bits(count-11, 7);
      }
      count = 0; prevlen = curlen;
      if(nextlen == 0){
	max_count = 138; min_count = 3;
      }
      else if(curlen == nextlen){
	max_count = 6; min_count = 3;
      }
      else{
	max_count = 7; min_count = 4;
      }
    }
  }

  // Output a byte on the stream.
  // IN assertion: there is enough room in pending_buf.
  final void put_byte(byte[] p, int start, int len){
    System.arraycopy(p, start, pending_buf, pending, len);
    pending+=len;
  }

  final void put_byte(byte c){
    pending_buf[pending++]=c;
  }
  final void put_short(int w) {
    put_byte((byte)(w/*&0xff*/));
    put_byte((byte)(w>>>8));
  }
  final void putShortMSB(int b){
    put_byte((byte)(b>>8));
    put_byte((byte)(b/*&0xff*/));
  }   

  final void send_code(int c, short[] tree){
    int c2=c*2;
    send_bits((tree[c2]&0xffff), (tree[c2+1]&0xffff));
  }

  void send_bits(int value, int length){
    int len = length;
    if (bi_valid > (int)Buf_size - len) {
      int val = value;
//      bi_buf |= (val << bi_valid);
      bi_buf |= ((val << bi_valid)&0xffff);
      put_short(bi_buf);
      bi_buf = (short)(val >>> (Buf_size - bi_valid));
      bi_valid += len - Buf_size;
    } else {
//      bi_buf |= (value) << bi_valid;
      bi_buf |= (((value) << bi_valid)&0xffff);
      bi_valid += len;
    }
  }

  // Send one empty static block to give enough lookahead for inflate.
  // This takes 10 bits, of which 7 may remain in the bit buffer.
  // The current inflate code requires 9 bits of lookahead. If the
  // last two codes for the previous block (real code plus EOB) were coded
  // on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
  // the last real code. In this case we send two empty static blocks instead
  // of one. (There are no problems if the previous block is stored or fixed.)
  // To simplify the code, we assume the worst case of last real code encoded
  // on one bit only.
  void _tr_align(){
    send_bits(STATIC_TREES<<1, 3);
    send_code(END_BLOCK, StaticTree.static_ltree);

    bi_flush();

    // Of the 10 bits for the empty block, we have already sent
    // (10 - bi_valid) bits. The lookahead for the last real code (before
    // the EOB of the previous block) was thus at least one plus the length
    // of the EOB plus what we have just sent of the empty static block.
    if (1 + last_eob_len + 10 - bi_valid < 9) {
      send_bits(STATIC_TREES<<1, 3);
      send_code(END_BLOCK, StaticTree.static_ltree);
      bi_flush();
    }
    last_eob_len = 7;
  }


  // Save the match info and tally the frequency counts. Return true if
  // the current block must be flushed.
  boolean _tr_tally (int dist, // distance of matched string
		     int lc // match length-MIN_MATCH or unmatched char (if dist==0)
		     ){

    pending_buf[d_buf+last_lit*2] = (byte)(dist>>>8);
    pending_buf[d_buf+last_lit*2+1] = (byte)dist;

    pending_buf[l_buf+last_lit] = (byte)lc; last_lit++;

    if (dist == 0) {
      // lc is the unmatched char
      dyn_ltree[lc*2]++;
    } 
    else {
      matches++;
      // Here, lc is the match length - MIN_MATCH
      dist--;             // dist = match distance - 1
      dyn_ltree[(Tree._length_code[lc]+LITERALS+1)*2]++;
      dyn_dtree[Tree.d_code(dist)*2]++;
    }

    if ((last_lit & 0x1fff) == 0 && level > 2) {
      // Compute an upper bound for the compressed length
      int out_length = last_lit*8;
      int in_length = strstart - block_start;
      int dcode;
      for (dcode = 0; dcode < D_CODES; dcode++) {
	out_length += (int)dyn_dtree[dcode*2] *
	  (5L+Tree.extra_dbits[dcode]);
      }
      out_length >>>= 3;
      if ((matches < (last_lit/2)) && out_length < in_length/2) return true;
    }

    return (last_lit == lit_bufsize-1);
    // We avoid equality with lit_bufsize because of wraparound at 64K
    // on 16 bit machines and because stored blocks are restricted to
    // 64K-1 bytes.
  }

  // Send the block data compressed using the given Huffman trees
  void compress_block(short[] ltree, short[] dtree){
    int  dist;      // distance of matched string
    int lc;         // match length or unmatched char (if dist == 0)
    int lx = 0;     // running index in l_buf
    int code;       // the code to send
    int extra;      // number of extra bits to send

    if (last_lit != 0){
      do{
	dist=((pending_buf[d_buf+lx*2]<<8)&0xff00)|
	  (pending_buf[d_buf+lx*2+1]&0xff);
	lc=(pending_buf[l_buf+lx])&0xff; lx++;

	if(dist == 0){
	  send_code(lc, ltree); // send a literal byte
	} 
	else{
	  // Here, lc is the match length - MIN_MATCH
	  code = Tree._length_code[lc];

	  send_code(code+LITERALS+1, ltree); // send the length code
	  extra = Tree.extra_lbits[code];
	  if(extra != 0){
	    lc -= Tree.base_length[code];
	    send_bits(lc, extra);       // send the extra length bits
	  }
	  dist--; // dist is now the match distance - 1
	  code = Tree.d_code(dist);

	  send_code(code, dtree);       // send the distance code
	  extra = Tree.extra_dbits[code];
	  if (extra != 0) {
	    dist -= Tree.base_dist[code];
	    send_bits(dist, extra);   // send the extra distance bits
	  }
	} // literal or match pair ?

	// Check that the overlay between pending_buf and d_buf+l_buf is ok:
      }
      while (lx < last_lit);
    }

    send_code(END_BLOCK, ltree);
    last_eob_len = ltree[END_BLOCK*2+1];
  }

  // Set the data type to ASCII or BINARY, using a crude approximation:
  // binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
  // IN assertion: the fields freq of dyn_ltree are set and the total of all
  // frequencies does not exceed 64K (to fit in an int on 16 bit machines).
  void set_data_type(){
    int n = 0;
    int  ascii_freq = 0;
    int  bin_freq = 0;
    while(n<7){ bin_freq += dyn_ltree[n*2]; n++;}
    while(n<128){ ascii_freq += dyn_ltree[n*2]; n++;}
    while(n<LITERALS){ bin_freq += dyn_ltree[n*2]; n++;}
    data_type=(byte)(bin_freq > (ascii_freq >>> 2) ? Z_BINARY : Z_ASCII);
  }

  // Flush the bit buffer, keeping at most 7 bits in it.
  void bi_flush(){
    if (bi_valid == 16) {
      put_short(bi_buf);
      bi_buf=0;
      bi_valid=0;
    }
    else if (bi_valid >= 8) {
      put_byte((byte)bi_buf);
      bi_buf>>>=8;
      bi_valid-=8;
    }
  }

  // Flush the bit buffer and align the output on a byte boundary
  void bi_windup(){
    if (bi_valid > 8) {
      put_short(bi_buf);
    } else if (bi_valid > 0) {
      put_byte((byte)bi_buf);
    }
    bi_buf = 0;
    bi_valid = 0;
  }

  // Copy a stored block, storing first the length and its
  // one's complement if requested.
  void copy_block(int buf,         // the input data
		  int len,         // its length
		  boolean header   // true if block header must be written
		  ){
    int index=0;
    bi_windup();      // align on byte boundary
    last_eob_len = 8; // enough lookahead for inflate

    if (header) {
      put_short((short)len);   
      put_short((short)~len);
    }

    //  while(len--!=0) {
    //    put_byte(window[buf+index]);
    //    index++;
    //  }
    put_byte(window, buf, len);
  }

  void flush_block_only(boolean eof){
    _tr_flush_block(block_start>=0 ? block_start : -1,
		    strstart-block_start,
		    eof);
    block_start=strstart;
    strm.flush_pending();
  }

  // Copy without compression as much as possible from the input stream, return
  // the current block state.
  // This function does not insert new strings in the dictionary since
  // uncompressible data is probably not useful. This function is used
  // only for the level=0 compression option.
  // NOTE: this function should be optimized to avoid extra copying from
  // window to pending_buf.
  int deflate_stored(int flush){
    // Stored blocks are limited to 0xffff bytes, pending_buf is limited
    // to pending_buf_size, and each stored block has a 5 byte header:

    int max_block_size = 0xffff;
    int max_start;

    if(max_block_size > pending_buf_size - 5) {
      max_block_size = pending_buf_size - 5;
    }

    // Copy as much as possible from input to output:
    while(true){
      // Fill the window as much as possible:
      if(lookahead<=1){
	fill_window();
	if(lookahead==0 && flush==Z_NO_FLUSH) return NeedMore;
	if(lookahead==0) break; // flush the current block
      }

      strstart+=lookahead;
      lookahead=0;

      // Emit a stored block if pending_buf will be full:
      max_start=block_start+max_block_size;
      if(strstart==0|| strstart>=max_start) {
	// strstart == 0 is possible when wraparound on 16-bit machine