1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2012 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6 /*
7 * Change history:
8 *
9 * 1.2.beta0 24 Nov 2002
10 * - First version -- complete rewrite of inflate to simplify code, avoid
11 * creation of window when not needed, minimize use of window when it is
12 * needed, make inffast.c even faster, implement gzip decoding, and to
13 * improve code readability and style over the previous zlib inflate code
14 *
15 * 1.2.beta1 25 Nov 2002
16 * - Use pointers for available input and output checking in inffast.c
17 * - Remove input and output counters in inffast.c
18 * - Change inffast.c entry and loop from avail_in >= 7 to >= 6
19 * - Remove unnecessary second byte pull from length extra in inffast.c
20 * - Unroll direct copy to three copies per loop in inffast.c
21 *
22 * 1.2.beta2 4 Dec 2002
23 * - Change external routine names to reduce potential conflicts
24 * - Correct filename to inffixed.h for fixed tables in inflate.c
25 * - Make hbuf[] unsigned char to match parameter type in inflate.c
26 * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
27 * to avoid negation problem on Alphas (64 bit) in inflate.c
28 *
29 * 1.2.beta3 22 Dec 2002
30 * - Add comments on state->bits assertion in inffast.c
31 * - Add comments on op field in inftrees.h
32 * - Fix bug in reuse of allocated window after inflateReset()
33 * - Remove bit fields--back to byte structure for speed
34 * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
35 * - Change post-increments to pre-increments in inflate_fast(), PPC biased?
36 * - Add compile time option, POSTINC, to use post-increments instead (Intel?)
37 * - Make MATCH copy in inflate() much faster for when inflate_fast() not used
38 * - Use local copies of stream next and avail values, as well as local bit
39 * buffer and bit count in inflate()--for speed when inflate_fast() not used
40 *
41 * 1.2.beta4 1 Jan 2003
42 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
43 * - Move a comment on output buffer sizes from inffast.c to inflate.c
44 * - Add comments in inffast.c to introduce the inflate_fast() routine
45 * - Rearrange window copies in inflate_fast() for speed and simplification
46 * - Unroll last copy for window match in inflate_fast()
47 * - Use local copies of window variables in inflate_fast() for speed
48 * - Pull out common wnext == 0 case for speed in inflate_fast()
49 * - Make op and len in inflate_fast() unsigned for consistency
50 * - Add FAR to lcode and dcode declarations in inflate_fast()
51 * - Simplified bad distance check in inflate_fast()
52 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
53 * source file infback.c to provide a call-back interface to inflate for
54 * programs like gzip and unzip -- uses window as output buffer to avoid
55 * window copying
56 *
57 * 1.2.beta5 1 Jan 2003
58 * - Improved inflateBack() interface to allow the caller to provide initial
59 * input in strm.
60 * - Fixed stored blocks bug in inflateBack()
61 *
62 * 1.2.beta6 4 Jan 2003
63 * - Added comments in inffast.c on effectiveness of POSTINC
64 * - Typecasting all around to reduce compiler warnings
65 * - Changed loops from while (1) or do {} while (1) to for (;;), again to
66 * make compilers happy
67 * - Changed type of window in inflateBackInit() to unsigned char *
68 *
69 * 1.2.beta7 27 Jan 2003
70 * - Changed many types to unsigned or unsigned short to avoid warnings
71 * - Added inflateCopy() function
72 *
73 * 1.2.0 9 Mar 2003
74 * - Changed inflateBack() interface to provide separate opaque descriptors
75 * for the in() and out() functions
76 * - Changed inflateBack() argument and in_func typedef to swap the length
77 * and buffer address return values for the input function
78 * - Check next_in and next_out for Z_NULL on entry to inflate()
79 *
80 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
81 */
82
83 #include "hammer2_zlib_zutil.h"
84 #include "hammer2_zlib_inftrees.h"
85 #include "hammer2_zlib_inflate.h"
86 #include "hammer2_zlib_inffast.h"
87 #include "../hammer2.h"
88 #include <sys/malloc.h> //for malloc macros
89
90 MALLOC_DECLARE(C_ZLIB_BUFFER_INFLATE);
91 MALLOC_DEFINE(C_ZLIB_BUFFER_INFLATE, "compzlibbufferinflate",
92 "A private buffer used by zlib library for inflate function.");
93
94 #ifdef MAKEFIXED
95 # ifndef BUILDFIXED
96 # define BUILDFIXED
97 # endif
98 #endif
99
100 /* function prototypes */
101 int inflateResetKeep(z_streamp strm);
102 int inflateReset(z_streamp strm);
103 int inflateReset2(z_streamp strm, int windowBits);
104 int inflateInit2_(z_streamp strm, int windowBits, const char *version,
105 int stream_size);
106 int inflatePrime(z_streamp strm, int bits, int value);
107 local void fixedtables(struct inflate_state FAR *state);
108 local int updatewindow(z_streamp strm, const unsigned char FAR *end,
109 unsigned copy);
110 #ifdef BUILDFIXED
111 void makefixed(void);
112 #endif
113
114 int
inflateResetKeep(z_streamp strm)115 inflateResetKeep(z_streamp strm)
116 {
117 struct inflate_state FAR *state;
118
119 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
120 state = (struct inflate_state FAR *)strm->state;
121 strm->total_in = strm->total_out = state->total = 0;
122 strm->msg = Z_NULL;
123 if (state->wrap) /* to support ill-conceived Java test suite */
124 strm->adler = state->wrap & 1;
125 state->mode = HEAD;
126 state->last = 0;
127 state->havedict = 0;
128 state->dmax = 32768U;
129 state->hold = 0;
130 state->bits = 0;
131 state->lencode = state->distcode = state->next = state->codes;
132 state->sane = 1;
133 state->back = -1;
134 Tracev((stderr, "inflate: reset\n"));
135 return Z_OK;
136 }
137
138 int
inflateReset(z_streamp strm)139 inflateReset(z_streamp strm)
140 {
141 struct inflate_state FAR *state;
142
143 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
144 state = (struct inflate_state FAR *)strm->state;
145 state->wsize = 0;
146 state->whave = 0;
147 state->wnext = 0;
148 return inflateResetKeep(strm);
149 }
150
151 int
inflateReset2(z_streamp strm,int windowBits)152 inflateReset2(z_streamp strm, int windowBits)
153 {
154 int wrap;
155 struct inflate_state FAR *state;
156
157 /* get the state */
158 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
159 state = (struct inflate_state FAR *)strm->state;
160
161 /* extract wrap request from windowBits parameter */
162 if (windowBits < 0) {
163 wrap = 0;
164 windowBits = -windowBits;
165 }
166 else {
167 wrap = (windowBits >> 4) + 1;
168 }
169
170 /* set number of window bits, free window if different */
171 if (windowBits && (windowBits < 8 || windowBits > 15))
172 return Z_STREAM_ERROR;
173 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
174 kfree(state->window, C_ZLIB_BUFFER_INFLATE);
175 state->window = Z_NULL;
176 }
177
178 /* update state and reset the rest of it */
179 state->wrap = wrap;
180 state->wbits = (unsigned)windowBits;
181 return inflateReset(strm);
182 }
183
184 int
inflateInit2_(z_streamp strm,int windowBits,const char * version,int stream_size)185 inflateInit2_(z_streamp strm, int windowBits, const char *version,
186 int stream_size)
187 {
188 int ret;
189 struct inflate_state FAR *state;
190
191 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
192 stream_size != (int)(sizeof(z_stream)))
193 return Z_VERSION_ERROR;
194 if (strm == Z_NULL) return Z_STREAM_ERROR;
195 strm->msg = Z_NULL; /* in case we return an error */
196 state = (struct inflate_state FAR *) kmalloc(sizeof(struct inflate_state), C_ZLIB_BUFFER_INFLATE, M_INTWAIT);
197 if (state == Z_NULL) return Z_MEM_ERROR;
198 Tracev((stderr, "inflate: allocated\n"));
199 strm->state = (struct internal_state FAR *)state;
200 state->window = Z_NULL;
201 ret = inflateReset2(strm, windowBits);
202 if (ret != Z_OK) {
203 kfree(state, C_ZLIB_BUFFER_INFLATE);
204 strm->state = Z_NULL;
205 }
206 return ret;
207 }
208
209 int
inflateInit_(z_streamp strm,const char * version,int stream_size)210 inflateInit_(z_streamp strm, const char *version, int stream_size)
211 {
212 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
213 }
214
215 int
inflatePrime(z_streamp strm,int bits,int value)216 inflatePrime(z_streamp strm, int bits, int value)
217 {
218 struct inflate_state FAR *state;
219
220 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
221 state = (struct inflate_state FAR *)strm->state;
222 if (bits < 0) {
223 state->hold = 0;
224 state->bits = 0;
225 return Z_OK;
226 }
227 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
228 value &= (1L << bits) - 1;
229 state->hold += value << state->bits;
230 state->bits += bits;
231 return Z_OK;
232 }
233
234 /*
235 Return state with length and distance decoding tables and index sizes set to
236 fixed code decoding. Normally this returns fixed tables from inffixed.h.
237 If BUILDFIXED is defined, then instead this routine builds the tables the
238 first time it's called, and returns those tables the first time and
239 thereafter. This reduces the size of the code by about 2K bytes, in
240 exchange for a little execution time. However, BUILDFIXED should not be
241 used for threaded applications, since the rewriting of the tables and virgin
242 may not be thread-safe.
243 */
244 local
245 void
fixedtables(struct inflate_state FAR * state)246 fixedtables(struct inflate_state FAR *state)
247 {
248 #ifdef BUILDFIXED
249 static int virgin = 1;
250 static code *lenfix, *distfix;
251 static code fixed[544];
252
253 /* build fixed huffman tables if first call (may not be thread safe) */
254 if (virgin) {
255 unsigned sym, bits;
256 static code *next;
257
258 /* literal/length table */
259 sym = 0;
260 while (sym < 144) state->lens[sym++] = 8;
261 while (sym < 256) state->lens[sym++] = 9;
262 while (sym < 280) state->lens[sym++] = 7;
263 while (sym < 288) state->lens[sym++] = 8;
264 next = fixed;
265 lenfix = next;
266 bits = 9;
267 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
268
269 /* distance table */
270 sym = 0;
271 while (sym < 32) state->lens[sym++] = 5;
272 distfix = next;
273 bits = 5;
274 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
275
276 /* do this just once */
277 virgin = 0;
278 }
279 #else /* !BUILDFIXED */
280 # include "hammer2_zlib_inffixed.h"
281 #endif /* BUILDFIXED */
282 state->lencode = lenfix;
283 state->lenbits = 9;
284 state->distcode = distfix;
285 state->distbits = 5;
286 }
287
288 #ifdef MAKEFIXED
289 #include <stdio.h>
290
291 /*
292 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
293 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
294 those tables to stdout, which would be piped to inffixed.h. A small program
295 can simply call makefixed to do this:
296
297 void makefixed(void);
298
299 int main(void)
300 {
301 makefixed();
302 return 0;
303 }
304
305 Then that can be linked with zlib built with MAKEFIXED defined and run:
306
307 a.out > inffixed.h
308 */
309 void
makefixed()310 makefixed()
311 {
312 unsigned low, size;
313 struct inflate_state state;
314
315 fixedtables(&state);
316 puts(" /* inffixed.h -- table for decoding fixed codes");
317 puts(" * Generated automatically by makefixed().");
318 puts(" */");
319 puts("");
320 puts(" /* WARNING: this file should *not* be used by applications.");
321 puts(" It is part of the implementation of this library and is");
322 puts(" subject to change. Applications should only use zlib.h.");
323 puts(" */");
324 puts("");
325 size = 1U << 9;
326 printf(" static const code lenfix[%u] = {", size);
327 low = 0;
328 for (;;) {
329 if ((low % 7) == 0) printf("\n ");
330 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
331 state.lencode[low].bits, state.lencode[low].val);
332 if (++low == size) break;
333 putchar(',');
334 }
335 puts("\n };");
336 size = 1U << 5;
337 printf("\n static const code distfix[%u] = {", size);
338 low = 0;
339 for (;;) {
340 if ((low % 6) == 0) printf("\n ");
341 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
342 state.distcode[low].val);
343 if (++low == size) break;
344 putchar(',');
345 }
346 puts("\n };");
347 }
348 #endif /* MAKEFIXED */
349
350 /*
351 Update the window with the last wsize (normally 32K) bytes written before
352 returning. If window does not exist yet, create it. This is only called
353 when a window is already in use, or when output has been written during this
354 inflate call, but the end of the deflate stream has not been reached yet.
355 It is also called to create a window for dictionary data when a dictionary
356 is loaded.
357
358 Providing output buffers larger than 32K to inflate() should provide a speed
359 advantage, since only the last 32K of output is copied to the sliding window
360 upon return from inflate(), and since all distances after the first 32K of
361 output will fall in the output data, making match copies simpler and faster.
362 The advantage may be dependent on the size of the processor's data caches.
363 */
364 local
365 int
updatewindow(z_streamp strm,const Bytef * end,unsigned copy)366 updatewindow(z_streamp strm, const Bytef *end, unsigned copy)
367 {
368 struct inflate_state FAR *state;
369 unsigned dist;
370
371 state = (struct inflate_state FAR *)strm->state;
372
373 /* if window not in use yet, initialize */
374 if (state->wsize == 0) {
375 state->wsize = 1U << state->wbits;
376 state->wnext = 0;
377 state->whave = 0;
378 }
379
380 /* copy state->wsize or less output bytes into the circular window */
381 if (copy >= state->wsize) {
382 zmemcpy(state->window, end - state->wsize, state->wsize);
383 state->wnext = 0;
384 state->whave = state->wsize;
385 }
386 else {
387 dist = state->wsize - state->wnext;
388 if (dist > copy) dist = copy;
389 zmemcpy(state->window + state->wnext, end - copy, dist);
390 copy -= dist;
391 if (copy) {
392 zmemcpy(state->window, end - copy, copy);
393 state->wnext = copy;
394 state->whave = state->wsize;
395 }
396 else {
397 state->wnext += dist;
398 if (state->wnext == state->wsize) state->wnext = 0;
399 if (state->whave < state->wsize) state->whave += dist;
400 }
401 }
402 return 0;
403 }
404
405 /* Macros for inflate(): */
406 #define UPDATE(check, buf, len) adler32(check, buf, len)
407
408 /* Load registers with state in inflate() for speed */
409 #define LOAD() \
410 do { \
411 put = strm->next_out; \
412 left = strm->avail_out; \
413 next = strm->next_in; \
414 have = strm->avail_in; \
415 hold = state->hold; \
416 bits = state->bits; \
417 } while (0)
418
419 /* Restore state from registers in inflate() */
420 #define RESTORE() \
421 do { \
422 strm->next_out = put; \
423 strm->avail_out = left; \
424 strm->next_in = next; \
425 strm->avail_in = have; \
426 state->hold = hold; \
427 state->bits = bits; \
428 } while (0)
429
430 /* Clear the input bit accumulator */
431 #define INITBITS() \
432 do { \
433 hold = 0; \
434 bits = 0; \
435 } while (0)
436
437 /* Get a byte of input into the bit accumulator, or return from inflate()
438 if there is no input available. */
439 #define PULLBYTE() \
440 do { \
441 if (have == 0) goto inf_leave; \
442 have--; \
443 hold += (unsigned long)(*next++) << bits; \
444 bits += 8; \
445 } while (0)
446
447 /* Assure that there are at least n bits in the bit accumulator. If there is
448 not enough available input to do that, then return from inflate(). */
449 #define NEEDBITS(n) \
450 do { \
451 while (bits < (unsigned)(n)) \
452 PULLBYTE(); \
453 } while (0)
454
455 /* Return the low n bits of the bit accumulator (n < 16) */
456 #define BITS(n) \
457 ((unsigned)hold & ((1U << (n)) - 1))
458
459 /* Remove n bits from the bit accumulator */
460 #define DROPBITS(n) \
461 do { \
462 hold >>= (n); \
463 bits -= (unsigned)(n); \
464 } while (0)
465
466 /* Remove zero to seven bits as needed to go to a byte boundary */
467 #define BYTEBITS() \
468 do { \
469 hold >>= bits & 7; \
470 bits -= bits & 7; \
471 } while (0)
472
473 /*
474 inflate() uses a state machine to process as much input data and generate as
475 much output data as possible before returning. The state machine is
476 structured roughly as follows:
477
478 for (;;) switch (state) {
479 ...
480 case STATEn:
481 if (not enough input data or output space to make progress)
482 return;
483 ... make progress ...
484 state = STATEm;
485 break;
486 ...
487 }
488
489 so when inflate() is called again, the same case is attempted again, and
490 if the appropriate resources are provided, the machine proceeds to the
491 next state. The NEEDBITS() macro is usually the way the state evaluates
492 whether it can proceed or should return. NEEDBITS() does the return if
493 the requested bits are not available. The typical use of the BITS macros
494 is:
495
496 NEEDBITS(n);
497 ... do something with BITS(n) ...
498 DROPBITS(n);
499
500 where NEEDBITS(n) either returns from inflate() if there isn't enough
501 input left to load n bits into the accumulator, or it continues. BITS(n)
502 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
503 the low n bits off the accumulator. INITBITS() clears the accumulator
504 and sets the number of available bits to zero. BYTEBITS() discards just
505 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
506 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
507
508 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
509 if there is no input available. The decoding of variable length codes uses
510 PULLBYTE() directly in order to pull just enough bytes to decode the next
511 code, and no more.
512
513 Some states loop until they get enough input, making sure that enough
514 state information is maintained to continue the loop where it left off
515 if NEEDBITS() returns in the loop. For example, want, need, and keep
516 would all have to actually be part of the saved state in case NEEDBITS()
517 returns:
518
519 case STATEw:
520 while (want < need) {
521 NEEDBITS(n);
522 keep[want++] = BITS(n);
523 DROPBITS(n);
524 }
525 state = STATEx;
526 case STATEx:
527
528 As shown above, if the next state is also the next case, then the break
529 is omitted.
530
531 A state may also return if there is not enough output space available to
532 complete that state. Those states are copying stored data, writing a
533 literal byte, and copying a matching string.
534
535 When returning, a "goto inf_leave" is used to update the total counters,
536 update the check value, and determine whether any progress has been made
537 during that inflate() call in order to return the proper return code.
538 Progress is defined as a change in either strm->avail_in or strm->avail_out.
539 When there is a window, goto inf_leave will update the window with the last
540 output written. If a goto inf_leave occurs in the middle of decompression
541 and there is no window currently, goto inf_leave will create one and copy
542 output to the window for the next call of inflate().
543
544 In this implementation, the flush parameter of inflate() only affects the
545 return code (per zlib.h). inflate() always writes as much as possible to
546 strm->next_out, given the space available and the provided input--the effect
547 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
548 the allocation of and copying into a sliding window until necessary, which
549 provides the effect documented in zlib.h for Z_FINISH when the entire input
550 stream available. So the only thing the flush parameter actually does is:
551 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
552 will return Z_BUF_ERROR if it has not reached the end of the stream.
553 */
554
555 int
inflate(z_streamp strm,int flush)556 inflate(z_streamp strm, int flush)
557 {
558 struct inflate_state FAR *state;
559 z_const unsigned char FAR *next; /* next input */
560 unsigned char FAR *put; /* next output */
561 unsigned have, left; /* available input and output */
562 unsigned long hold; /* bit buffer */
563 unsigned bits; /* bits in bit buffer */
564 unsigned in, out; /* save starting available input and output */
565 unsigned copy; /* number of stored or match bytes to copy */
566 unsigned char FAR *from; /* where to copy match bytes from */
567 code here; /* current decoding table entry */
568 code last; /* parent table entry */
569 unsigned len; /* length to copy for repeats, bits to drop */
570 int ret; /* return code */
571
572 static const unsigned short order[19] = /* permutation of code lengths */
573 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
574
575 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
576 (strm->next_in == Z_NULL && strm->avail_in != 0))
577 return Z_STREAM_ERROR;
578
579 state = (struct inflate_state FAR *)strm->state;
580 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
581 LOAD();
582 in = have;
583 out = left;
584 ret = Z_OK;
585 for (;;)
586 switch (state->mode) {
587 case HEAD:
588 if (state->wrap == 0) {
589 state->mode = TYPEDO;
590 break;
591 }
592 NEEDBITS(16);
593 if (((BITS(8) << 8) + (hold >> 8)) % 31) {
594 strm->msg = (char *)"incorrect header check";
595 state->mode = BAD;
596 break;
597 }
598 if (BITS(4) != Z_DEFLATED) {
599 strm->msg = (char *)"unknown compression method";
600 state->mode = BAD;
601 break;
602 }
603 DROPBITS(4);
604 len = BITS(4) + 8;
605 if (state->wbits == 0)
606 state->wbits = len;
607 else if (len > state->wbits) {
608 strm->msg = (char *)"invalid window size";
609 state->mode = BAD;
610 break;
611 }
612 state->dmax = 1U << len;
613 Tracev((stderr, "inflate: zlib header ok\n"));
614 strm->adler = state->check = adler32(0L, Z_NULL, 0);
615 state->mode = hold & 0x200 ? DICTID : TYPE;
616 INITBITS();
617 break;
618 case DICTID:
619 NEEDBITS(32);
620 strm->adler = state->check = ZSWAP32(hold);
621 INITBITS();
622 state->mode = DICT;
623 case DICT:
624 if (state->havedict == 0) {
625 RESTORE();
626 return Z_NEED_DICT;
627 }
628 strm->adler = state->check = adler32(0L, Z_NULL, 0);
629 state->mode = TYPE;
630 case TYPE:
631 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
632 case TYPEDO:
633 if (state->last) {
634 BYTEBITS();
635 state->mode = CHECK;
636 break;
637 }
638 NEEDBITS(3);
639 state->last = BITS(1);
640 DROPBITS(1);
641 switch (BITS(2)) {
642 case 0: /* stored block */
643 Tracev((stderr, "inflate: stored block%s\n",
644 state->last ? " (last)" : ""));
645 state->mode = STORED;
646 break;
647 case 1: /* fixed block */
648 fixedtables(state);
649 Tracev((stderr, "inflate: fixed codes block%s\n",
650 state->last ? " (last)" : ""));
651 state->mode = LEN_; /* decode codes */
652 if (flush == Z_TREES) {
653 DROPBITS(2);
654 goto inf_leave;
655 }
656 break;
657 case 2: /* dynamic block */
658 Tracev((stderr, "inflate: dynamic codes block%s\n",
659 state->last ? " (last)" : ""));
660 state->mode = TABLE;
661 break;
662 case 3:
663 strm->msg = (char *)"invalid block type";
664 state->mode = BAD;
665 }
666 DROPBITS(2);
667 break;
668 case STORED:
669 BYTEBITS(); /* go to byte boundary */
670 NEEDBITS(32);
671 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
672 strm->msg = (char *)"invalid stored block lengths";
673 state->mode = BAD;
674 break;
675 }
676 state->length = (unsigned)hold & 0xffff;
677 Tracev((stderr, "inflate: stored length %u\n",
678 state->length));
679 INITBITS();
680 state->mode = COPY_;
681 if (flush == Z_TREES) goto inf_leave;
682 case COPY_:
683 state->mode = COPY;
684 case COPY:
685 copy = state->length;
686 if (copy) {
687 if (copy > have) copy = have;
688 if (copy > left) copy = left;
689 if (copy == 0) goto inf_leave;
690 zmemcpy(put, next, copy);
691 have -= copy;
692 next += copy;
693 left -= copy;
694 put += copy;
695 state->length -= copy;
696 break;
697 }
698 Tracev((stderr, "inflate: stored end\n"));
699 state->mode = TYPE;
700 break;
701 case TABLE:
702 NEEDBITS(14);
703 state->nlen = BITS(5) + 257;
704 DROPBITS(5);
705 state->ndist = BITS(5) + 1;
706 DROPBITS(5);
707 state->ncode = BITS(4) + 4;
708 DROPBITS(4);
709 #ifndef PKZIP_BUG_WORKAROUND
710 if (state->nlen > 286 || state->ndist > 30) {
711 strm->msg = (char *)"too many length or distance symbols";
712 state->mode = BAD;
713 break;
714 }
715 #endif
716 Tracev((stderr, "inflate: table sizes ok\n"));
717 state->have = 0;
718 state->mode = LENLENS;
719 case LENLENS:
720 while (state->have < state->ncode) {
721 NEEDBITS(3);
722 state->lens[order[state->have++]] = (unsigned short)BITS(3);
723 DROPBITS(3);
724 }
725 while (state->have < 19)
726 state->lens[order[state->have++]] = 0;
727 state->next = state->codes;
728 state->lencode = (const code FAR *)(state->next);
729 state->lenbits = 7;
730 ret = inflate_table(CODES, state->lens, 19, &(state->next),
731 &(state->lenbits), state->work);
732 if (ret) {
733 strm->msg = (char *)"invalid code lengths set";
734 state->mode = BAD;
735 break;
736 }
737 Tracev((stderr, "inflate: code lengths ok\n"));
738 state->have = 0;
739 state->mode = CODELENS;
740 case CODELENS:
741 while (state->have < state->nlen + state->ndist) {
742 for (;;) {
743 here = state->lencode[BITS(state->lenbits)];
744 if ((unsigned)(here.bits) <= bits) break;
745 PULLBYTE();
746 }
747 if (here.val < 16) {
748 DROPBITS(here.bits);
749 state->lens[state->have++] = here.val;
750 }
751 else {
752 if (here.val == 16) {
753 NEEDBITS(here.bits + 2);
754 DROPBITS(here.bits);
755 if (state->have == 0) {
756 strm->msg = (char *)"invalid bit length repeat";
757 state->mode = BAD;
758 break;
759 }
760 len = state->lens[state->have - 1];
761 copy = 3 + BITS(2);
762 DROPBITS(2);
763 }
764 else if (here.val == 17) {
765 NEEDBITS(here.bits + 3);
766 DROPBITS(here.bits);
767 len = 0;
768 copy = 3 + BITS(3);
769 DROPBITS(3);
770 }
771 else {
772 NEEDBITS(here.bits + 7);
773 DROPBITS(here.bits);
774 len = 0;
775 copy = 11 + BITS(7);
776 DROPBITS(7);
777 }
778 if (state->have + copy > state->nlen + state->ndist) {
779 strm->msg = (char *)"invalid bit length repeat";
780 state->mode = BAD;
781 break;
782 }
783 while (copy--)
784 state->lens[state->have++] = (unsigned short)len;
785 }
786 }
787
788 /* handle error breaks in while */
789 if (state->mode == BAD) break;
790
791 /* check for end-of-block code (better have one) */
792 if (state->lens[256] == 0) {
793 strm->msg = (char *)"invalid code -- missing end-of-block";
794 state->mode = BAD;
795 break;
796 }
797
798 /* build code tables -- note: do not change the lenbits or distbits
799 values here (9 and 6) without reading the comments in inftrees.h
800 concerning the ENOUGH constants, which depend on those values */
801 state->next = state->codes;
802 state->lencode = (const code FAR *)(state->next);
803 state->lenbits = 9;
804 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
805 &(state->lenbits), state->work);
806 if (ret) {
807 strm->msg = (char *)"invalid literal/lengths set";
808 state->mode = BAD;
809 break;
810 }
811 state->distcode = (const code FAR *)(state->next);
812 state->distbits = 6;
813 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
814 &(state->next), &(state->distbits), state->work);
815 if (ret) {
816 strm->msg = (char *)"invalid distances set";
817 state->mode = BAD;
818 break;
819 }
820 Tracev((stderr, "inflate: codes ok\n"));
821 state->mode = LEN_;
822 if (flush == Z_TREES) goto inf_leave;
823 case LEN_:
824 state->mode = LEN;
825 case LEN:
826 if (have >= 6 && left >= 258) {
827 RESTORE();
828 inflate_fast(strm, out);
829 LOAD();
830 if (state->mode == TYPE)
831 state->back = -1;
832 break;
833 }
834 state->back = 0;
835 for (;;) {
836 here = state->lencode[BITS(state->lenbits)];
837 if ((unsigned)(here.bits) <= bits) break;
838 PULLBYTE();
839 }
840 if (here.op && (here.op & 0xf0) == 0) {
841 last = here;
842 for (;;) {
843 here = state->lencode[last.val +
844 (BITS(last.bits + last.op) >> last.bits)];
845 if ((unsigned)(last.bits + here.bits) <= bits) break;
846 PULLBYTE();
847 }
848 DROPBITS(last.bits);
849 state->back += last.bits;
850 }
851 DROPBITS(here.bits);
852 state->back += here.bits;
853 state->length = (unsigned)here.val;
854 if ((int)(here.op) == 0) {
855 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
856 "inflate: literal '%c'\n" :
857 "inflate: literal 0x%02x\n", here.val));
858 state->mode = LIT;
859 break;
860 }
861 if (here.op & 32) {
862 Tracevv((stderr, "inflate: end of block\n"));
863 state->back = -1;
864 state->mode = TYPE;
865 break;
866 }
867 if (here.op & 64) {
868 strm->msg = (char *)"invalid literal/length code";
869 state->mode = BAD;
870 break;
871 }
872 state->extra = (unsigned)(here.op) & 15;
873 state->mode = LENEXT;
874 case LENEXT:
875 if (state->extra) {
876 NEEDBITS(state->extra);
877 state->length += BITS(state->extra);
878 DROPBITS(state->extra);
879 state->back += state->extra;
880 }
881 Tracevv((stderr, "inflate: length %u\n", state->length));
882 state->was = state->length;
883 state->mode = DIST;
884 case DIST:
885 for (;;) {
886 here = state->distcode[BITS(state->distbits)];
887 if ((unsigned)(here.bits) <= bits) break;
888 PULLBYTE();
889 }
890 if ((here.op & 0xf0) == 0) {
891 last = here;
892 for (;;) {
893 here = state->distcode[last.val +
894 (BITS(last.bits + last.op) >> last.bits)];
895 if ((unsigned)(last.bits + here.bits) <= bits) break;
896 PULLBYTE();
897 }
898 DROPBITS(last.bits);
899 state->back += last.bits;
900 }
901 DROPBITS(here.bits);
902 state->back += here.bits;
903 if (here.op & 64) {
904 strm->msg = (char *)"invalid distance code";
905 state->mode = BAD;
906 break;
907 }
908 state->offset = (unsigned)here.val;
909 state->extra = (unsigned)(here.op) & 15;
910 state->mode = DISTEXT;
911 case DISTEXT:
912 if (state->extra) {
913 NEEDBITS(state->extra);
914 state->offset += BITS(state->extra);
915 DROPBITS(state->extra);
916 state->back += state->extra;
917 }
918 #ifdef INFLATE_STRICT
919 if (state->offset > state->dmax) {
920 strm->msg = (char *)"invalid distance too far back";
921 state->mode = BAD;
922 break;
923 }
924 #endif
925 Tracevv((stderr, "inflate: distance %u\n", state->offset));
926 state->mode = MATCH;
927 case MATCH:
928 if (left == 0) goto inf_leave;
929 copy = out - left;
930 if (state->offset > copy) { /* copy from window */
931 copy = state->offset - copy;
932 if (copy > state->whave) {
933 if (state->sane) {
934 strm->msg = (char *)"invalid distance too far back";
935 state->mode = BAD;
936 break;
937 }
938 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
939 Trace((stderr, "inflate.c too far\n"));
940 copy -= state->whave;
941 if (copy > state->length) copy = state->length;
942 if (copy > left) copy = left;
943 left -= copy;
944 state->length -= copy;
945 do {
946 *put++ = 0;
947 } while (--copy);
948 if (state->length == 0) state->mode = LEN;
949 break;
950 #endif
951 }
952 if (copy > state->wnext) {
953 copy -= state->wnext;
954 from = state->window + (state->wsize - copy);
955 }
956 else
957 from = state->window + (state->wnext - copy);
958 if (copy > state->length) copy = state->length;
959 }
960 else { /* copy from output */
961 from = put - state->offset;
962 copy = state->length;
963 }
964 if (copy > left) copy = left;
965 left -= copy;
966 state->length -= copy;
967 do {
968 *put++ = *from++;
969 } while (--copy);
970 if (state->length == 0) state->mode = LEN;
971 break;
972 case LIT:
973 if (left == 0) goto inf_leave;
974 *put++ = (unsigned char)(state->length);
975 left--;
976 state->mode = LEN;
977 break;
978 case CHECK:
979 if (state->wrap) {
980 NEEDBITS(32);
981 out -= left;
982 strm->total_out += out;
983 state->total += out;
984 if (out)
985 strm->adler = state->check =
986 UPDATE(state->check, put - out, out);
987 out = left;
988 if ((ZSWAP32(hold)) != state->check) {
989 strm->msg = (char *)"incorrect data check";
990 state->mode = BAD;
991 break;
992 }
993 INITBITS();
994 Tracev((stderr, "inflate: check matches trailer\n"));
995 }
996 state->mode = DONE;
997 case DONE:
998 ret = Z_STREAM_END;
999 goto inf_leave;
1000 case BAD:
1001 ret = Z_DATA_ERROR;
1002 goto inf_leave;
1003 case MEM:
1004 return Z_MEM_ERROR;
1005 case SYNC:
1006 default:
1007 return Z_STREAM_ERROR;
1008 }
1009
1010 /*
1011 Return from inflate(), updating the total counts and the check value.
1012 If there was no progress during the inflate() call, return a buffer
1013 error. Call updatewindow() to create and/or update the window state.
1014 Note: a memory error from inflate() is non-recoverable.
1015 */
1016 inf_leave:
1017 RESTORE();
1018 if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1019 (state->mode < CHECK || flush != Z_FINISH)))
1020 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1021 state->mode = MEM;
1022 return Z_MEM_ERROR;
1023 }
1024 in -= strm->avail_in;
1025 out -= strm->avail_out;
1026 strm->total_in += in;
1027 strm->total_out += out;
1028 state->total += out;
1029 if (state->wrap && out)
1030 strm->adler = state->check =
1031 UPDATE(state->check, strm->next_out - out, out);
1032 strm->data_type = state->bits + (state->last ? 64 : 0) +
1033 (state->mode == TYPE ? 128 : 0) +
1034 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1035 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1036 ret = Z_BUF_ERROR;
1037 return ret;
1038 }
1039
1040 int
inflateEnd(z_streamp strm)1041 inflateEnd(z_streamp strm)
1042 {
1043 struct inflate_state FAR *state;
1044 if (strm == Z_NULL || strm->state == Z_NULL)
1045 return Z_STREAM_ERROR;
1046 state = (struct inflate_state FAR *)strm->state;
1047 if (state->window != Z_NULL) kfree(state->window, C_ZLIB_BUFFER_INFLATE);
1048 kfree(strm->state, C_ZLIB_BUFFER_INFLATE);
1049 strm->state = Z_NULL;
1050 Tracev((stderr, "inflate: end\n"));
1051 return Z_OK;
1052 }
1053