1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2005 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 write == 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 "zutil.h"
84 #include "inftrees.h"
85 #include "inflate.h"
86 #include "inffast.h"
87
88 #ifdef MAKEFIXED
89 # ifndef BUILDFIXED
90 # define BUILDFIXED
91 # endif
92 #endif
93
94 /* function prototypes */
95 local void fixedtables OF((struct inflate_state FAR *state));
96 local int updatewindow OF((z_streamp strm, unsigned out));
97 #ifdef BUILDFIXED
98 void makefixed OF((void));
99 #endif
100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
101 unsigned len));
102
inflateReset(z_streamp strm)103 int ZEXPORT inflateReset (z_streamp strm)
104 {
105 struct inflate_state FAR *state;
106
107 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
108 state = (struct inflate_state FAR *)strm->state;
109 strm->total_in = strm->total_out = state->total = 0;
110 strm->msg = Z_NULL;
111 strm->adler = 1; /* to support ill-conceived Java test suite */
112 state->mode = HEAD;
113 state->last = 0;
114 state->havedict = 0;
115 state->dmax = 32768U;
116 state->head = Z_NULL;
117 state->wsize = 0;
118 state->whave = 0;
119 state->write = 0;
120 state->hold = 0;
121 state->bits = 0;
122 state->lencode = state->distcode = state->next = state->codes;
123 Tracev((stderr, "inflate: reset\n"));
124 return Z_OK;
125 }
126
inflatePrime(z_streamp strm,int bits,int value)127 int ZEXPORT inflatePrime (z_streamp strm, int bits, int value)
128 {
129 struct inflate_state FAR *state;
130
131 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
132 state = (struct inflate_state FAR *)strm->state;
133 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
134 value &= (1 << bits) - 1;
135 state->hold += value << state->bits;
136 state->bits += bits;
137 return Z_OK;
138 }
139
inflateInit2_(z_streamp strm,int windowBits,const char * version,int stream_size)140 int ZEXPORT inflateInit2_(z_streamp strm, int windowBits, const char *version, int stream_size)
141 {
142 struct inflate_state FAR *state;
143
144 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
145 stream_size != (int)(sizeof(z_stream)))
146 return Z_VERSION_ERROR;
147 if (strm == Z_NULL) return Z_STREAM_ERROR;
148 strm->msg = Z_NULL; /* in case we return an error */
149 if (strm->zalloc == (alloc_func)0) {
150 strm->zalloc = zcalloc;
151 strm->opaque = (voidpf)0;
152 }
153 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
154 state = (struct inflate_state FAR *)
155 ZALLOC(strm, 1, sizeof(struct inflate_state));
156 if (state == Z_NULL) return Z_MEM_ERROR;
157 Tracev((stderr, "inflate: allocated\n"));
158 strm->state = (struct internal_state FAR *)state;
159 if (windowBits < 0) {
160 state->wrap = 0;
161 windowBits = -windowBits;
162 }
163 else {
164 state->wrap = (windowBits >> 4) + 1;
165 #ifdef GUNZIP
166 if (windowBits < 48) windowBits &= 15;
167 #endif
168 }
169 if (windowBits < 8 || windowBits > 15) {
170 ZFREE(strm, state);
171 strm->state = Z_NULL;
172 return Z_STREAM_ERROR;
173 }
174 state->wbits = (unsigned)windowBits;
175 state->window = Z_NULL;
176 return inflateReset(strm);
177 }
178
inflateInit_(z_streamp strm,const char * version,int stream_size)179 int ZEXPORT inflateInit_ (z_streamp strm, const char *version, int stream_size)
180 {
181 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
182 }
183
184 /*
185 Return state with length and distance decoding tables and index sizes set to
186 fixed code decoding. Normally this returns fixed tables from inffixed.h.
187 If BUILDFIXED is defined, then instead this routine builds the tables the
188 first time it's called, and returns those tables the first time and
189 thereafter. This reduces the size of the code by about 2K bytes, in
190 exchange for a little execution time. However, BUILDFIXED should not be
191 used for threaded applications, since the rewriting of the tables and virgin
192 may not be thread-safe.
193 */
fixedtables(struct inflate_state FAR * state)194 local void fixedtables (struct inflate_state FAR *state)
195 {
196 #ifdef BUILDFIXED
197 static int virgin = 1;
198 static code *lenfix, *distfix;
199 static code fixed[544];
200
201 /* build fixed huffman tables if first call (may not be thread safe) */
202 if (virgin) {
203 unsigned sym, bits;
204 static code *next;
205
206 /* literal/length table */
207 sym = 0;
208 while (sym < 144) state->lens[sym++] = 8;
209 while (sym < 256) state->lens[sym++] = 9;
210 while (sym < 280) state->lens[sym++] = 7;
211 while (sym < 288) state->lens[sym++] = 8;
212 next = fixed;
213 lenfix = next;
214 bits = 9;
215 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
216
217 /* distance table */
218 sym = 0;
219 while (sym < 32) state->lens[sym++] = 5;
220 distfix = next;
221 bits = 5;
222 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
223
224 /* do this just once */
225 virgin = 0;
226 }
227 #else /* !BUILDFIXED */
228 # include "inffixed.h"
229 #endif /* BUILDFIXED */
230 state->lencode = lenfix;
231 state->lenbits = 9;
232 state->distcode = distfix;
233 state->distbits = 5;
234 }
235
236 #ifdef MAKEFIXED
237 #include <stdio.h>
238
239 /*
240 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
241 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
242 those tables to stdout, which would be piped to inffixed.h. A small program
243 can simply call makefixed to do this:
244
245 void makefixed(void);
246
247 int main(void)
248 {
249 makefixed();
250 return 0;
251 }
252
253 Then that can be linked with zlib built with MAKEFIXED defined and run:
254
255 a.out > inffixed.h
256 */
makefixed()257 void makefixed()
258 {
259 unsigned low, size;
260 struct inflate_state state;
261
262 fixedtables(&state);
263 puts(" /* inffixed.h -- table for decoding fixed codes");
264 puts(" * Generated automatically by makefixed().");
265 puts(" */");
266 puts("");
267 puts(" /* WARNING: this file should *not* be used by applications.");
268 puts(" It is part of the implementation of this library and is");
269 puts(" subject to change. Applications should only use zlib.h.");
270 puts(" */");
271 puts("");
272 size = 1U << 9;
273 printf(" static const code lenfix[%u] = {", size);
274 low = 0;
275 for (;;) {
276 if ((low % 7) == 0) printf("\n ");
277 printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
278 state.lencode[low].val);
279 if (++low == size) break;
280 putchar(',');
281 }
282 puts("\n };");
283 size = 1U << 5;
284 printf("\n static const code distfix[%u] = {", size);
285 low = 0;
286 for (;;) {
287 if ((low % 6) == 0) printf("\n ");
288 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
289 state.distcode[low].val);
290 if (++low == size) break;
291 putchar(',');
292 }
293 puts("\n };");
294 }
295 #endif /* MAKEFIXED */
296
297 /*
298 Update the window with the last wsize (normally 32K) bytes written before
299 returning. If window does not exist yet, create it. This is only called
300 when a window is already in use, or when output has been written during this
301 inflate call, but the end of the deflate stream has not been reached yet.
302 It is also called to create a window for dictionary data when a dictionary
303 is loaded.
304
305 Providing output buffers larger than 32K to inflate() should provide a speed
306 advantage, since only the last 32K of output is copied to the sliding window
307 upon return from inflate(), and since all distances after the first 32K of
308 output will fall in the output data, making match copies simpler and faster.
309 The advantage may be dependent on the size of the processor's data caches.
310 */
updatewindow(z_streamp strm,unsigned out)311 local int updatewindow (z_streamp strm, unsigned out)
312 {
313 struct inflate_state FAR *state;
314 unsigned copy, dist;
315
316 state = (struct inflate_state FAR *)strm->state;
317
318 /* if it hasn't been done already, allocate space for the window */
319 if (state->window == Z_NULL) {
320 state->window = (unsigned char FAR *)
321 ZALLOC(strm, 1U << state->wbits,
322 sizeof(unsigned char));
323 if (state->window == Z_NULL) return 1;
324 }
325
326 /* if window not in use yet, initialize */
327 if (state->wsize == 0) {
328 state->wsize = 1U << state->wbits;
329 state->write = 0;
330 state->whave = 0;
331 }
332
333 /* copy state->wsize or less output bytes into the circular window */
334 copy = out - strm->avail_out;
335 if (copy >= state->wsize) {
336 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
337 state->write = 0;
338 state->whave = state->wsize;
339 }
340 else {
341 dist = state->wsize - state->write;
342 if (dist > copy) dist = copy;
343 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
344 copy -= dist;
345 if (copy) {
346 zmemcpy(state->window, strm->next_out - copy, copy);
347 state->write = copy;
348 state->whave = state->wsize;
349 }
350 else {
351 state->write += dist;
352 if (state->write == state->wsize) state->write = 0;
353 if (state->whave < state->wsize) state->whave += dist;
354 }
355 }
356 return 0;
357 }
358
359 /* Macros for inflate(): */
360
361 /* check function to use adler32() for zlib or crc32() for gzip */
362 #ifdef GUNZIP
363 # define UPDATE(check, buf, len) \
364 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
365 #else
366 # define UPDATE(check, buf, len) adler32(check, buf, len)
367 #endif
368
369 /* check macros for header crc */
370 #ifdef GUNZIP
371 # define CRC2(check, word) \
372 do { \
373 hbuf[0] = (unsigned char)(word); \
374 hbuf[1] = (unsigned char)((word) >> 8); \
375 check = crc32(check, hbuf, 2); \
376 } while (0)
377
378 # define CRC4(check, word) \
379 do { \
380 hbuf[0] = (unsigned char)(word); \
381 hbuf[1] = (unsigned char)((word) >> 8); \
382 hbuf[2] = (unsigned char)((word) >> 16); \
383 hbuf[3] = (unsigned char)((word) >> 24); \
384 check = crc32(check, hbuf, 4); \
385 } while (0)
386 #endif
387
388 /* Load registers with state in inflate() for speed */
389 #define LOAD() \
390 do { \
391 put = strm->next_out; \
392 left = strm->avail_out; \
393 next = strm->next_in; \
394 have = strm->avail_in; \
395 hold = state->hold; \
396 bits = state->bits; \
397 } while (0)
398
399 /* Restore state from registers in inflate() */
400 #define RESTORE() \
401 do { \
402 strm->next_out = put; \
403 strm->avail_out = left; \
404 strm->next_in = next; \
405 strm->avail_in = have; \
406 state->hold = hold; \
407 state->bits = bits; \
408 } while (0)
409
410 /* Clear the input bit accumulator */
411 #define INITBITS() \
412 do { \
413 hold = 0; \
414 bits = 0; \
415 } while (0)
416
417 /* Get a byte of input into the bit accumulator, or return from inflate()
418 if there is no input available. */
419 #define PULLBYTE() \
420 do { \
421 if (have == 0) goto inf_leave; \
422 have--; \
423 hold += (unsigned long)(*next++) << bits; \
424 bits += 8; \
425 } while (0)
426
427 /* Assure that there are at least n bits in the bit accumulator. If there is
428 not enough available input to do that, then return from inflate(). */
429 #define NEEDBITS(n) \
430 do { \
431 while (bits < (unsigned)(n)) \
432 PULLBYTE(); \
433 } while (0)
434
435 /* Return the low n bits of the bit accumulator (n < 16) */
436 #define BITS(n) \
437 ((unsigned)hold & ((1U << (n)) - 1))
438
439 /* Remove n bits from the bit accumulator */
440 #define DROPBITS(n) \
441 do { \
442 hold >>= (n); \
443 bits -= (unsigned)(n); \
444 } while (0)
445
446 /* Remove zero to seven bits as needed to go to a byte boundary */
447 #define BYTEBITS() \
448 do { \
449 hold >>= bits & 7; \
450 bits -= bits & 7; \
451 } while (0)
452
453 /* Reverse the bytes in a 32-bit value */
454 #define REVERSE(q) \
455 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
456 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
457
458 /*
459 inflate() uses a state machine to process as much input data and generate as
460 much output data as possible before returning. The state machine is
461 structured roughly as follows:
462
463 for (;;) switch (state) {
464 ...
465 case STATEn:
466 if (not enough input data or output space to make progress)
467 return;
468 ... make progress ...
469 state = STATEm;
470 break;
471 ...
472 }
473
474 so when inflate() is called again, the same case is attempted again, and
475 if the appropriate resources are provided, the machine proceeds to the
476 next state. The NEEDBITS() macro is usually the way the state evaluates
477 whether it can proceed or should return. NEEDBITS() does the return if
478 the requested bits are not available. The typical use of the BITS macros
479 is:
480
481 NEEDBITS(n);
482 ... do something with BITS(n) ...
483 DROPBITS(n);
484
485 where NEEDBITS(n) either returns from inflate() if there isn't enough
486 input left to load n bits into the accumulator, or it continues. BITS(n)
487 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
488 the low n bits off the accumulator. INITBITS() clears the accumulator
489 and sets the number of available bits to zero. BYTEBITS() discards just
490 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
491 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
492
493 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
494 if there is no input available. The decoding of variable length codes uses
495 PULLBYTE() directly in order to pull just enough bytes to decode the next
496 code, and no more.
497
498 Some states loop until they get enough input, making sure that enough
499 state information is maintained to continue the loop where it left off
500 if NEEDBITS() returns in the loop. For example, want, need, and keep
501 would all have to actually be part of the saved state in case NEEDBITS()
502 returns:
503
504 case STATEw:
505 while (want < need) {
506 NEEDBITS(n);
507 keep[want++] = BITS(n);
508 DROPBITS(n);
509 }
510 state = STATEx;
511 case STATEx:
512
513 As shown above, if the next state is also the next case, then the break
514 is omitted.
515
516 A state may also return if there is not enough output space available to
517 complete that state. Those states are copying stored data, writing a
518 literal byte, and copying a matching string.
519
520 When returning, a "goto inf_leave" is used to update the total counters,
521 update the check value, and determine whether any progress has been made
522 during that inflate() call in order to return the proper return code.
523 Progress is defined as a change in either strm->avail_in or strm->avail_out.
524 When there is a window, goto inf_leave will update the window with the last
525 output written. If a goto inf_leave occurs in the middle of decompression
526 and there is no window currently, goto inf_leave will create one and copy
527 output to the window for the next call of inflate().
528
529 In this implementation, the flush parameter of inflate() only affects the
530 return code (per zlib.h). inflate() always writes as much as possible to
531 strm->next_out, given the space available and the provided input--the effect
532 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
533 the allocation of and copying into a sliding window until necessary, which
534 provides the effect documented in zlib.h for Z_FINISH when the entire input
535 stream available. So the only thing the flush parameter actually does is:
536 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
537 will return Z_BUF_ERROR if it has not reached the end of the stream.
538 */
539
inflate(z_streamp strm,int flush)540 int ZEXPORT inflate (z_streamp strm, int flush)
541 {
542 struct inflate_state FAR *state;
543 unsigned char FAR *next; /* next input */
544 unsigned char FAR *put; /* next output */
545 unsigned have, left; /* available input and output */
546 unsigned long hold; /* bit buffer */
547 unsigned bits; /* bits in bit buffer */
548 unsigned in, out; /* save starting available input and output */
549 unsigned copy; /* number of stored or match bytes to copy */
550 unsigned char FAR *from; /* where to copy match bytes from */
551 code thisx; /* current decoding table entry */
552 code last; /* parent table entry */
553 unsigned len; /* length to copy for repeats, bits to drop */
554 int ret; /* return code */
555 #ifdef GUNZIP
556 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
557 #endif
558 static const unsigned short order[19] = /* permutation of code lengths */
559 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
560
561 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
562 (strm->next_in == Z_NULL && strm->avail_in != 0))
563 return Z_STREAM_ERROR;
564
565 state = (struct inflate_state FAR *)strm->state;
566 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
567 LOAD();
568 in = have;
569 out = left;
570 ret = Z_OK;
571 for (;;)
572 switch (state->mode) {
573 case HEAD:
574 if (state->wrap == 0) {
575 state->mode = TYPEDO;
576 break;
577 }
578 NEEDBITS(16);
579 #ifdef GUNZIP
580 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
581 state->check = crc32(0L, Z_NULL, 0);
582 CRC2(state->check, hold);
583 INITBITS();
584 state->mode = FLAGS;
585 break;
586 }
587 state->flags = 0; /* expect zlib header */
588 if (state->head != Z_NULL)
589 state->head->done = -1;
590 if (!(state->wrap & 1) || /* check if zlib header allowed */
591 #else
592 if (
593 #endif
594 ((BITS(8) << 8) + (hold >> 8)) % 31) {
595 strm->msg = (char *)"incorrect header check";
596 state->mode = BAD;
597 break;
598 }
599 if (BITS(4) != Z_DEFLATED) {
600 strm->msg = (char *)"unknown compression method";
601 state->mode = BAD;
602 break;
603 }
604 DROPBITS(4);
605 len = BITS(4) + 8;
606 if (len > state->wbits) {
607 strm->msg = (char *)"invalid window size";
608 state->mode = BAD;
609 break;
610 }
611 state->dmax = 1U << len;
612 Tracev((stderr, "inflate: zlib header ok\n"));
613 strm->adler = state->check = adler32(0L, Z_NULL, 0);
614 state->mode = hold & 0x200 ? DICTID : TYPE;
615 INITBITS();
616 break;
617 #ifdef GUNZIP
618 case FLAGS:
619 NEEDBITS(16);
620 state->flags = (int)(hold);
621 if ((state->flags & 0xff) != Z_DEFLATED) {
622 strm->msg = (char *)"unknown compression method";
623 state->mode = BAD;
624 break;
625 }
626 if (state->flags & 0xe000) {
627 strm->msg = (char *)"unknown header flags set";
628 state->mode = BAD;
629 break;
630 }
631 if (state->head != Z_NULL)
632 state->head->text = (int)((hold >> 8) & 1);
633 if (state->flags & 0x0200) CRC2(state->check, hold);
634 INITBITS();
635 state->mode = TIME;
636 case TIME:
637 NEEDBITS(32);
638 if (state->head != Z_NULL)
639 state->head->time = hold;
640 if (state->flags & 0x0200) CRC4(state->check, hold);
641 INITBITS();
642 state->mode = OS;
643 case OS:
644 NEEDBITS(16);
645 if (state->head != Z_NULL) {
646 state->head->xflags = (int)(hold & 0xff);
647 state->head->os = (int)(hold >> 8);
648 }
649 if (state->flags & 0x0200) CRC2(state->check, hold);
650 INITBITS();
651 state->mode = EXLEN;
652 case EXLEN:
653 if (state->flags & 0x0400) {
654 NEEDBITS(16);
655 state->length = (unsigned)(hold);
656 if (state->head != Z_NULL)
657 state->head->extra_len = (unsigned)hold;
658 if (state->flags & 0x0200) CRC2(state->check, hold);
659 INITBITS();
660 }
661 else if (state->head != Z_NULL)
662 state->head->extra = Z_NULL;
663 state->mode = EXTRA;
664 case EXTRA:
665 if (state->flags & 0x0400) {
666 copy = state->length;
667 if (copy > have) copy = have;
668 if (copy) {
669 if (state->head != Z_NULL &&
670 state->head->extra != Z_NULL) {
671 len = state->head->extra_len - state->length;
672 zmemcpy(state->head->extra + len, next,
673 len + copy > state->head->extra_max ?
674 state->head->extra_max - len : copy);
675 }
676 if (state->flags & 0x0200)
677 state->check = crc32(state->check, next, copy);
678 have -= copy;
679 next += copy;
680 state->length -= copy;
681 }
682 if (state->length) goto inf_leave;
683 }
684 state->length = 0;
685 state->mode = NAME;
686 case NAME:
687 if (state->flags & 0x0800) {
688 if (have == 0) goto inf_leave;
689 copy = 0;
690 do {
691 len = (unsigned)(next[copy++]);
692 if (state->head != Z_NULL &&
693 state->head->name != Z_NULL &&
694 state->length < state->head->name_max)
695 state->head->name[state->length++] = len;
696 } while (len && copy < have);
697 if (state->flags & 0x0200)
698 state->check = crc32(state->check, next, copy);
699 have -= copy;
700 next += copy;
701 if (len) goto inf_leave;
702 }
703 else if (state->head != Z_NULL)
704 state->head->name = Z_NULL;
705 state->length = 0;
706 state->mode = COMMENT;
707 case COMMENT:
708 if (state->flags & 0x1000) {
709 if (have == 0) goto inf_leave;
710 copy = 0;
711 do {
712 len = (unsigned)(next[copy++]);
713 if (state->head != Z_NULL &&
714 state->head->comment != Z_NULL &&
715 state->length < state->head->comm_max)
716 state->head->comment[state->length++] = len;
717 } while (len && copy < have);
718 if (state->flags & 0x0200)
719 state->check = crc32(state->check, next, copy);
720 have -= copy;
721 next += copy;
722 if (len) goto inf_leave;
723 }
724 else if (state->head != Z_NULL)
725 state->head->comment = Z_NULL;
726 state->mode = HCRC;
727 case HCRC:
728 if (state->flags & 0x0200) {
729 NEEDBITS(16);
730 if (hold != (state->check & 0xffff)) {
731 strm->msg = (char *)"header crc mismatch";
732 state->mode = BAD;
733 break;
734 }
735 INITBITS();
736 }
737 if (state->head != Z_NULL) {
738 state->head->hcrc = (int)((state->flags >> 9) & 1);
739 state->head->done = 1;
740 }
741 strm->adler = state->check = crc32(0L, Z_NULL, 0);
742 state->mode = TYPE;
743 break;
744 #endif
745 case DICTID:
746 NEEDBITS(32);
747 strm->adler = state->check = REVERSE(hold);
748 INITBITS();
749 state->mode = DICT;
750 case DICT:
751 if (state->havedict == 0) {
752 RESTORE();
753 return Z_NEED_DICT;
754 }
755 strm->adler = state->check = adler32(0L, Z_NULL, 0);
756 state->mode = TYPE;
757 case TYPE:
758 if (flush == Z_BLOCK) goto inf_leave;
759 case TYPEDO:
760 if (state->last) {
761 BYTEBITS();
762 state->mode = CHECK;
763 break;
764 }
765 NEEDBITS(3);
766 state->last = BITS(1);
767 DROPBITS(1);
768 switch (BITS(2)) {
769 case 0: /* stored block */
770 Tracev((stderr, "inflate: stored block%s\n",
771 state->last ? " (last)" : ""));
772 state->mode = STORED;
773 break;
774 case 1: /* fixed block */
775 fixedtables(state);
776 Tracev((stderr, "inflate: fixed codes block%s\n",
777 state->last ? " (last)" : ""));
778 state->mode = LEN; /* decode codes */
779 break;
780 case 2: /* dynamic block */
781 Tracev((stderr, "inflate: dynamic codes block%s\n",
782 state->last ? " (last)" : ""));
783 state->mode = TABLE;
784 break;
785 case 3:
786 strm->msg = (char *)"invalid block type";
787 state->mode = BAD;
788 }
789 DROPBITS(2);
790 break;
791 case STORED:
792 BYTEBITS(); /* go to byte boundary */
793 NEEDBITS(32);
794 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
795 strm->msg = (char *)"invalid stored block lengths";
796 state->mode = BAD;
797 break;
798 }
799 state->length = (unsigned)hold & 0xffff;
800 Tracev((stderr, "inflate: stored length %u\n",
801 state->length));
802 INITBITS();
803 state->mode = COPY;
804 case COPY:
805 copy = state->length;
806 if (copy) {
807 if (copy > have) copy = have;
808 if (copy > left) copy = left;
809 if (copy == 0) goto inf_leave;
810 zmemcpy(put, next, copy);
811 have -= copy;
812 next += copy;
813 left -= copy;
814 put += copy;
815 state->length -= copy;
816 break;
817 }
818 Tracev((stderr, "inflate: stored end\n"));
819 state->mode = TYPE;
820 break;
821 case TABLE:
822 NEEDBITS(14);
823 state->nlen = BITS(5) + 257;
824 DROPBITS(5);
825 state->ndist = BITS(5) + 1;
826 DROPBITS(5);
827 state->ncode = BITS(4) + 4;
828 DROPBITS(4);
829 #ifndef PKZIP_BUG_WORKAROUND
830 if (state->nlen > 286 || state->ndist > 30) {
831 strm->msg = (char *)"too many length or distance symbols";
832 state->mode = BAD;
833 break;
834 }
835 #endif
836 Tracev((stderr, "inflate: table sizes ok\n"));
837 state->have = 0;
838 state->mode = LENLENS;
839 case LENLENS:
840 while (state->have < state->ncode) {
841 NEEDBITS(3);
842 state->lens[order[state->have++]] = (unsigned short)BITS(3);
843 DROPBITS(3);
844 }
845 while (state->have < 19)
846 state->lens[order[state->have++]] = 0;
847 state->next = state->codes;
848 state->lencode = (code const FAR *)(state->next);
849 state->lenbits = 7;
850 ret = inflate_table(CODES, state->lens, 19, &(state->next),
851 &(state->lenbits), state->work);
852 if (ret) {
853 strm->msg = (char *)"invalid code lengths set";
854 state->mode = BAD;
855 break;
856 }
857 Tracev((stderr, "inflate: code lengths ok\n"));
858 state->have = 0;
859 state->mode = CODELENS;
860 case CODELENS:
861 while (state->have < state->nlen + state->ndist) {
862 for (;;) {
863 thisx = state->lencode[BITS(state->lenbits)];
864 if ((unsigned)(thisx.bits) <= bits) break;
865 PULLBYTE();
866 }
867 if (thisx.val < 16) {
868 NEEDBITS(thisx.bits);
869 DROPBITS(thisx.bits);
870 state->lens[state->have++] = thisx.val;
871 }
872 else {
873 if (thisx.val == 16) {
874 NEEDBITS(thisx.bits + 2);
875 DROPBITS(thisx.bits);
876 if (state->have == 0) {
877 strm->msg = (char *)"invalid bit length repeat";
878 state->mode = BAD;
879 break;
880 }
881 len = state->lens[state->have - 1];
882 copy = 3 + BITS(2);
883 DROPBITS(2);
884 }
885 else if (thisx.val == 17) {
886 NEEDBITS(thisx.bits + 3);
887 DROPBITS(thisx.bits);
888 len = 0;
889 copy = 3 + BITS(3);
890 DROPBITS(3);
891 }
892 else {
893 NEEDBITS(thisx.bits + 7);
894 DROPBITS(thisx.bits);
895 len = 0;
896 copy = 11 + BITS(7);
897 DROPBITS(7);
898 }
899 if (state->have + copy > state->nlen + state->ndist) {
900 strm->msg = (char *)"invalid bit length repeat";
901 state->mode = BAD;
902 break;
903 }
904 while (copy--)
905 state->lens[state->have++] = (unsigned short)len;
906 }
907 }
908
909 /* handle error breaks in while */
910 if (state->mode == BAD) break;
911
912 /* build code tables */
913 state->next = state->codes;
914 state->lencode = (code const FAR *)(state->next);
915 state->lenbits = 9;
916 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
917 &(state->lenbits), state->work);
918 if (ret) {
919 strm->msg = (char *)"invalid literal/lengths set";
920 state->mode = BAD;
921 break;
922 }
923 state->distcode = (code const FAR *)(state->next);
924 state->distbits = 6;
925 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
926 &(state->next), &(state->distbits), state->work);
927 if (ret) {
928 strm->msg = (char *)"invalid distances set";
929 state->mode = BAD;
930 break;
931 }
932 Tracev((stderr, "inflate: codes ok\n"));
933 state->mode = LEN;
934 case LEN:
935 if (have >= 6 && left >= 258) {
936 RESTORE();
937 inflate_fast(strm, out);
938 LOAD();
939 break;
940 }
941 for (;;) {
942 thisx = state->lencode[BITS(state->lenbits)];
943 if ((unsigned)(thisx.bits) <= bits) break;
944 PULLBYTE();
945 }
946 if (thisx.op && (thisx.op & 0xf0) == 0) {
947 last = thisx;
948 for (;;) {
949 thisx = state->lencode[last.val +
950 (BITS(last.bits + last.op) >> last.bits)];
951 if ((unsigned)(last.bits + thisx.bits) <= bits) break;
952 PULLBYTE();
953 }
954 DROPBITS(last.bits);
955 }
956 DROPBITS(thisx.bits);
957 state->length = (unsigned)thisx.val;
958 if ((int)(thisx.op) == 0) {
959 Tracevv((stderr, thisx.val >= 0x20 && thisx.val < 0x7f ?
960 "inflate: literal '%c'\n" :
961 "inflate: literal 0x%02x\n", thisx.val));
962 state->mode = LIT;
963 break;
964 }
965 if (thisx.op & 32) {
966 Tracevv((stderr, "inflate: end of block\n"));
967 state->mode = TYPE;
968 break;
969 }
970 if (thisx.op & 64) {
971 strm->msg = (char *)"invalid literal/length code";
972 state->mode = BAD;
973 break;
974 }
975 state->extra = (unsigned)(thisx.op) & 15;
976 state->mode = LENEXT;
977 case LENEXT:
978 if (state->extra) {
979 NEEDBITS(state->extra);
980 state->length += BITS(state->extra);
981 DROPBITS(state->extra);
982 }
983 Tracevv((stderr, "inflate: length %u\n", state->length));
984 state->mode = DIST;
985 case DIST:
986 for (;;) {
987 thisx = state->distcode[BITS(state->distbits)];
988 if ((unsigned)(thisx.bits) <= bits) break;
989 PULLBYTE();
990 }
991 if ((thisx.op & 0xf0) == 0) {
992 last = thisx;
993 for (;;) {
994 thisx = state->distcode[last.val +
995 (BITS(last.bits + last.op) >> last.bits)];
996 if ((unsigned)(last.bits + thisx.bits) <= bits) break;
997 PULLBYTE();
998 }
999 DROPBITS(last.bits);
1000 }
1001 DROPBITS(thisx.bits);
1002 if (thisx.op & 64) {
1003 strm->msg = (char *)"invalid distance code";
1004 state->mode = BAD;
1005 break;
1006 }
1007 state->offset = (unsigned)thisx.val;
1008 state->extra = (unsigned)(thisx.op) & 15;
1009 state->mode = DISTEXT;
1010 case DISTEXT:
1011 if (state->extra) {
1012 NEEDBITS(state->extra);
1013 state->offset += BITS(state->extra);
1014 DROPBITS(state->extra);
1015 }
1016 #ifdef INFLATE_STRICT
1017 if (state->offset > state->dmax) {
1018 strm->msg = (char *)"invalid distance too far back";
1019 state->mode = BAD;
1020 break;
1021 }
1022 #endif
1023 if (state->offset > state->whave + out - left) {
1024 strm->msg = (char *)"invalid distance too far back";
1025 state->mode = BAD;
1026 break;
1027 }
1028 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1029 state->mode = MATCH;
1030 case MATCH:
1031 if (left == 0) goto inf_leave;
1032 copy = out - left;
1033 if (state->offset > copy) { /* copy from window */
1034 copy = state->offset - copy;
1035 if (copy > state->write) {
1036 copy -= state->write;
1037 from = state->window + (state->wsize - copy);
1038 }
1039 else
1040 from = state->window + (state->write - copy);
1041 if (copy > state->length) copy = state->length;
1042 }
1043 else { /* copy from output */
1044 from = put - state->offset;
1045 copy = state->length;
1046 }
1047 if (copy > left) copy = left;
1048 left -= copy;
1049 state->length -= copy;
1050 do {
1051 *put++ = *from++;
1052 } while (--copy);
1053 if (state->length == 0) state->mode = LEN;
1054 break;
1055 case LIT:
1056 if (left == 0) goto inf_leave;
1057 *put++ = (unsigned char)(state->length);
1058 left--;
1059 state->mode = LEN;
1060 break;
1061 case CHECK:
1062 if (state->wrap) {
1063 NEEDBITS(32);
1064 out -= left;
1065 strm->total_out += out;
1066 state->total += out;
1067 if (out)
1068 strm->adler = state->check =
1069 UPDATE(state->check, put - out, out);
1070 out = left;
1071 if ((
1072 #ifdef GUNZIP
1073 state->flags ? hold :
1074 #endif
1075 REVERSE(hold)) != state->check) {
1076 strm->msg = (char *)"incorrect data check";
1077 state->mode = BAD;
1078 break;
1079 }
1080 INITBITS();
1081 Tracev((stderr, "inflate: check matches trailer\n"));
1082 }
1083 #ifdef GUNZIP
1084 state->mode = LENGTH;
1085 case LENGTH:
1086 if (state->wrap && state->flags) {
1087 NEEDBITS(32);
1088 if (hold != (state->total & 0xffffffffUL)) {
1089 strm->msg = (char *)"incorrect length check";
1090 state->mode = BAD;
1091 break;
1092 }
1093 INITBITS();
1094 Tracev((stderr, "inflate: length matches trailer\n"));
1095 }
1096 #endif
1097 state->mode = DONE;
1098 case DONE:
1099 ret = Z_STREAM_END;
1100 goto inf_leave;
1101 case BAD:
1102 ret = Z_DATA_ERROR;
1103 goto inf_leave;
1104 case MEM:
1105 return Z_MEM_ERROR;
1106 case SYNC:
1107 default:
1108 return Z_STREAM_ERROR;
1109 }
1110
1111 /*
1112 Return from inflate(), updating the total counts and the check value.
1113 If there was no progress during the inflate() call, return a buffer
1114 error. Call updatewindow() to create and/or update the window state.
1115 Note: a memory error from inflate() is non-recoverable.
1116 */
1117 inf_leave:
1118 RESTORE();
1119 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1120 if (updatewindow(strm, out)) {
1121 state->mode = MEM;
1122 return Z_MEM_ERROR;
1123 }
1124 in -= strm->avail_in;
1125 out -= strm->avail_out;
1126 strm->total_in += in;
1127 strm->total_out += out;
1128 state->total += out;
1129 if (state->wrap && out)
1130 strm->adler = state->check =
1131 UPDATE(state->check, strm->next_out - out, out);
1132 strm->data_type = state->bits + (state->last ? 64 : 0) +
1133 (state->mode == TYPE ? 128 : 0);
1134 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1135 ret = Z_BUF_ERROR;
1136 return ret;
1137 }
1138
inflateEnd(z_streamp strm)1139 int ZEXPORT inflateEnd (z_streamp strm)
1140 {
1141 struct inflate_state FAR *state;
1142 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1143 return Z_STREAM_ERROR;
1144 state = (struct inflate_state FAR *)strm->state;
1145 if (state->window != Z_NULL) ZFREE(strm, state->window);
1146 ZFREE(strm, strm->state);
1147 strm->state = Z_NULL;
1148 Tracev((stderr, "inflate: end\n"));
1149 return Z_OK;
1150 }
1151
inflateSetDictionary(z_streamp strm,const Bytef * dictionary,uInt dictLength)1152 int ZEXPORT inflateSetDictionary (z_streamp strm, const Bytef *dictionary, uInt dictLength)
1153 {
1154 struct inflate_state FAR *state;
1155 unsigned long id_;
1156
1157 /* check state */
1158 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1159 state = (struct inflate_state FAR *)strm->state;
1160 if (state->wrap != 0 && state->mode != DICT)
1161 return Z_STREAM_ERROR;
1162
1163 /* check for correct dictionary id */
1164 if (state->mode == DICT) {
1165 id_ = adler32(0L, Z_NULL, 0);
1166 id_ = adler32(id_, dictionary, dictLength);
1167 if (id_ != state->check)
1168 return Z_DATA_ERROR;
1169 }
1170
1171 /* copy dictionary to window */
1172 if (updatewindow(strm, strm->avail_out)) {
1173 state->mode = MEM;
1174 return Z_MEM_ERROR;
1175 }
1176 if (dictLength > state->wsize) {
1177 zmemcpy(state->window, dictionary + dictLength - state->wsize,
1178 state->wsize);
1179 state->whave = state->wsize;
1180 }
1181 else {
1182 zmemcpy(state->window + state->wsize - dictLength, dictionary,
1183 dictLength);
1184 state->whave = dictLength;
1185 }
1186 state->havedict = 1;
1187 Tracev((stderr, "inflate: dictionary set\n"));
1188 return Z_OK;
1189 }
1190
inflateGetHeader(z_streamp strm,gz_headerp head)1191 int ZEXPORT inflateGetHeader (z_streamp strm, gz_headerp head)
1192 {
1193 struct inflate_state FAR *state;
1194
1195 /* check state */
1196 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1197 state = (struct inflate_state FAR *)strm->state;
1198 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1199
1200 /* save header structure */
1201 state->head = head;
1202 head->done = 0;
1203 return Z_OK;
1204 }
1205
1206 /*
1207 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1208 or when out of input. When called, *have is the number of pattern bytes
1209 found in order so far, in 0..3. On return *have is updated to the new
1210 state. If on return *have equals four, then the pattern was found and the
1211 return value is how many bytes were read including the last byte of the
1212 pattern. If *have is less than four, then the pattern has not been found
1213 yet and the return value is len. In the latter case, syncsearch() can be
1214 called again with more data and the *have state. *have is initialized to
1215 zero for the first call.
1216 */
syncsearch(unsigned FAR * have,unsigned char FAR * buf,unsigned len)1217 local unsigned syncsearch (unsigned FAR *have, unsigned char FAR *buf, unsigned len)
1218 {
1219 unsigned got;
1220 unsigned next;
1221
1222 got = *have;
1223 next = 0;
1224 while (next < len && got < 4) {
1225 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1226 got++;
1227 else if (buf[next])
1228 got = 0;
1229 else
1230 got = 4 - got;
1231 next++;
1232 }
1233 *have = got;
1234 return next;
1235 }
1236
inflateSync(z_streamp strm)1237 int ZEXPORT inflateSync (z_streamp strm)
1238 {
1239 unsigned len; /* number of bytes to look at or looked at */
1240 unsigned long in, out; /* temporary to save total_in and total_out */
1241 unsigned char buf[4]; /* to restore bit buffer to byte string */
1242 struct inflate_state FAR *state;
1243
1244 /* check parameters */
1245 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1246 state = (struct inflate_state FAR *)strm->state;
1247 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1248
1249 /* if first time, start search in bit buffer */
1250 if (state->mode != SYNC) {
1251 state->mode = SYNC;
1252 state->hold <<= state->bits & 7;
1253 state->bits -= state->bits & 7;
1254 len = 0;
1255 while (state->bits >= 8) {
1256 buf[len++] = (unsigned char)(state->hold);
1257 state->hold >>= 8;
1258 state->bits -= 8;
1259 }
1260 state->have = 0;
1261 syncsearch(&(state->have), buf, len);
1262 }
1263
1264 /* search available input */
1265 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1266 strm->avail_in -= len;
1267 strm->next_in += len;
1268 strm->total_in += len;
1269
1270 /* return no joy or set up to restart inflate() on a new block */
1271 if (state->have != 4) return Z_DATA_ERROR;
1272 in = strm->total_in; out = strm->total_out;
1273 inflateReset(strm);
1274 strm->total_in = in; strm->total_out = out;
1275 state->mode = TYPE;
1276 return Z_OK;
1277 }
1278
1279 /*
1280 Returns true if inflate is currently at the end of a block generated by
1281 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1282 implementation to provide an additional safety check. PPP uses
1283 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1284 block. When decompressing, PPP checks that at the end of input packet,
1285 inflate is waiting for these length bytes.
1286 */
inflateSyncPoint(z_streamp strm)1287 int ZEXPORT inflateSyncPoint (z_streamp strm)
1288 {
1289 struct inflate_state FAR *state;
1290
1291 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1292 state = (struct inflate_state FAR *)strm->state;
1293 return state->mode == STORED && state->bits == 0;
1294 }
1295
inflateCopy(z_streamp dest,z_streamp source)1296 int ZEXPORT inflateCopy(z_streamp dest, z_streamp source)
1297 {
1298 struct inflate_state FAR *state;
1299 struct inflate_state FAR *copy;
1300 unsigned char FAR *window;
1301 unsigned wsize;
1302
1303 /* check input */
1304 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1305 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1306 return Z_STREAM_ERROR;
1307 state = (struct inflate_state FAR *)source->state;
1308
1309 /* allocate space */
1310 copy = (struct inflate_state FAR *)
1311 ZALLOC(source, 1, sizeof(struct inflate_state));
1312 if (copy == Z_NULL) return Z_MEM_ERROR;
1313 window = Z_NULL;
1314 if (state->window != Z_NULL) {
1315 window = (unsigned char FAR *)
1316 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1317 if (window == Z_NULL) {
1318 ZFREE(source, copy);
1319 return Z_MEM_ERROR;
1320 }
1321 }
1322
1323 /* copy state */
1324 zmemcpy(dest, source, sizeof(z_stream));
1325 zmemcpy(copy, state, sizeof(struct inflate_state));
1326 if (state->lencode >= state->codes &&
1327 state->lencode <= state->codes + ENOUGH - 1) {
1328 copy->lencode = copy->codes + (state->lencode - state->codes);
1329 copy->distcode = copy->codes + (state->distcode - state->codes);
1330 }
1331 copy->next = copy->codes + (state->next - state->codes);
1332 if (window != Z_NULL) {
1333 wsize = 1U << state->wbits;
1334 zmemcpy(window, state->window, wsize);
1335 }
1336 copy->window = window;
1337 dest->state = (struct internal_state FAR *)copy;
1338 return Z_OK;
1339 }
1340