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