tree.java

zlib 算法在j2me 中的应用

      if (bits > max_length){ bits = max_length; overflow++; }
      //tree[n*2+1] = (short)bits;
      tree.set(n*2+1, (short)bits);
      // We overwrite tree[n*2+1] which is no longer needed

      if (n > max_code) continue;  // not a leaf node

      s.bl_count[bits]++;
      xbits = 0;
      if (n >= base) xbits = extra[n-base];
      //f = tree[n*2];
      f = tree.get(n*2);
      s.opt_len += f * (bits + xbits);
      if (stree!=null) s.static_len += f * (stree[n*2+1] + xbits);
    }
    if (overflow == 0) return;

    // This happens for example on obj2 and pic of the Calgary corpus
    // Find the first bit length which could increase:
    do {
      bits = max_length-1;
      while(s.bl_count[bits]==0) bits--;
      s.bl_count[bits]--;      // move one leaf down the tree
      s.bl_count[bits+1]+=2;   // move one overflow item as its brother
      s.bl_count[max_length]--;
      // The brother of the overflow item also moves one step up,
      // but this does not affect bl_count[max_length]
      overflow -= 2;
    }
    while (overflow > 0);

    for (bits = max_length; bits != 0; bits--) {
      n = s.bl_count[bits];
      while (n != 0) {
	m = s.heap[--h];
	if (m > max_code) continue;
	//if (tree[m*2+1] != bits) {
	if (tree.get(m*2+1) != bits) {	  
	  //s.opt_len += ((long)bits - (long)tree[m*2+1])*(long)tree[m*2];
	  s.opt_len += ((long)bits - (long)tree.get(m*2+1))*(long)tree.get(m*2);
	  //tree[m*2+1] = (short)bits;
	  tree.set(m*2+1, (short)bits);
	}
	n--;
      }
    }
  }

  // Construct one Huffman tree and assigns the code bit strings and lengths.
  // Update the total bit length for the current block.
  // IN assertion: the field freq is set for all tree elements.
  // OUT assertions: the fields len and code are set to the optimal bit length
  //     and corresponding code. The length opt_len is updated; static_len is
  //     also updated if stree is not null. The field max_code is set.
  void build_tree(Deflate s){
    short_array tree=dyn_tree;
    short[] stree=stat_desc.static_tree;
    int elems=stat_desc.elems;
    int n, m;          // iterate over heap elements
    int max_code=-1;   // largest code with non zero frequency
    int node;          // new node being created

    // Construct the initial heap, with least frequent element in
    // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
    // heap[0] is not used.
    s.heap_len = 0;
    s.heap_max = HEAP_SIZE;

    for(n=0; n<elems; n++) {
      //if(tree[n*2] != 0) {
      if(tree.get(n*2) != 0) {      
	s.heap[++s.heap_len] = max_code = n;
	//s.depth[n] = 0;
	s.depth.set(n,(byte)0);	
      }
      else{
	//tree[n*2+1] = 0;
	tree.set(n*2+1, (short)0);
      }
    }

    // The pkzip format requires that at least one distance code exists,
    // and that at least one bit should be sent even if there is only one
    // possible code. So to avoid special checks later on we force at least
    // two codes of non zero frequency.
    while (s.heap_len < 2) {
      node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
      //tree[node*2] = 1;
      tree.set(node*2,(short)1);
      //s.depth[node] = 0;
      s.depth.set(node,(byte)0);
      s.opt_len--; if (stree!=null) s.static_len -= stree[node*2+1];
      // node is 0 or 1 so it does not have extra bits
    }
    this.max_code = max_code;

    // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
    // establish sub-heaps of increasing lengths:

    for(n=s.heap_len/2;n>=1; n--)
      s.pqdownheap(tree, n);

    // Construct the Huffman tree by repeatedly combining the least two
    // frequent nodes.

    node=elems;                 // next internal node of the tree
    do{
      // n = node of least frequency
      n=s.heap[1];
      s.heap[1]=s.heap[s.heap_len--];
      s.pqdownheap(tree, 1);
      m=s.heap[1];                // m = node of next least frequency

      s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
      s.heap[--s.heap_max] = m;

      // Create a new node father of n and m
      //tree[node*2] = (short)(tree[n*2] + tree[m*2]);
      tree.set(node*2, (short)(tree.get(n*2) + tree.get(m*2)) );      
      //s.depth[node] = (byte)(Math.max(s.depth[n],s.depth[m])+1);
      s.depth.set(node,  (byte)(Math.max(s.depth.get(n),s.depth.get(m))+1)  );      
      //tree[n*2+1] = tree[m*2+1] = (short)node;
      tree.set(n*2+1,(short)node); tree.set(m*2+1,(short)node);
      
      // and insert the new node in the heap
      s.heap[1] = node++;
      s.pqdownheap(tree, 1);
    }
    while(s.heap_len>=2);

    s.heap[--s.heap_max] = s.heap[1];

    // At this point, the fields freq and dad are set. We can now
    // generate the bit lengths.

    gen_bitlen(s);

    // The field len is now set, we can generate the bit codes
    gen_codes(tree, max_code, s.bl_count);
  }

  // Generate the codes for a given tree and bit counts (which need not be
  // optimal).
  // IN assertion: the array bl_count contains the bit length statistics for
  // the given tree and the field len is set for all tree elements.
  // OUT assertion: the field code is set for all tree elements of non
  //     zero code length.
  static void gen_codes(short_array tree, // the tree to decorate
			int max_code, // largest code with non zero frequency
			short[] bl_count // number of codes at each bit length
			){
    short[] next_code=new short[MAX_BITS+1]; // next code value for each bit length
    short code = 0;            // running code value
    int bits;                  // bit index
    int n;                     // code index

    // The distribution counts are first used to generate the code values
    // without bit reversal.
    for (bits = 1; bits <= MAX_BITS; bits++) {
      next_code[bits] = code = (short)((code + bl_count[bits-1]) << 1);
    }

    // Check that the bit counts in bl_count are consistent. The last code
    // must be all ones.
    //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
    //        "inconsistent bit counts");
    //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));

    for (n = 0;  n <= max_code; n++) {
      //int len = tree[n*2+1];
      int len = tree.get(n*2+1);
      if (len == 0) continue;
      // Now reverse the bits
      //tree[n*2] = (short)(bi_reverse(next_code[len]++, len));
      tree.set(n*2,  (short)(bi_reverse(next_code[len]++, len))  );
    }
  }

  // Reverse the first len bits of a code, using straightforward code (a faster
  // method would use a table)
  // IN assertion: 1 <= len <= 15
  static int bi_reverse(int code, // the value to invert
			int len   // its bit length
			){
    int res = 0;
    do{
      res|=code&1;
      code>>>=1;
      res<<=1;
    } 
    while(--len>0);
    return res>>>1;
  }
}