deflate.java

来自「zlib 算法在j2me 中的应用」· Java 代码 · 共 1,764 行 · 第 1/5 页

    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;
	ins_h=(((ins_h)<<hash_shift)^(window.get((strstart)+(MIN_MATCH-1)) &0xff))&hash_mask;

        //hash_head=(head[ins_h]&0xffff);
        hash_head=(head.get(ins_h)&0xffff);	
//	prev[strstart&w_mask]=head[ins_h];
	prev.set(strstart&w_mask,head.get(ins_h));	
	//head[ins_h]=(short)strstart;
	head.set(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<=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;
	    ins_h=((ins_h<<hash_shift)^(window.get((strstart)+(MIN_MATCH-1)) &0xff))&hash_mask;	    

	    //hash_head=(head[ins_h]&0xffff);
	    hash_head=(head.get(ins_h)&0xffff);
	    //prev[strstart&w_mask]=head[ins_h];
	    prev.set(strstart&w_mask,head.get(ins_h)); 
	    //head[ins_h]=(short)strstart;
	    head.set(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 = window.get(strstart)&0xff;	  

	  //ins_h=(((ins_h)<<hash_shift)^(window[strstart+1]&0xff))&hash_mask;
	  ins_h=(((ins_h)<<hash_shift)^(window.get(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);
	bflush=_tr_tally(0, window.get(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;
	ins_h=(((ins_h)<<hash_shift)^(window.get((strstart)+(MIN_MATCH-1))&0xff)) & hash_mask;	
	//hash_head=(head[ins_h]&0xffff);
	hash_head=(head.get(ins_h)&0xffff);
	//prev[strstart&w_mask]=head[ins_h];
	prev.set(strstart&w_mask,head.get(ins_h));
	//head[ins_h]=(short)strstart;
	head.set(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 <= 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;
	    ins_h=(((ins_h)<<hash_shift)^(window.get((strstart)+(MIN_MATCH-1))&0xff))&hash_mask;	    
	    //hash_head=(head[ins_h]&0xffff);
	    hash_head=(head.get(ins_h)&0xffff);
	    //prev[strstart&w_mask]=head[ins_h];
	    prev.set(strstart&w_mask,head.get(ins_h)); 
	    //head[ins_h]=(short)strstart;
                  head.set(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);
	bflush=_tr_tally(0, window.get(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--;
      }
    }

    if(match_available!=0) {
      //bflush=_tr_tally(0, window[strstart-1]&0xff);
      bflush=_tr_tally(0, window.get(strstart-1)&0xff);      
      match_available = 0;
    }
    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;
  }

  int longest_match(int cur_match){
    int chain_length = max_chain_length; // max hash chain length
    int scan = strstart;                 // current string
    int match;                           // matched string
    int len;                             // length of current match
    int best_len = prev_length;          // best match length so far
    int limit = strstart>(w_size-MIN_LOOKAHEAD) ?
      strstart-(w_size-MIN_LOOKAHEAD) : 0;
    int nice_match=this.nice_match;

    // Stop when cur_match becomes <= limit. To simplify the code,
    // we prevent matches with the string of window index 0.

    int wmask = w_mask;

    int strend = strstart + MAX_MATCH;
    //byte scan_end1 = window[scan+best_len-1];
    //byte scan_end = window[scan+best_len];
    byte scan_end1 = window.get(scan+best_len-1);
    byte scan_end = window.get(scan+best_len);

    // The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
    // It is easy to get rid of this optimization if necessary.

    // Do not waste too much time if we already have a good match:
    if (prev_length >= good_match) {
      chain_length >>= 2;
    }

    // Do not look for matches beyond the end of the input. This is necessary
    // to make deflate deterministic.
    if (nice_match > lookahead) nice_match = lookahead;

    do {
      match = cur_match;

      // Skip to next match if the match length cannot increase
      // or if the match length is less than 2:

      //      if (window[match+best_len]   != scan_end  ||
      //	  window[match+best_len-1] != scan_end1 ||
      //	  window[match]       != window[scan]     ||
      //	  window[++match]     != window[scan+1])      continue;
      
      if (window.get(match+best_len)   != scan_end  ||
	  window.get(match+best_len-1) != scan_end1 ||
	  window.get(match)       != window.get(scan)     ||
	  window.get(++match)     != window.get(scan+1))      continue;

      
      // The check at best_len-1 can be removed because it will be made
      // again later. (This heuristic is not always a win.)
      // It is not necessary to compare scan[2] and match[2] since they
      // are always equal when the other bytes match, given that
      // the hash keys are equal and that HASH_BITS >= 8.

      scan += 2; match++;

      // We check for insufficient lookahead only every 8th comparison;
      // the 256th check will be made at strstart+258.

      do {	
      //} while (window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     window[++scan] == window[++match] &&
	//     scan < strend);
      } while (window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       window.get(++scan) == window.get(++match) &&
	       scan < strend);

      len = MAX_MATCH - (int)(strend - scan);
      scan = strend - MAX_MATCH;

      if(len>best_len) {
	match_start = cur_match;
	best_len = len;
	if (len >= nice_match) break;
	//scan_end1  = window[scan+best_len-1];
	//scan_end   = window[scan+best_len];
	scan_end1  = window.get(scan+best_len-1);
	scan_end   = window.get(scan+best_len);
      }
    //} while ((cur_match = (prev[cur_match & wmask]&0xffff)) > limit
    } while ((cur_match = (prev.get(cur_match & wmask)&0xffff)) > limit	     
	     && --chain_length != 0);

    if (best_len <= lookahead) return best_len;
    return lookahead;
  }
    
  int deflateInit(ZStream strm, int level, int bits){
    return deflateInit2(strm, level, Z_DEFLATED, bits, DEF_MEM_LEVEL,
			Z_DEFAULT_STRATEGY);
  }
  int deflateInit(ZStream strm, int level){
    return deflateInit(strm, level, MAX_WBITS);