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