View Javadoc

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