|
1 /* inflate.c -- Not copyrighted 1992 by Mark Adler |
|
2 version c10p1, 10 January 1993 */ |
|
3 |
|
4 /* You can do whatever you like with this source file, though I would |
|
5 prefer that if you modify it and redistribute it that you include |
|
6 comments to that effect with your name and the date. Thank you. |
|
7 [The history has been moved to the file ChangeLog.] |
|
8 */ |
|
9 |
|
10 /* |
|
11 Inflate deflated (PKZIP's method 8 compressed) data. The compression |
|
12 method searches for as much of the current string of bytes (up to a |
|
13 length of 258) in the previous 32K bytes. If it doesn't find any |
|
14 matches (of at least length 3), it codes the next byte. Otherwise, it |
|
15 codes the length of the matched string and its distance backwards from |
|
16 the current position. There is a single Huffman code that codes both |
|
17 single bytes (called "literals") and match lengths. A second Huffman |
|
18 code codes the distance information, which follows a length code. Each |
|
19 length or distance code actually represents a base value and a number |
|
20 of "extra" (sometimes zero) bits to get to add to the base value. At |
|
21 the end of each deflated block is a special end-of-block (EOB) literal/ |
|
22 length code. The decoding process is basically: get a literal/length |
|
23 code; if EOB then done; if a literal, emit the decoded byte; if a |
|
24 length then get the distance and emit the referred-to bytes from the |
|
25 sliding window of previously emitted data. |
|
26 |
|
27 There are (currently) three kinds of inflate blocks: stored, fixed, and |
|
28 dynamic. The compressor deals with some chunk of data at a time, and |
|
29 decides which method to use on a chunk-by-chunk basis. A chunk might |
|
30 typically be 32K or 64K. If the chunk is uncompressible, then the |
|
31 "stored" method is used. In this case, the bytes are simply stored as |
|
32 is, eight bits per byte, with none of the above coding. The bytes are |
|
33 preceded by a count, since there is no longer an EOB code. |
|
34 |
|
35 If the data is compressible, then either the fixed or dynamic methods |
|
36 are used. In the dynamic method, the compressed data is preceded by |
|
37 an encoding of the literal/length and distance Huffman codes that are |
|
38 to be used to decode this block. The representation is itself Huffman |
|
39 coded, and so is preceded by a description of that code. These code |
|
40 descriptions take up a little space, and so for small blocks, there is |
|
41 a predefined set of codes, called the fixed codes. The fixed method is |
|
42 used if the block codes up smaller that way (usually for quite small |
|
43 chunks), otherwise the dynamic method is used. In the latter case, the |
|
44 codes are customized to the probabilities in the current block, and so |
|
45 can code it much better than the pre-determined fixed codes. |
|
46 |
|
47 The Huffman codes themselves are decoded using a mutli-level table |
|
48 lookup, in order to maximize the speed of decoding plus the speed of |
|
49 building the decoding tables. See the comments below that precede the |
|
50 lbits and dbits tuning parameters. |
|
51 */ |
|
52 |
|
53 |
|
54 /* |
|
55 Notes beyond the 1.93a appnote.txt: |
|
56 |
|
57 1. Distance pointers never point before the beginning of the output |
|
58 stream. |
|
59 2. Distance pointers can point back across blocks, up to 32k away. |
|
60 3. There is an implied maximum of 7 bits for the bit length table and |
|
61 15 bits for the actual data. |
|
62 4. If only one code exists, then it is encoded using one bit. (Zero |
|
63 would be more efficient, but perhaps a little confusing.) If two |
|
64 codes exist, they are coded using one bit each (0 and 1). |
|
65 5. There is no way of sending zero distance codes--a dummy must be |
|
66 sent if there are none. (History: a pre 2.0 version of PKZIP would |
|
67 store blocks with no distance codes, but this was discovered to be |
|
68 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow |
|
69 zero distance codes, which is sent as one code of zero bits in |
|
70 length. |
|
71 6. There are up to 286 literal/length codes. Code 256 represents the |
|
72 end-of-block. Note however that the static length tree defines |
|
73 288 codes just to fill out the Huffman codes. Codes 286 and 287 |
|
74 cannot be used though, since there is no length base or extra bits |
|
75 defined for them. Similarly, there are up to 30 distance codes. |
|
76 However, static trees define 32 codes (all 5 bits) to fill out the |
|
77 Huffman codes, but the last two had better not show up in the data. |
|
78 7. Unzip can check dynamic Huffman blocks for complete code sets. |
|
79 The exception is that a single code would not be complete (see #4). |
|
80 8. The five bits following the block type is really the number of |
|
81 literal codes sent minus 257. |
|
82 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits |
|
83 (1+6+6). Therefore, to output three times the length, you output |
|
84 three codes (1+1+1), whereas to output four times the same length, |
|
85 you only need two codes (1+3). Hmm. |
|
86 10. In the tree reconstruction algorithm, Code = Code + Increment |
|
87 only if BitLength(i) is not zero. (Pretty obvious.) |
|
88 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) |
|
89 12. Note: length code 284 can represent 227-258, but length code 285 |
|
90 really is 258. The last length deserves its own, short code |
|
91 since it gets used a lot in very redundant files. The length |
|
92 258 is special since 258 - 3 (the min match length) is 255. |
|
93 13. The literal/length and distance code bit lengths are read as a |
|
94 single stream of lengths. It is possible (and advantageous) for |
|
95 a repeat code (16, 17, or 18) to go across the boundary between |
|
96 the two sets of lengths. |
|
97 */ |
|
98 |
|
99 #include "inflate.h" |
|
100 |
|
101 extern void* memcpy(void*, const void*, unsigned); |
|
102 extern void* memset(void*, int, unsigned); |
|
103 |
|
104 /* Huffman code lookup table entry--this entry is four bytes for machines |
|
105 that have 16-bit pointers (e.g. PC's in the small or medium model). |
|
106 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 |
|
107 means that v is a literal, 16 < e < 32 means that v is a pointer to |
|
108 the next table, which codes e - 16 bits, and lastly e == 99 indicates |
|
109 an unused code. If a code with e == 99 is looked up, this implies an |
|
110 error in the data. */ |
|
111 struct huft { |
|
112 uch e; /* number of extra bits or operation */ |
|
113 uch b; /* number of bits in this code or subcode */ |
|
114 union { |
|
115 ush n; /* literal, length base, or distance base */ |
|
116 struct huft *t; /* pointer to next level of table */ |
|
117 } v; |
|
118 }; |
|
119 |
|
120 |
|
121 /* Function prototypes */ |
|
122 int huft_build(unsigned *, unsigned, unsigned, const ush *, const ush *, |
|
123 struct huft **, int *); |
|
124 int huft_free(struct huft *); |
|
125 int inflate_codes(struct huft *, struct huft *, int, int); |
|
126 int inflate_stored(void); |
|
127 int inflate_fixed(void); |
|
128 int inflate_dynamic(void); |
|
129 int inflate_block(int *); |
|
130 int inflate(void); |
|
131 |
|
132 |
|
133 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed |
|
134 stream to find repeated byte strings. This is implemented here as a |
|
135 circular buffer. The index is updated simply by incrementing and then |
|
136 and'ing with 0x7fff (32K-1). */ |
|
137 /* It is left to other modules to supply the 32K area. It is assumed |
|
138 to be usable as if it were declared "uch slide[32768];" or as just |
|
139 "uch *slide;" and then malloc'ed in the latter case. The definition |
|
140 must be in unzip.h, included above. */ |
|
141 /* unsigned wp; current position in slide */ |
|
142 /*#define wp outcnt*/ |
|
143 /*#define flush_output(w) (wp=(w),flush_window())*/ |
|
144 |
|
145 /* Tables for deflate from PKZIP's appnote.txt. */ |
|
146 static const unsigned border[] = { /* Order of the bit length code lengths */ |
|
147 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
|
148 static const ush 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, |
|
150 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
|
151 /* note: see note #13 above about the 258 in this list. */ |
|
152 static const ush cplext[] = { /* Extra bits for literal codes 257..285 */ |
|
153 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, |
|
154 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ |
|
155 static const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ |
|
156 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
|
157 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
|
158 8193, 12289, 16385, 24577}; |
|
159 static const ush cpdext[] = { /* Extra bits for distance codes */ |
|
160 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, |
|
161 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, |
|
162 12, 12, 13, 13}; |
|
163 |
|
164 |
|
165 |
|
166 /* Macros for inflate() bit peeking and grabbing. |
|
167 The usage is: |
|
168 |
|
169 NEEDBITS(j) |
|
170 x = b & mask_bits[j]; |
|
171 DUMPBITS(j) |
|
172 |
|
173 where NEEDBITS makes sure that b has at least j bits in it, and |
|
174 DUMPBITS removes the bits from b. The macros use the variable k |
|
175 for the number of bits in b. Normally, b and k are register |
|
176 variables for speed, and are initialized at the beginning of a |
|
177 routine that uses these macros from a global bit buffer and count. |
|
178 |
|
179 If we assume that EOB will be the longest code, then we will never |
|
180 ask for bits with NEEDBITS that are beyond the end of the stream. |
|
181 So, NEEDBITS should not read any more bytes than are needed to |
|
182 meet the request. Then no bytes need to be "returned" to the buffer |
|
183 at the end of the last block. |
|
184 |
|
185 However, this assumption is not true for fixed blocks--the EOB code |
|
186 is 7 bits, but the other literal/length codes can be 8 or 9 bits. |
|
187 (The EOB code is shorter than other codes because fixed blocks are |
|
188 generally short. So, while a block always has an EOB, many other |
|
189 literal/length codes have a significantly lower probability of |
|
190 showing up at all.) However, by making the first table have a |
|
191 lookup of seven bits, the EOB code will be found in that first |
|
192 lookup, and so will not require that too many bits be pulled from |
|
193 the stream. |
|
194 */ |
|
195 |
|
196 ulg bb; /* bit buffer */ |
|
197 unsigned bk; /* bits in bit buffer */ |
|
198 |
|
199 static const ush mask_bits[] = { |
|
200 0x0000, |
|
201 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, |
|
202 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff |
|
203 }; |
|
204 |
|
205 #define get_byte() (inptr < inbuf_end ? *inptr++ : fill_inbuf()) |
|
206 #define NEXTBYTE() (uch)get_byte() |
|
207 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}} |
|
208 #define DUMPBITS(n) {b>>=(n);k-=(n);} |
|
209 |
|
210 |
|
211 /* |
|
212 Huffman code decoding is performed using a multi-level table lookup. |
|
213 The fastest way to decode is to simply build a lookup table whose |
|
214 size is determined by the longest code. However, the time it takes |
|
215 to build this table can also be a factor if the data being decoded |
|
216 is not very long. The most common codes are necessarily the |
|
217 shortest codes, so those codes dominate the decoding time, and hence |
|
218 the speed. The idea is you can have a shorter table that decodes the |
|
219 shorter, more probable codes, and then point to subsidiary tables for |
|
220 the longer codes. The time it costs to decode the longer codes is |
|
221 then traded against the time it takes to make longer tables. |
|
222 |
|
223 This results of this trade are in the variables lbits and dbits |
|
224 below. lbits is the number of bits the first level table for literal/ |
|
225 length codes can decode in one step, and dbits is the same thing for |
|
226 the distance codes. Subsequent tables are also less than or equal to |
|
227 those sizes. These values may be adjusted either when all of the |
|
228 codes are shorter than that, in which case the longest code length in |
|
229 bits is used, or when the shortest code is *longer* than the requested |
|
230 table size, in which case the length of the shortest code in bits is |
|
231 used. |
|
232 |
|
233 There are two different values for the two tables, since they code a |
|
234 different number of possibilities each. The literal/length table |
|
235 codes 286 possible values, or in a flat code, a little over eight |
|
236 bits. The distance table codes 30 possible values, or a little less |
|
237 than five bits, flat. The optimum values for speed end up being |
|
238 about one bit more than those, so lbits is 8+1 and dbits is 5+1. |
|
239 The optimum values may differ though from machine to machine, and |
|
240 possibly even between compilers. Your mileage may vary. |
|
241 */ |
|
242 |
|
243 |
|
244 static const int lbits = 9; /* bits in base literal/length lookup table */ |
|
245 static const int dbits = 6; /* bits in base distance lookup table */ |
|
246 |
|
247 |
|
248 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ |
|
249 #define BMAX 16 /* maximum bit length of any code (16 for explode) */ |
|
250 #define N_MAX 288 /* maximum number of codes in any set */ |
|
251 |
|
252 |
|
253 unsigned hufts; /* track memory usage */ |
|
254 |
|
255 |
|
256 int huft_build( |
|
257 unsigned *b, /* code lengths in bits (all assumed <= BMAX) */ |
|
258 unsigned n, /* number of codes (assumed <= N_MAX) */ |
|
259 unsigned s, /* number of simple-valued codes (0..s-1) */ |
|
260 const ush *d, /* list of base values for non-simple codes */ |
|
261 const ush *e, /* list of extra bits for non-simple codes */ |
|
262 struct huft **t, /* result: starting table */ |
|
263 int *m /* maximum lookup bits, returns actual */ |
|
264 ) |
|
265 /* Given a list of code lengths and a maximum table size, make a set of |
|
266 tables to decode that set of codes. Return zero on success, one if |
|
267 the given code set is incomplete (the tables are still built in this |
|
268 case), two if the input is invalid (all zero length codes or an |
|
269 oversubscribed set of lengths), and three if not enough memory. */ |
|
270 { |
|
271 unsigned a; /* counter for codes of length k */ |
|
272 unsigned c[BMAX+1]; /* bit length count table */ |
|
273 unsigned f; /* i repeats in table every f entries */ |
|
274 int g; /* maximum code length */ |
|
275 int h; /* table level */ |
|
276 register unsigned i; /* counter, current code */ |
|
277 register unsigned j; /* counter */ |
|
278 register int k; /* number of bits in current code */ |
|
279 int l; /* bits per table (returned in m) */ |
|
280 register unsigned *p; /* pointer into c[], b[], or v[] */ |
|
281 register struct huft *q; /* points to current table */ |
|
282 struct huft r; /* table entry for structure assignment */ |
|
283 struct huft *u[BMAX]; /* table stack */ |
|
284 unsigned v[N_MAX]; /* values in order of bit length */ |
|
285 register int w; /* bits before this table == (l * h) */ |
|
286 unsigned x[BMAX+1]; /* bit offsets, then code stack */ |
|
287 unsigned *xp; /* pointer into x */ |
|
288 int y; /* number of dummy codes added */ |
|
289 unsigned z; /* number of entries in current table */ |
|
290 |
|
291 |
|
292 /* Generate counts for each bit length */ |
|
293 memset(c, 0, sizeof(c)); |
|
294 p = b; i = n; |
|
295 do { |
|
296 /* Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), |
|
297 n-i, *p));*/ |
|
298 c[*p]++; /* assume all entries <= BMAX */ |
|
299 p++; /* Can't combine with above line (Solaris bug) */ |
|
300 } while (--i); |
|
301 if (c[0] == n) /* null input--all zero length codes */ |
|
302 { |
|
303 *t = (struct huft *)NULL; |
|
304 *m = 0; |
|
305 return 0; |
|
306 } |
|
307 |
|
308 |
|
309 /* Find minimum and maximum length, bound *m by those */ |
|
310 l = *m; |
|
311 for (j = 1; j <= BMAX; j++) |
|
312 if (c[j]) |
|
313 break; |
|
314 k = j; /* minimum code length */ |
|
315 if ((unsigned)l < j) |
|
316 l = j; |
|
317 for (i = BMAX; i; i--) |
|
318 if (c[i]) |
|
319 break; |
|
320 g = i; /* maximum code length */ |
|
321 if ((unsigned)l > i) |
|
322 l = i; |
|
323 *m = l; |
|
324 |
|
325 |
|
326 /* Adjust last length count to fill out codes, if needed */ |
|
327 for (y = 1 << j; j < i; j++, y <<= 1) |
|
328 if ((y -= c[j]) < 0) |
|
329 return 2; /* bad input: more codes than bits */ |
|
330 if ((y -= c[i]) < 0) |
|
331 return 2; |
|
332 c[i] += y; |
|
333 |
|
334 |
|
335 /* Generate starting offsets into the value table for each length */ |
|
336 x[1] = j = 0; |
|
337 p = c + 1; xp = x + 2; |
|
338 while (--i) { /* note that i == g from above */ |
|
339 *xp++ = (j += *p++); |
|
340 } |
|
341 |
|
342 |
|
343 /* Make a table of values in order of bit lengths */ |
|
344 p = b; i = 0; |
|
345 do { |
|
346 if ((j = *p++) != 0) |
|
347 v[x[j]++] = i; |
|
348 } while (++i < n); |
|
349 |
|
350 |
|
351 /* Generate the Huffman codes and for each, make the table entries */ |
|
352 x[0] = i = 0; /* first Huffman code is zero */ |
|
353 p = v; /* grab values in bit order */ |
|
354 h = -1; /* no tables yet--level -1 */ |
|
355 w = -l; /* bits decoded == (l * h) */ |
|
356 u[0] = (struct huft *)NULL; /* just to keep compilers happy */ |
|
357 q = (struct huft *)NULL; /* ditto */ |
|
358 z = 0; /* ditto */ |
|
359 |
|
360 /* go through the bit lengths (k already is bits in shortest code) */ |
|
361 for (; k <= g; k++) |
|
362 { |
|
363 a = c[k]; |
|
364 while (a--) |
|
365 { |
|
366 /* here i is the Huffman code of length k bits for value *p */ |
|
367 /* make tables up to required level */ |
|
368 while (k > w + l) |
|
369 { |
|
370 h++; |
|
371 w += l; /* previous table always l bits */ |
|
372 |
|
373 /* compute minimum size table less than or equal to l bits */ |
|
374 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */ |
|
375 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ |
|
376 { /* too few codes for k-w bit table */ |
|
377 f -= a + 1; /* deduct codes from patterns left */ |
|
378 xp = c + k; |
|
379 while (++j < z) /* try smaller tables up to z bits */ |
|
380 { |
|
381 if ((f <<= 1) <= *++xp) |
|
382 break; /* enough codes to use up j bits */ |
|
383 f -= *xp; /* else deduct codes from patterns */ |
|
384 } |
|
385 } |
|
386 z = 1 << j; /* table entries for j-bit table */ |
|
387 |
|
388 /* allocate and link in new table */ |
|
389 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == |
|
390 (struct huft *)NULL) |
|
391 { |
|
392 if (h) |
|
393 huft_free(u[0]); |
|
394 return 3; /* not enough memory */ |
|
395 } |
|
396 hufts += z + 1; /* track memory usage */ |
|
397 *t = q + 1; /* link to list for huft_free() */ |
|
398 *(t = &(q->v.t)) = (struct huft *)NULL; |
|
399 u[h] = ++q; /* table starts after link */ |
|
400 |
|
401 /* connect to last table, if there is one */ |
|
402 if (h) |
|
403 { |
|
404 x[h] = i; /* save pattern for backing up */ |
|
405 r.b = (uch)l; /* bits to dump before this table */ |
|
406 r.e = (uch)(16 + j); /* bits in this table */ |
|
407 r.v.t = q; /* pointer to this table */ |
|
408 j = i >> (w - l); /* (get around Turbo C bug) */ |
|
409 u[h-1][j] = r; /* connect to last table */ |
|
410 } |
|
411 } |
|
412 |
|
413 /* set up table entry in r */ |
|
414 r.b = (uch)(k - w); |
|
415 if (p >= v + n) |
|
416 r.e = 99; /* out of values--invalid code */ |
|
417 else if (*p < s) |
|
418 { |
|
419 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ |
|
420 r.v.n = (ush)(*p); /* simple code is just the value */ |
|
421 p++; /* one compiler does not like *p++ */ |
|
422 } |
|
423 else |
|
424 { |
|
425 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ |
|
426 r.v.n = d[*p++ - s]; |
|
427 } |
|
428 |
|
429 /* fill code-like entries with r */ |
|
430 f = 1 << (k - w); |
|
431 for (j = i >> w; j < z; j += f) |
|
432 q[j] = r; |
|
433 |
|
434 /* backwards increment the k-bit code i */ |
|
435 for (j = 1 << (k - 1); i & j; j >>= 1) |
|
436 i ^= j; |
|
437 i ^= j; |
|
438 |
|
439 /* backup over finished tables */ |
|
440 while ((i & ((1 << w) - 1)) != x[h]) |
|
441 { |
|
442 h--; /* don't need to update q */ |
|
443 w -= l; |
|
444 } |
|
445 } |
|
446 } |
|
447 |
|
448 |
|
449 /* Return true (1) if we were given an incomplete table */ |
|
450 return y != 0 && g != 1; |
|
451 } |
|
452 |
|
453 |
|
454 |
|
455 int huft_free(struct huft *t) |
|
456 /* Free the malloc'ed tables built by huft_build(), which makes a linked |
|
457 list of the tables it made, with the links in a dummy first entry of |
|
458 each table. */ |
|
459 { |
|
460 register struct huft *p, *q; |
|
461 |
|
462 |
|
463 /* Go through linked list, freeing from the malloced (t[-1]) address. */ |
|
464 p = t; |
|
465 while (p != (struct huft *)NULL) |
|
466 { |
|
467 q = (--p)->v.t; |
|
468 free((char*)p); |
|
469 p = q; |
|
470 } |
|
471 return 0; |
|
472 } |
|
473 |
|
474 |
|
475 int inflate_codes( |
|
476 struct huft *tl, |
|
477 struct huft *td, /* literal/length and distance decoder tables */ |
|
478 int bl, |
|
479 int bd /* number of bits decoded by tl[] and td[] */ |
|
480 ) |
|
481 /* inflate (decompress) the codes in a deflated (compressed) block. |
|
482 Return an error code or zero if it all goes ok. */ |
|
483 { |
|
484 register unsigned e; /* table entry flag/number of extra bits */ |
|
485 unsigned n, d; /* length and index for copy */ |
|
486 struct huft *t; /* pointer to table entry */ |
|
487 unsigned ml, md; /* masks for bl and bd bits */ |
|
488 register ulg b=bb; /* bit buffer */ |
|
489 register unsigned k=bk; /* number of bits in bit buffer */ |
|
490 register uch* p=(uch*)outptr; |
|
491 |
|
492 /* inflate the coded data */ |
|
493 ml = mask_bits[bl]; /* precompute masks for speed */ |
|
494 md = mask_bits[bd]; |
|
495 for (;;) /* do until end of block */ |
|
496 { |
|
497 NEEDBITS((unsigned)bl) |
|
498 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) |
|
499 do { |
|
500 if (e == 99) |
|
501 return 1; |
|
502 DUMPBITS(t->b) |
|
503 e -= 16; |
|
504 NEEDBITS(e) |
|
505 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); |
|
506 DUMPBITS(t->b) |
|
507 if (e == 16) /* then it's a literal */ |
|
508 { |
|
509 *p++ = (uch)t->v.n; |
|
510 } |
|
511 else /* it's an EOB or a length */ |
|
512 { |
|
513 /* exit if end of block */ |
|
514 if (e == 15) |
|
515 break; |
|
516 |
|
517 /* get length of block to copy */ |
|
518 NEEDBITS(e) |
|
519 n = t->v.n + ((unsigned)b & mask_bits[e]); |
|
520 DUMPBITS(e); |
|
521 |
|
522 /* decode distance of block to copy */ |
|
523 NEEDBITS((unsigned)bd) |
|
524 if ((e = (t = td + ((unsigned)b & md))->e) > 16) |
|
525 do { |
|
526 if (e == 99) |
|
527 return 1; |
|
528 DUMPBITS(t->b) |
|
529 e -= 16; |
|
530 NEEDBITS(e) |
|
531 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); |
|
532 DUMPBITS(t->b) |
|
533 NEEDBITS(e) |
|
534 d = t->v.n + ((unsigned)b & mask_bits[e]); |
|
535 d &= ZIP_WINDOW_SIZE-1; |
|
536 DUMPBITS(e) |
|
537 |
|
538 /* do the copy */ |
|
539 if (d>=n) |
|
540 { |
|
541 memcpy(p, p-d, n); |
|
542 p+=n; |
|
543 } |
|
544 else |
|
545 { |
|
546 uch* q=p-d; |
|
547 while(n--) *p++=*q++; |
|
548 } |
|
549 } |
|
550 } |
|
551 |
|
552 |
|
553 /* restore the globals from the locals */ |
|
554 outptr=p; |
|
555 bb = b; /* restore global bit buffer */ |
|
556 bk = k; |
|
557 |
|
558 /* done */ |
|
559 return 0; |
|
560 } |
|
561 |
|
562 |
|
563 |
|
564 int inflate_stored() |
|
565 /* "decompress" an inflated type 0 (stored) block. */ |
|
566 { |
|
567 unsigned n; /* number of bytes in block */ |
|
568 register ulg b; /* bit buffer */ |
|
569 register unsigned k; /* number of bits in bit buffer */ |
|
570 |
|
571 register uch* p=(uch*)outptr; |
|
572 |
|
573 |
|
574 /* make local copies of globals */ |
|
575 b = bb; /* initialize bit buffer */ |
|
576 k = bk; |
|
577 |
|
578 |
|
579 /* go to byte boundary */ |
|
580 n = k & 7; |
|
581 DUMPBITS(n); |
|
582 |
|
583 |
|
584 /* get the length and its complement */ |
|
585 NEEDBITS(16) |
|
586 n = ((unsigned)b & 0xffff); |
|
587 DUMPBITS(16) |
|
588 NEEDBITS(16) |
|
589 if (n != (unsigned)((~b) & 0xffff)) |
|
590 return 1; /* error in compressed data */ |
|
591 DUMPBITS(16) |
|
592 |
|
593 |
|
594 /* read and output the compressed data */ |
|
595 while (n--) |
|
596 { |
|
597 NEEDBITS(8) |
|
598 *p++=(uch)b; |
|
599 DUMPBITS(8) |
|
600 } |
|
601 |
|
602 |
|
603 /* restore the globals from the locals */ |
|
604 outptr=p; |
|
605 bb = b; /* restore global bit buffer */ |
|
606 bk = k; |
|
607 return 0; |
|
608 } |
|
609 |
|
610 |
|
611 |
|
612 int inflate_fixed() |
|
613 /* decompress an inflated type 1 (fixed Huffman codes) block. We should |
|
614 either replace this with a custom decoder, or at least precompute the |
|
615 Huffman tables. */ |
|
616 { |
|
617 int i; /* temporary variable */ |
|
618 struct huft *tl; /* literal/length code table */ |
|
619 struct huft *td; /* distance code table */ |
|
620 int bl; /* lookup bits for tl */ |
|
621 int bd; /* lookup bits for td */ |
|
622 unsigned l[288]; /* length list for huft_build */ |
|
623 |
|
624 |
|
625 /* set up literal table */ |
|
626 for (i = 0; i < 144; i++) |
|
627 l[i] = 8; |
|
628 for (; i < 256; i++) |
|
629 l[i] = 9; |
|
630 for (; i < 280; i++) |
|
631 l[i] = 7; |
|
632 for (; i < 288; i++) /* make a complete, but wrong code set */ |
|
633 l[i] = 8; |
|
634 bl = 7; |
|
635 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) |
|
636 return i; |
|
637 |
|
638 |
|
639 /* set up distance table */ |
|
640 for (i = 0; i < 30; i++) /* make an incomplete code set */ |
|
641 l[i] = 5; |
|
642 bd = 5; |
|
643 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) |
|
644 { |
|
645 huft_free(tl); |
|
646 return i; |
|
647 } |
|
648 |
|
649 |
|
650 /* decompress until an end-of-block code */ |
|
651 if (inflate_codes(tl, td, bl, bd)) |
|
652 return 1; |
|
653 |
|
654 |
|
655 /* free the decoding tables, return */ |
|
656 huft_free(tl); |
|
657 huft_free(td); |
|
658 return 0; |
|
659 } |
|
660 |
|
661 |
|
662 |
|
663 int inflate_dynamic() |
|
664 /* decompress an inflated type 2 (dynamic Huffman codes) block. */ |
|
665 { |
|
666 int i; /* temporary variables */ |
|
667 unsigned j; |
|
668 unsigned l; /* last length */ |
|
669 unsigned m; /* mask for bit lengths table */ |
|
670 unsigned n; /* number of lengths to get */ |
|
671 struct huft *tl; /* literal/length code table */ |
|
672 struct huft *td; /* distance code table */ |
|
673 int bl; /* lookup bits for tl */ |
|
674 int bd; /* lookup bits for td */ |
|
675 unsigned nb; /* number of bit length codes */ |
|
676 unsigned nl; /* number of literal/length codes */ |
|
677 unsigned nd; /* number of distance codes */ |
|
678 #ifdef PKZIP_BUG_WORKAROUND |
|
679 unsigned ll[288+32]; /* literal/length and distance code lengths */ |
|
680 #else |
|
681 unsigned ll[286+30]; /* literal/length and distance code lengths */ |
|
682 #endif |
|
683 register ulg b; /* bit buffer */ |
|
684 register unsigned k; /* number of bits in bit buffer */ |
|
685 |
|
686 |
|
687 /* make local bit buffer */ |
|
688 b = bb; |
|
689 k = bk; |
|
690 |
|
691 |
|
692 /* read in table lengths */ |
|
693 NEEDBITS(5) |
|
694 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ |
|
695 DUMPBITS(5) |
|
696 NEEDBITS(5) |
|
697 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ |
|
698 DUMPBITS(5) |
|
699 NEEDBITS(4) |
|
700 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ |
|
701 DUMPBITS(4) |
|
702 #ifdef PKZIP_BUG_WORKAROUND |
|
703 if (nl > 288 || nd > 32) |
|
704 #else |
|
705 if (nl > 286 || nd > 30) |
|
706 #endif |
|
707 return 1; /* bad lengths */ |
|
708 |
|
709 |
|
710 /* read in bit-length-code lengths */ |
|
711 for (j = 0; j < nb; j++) |
|
712 { |
|
713 NEEDBITS(3) |
|
714 ll[border[j]] = (unsigned)b & 7; |
|
715 DUMPBITS(3) |
|
716 } |
|
717 for (; j < 19; j++) |
|
718 ll[border[j]] = 0; |
|
719 |
|
720 |
|
721 /* build decoding table for trees--single level, 7 bit lookup */ |
|
722 bl = 7; |
|
723 if ((i = huft_build(ll, 19, 19, (ush*)NULL, (ush*)NULL, &tl, &bl)) != 0) |
|
724 { |
|
725 if (i == 1) |
|
726 huft_free(tl); |
|
727 return i; /* incomplete code set */ |
|
728 } |
|
729 |
|
730 |
|
731 /* read in literal and distance code lengths */ |
|
732 n = nl + nd; |
|
733 m = mask_bits[bl]; |
|
734 i = l = 0; |
|
735 while ((unsigned)i < n) |
|
736 { |
|
737 NEEDBITS((unsigned)bl) |
|
738 j = (td = tl + ((unsigned)b & m))->b; |
|
739 DUMPBITS(j) |
|
740 j = td->v.n; |
|
741 if (j < 16) /* length of code in bits (0..15) */ |
|
742 ll[i++] = l = j; /* save last length in l */ |
|
743 else if (j == 16) /* repeat last length 3 to 6 times */ |
|
744 { |
|
745 NEEDBITS(2) |
|
746 j = 3 + ((unsigned)b & 3); |
|
747 DUMPBITS(2) |
|
748 if ((unsigned)i + j > n) |
|
749 return 1; |
|
750 while (j--) |
|
751 ll[i++] = l; |
|
752 } |
|
753 else if (j == 17) /* 3 to 10 zero length codes */ |
|
754 { |
|
755 NEEDBITS(3) |
|
756 j = 3 + ((unsigned)b & 7); |
|
757 DUMPBITS(3) |
|
758 if ((unsigned)i + j > n) |
|
759 return 1; |
|
760 while (j--) |
|
761 ll[i++] = 0; |
|
762 l = 0; |
|
763 } |
|
764 else /* j == 18: 11 to 138 zero length codes */ |
|
765 { |
|
766 NEEDBITS(7) |
|
767 j = 11 + ((unsigned)b & 0x7f); |
|
768 DUMPBITS(7) |
|
769 if ((unsigned)i + j > n) |
|
770 return 1; |
|
771 while (j--) |
|
772 ll[i++] = 0; |
|
773 l = 0; |
|
774 } |
|
775 } |
|
776 |
|
777 |
|
778 /* free decoding table for trees */ |
|
779 huft_free(tl); |
|
780 |
|
781 |
|
782 /* restore the global bit buffer */ |
|
783 bb = b; |
|
784 bk = k; |
|
785 |
|
786 |
|
787 /* build the decoding tables for literal/length and distance codes */ |
|
788 bl = lbits; |
|
789 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) |
|
790 { |
|
791 if (i == 1) { |
|
792 /* fprintf(stderr, " incomplete literal tree\n");*/ |
|
793 huft_free(tl); |
|
794 } |
|
795 return i; /* incomplete code set */ |
|
796 } |
|
797 bd = dbits; |
|
798 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) |
|
799 { |
|
800 if (i == 1) { |
|
801 /* fprintf(stderr, " incomplete distance tree\n");*/ |
|
802 #ifdef PKZIP_BUG_WORKAROUND |
|
803 i = 0; |
|
804 } |
|
805 #else |
|
806 huft_free(td); |
|
807 } |
|
808 huft_free(tl); |
|
809 return i; /* incomplete code set */ |
|
810 #endif |
|
811 } |
|
812 |
|
813 |
|
814 /* decompress until an end-of-block code */ |
|
815 if (inflate_codes(tl, td, bl, bd)) |
|
816 return 1; |
|
817 |
|
818 |
|
819 /* free the decoding tables, return */ |
|
820 huft_free(tl); |
|
821 huft_free(td); |
|
822 return 0; |
|
823 } |
|
824 |
|
825 |
|
826 |
|
827 int inflate_block(int* e) |
|
828 /* decompress an inflated block */ |
|
829 { |
|
830 unsigned t; /* block type */ |
|
831 register ulg b; /* bit buffer */ |
|
832 register unsigned k; /* number of bits in bit buffer */ |
|
833 |
|
834 |
|
835 /* make local bit buffer */ |
|
836 b = bb; |
|
837 k = bk; |
|
838 |
|
839 |
|
840 /* read in last block bit */ |
|
841 NEEDBITS(1) |
|
842 *e = (int)b & 1; |
|
843 DUMPBITS(1) |
|
844 |
|
845 |
|
846 /* read in block type */ |
|
847 NEEDBITS(2) |
|
848 t = (unsigned)b & 3; |
|
849 DUMPBITS(2) |
|
850 |
|
851 |
|
852 /* restore the global bit buffer */ |
|
853 bb = b; |
|
854 bk = k; |
|
855 |
|
856 |
|
857 /* inflate that block type */ |
|
858 if (t == 2) |
|
859 return inflate_dynamic(); |
|
860 if (t == 0) |
|
861 return inflate_stored(); |
|
862 if (t == 1) |
|
863 return inflate_fixed(); |
|
864 |
|
865 |
|
866 /* bad block type */ |
|
867 return 2; |
|
868 } |
|
869 |
|
870 |
|
871 |
|
872 int inflate() |
|
873 /* decompress an inflated entry */ |
|
874 { |
|
875 int e; /* last block flag */ |
|
876 int r; /* result code */ |
|
877 unsigned h; /* maximum struct huft's malloc'ed */ |
|
878 |
|
879 |
|
880 /* initialize window, bit buffer */ |
|
881 /* wp = 0;*/ |
|
882 bk = 0; |
|
883 bb = 0; |
|
884 |
|
885 |
|
886 /* decompress until the last block */ |
|
887 h = 0; |
|
888 do { |
|
889 hufts = 0; |
|
890 r=inflate_block(&e); |
|
891 process_block(r); |
|
892 if (r!=0) |
|
893 return r; |
|
894 if (hufts > h) |
|
895 h = hufts; |
|
896 } while (!e); |
|
897 |
|
898 /* Undo too much lookahead. The next read will be byte aligned so we |
|
899 * can discard unused bits in the last meaningful byte. |
|
900 */ |
|
901 /* while (bk >= 8) { |
|
902 bk -= 8; |
|
903 inptr--; |
|
904 }*/ |
|
905 |
|
906 /* flush out slide */ |
|
907 /* flush_output(wp);*/ |
|
908 |
|
909 |
|
910 /* return success */ |
|
911 #ifdef DEBUG |
|
912 /* fprintf(stderr, "<%u> ", h);*/ |
|
913 #endif /* DEBUG */ |
|
914 |
|
915 return 0; |
|
916 } |