inftree.java

java 版本的zlib压缩代码

    // Generate counts for each bit length

    p = 0; i = n;
    do {
      c[b[bindex+p]]++; p++; i--;   // assume all entries <= BMAX
    }while(i!=0);

    if(c[0] == n){                // null input--all zero length codes
      t[0] = -1;
      m[0] = 0;
      return Z_OK;
    }

    // Find minimum and maximum length, bound *m by those
    l = m[0];
    for (j = 1; j <= BMAX; j++)
      if(c[j]!=0) break;
    k = j;                        // minimum code length
    if(l < j){
      l = j;
    }
    for (i = BMAX; i!=0; i--){
      if(c[i]!=0) break;
    }
    g = i;                        // maximum code length
    if(l > i){
      l = i;
    }
    m[0] = l;

    // Adjust last length count to fill out codes, if needed
    for (y = 1 << j; j < i; j++, y <<= 1){
      if ((y -= c[j]) < 0){
        return Z_DATA_ERROR;
      }
    }
    if ((y -= c[i]) < 0){
      return Z_DATA_ERROR;
    }
    c[i] += y;

    // Generate starting offsets into the value table for each length
    x[1] = j = 0;
    p = 1;  xp = 2;
    while (--i!=0) {                 // note that i == g from above
      x[xp] = (j += c[p]);
      xp++;
      p++;
    }

    // Make a table of values in order of bit lengths
    i = 0; p = 0;
    do {
      if ((j = b[bindex+p]) != 0){
        v[x[j]++] = i;
      }
      p++;
    }
    while (++i < n);
    n = x[g];                     // set n to length of v

    // Generate the Huffman codes and for each, make the table entries
    x[0] = i = 0;                 // first Huffman code is zero
    p = 0;                        // grab values in bit order
    h = -1;                       // no tables yet--level -1
    w = -l;                       // bits decoded == (l * h)
    u[0] = 0;                     // just to keep compilers happy
    q = 0;                        // ditto
    z = 0;                        // ditto

    // go through the bit lengths (k already is bits in shortest code)
    for (; k <= g; k++){
      a = c[k];
      while (a--!=0){
	// here i is the Huffman code of length k bits for value *p
	// make tables up to required level
        while (k > w + l){
          h++;
          w += l;                 // previous table always l bits
	  // compute minimum size table less than or equal to l bits
          z = g - w;
          z = (z > l) ? l : z;        // table size upper limit
          if((f=1<<(j=k-w))>a+1){     // try a k-w bit table
                                      // too few codes for k-w bit table
            f -= a + 1;               // deduct codes from patterns left
            xp = k;
            if(j < z){
              while (++j < z){        // try smaller tables up to z bits
                if((f <<= 1) <= c[++xp])
                  break;              // enough codes to use up j bits
                f -= c[xp];           // else deduct codes from patterns
              }
	    }
          }
          z = 1 << j;                 // table entries for j-bit table

	  // allocate new table
          if (hn[0] + z > MANY){       // (note: doesn't matter for fixed)
            return Z_DATA_ERROR;       // overflow of MANY
          }
          u[h] = q = /*hp+*/ hn[0];   // DEBUG
          hn[0] += z;
 
	  // connect to last table, if there is one
	  if(h!=0){
            x[h]=i;           // save pattern for backing up
            r[0]=(byte)j;     // bits in this table
            r[1]=(byte)l;     // bits to dump before this table
            j=i>>>(w - l);
            r[2] = (int)(q - u[h-1] - j);               // offset to this table
            System.arraycopy(r, 0, hp, (u[h-1]+j)*3, 3); // connect to last table
          }
          else{
            t[0] = q;               // first table is returned result
	  }
        }

	// set up table entry in r
        r[1] = (byte)(k - w);
        if (p >= n){
          r[0] = 128 + 64;      // out of values--invalid code
	}
        else if (v[p] < s){
          r[0] = (byte)(v[p] < 256 ? 0 : 32 + 64);  // 256 is end-of-block
          r[2] = v[p++];          // simple code is just the value
        }
        else{
          r[0]=(byte)(e[v[p]-s]+16+64); // non-simple--look up in lists
          r[2]=d[v[p++] - s];
        }

        // fill code-like entries with r
        f=1<<(k-w);
        for (j=i>>>w;j<z;j+=f){
          System.arraycopy(r, 0, hp, (q+j)*3, 3);
	}

	// backwards increment the k-bit code i
        for (j = 1 << (k - 1); (i & j)!=0; j >>>= 1){
          i ^= j;
	}
        i ^= j;

	// backup over finished tables
        mask = (1 << w) - 1;      // needed on HP, cc -O bug
        while ((i & mask) != x[h]){
          h--;                    // don't need to update q
          w -= l;
          mask = (1 << w) - 1;
        }
      }
    }
    // Return Z_BUF_ERROR if we were given an incomplete table
    return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
  }

  int inflate_trees_bits(int[] c,  // 19 code lengths
                         int[] bb, // bits tree desired/actual depth
                         int[] tb, // bits tree result
                         int[] hp, // space for trees
                         ZStream z // for messages
                         ){
    int result;
    initWorkArea(19);
    hn[0]=0;
    result = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v);

    if(result == Z_DATA_ERROR){
      z.msg = "oversubscribed dynamic bit lengths tree";
    }
    else if(result == Z_BUF_ERROR || bb[0] == 0){
      z.msg = "incomplete dynamic bit lengths tree";
      result = Z_DATA_ERROR;
    }
    return result;
  }

  int inflate_trees_dynamic(int nl,   // number of literal/length codes
                            int nd,   // number of distance codes
                            int[] c,  // that many (total) code lengths
                            int[] bl, // literal desired/actual bit depth
                            int[] bd, // distance desired/actual bit depth 
                            int[] tl, // literal/length tree result
                            int[] td, // distance tree result
                            int[] hp, // space for trees
                            ZStream z // for messages
                            ){
    int result;

    // build literal/length tree
    initWorkArea(288);
    hn[0]=0;
    result = huft_build(c, 0, nl, 257, cplens, cplext, tl, bl, hp, hn, v);
    if (result != Z_OK || bl[0] == 0){
      if(result == Z_DATA_ERROR){
        z.msg = "oversubscribed literal/length tree";
      }
      else if (result != Z_MEM_ERROR){
        z.msg = "incomplete literal/length tree";
        result = Z_DATA_ERROR;
      }
      return result;
    }

    // build distance tree
    initWorkArea(288);
    result = huft_build(c, nl, nd, 0, cpdist, cpdext, td, bd, hp, hn, v);

    if (result != Z_OK || (bd[0] == 0 && nl > 257)){
      if (result == Z_DATA_ERROR){
        z.msg = "oversubscribed distance tree";
      }
      else if (result == Z_BUF_ERROR) {
        z.msg = "incomplete distance tree";
        result = Z_DATA_ERROR;
      }
      else if (result != Z_MEM_ERROR){
        z.msg = "empty distance tree with lengths";
        result = Z_DATA_ERROR;
      }
      return result;
    }

    return Z_OK;
  }

  static int inflate_trees_fixed(int[] bl,  //literal desired/actual bit depth
                                 int[] bd,  //distance desired/actual bit depth
                                 int[][] tl,//literal/length tree result
                                 int[][] td,//distance tree result 
                                 ZStream z  //for memory allocation
				 ){
    bl[0]=fixed_bl;
    bd[0]=fixed_bd;
    tl[0]=fixed_tl;
    td[0]=fixed_td;
    return Z_OK;
  }

  private void initWorkArea(int vsize){
    if(hn==null){
      hn=new int[1];
      v=new int[vsize];
      c=new int[BMAX+1];
      r=new int[3];
      u=new int[BMAX];
      x=new int[BMAX+1];
    }
    if(v.length<vsize){ v=new int[vsize]; }
    for(int i=0; i<vsize; i++){v[i]=0;}
    for(int i=0; i<BMAX+1; i++){c[i]=0;}
    for(int i=0; i<3; i++){r[i]=0;}
//  for(int i=0; i<BMAX; i++){u[i]=0;}
    System.arraycopy(c, 0, u, 0, BMAX);
//  for(int i=0; i<BMAX+1; i++){x[i]=0;}
    System.arraycopy(c, 0, x, 0, BMAX+1);
  }
}