jaroslav@694: /* -*-mode:java; c-basic-offset:2; indent-tabs-mode:nil -*- */ jaroslav@694: /* jaroslav@694: Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved. jaroslav@694: jaroslav@694: Redistribution and use in source and binary forms, with or without jaroslav@694: modification, are permitted provided that the following conditions are met: jaroslav@694: jaroslav@694: 1. Redistributions of source code must retain the above copyright notice, jaroslav@694: this list of conditions and the following disclaimer. jaroslav@694: jaroslav@694: 2. Redistributions in binary form must reproduce the above copyright jaroslav@694: notice, this list of conditions and the following disclaimer in jaroslav@694: the documentation and/or other materials provided with the distribution. jaroslav@694: jaroslav@694: 3. The names of the authors may not be used to endorse or promote products jaroslav@694: derived from this software without specific prior written permission. jaroslav@694: jaroslav@694: THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, jaroslav@694: INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND jaroslav@694: FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT, jaroslav@694: INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT, jaroslav@694: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT jaroslav@694: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, jaroslav@694: OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF jaroslav@694: LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING jaroslav@694: NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, jaroslav@694: EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. jaroslav@694: */ jaroslav@694: /* jaroslav@694: * This program is based on zlib-1.1.3, so all credit should go authors jaroslav@694: * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu) jaroslav@694: * and contributors of zlib. jaroslav@694: */ jaroslav@694: jaroslav@694: package org.apidesign.bck2brwsr.emul.zip; jaroslav@694: jaroslav@694: import org.apidesign.bck2brwsr.emul.lang.System; jaroslav@694: jaroslav@694: final class InfTree{ jaroslav@694: jaroslav@694: static final private int MANY=1440; jaroslav@694: jaroslav@694: static final private int Z_OK=0; jaroslav@694: static final private int Z_STREAM_END=1; jaroslav@694: static final private int Z_NEED_DICT=2; jaroslav@694: static final private int Z_ERRNO=-1; jaroslav@694: static final private int Z_STREAM_ERROR=-2; jaroslav@694: static final private int Z_DATA_ERROR=-3; jaroslav@694: static final private int Z_MEM_ERROR=-4; jaroslav@694: static final private int Z_BUF_ERROR=-5; jaroslav@694: static final private int Z_VERSION_ERROR=-6; jaroslav@694: jaroslav@694: static final int fixed_bl = 9; jaroslav@694: static final int fixed_bd = 5; jaroslav@694: jaroslav@694: static final int[] fixed_tl = { jaroslav@694: 96,7,256, 0,8,80, 0,8,16, 84,8,115, jaroslav@694: 82,7,31, 0,8,112, 0,8,48, 0,9,192, jaroslav@694: 80,7,10, 0,8,96, 0,8,32, 0,9,160, jaroslav@694: 0,8,0, 0,8,128, 0,8,64, 0,9,224, jaroslav@694: 80,7,6, 0,8,88, 0,8,24, 0,9,144, jaroslav@694: 83,7,59, 0,8,120, 0,8,56, 0,9,208, jaroslav@694: 81,7,17, 0,8,104, 0,8,40, 0,9,176, jaroslav@694: 0,8,8, 0,8,136, 0,8,72, 0,9,240, jaroslav@694: 80,7,4, 0,8,84, 0,8,20, 85,8,227, jaroslav@694: 83,7,43, 0,8,116, 0,8,52, 0,9,200, jaroslav@694: 81,7,13, 0,8,100, 0,8,36, 0,9,168, jaroslav@694: 0,8,4, 0,8,132, 0,8,68, 0,9,232, jaroslav@694: 80,7,8, 0,8,92, 0,8,28, 0,9,152, jaroslav@694: 84,7,83, 0,8,124, 0,8,60, 0,9,216, jaroslav@694: 82,7,23, 0,8,108, 0,8,44, 0,9,184, jaroslav@694: 0,8,12, 0,8,140, 0,8,76, 0,9,248, jaroslav@694: 80,7,3, 0,8,82, 0,8,18, 85,8,163, jaroslav@694: 83,7,35, 0,8,114, 0,8,50, 0,9,196, jaroslav@694: 81,7,11, 0,8,98, 0,8,34, 0,9,164, jaroslav@694: 0,8,2, 0,8,130, 0,8,66, 0,9,228, jaroslav@694: 80,7,7, 0,8,90, 0,8,26, 0,9,148, jaroslav@694: 84,7,67, 0,8,122, 0,8,58, 0,9,212, jaroslav@694: 82,7,19, 0,8,106, 0,8,42, 0,9,180, jaroslav@694: 0,8,10, 0,8,138, 0,8,74, 0,9,244, jaroslav@694: 80,7,5, 0,8,86, 0,8,22, 192,8,0, jaroslav@694: 83,7,51, 0,8,118, 0,8,54, 0,9,204, jaroslav@694: 81,7,15, 0,8,102, 0,8,38, 0,9,172, jaroslav@694: 0,8,6, 0,8,134, 0,8,70, 0,9,236, jaroslav@694: 80,7,9, 0,8,94, 0,8,30, 0,9,156, jaroslav@694: 84,7,99, 0,8,126, 0,8,62, 0,9,220, jaroslav@694: 82,7,27, 0,8,110, 0,8,46, 0,9,188, jaroslav@694: 0,8,14, 0,8,142, 0,8,78, 0,9,252, jaroslav@694: 96,7,256, 0,8,81, 0,8,17, 85,8,131, jaroslav@694: 82,7,31, 0,8,113, 0,8,49, 0,9,194, jaroslav@694: 80,7,10, 0,8,97, 0,8,33, 0,9,162, jaroslav@694: 0,8,1, 0,8,129, 0,8,65, 0,9,226, jaroslav@694: 80,7,6, 0,8,89, 0,8,25, 0,9,146, jaroslav@694: 83,7,59, 0,8,121, 0,8,57, 0,9,210, jaroslav@694: 81,7,17, 0,8,105, 0,8,41, 0,9,178, jaroslav@694: 0,8,9, 0,8,137, 0,8,73, 0,9,242, jaroslav@694: 80,7,4, 0,8,85, 0,8,21, 80,8,258, jaroslav@694: 83,7,43, 0,8,117, 0,8,53, 0,9,202, jaroslav@694: 81,7,13, 0,8,101, 0,8,37, 0,9,170, jaroslav@694: 0,8,5, 0,8,133, 0,8,69, 0,9,234, jaroslav@694: 80,7,8, 0,8,93, 0,8,29, 0,9,154, jaroslav@694: 84,7,83, 0,8,125, 0,8,61, 0,9,218, jaroslav@694: 82,7,23, 0,8,109, 0,8,45, 0,9,186, jaroslav@694: 0,8,13, 0,8,141, 0,8,77, 0,9,250, jaroslav@694: 80,7,3, 0,8,83, 0,8,19, 85,8,195, jaroslav@694: 83,7,35, 0,8,115, 0,8,51, 0,9,198, jaroslav@694: 81,7,11, 0,8,99, 0,8,35, 0,9,166, jaroslav@694: 0,8,3, 0,8,131, 0,8,67, 0,9,230, jaroslav@694: 80,7,7, 0,8,91, 0,8,27, 0,9,150, jaroslav@694: 84,7,67, 0,8,123, 0,8,59, 0,9,214, jaroslav@694: 82,7,19, 0,8,107, 0,8,43, 0,9,182, jaroslav@694: 0,8,11, 0,8,139, 0,8,75, 0,9,246, jaroslav@694: 80,7,5, 0,8,87, 0,8,23, 192,8,0, jaroslav@694: 83,7,51, 0,8,119, 0,8,55, 0,9,206, jaroslav@694: 81,7,15, 0,8,103, 0,8,39, 0,9,174, jaroslav@694: 0,8,7, 0,8,135, 0,8,71, 0,9,238, jaroslav@694: 80,7,9, 0,8,95, 0,8,31, 0,9,158, jaroslav@694: 84,7,99, 0,8,127, 0,8,63, 0,9,222, jaroslav@694: 82,7,27, 0,8,111, 0,8,47, 0,9,190, jaroslav@694: 0,8,15, 0,8,143, 0,8,79, 0,9,254, jaroslav@694: 96,7,256, 0,8,80, 0,8,16, 84,8,115, jaroslav@694: 82,7,31, 0,8,112, 0,8,48, 0,9,193, jaroslav@694: jaroslav@694: 80,7,10, 0,8,96, 0,8,32, 0,9,161, jaroslav@694: 0,8,0, 0,8,128, 0,8,64, 0,9,225, jaroslav@694: 80,7,6, 0,8,88, 0,8,24, 0,9,145, jaroslav@694: 83,7,59, 0,8,120, 0,8,56, 0,9,209, jaroslav@694: 81,7,17, 0,8,104, 0,8,40, 0,9,177, jaroslav@694: 0,8,8, 0,8,136, 0,8,72, 0,9,241, jaroslav@694: 80,7,4, 0,8,84, 0,8,20, 85,8,227, jaroslav@694: 83,7,43, 0,8,116, 0,8,52, 0,9,201, jaroslav@694: 81,7,13, 0,8,100, 0,8,36, 0,9,169, jaroslav@694: 0,8,4, 0,8,132, 0,8,68, 0,9,233, jaroslav@694: 80,7,8, 0,8,92, 0,8,28, 0,9,153, jaroslav@694: 84,7,83, 0,8,124, 0,8,60, 0,9,217, jaroslav@694: 82,7,23, 0,8,108, 0,8,44, 0,9,185, jaroslav@694: 0,8,12, 0,8,140, 0,8,76, 0,9,249, jaroslav@694: 80,7,3, 0,8,82, 0,8,18, 85,8,163, jaroslav@694: 83,7,35, 0,8,114, 0,8,50, 0,9,197, jaroslav@694: 81,7,11, 0,8,98, 0,8,34, 0,9,165, jaroslav@694: 0,8,2, 0,8,130, 0,8,66, 0,9,229, jaroslav@694: 80,7,7, 0,8,90, 0,8,26, 0,9,149, jaroslav@694: 84,7,67, 0,8,122, 0,8,58, 0,9,213, jaroslav@694: 82,7,19, 0,8,106, 0,8,42, 0,9,181, jaroslav@694: 0,8,10, 0,8,138, 0,8,74, 0,9,245, jaroslav@694: 80,7,5, 0,8,86, 0,8,22, 192,8,0, jaroslav@694: 83,7,51, 0,8,118, 0,8,54, 0,9,205, jaroslav@694: 81,7,15, 0,8,102, 0,8,38, 0,9,173, jaroslav@694: 0,8,6, 0,8,134, 0,8,70, 0,9,237, jaroslav@694: 80,7,9, 0,8,94, 0,8,30, 0,9,157, jaroslav@694: 84,7,99, 0,8,126, 0,8,62, 0,9,221, jaroslav@694: 82,7,27, 0,8,110, 0,8,46, 0,9,189, jaroslav@694: 0,8,14, 0,8,142, 0,8,78, 0,9,253, jaroslav@694: 96,7,256, 0,8,81, 0,8,17, 85,8,131, jaroslav@694: 82,7,31, 0,8,113, 0,8,49, 0,9,195, jaroslav@694: 80,7,10, 0,8,97, 0,8,33, 0,9,163, jaroslav@694: 0,8,1, 0,8,129, 0,8,65, 0,9,227, jaroslav@694: 80,7,6, 0,8,89, 0,8,25, 0,9,147, jaroslav@694: 83,7,59, 0,8,121, 0,8,57, 0,9,211, jaroslav@694: 81,7,17, 0,8,105, 0,8,41, 0,9,179, jaroslav@694: 0,8,9, 0,8,137, 0,8,73, 0,9,243, jaroslav@694: 80,7,4, 0,8,85, 0,8,21, 80,8,258, jaroslav@694: 83,7,43, 0,8,117, 0,8,53, 0,9,203, jaroslav@694: 81,7,13, 0,8,101, 0,8,37, 0,9,171, jaroslav@694: 0,8,5, 0,8,133, 0,8,69, 0,9,235, jaroslav@694: 80,7,8, 0,8,93, 0,8,29, 0,9,155, jaroslav@694: 84,7,83, 0,8,125, 0,8,61, 0,9,219, jaroslav@694: 82,7,23, 0,8,109, 0,8,45, 0,9,187, jaroslav@694: 0,8,13, 0,8,141, 0,8,77, 0,9,251, jaroslav@694: 80,7,3, 0,8,83, 0,8,19, 85,8,195, jaroslav@694: 83,7,35, 0,8,115, 0,8,51, 0,9,199, jaroslav@694: 81,7,11, 0,8,99, 0,8,35, 0,9,167, jaroslav@694: 0,8,3, 0,8,131, 0,8,67, 0,9,231, jaroslav@694: 80,7,7, 0,8,91, 0,8,27, 0,9,151, jaroslav@694: 84,7,67, 0,8,123, 0,8,59, 0,9,215, jaroslav@694: 82,7,19, 0,8,107, 0,8,43, 0,9,183, jaroslav@694: 0,8,11, 0,8,139, 0,8,75, 0,9,247, jaroslav@694: 80,7,5, 0,8,87, 0,8,23, 192,8,0, jaroslav@694: 83,7,51, 0,8,119, 0,8,55, 0,9,207, jaroslav@694: 81,7,15, 0,8,103, 0,8,39, 0,9,175, jaroslav@694: 0,8,7, 0,8,135, 0,8,71, 0,9,239, jaroslav@694: 80,7,9, 0,8,95, 0,8,31, 0,9,159, jaroslav@694: 84,7,99, 0,8,127, 0,8,63, 0,9,223, jaroslav@694: 82,7,27, 0,8,111, 0,8,47, 0,9,191, jaroslav@694: 0,8,15, 0,8,143, 0,8,79, 0,9,255 jaroslav@694: }; jaroslav@694: static final int[] fixed_td = { jaroslav@694: 80,5,1, 87,5,257, 83,5,17, 91,5,4097, jaroslav@694: 81,5,5, 89,5,1025, 85,5,65, 93,5,16385, jaroslav@694: 80,5,3, 88,5,513, 84,5,33, 92,5,8193, jaroslav@694: 82,5,9, 90,5,2049, 86,5,129, 192,5,24577, jaroslav@694: 80,5,2, 87,5,385, 83,5,25, 91,5,6145, jaroslav@694: 81,5,7, 89,5,1537, 85,5,97, 93,5,24577, jaroslav@694: 80,5,4, 88,5,769, 84,5,49, 92,5,12289, jaroslav@694: 82,5,13, 90,5,3073, 86,5,193, 192,5,24577 jaroslav@694: }; jaroslav@694: jaroslav@694: // Tables for deflate from PKZIP's appnote.txt. jaroslav@694: static final int[] cplens = { // Copy lengths for literal codes 257..285 jaroslav@694: 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, jaroslav@694: 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0 jaroslav@694: }; jaroslav@694: jaroslav@694: // see note #13 above about 258 jaroslav@694: static final int[] cplext = { // Extra bits for literal codes 257..285 jaroslav@694: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, jaroslav@694: 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112 // 112==invalid jaroslav@694: }; jaroslav@694: jaroslav@694: static final int[] cpdist = { // Copy offsets for distance codes 0..29 jaroslav@694: 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, jaroslav@694: 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, jaroslav@694: 8193, 12289, 16385, 24577 jaroslav@694: }; jaroslav@694: jaroslav@694: static final int[] cpdext = { // Extra bits for distance codes jaroslav@694: 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, jaroslav@694: 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, jaroslav@694: 12, 12, 13, 13}; jaroslav@694: jaroslav@694: // If BMAX needs to be larger than 16, then h and x[] should be uLong. jaroslav@694: static final int BMAX=15; // maximum bit length of any code jaroslav@694: jaroslav@694: int[] hn = null; // hufts used in space jaroslav@694: int[] v = null; // work area for huft_build jaroslav@694: int[] c = null; // bit length count table jaroslav@694: int[] r = null; // table entry for structure assignment jaroslav@694: int[] u = null; // table stack jaroslav@694: int[] x = null; // bit offsets, then code stack jaroslav@694: jaroslav@694: private int huft_build(int[] b, // code lengths in bits (all assumed <= BMAX) jaroslav@694: int bindex, jaroslav@694: int n, // number of codes (assumed <= 288) jaroslav@694: int s, // number of simple-valued codes (0..s-1) jaroslav@694: int[] d, // list of base values for non-simple codes jaroslav@694: int[] e, // list of extra bits for non-simple codes jaroslav@694: int[] t, // result: starting table jaroslav@694: int[] m, // maximum lookup bits, returns actual jaroslav@694: int[] hp,// space for trees jaroslav@694: int[] hn,// hufts used in space jaroslav@694: int[] v // working area: values in order of bit length jaroslav@694: ){ jaroslav@694: // Given a list of code lengths and a maximum table size, make a set of jaroslav@694: // tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR jaroslav@694: // if the given code set is incomplete (the tables are still built in this jaroslav@694: // case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of jaroslav@694: // lengths), or Z_MEM_ERROR if not enough memory. jaroslav@694: jaroslav@694: int a; // counter for codes of length k jaroslav@694: int f; // i repeats in table every f entries jaroslav@694: int g; // maximum code length jaroslav@694: int h; // table level jaroslav@694: int i; // counter, current code jaroslav@694: int j; // counter jaroslav@694: int k; // number of bits in current code jaroslav@694: int l; // bits per table (returned in m) jaroslav@694: int mask; // (1 << w) - 1, to avoid cc -O bug on HP jaroslav@694: int p; // pointer into c[], b[], or v[] jaroslav@694: int q; // points to current table jaroslav@694: int w; // bits before this table == (l * h) jaroslav@694: int xp; // pointer into x jaroslav@694: int y; // number of dummy codes added jaroslav@694: int z; // number of entries in current table jaroslav@694: jaroslav@694: // Generate counts for each bit length jaroslav@694: jaroslav@694: p = 0; i = n; jaroslav@694: do { jaroslav@694: c[b[bindex+p]]++; p++; i--; // assume all entries <= BMAX jaroslav@694: }while(i!=0); jaroslav@694: jaroslav@694: if(c[0] == n){ // null input--all zero length codes jaroslav@694: t[0] = -1; jaroslav@694: m[0] = 0; jaroslav@694: return Z_OK; jaroslav@694: } jaroslav@694: jaroslav@694: // Find minimum and maximum length, bound *m by those jaroslav@694: l = m[0]; jaroslav@694: for (j = 1; j <= BMAX; j++) jaroslav@694: if(c[j]!=0) break; jaroslav@694: k = j; // minimum code length jaroslav@694: if(l < j){ jaroslav@694: l = j; jaroslav@694: } jaroslav@694: for (i = BMAX; i!=0; i--){ jaroslav@694: if(c[i]!=0) break; jaroslav@694: } jaroslav@694: g = i; // maximum code length jaroslav@694: if(l > i){ jaroslav@694: l = i; jaroslav@694: } jaroslav@694: m[0] = l; jaroslav@694: jaroslav@694: // Adjust last length count to fill out codes, if needed jaroslav@694: for (y = 1 << j; j < i; j++, y <<= 1){ jaroslav@694: if ((y -= c[j]) < 0){ jaroslav@694: return Z_DATA_ERROR; jaroslav@694: } jaroslav@694: } jaroslav@694: if ((y -= c[i]) < 0){ jaroslav@694: return Z_DATA_ERROR; jaroslav@694: } jaroslav@694: c[i] += y; jaroslav@694: jaroslav@694: // Generate starting offsets into the value table for each length jaroslav@694: x[1] = j = 0; jaroslav@694: p = 1; xp = 2; jaroslav@694: while (--i!=0) { // note that i == g from above jaroslav@694: x[xp] = (j += c[p]); jaroslav@694: xp++; jaroslav@694: p++; jaroslav@694: } jaroslav@694: jaroslav@694: // Make a table of values in order of bit lengths jaroslav@694: i = 0; p = 0; jaroslav@694: do { jaroslav@694: if ((j = b[bindex+p]) != 0){ jaroslav@694: v[x[j]++] = i; jaroslav@694: } jaroslav@694: p++; jaroslav@694: } jaroslav@694: while (++i < n); jaroslav@694: n = x[g]; // set n to length of v jaroslav@694: jaroslav@694: // Generate the Huffman codes and for each, make the table entries jaroslav@694: x[0] = i = 0; // first Huffman code is zero jaroslav@694: p = 0; // grab values in bit order jaroslav@694: h = -1; // no tables yet--level -1 jaroslav@694: w = -l; // bits decoded == (l * h) jaroslav@694: u[0] = 0; // just to keep compilers happy jaroslav@694: q = 0; // ditto jaroslav@694: z = 0; // ditto jaroslav@694: jaroslav@694: // go through the bit lengths (k already is bits in shortest code) jaroslav@694: for (; k <= g; k++){ jaroslav@694: a = c[k]; jaroslav@694: while (a--!=0){ jaroslav@694: // here i is the Huffman code of length k bits for value *p jaroslav@694: // make tables up to required level jaroslav@694: while (k > w + l){ jaroslav@694: h++; jaroslav@694: w += l; // previous table always l bits jaroslav@694: // compute minimum size table less than or equal to l bits jaroslav@694: z = g - w; jaroslav@694: z = (z > l) ? l : z; // table size upper limit jaroslav@694: if((f=1<<(j=k-w))>a+1){ // try a k-w bit table jaroslav@694: // too few codes for k-w bit table jaroslav@694: f -= a + 1; // deduct codes from patterns left jaroslav@694: xp = k; jaroslav@694: if(j < z){ jaroslav@694: while (++j < z){ // try smaller tables up to z bits jaroslav@694: if((f <<= 1) <= c[++xp]) jaroslav@694: break; // enough codes to use up j bits jaroslav@694: f -= c[xp]; // else deduct codes from patterns jaroslav@694: } jaroslav@694: } jaroslav@694: } jaroslav@694: z = 1 << j; // table entries for j-bit table jaroslav@694: jaroslav@694: // allocate new table jaroslav@694: if (hn[0] + z > MANY){ // (note: doesn't matter for fixed) jaroslav@694: return Z_DATA_ERROR; // overflow of MANY jaroslav@694: } jaroslav@694: u[h] = q = /*hp+*/ hn[0]; // DEBUG jaroslav@694: hn[0] += z; jaroslav@694: jaroslav@694: // connect to last table, if there is one jaroslav@694: if(h!=0){ jaroslav@694: x[h]=i; // save pattern for backing up jaroslav@694: r[0]=(byte)j; // bits in this table jaroslav@694: r[1]=(byte)l; // bits to dump before this table jaroslav@694: j=i>>>(w - l); jaroslav@694: r[2] = (int)(q - u[h-1] - j); // offset to this table jaroslav@694: System.arraycopy(r, 0, hp, (u[h-1]+j)*3, 3); // connect to last table jaroslav@694: } jaroslav@694: else{ jaroslav@694: t[0] = q; // first table is returned result jaroslav@694: } jaroslav@694: } jaroslav@694: jaroslav@694: // set up table entry in r jaroslav@694: r[1] = (byte)(k - w); jaroslav@694: if (p >= n){ jaroslav@694: r[0] = 128 + 64; // out of values--invalid code jaroslav@694: } jaroslav@694: else if (v[p] < s){ jaroslav@694: r[0] = (byte)(v[p] < 256 ? 0 : 32 + 64); // 256 is end-of-block jaroslav@694: r[2] = v[p++]; // simple code is just the value jaroslav@694: } jaroslav@694: else{ jaroslav@694: r[0]=(byte)(e[v[p]-s]+16+64); // non-simple--look up in lists jaroslav@694: r[2]=d[v[p++] - s]; jaroslav@694: } jaroslav@694: jaroslav@694: // fill code-like entries with r jaroslav@694: f=1<<(k-w); jaroslav@694: for (j=i>>>w;j>>= 1){ jaroslav@694: i ^= j; jaroslav@694: } jaroslav@694: i ^= j; jaroslav@694: jaroslav@694: // backup over finished tables jaroslav@694: mask = (1 << w) - 1; // needed on HP, cc -O bug jaroslav@694: while ((i & mask) != x[h]){ jaroslav@694: h--; // don't need to update q jaroslav@694: w -= l; jaroslav@694: mask = (1 << w) - 1; jaroslav@694: } jaroslav@694: } jaroslav@694: } jaroslav@694: // Return Z_BUF_ERROR if we were given an incomplete table jaroslav@694: return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; jaroslav@694: } jaroslav@694: jaroslav@694: int inflate_trees_bits(int[] c, // 19 code lengths jaroslav@694: int[] bb, // bits tree desired/actual depth jaroslav@694: int[] tb, // bits tree result jaroslav@694: int[] hp, // space for trees jaroslav@694: ZStream z // for messages jaroslav@694: ){ jaroslav@694: int result; jaroslav@694: initWorkArea(19); jaroslav@694: hn[0]=0; jaroslav@694: result = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v); jaroslav@694: jaroslav@694: if(result == Z_DATA_ERROR){ jaroslav@694: z.msg = "oversubscribed dynamic bit lengths tree"; jaroslav@694: } jaroslav@694: else if(result == Z_BUF_ERROR || bb[0] == 0){ jaroslav@694: z.msg = "incomplete dynamic bit lengths tree"; jaroslav@694: result = Z_DATA_ERROR; jaroslav@694: } jaroslav@694: return result; jaroslav@694: } jaroslav@694: jaroslav@694: int inflate_trees_dynamic(int nl, // number of literal/length codes jaroslav@694: int nd, // number of distance codes jaroslav@694: int[] c, // that many (total) code lengths jaroslav@694: int[] bl, // literal desired/actual bit depth jaroslav@694: int[] bd, // distance desired/actual bit depth jaroslav@694: int[] tl, // literal/length tree result jaroslav@694: int[] td, // distance tree result jaroslav@694: int[] hp, // space for trees jaroslav@694: ZStream z // for messages jaroslav@694: ){ jaroslav@694: int result; jaroslav@694: jaroslav@694: // build literal/length tree jaroslav@694: initWorkArea(288); jaroslav@694: hn[0]=0; jaroslav@694: result = huft_build(c, 0, nl, 257, cplens, cplext, tl, bl, hp, hn, v); jaroslav@694: if (result != Z_OK || bl[0] == 0){ jaroslav@694: if(result == Z_DATA_ERROR){ jaroslav@694: z.msg = "oversubscribed literal/length tree"; jaroslav@694: } jaroslav@694: else if (result != Z_MEM_ERROR){ jaroslav@694: z.msg = "incomplete literal/length tree"; jaroslav@694: result = Z_DATA_ERROR; jaroslav@694: } jaroslav@694: return result; jaroslav@694: } jaroslav@694: jaroslav@694: // build distance tree jaroslav@694: initWorkArea(288); jaroslav@694: result = huft_build(c, nl, nd, 0, cpdist, cpdext, td, bd, hp, hn, v); jaroslav@694: jaroslav@694: if (result != Z_OK || (bd[0] == 0 && nl > 257)){ jaroslav@694: if (result == Z_DATA_ERROR){ jaroslav@694: z.msg = "oversubscribed distance tree"; jaroslav@694: } jaroslav@694: else if (result == Z_BUF_ERROR) { jaroslav@694: z.msg = "incomplete distance tree"; jaroslav@694: result = Z_DATA_ERROR; jaroslav@694: } jaroslav@694: else if (result != Z_MEM_ERROR){ jaroslav@694: z.msg = "empty distance tree with lengths"; jaroslav@694: result = Z_DATA_ERROR; jaroslav@694: } jaroslav@694: return result; jaroslav@694: } jaroslav@694: jaroslav@694: return Z_OK; jaroslav@694: } jaroslav@694: jaroslav@694: static int inflate_trees_fixed(int[] bl, //literal desired/actual bit depth jaroslav@694: int[] bd, //distance desired/actual bit depth jaroslav@694: int[][] tl,//literal/length tree result jaroslav@694: int[][] td,//distance tree result jaroslav@694: ZStream z //for memory allocation jaroslav@694: ){ jaroslav@694: bl[0]=fixed_bl; jaroslav@694: bd[0]=fixed_bd; jaroslav@694: tl[0]=fixed_tl; jaroslav@694: td[0]=fixed_td; jaroslav@694: return Z_OK; jaroslav@694: } jaroslav@694: jaroslav@694: private void initWorkArea(int vsize){ jaroslav@694: if(hn==null){ jaroslav@694: hn=new int[1]; jaroslav@694: v=new int[vsize]; jaroslav@694: c=new int[BMAX+1]; jaroslav@694: r=new int[3]; jaroslav@694: u=new int[BMAX]; jaroslav@694: x=new int[BMAX+1]; jaroslav@694: } jaroslav@694: if(v.length