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