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