deflate.java

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

    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++;

	dist=((pending_buf.get(d_buf+lx*2)<<8)&0xff00) | (pending_buf.get(d_buf+lx*2+1)&0xff);
	lc=(pending_buf.get(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];
    last_eob_len = ltree.get(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<7){ bin_freq += dyn_ltree.get(n*2); n++;}  
    //while(n<128){ ascii_freq += dyn_ltree[n*2]; n++;}
    while(n<128){ ascii_freq += dyn_ltree.get(n*2); n++;}
    //while(n<LITERALS){ bin_freq += dyn_ltree[n*2]; n++;}
    while(n<LITERALS){ bin_freq += dyn_ltree.get(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
	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);
	byte_array.Copy(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);
                m = (head.get(--p)&0xffff);	  
                //head[p]=(m>=w_size ? (short)(m-w_size) : 0);
	  head.set(p,  (m>=w_size ? (short)(m-w_size) : 0)  );
	}
	while (--n != 0);

	n = w_size;
	p = n;
	do {
	  // m = (prev[--p]&0xffff);
                m = (prev.get(--p)&0xffff);	  
                //prev[p] = (m >= w_size ? (short)(m-w_size) : 0);
                prev.set(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;
	ins_h = window.get(strstart)&0xff;
	ins_h=(((ins_h)<<hash_shift)^(window.get(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