View Javadoc

1   /*
2    * Copyright 2009 Red Hat, Inc.
3    *
4    * Red Hat licenses this file to you under the Apache License, version 2.0
5    * (the "License"); you may not use this file except in compliance with the
6    * License.  You may obtain a copy of the License at:
7    *
8    *    http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  /*
17  Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
18  
19  Redistribution and use in source and binary forms, with or without
20  modification, are permitted provided that the following conditions are met:
21  
22    1. Redistributions of source code must retain the above copyright notice,
23       this list of conditions and the following disclaimer.
24  
25    2. Redistributions in binary form must reproduce the above copyright
26       notice, this list of conditions and the following disclaimer in
27       the documentation and/or other materials provided with the distribution.
28  
29    3. The names of the authors may not be used to endorse or promote products
30       derived from this software without specific prior written permission.
31  
32  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
33  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
34  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
35  INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
36  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
37  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
38  OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
39  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
40  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
41  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42   */
43  /*
44   * This program is based on zlib-1.1.3, so all credit should go authors
45   * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
46   * and contributors of zlib.
47   */
48  
49  package org.jboss.netty.util.internal.jzlib;
50  
51  final class InfTree {
52  
53      static final int fixed_bl = 9;
54      static final int fixed_bd = 5;
55  
56      static final int[] fixed_tl = { 96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115,
57              82, 7, 31, 0, 8, 112, 0, 8, 48, 0, 9, 192, 80, 7, 10, 0, 8, 96, 0,
58              8, 32, 0, 9, 160, 0, 8, 0, 0, 8, 128, 0, 8, 64, 0, 9, 224, 80, 7,
59              6, 0, 8, 88, 0, 8, 24, 0, 9, 144, 83, 7, 59, 0, 8, 120, 0, 8, 56,
60              0, 9, 208, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0, 9, 176, 0, 8, 8, 0,
61              8, 136, 0, 8, 72, 0, 9, 240, 80, 7, 4, 0, 8, 84, 0, 8, 20, 85, 8,
62              227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9, 200, 81, 7, 13, 0, 8,
63              100, 0, 8, 36, 0, 9, 168, 0, 8, 4, 0, 8, 132, 0, 8, 68, 0, 9, 232,
64              80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 152, 84, 7, 83, 0, 8, 124, 0,
65              8, 60, 0, 9, 216, 82, 7, 23, 0, 8, 108, 0, 8, 44, 0, 9, 184, 0, 8,
66              12, 0, 8, 140, 0, 8, 76, 0, 9, 248, 80, 7, 3, 0, 8, 82, 0, 8, 18,
67              85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0, 9, 196, 81, 7, 11,
68              0, 8, 98, 0, 8, 34, 0, 9, 164, 0, 8, 2, 0, 8, 130, 0, 8, 66, 0, 9,
69              228, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 148, 84, 7, 67, 0, 8, 122,
70              0, 8, 58, 0, 9, 212, 82, 7, 19, 0, 8, 106, 0, 8, 42, 0, 9, 180, 0,
71              8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 244, 80, 7, 5, 0, 8, 86, 0, 8,
72              22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8, 54, 0, 9, 204, 81, 7,
73              15, 0, 8, 102, 0, 8, 38, 0, 9, 172, 0, 8, 6, 0, 8, 134, 0, 8, 70,
74              0, 9, 236, 80, 7, 9, 0, 8, 94, 0, 8, 30, 0, 9, 156, 84, 7, 99, 0,
75              8, 126, 0, 8, 62, 0, 9, 220, 82, 7, 27, 0, 8, 110, 0, 8, 46, 0, 9,
76              188, 0, 8, 14, 0, 8, 142, 0, 8, 78, 0, 9, 252, 96, 7, 256, 0, 8,
77              81, 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113, 0, 8, 49, 0, 9,
78              194, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 162, 0, 8, 1, 0, 8, 129,
79              0, 8, 65, 0, 9, 226, 80, 7, 6, 0, 8, 89, 0, 8, 25, 0, 9, 146, 83,
80              7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 210, 81, 7, 17, 0, 8, 105, 0, 8,
81              41, 0, 9, 178, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9, 242, 80, 7, 4,
82              0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8, 117, 0, 8, 53, 0,
83              9, 202, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0, 9, 170, 0, 8, 5, 0, 8,
84              133, 0, 8, 69, 0, 9, 234, 80, 7, 8, 0, 8, 93, 0, 8, 29, 0, 9, 154,
85              84, 7, 83, 0, 8, 125, 0, 8, 61, 0, 9, 218, 82, 7, 23, 0, 8, 109, 0,
86              8, 45, 0, 9, 186, 0, 8, 13, 0, 8, 141, 0, 8, 77, 0, 9, 250, 80, 7,
87              3, 0, 8, 83, 0, 8, 19, 85, 8, 195, 83, 7, 35, 0, 8, 115, 0, 8, 51,
88              0, 9, 198, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0, 9, 166, 0, 8, 3, 0, 8,
89              131, 0, 8, 67, 0, 9, 230, 80, 7, 7, 0, 8, 91, 0, 8, 27, 0, 9, 150,
90              84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 214, 82, 7, 19, 0, 8, 107, 0,
91              8, 43, 0, 9, 182, 0, 8, 11, 0, 8, 139, 0, 8, 75, 0, 9, 246, 80, 7,
92              5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7, 51, 0, 8, 119, 0, 8, 55,
93              0, 9, 206, 81, 7, 15, 0, 8, 103, 0, 8, 39, 0, 9, 174, 0, 8, 7, 0,
94              8, 135, 0, 8, 71, 0, 9, 238, 80, 7, 9, 0, 8, 95, 0, 8, 31, 0, 9,
95              158, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 222, 82, 7, 27, 0, 8,
96              111, 0, 8, 47, 0, 9, 190, 0, 8, 15, 0, 8, 143, 0, 8, 79, 0, 9, 254,
97              96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115, 82, 7, 31, 0, 8, 112,
98              0, 8, 48, 0, 9, 193,
99              80, 7, 10, 0, 8, 96, 0, 8, 32, 0, 9, 161, 0, 8, 0, 0, 8, 128, 0, 8,
100             64, 0, 9, 225, 80, 7, 6, 0, 8, 88, 0, 8, 24, 0, 9, 145, 83, 7, 59,
101             0, 8, 120, 0, 8, 56, 0, 9, 209, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0,
102             9, 177, 0, 8, 8, 0, 8, 136, 0, 8, 72, 0, 9, 241, 80, 7, 4, 0, 8,
103             84, 0, 8, 20, 85, 8, 227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9,
104             201, 81, 7, 13, 0, 8, 100, 0, 8, 36, 0, 9, 169, 0, 8, 4, 0, 8, 132,
105             0, 8, 68, 0, 9, 233, 80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 153, 84,
106             7, 83, 0, 8, 124, 0, 8, 60, 0, 9, 217, 82, 7, 23, 0, 8, 108, 0, 8,
107             44, 0, 9, 185, 0, 8, 12, 0, 8, 140, 0, 8, 76, 0, 9, 249, 80, 7, 3,
108             0, 8, 82, 0, 8, 18, 85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0,
109             9, 197, 81, 7, 11, 0, 8, 98, 0, 8, 34, 0, 9, 165, 0, 8, 2, 0, 8,
110             130, 0, 8, 66, 0, 9, 229, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 149,
111             84, 7, 67, 0, 8, 122, 0, 8, 58, 0, 9, 213, 82, 7, 19, 0, 8, 106, 0,
112             8, 42, 0, 9, 181, 0, 8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 245, 80, 7,
113             5, 0, 8, 86, 0, 8, 22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8, 54,
114             0, 9, 205, 81, 7, 15, 0, 8, 102, 0, 8, 38, 0, 9, 173, 0, 8, 6, 0,
115             8, 134, 0, 8, 70, 0, 9, 237, 80, 7, 9, 0, 8, 94, 0, 8, 30, 0, 9,
116             157, 84, 7, 99, 0, 8, 126, 0, 8, 62, 0, 9, 221, 82, 7, 27, 0, 8,
117             110, 0, 8, 46, 0, 9, 189, 0, 8, 14, 0, 8, 142, 0, 8, 78, 0, 9, 253,
118             96, 7, 256, 0, 8, 81, 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113,
119             0, 8, 49, 0, 9, 195, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 163, 0,
120             8, 1, 0, 8, 129, 0, 8, 65, 0, 9, 227, 80, 7, 6, 0, 8, 89, 0, 8, 25,
121             0, 9, 147, 83, 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 211, 81, 7, 17, 0,
122             8, 105, 0, 8, 41, 0, 9, 179, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9,
123             243, 80, 7, 4, 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8,
124             117, 0, 8, 53, 0, 9, 203, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0, 9,
125             171, 0, 8, 5, 0, 8, 133, 0, 8, 69, 0, 9, 235, 80, 7, 8, 0, 8, 93,
126             0, 8, 29, 0, 9, 155, 84, 7, 83, 0, 8, 125, 0, 8, 61, 0, 9, 219, 82,
127             7, 23, 0, 8, 109, 0, 8, 45, 0, 9, 187, 0, 8, 13, 0, 8, 141, 0, 8,
128             77, 0, 9, 251, 80, 7, 3, 0, 8, 83, 0, 8, 19, 85, 8, 195, 83, 7, 35,
129             0, 8, 115, 0, 8, 51, 0, 9, 199, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0,
130             9, 167, 0, 8, 3, 0, 8, 131, 0, 8, 67, 0, 9, 231, 80, 7, 7, 0, 8,
131             91, 0, 8, 27, 0, 9, 151, 84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 215,
132             82, 7, 19, 0, 8, 107, 0, 8, 43, 0, 9, 183, 0, 8, 11, 0, 8, 139, 0,
133             8, 75, 0, 9, 247, 80, 7, 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7,
134             51, 0, 8, 119, 0, 8, 55, 0, 9, 207, 81, 7, 15, 0, 8, 103, 0, 8, 39,
135             0, 9, 175, 0, 8, 7, 0, 8, 135, 0, 8, 71, 0, 9, 239, 80, 7, 9, 0, 8,
136             95, 0, 8, 31, 0, 9, 159, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 223,
137             82, 7, 27, 0, 8, 111, 0, 8, 47, 0, 9, 191, 0, 8, 15, 0, 8, 143, 0,
138             8, 79, 0, 9, 255 };
139 
140     static final int[] fixed_td = { 80, 5, 1, 87, 5, 257, 83, 5, 17, 91, 5,
141             4097, 81, 5, 5, 89, 5, 1025, 85, 5, 65, 93, 5, 16385, 80, 5, 3, 88,
142             5, 513, 84, 5, 33, 92, 5, 8193, 82, 5, 9, 90, 5, 2049, 86, 5, 129,
143             192, 5, 24577, 80, 5, 2, 87, 5, 385, 83, 5, 25, 91, 5, 6145, 81, 5,
144             7, 89, 5, 1537, 85, 5, 97, 93, 5, 24577, 80, 5, 4, 88, 5, 769, 84,
145             5, 49, 92, 5, 12289, 82, 5, 13, 90, 5, 3073, 86, 5, 193, 192, 5,
146             24577 };
147 
148     // Tables for deflate from PKZIP's appnote.txt.
149     static final int[] cplens = { // Copy lengths for literal codes 257..285
150     3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
151             67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0 };
152 
153     // see note #13 above about 258
154     static final int[] cplext = { // Extra bits for literal codes 257..285
155     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5,
156             5, 5, 5, 0, 112, 112 // 112==invalid
157     };
158 
159     static final int[] cpdist = { // Copy offsets for distance codes 0..29
160     1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
161             769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 };
162 
163     static final int[] cpdext = { // Extra bits for distance codes
164     0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
165             11, 11, 12, 12, 13, 13 };
166 
167     // If BMAX needs to be larger than 16, then h and x[] should be uLong.
168     static final int BMAX = 15; // maximum bit length of any code
169 
170     private int[] hn; // hufts used in space
171     private int[] v;  // work area for huft_build
172     private int[] c;  // bit length count table
173     private int[] r;  // table entry for structure assignment
174     private int[] u;  // table stack
175     private int[] x;  // bit offsets, then code stack
176 
177     private int huft_build(int[] b, // code lengths in bits (all assumed <= BMAX)
178             int bindex, int n, // number of codes (assumed <= 288)
179             int s, // number of simple-valued codes (0..s-1)
180             int[] d, // list of base values for non-simple codes
181             int[] e, // list of extra bits for non-simple codes
182             int[] t, // result: starting table
183             int[] m, // maximum lookup bits, returns actual
184             int[] hp,// space for trees
185             int[] hn,// hufts used in space
186             int[] v // working area: values in order of bit length
187     ) {
188         // Given a list of code lengths and a maximum table size, make a set of
189         // tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
190         // if the given code set is incomplete (the tables are still built in this
191         // case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
192         // lengths), or Z_MEM_ERROR if not enough memory.
193 
194         int a; // counter for codes of length k
195         int f; // i repeats in table every f entries
196         int g; // maximum code length
197         int h; // table level
198         int i; // counter, current code
199         int j; // counter
200         int k; // number of bits in current code
201         int l; // bits per table (returned in m)
202         int mask; // (1 << w) - 1, to avoid cc -O bug on HP
203         int p; // pointer into c[], b[], or v[]
204         int q; // points to current table
205         int w; // bits before this table == (l * h)
206         int xp; // pointer into x
207         int y; // number of dummy codes added
208         int z; // number of entries in current table
209 
210         // Generate counts for each bit length
211 
212         p = 0;
213         i = n;
214         do {
215             c[b[bindex + p]] ++;
216             p ++;
217             i --; // assume all entries <= BMAX
218         } while (i != 0);
219 
220         if (c[0] == n) { // null input--all zero length codes
221             t[0] = -1;
222             m[0] = 0;
223             return JZlib.Z_OK;
224         }
225 
226         // Find minimum and maximum length, bound *m by those
227         l = m[0];
228         for (j = 1; j <= BMAX; j ++) {
229             if (c[j] != 0) {
230                 break;
231             }
232         }
233         k = j; // minimum code length
234         if (l < j) {
235             l = j;
236         }
237         for (i = BMAX; i != 0; i --) {
238             if (c[i] != 0) {
239                 break;
240             }
241         }
242         g = i; // maximum code length
243         if (l > i) {
244             l = i;
245         }
246         m[0] = l;
247 
248         // Adjust last length count to fill out codes, if needed
249         for (y = 1 << j; j < i; j ++, y <<= 1) {
250             if ((y -= c[j]) < 0) {
251                 return JZlib.Z_DATA_ERROR;
252             }
253         }
254         if ((y -= c[i]) < 0) {
255             return JZlib.Z_DATA_ERROR;
256         }
257         c[i] += y;
258 
259         // Generate starting offsets into the value table for each length
260         x[1] = j = 0;
261         p = 1;
262         xp = 2;
263         while (-- i != 0) { // note that i == g from above
264             x[xp] = j += c[p];
265             xp ++;
266             p ++;
267         }
268 
269         // Make a table of values in order of bit lengths
270         i = 0;
271         p = 0;
272         do {
273             if ((j = b[bindex + p]) != 0) {
274                 v[x[j] ++] = i;
275             }
276             p ++;
277         } while (++ i < n);
278         n = x[g]; // set n to length of v
279 
280         // Generate the Huffman codes and for each, make the table entries
281         x[0] = i = 0; // first Huffman code is zero
282         p = 0; // grab values in bit order
283         h = -1; // no tables yet--level -1
284         w = -l; // bits decoded == (l * h)
285         u[0] = 0; // just to keep compilers happy
286         q = 0; // ditto
287         z = 0; // ditto
288 
289         // go through the bit lengths (k already is bits in shortest code)
290         for (; k <= g; k ++) {
291             a = c[k];
292             while (a -- != 0) {
293                 // here i is the Huffman code of length k bits for value *p
294                 // make tables up to required level
295                 while (k > w + l) {
296                     h ++;
297                     w += l; // previous table always l bits
298                     // compute minimum size table less than or equal to l bits
299                     z = g - w;
300                     z = z > l? l : z; // table size upper limit
301                     if ((f = 1 << (j = k - w)) > a + 1) { // try a k-w bit table
302                         // too few codes for k-w bit table
303                         f -= a + 1; // deduct codes from patterns left
304                         xp = k;
305                         if (j < z) {
306                             while (++ j < z) { // try smaller tables up to z bits
307                                 if ((f <<= 1) <= c[++ xp]) {
308                                     break; // enough codes to use up j bits
309                                 }
310                                 f -= c[xp]; // else deduct codes from patterns
311                             }
312                         }
313                     }
314                     z = 1 << j; // table entries for j-bit table
315 
316                     // allocate new table
317                     if (hn[0] + z > JZlib.MANY) { // (note: doesn't matter for fixed)
318                         return JZlib.Z_DATA_ERROR; // overflow of MANY
319                     }
320                     u[h] = q = /*hp+*/hn[0]; // DEBUG
321                     hn[0] += z;
322 
323                     // connect to last table, if there is one
324                     if (h != 0) {
325                         x[h] = i; // save pattern for backing up
326                         r[0] = (byte) j; // bits in this table
327                         r[1] = (byte) l; // bits to dump before this table
328                         j = i >>> w - l;
329                         r[2] = q - u[h - 1] - j; // offset to this table
330                         System.arraycopy(r, 0, hp, (u[h - 1] + j) * 3, 3); // connect to last table
331                     } else {
332                         t[0] = q; // first table is returned result
333                     }
334                 }
335 
336                 // set up table entry in r
337                 r[1] = (byte) (k - w);
338                 if (p >= n) {
339                     r[0] = 128 + 64; // out of values--invalid code
340                 } else if (v[p] < s) {
341                     r[0] = (byte) (v[p] < 256? 0 : 32 + 64); // 256 is end-of-block
342                     r[2] = v[p ++]; // simple code is just the value
343                 } else {
344                     r[0] = (byte) (e[v[p] - s] + 16 + 64); // non-simple--look up in lists
345                     r[2] = d[v[p ++] - s];
346                 }
347 
348                 // fill code-like entries with r
349                 f = 1 << k - w;
350                 for (j = i >>> w; j < z; j += f) {
351                     System.arraycopy(r, 0, hp, (q + j) * 3, 3);
352                 }
353 
354                 // backwards increment the k-bit code i
355                 for (j = 1 << k - 1; (i & j) != 0; j >>>= 1) {
356                     i ^= j;
357                 }
358                 i ^= j;
359 
360                 // backup over finished tables
361                 mask = (1 << w) - 1; // needed on HP, cc -O bug
362                 while ((i & mask) != x[h]) {
363                     h --; // don't need to update q
364                     w -= l;
365                     mask = (1 << w) - 1;
366                 }
367             }
368         }
369         // Return Z_BUF_ERROR if we were given an incomplete table
370         return y != 0 && g != 1? JZlib.Z_BUF_ERROR : JZlib.Z_OK;
371     }
372 
373     int inflate_trees_bits(int[] c, // 19 code lengths
374             int[] bb, // bits tree desired/actual depth
375             int[] tb, // bits tree result
376             int[] hp, // space for trees
377             ZStream z // for messages
378     ) {
379         int result;
380         initWorkArea(19);
381         hn[0] = 0;
382         result = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v);
383 
384         if (result == JZlib.Z_DATA_ERROR) {
385             z.msg = "oversubscribed dynamic bit lengths tree";
386         } else if (result == JZlib.Z_BUF_ERROR || bb[0] == 0) {
387             z.msg = "incomplete dynamic bit lengths tree";
388             result = JZlib.Z_DATA_ERROR;
389         }
390         return result;
391     }
392 
393     int inflate_trees_dynamic(int nl, // number of literal/length codes
394             int nd, // number of distance codes
395             int[] c, // that many (total) code lengths
396             int[] bl, // literal desired/actual bit depth
397             int[] bd, // distance desired/actual bit depth
398             int[] tl, // literal/length tree result
399             int[] td, // distance tree result
400             int[] hp, // space for trees
401             ZStream z // for messages
402     ) {
403         int result;
404 
405         // build literal/length tree
406         initWorkArea(288);
407         hn[0] = 0;
408         result = huft_build(c, 0, nl, 257, cplens, cplext, tl, bl, hp, hn, v);
409         if (result != JZlib.Z_OK || bl[0] == 0) {
410             if (result == JZlib.Z_DATA_ERROR) {
411                 z.msg = "oversubscribed literal/length tree";
412             } else if (result != JZlib.Z_MEM_ERROR) {
413                 z.msg = "incomplete literal/length tree";
414                 result = JZlib.Z_DATA_ERROR;
415             }
416             return result;
417         }
418 
419         // build distance tree
420         initWorkArea(288);
421         result = huft_build(c, nl, nd, 0, cpdist, cpdext, td, bd, hp, hn, v);
422 
423         if (result != JZlib.Z_OK || bd[0] == 0 && nl > 257) {
424             if (result == JZlib.Z_DATA_ERROR) {
425                 z.msg = "oversubscribed distance tree";
426             } else if (result == JZlib.Z_BUF_ERROR) {
427                 z.msg = "incomplete distance tree";
428                 result = JZlib.Z_DATA_ERROR;
429             } else if (result != JZlib.Z_MEM_ERROR) {
430                 z.msg = "empty distance tree with lengths";
431                 result = JZlib.Z_DATA_ERROR;
432             }
433             return result;
434         }
435 
436         return JZlib.Z_OK;
437     }
438 
439     static int inflate_trees_fixed(int[] bl, //literal desired/actual bit depth
440             int[] bd, //distance desired/actual bit depth
441             int[][] tl,//literal/length tree result
442             int[][] td //distance tree result
443     ) {
444         bl[0] = fixed_bl;
445         bd[0] = fixed_bd;
446         tl[0] = fixed_tl;
447         td[0] = fixed_td;
448         return JZlib.Z_OK;
449     }
450 
451     private void initWorkArea(int vsize) {
452         if (hn == null) {
453             hn = new int[1];
454             v = new int[vsize];
455             c = new int[BMAX + 1];
456             r = new int[3];
457             u = new int[BMAX];
458             x = new int[BMAX + 1];
459         } else {
460             if (v.length < vsize) {
461                 v = new int[vsize];
462             } else {
463                 for (int i = 0; i < vsize; i ++) {
464                     v[i] = 0;
465                 }
466             }
467             for (int i = 0; i < BMAX + 1; i ++) {
468                 c[i] = 0;
469             }
470             for (int i = 0; i < 3; i ++) {
471                 r[i] = 0;
472             }
473             //  for(int i=0; i<BMAX; i++){u[i]=0;}
474             System.arraycopy(c, 0, u, 0, BMAX);
475             //  for(int i=0; i<BMAX+1; i++){x[i]=0;}
476             System.arraycopy(c, 0, x, 0, BMAX + 1);
477         }
478     }
479 }