inftree.java

ziplib for java 是很好的程序。务必读一读。压缩质量好

    int p;                       // pointer into c[], b[], or v[]
    int q;                       // points to current table
    int[] r=new int[3];          // table entry for structure assignment
    int[] u=new int[BMAX];       // table stack
    int w;                       // bits before this table == (l * h)
    int[] x=new int[BMAX+1];     // bit offsets, then code stack
    int xp;                      // pointer into x
    int y;                       // number of dummy codes added
    int z;                       // number of entries in current table

    // 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;
  }

  static 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 r;
    int[] hn = new int[1];          // hufts used in space
    int[] v=new int[19];            // work area for huft_build 

    r = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v);

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

  static 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 r;
    int[] hn = new int[1];           // hufts used in space
    int[] v=new int[288];            // work area for huft_build

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

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

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

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