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
5 local void fixedtables OF((struct inflate_state FAR *state));
6 local int updatewindow OF((z_streamp strm, unsigned out));
8 int ZEXPORT inflateReset(strm)
11 struct inflate_state FAR *state;
13 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
14 state = (struct inflate_state FAR *)strm->state;
15 strm->total_in = strm->total_out = state->total = 0;
17 strm->adler = 1; /* to support ill-conceived Java test suite */
28 state->lencode = state->distcode = state->next = state->codes;
30 Tracev((stderr, "inflate: reset\n"));
34 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
40 struct inflate_state FAR *state;
42 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
43 stream_size != (int)(sizeof(z_stream)))
44 return Z_VERSION_ERROR;
45 if (strm == Z_NULL) return Z_STREAM_ERROR;
46 strm->msg = Z_NULL; /* in case we return an error */
47 if (strm->zalloc == (alloc_func)0) {
48 strm->zalloc = zcalloc;
49 strm->opaque = (voidpf)0;
51 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
52 state = (struct inflate_state FAR *)
53 ZALLOC(strm, 1, sizeof(struct inflate_state));
54 if (state == Z_NULL) return Z_MEM_ERROR;
55 Tracev((stderr, "inflate: allocated\n"));
56 strm->state = (struct internal_state FAR *)state;
59 windowBits = -windowBits;
62 state->wrap = (windowBits >> 4) + 1;
64 if (windowBits < 48) windowBits &= 15;
67 if (windowBits < 8 || windowBits > 15) {
70 return Z_STREAM_ERROR;
72 state->wbits = (unsigned)windowBits;
73 state->window = Z_NULL;
74 return inflateReset(strm);
77 int ZEXPORT inflateInit_(strm, version, stream_size)
82 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
85 local void fixedtables(state)
86 struct inflate_state FAR *state;
88 state->lencode = lenfix;
90 state->distcode = distfix;
95 Update the window with the last wsize (normally 32K) bytes written before
96 returning. If window does not exist yet, create it. This is only called
97 when a window is already in use, or when output has been written during this
98 inflate call, but the end of the deflate stream has not been reached yet.
99 It is also called to create a window for dictionary data when a dictionary
102 Providing output buffers larger than 32K to inflate() should provide a speed
103 advantage, since only the last 32K of output is copied to the sliding window
104 upon return from inflate(), and since all distances after the first 32K of
105 output will fall in the output data, making match copies simpler and faster.
106 The advantage may be dependent on the size of the processor's data caches.
108 local int updatewindow(strm, out)
112 struct inflate_state FAR *state;
115 state = (struct inflate_state FAR *)strm->state;
117 /* if it hasn't been done already, allocate space for the window */
118 if (state->window == Z_NULL) {
119 state->window = (unsigned char FAR *)
120 ZALLOC(strm, 1U << state->wbits,
121 sizeof(unsigned char));
122 if (state->window == Z_NULL) return 1;
125 /* if window not in use yet, initialize */
126 if (state->wsize == 0) {
127 state->wsize = 1U << state->wbits;
132 /* copy state->wsize or less output bytes into the circular window */
133 copy = out - strm->avail_out;
134 if (copy >= state->wsize) {
135 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
137 state->whave = state->wsize;
140 dist = state->wsize - state->write;
141 if (dist > copy) dist = copy;
142 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
145 zmemcpy(state->window, strm->next_out - copy, copy);
147 state->whave = state->wsize;
150 state->write += dist;
151 if (state->write == state->wsize) state->write = 0;
152 if (state->whave < state->wsize) state->whave += dist;
158 /* Macros for inflate(): */
160 /* check function to use adler32() for zlib or crc32() for gzip */
162 # define UPDATE(check, buf, len) \
163 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
165 # define UPDATE(check, buf, len) adler32(check, buf, len)
168 /* check macros for header crc */
170 # define CRC2(check, word) \
172 hbuf[0] = (unsigned char)(word); \
173 hbuf[1] = (unsigned char)((word) >> 8); \
174 check = crc32(check, hbuf, 2); \
177 # define CRC4(check, word) \
179 hbuf[0] = (unsigned char)(word); \
180 hbuf[1] = (unsigned char)((word) >> 8); \
181 hbuf[2] = (unsigned char)((word) >> 16); \
182 hbuf[3] = (unsigned char)((word) >> 24); \
183 check = crc32(check, hbuf, 4); \
187 /* Load registers with state in inflate() for speed */
190 put = strm->next_out; \
191 left = strm->avail_out; \
192 next = strm->next_in; \
193 have = strm->avail_in; \
194 hold = state->hold; \
195 bits = state->bits; \
198 /* Restore state from registers in inflate() */
201 strm->next_out = put; \
202 strm->avail_out = left; \
203 strm->next_in = next; \
204 strm->avail_in = have; \
205 state->hold = hold; \
206 state->bits = bits; \
209 /* Clear the input bit accumulator */
216 /* Get a byte of input into the bit accumulator, or return from inflate()
217 if there is no input available. */
220 if (have == 0) goto inf_leave; \
222 hold += (unsigned long)(*next++) << bits; \
226 /* Assure that there are at least n bits in the bit accumulator. If there is
227 not enough available input to do that, then return from inflate(). */
228 #define NEEDBITS(n) \
230 while (bits < (unsigned)(n)) \
234 /* Return the low n bits of the bit accumulator (n < 16) */
236 ((unsigned)hold & ((1U << (n)) - 1))
238 /* Remove n bits from the bit accumulator */
239 #define DROPBITS(n) \
242 bits -= (unsigned)(n); \
245 /* Remove zero to seven bits as needed to go to a byte boundary */
252 /* Reverse the bytes in a 32-bit value */
254 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
255 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
258 inflate() uses a state machine to process as much input data and generate as
259 much output data as possible before returning. The state machine is
260 structured roughly as follows:
262 for (;;) switch (state) {
265 if (not enough input data or output space to make progress)
267 ... make progress ...
273 so when inflate() is called again, the same case is attempted again, and
274 if the appropriate resources are provided, the machine proceeds to the
275 next state. The NEEDBITS() macro is usually the way the state evaluates
276 whether it can proceed or should return. NEEDBITS() does the return if
277 the requested bits are not available. The typical use of the BITS macros
281 ... do something with BITS(n) ...
284 where NEEDBITS(n) either returns from inflate() if there isn't enough
285 input left to load n bits into the accumulator, or it continues. BITS(n)
286 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
287 the low n bits off the accumulator. INITBITS() clears the accumulator
288 and sets the number of available bits to zero. BYTEBITS() discards just
289 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
290 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
292 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
293 if there is no input available. The decoding of variable length codes uses
294 PULLBYTE() directly in order to pull just enough bytes to decode the next
297 Some states loop until they get enough input, making sure that enough
298 state information is maintained to continue the loop where it left off
299 if NEEDBITS() returns in the loop. For example, want, need, and keep
300 would all have to actually be part of the saved state in case NEEDBITS()
304 while (want < need) {
306 keep[want++] = BITS(n);
312 As shown above, if the next state is also the next case, then the break
315 A state may also return if there is not enough output space available to
316 complete that state. Those states are copying stored data, writing a
317 literal byte, and copying a matching string.
319 When returning, a "goto inf_leave" is used to update the total counters,
320 update the check value, and determine whether any progress has been made
321 during that inflate() call in order to return the proper return code.
322 Progress is defined as a change in either strm->avail_in or strm->avail_out.
323 When there is a window, goto inf_leave will update the window with the last
324 output written. If a goto inf_leave occurs in the middle of decompression
325 and there is no window currently, goto inf_leave will create one and copy
326 output to the window for the next call of inflate().
328 In this implementation, the flush parameter of inflate() only affects the
329 return code (per zlib.h). inflate() always writes as much as possible to
330 strm->next_out, given the space available and the provided input--the effect
331 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
332 the allocation of and copying into a sliding window until necessary, which
333 provides the effect documented in zlib.h for Z_FINISH when the entire input
334 stream available. So the only thing the flush parameter actually does is:
335 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
336 will return Z_BUF_ERROR if it has not reached the end of the stream.
338 int ZEXPORT inflate(strm, flush)
342 struct inflate_state FAR *state;
343 unsigned char FAR *next; /* next input */
344 unsigned char FAR *put; /* next output */
345 unsigned have, left; /* available input and output */
346 unsigned long hold; /* bit buffer */
347 unsigned bits; /* bits in bit buffer */
348 unsigned in, out; /* save starting available input and output */
349 unsigned copy; /* number of stored or match bytes to copy */
350 unsigned char FAR *from; /* where to copy match bytes from */
351 code this; /* current decoding table entry */
352 code last; /* parent table entry */
353 unsigned len; /* length to copy for repeats, bits to drop */
354 int ret; /* return code */
356 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
358 static const unsigned short order[19] = /* permutation of code lengths */
359 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
361 if (strm == Z_NULL || strm->state == Z_NULL ||
362 (strm->next_in == Z_NULL && strm->avail_in != 0))
363 return Z_STREAM_ERROR;
365 state = (struct inflate_state FAR *)strm->state;
366 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
372 switch (state->mode) {
374 if (state->wrap == 0) {
375 state->mode = TYPEDO;
380 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
381 state->check = crc32(0L, Z_NULL, 0);
382 CRC2(state->check, hold);
387 state->flags = 0; /* expect zlib header */
388 if (state->head != Z_NULL)
389 state->head->done = -1;
390 if (!(state->wrap & 1) || /* check if zlib header allowed */
394 ((BITS(8) << 8) + (hold >> 8)) % 31) {
395 strm->msg = (char *)"incorrect header check";
399 if (BITS(4) != Z_DEFLATED) {
400 strm->msg = (char *)"unknown compression method";
406 if (len > state->wbits) {
407 strm->msg = (char *)"invalid window size";
411 state->dmax = 1U << len;
412 Tracev((stderr, "inflate: zlib header ok\n"));
413 strm->adler = state->check = adler32(0L, Z_NULL, 0);
414 state->mode = hold & 0x200 ? DICTID : TYPE;
420 state->flags = (int)(hold);
421 if ((state->flags & 0xff) != Z_DEFLATED) {
422 strm->msg = (char *)"unknown compression method";
426 if (state->flags & 0xe000) {
427 strm->msg = (char *)"unknown header flags set";
431 if (state->head != Z_NULL)
432 state->head->text = (int)((hold >> 8) & 1);
433 if (state->flags & 0x0200) CRC2(state->check, hold);
438 if (state->head != Z_NULL)
439 state->head->time = hold;
440 if (state->flags & 0x0200) CRC4(state->check, hold);
445 if (state->head != Z_NULL) {
446 state->head->xflags = (int)(hold & 0xff);
447 state->head->os = (int)(hold >> 8);
449 if (state->flags & 0x0200) CRC2(state->check, hold);
453 if (state->flags & 0x0400) {
455 state->length = (unsigned)(hold);
456 if (state->head != Z_NULL)
457 state->head->extra_len = (unsigned)hold;
458 if (state->flags & 0x0200) CRC2(state->check, hold);
461 else if (state->head != Z_NULL)
462 state->head->extra = Z_NULL;
465 if (state->flags & 0x0400) {
466 copy = state->length;
467 if (copy > have) copy = have;
469 if (state->head != Z_NULL &&
470 state->head->extra != Z_NULL) {
471 len = state->head->extra_len - state->length;
472 zmemcpy(state->head->extra + len, next,
473 len + copy > state->head->extra_max ?
474 state->head->extra_max - len : copy);
476 if (state->flags & 0x0200)
477 state->check = crc32(state->check, next, copy);
480 state->length -= copy;
482 if (state->length) goto inf_leave;
487 if (state->flags & 0x0800) {
488 if (have == 0) goto inf_leave;
491 len = (unsigned)(next[copy++]);
492 if (state->head != Z_NULL &&
493 state->head->name != Z_NULL &&
494 state->length < state->head->name_max)
495 state->head->name[state->length++] = len;
496 } while (len && copy < have);
497 if (state->flags & 0x0200)
498 state->check = crc32(state->check, next, copy);
501 if (len) goto inf_leave;
503 else if (state->head != Z_NULL)
504 state->head->name = Z_NULL;
506 state->mode = COMMENT;
508 if (state->flags & 0x1000) {
509 if (have == 0) goto inf_leave;
512 len = (unsigned)(next[copy++]);
513 if (state->head != Z_NULL &&
514 state->head->comment != Z_NULL &&
515 state->length < state->head->comm_max)
516 state->head->comment[state->length++] = len;
517 } while (len && copy < have);
518 if (state->flags & 0x0200)
519 state->check = crc32(state->check, next, copy);
522 if (len) goto inf_leave;
524 else if (state->head != Z_NULL)
525 state->head->comment = Z_NULL;
528 if (state->flags & 0x0200) {
530 if (hold != (state->check & 0xffff)) {
531 strm->msg = (char *)"header crc mismatch";
537 if (state->head != Z_NULL) {
538 state->head->hcrc = (int)((state->flags >> 9) & 1);
539 state->head->done = 1;
541 strm->adler = state->check = crc32(0L, Z_NULL, 0);
547 strm->adler = state->check = REVERSE(hold);
551 if (state->havedict == 0) {
555 strm->adler = state->check = adler32(0L, Z_NULL, 0);
559 if (flush == Z_BLOCK) goto inf_leave;
567 state->last = BITS(1);
570 case 0: /* stored block */
571 Tracev((stderr, "inflate: stored block%s\n",
572 state->last ? " (last)" : ""));
573 state->mode = STORED;
575 case 1: /* fixed block */
577 Tracev((stderr, "inflate: fixed codes block%s\n",
578 state->last ? " (last)" : ""));
579 state->mode = LEN; /* decode codes */
581 case 2: /* dynamic block */
582 Tracev((stderr, "inflate: dynamic codes block%s\n",
583 state->last ? " (last)" : ""));
587 strm->msg = (char *)"invalid block type";
593 BYTEBITS(); /* go to byte boundary */
595 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
596 strm->msg = (char *)"invalid stored block lengths";
600 state->length = (unsigned)hold & 0xffff;
601 Tracev((stderr, "inflate: stored length %u\n",
606 copy = state->length;
608 if (copy > have) copy = have;
609 if (copy > left) copy = left;
610 if (copy == 0) goto inf_leave;
611 zmemcpy(put, next, copy);
616 state->length -= copy;
619 Tracev((stderr, "inflate: stored end\n"));
624 state->nlen = BITS(5) + 257;
626 state->ndist = BITS(5) + 1;
628 state->ncode = BITS(4) + 4;
630 #ifndef PKZIP_BUG_WORKAROUND
631 if (state->nlen > 286 || state->ndist > 30) {
632 strm->msg = (char *)"too many length or distance symbols";
637 Tracev((stderr, "inflate: table sizes ok\n"));
639 state->mode = LENLENS;
641 while (state->have < state->ncode) {
643 state->lens[order[state->have++]] = (unsigned short)BITS(3);
646 while (state->have < 19)
647 state->lens[order[state->have++]] = 0;
648 state->next = state->codes;
649 state->lencode = (code const FAR *)(state->next);
651 ret = inflate_table(CODES, state->lens, 19, &(state->next),
652 &(state->lenbits), state->work);
654 strm->msg = (char *)"invalid code lengths set";
658 Tracev((stderr, "inflate: code lengths ok\n"));
660 state->mode = CODELENS;
662 while (state->have < state->nlen + state->ndist) {
664 this = state->lencode[BITS(state->lenbits)];
665 if ((unsigned)(this.bits) <= bits) break;
671 state->lens[state->have++] = this.val;
674 if (this.val == 16) {
675 NEEDBITS(this.bits + 2);
677 if (state->have == 0) {
678 strm->msg = (char *)"invalid bit length repeat";
682 len = state->lens[state->have - 1];
686 else if (this.val == 17) {
687 NEEDBITS(this.bits + 3);
694 NEEDBITS(this.bits + 7);
700 if (state->have + copy > state->nlen + state->ndist) {
701 strm->msg = (char *)"invalid bit length repeat";
706 state->lens[state->have++] = (unsigned short)len;
710 /* handle error breaks in while */
711 if (state->mode == BAD) break;
713 /* build code tables */
714 state->next = state->codes;
715 state->lencode = (code const FAR *)(state->next);
717 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
718 &(state->lenbits), state->work);
720 strm->msg = (char *)"invalid literal/lengths set";
724 state->distcode = (code const FAR *)(state->next);
726 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
727 &(state->next), &(state->distbits), state->work);
729 strm->msg = (char *)"invalid distances set";
733 Tracev((stderr, "inflate: codes ok\n"));
737 if (have >= 6 && left >= 258) {
739 inflate_fast(strm, out);
744 this = state->lencode[BITS(state->lenbits)];
745 if ((unsigned)(this.bits) <= bits) break;
748 if (this.op && (this.op & 0xf0) == 0) {
751 this = state->lencode[last.val +
752 (BITS(last.bits + last.op) >> last.bits)];
753 if ((unsigned)(last.bits + this.bits) <= bits) break;
759 state->length = (unsigned)this.val;
760 if ((int)(this.op) == 0) {
761 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
762 "inflate: literal '%c'\n" :
763 "inflate: literal 0x%02x\n", this.val));
768 Tracevv((stderr, "inflate: end of block\n"));
773 strm->msg = (char *)"invalid literal/length code";
777 state->extra = (unsigned)(this.op) & 15;
778 state->mode = LENEXT;
781 NEEDBITS(state->extra);
782 state->length += BITS(state->extra);
783 DROPBITS(state->extra);
785 Tracevv((stderr, "inflate: length %u\n", state->length));
789 this = state->distcode[BITS(state->distbits)];
790 if ((unsigned)(this.bits) <= bits) break;
793 if ((this.op & 0xf0) == 0) {
796 this = state->distcode[last.val +
797 (BITS(last.bits + last.op) >> last.bits)];
798 if ((unsigned)(last.bits + this.bits) <= bits) break;
805 strm->msg = (char *)"invalid distance code";
809 state->offset = (unsigned)this.val;
810 state->extra = (unsigned)(this.op) & 15;
811 state->mode = DISTEXT;
814 NEEDBITS(state->extra);
815 state->offset += BITS(state->extra);
816 DROPBITS(state->extra);
818 #ifdef INFLATE_STRICT
819 if (state->offset > state->dmax) {
820 strm->msg = (char *)"invalid distance too far back";
825 if (state->offset > state->whave + out - left) {
826 strm->msg = (char *)"invalid distance too far back";
830 Tracevv((stderr, "inflate: distance %u\n", state->offset));
833 if (left == 0) goto inf_leave;
835 if (state->offset > copy) { /* copy from window */
836 copy = state->offset - copy;
837 if (copy > state->write) {
838 copy -= state->write;
839 from = state->window + (state->wsize - copy);
842 from = state->window + (state->write - copy);
843 if (copy > state->length) copy = state->length;
845 else { /* copy from output */
846 from = put - state->offset;
847 copy = state->length;
849 if (copy > left) copy = left;
851 state->length -= copy;
855 if (state->length == 0) state->mode = LEN;
858 if (left == 0) goto inf_leave;
859 *put++ = (unsigned char)(state->length);
867 strm->total_out += out;
870 strm->adler = state->check =
871 UPDATE(state->check, put - out, out);
875 state->flags ? hold :
877 REVERSE(hold)) != state->check) {
878 strm->msg = (char *)"incorrect data check";
883 Tracev((stderr, "inflate: check matches trailer\n"));
886 state->mode = LENGTH;
888 if (state->wrap && state->flags) {
890 if (hold != (state->total & 0xffffffffUL)) {
891 strm->msg = (char *)"incorrect length check";
896 Tracev((stderr, "inflate: length matches trailer\n"));
910 return Z_STREAM_ERROR;
914 Return from inflate(), updating the total counts and the check value.
915 If there was no progress during the inflate() call, return a buffer
916 error. Call updatewindow() to create and/or update the window state.
917 Note: a memory error from inflate() is non-recoverable.
921 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
922 if (updatewindow(strm, out)) {
926 in -= strm->avail_in;
927 out -= strm->avail_out;
928 strm->total_in += in;
929 strm->total_out += out;
931 if (state->wrap && out)
932 strm->adler = state->check =
933 UPDATE(state->check, strm->next_out - out, out);
934 strm->data_type = state->bits + (state->last ? 64 : 0) +
935 (state->mode == TYPE ? 128 : 0);
936 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
941 int ZEXPORT inflateEnd(strm)
944 struct inflate_state FAR *state;
945 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
946 return Z_STREAM_ERROR;
947 state = (struct inflate_state FAR *)strm->state;
948 if (state->window != Z_NULL) {
950 ZFREE(strm, state->window);
952 ZFREE(strm, strm->state);
953 strm->state = Z_NULL;
954 Tracev((stderr, "inflate: end\n"));