1 /*
2 * inflate.c - inflate decompression routine
3 *
4 * Version 1.1.2
5 */
6
7 /*
8 * Copyright (C) 1995, Edward B. Hamrick
9 *
10 * Permission to use, copy, modify, and distribute this software and
11 * its documentation for any purpose and without fee is hereby granted,
12 * provided that the above copyright notice appear in all copies and
13 * that both that copyright notice and this permission notice appear in
14 * supporting documentation, and that the name of the copyright holders
15 * not be used in advertising or publicity pertaining to distribution of
16 * the software without specific, written prior permission. The copyright
17 * holders makes no representations about the suitability of this software
18 * for any purpose. It is provided "as is" without express or implied warranty.
19 *
20 * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
21 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS,
22 * IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT
23 * OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
24 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
25 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
26 * OF THIS SOFTWARE.
27 */
28
29 /*
30 * Changes from 1.1 to 1.1.2:
31 * Relicensed under the MIT license, with consent of the copyright holders.
32 * Claudio Matsuoka (Jan 11 2011)
33 */
34
35 /*
36 * inflate.c is based on the public-domain (non-copyrighted) version
37 * written by Mark Adler, version c14o, 23 August 1994. It has been
38 * modified to be reentrant, more portable, and to be data driven.
39 */
40
41 /*
42 * 1) All file i/o is done externally to these routines
43 * 2) Routines are symmetrical so inflate can feed into deflate
44 * 3) Routines can be easily integrated into wide range of applications
45 * 4) Routines are very portable, and use only ANSI C
46 * 5) No #defines in inflate.h to conflict with external #defines
47 * 6) No external routines need be called by these routines
48 * 7) Buffers are owned by the calling routine
49 * 8) No static non-constant variables are allowed
50 */
51
52 /*
53 * Note that for each call to InflatePutBuffer, there will be
54 * 0 or more calls to (*putbuffer_ptr). Before InflatePutBuffer
55 * returns, it will have output as much uncompressed data as
56 * is possible.
57 */
58
59 #ifdef MEMCPY
60 #include <mem.h>
61 #endif
62
63 #include "inflate.h"
64
65 /*
66 * Macros for constants
67 */
68
69 #ifndef NULL
70 #define NULL ((void *) 0)
71 #endif
72
73 #ifndef TRUE
74 #define TRUE 1
75 #endif
76
77 #ifndef FALSE
78 #define FALSE 0
79 #endif
80
81 #ifndef WINDOWSIZE
82 #define WINDOWSIZE 0x8000
83 #endif
84
85 #ifndef WINDOWMASK
86 #define WINDOWMASK 0x7fff
87 #endif
88
89 #ifndef BUFFERSIZE
90 #define BUFFERSIZE 0x4000
91 #endif
92
93 #ifndef BUFFERMASK
94 #define BUFFERMASK 0x3fff
95 #endif
96
97 #ifndef INFLATESTATETYPE
98 #define INFLATESTATETYPE 0xabcdabcdL
99 #endif
100
101 /*
102 * typedefs
103 */
104
105 typedef unsigned long ulg;
106 typedef unsigned short ush;
107 typedef unsigned char uch;
108
109 /* Structure to hold state for inflating zip files */
110 struct InflateState {
111
112 unsigned long runtimetypeid1; /* to detect run-time errors */
113 int errorencountered; /* error encountered flag */
114
115 /* Decoding state */
116 int state; /* -1 -> need block type */
117 /* 0 -> need stored setup */
118 /* 1 -> need fixed setup */
119 /* 2 -> need dynamic setup */
120 /* 10 -> need stored data */
121 /* 11 -> need fixed data */
122 /* 12 -> need dynamic data */
123
124 /* State for decoding fixed & dynamic data */
125 struct huft *tl; /* literal/length decoder tbl */
126 struct huft *td; /* distance decoder table */
127 int bl; /* bits decoded by tl */
128 int bd; /* bits decoded by td */
129
130 /* State for decoding stored data */
131 unsigned int storelength;
132
133 /* State to keep track that last block has been encountered */
134 int lastblock; /* current block is last */
135
136 /* Input buffer state (circular) */
137 ulg bb; /* input buffer bits */
138 unsigned int bk; /* input buffer count of bits */
139 unsigned int bp; /* input buffer pointer */
140 unsigned int bs; /* input buffer size */
141 unsigned char buffer[BUFFERSIZE]; /* input buffer data */
142
143 /* Storage for try/catch */
144 ulg catch_bb; /* bit buffer */
145 unsigned int catch_bk; /* bits in bit buffer */
146 unsigned int catch_bp; /* buffer pointer */
147 unsigned int catch_bs; /* buffer size */
148
149 /* Output window state (circular) */
150 unsigned int wp; /* output window pointer */
151 unsigned int wf; /* output window flush-from */
152 unsigned char window[WINDOWSIZE]; /* output window data */
153
154 /* Application state */
155 void *AppState; /* opaque ptr for callout */
156
157 /* pointers to call-outs */
158 int (*putbuffer_ptr)( /* returns 0 on success */
159 void *AppState, /* opaque ptr from Initialize */
160 unsigned char *buffer, /* buffer to put */
161 long length /* length of buffer */
162 );
163
164 void *(*malloc_ptr)(long length); /* utility routine */
165
166 void (*free_ptr)(void *buffer); /* utility routine */
167
168 unsigned long runtimetypeid2; /* to detect run-time errors */
169 };
170
171 /*
172 * Error handling macro
173 */
174
175 #define ERROREXIT(is) {(is)->errorencountered = TRUE; return TRUE;}
176
177 /*
178 * Macros for handling data in the input buffer
179 *
180 * Note that the NEEDBITS and DUMPBITS macros
181 * need to be bracketed by the TRY/CATCH macros
182 *
183 * The usage is:
184 *
185 * TRY
186 * {
187 * NEEDBITS(j)
188 * x = b & mask_bits[j];
189 * DUMPBITS(j)
190 * }
191 * CATCH_BEGIN
192 * cleanup code
193 * CATCH_END
194 *
195 * Note that there can only be one TRY/CATCH pair per routine
196 * because of the use of goto in the implementation of the macros.
197 *
198 * NEEDBITS makes sure that b has at least j bits in it, and
199 * DUMPBITS removes the bits from b. The macros use the variable k
200 * for the number of bits in b. Normally, b and k are register
201 * variables for speed, and are initialized at the beginning of a
202 * routine that uses these macros from a global bit buffer and count.
203 *
204 * In order to not ask for more bits than there are in the compressed
205 * stream, the Huffman tables are constructed to only ask for just
206 * enough bits to make up the end-of-block code (value 256). Then no
207 * bytes need to be "returned" to the buffer at the end of the last
208 * block. See the huft_build() routine.
209 */
210
211 #define TRY \
212 is->catch_bb = b; \
213 is->catch_bk = k; \
214 is->catch_bp = is->bp; \
215 is->catch_bs = is->bs;
216
217 #define CATCH_BEGIN \
218 goto cleanup_done; \
219 cleanup: \
220 b = is->catch_bb; \
221 k = is->catch_bk; \
222 is->bb = b; \
223 is->bk = k; \
224 is->bp = is->catch_bp; \
225 is->bs = is->catch_bs;
226
227 #define CATCH_END \
228 cleanup_done: ;
229
230 #define NEEDBITS(n) \
231 { \
232 while (k < (n)) \
233 { \
234 if (is->bs <= 0) \
235 { \
236 goto cleanup; \
237 } \
238 b |= ((ulg) (is->buffer[is->bp & BUFFERMASK])) << k; \
239 is->bs--; \
240 is->bp++; \
241 k += 8; \
242 } \
243 }
244
245 #define DUMPBITS(n) \
246 { \
247 b >>= (n); \
248 k -= (n); \
249 }
250
251 /*
252 * Macro for flushing the output window to the putbuffer callout.
253 *
254 * Note that the window is always flushed when it fills to 32K,
255 * and before returning to the application.
256 */
257
258 #define FLUSHWINDOW(w, now) \
259 if ((now && (is->wp > is->wf)) || ((w) >= WINDOWSIZE)) \
260 { \
261 is->wp = (w); \
262 if ((*(is->putbuffer_ptr)) \
263 (is->AppState, is->window+is->wf, is->wp-is->wf)) \
264 ERROREXIT(is); \
265 is->wp &= WINDOWMASK; \
266 is->wf = is->wp; \
267 (w) = is->wp; \
268 }
269
270 /*
271 * Inflate deflated (PKZIP's method 8 compressed) data. The compression
272 * method searches for as much of the current string of bytes (up to a
273 * length of 258) in the previous 32K bytes. If it doesn't find any
274 * matches (of at least length 3), it codes the next byte. Otherwise, it
275 * codes the length of the matched string and its distance backwards from
276 * the current position. There is a single Huffman code that codes both
277 * single bytes (called "literals") and match lengths. A second Huffman
278 * code codes the distance information, which follows a length code. Each
279 * length or distance code actually represents a base value and a number
280 * of "extra" (sometimes zero) bits to get to add to the base value. At
281 * the end of each deflated block is a special end-of-block (EOB) literal/
282 * length code. The decoding process is basically: get a literal/length
283 * code; if EOB then done; if a literal, emit the decoded byte; if a
284 * length then get the distance and emit the referred-to bytes from the
285 * sliding window of previously emitted data.
286 *
287 * There are (currently) three kinds of inflate blocks: stored, fixed, and
288 * dynamic. The compressor outputs a chunk of data at a time and decides
289 * which method to use on a chunk-by-chunk basis. A chunk might typically
290 * be 32K to 64K, uncompressed. If the chunk is uncompressible, then the
291 * "stored" method is used. In this case, the bytes are simply stored as
292 * is, eight bits per byte, with none of the above coding. The bytes are
293 * preceded by a count, since there is no longer an EOB code.
294 *
295 * If the data is compressible, then either the fixed or dynamic methods
296 * are used. In the dynamic method, the compressed data is preceded by
297 * an encoding of the literal/length and distance Huffman codes that are
298 * to be used to decode this block. The representation is itself Huffman
299 * coded, and so is preceded by a description of that code. These code
300 * descriptions take up a little space, and so for small blocks, there is
301 * a predefined set of codes, called the fixed codes. The fixed method is
302 * used if the block ends up smaller that way (usually for quite small
303 * chunks); otherwise the dynamic method is used. In the latter case, the
304 * codes are customized to the probabilities in the current block and so
305 * can code it much better than the pre-determined fixed codes can.
306 *
307 * The Huffman codes themselves are decoded using a mutli-level table
308 * lookup, in order to maximize the speed of decoding plus the speed of
309 * building the decoding tables. See the comments below that precede the
310 * lbits and dbits tuning parameters.
311 */
312
313 /*
314 * Notes beyond the 1.93a appnote.txt:
315 *
316 * 1. Distance pointers never point before the beginning of the output
317 * stream.
318 * 2. Distance pointers can point back across blocks, up to 32k away.
319 * 3. There is an implied maximum of 7 bits for the bit length table and
320 * 15 bits for the actual data.
321 * 4. If only one code exists, then it is encoded using one bit. (Zero
322 * would be more efficient, but perhaps a little confusing.) If two
323 * codes exist, they are coded using one bit each (0 and 1).
324 * 5. There is no way of sending zero distance codes--a dummy must be
325 * sent if there are none. (History: a pre 2.0 version of PKZIP would
326 * store blocks with no distance codes, but this was discovered to be
327 * too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
328 * zero distance codes, which is sent as one code of zero bits in
329 * length.
330 * 6. There are up to 286 literal/length codes. Code 256 represents the
331 * end-of-block. Note however that the static length tree defines
332 * 288 codes just to fill out the Huffman codes. Codes 286 and 287
333 * cannot be used though, since there is no length base or extra bits
334 * defined for them. Similarly, there are up to 30 distance codes.
335 * However, static trees define 32 codes (all 5 bits) to fill out the
336 * Huffman codes, but the last two had better not show up in the data.
337 * 7. Unzip can check dynamic Huffman blocks for complete code sets.
338 * The exception is that a single code would not be complete (see #4).
339 * 8. The five bits following the block type is really the number of
340 * literal codes sent minus 257.
341 * 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
342 * (1+6+6). Therefore, to output three times the length, you output
343 * three codes (1+1+1), whereas to output four times the same length,
344 * you only need two codes (1+3). Hmm.
345 *10. In the tree reconstruction algorithm, Code = Code + Increment
346 * only if BitLength(i) is not zero. (Pretty obvious.)
347 *11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
348 *12. Note: length code 284 can represent 227-258, but length code 285
349 * really is 258. The last length deserves its own, short code
350 * since it gets used a lot in very redundant files. The length
351 * 258 is special since 258 - 3 (the min match length) is 255.
352 *13. The literal/length and distance code bit lengths are read as a
353 * single stream of lengths. It is possible (and advantageous) for
354 * a repeat code (16, 17, or 18) to go across the boundary between
355 * the two sets of lengths.
356 */
357
358 /*
359 * Huffman code lookup table entry--this entry is four bytes for machines
360 * that have 16-bit pointers (e.g. PC's in the small or medium model).
361 * Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
362 * means that v is a literal, 16 < e < 32 means that v is a pointer to
363 * the next table, which codes e - 16 bits, and lastly e == 99 indicates
364 * an unused code. If a code with e == 99 is looked up, this implies an
365 * error in the data.
366 */
367
368 struct huft {
369 uch e; /* number of extra bits or operation */
370 uch b; /* number of bits in this code or subcode */
371 union {
372 ush n; /* literal, length base, or distance base */
373 struct huft *t; /* pointer to next level of table */
374 } v;
375 };
376
377 /*
378 * Tables for deflate from PKZIP's appnote.txt.
379 */
380
381 static const unsigned border[] = { /* Order of the bit length code lengths */
382 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
383
384 static const ush cplens[] = { /* Copy lengths for literal codes 257..285 */
385 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
386 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
387 /* note: see note #13 above about the 258 in this list. */
388
389 static const ush cplext[] = { /* Extra bits for literal codes 257..285 */
390 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
391 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
392
393 static const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */
394 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
395 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
396 8193, 12289, 16385, 24577};
397
398 static const ush cpdext[] = { /* Extra bits for distance codes */
399 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
400 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
401 12, 12, 13, 13};
402
403 /*
404 * Constants for run-time computation of mask
405 */
406
407 static const ush mask_bits[] = {
408 0x0000,
409 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
410 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
411 };
412
413 /*
414 * Huffman code decoding is performed using a multi-level table lookup.
415 * The fastest way to decode is to simply build a lookup table whose
416 * size is determined by the longest code. However, the time it takes
417 * to build this table can also be a factor if the data being decoded
418 * is not very long. The most common codes are necessarily the
419 * shortest codes, so those codes dominate the decoding time, and hence
420 * the speed. The idea is you can have a shorter table that decodes the
421 * shorter, more probable codes, and then point to subsidiary tables for
422 * the longer codes. The time it costs to decode the longer codes is
423 * then traded against the time it takes to make longer tables.
424 *
425 * This results of this trade are in the variables lbits and dbits
426 * below. lbits is the number of bits the first level table for literal/
427 * length codes can decode in one step, and dbits is the same thing for
428 * the distance codes. Subsequent tables are also less than or equal to
429 * those sizes. These values may be adjusted either when all of the
430 * codes are shorter than that, in which case the longest code length in
431 * bits is used, or when the shortest code is *longer* than the requested
432 * table size, in which case the length of the shortest code in bits is
433 * used.
434 *
435 * There are two different values for the two tables, since they code a
436 * different number of possibilities each. The literal/length table
437 * codes 286 possible values, or in a flat code, a little over eight
438 * bits. The distance table codes 30 possible values, or a little less
439 * than five bits, flat. The optimum values for speed end up being
440 * about one bit more than those, so lbits is 8+1 and dbits is 5+1.
441 * The optimum values may differ though from machine to machine, and
442 * possibly even between compilers. Your mileage may vary.
443 */
444
445 static const int lbits = 9; /* bits in base literal/length lookup table */
446 static const int dbits = 6; /* bits in base distance lookup table */
447
448 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
449 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
450 #define N_MAX 288 /* maximum number of codes in any set */
451
452 /*
453 * Free the malloc'ed tables built by huft_build(), which makes a linked
454 * list of the tables it made, with the links in a dummy first entry of
455 * each table.
456 */
457
huft_free(struct InflateState * is,struct huft * t)458 static int huft_free(
459 struct InflateState *is, /* Inflate state */
460 struct huft *t /* table to free */
461 )
462 {
463 struct huft *p, *q;
464
465 /* Go through linked list, freeing from the malloced (t[-1]) address. */
466 p = t;
467 while (p != (struct huft *)NULL)
468 {
469 q = (--p)->v.t;
470 (*is->free_ptr)((char*)p);
471 p = q;
472 }
473 return 0;
474 }
475
476 /*
477 * Given a list of code lengths and a maximum table size, make a set of
478 * tables to decode that set of codes. Return zero on success, one if
479 * the given code set is incomplete (the tables are still built in this
480 * case), two if the input is invalid (all zero length codes or an
481 * oversubscribed set of lengths), and three if not enough memory.
482 * The code with value 256 is special, and the tables are constructed
483 * so that no bits beyond that code are fetched when that code is
484 * decoded.
485 */
486
huft_build(struct InflateState * is,unsigned * b,unsigned n,unsigned s,const ush * d,const ush * e,struct huft ** t,int * m)487 static int huft_build(
488 struct InflateState *is, /* Inflate state */
489 unsigned *b, /* code lengths in bits (all assumed <= BMAX) */
490 unsigned n, /* number of codes (assumed <= N_MAX) */
491 unsigned s, /* number of simple-valued codes (0..s-1) */
492 const ush *d, /* list of base values for non-simple codes */
493 const ush *e, /* list of extra bits for non-simple codes */
494 struct huft **t, /* result: starting table */
495 int *m /* maximum lookup bits, returns actual */
496 )
497 {
498 unsigned a; /* counter for codes of length k */
499 unsigned c[BMAX+1]; /* bit length count table */
500 unsigned el; /* length of EOB code (value 256) */
501 unsigned f; /* i repeats in table every f entries */
502 int g; /* maximum code length */
503 int h; /* table level */
504 unsigned i; /* counter, current code */
505 unsigned j; /* counter */
506 int k; /* number of bits in current code */
507 int lx[BMAX+1]; /* memory for l[-1..BMAX-1] */
508 int *l = lx+1; /* stack of bits per table */
509 unsigned *p; /* pointer into c[], b[], or v[] */
510 struct huft *q; /* points to current table */
511 struct huft r; /* table entry for structure assignment */
512 struct huft *u[BMAX]; /* table stack */
513 unsigned v[N_MAX]; /* values in order of bit length */
514 int w; /* bits before this table == (l * h) */
515 unsigned x[BMAX+1]; /* bit offsets, then code stack */
516 unsigned *xp; /* pointer into x */
517 int y; /* number of dummy codes added */
518 unsigned z; /* number of entries in current table */
519
520 /* clear the bit length count table */
521 for (i=0; i<(BMAX+1); i++)
522 {
523 c[i] = 0;
524 }
525
526 /* Generate counts for each bit length */
527 el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */
528 p = b; i = n;
529 do {
530 c[*p]++; p++; /* assume all entries <= BMAX */
531 } while (--i);
532 if (c[0] == n) /* null input--all zero length codes */
533 {
534 *t = (struct huft *)NULL;
535 *m = 0;
536 return 0;
537 }
538
539 /* Find minimum and maximum length, bound *m by those */
540 for (j = 1; j <= BMAX; j++)
541 if (c[j])
542 break;
543 k = j; /* minimum code length */
544 if ((unsigned)*m < j)
545 *m = j;
546 for (i = BMAX; i; i--)
547 if (c[i])
548 break;
549 g = i; /* maximum code length */
550 if ((unsigned)*m > i)
551 *m = i;
552
553 /* Adjust last length count to fill out codes, if needed */
554 for (y = 1 << j; j < i; j++, y <<= 1)
555 if ((y -= c[j]) < 0)
556 return 2; /* bad input: more codes than bits */
557 if ((y -= c[i]) < 0)
558 return 2;
559 c[i] += y;
560
561 /* Generate starting offsets into the value table for each length */
562 x[1] = j = 0;
563 p = c + 1; xp = x + 2;
564 while (--i) { /* note that i == g from above */
565 *xp++ = (j += *p++);
566 }
567
568 /* Make a table of values in order of bit lengths */
569 p = b; i = 0;
570 do {
571 if ((j = *p++) != 0)
572 v[x[j]++] = i;
573 } while (++i < n);
574
575 /* Generate the Huffman codes and for each, make the table entries */
576 x[0] = i = 0; /* first Huffman code is zero */
577 p = v; /* grab values in bit order */
578 h = -1; /* no tables yet--level -1 */
579 w = l[-1] = 0; /* no bits decoded yet */
580 u[0] = (struct huft *)NULL; /* just to keep compilers happy */
581 q = (struct huft *)NULL; /* ditto */
582 z = 0; /* ditto */
583
584 /* go through the bit lengths (k already is bits in shortest code) */
585 for (; k <= g; k++)
586 {
587 a = c[k];
588 while (a--)
589 {
590 /* here i is the Huffman code of length k bits for value *p */
591 /* make tables up to required level */
592 while (k > w + l[h])
593 {
594 w += l[h++]; /* add bits already decoded */
595
596 /* compute minimum size table less than or equal to *m bits */
597 z = (z = g - w) > (unsigned)*m ? *m : z; /* upper limit */
598 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
599 { /* too few codes for k-w bit table */
600 f -= a + 1; /* deduct codes from patterns left */
601 xp = c + k;
602 while (++j < z) /* try smaller tables up to z bits */
603 {
604 if ((f <<= 1) <= *++xp)
605 break; /* enough codes to use up j bits */
606 f -= *xp; /* else deduct codes from patterns */
607 }
608 }
609 if ((unsigned)w + j > el && (unsigned)w < el)
610 j = el - w; /* make EOB code end at table */
611 z = 1 << j; /* table entries for j-bit table */
612 l[h] = j; /* set table size in stack */
613
614 /* allocate and link in new table */
615 if ((q = (struct huft *)
616 ((*is->malloc_ptr)((z + 1)*sizeof(struct huft)))) ==
617 (struct huft *)NULL)
618 {
619 if (h)
620 huft_free(is, u[0]);
621 return 3; /* not enough memory */
622 }
623 *t = q + 1; /* link to list for huft_free() */
624 *(t = &(q->v.t)) = (struct huft *)NULL;
625 u[h] = ++q; /* table starts after link */
626
627 /* connect to last table, if there is one */
628 if (h)
629 {
630 x[h] = i; /* save pattern for backing up */
631 r.b = (uch)l[h-1]; /* bits to dump before this table */
632 r.e = (uch)(16 + j); /* bits in this table */
633 r.v.t = q; /* pointer to this table */
634 j = (i & ((1 << w) - 1)) >> (w - l[h-1]);
635 u[h-1][j] = r; /* connect to last table */
636 }
637 }
638
639 /* set up table entry in r */
640 r.b = (uch)(k - w);
641 if (p >= v + n)
642 r.e = 99; /* out of values--invalid code */
643 else if (*p < s)
644 {
645 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */
646 r.v.n = (ush) *p++; /* simple code is just the value */
647 }
648 else
649 {
650 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */
651 r.v.n = d[*p++ - s];
652 }
653
654 /* fill code-like entries with r */
655 f = 1 << (k - w);
656 for (j = i >> w; j < z; j += f)
657 q[j] = r;
658
659 /* backwards increment the k-bit code i */
660 for (j = 1 << (k - 1); i & j; j >>= 1)
661 i ^= j;
662 i ^= j;
663
664 /* backup over finished tables */
665 while ((i & ((1 << w) - 1)) != x[h])
666 w -= l[--h]; /* don't need to update q */
667 }
668 }
669
670 /* return actual size of base table */
671 *m = l[0];
672
673 /* Return true (1) if we were given an incomplete table */
674 return y != 0 && g != 1;
675 }
676
677 /*
678 * inflate (decompress) the codes in a stored (uncompressed) block.
679 * Return an error code or zero if it all goes ok.
680 */
681
inflate_stored(struct InflateState * is)682 static int inflate_stored(
683 struct InflateState *is /* Inflate state */
684 )
685 {
686 ulg b; /* bit buffer */
687 unsigned k; /* number of bits in bit buffer */
688 unsigned w; /* current window position */
689
690 /* make local copies of state */
691 b = is->bb; /* initialize bit buffer */
692 k = is->bk; /* initialize bit count */
693 w = is->wp; /* initialize window position */
694
695 /*
696 * Note that this code knows that NEEDBITS jumps to cleanup
697 */
698
699 while (is->storelength > 0) /* do until end of block */
700 {
701 NEEDBITS(8)
702 is->window[w++] = (uch) b;
703 DUMPBITS(8)
704 FLUSHWINDOW(w, FALSE);
705 is->storelength--;
706 }
707
708 cleanup:
709
710 /* restore the state from the locals */
711 is->bb = b; /* restore bit buffer */
712 is->bk = k; /* restore bit count */
713 is->wp = w; /* restore window pointer */
714
715 if (is->storelength > 0)
716 return -1;
717 else
718 return 0;
719 }
720
inflate_codes(struct InflateState * is,struct huft * tl,struct huft * td,int bl,int bd)721 static int inflate_codes(
722 struct InflateState *is, /* Inflate state */
723 struct huft *tl, /* literal/length decoder table */
724 struct huft *td, /* distance decoder table */
725 int bl, /* number of bits decoded by tl[] */
726 int bd /* number of bits decoded by td[] */
727 )
728 {
729 unsigned e; /* table entry flag/number of extra bits */
730 unsigned n, d; /* length and index for copy */
731 unsigned w; /* current window position */
732 struct huft *t; /* pointer to table entry */
733 unsigned ml, md; /* masks for bl and bd bits */
734 ulg b; /* bit buffer */
735 unsigned k; /* number of bits in bit buffer */
736
737 /* make local copies of state */
738 b = is->bb; /* initialize bit buffer */
739 k = is->bk; /* initialize bit count */
740 w = is->wp; /* initialize window position */
741
742 /* inflate the coded data */
743 ml = mask_bits[bl]; /* precompute masks for speed */
744 md = mask_bits[bd];
745 for (;;) /* do until end of block */
746 {
747 TRY
748 {
749 NEEDBITS((unsigned)bl)
750 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
751 do {
752 if (e == 99)
753 return 1;
754 DUMPBITS(t->b)
755 e -= 16;
756 NEEDBITS(e)
757 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
758 DUMPBITS(t->b)
759
760 if (e == 16) /* it's a literal */
761 {
762 is->window[w++] = (uch)t->v.n;
763 FLUSHWINDOW(w, FALSE);
764 }
765 else if (e == 15) /* it's an EOB */
766 {
767 break;
768 }
769 else /* it's a length */
770 {
771 /* get length of block to copy */
772 NEEDBITS(e)
773 n = t->v.n + ((unsigned)b & mask_bits[e]);
774 DUMPBITS(e);
775
776 /* decode distance of block to copy */
777 NEEDBITS((unsigned)bd)
778 if ((e = (t = td + ((unsigned)b & md))->e) > 16)
779 do {
780 if (e == 99)
781 return 1;
782 DUMPBITS(t->b)
783 e -= 16;
784 NEEDBITS(e)
785 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
786 DUMPBITS(t->b)
787 NEEDBITS(e)
788 d = w - t->v.n - ((unsigned)b & mask_bits[e]);
789 DUMPBITS(e)
790
791 /* do the copy */
792 do {
793 n -= (e = ((e = WINDOWSIZE - ((d &= WINDOWMASK) > w ? d : w)) > n)
794 ? n : e
795 );
796 #if defined(MEMCPY)
797 if (w - d >= e) /* (this test assumes unsigned comparison) */
798 {
799 memcpy(is->window + w, is->window + d, e);
800 w += e;
801 d += e;
802 }
803 else /* do it slow to avoid memcpy() overlap */
804 #endif /* MEMCPY */
805 do {
806 is->window[w++] = is->window[d++];
807 } while (--e);
808 FLUSHWINDOW(w, FALSE);
809 } while (n);
810 }
811 }
812 CATCH_BEGIN
813 is->wp = w; /* restore window pointer */
814 return -1;
815 CATCH_END
816 }
817
818 /* restore the state from the locals */
819 is->bb = b; /* restore bit buffer */
820 is->bk = k; /* restore bit count */
821 is->wp = w; /* restore window pointer */
822
823 /* done */
824 return 0;
825 }
826
827 /*
828 * "decompress" an inflated type 0 (stored) block.
829 */
830
inflate_stored_setup(struct InflateState * is)831 static int inflate_stored_setup(
832 struct InflateState *is /* Inflate state */
833 )
834 {
835 unsigned n; /* number of bytes in block */
836 ulg b; /* bit buffer */
837 unsigned k; /* number of bits in bit buffer */
838
839 /* make local copies of state */
840 b = is->bb; /* initialize bit buffer */
841 k = is->bk; /* initialize bit count */
842
843 TRY
844 {
845 /* go to byte boundary */
846 n = k & 7;
847 DUMPBITS(n);
848
849 /* get the length and its complement */
850 NEEDBITS(16)
851 n = ((unsigned)b & 0xffff);
852 DUMPBITS(16)
853 NEEDBITS(16)
854 if (n != (unsigned)((~b) & 0xffff))
855 return 1; /* error in compressed data */
856 DUMPBITS(16)
857 }
858 CATCH_BEGIN
859 return -1;
860 CATCH_END
861
862 /* Save store state for this block */
863 is->storelength = n;
864
865 /* restore the state from the locals */
866 is->bb = b; /* restore bit buffer */
867 is->bk = k; /* restore bit count */
868
869 return 0;
870 }
871
872 /*
873 * decompress an inflated type 1 (fixed Huffman codes) block. We should
874 * either replace this with a custom decoder, or at least precompute the
875 * Huffman tables.
876 */
877
inflate_fixed_setup(struct InflateState * is)878 static int inflate_fixed_setup(
879 struct InflateState *is /* Inflate state */
880 )
881 {
882 int i; /* temporary variable */
883 struct huft *tl; /* literal/length code table */
884 struct huft *td; /* distance code table */
885 int bl; /* lookup bits for tl */
886 int bd; /* lookup bits for td */
887 unsigned l[288]; /* length list for huft_build */
888
889 /* set up literal table */
890 for (i = 0; i < 144; i++)
891 l[i] = 8;
892 for (; i < 256; i++)
893 l[i] = 9;
894 for (; i < 280; i++)
895 l[i] = 7;
896 for (; i < 288; i++) /* make a complete, but wrong code set */
897 l[i] = 8;
898 bl = 7;
899 if ((i = huft_build(is, l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
900 return i;
901
902 /* set up distance table */
903 for (i = 0; i < 30; i++) /* make an incomplete code set */
904 l[i] = 5;
905 bd = 5;
906 if ((i = huft_build(is, l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
907 {
908 huft_free(is, tl);
909 return i;
910 }
911
912 /* Save inflate state for this block */
913 is->tl = tl;
914 is->td = td;
915 is->bl = bl;
916 is->bd = bd;
917
918 return 0;
919 }
920
921 /*
922 * decompress an inflated type 2 (dynamic Huffman codes) block.
923 */
924
925 #define PKZIP_BUG_WORKAROUND
926
inflate_dynamic_setup(struct InflateState * is)927 static int inflate_dynamic_setup(
928 struct InflateState *is /* Inflate state */
929 )
930 {
931 int i; /* temporary variables */
932 unsigned j;
933 unsigned l; /* last length */
934 unsigned m; /* mask for bit lengths table */
935 unsigned n; /* number of lengths to get */
936 struct huft *tl; /* literal/length code table */
937 struct huft *td; /* distance code table */
938 int bl; /* lookup bits for tl */
939 int bd; /* lookup bits for td */
940 unsigned nb; /* number of bit length codes */
941 unsigned nl; /* number of literal/length codes */
942 unsigned nd; /* number of distance codes */
943 #ifdef PKZIP_BUG_WORKAROUND
944 unsigned ll[288+32]; /* literal/length and distance code lengths */
945 #else
946 unsigned ll[286+30]; /* literal/length and distance code lengths */
947 #endif
948 ulg b; /* bit buffer */
949 unsigned k; /* number of bits in bit buffer */
950
951 /* make local copies of state */
952 b = is->bb; /* initialize bit buffer */
953 k = is->bk; /* initialize bit count */
954
955 /* initialize tl for cleanup */
956 tl = NULL;
957
958 TRY
959 {
960 /* read in table lengths */
961 NEEDBITS(5)
962 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */
963 DUMPBITS(5)
964 NEEDBITS(5)
965 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */
966 DUMPBITS(5)
967 NEEDBITS(4)
968 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */
969 DUMPBITS(4)
970 #ifdef PKZIP_BUG_WORKAROUND
971 if (nl > 288 || nd > 32)
972 #else
973 if (nl > 286 || nd > 30)
974 #endif
975 return 1; /* bad lengths */
976
977 /* read in bit-length-code lengths */
978 for (j = 0; j < 19; j++) ll[j] = 0;
979 for (j = 0; j < nb; j++)
980 {
981 NEEDBITS(3)
982 ll[border[j]] = (unsigned)b & 7;
983 DUMPBITS(3)
984 }
985
986 /* build decoding table for trees--single level, 7 bit lookup */
987 bl = 7;
988 if ((i = huft_build(is, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
989 {
990 if (i == 1)
991 huft_free(is, tl);
992 return i; /* incomplete code set */
993 }
994
995 /* read in literal and distance code lengths */
996 n = nl + nd;
997 m = mask_bits[bl];
998 i = l = 0;
999 while ((unsigned)i < n)
1000 {
1001 NEEDBITS((unsigned)bl)
1002 j = (td = tl + ((unsigned)b & m))->b;
1003 DUMPBITS(j)
1004 j = td->v.n;
1005 if (j < 16) /* length of code in bits (0..15) */
1006 ll[i++] = l = j; /* save last length in l */
1007 else if (j == 16) /* repeat last length 3 to 6 times */
1008 {
1009 NEEDBITS(2)
1010 j = 3 + ((unsigned)b & 3);
1011 DUMPBITS(2)
1012 if ((unsigned)i + j > n)
1013 return 1;
1014 while (j--)
1015 ll[i++] = l;
1016 }
1017 else if (j == 17) /* 3 to 10 zero length codes */
1018 {
1019 NEEDBITS(3)
1020 j = 3 + ((unsigned)b & 7);
1021 DUMPBITS(3)
1022 if ((unsigned)i + j > n)
1023 return 1;
1024 while (j--)
1025 ll[i++] = 0;
1026 l = 0;
1027 }
1028 else /* j == 18: 11 to 138 zero length codes */
1029 {
1030 NEEDBITS(7)
1031 j = 11 + ((unsigned)b & 0x7f);
1032 DUMPBITS(7)
1033 if ((unsigned)i + j > n)
1034 return 1;
1035 while (j--)
1036 ll[i++] = 0;
1037 l = 0;
1038 }
1039 }
1040
1041 /* free decoding table for trees */
1042 huft_free(is, tl);
1043 }
1044 CATCH_BEGIN
1045 if (tl) huft_free(is, tl);
1046 return -1;
1047 CATCH_END
1048
1049 /* restore the state from the locals */
1050 is->bb = b; /* restore bit buffer */
1051 is->bk = k; /* restore bit count */
1052
1053 /* build the decoding tables for literal/length and distance codes */
1054 bl = lbits;
1055 if ((i = huft_build(is, ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
1056 {
1057 if (i == 1) {
1058 /* incomplete literal tree */
1059 huft_free(is, tl);
1060 }
1061 return i; /* incomplete code set */
1062 }
1063 bd = dbits;
1064 if ((i = huft_build(is, ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
1065 {
1066 if (i == 1) {
1067 /* incomplete distance tree */
1068 #ifdef PKZIP_BUG_WORKAROUND
1069 }
1070 #else
1071 huft_free(is, td);
1072 }
1073 huft_free(is, tl);
1074 return i; /* incomplete code set */
1075 #endif
1076 }
1077
1078 /* Save inflate state for this block */
1079 is->tl = tl;
1080 is->td = td;
1081 is->bl = bl;
1082 is->bd = bd;
1083
1084 return 0;
1085 }
1086
1087 /* Routine to initialize inflate decompression */
InflateInitialize(void * AppState,int (* putbuffer_ptr)(void * AppState,unsigned char * buffer,long length),void * (* malloc_ptr)(long length),void (* free_ptr)(void * buffer))1088 void *InflateInitialize( /* returns InflateState */
1089 void *AppState, /* for passing to putbuffer */
1090 int (*putbuffer_ptr)( /* returns 0 on success */
1091 void *AppState, /* opaque ptr from Initialize */
1092 unsigned char *buffer, /* buffer to put */
1093 long length /* length of buffer */
1094 ),
1095 void *(*malloc_ptr)(long length), /* utility routine */
1096 void (*free_ptr)(void *buffer) /* utility routine */
1097 )
1098 {
1099 struct InflateState *is;
1100
1101 /* Do some argument checking */
1102 if ((!putbuffer_ptr) || (!malloc_ptr) || (!free_ptr)) return NULL;
1103
1104 /* Allocate the InflateState memory area */
1105 is = (struct InflateState *) (*malloc_ptr)(sizeof(struct InflateState));
1106 if (!is) return NULL;
1107
1108 /* Set up the initial values of the inflate state */
1109 is->runtimetypeid1 = INFLATESTATETYPE;
1110 is->errorencountered = FALSE;
1111
1112 is->bb = 0;
1113 is->bk = 0;
1114 is->bp = 0;
1115 is->bs = 0;
1116
1117 is->wp = 0;
1118 is->wf = 0;
1119
1120 is->state = -1;
1121 is->lastblock = FALSE;
1122
1123 is->AppState = AppState;
1124
1125 is->putbuffer_ptr = putbuffer_ptr;
1126 is->malloc_ptr = malloc_ptr;
1127 is->free_ptr = free_ptr;
1128
1129 is->runtimetypeid2 = INFLATESTATETYPE;
1130
1131 /* Return this state info to the caller */
1132 return is;
1133 }
1134
1135 /* Call-in routine to put a buffer into inflate decompression */
InflatePutBuffer(void * InflateState,unsigned char * buffer,long length)1136 int InflatePutBuffer( /* returns 0 on success */
1137 void *InflateState, /* opaque ptr from Initialize */
1138 unsigned char *buffer, /* buffer to put */
1139 long length /* length of buffer */
1140 )
1141 {
1142 struct InflateState *is;
1143
1144 int beginstate;
1145
1146 /* Get (and check) the InflateState structure */
1147 is = (struct InflateState *) InflateState;
1148 if (!is || (is->runtimetypeid1 != INFLATESTATETYPE)
1149 || (is->runtimetypeid2 != INFLATESTATETYPE)) return TRUE;
1150 if (is->errorencountered) return TRUE;
1151
1152 do
1153 {
1154 int size, i;
1155
1156
1157 if ((is->state == -1) && (is->lastblock)) break;
1158
1159 /* Save the beginning state */
1160 beginstate = is->state;
1161
1162 /* Push as much as possible into input buffer */
1163 size = BUFFERSIZE - is->bs;
1164 if (size > length) size = (int) length;
1165 i = is->bp + is->bs;
1166
1167 while (size-- > 0)
1168 {
1169 is->buffer[i++ & BUFFERMASK] = *buffer;
1170 is->bs++;
1171 buffer++;
1172 length--;
1173 }
1174
1175 /* Process some more data */
1176 if (is->state == -1)
1177 {
1178 int e; /* last block flag */
1179 unsigned t; /* block type */
1180
1181 ulg b; /* bit buffer */
1182 unsigned k; /* number of bits in bit buffer */
1183
1184 /* make local copies of state */
1185 b = is->bb; /* initialize bit buffer */
1186 k = is->bk; /* initialize bit count */
1187
1188 TRY
1189 {
1190 /* read in last block bit */
1191 NEEDBITS(1)
1192 e = (int)b & 1;
1193 DUMPBITS(1)
1194
1195 /* read in block type */
1196 NEEDBITS(2)
1197 t = (unsigned)b & 3;
1198 DUMPBITS(2)
1199
1200 if (t <= 2)
1201 {
1202 is->state = t;
1203 is->lastblock = e;
1204 }
1205 else
1206 {
1207 ERROREXIT(is);
1208 }
1209 }
1210 CATCH_BEGIN
1211 CATCH_END
1212
1213 /* restore the state from the locals */
1214 is->bb = b; /* restore bit buffer */
1215 is->bk = k; /* restore bit count */
1216 }
1217 else if (is->state == 0)
1218 {
1219 int ret;
1220
1221 ret = inflate_stored_setup(is);
1222
1223 if (ret > 0)
1224 ERROREXIT(is);
1225
1226 if (ret == 0) is->state += 10;
1227 }
1228 else if (is->state == 1)
1229 {
1230 int ret;
1231
1232 ret = inflate_fixed_setup(is);
1233
1234 if (ret > 0)
1235 ERROREXIT(is);
1236
1237 if (ret == 0) is->state += 10;
1238 }
1239 else if (is->state == 2)
1240 {
1241 int ret;
1242
1243 ret = inflate_dynamic_setup(is);
1244
1245 if (ret > 0)
1246 ERROREXIT(is);
1247
1248 if (ret == 0) is->state += 10;
1249 }
1250 else if (is->state == 10)
1251 {
1252 int ret;
1253
1254 ret = inflate_stored(is);
1255
1256 if (ret > 0)
1257 ERROREXIT(is);
1258
1259 if (ret == 0)
1260 {
1261 is->state = -1;
1262 }
1263 }
1264 else if ((is->state == 11) ||
1265 (is->state == 12) )
1266 {
1267 int ret;
1268
1269 ret = inflate_codes(is, is->tl, is->td, is->bl, is->bd);
1270
1271 if (ret > 0)
1272 ERROREXIT(is);
1273
1274 if (ret == 0)
1275 {
1276 /* free the decoding tables */
1277 huft_free(is, is->tl);
1278 huft_free(is, is->td);
1279 is->state = -1;
1280 }
1281 }
1282 else
1283 {
1284 ERROREXIT(is);
1285 }
1286 }
1287 while (length || (is->state != beginstate));
1288
1289 FLUSHWINDOW(is->wp, TRUE);
1290
1291 return is->errorencountered;
1292 }
1293
1294 /* Routine to terminate inflate decompression */
InflateTerminate(void * InflateState)1295 int InflateTerminate( /* returns 0 on success */
1296 void *InflateState /* opaque ptr from Initialize */
1297 )
1298 {
1299 int err;
1300 void (*free_ptr)(void *buffer);
1301
1302 struct InflateState *is;
1303
1304 /* Get (and check) the InflateState structure */
1305 is = (struct InflateState *) InflateState;
1306 if (!is || (is->runtimetypeid1 != INFLATESTATETYPE)
1307 || (is->runtimetypeid2 != INFLATESTATETYPE)) return TRUE;
1308
1309 /* save the error return */
1310 err = is->errorencountered || (is->bs > 0)
1311 || (is->state != -1)
1312 || (!is->lastblock);
1313
1314 /* save the address of the free routine */
1315 free_ptr = is->free_ptr;
1316
1317 /* Deallocate everything */
1318 (*free_ptr)(is);
1319
1320 return err;
1321 }
1322