deflate.java

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

	lookahead = (int)(strstart-max_start);
	strstart = (int)max_start;
      
	flush_block_only(false);
	if(strm.avail_out==0) return NeedMore;

      }

      // Flush if we may have to slide, otherwise block_start may become
      // negative and the data will be gone:
      if(strstart-block_start >= w_size-MIN_LOOKAHEAD) {
	flush_block_only(false);
	if(strm.avail_out==0) return NeedMore;
      }
    }

    flush_block_only(flush == Z_FINISH);
    if(strm.avail_out==0)
      return (flush == Z_FINISH) ? FinishStarted : NeedMore;

    return flush == Z_FINISH ? FinishDone : BlockDone;
  }

  // Send a stored block
  void _tr_stored_block(int buf,        // input block
			int stored_len, // length of input block
			boolean eof     // true if this is the last block for a file
			){
    send_bits((STORED_BLOCK<<1)+(eof?1:0), 3);  // send block type
    copy_block(buf, stored_len, true);          // with header
  }

  // Determine the best encoding for the current block: dynamic trees, static
  // trees or store, and output the encoded block to the zip file.
  void _tr_flush_block(int buf,        // input block, or NULL if too old
		       int stored_len, // length of input block
		       boolean eof     // true if this is the last block for a file
		       ) {
    int opt_lenb, static_lenb;// opt_len and static_len in bytes
    int max_blindex = 0;      // index of last bit length code of non zero freq

    // Build the Huffman trees unless a stored block is forced
    if(level > 0) {
      // Check if the file is ascii or binary
      if(data_type == Z_UNKNOWN) set_data_type();

      // Construct the literal and distance trees
      l_desc.build_tree(this);

      d_desc.build_tree(this);

      // At this point, opt_len and static_len are the total bit lengths of
      // the compressed block data, excluding the tree representations.

      // Build the bit length tree for the above two trees, and get the index
      // in bl_order of the last bit length code to send.
      max_blindex=build_bl_tree();

      // Determine the best encoding. Compute first the block length in bytes
      opt_lenb=(opt_len+3+7)>>>3;
      static_lenb=(static_len+3+7)>>>3;

      if(static_lenb<=opt_lenb) opt_lenb=static_lenb;
    }
    else {
      opt_lenb=static_lenb=stored_len+5; // force a stored block
    }

    if(stored_len+4<=opt_lenb && buf != -1){
      // 4: two words for the lengths
      // The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
      // Otherwise we can't have processed more than WSIZE input bytes since
      // the last block flush, because compression would have been
      // successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
      // transform a block into a stored block.
      _tr_stored_block(buf, stored_len, eof);
    }
    else if(static_lenb == opt_lenb){
      send_bits((STATIC_TREES<<1)+(eof?1:0), 3);
      compress_block(StaticTree.static_ltree, StaticTree.static_dtree);
    }
    else{
      send_bits((DYN_TREES<<1)+(eof?1:0), 3);
      send_all_trees(l_desc.max_code+1, d_desc.max_code+1, max_blindex+1);
      compress_block(dyn_ltree, dyn_dtree);
    }

    // The above check is made mod 2^32, for files larger than 512 MB
    // and uLong implemented on 32 bits.

    init_block();

    if(eof){
      bi_windup();
    }
  }

  // Fill the window when the lookahead becomes insufficient.
  // Updates strstart and lookahead.
  //
  // IN assertion: lookahead < MIN_LOOKAHEAD
  // OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
  //    At least one byte has been read, or avail_in == 0; reads are
  //    performed for at least two bytes (required for the zip translate_eol
  //    option -- not supported here).
  void fill_window(){
    int n, m;
    int p;
    int more;    // Amount of free space at the end of the window.

    do{
      more = (window_size-lookahead-strstart);

      // Deal with !@#$% 64K limit:
      if(more==0 && strstart==0 && lookahead==0){
	more = w_size;
      } 
      else if(more==-1) {
	// Very unlikely, but possible on 16 bit machine if strstart == 0
	// and lookahead == 1 (input done one byte at time)
	more--;

	// If the window is almost full and there is insufficient lookahead,
	// move the upper half to the lower one to make room in the upper half.
      }
      else if(strstart >= w_size+ w_size-MIN_LOOKAHEAD) {
	System.arraycopy(window, w_size, window, 0, w_size);
	match_start-=w_size;
	strstart-=w_size; // we now have strstart >= MAX_DIST
	block_start-=w_size;

	// Slide the hash table (could be avoided with 32 bit values
	// at the expense of memory usage). We slide even when level == 0
	// to keep the hash table consistent if we switch back to level > 0
	// later. (Using level 0 permanently is not an optimal usage of
	// zlib, so we don't care about this pathological case.)

	n = hash_size;
	p=n;
	do {
	  m = (head[--p]&0xffff);
	  head[p]=(m>=w_size ? (short)(m-w_size) : 0);
	}
	while (--n != 0);

	n = w_size;
	p = n;
	do {
	  m = (prev[--p]&0xffff);
	  prev[p] = (m >= w_size ? (short)(m-w_size) : 0);
	  // If n is not on any hash chain, prev[n] is garbage but
	  // its value will never be used.
	}
	while (--n!=0);
	more += w_size;
      }

      if (strm.avail_in == 0) return;

      // If there was no sliding:
      //    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
      //    more == window_size - lookahead - strstart
      // => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
      // => more >= window_size - 2*WSIZE + 2
      // In the BIG_MEM or MMAP case (not yet supported),
      //   window_size == input_size + MIN_LOOKAHEAD  &&
      //   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
      // Otherwise, window_size == 2*WSIZE so more >= 2.
      // If there was sliding, more >= WSIZE. So in all cases, more >= 2.

      n = strm.read_buf(window, strstart + lookahead, more);
      lookahead += n;

      // Initialize the hash value now that we have some input:
      if(lookahead >= MIN_MATCH) {
	ins_h = window[strstart]&0xff;
	ins_h=(((ins_h)<<hash_shift)^(window[strstart+1]&0xff))&hash_mask;
      }
      // If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
      // but this is not important since only literal bytes will be emitted.
    }
    while (lookahead < MIN_LOOKAHEAD && strm.avail_in != 0);
  }

  // Compress as much as possible from the input stream, return the current
  // block state.
  // This function does not perform lazy evaluation of matches and inserts
  // new strings in the dictionary only for unmatched strings or for short
  // matches. It is used only for the fast compression options.
  int deflate_fast(int flush){
//    short hash_head = 0; // head of the hash chain
    int hash_head = 0; // head of the hash chain
    boolean bflush;      // set if current block must be flushed

    while(true){
      // Make sure that we always have enough lookahead, except
      // at the end of the input file. We need MAX_MATCH bytes
      // for the next match, plus MIN_MATCH bytes to insert the
      // string following the next match.
      if(lookahead < MIN_LOOKAHEAD){
	fill_window();
	if(lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH){
	  return NeedMore;
	}
	if(lookahead == 0) break; // flush the current block
      }

      // Insert the string window[strstart .. strstart+2] in the
      // dictionary, and set hash_head to the head of the hash chain:
      if(lookahead >= MIN_MATCH){
	ins_h=(((ins_h)<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff))&hash_mask;

//	prev[strstart&w_mask]=hash_head=head[ins_h];
        hash_head=(head[ins_h]&0xffff);
	prev[strstart&w_mask]=head[ins_h];
	head[ins_h]=(short)strstart;
      }

      // Find the longest match, discarding those <= prev_length.
      // At this point we have always match_length < MIN_MATCH

      if(hash_head!=0L && 
	 ((strstart-hash_head)&0xffff) <= w_size-MIN_LOOKAHEAD
	 ){
	// To simplify the code, we prevent matches with the string
	// of window index 0 (in particular we have to avoid a match
	// of the string with itself at the start of the input file).
	if(strategy != Z_HUFFMAN_ONLY){
	  match_length=longest_match (hash_head);
	}
	// longest_match() sets match_start
      }
      if(match_length>=MIN_MATCH){
	//        check_match(strstart, match_start, match_length);

	bflush=_tr_tally(strstart-match_start, match_length-MIN_MATCH);

	lookahead -= match_length;

	// Insert new strings in the hash table only if the match length
	// is not too large. This saves time but degrades compression.
	if(match_length <= max_lazy_match &&
	   lookahead >= MIN_MATCH) {
	  match_length--; // string at strstart already in hash table
	  do{
	    strstart++;

	    ins_h=((ins_h<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff))&hash_mask;
//	    prev[strstart&w_mask]=hash_head=head[ins_h];
	    hash_head=(head[ins_h]&0xffff);
	    prev[strstart&w_mask]=head[ins_h];
	    head[ins_h]=(short)strstart;

	    // strstart never exceeds WSIZE-MAX_MATCH, so there are
	    // always MIN_MATCH bytes ahead.
	  }
	  while (--match_length != 0);
	  strstart++; 
	}
	else{
	  strstart += match_length;
	  match_length = 0;
	  ins_h = window[strstart]&0xff;

	  ins_h=(((ins_h)<<hash_shift)^(window[strstart+1]&0xff))&hash_mask;
	  // If lookahead < MIN_MATCH, ins_h is garbage, but it does not
	  // matter since it will be recomputed at next deflate call.
	}
      }
      else {
	// No match, output a literal byte

	bflush=_tr_tally(0, window[strstart]&0xff);
	lookahead--;
	strstart++; 
      }
      if (bflush){

	flush_block_only(false);
	if(strm.avail_out==0) return NeedMore;
      }
    }

    flush_block_only(flush == Z_FINISH);
    if(strm.avail_out==0){
      if(flush == Z_FINISH) return FinishStarted;
      else return NeedMore;
    }
    return flush==Z_FINISH ? FinishDone : BlockDone;
  }

  // Same as above, but achieves better compression. We use a lazy
  // evaluation for matches: a match is finally adopted only if there is
  // no better match at the next window position.
  int deflate_slow(int flush){
//    short hash_head = 0;    // head of hash chain
    int hash_head = 0;    // head of hash chain
    boolean bflush;         // set if current block must be flushed

    // Process the input block.
    while(true){
      // Make sure that we always have enough lookahead, except
      // at the end of the input file. We need MAX_MATCH bytes
      // for the next match, plus MIN_MATCH bytes to insert the
      // string following the next match.

      if (lookahead < MIN_LOOKAHEAD) {
	fill_window();
	if(lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
	  return NeedMore;
	}
	if(lookahead == 0) break; // flush the current block
      }

      // Insert the string window[strstart .. strstart+2] in the
      // dictionary, and set hash_head to the head of the hash chain:

      if(lookahead >= MIN_MATCH) {
	ins_h=(((ins_h)<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff)) & hash_mask;
//	prev[strstart&w_mask]=hash_head=head[ins_h];
	hash_head=(head[ins_h]&0xffff);
	prev[strstart&w_mask]=head[ins_h];
	head[ins_h]=(short)strstart;
      }

      // Find the longest match, discarding those <= prev_length.
      prev_length = match_length; prev_match = match_start;
      match_length = MIN_MATCH-1;

      if (hash_head != 0 && prev_length < max_lazy_match &&
	  ((strstart-hash_head)&0xffff) <= w_size-MIN_LOOKAHEAD
	  ){
	// To simplify the code, we prevent matches with the string
	// of window index 0 (in particular we have to avoid a match
	// of the string with itself at the start of the input file).

	if(strategy != Z_HUFFMAN_ONLY) {
	  match_length = longest_match(hash_head);
	}
	// longest_match() sets match_start

	if (match_length <= 5 && (strategy == Z_FILTERED ||
				  (match_length == MIN_MATCH &&
				   strstart - match_start > 4096))) {

	  // If prev_match is also MIN_MATCH, match_start is garbage
	  // but we will ignore the current match anyway.
	  match_length = MIN_MATCH-1;
	}
      }

      // If there was a match at the previous step and the current
      // match is not better, output the previous match:
      if(prev_length >= MIN_MATCH && match_length <= prev_length) {
	int max_insert = strstart + lookahead - MIN_MATCH;
	// Do not insert strings in hash table beyond this.

	//          check_match(strstart-1, prev_match, prev_length);

	bflush=_tr_tally(strstart-1-prev_match, prev_length - MIN_MATCH);

	// Insert in hash table all strings up to the end of the match.
	// strstart-1 and strstart are already inserted. If there is not
	// enough lookahead, the last two strings are not inserted in
	// the hash table.
	lookahead -= prev_length-1;
	prev_length -= 2;
	do{
	  if(++strstart <= max_insert) {
	    ins_h=(((ins_h)<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff))&hash_mask;
	    //prev[strstart&w_mask]=hash_head=head[ins_h];
	    hash_head=(head[ins_h]&0xffff);
	    prev[strstart&w_mask]=head[ins_h];
	    head[ins_h]=(short)strstart;
	  }
	}
	while(--prev_length != 0);
	match_available = 0;
	match_length = MIN_MATCH-1;
	strstart++;

	if (bflush){
	  flush_block_only(false);
	  if(strm.avail_out==0) return NeedMore;
	}
      } else if (match_available!=0) {

	// If there was no match at the previous position, output a
	// single literal. If there was a match but the current match
	// is longer, truncate the previous match to a single literal.

	bflush=_tr_tally(0, window[strstart-1]&0xff);

	if (bflush) {
	  flush_block_only(false);
	}
	strstart++;
	lookahead--;
	if(strm.avail_out == 0) return NeedMore;
      } else {
	// There is no previous match to compare with, wait for
	// the next step to decide.

	match_available = 1;
	strstart++;
	lookahead--;