deflate.java

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

    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 < L_CODES; i++) dyn_ltree.set(i*2,(short)0);
    //for(int i= 0; i < D_CODES; i++) dyn_dtree[i*2] = 0;
    for(int i= 0; i < D_CODES; i++) dyn_dtree.set(i*2,(short)0);
    //for(int i= 0; i < BL_CODES; i++) bl_tree[i*2] = 0;
    for(int i= 0; i < BL_CODES; i++) bl_tree.set(i*2,(short)0);

    //dyn_ltree[END_BLOCK*2] = 1;
    dyn_ltree.set(END_BLOCK*2,(short)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_array 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 final boolean smaller(short_array  tree, int n, int m, byte_array depth){
    //return (tree[n*2] < tree[m*2] ||          was originally commented
    //            (tree[n*2] == tree[m*2] && depth[n] <= depth[m]));   was originally commented
    
    //return (tree[n*2] < tree[m*2] || (tree[n*2] == tree[m*2] && depth.get(n)<= depth.get(m)));
    return (tree.get(n*2) < tree.get(m*2) || (tree.get(n*2) == tree.get(m*2) && depth.get(n)<= depth.get(m)));
  }

  // Scan a literal or distance tree to determine the frequencies of the codes
  // in the bit length tree.
  void scan_tree (short_array 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 nextlen = tree.get(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
    tree.set((max_code+1)*2+1, (short)0xffff); // guard    

    for(n = 0; n <= max_code; n++) {
      //curlen = nextlen; nextlen = tree[(n+1)*2+1];
      curlen = nextlen; nextlen = tree.get((n+1)*2+1);
      if(++count < max_count && curlen == nextlen) {
	continue;
      }
      else if(count < min_count) {
	//bl_tree[curlen*2] += count;
	bl_tree.set(curlen*2,  (short)(bl_tree.get(curlen*2)+count)  );
      }
      else if(curlen != 0) {
	//if(curlen != prevlen) bl_tree[curlen*2]++;
	if(curlen != prevlen) bl_tree.set(curlen*2, (short)(bl_tree.get(curlen*2)+1)  );	
	//bl_tree[REP_3_6*2]++;
	bl_tree.set(REP_3_6*2, (short)(bl_tree.get(REP_3_6*2)+1) );
      }
      else if(count <= 10) {
	//bl_tree[REPZ_3_10*2]++;
              bl_tree.set(REPZ_3_10*2,  (short)(bl_tree.get(REPZ_3_10*2)+1)  );
      }
      else{
	//bl_tree[REPZ_11_138*2]++;
              bl_tree.set(REPZ_11_138*2,(short)(bl_tree.get(REPZ_11_138*2)+1)  );
      }
      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;
      if (bl_tree.get(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_bits(bl_tree.get(Tree.bl_order[rank]*2+1), 3);      
    }//for
    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_array 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 nextlen = tree.get(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];
      curlen = nextlen; nextlen = tree.get((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_array p, int start, int len){
    //System.arraycopy(p, start, pending_buf, pending, len);
    byte_array.Copy(p, start, pending_buf, pending, len);
    pending+=len;
  }

  final void put_byte(byte c){
    //pending_buf[pending++]=c;
    pending_buf.set(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_AccessibleArray tree){
    //send_bits((tree[c*2]&0xffff), (tree[c*2+1]&0xffff));
    send_bits((tree.get(c*2)&0xffff), (tree.get(c*2+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++;

    pending_buf.set(d_buf+last_lit*2, (byte)(dist>>>8));
    pending_buf.set(d_buf+last_lit*2+1, (byte)dist);
    pending_buf.set(l_buf+last_lit, (byte)lc); last_lit++;

    if (dist == 0) {
      // lc is the unmatched char
      //dyn_ltree[lc*2]++;
      dyn_ltree.set(lc*2, (short)((dyn_ltree.get(lc*2))+1)  );
    } 
    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_ltree.set( (Tree._length_code[lc]+LITERALS+1)*2,  (short)(dyn_ltree.get((Tree._length_code[lc]+LITERALS+1)*2)+1)  );
      //dyn_dtree[Tree.d_code(dist)*2]++;
      dyn_dtree.set(Tree.d_code(dist)*2, (short)(dyn_dtree.get(Tree.d_code(dist)*2)+1) );
    }

    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 += (int)dyn_dtree.get(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_AccessibleArray ltree, short_AccessibleArray dtree){
    int  dist;      // distance of matched string