1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2022 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
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
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
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
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
41 * 1.2.beta4 1 Jan 2003
42 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
43 * - Move a comment on output buffer sizes from inffast.c to inflate.c
44 * - Add comments in inffast.c to introduce the inflate_fast() routine
45 * - Rearrange window copies in inflate_fast() for speed and simplification
46 * - Unroll last copy for window match in inflate_fast()
47 * - Use local copies of window variables in inflate_fast() for speed
48 * - Pull out common wnext == 0 case for speed in inflate_fast()
49 * - Make op and len in inflate_fast() unsigned for consistency
50 * - Add FAR to lcode and dcode declarations in inflate_fast()
51 * - Simplified bad distance check in inflate_fast()
52 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
53 * source file infback.c to provide a call-back interface to inflate for
54 * programs like gzip and unzip -- uses window as output buffer to avoid
57 * 1.2.beta5 1 Jan 2003
58 * - Improved inflateBack() interface to allow the caller to provide initial
60 * - Fixed stored blocks bug in inflateBack()
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 *
69 * 1.2.beta7 27 Jan 2003
70 * - Changed many types to unsigned or unsigned short to avoid warnings
71 * - Added inflateCopy() function
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()
80 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
94 /* function prototypes */
95 local
int inflateStateCheck
OF((z_streamp strm
));
96 local
void fixedtables
OF((struct inflate_state FAR
*state
));
97 local
int updatewindow
OF((z_streamp strm
, const unsigned char FAR
*end
,
100 void makefixed
OF((void));
102 local
unsigned syncsearch
OF((unsigned FAR
*have
, const unsigned char FAR
*buf
,
105 local
int inflateStateCheck(strm
)
108 struct inflate_state FAR
*state
;
109 if (strm
== Z_NULL
||
110 strm
->zalloc
== (alloc_func
)0 || strm
->zfree
== (free_func
)0)
112 state
= (struct inflate_state FAR
*)strm
->state
;
113 if (state
== Z_NULL
|| state
->strm
!= strm
||
114 state
->mode
< HEAD
|| state
->mode
> SYNC
)
119 int ZEXPORT
inflateResetKeep(strm
)
122 struct inflate_state FAR
*state
;
124 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
125 state
= (struct inflate_state FAR
*)strm
->state
;
126 strm
->total_in
= strm
->total_out
= state
->total
= 0;
128 if (state
->wrap
) /* to support ill-conceived Java test suite */
129 strm
->adler
= state
->wrap
& 1;
134 state
->dmax
= 32768U;
135 state
->head
= Z_NULL
;
138 state
->lencode
= state
->distcode
= state
->next
= state
->codes
;
141 Tracev((stderr
, "inflate: reset\n"));
145 int ZEXPORT
inflateReset(strm
)
148 struct inflate_state FAR
*state
;
150 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
151 state
= (struct inflate_state FAR
*)strm
->state
;
155 return inflateResetKeep(strm
);
158 int ZEXPORT
inflateReset2(strm
, windowBits
)
163 struct inflate_state FAR
*state
;
166 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
167 state
= (struct inflate_state FAR
*)strm
->state
;
169 /* extract wrap request from windowBits parameter */
170 if (windowBits
< 0) {
171 if (windowBits
< -15)
172 return Z_STREAM_ERROR
;
174 windowBits
= -windowBits
;
177 wrap
= (windowBits
>> 4) + 5;
184 /* set number of window bits, free window if different */
185 if (windowBits
&& (windowBits
< 8 || windowBits
> 15))
186 return Z_STREAM_ERROR
;
187 if (state
->window
!= Z_NULL
&& state
->wbits
!= (unsigned)windowBits
) {
188 ZFREE(strm
, state
->window
);
189 state
->window
= Z_NULL
;
192 /* update state and reset the rest of it */
194 state
->wbits
= (unsigned)windowBits
;
195 return inflateReset(strm
);
198 int ZEXPORT
inflateInit2_(strm
, windowBits
, version
, stream_size
)
205 struct inflate_state FAR
*state
;
207 if (version
== Z_NULL
|| version
[0] != ZLIB_VERSION
[0] ||
208 stream_size
!= (int)(sizeof(z_stream
)))
209 return Z_VERSION_ERROR
;
210 if (strm
== Z_NULL
) return Z_STREAM_ERROR
;
211 strm
->msg
= Z_NULL
; /* in case we return an error */
212 if (strm
->zalloc
== (alloc_func
)0) {
214 return Z_STREAM_ERROR
;
216 strm
->zalloc
= zcalloc
;
217 strm
->opaque
= (voidpf
)0;
220 if (strm
->zfree
== (free_func
)0)
222 return Z_STREAM_ERROR
;
224 strm
->zfree
= zcfree
;
226 state
= (struct inflate_state FAR
*)
227 ZALLOC(strm
, 1, sizeof(struct inflate_state
));
228 if (state
== Z_NULL
) return Z_MEM_ERROR
;
229 Tracev((stderr
, "inflate: allocated\n"));
230 strm
->state
= (struct internal_state FAR
*)state
;
232 state
->window
= Z_NULL
;
233 state
->mode
= HEAD
; /* to pass state test in inflateReset2() */
234 ret
= inflateReset2(strm
, windowBits
);
237 strm
->state
= Z_NULL
;
242 int ZEXPORT
inflateInit_(strm
, version
, stream_size
)
247 return inflateInit2_(strm
, DEF_WBITS
, version
, stream_size
);
250 int ZEXPORT
inflatePrime(strm
, bits
, value
)
255 struct inflate_state FAR
*state
;
257 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
258 state
= (struct inflate_state FAR
*)strm
->state
;
264 if (bits
> 16 || state
->bits
+ (uInt
)bits
> 32) return Z_STREAM_ERROR
;
265 value
&= (1L << bits
) - 1;
266 state
->hold
+= (unsigned)value
<< state
->bits
;
267 state
->bits
+= (uInt
)bits
;
272 Return state with length and distance decoding tables and index sizes set to
273 fixed code decoding. Normally this returns fixed tables from inffixed.h.
274 If BUILDFIXED is defined, then instead this routine builds the tables the
275 first time it's called, and returns those tables the first time and
276 thereafter. This reduces the size of the code by about 2K bytes, in
277 exchange for a little execution time. However, BUILDFIXED should not be
278 used for threaded applications, since the rewriting of the tables and virgin
279 may not be thread-safe.
281 local
void fixedtables(state
)
282 struct inflate_state FAR
*state
;
285 static int virgin
= 1;
286 static code
*lenfix
, *distfix
;
287 static code fixed
[544];
289 /* build fixed huffman tables if first call (may not be thread safe) */
294 /* literal/length table */
296 while (sym
< 144) state
->lens
[sym
++] = 8;
297 while (sym
< 256) state
->lens
[sym
++] = 9;
298 while (sym
< 280) state
->lens
[sym
++] = 7;
299 while (sym
< 288) state
->lens
[sym
++] = 8;
303 inflate_table(LENS
, state
->lens
, 288, &(next
), &(bits
), state
->work
);
307 while (sym
< 32) state
->lens
[sym
++] = 5;
310 inflate_table(DISTS
, state
->lens
, 32, &(next
), &(bits
), state
->work
);
312 /* do this just once */
315 #else /* !BUILDFIXED */
316 # include "inffixed.h"
317 #endif /* BUILDFIXED */
318 state
->lencode
= lenfix
;
320 state
->distcode
= distfix
;
328 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
329 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
330 those tables to stdout, which would be piped to inffixed.h. A small program
331 can simply call makefixed to do this:
333 void makefixed(void);
341 Then that can be linked with zlib built with MAKEFIXED defined and run:
348 struct inflate_state state
;
351 puts(" /* inffixed.h -- table for decoding fixed codes");
352 puts(" * Generated automatically by makefixed().");
355 puts(" /* WARNING: this file should *not* be used by applications.");
356 puts(" It is part of the implementation of this library and is");
357 puts(" subject to change. Applications should only use zlib.h.");
361 printf(" static const code lenfix[%u] = {", size
);
364 if ((low
% 7) == 0) printf("\n ");
365 printf("{%u,%u,%d}", (low
& 127) == 99 ? 64 : state
.lencode
[low
].op
,
366 state
.lencode
[low
].bits
, state
.lencode
[low
].val
);
367 if (++low
== size
) break;
372 printf("\n static const code distfix[%u] = {", size
);
375 if ((low
% 6) == 0) printf("\n ");
376 printf("{%u,%u,%d}", state
.distcode
[low
].op
, state
.distcode
[low
].bits
,
377 state
.distcode
[low
].val
);
378 if (++low
== size
) break;
383 #endif /* MAKEFIXED */
386 Update the window with the last wsize (normally 32K) bytes written before
387 returning. If window does not exist yet, create it. This is only called
388 when a window is already in use, or when output has been written during this
389 inflate call, but the end of the deflate stream has not been reached yet.
390 It is also called to create a window for dictionary data when a dictionary
393 Providing output buffers larger than 32K to inflate() should provide a speed
394 advantage, since only the last 32K of output is copied to the sliding window
395 upon return from inflate(), and since all distances after the first 32K of
396 output will fall in the output data, making match copies simpler and faster.
397 The advantage may be dependent on the size of the processor's data caches.
399 local
int updatewindow(strm
, end
, copy
)
404 struct inflate_state FAR
*state
;
407 state
= (struct inflate_state FAR
*)strm
->state
;
409 /* if it hasn't been done already, allocate space for the window */
410 if (state
->window
== Z_NULL
) {
411 state
->window
= (unsigned char FAR
*)
412 ZALLOC(strm
, 1U << state
->wbits
,
413 sizeof(unsigned char));
414 if (state
->window
== Z_NULL
) return 1;
417 /* if window not in use yet, initialize */
418 if (state
->wsize
== 0) {
419 state
->wsize
= 1U << state
->wbits
;
424 /* copy state->wsize or less output bytes into the circular window */
425 if (copy
>= state
->wsize
) {
426 zmemcpy(state
->window
, end
- state
->wsize
, state
->wsize
);
428 state
->whave
= state
->wsize
;
431 dist
= state
->wsize
- state
->wnext
;
432 if (dist
> copy
) dist
= copy
;
433 zmemcpy(state
->window
+ state
->wnext
, end
- copy
, dist
);
436 zmemcpy(state
->window
, end
- copy
, copy
);
438 state
->whave
= state
->wsize
;
441 state
->wnext
+= dist
;
442 if (state
->wnext
== state
->wsize
) state
->wnext
= 0;
443 if (state
->whave
< state
->wsize
) state
->whave
+= dist
;
449 /* Macros for inflate(): */
451 /* check function to use adler32() for zlib or crc32() for gzip */
453 # define UPDATE_CHECK(check, buf, len) \
454 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
456 # define UPDATE_CHECK(check, buf, len) adler32(check, buf, len)
459 /* check macros for header crc */
461 # define CRC2(check, word) \
463 hbuf[0] = (unsigned char)(word); \
464 hbuf[1] = (unsigned char)((word) >> 8); \
465 check = crc32(check, hbuf, 2); \
468 # define CRC4(check, word) \
470 hbuf[0] = (unsigned char)(word); \
471 hbuf[1] = (unsigned char)((word) >> 8); \
472 hbuf[2] = (unsigned char)((word) >> 16); \
473 hbuf[3] = (unsigned char)((word) >> 24); \
474 check = crc32(check, hbuf, 4); \
478 /* Load registers with state in inflate() for speed */
481 put = strm->next_out; \
482 left = strm->avail_out; \
483 next = strm->next_in; \
484 have = strm->avail_in; \
485 hold = state->hold; \
486 bits = state->bits; \
489 /* Restore state from registers in inflate() */
492 strm->next_out = put; \
493 strm->avail_out = left; \
494 strm->next_in = next; \
495 strm->avail_in = have; \
496 state->hold = hold; \
497 state->bits = bits; \
500 /* Clear the input bit accumulator */
507 /* Get a byte of input into the bit accumulator, or return from inflate()
508 if there is no input available. */
511 if (have == 0) goto inf_leave; \
513 hold += (unsigned long)(*next++) << bits; \
517 /* Assure that there are at least n bits in the bit accumulator. If there is
518 not enough available input to do that, then return from inflate(). */
519 #define NEEDBITS(n) \
521 while (bits < (unsigned)(n)) \
525 /* Return the low n bits of the bit accumulator (n < 16) */
527 ((unsigned)hold & ((1U << (n)) - 1))
529 /* Remove n bits from the bit accumulator */
530 #define DROPBITS(n) \
533 bits -= (unsigned)(n); \
536 /* Remove zero to seven bits as needed to go to a byte boundary */
544 inflate() uses a state machine to process as much input data and generate as
545 much output data as possible before returning. The state machine is
546 structured roughly as follows:
548 for (;;) switch (state) {
551 if (not enough input data or output space to make progress)
553 ... make progress ...
559 so when inflate() is called again, the same case is attempted again, and
560 if the appropriate resources are provided, the machine proceeds to the
561 next state. The NEEDBITS() macro is usually the way the state evaluates
562 whether it can proceed or should return. NEEDBITS() does the return if
563 the requested bits are not available. The typical use of the BITS macros
567 ... do something with BITS(n) ...
570 where NEEDBITS(n) either returns from inflate() if there isn't enough
571 input left to load n bits into the accumulator, or it continues. BITS(n)
572 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
573 the low n bits off the accumulator. INITBITS() clears the accumulator
574 and sets the number of available bits to zero. BYTEBITS() discards just
575 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
576 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
578 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
579 if there is no input available. The decoding of variable length codes uses
580 PULLBYTE() directly in order to pull just enough bytes to decode the next
583 Some states loop until they get enough input, making sure that enough
584 state information is maintained to continue the loop where it left off
585 if NEEDBITS() returns in the loop. For example, want, need, and keep
586 would all have to actually be part of the saved state in case NEEDBITS()
590 while (want < need) {
592 keep[want++] = BITS(n);
598 As shown above, if the next state is also the next case, then the break
601 A state may also return if there is not enough output space available to
602 complete that state. Those states are copying stored data, writing a
603 literal byte, and copying a matching string.
605 When returning, a "goto inf_leave" is used to update the total counters,
606 update the check value, and determine whether any progress has been made
607 during that inflate() call in order to return the proper return code.
608 Progress is defined as a change in either strm->avail_in or strm->avail_out.
609 When there is a window, goto inf_leave will update the window with the last
610 output written. If a goto inf_leave occurs in the middle of decompression
611 and there is no window currently, goto inf_leave will create one and copy
612 output to the window for the next call of inflate().
614 In this implementation, the flush parameter of inflate() only affects the
615 return code (per zlib.h). inflate() always writes as much as possible to
616 strm->next_out, given the space available and the provided input--the effect
617 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
618 the allocation of and copying into a sliding window until necessary, which
619 provides the effect documented in zlib.h for Z_FINISH when the entire input
620 stream available. So the only thing the flush parameter actually does is:
621 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
622 will return Z_BUF_ERROR if it has not reached the end of the stream.
625 int ZEXPORT
inflate(strm
, flush
)
629 struct inflate_state FAR
*state
;
630 z_const
unsigned char FAR
*next
; /* next input */
631 unsigned char FAR
*put
; /* next output */
632 unsigned have
, left
; /* available input and output */
633 unsigned long hold
; /* bit buffer */
634 unsigned bits
; /* bits in bit buffer */
635 unsigned in
, out
; /* save starting available input and output */
636 unsigned copy
; /* number of stored or match bytes to copy */
637 unsigned char FAR
*from
; /* where to copy match bytes from */
638 code here
; /* current decoding table entry */
639 code last
; /* parent table entry */
640 unsigned len
; /* length to copy for repeats, bits to drop */
641 int ret
; /* return code */
643 unsigned char hbuf
[4]; /* buffer for gzip header crc calculation */
645 static const unsigned short order
[19] = /* permutation of code lengths */
646 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
648 if (inflateStateCheck(strm
) || strm
->next_out
== Z_NULL
||
649 (strm
->next_in
== Z_NULL
&& strm
->avail_in
!= 0))
650 return Z_STREAM_ERROR
;
652 state
= (struct inflate_state FAR
*)strm
->state
;
653 if (state
->mode
== TYPE
) state
->mode
= TYPEDO
; /* skip check */
659 switch (state
->mode
) {
661 if (state
->wrap
== 0) {
662 state
->mode
= TYPEDO
;
667 if ((state
->wrap
& 2) && hold
== 0x8b1f) { /* gzip header */
668 if (state
->wbits
== 0)
670 state
->check
= crc32(0L, Z_NULL
, 0);
671 CRC2(state
->check
, hold
);
676 if (state
->head
!= Z_NULL
)
677 state
->head
->done
= -1;
678 if (!(state
->wrap
& 1) || /* check if zlib header allowed */
682 ((BITS(8) << 8) + (hold
>> 8)) % 31) {
683 strm
->msg
= (char *)"incorrect header check";
687 if (BITS(4) != Z_DEFLATED
) {
688 strm
->msg
= (char *)"unknown compression method";
694 if (state
->wbits
== 0)
696 if (len
> 15 || len
> state
->wbits
) {
697 strm
->msg
= (char *)"invalid window size";
701 state
->dmax
= 1U << len
;
702 state
->flags
= 0; /* indicate zlib header */
703 Tracev((stderr
, "inflate: zlib header ok\n"));
704 strm
->adler
= state
->check
= adler32(0L, Z_NULL
, 0);
705 state
->mode
= hold
& 0x200 ? DICTID
: TYPE
;
711 state
->flags
= (int)(hold
);
712 if ((state
->flags
& 0xff) != Z_DEFLATED
) {
713 strm
->msg
= (char *)"unknown compression method";
717 if (state
->flags
& 0xe000) {
718 strm
->msg
= (char *)"unknown header flags set";
722 if (state
->head
!= Z_NULL
)
723 state
->head
->text
= (int)((hold
>> 8) & 1);
724 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
725 CRC2(state
->check
, hold
);
731 if (state
->head
!= Z_NULL
)
732 state
->head
->time
= hold
;
733 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
734 CRC4(state
->check
, hold
);
740 if (state
->head
!= Z_NULL
) {
741 state
->head
->xflags
= (int)(hold
& 0xff);
742 state
->head
->os
= (int)(hold
>> 8);
744 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
745 CRC2(state
->check
, hold
);
750 if (state
->flags
& 0x0400) {
752 state
->length
= (unsigned)(hold
);
753 if (state
->head
!= Z_NULL
)
754 state
->head
->extra_len
= (unsigned)hold
;
755 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
756 CRC2(state
->check
, hold
);
759 else if (state
->head
!= Z_NULL
)
760 state
->head
->extra
= Z_NULL
;
764 if (state
->flags
& 0x0400) {
765 copy
= state
->length
;
766 if (copy
> have
) copy
= have
;
768 if (state
->head
!= Z_NULL
&&
769 state
->head
->extra
!= Z_NULL
&&
770 (len
= state
->head
->extra_len
- state
->length
) <
771 state
->head
->extra_max
) {
772 zmemcpy(state
->head
->extra
+ len
, next
,
773 len
+ copy
> state
->head
->extra_max
?
774 state
->head
->extra_max
- len
: copy
);
776 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
777 state
->check
= crc32(state
->check
, next
, copy
);
780 state
->length
-= copy
;
782 if (state
->length
) goto inf_leave
;
788 if (state
->flags
& 0x0800) {
789 if (have
== 0) goto inf_leave
;
792 len
= (unsigned)(next
[copy
++]);
793 if (state
->head
!= Z_NULL
&&
794 state
->head
->name
!= Z_NULL
&&
795 state
->length
< state
->head
->name_max
)
796 state
->head
->name
[state
->length
++] = (Bytef
)len
;
797 } while (len
&& copy
< have
);
798 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
799 state
->check
= crc32(state
->check
, next
, copy
);
802 if (len
) goto inf_leave
;
804 else if (state
->head
!= Z_NULL
)
805 state
->head
->name
= Z_NULL
;
807 state
->mode
= COMMENT
;
810 if (state
->flags
& 0x1000) {
811 if (have
== 0) goto inf_leave
;
814 len
= (unsigned)(next
[copy
++]);
815 if (state
->head
!= Z_NULL
&&
816 state
->head
->comment
!= Z_NULL
&&
817 state
->length
< state
->head
->comm_max
)
818 state
->head
->comment
[state
->length
++] = (Bytef
)len
;
819 } while (len
&& copy
< have
);
820 if ((state
->flags
& 0x0200) && (state
->wrap
& 4))
821 state
->check
= crc32(state
->check
, next
, copy
);
824 if (len
) goto inf_leave
;
826 else if (state
->head
!= Z_NULL
)
827 state
->head
->comment
= Z_NULL
;
831 if (state
->flags
& 0x0200) {
833 if ((state
->wrap
& 4) && hold
!= (state
->check
& 0xffff)) {
834 strm
->msg
= (char *)"header crc mismatch";
840 if (state
->head
!= Z_NULL
) {
841 state
->head
->hcrc
= (int)((state
->flags
>> 9) & 1);
842 state
->head
->done
= 1;
844 strm
->adler
= state
->check
= crc32(0L, Z_NULL
, 0);
850 strm
->adler
= state
->check
= ZSWAP32(hold
);
855 if (state
->havedict
== 0) {
859 strm
->adler
= state
->check
= adler32(0L, Z_NULL
, 0);
863 if (flush
== Z_BLOCK
|| flush
== Z_TREES
) goto inf_leave
;
872 state
->last
= BITS(1);
875 case 0: /* stored block */
876 Tracev((stderr
, "inflate: stored block%s\n",
877 state
->last
? " (last)" : ""));
878 state
->mode
= STORED
;
880 case 1: /* fixed block */
882 Tracev((stderr
, "inflate: fixed codes block%s\n",
883 state
->last
? " (last)" : ""));
884 state
->mode
= LEN_
; /* decode codes */
885 if (flush
== Z_TREES
) {
890 case 2: /* dynamic block */
891 Tracev((stderr
, "inflate: dynamic codes block%s\n",
892 state
->last
? " (last)" : ""));
896 strm
->msg
= (char *)"invalid block type";
902 BYTEBITS(); /* go to byte boundary */
904 if ((hold
& 0xffff) != ((hold
>> 16) ^ 0xffff)) {
905 strm
->msg
= (char *)"invalid stored block lengths";
909 state
->length
= (unsigned)hold
& 0xffff;
910 Tracev((stderr
, "inflate: stored length %u\n",
914 if (flush
== Z_TREES
) goto inf_leave
;
920 copy
= state
->length
;
922 if (copy
> have
) copy
= have
;
923 if (copy
> left
) copy
= left
;
924 if (copy
== 0) goto inf_leave
;
925 zmemcpy(put
, next
, copy
);
930 state
->length
-= copy
;
933 Tracev((stderr
, "inflate: stored end\n"));
938 state
->nlen
= BITS(5) + 257;
940 state
->ndist
= BITS(5) + 1;
942 state
->ncode
= BITS(4) + 4;
944 #ifndef PKZIP_BUG_WORKAROUND
945 if (state
->nlen
> 286 || state
->ndist
> 30) {
946 strm
->msg
= (char *)"too many length or distance symbols";
951 Tracev((stderr
, "inflate: table sizes ok\n"));
953 state
->mode
= LENLENS
;
956 while (state
->have
< state
->ncode
) {
958 state
->lens
[order
[state
->have
++]] = (unsigned short)BITS(3);
961 while (state
->have
< 19)
962 state
->lens
[order
[state
->have
++]] = 0;
963 state
->next
= state
->codes
;
964 state
->lencode
= (const code FAR
*)(state
->next
);
966 ret
= inflate_table(CODES
, state
->lens
, 19, &(state
->next
),
967 &(state
->lenbits
), state
->work
);
969 strm
->msg
= (char *)"invalid code lengths set";
973 Tracev((stderr
, "inflate: code lengths ok\n"));
975 state
->mode
= CODELENS
;
978 while (state
->have
< state
->nlen
+ state
->ndist
) {
980 here
= state
->lencode
[BITS(state
->lenbits
)];
981 if ((unsigned)(here
.bits
) <= bits
) break;
986 state
->lens
[state
->have
++] = here
.val
;
989 if (here
.val
== 16) {
990 NEEDBITS(here
.bits
+ 2);
992 if (state
->have
== 0) {
993 strm
->msg
= (char *)"invalid bit length repeat";
997 len
= state
->lens
[state
->have
- 1];
1001 else if (here
.val
== 17) {
1002 NEEDBITS(here
.bits
+ 3);
1003 DROPBITS(here
.bits
);
1009 NEEDBITS(here
.bits
+ 7);
1010 DROPBITS(here
.bits
);
1012 copy
= 11 + BITS(7);
1015 if (state
->have
+ copy
> state
->nlen
+ state
->ndist
) {
1016 strm
->msg
= (char *)"invalid bit length repeat";
1021 state
->lens
[state
->have
++] = (unsigned short)len
;
1025 /* handle error breaks in while */
1026 if (state
->mode
== BAD
) break;
1028 /* check for end-of-block code (better have one) */
1029 if (state
->lens
[256] == 0) {
1030 strm
->msg
= (char *)"invalid code -- missing end-of-block";
1035 /* build code tables -- note: do not change the lenbits or distbits
1036 values here (9 and 6) without reading the comments in inftrees.h
1037 concerning the ENOUGH constants, which depend on those values */
1038 state
->next
= state
->codes
;
1039 state
->lencode
= (const code FAR
*)(state
->next
);
1041 ret
= inflate_table(LENS
, state
->lens
, state
->nlen
, &(state
->next
),
1042 &(state
->lenbits
), state
->work
);
1044 strm
->msg
= (char *)"invalid literal/lengths set";
1048 state
->distcode
= (const code FAR
*)(state
->next
);
1049 state
->distbits
= 6;
1050 ret
= inflate_table(DISTS
, state
->lens
+ state
->nlen
, state
->ndist
,
1051 &(state
->next
), &(state
->distbits
), state
->work
);
1053 strm
->msg
= (char *)"invalid distances set";
1057 Tracev((stderr
, "inflate: codes ok\n"));
1059 if (flush
== Z_TREES
) goto inf_leave
;
1065 if (have
>= 6 && left
>= 258) {
1067 inflate_fast(strm
, out
);
1069 if (state
->mode
== TYPE
)
1075 here
= state
->lencode
[BITS(state
->lenbits
)];
1076 if ((unsigned)(here
.bits
) <= bits
) break;
1079 if (here
.op
&& (here
.op
& 0xf0) == 0) {
1082 here
= state
->lencode
[last
.val
+
1083 (BITS(last
.bits
+ last
.op
) >> last
.bits
)];
1084 if ((unsigned)(last
.bits
+ here
.bits
) <= bits
) break;
1087 DROPBITS(last
.bits
);
1088 state
->back
+= last
.bits
;
1090 DROPBITS(here
.bits
);
1091 state
->back
+= here
.bits
;
1092 state
->length
= (unsigned)here
.val
;
1093 if ((int)(here
.op
) == 0) {
1094 Tracevv((stderr
, here
.val
>= 0x20 && here
.val
< 0x7f ?
1095 "inflate: literal '%c'\n" :
1096 "inflate: literal 0x%02x\n", here
.val
));
1101 Tracevv((stderr
, "inflate: end of block\n"));
1107 strm
->msg
= (char *)"invalid literal/length code";
1111 state
->extra
= (unsigned)(here
.op
) & 15;
1112 state
->mode
= LENEXT
;
1116 NEEDBITS(state
->extra
);
1117 state
->length
+= BITS(state
->extra
);
1118 DROPBITS(state
->extra
);
1119 state
->back
+= state
->extra
;
1121 Tracevv((stderr
, "inflate: length %u\n", state
->length
));
1122 state
->was
= state
->length
;
1127 here
= state
->distcode
[BITS(state
->distbits
)];
1128 if ((unsigned)(here
.bits
) <= bits
) break;
1131 if ((here
.op
& 0xf0) == 0) {
1134 here
= state
->distcode
[last
.val
+
1135 (BITS(last
.bits
+ last
.op
) >> last
.bits
)];
1136 if ((unsigned)(last
.bits
+ here
.bits
) <= bits
) break;
1139 DROPBITS(last
.bits
);
1140 state
->back
+= last
.bits
;
1142 DROPBITS(here
.bits
);
1143 state
->back
+= here
.bits
;
1145 strm
->msg
= (char *)"invalid distance code";
1149 state
->offset
= (unsigned)here
.val
;
1150 state
->extra
= (unsigned)(here
.op
) & 15;
1151 state
->mode
= DISTEXT
;
1155 NEEDBITS(state
->extra
);
1156 state
->offset
+= BITS(state
->extra
);
1157 DROPBITS(state
->extra
);
1158 state
->back
+= state
->extra
;
1160 #ifdef INFLATE_STRICT
1161 if (state
->offset
> state
->dmax
) {
1162 strm
->msg
= (char *)"invalid distance too far back";
1167 Tracevv((stderr
, "inflate: distance %u\n", state
->offset
));
1168 state
->mode
= MATCH
;
1171 if (left
== 0) goto inf_leave
;
1173 if (state
->offset
> copy
) { /* copy from window */
1174 copy
= state
->offset
- copy
;
1175 if (copy
> state
->whave
) {
1177 strm
->msg
= (char *)"invalid distance too far back";
1181 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1182 Trace((stderr
, "inflate.c too far\n"));
1183 copy
-= state
->whave
;
1184 if (copy
> state
->length
) copy
= state
->length
;
1185 if (copy
> left
) copy
= left
;
1187 state
->length
-= copy
;
1191 if (state
->length
== 0) state
->mode
= LEN
;
1195 if (copy
> state
->wnext
) {
1196 copy
-= state
->wnext
;
1197 from
= state
->window
+ (state
->wsize
- copy
);
1200 from
= state
->window
+ (state
->wnext
- copy
);
1201 if (copy
> state
->length
) copy
= state
->length
;
1203 else { /* copy from output */
1204 from
= put
- state
->offset
;
1205 copy
= state
->length
;
1207 if (copy
> left
) copy
= left
;
1209 state
->length
-= copy
;
1213 if (state
->length
== 0) state
->mode
= LEN
;
1216 if (left
== 0) goto inf_leave
;
1217 *put
++ = (unsigned char)(state
->length
);
1225 strm
->total_out
+= out
;
1226 state
->total
+= out
;
1227 if ((state
->wrap
& 4) && out
)
1228 strm
->adler
= state
->check
=
1229 UPDATE_CHECK(state
->check
, put
- out
, out
);
1231 if ((state
->wrap
& 4) && (
1233 state
->flags
? hold
:
1235 ZSWAP32(hold
)) != state
->check
) {
1236 strm
->msg
= (char *)"incorrect data check";
1241 Tracev((stderr
, "inflate: check matches trailer\n"));
1244 state
->mode
= LENGTH
;
1247 if (state
->wrap
&& state
->flags
) {
1249 if ((state
->wrap
& 4) && hold
!= (state
->total
& 0xffffffff)) {
1250 strm
->msg
= (char *)"incorrect length check";
1255 Tracev((stderr
, "inflate: length matches trailer\n"));
1271 return Z_STREAM_ERROR
;
1275 Return from inflate(), updating the total counts and the check value.
1276 If there was no progress during the inflate() call, return a buffer
1277 error. Call updatewindow() to create and/or update the window state.
1278 Note: a memory error from inflate() is non-recoverable.
1282 if (state
->wsize
|| (out
!= strm
->avail_out
&& state
->mode
< BAD
&&
1283 (state
->mode
< CHECK
|| flush
!= Z_FINISH
)))
1284 if (updatewindow(strm
, strm
->next_out
, out
- strm
->avail_out
)) {
1288 in
-= strm
->avail_in
;
1289 out
-= strm
->avail_out
;
1290 strm
->total_in
+= in
;
1291 strm
->total_out
+= out
;
1292 state
->total
+= out
;
1293 if ((state
->wrap
& 4) && out
)
1294 strm
->adler
= state
->check
=
1295 UPDATE_CHECK(state
->check
, strm
->next_out
- out
, out
);
1296 strm
->data_type
= (int)state
->bits
+ (state
->last
? 64 : 0) +
1297 (state
->mode
== TYPE
? 128 : 0) +
1298 (state
->mode
== LEN_
|| state
->mode
== COPY_
? 256 : 0);
1299 if (((in
== 0 && out
== 0) || flush
== Z_FINISH
) && ret
== Z_OK
)
1304 int ZEXPORT
inflateEnd(strm
)
1307 struct inflate_state FAR
*state
;
1308 if (inflateStateCheck(strm
))
1309 return Z_STREAM_ERROR
;
1310 state
= (struct inflate_state FAR
*)strm
->state
;
1311 if (state
->window
!= Z_NULL
) ZFREE(strm
, state
->window
);
1312 ZFREE(strm
, strm
->state
);
1313 strm
->state
= Z_NULL
;
1314 Tracev((stderr
, "inflate: end\n"));
1318 int ZEXPORT
inflateGetDictionary(strm
, dictionary
, dictLength
)
1323 struct inflate_state FAR
*state
;
1326 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1327 state
= (struct inflate_state FAR
*)strm
->state
;
1329 /* copy dictionary */
1330 if (state
->whave
&& dictionary
!= Z_NULL
) {
1331 zmemcpy(dictionary
, state
->window
+ state
->wnext
,
1332 state
->whave
- state
->wnext
);
1333 zmemcpy(dictionary
+ state
->whave
- state
->wnext
,
1334 state
->window
, state
->wnext
);
1336 if (dictLength
!= Z_NULL
)
1337 *dictLength
= state
->whave
;
1341 int ZEXPORT
inflateSetDictionary(strm
, dictionary
, dictLength
)
1343 const Bytef
*dictionary
;
1346 struct inflate_state FAR
*state
;
1347 unsigned long dictid
;
1351 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1352 state
= (struct inflate_state FAR
*)strm
->state
;
1353 if (state
->wrap
!= 0 && state
->mode
!= DICT
)
1354 return Z_STREAM_ERROR
;
1356 /* check for correct dictionary identifier */
1357 if (state
->mode
== DICT
) {
1358 dictid
= adler32(0L, Z_NULL
, 0);
1359 dictid
= adler32(dictid
, dictionary
, dictLength
);
1360 if (dictid
!= state
->check
)
1361 return Z_DATA_ERROR
;
1364 /* copy dictionary to window using updatewindow(), which will amend the
1365 existing dictionary if appropriate */
1366 ret
= updatewindow(strm
, dictionary
+ dictLength
, dictLength
);
1371 state
->havedict
= 1;
1372 Tracev((stderr
, "inflate: dictionary set\n"));
1376 int ZEXPORT
inflateGetHeader(strm
, head
)
1380 struct inflate_state FAR
*state
;
1383 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1384 state
= (struct inflate_state FAR
*)strm
->state
;
1385 if ((state
->wrap
& 2) == 0) return Z_STREAM_ERROR
;
1387 /* save header structure */
1394 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1395 or when out of input. When called, *have is the number of pattern bytes
1396 found in order so far, in 0..3. On return *have is updated to the new
1397 state. If on return *have equals four, then the pattern was found and the
1398 return value is how many bytes were read including the last byte of the
1399 pattern. If *have is less than four, then the pattern has not been found
1400 yet and the return value is len. In the latter case, syncsearch() can be
1401 called again with more data and the *have state. *have is initialized to
1402 zero for the first call.
1404 local
unsigned syncsearch(have
, buf
, len
)
1406 const unsigned char FAR
*buf
;
1414 while (next
< len
&& got
< 4) {
1415 if ((int)(buf
[next
]) == (got
< 2 ? 0 : 0xff))
1427 int ZEXPORT
inflateSync(strm
)
1430 unsigned len
; /* number of bytes to look at or looked at */
1431 int flags
; /* temporary to save header status */
1432 unsigned long in
, out
; /* temporary to save total_in and total_out */
1433 unsigned char buf
[4]; /* to restore bit buffer to byte string */
1434 struct inflate_state FAR
*state
;
1436 /* check parameters */
1437 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1438 state
= (struct inflate_state FAR
*)strm
->state
;
1439 if (strm
->avail_in
== 0 && state
->bits
< 8) return Z_BUF_ERROR
;
1441 /* if first time, start search in bit buffer */
1442 if (state
->mode
!= SYNC
) {
1444 state
->hold
<<= state
->bits
& 7;
1445 state
->bits
-= state
->bits
& 7;
1447 while (state
->bits
>= 8) {
1448 buf
[len
++] = (unsigned char)(state
->hold
);
1453 syncsearch(&(state
->have
), buf
, len
);
1456 /* search available input */
1457 len
= syncsearch(&(state
->have
), strm
->next_in
, strm
->avail_in
);
1458 strm
->avail_in
-= len
;
1459 strm
->next_in
+= len
;
1460 strm
->total_in
+= len
;
1462 /* return no joy or set up to restart inflate() on a new block */
1463 if (state
->have
!= 4) return Z_DATA_ERROR
;
1464 if (state
->flags
== -1)
1465 state
->wrap
= 0; /* if no header yet, treat as raw */
1467 state
->wrap
&= ~4; /* no point in computing a check value now */
1468 flags
= state
->flags
;
1469 in
= strm
->total_in
; out
= strm
->total_out
;
1471 strm
->total_in
= in
; strm
->total_out
= out
;
1472 state
->flags
= flags
;
1478 Returns true if inflate is currently at the end of a block generated by
1479 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1480 implementation to provide an additional safety check. PPP uses
1481 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1482 block. When decompressing, PPP checks that at the end of input packet,
1483 inflate is waiting for these length bytes.
1485 int ZEXPORT
inflateSyncPoint(strm
)
1488 struct inflate_state FAR
*state
;
1490 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1491 state
= (struct inflate_state FAR
*)strm
->state
;
1492 return state
->mode
== STORED
&& state
->bits
== 0;
1495 int ZEXPORT
inflateCopy(dest
, source
)
1499 struct inflate_state FAR
*state
;
1500 struct inflate_state FAR
*copy
;
1501 unsigned char FAR
*window
;
1505 if (inflateStateCheck(source
) || dest
== Z_NULL
)
1506 return Z_STREAM_ERROR
;
1507 state
= (struct inflate_state FAR
*)source
->state
;
1509 /* allocate space */
1510 copy
= (struct inflate_state FAR
*)
1511 ZALLOC(source
, 1, sizeof(struct inflate_state
));
1512 if (copy
== Z_NULL
) return Z_MEM_ERROR
;
1514 if (state
->window
!= Z_NULL
) {
1515 window
= (unsigned char FAR
*)
1516 ZALLOC(source
, 1U << state
->wbits
, sizeof(unsigned char));
1517 if (window
== Z_NULL
) {
1518 ZFREE(source
, copy
);
1524 zmemcpy((voidpf
)dest
, (voidpf
)source
, sizeof(z_stream
));
1525 zmemcpy((voidpf
)copy
, (voidpf
)state
, sizeof(struct inflate_state
));
1527 if (state
->lencode
>= state
->codes
&&
1528 state
->lencode
<= state
->codes
+ ENOUGH
- 1) {
1529 copy
->lencode
= copy
->codes
+ (state
->lencode
- state
->codes
);
1530 copy
->distcode
= copy
->codes
+ (state
->distcode
- state
->codes
);
1532 copy
->next
= copy
->codes
+ (state
->next
- state
->codes
);
1533 if (window
!= Z_NULL
) {
1534 wsize
= 1U << state
->wbits
;
1535 zmemcpy(window
, state
->window
, wsize
);
1537 copy
->window
= window
;
1538 dest
->state
= (struct internal_state FAR
*)copy
;
1542 int ZEXPORT
inflateUndermine(strm
, subvert
)
1546 struct inflate_state FAR
*state
;
1548 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1549 state
= (struct inflate_state FAR
*)strm
->state
;
1550 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1551 state
->sane
= !subvert
;
1556 return Z_DATA_ERROR
;
1560 int ZEXPORT
inflateValidate(strm
, check
)
1564 struct inflate_state FAR
*state
;
1566 if (inflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1567 state
= (struct inflate_state FAR
*)strm
->state
;
1568 if (check
&& state
->wrap
)
1575 long ZEXPORT
inflateMark(strm
)
1578 struct inflate_state FAR
*state
;
1580 if (inflateStateCheck(strm
))
1582 state
= (struct inflate_state FAR
*)strm
->state
;
1583 return (long)(((unsigned long)((long)state
->back
)) << 16) +
1584 (state
->mode
== COPY
? state
->length
:
1585 (state
->mode
== MATCH
? state
->was
- state
->length
: 0));
1588 unsigned long ZEXPORT
inflateCodesUsed(strm
)
1591 struct inflate_state FAR
*state
;
1592 if (inflateStateCheck(strm
)) return (unsigned long)-1;
1593 state
= (struct inflate_state FAR
*)strm
->state
;
1594 return (unsigned long)(state
->next
- state
->codes
);