]>
gcc.gnu.org Git - gcc.git/blob - zlib/inflate.c
1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2012 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
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
void fixedtables
OF((struct inflate_state FAR
*state
));
96 local
int updatewindow
OF((z_streamp strm
, unsigned out
));
98 void makefixed
OF((void));
100 local
unsigned syncsearch
OF((unsigned FAR
*have
, unsigned char FAR
*buf
,
103 int ZEXPORT
inflateResetKeep(strm
)
106 struct inflate_state FAR
*state
;
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;
112 if (state
->wrap
) /* to support ill-conceived Java test suite */
113 strm
->adler
= state
->wrap
& 1;
117 state
->dmax
= 32768U;
118 state
->head
= Z_NULL
;
121 state
->lencode
= state
->distcode
= state
->next
= state
->codes
;
124 Tracev((stderr
, "inflate: reset\n"));
128 int ZEXPORT
inflateReset(strm
)
131 struct inflate_state FAR
*state
;
133 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
134 state
= (struct inflate_state FAR
*)strm
->state
;
138 return inflateResetKeep(strm
);
141 int ZEXPORT
inflateReset2(strm
, windowBits
)
146 struct inflate_state FAR
*state
;
149 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
150 state
= (struct inflate_state FAR
*)strm
->state
;
152 /* extract wrap request from windowBits parameter */
153 if (windowBits
< 0) {
155 windowBits
= -windowBits
;
158 wrap
= (windowBits
>> 4) + 1;
165 /* set number of window bits, free window if different */
166 if (windowBits
&& (windowBits
< 8 || windowBits
> 15))
167 return Z_STREAM_ERROR
;
168 if (state
->window
!= Z_NULL
&& state
->wbits
!= (unsigned)windowBits
) {
169 ZFREE(strm
, state
->window
);
170 state
->window
= Z_NULL
;
173 /* update state and reset the rest of it */
175 state
->wbits
= (unsigned)windowBits
;
176 return inflateReset(strm
);
179 int ZEXPORT
inflateInit2_(strm
, windowBits
, version
, stream_size
)
186 struct inflate_state FAR
*state
;
188 if (version
== Z_NULL
|| version
[0] != ZLIB_VERSION
[0] ||
189 stream_size
!= (int)(sizeof(z_stream
)))
190 return Z_VERSION_ERROR
;
191 if (strm
== Z_NULL
) return Z_STREAM_ERROR
;
192 strm
->msg
= Z_NULL
; /* in case we return an error */
193 if (strm
->zalloc
== (alloc_func
)0) {
195 return Z_STREAM_ERROR
;
197 strm
->zalloc
= zcalloc
;
198 strm
->opaque
= (voidpf
)0;
201 if (strm
->zfree
== (free_func
)0)
203 return Z_STREAM_ERROR
;
205 strm
->zfree
= zcfree
;
207 state
= (struct inflate_state FAR
*)
208 ZALLOC(strm
, 1, sizeof(struct inflate_state
));
209 if (state
== Z_NULL
) return Z_MEM_ERROR
;
210 Tracev((stderr
, "inflate: allocated\n"));
211 strm
->state
= (struct internal_state FAR
*)state
;
212 state
->window
= Z_NULL
;
213 ret
= inflateReset2(strm
, windowBits
);
216 strm
->state
= Z_NULL
;
221 int ZEXPORT
inflateInit_(strm
, version
, stream_size
)
226 return inflateInit2_(strm
, DEF_WBITS
, version
, stream_size
);
229 int ZEXPORT
inflatePrime(strm
, bits
, value
)
234 struct inflate_state FAR
*state
;
236 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
237 state
= (struct inflate_state FAR
*)strm
->state
;
243 if (bits
> 16 || state
->bits
+ bits
> 32) return Z_STREAM_ERROR
;
244 value
&= (1L << bits
) - 1;
245 state
->hold
+= value
<< state
->bits
;
251 Return state with length and distance decoding tables and index sizes set to
252 fixed code decoding. Normally this returns fixed tables from inffixed.h.
253 If BUILDFIXED is defined, then instead this routine builds the tables the
254 first time it's called, and returns those tables the first time and
255 thereafter. This reduces the size of the code by about 2K bytes, in
256 exchange for a little execution time. However, BUILDFIXED should not be
257 used for threaded applications, since the rewriting of the tables and virgin
258 may not be thread-safe.
260 local
void fixedtables(state
)
261 struct inflate_state FAR
*state
;
264 static int virgin
= 1;
265 static code
*lenfix
, *distfix
;
266 static code fixed
[544];
268 /* build fixed huffman tables if first call (may not be thread safe) */
273 /* literal/length table */
275 while (sym
< 144) state
->lens
[sym
++] = 8;
276 while (sym
< 256) state
->lens
[sym
++] = 9;
277 while (sym
< 280) state
->lens
[sym
++] = 7;
278 while (sym
< 288) state
->lens
[sym
++] = 8;
282 inflate_table(LENS
, state
->lens
, 288, &(next
), &(bits
), state
->work
);
286 while (sym
< 32) state
->lens
[sym
++] = 5;
289 inflate_table(DISTS
, state
->lens
, 32, &(next
), &(bits
), state
->work
);
291 /* do this just once */
294 #else /* !BUILDFIXED */
295 # include "inffixed.h"
296 #endif /* BUILDFIXED */
297 state
->lencode
= lenfix
;
299 state
->distcode
= distfix
;
307 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
308 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
309 those tables to stdout, which would be piped to inffixed.h. A small program
310 can simply call makefixed to do this:
312 void makefixed(void);
320 Then that can be linked with zlib built with MAKEFIXED defined and run:
327 struct inflate_state state
;
330 puts(" /* inffixed.h -- table for decoding fixed codes");
331 puts(" * Generated automatically by makefixed().");
334 puts(" /* WARNING: this file should *not* be used by applications.");
335 puts(" It is part of the implementation of this library and is");
336 puts(" subject to change. Applications should only use zlib.h.");
340 printf(" static const code lenfix[%u] = {", size
);
343 if ((low
% 7) == 0) printf("\n ");
344 printf("{%u,%u,%d}", (low
& 127) == 99 ? 64 : state
.lencode
[low
].op
,
345 state
.lencode
[low
].bits
, state
.lencode
[low
].val
);
346 if (++low
== size
) break;
351 printf("\n static const code distfix[%u] = {", size
);
354 if ((low
% 6) == 0) printf("\n ");
355 printf("{%u,%u,%d}", state
.distcode
[low
].op
, state
.distcode
[low
].bits
,
356 state
.distcode
[low
].val
);
357 if (++low
== size
) break;
362 #endif /* MAKEFIXED */
365 Update the window with the last wsize (normally 32K) bytes written before
366 returning. If window does not exist yet, create it. This is only called
367 when a window is already in use, or when output has been written during this
368 inflate call, but the end of the deflate stream has not been reached yet.
369 It is also called to create a window for dictionary data when a dictionary
372 Providing output buffers larger than 32K to inflate() should provide a speed
373 advantage, since only the last 32K of output is copied to the sliding window
374 upon return from inflate(), and since all distances after the first 32K of
375 output will fall in the output data, making match copies simpler and faster.
376 The advantage may be dependent on the size of the processor's data caches.
378 local
int updatewindow(strm
, out
)
382 struct inflate_state FAR
*state
;
385 state
= (struct inflate_state FAR
*)strm
->state
;
387 /* if it hasn't been done already, allocate space for the window */
388 if (state
->window
== Z_NULL
) {
389 state
->window
= (unsigned char FAR
*)
390 ZALLOC(strm
, 1U << state
->wbits
,
391 sizeof(unsigned char));
392 if (state
->window
== Z_NULL
) return 1;
395 /* if window not in use yet, initialize */
396 if (state
->wsize
== 0) {
397 state
->wsize
= 1U << state
->wbits
;
402 /* copy state->wsize or less output bytes into the circular window */
403 copy
= out
- strm
->avail_out
;
404 if (copy
>= state
->wsize
) {
405 zmemcpy(state
->window
, strm
->next_out
- state
->wsize
, state
->wsize
);
407 state
->whave
= state
->wsize
;
410 dist
= state
->wsize
- state
->wnext
;
411 if (dist
> copy
) dist
= copy
;
412 zmemcpy(state
->window
+ state
->wnext
, strm
->next_out
- copy
, dist
);
415 zmemcpy(state
->window
, strm
->next_out
- copy
, copy
);
417 state
->whave
= state
->wsize
;
420 state
->wnext
+= dist
;
421 if (state
->wnext
== state
->wsize
) state
->wnext
= 0;
422 if (state
->whave
< state
->wsize
) state
->whave
+= dist
;
428 /* Macros for inflate(): */
430 /* check function to use adler32() for zlib or crc32() for gzip */
432 # define UPDATE(check, buf, len) \
433 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
435 # define UPDATE(check, buf, len) adler32(check, buf, len)
438 /* check macros for header crc */
440 # define CRC2(check, word) \
442 hbuf[0] = (unsigned char)(word); \
443 hbuf[1] = (unsigned char)((word) >> 8); \
444 check = crc32(check, hbuf, 2); \
447 # define CRC4(check, word) \
449 hbuf[0] = (unsigned char)(word); \
450 hbuf[1] = (unsigned char)((word) >> 8); \
451 hbuf[2] = (unsigned char)((word) >> 16); \
452 hbuf[3] = (unsigned char)((word) >> 24); \
453 check = crc32(check, hbuf, 4); \
457 /* Load registers with state in inflate() for speed */
460 put = strm->next_out; \
461 left = strm->avail_out; \
462 next = strm->next_in; \
463 have = strm->avail_in; \
464 hold = state->hold; \
465 bits = state->bits; \
468 /* Restore state from registers in inflate() */
471 strm->next_out = put; \
472 strm->avail_out = left; \
473 strm->next_in = next; \
474 strm->avail_in = have; \
475 state->hold = hold; \
476 state->bits = bits; \
479 /* Clear the input bit accumulator */
486 /* Get a byte of input into the bit accumulator, or return from inflate()
487 if there is no input available. */
490 if (have == 0) goto inf_leave; \
492 hold += (unsigned long)(*next++) << bits; \
496 /* Assure that there are at least n bits in the bit accumulator. If there is
497 not enough available input to do that, then return from inflate(). */
498 #define NEEDBITS(n) \
500 while (bits < (unsigned)(n)) \
504 /* Return the low n bits of the bit accumulator (n < 16) */
506 ((unsigned)hold & ((1U << (n)) - 1))
508 /* Remove n bits from the bit accumulator */
509 #define DROPBITS(n) \
512 bits -= (unsigned)(n); \
515 /* Remove zero to seven bits as needed to go to a byte boundary */
523 inflate() uses a state machine to process as much input data and generate as
524 much output data as possible before returning. The state machine is
525 structured roughly as follows:
527 for (;;) switch (state) {
530 if (not enough input data or output space to make progress)
532 ... make progress ...
538 so when inflate() is called again, the same case is attempted again, and
539 if the appropriate resources are provided, the machine proceeds to the
540 next state. The NEEDBITS() macro is usually the way the state evaluates
541 whether it can proceed or should return. NEEDBITS() does the return if
542 the requested bits are not available. The typical use of the BITS macros
546 ... do something with BITS(n) ...
549 where NEEDBITS(n) either returns from inflate() if there isn't enough
550 input left to load n bits into the accumulator, or it continues. BITS(n)
551 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
552 the low n bits off the accumulator. INITBITS() clears the accumulator
553 and sets the number of available bits to zero. BYTEBITS() discards just
554 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
555 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
557 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
558 if there is no input available. The decoding of variable length codes uses
559 PULLBYTE() directly in order to pull just enough bytes to decode the next
562 Some states loop until they get enough input, making sure that enough
563 state information is maintained to continue the loop where it left off
564 if NEEDBITS() returns in the loop. For example, want, need, and keep
565 would all have to actually be part of the saved state in case NEEDBITS()
569 while (want < need) {
571 keep[want++] = BITS(n);
577 As shown above, if the next state is also the next case, then the break
580 A state may also return if there is not enough output space available to
581 complete that state. Those states are copying stored data, writing a
582 literal byte, and copying a matching string.
584 When returning, a "goto inf_leave" is used to update the total counters,
585 update the check value, and determine whether any progress has been made
586 during that inflate() call in order to return the proper return code.
587 Progress is defined as a change in either strm->avail_in or strm->avail_out.
588 When there is a window, goto inf_leave will update the window with the last
589 output written. If a goto inf_leave occurs in the middle of decompression
590 and there is no window currently, goto inf_leave will create one and copy
591 output to the window for the next call of inflate().
593 In this implementation, the flush parameter of inflate() only affects the
594 return code (per zlib.h). inflate() always writes as much as possible to
595 strm->next_out, given the space available and the provided input--the effect
596 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
597 the allocation of and copying into a sliding window until necessary, which
598 provides the effect documented in zlib.h for Z_FINISH when the entire input
599 stream available. So the only thing the flush parameter actually does is:
600 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
601 will return Z_BUF_ERROR if it has not reached the end of the stream.
604 int ZEXPORT
inflate(strm
, flush
)
608 struct inflate_state FAR
*state
;
609 unsigned char FAR
*next
; /* next input */
610 unsigned char FAR
*put
; /* next output */
611 unsigned have
, left
; /* available input and output */
612 unsigned long hold
; /* bit buffer */
613 unsigned bits
; /* bits in bit buffer */
614 unsigned in
, out
; /* save starting available input and output */
615 unsigned copy
; /* number of stored or match bytes to copy */
616 unsigned char FAR
*from
; /* where to copy match bytes from */
617 code here
; /* current decoding table entry */
618 code last
; /* parent table entry */
619 unsigned len
; /* length to copy for repeats, bits to drop */
620 int ret
; /* return code */
622 unsigned char hbuf
[4]; /* buffer for gzip header crc calculation */
624 static const unsigned short order
[19] = /* permutation of code lengths */
625 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
627 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
|| strm
->next_out
== Z_NULL
||
628 (strm
->next_in
== Z_NULL
&& strm
->avail_in
!= 0))
629 return Z_STREAM_ERROR
;
631 state
= (struct inflate_state FAR
*)strm
->state
;
632 if (state
->mode
== TYPE
) state
->mode
= TYPEDO
; /* skip check */
638 switch (state
->mode
) {
640 if (state
->wrap
== 0) {
641 state
->mode
= TYPEDO
;
646 if ((state
->wrap
& 2) && hold
== 0x8b1f) { /* gzip header */
647 state
->check
= crc32(0L, Z_NULL
, 0);
648 CRC2(state
->check
, hold
);
653 state
->flags
= 0; /* expect zlib header */
654 if (state
->head
!= Z_NULL
)
655 state
->head
->done
= -1;
656 if (!(state
->wrap
& 1) || /* check if zlib header allowed */
660 ((BITS(8) << 8) + (hold
>> 8)) % 31) {
661 strm
->msg
= (char *)"incorrect header check";
665 if (BITS(4) != Z_DEFLATED
) {
666 strm
->msg
= (char *)"unknown compression method";
672 if (state
->wbits
== 0)
674 else if (len
> state
->wbits
) {
675 strm
->msg
= (char *)"invalid window size";
679 state
->dmax
= 1U << len
;
680 Tracev((stderr
, "inflate: zlib header ok\n"));
681 strm
->adler
= state
->check
= adler32(0L, Z_NULL
, 0);
682 state
->mode
= hold
& 0x200 ? DICTID
: TYPE
;
688 state
->flags
= (int)(hold
);
689 if ((state
->flags
& 0xff) != Z_DEFLATED
) {
690 strm
->msg
= (char *)"unknown compression method";
694 if (state
->flags
& 0xe000) {
695 strm
->msg
= (char *)"unknown header flags set";
699 if (state
->head
!= Z_NULL
)
700 state
->head
->text
= (int)((hold
>> 8) & 1);
701 if (state
->flags
& 0x0200) CRC2(state
->check
, hold
);
706 if (state
->head
!= Z_NULL
)
707 state
->head
->time
= hold
;
708 if (state
->flags
& 0x0200) CRC4(state
->check
, hold
);
713 if (state
->head
!= Z_NULL
) {
714 state
->head
->xflags
= (int)(hold
& 0xff);
715 state
->head
->os
= (int)(hold
>> 8);
717 if (state
->flags
& 0x0200) CRC2(state
->check
, hold
);
721 if (state
->flags
& 0x0400) {
723 state
->length
= (unsigned)(hold
);
724 if (state
->head
!= Z_NULL
)
725 state
->head
->extra_len
= (unsigned)hold
;
726 if (state
->flags
& 0x0200) CRC2(state
->check
, hold
);
729 else if (state
->head
!= Z_NULL
)
730 state
->head
->extra
= Z_NULL
;
733 if (state
->flags
& 0x0400) {
734 copy
= state
->length
;
735 if (copy
> have
) copy
= have
;
737 if (state
->head
!= Z_NULL
&&
738 state
->head
->extra
!= Z_NULL
) {
739 len
= state
->head
->extra_len
- state
->length
;
740 zmemcpy(state
->head
->extra
+ len
, next
,
741 len
+ copy
> state
->head
->extra_max
?
742 state
->head
->extra_max
- len
: copy
);
744 if (state
->flags
& 0x0200)
745 state
->check
= crc32(state
->check
, next
, copy
);
748 state
->length
-= copy
;
750 if (state
->length
) goto inf_leave
;
755 if (state
->flags
& 0x0800) {
756 if (have
== 0) goto inf_leave
;
759 len
= (unsigned)(next
[copy
++]);
760 if (state
->head
!= Z_NULL
&&
761 state
->head
->name
!= Z_NULL
&&
762 state
->length
< state
->head
->name_max
)
763 state
->head
->name
[state
->length
++] = len
;
764 } while (len
&& copy
< have
);
765 if (state
->flags
& 0x0200)
766 state
->check
= crc32(state
->check
, next
, copy
);
769 if (len
) goto inf_leave
;
771 else if (state
->head
!= Z_NULL
)
772 state
->head
->name
= Z_NULL
;
774 state
->mode
= COMMENT
;
776 if (state
->flags
& 0x1000) {
777 if (have
== 0) goto inf_leave
;
780 len
= (unsigned)(next
[copy
++]);
781 if (state
->head
!= Z_NULL
&&
782 state
->head
->comment
!= Z_NULL
&&
783 state
->length
< state
->head
->comm_max
)
784 state
->head
->comment
[state
->length
++] = len
;
785 } while (len
&& copy
< have
);
786 if (state
->flags
& 0x0200)
787 state
->check
= crc32(state
->check
, next
, copy
);
790 if (len
) goto inf_leave
;
792 else if (state
->head
!= Z_NULL
)
793 state
->head
->comment
= Z_NULL
;
796 if (state
->flags
& 0x0200) {
798 if (hold
!= (state
->check
& 0xffff)) {
799 strm
->msg
= (char *)"header crc mismatch";
805 if (state
->head
!= Z_NULL
) {
806 state
->head
->hcrc
= (int)((state
->flags
>> 9) & 1);
807 state
->head
->done
= 1;
809 strm
->adler
= state
->check
= crc32(0L, Z_NULL
, 0);
815 strm
->adler
= state
->check
= ZSWAP32(hold
);
819 if (state
->havedict
== 0) {
823 strm
->adler
= state
->check
= adler32(0L, Z_NULL
, 0);
826 if (flush
== Z_BLOCK
|| flush
== Z_TREES
) goto inf_leave
;
834 state
->last
= BITS(1);
837 case 0: /* stored block */
838 Tracev((stderr
, "inflate: stored block%s\n",
839 state
->last
? " (last)" : ""));
840 state
->mode
= STORED
;
842 case 1: /* fixed block */
844 Tracev((stderr
, "inflate: fixed codes block%s\n",
845 state
->last
? " (last)" : ""));
846 state
->mode
= LEN_
; /* decode codes */
847 if (flush
== Z_TREES
) {
852 case 2: /* dynamic block */
853 Tracev((stderr
, "inflate: dynamic codes block%s\n",
854 state
->last
? " (last)" : ""));
858 strm
->msg
= (char *)"invalid block type";
864 BYTEBITS(); /* go to byte boundary */
866 if ((hold
& 0xffff) != ((hold
>> 16) ^ 0xffff)) {
867 strm
->msg
= (char *)"invalid stored block lengths";
871 state
->length
= (unsigned)hold
& 0xffff;
872 Tracev((stderr
, "inflate: stored length %u\n",
876 if (flush
== Z_TREES
) goto inf_leave
;
880 copy
= state
->length
;
882 if (copy
> have
) copy
= have
;
883 if (copy
> left
) copy
= left
;
884 if (copy
== 0) goto inf_leave
;
885 zmemcpy(put
, next
, copy
);
890 state
->length
-= copy
;
893 Tracev((stderr
, "inflate: stored end\n"));
898 state
->nlen
= BITS(5) + 257;
900 state
->ndist
= BITS(5) + 1;
902 state
->ncode
= BITS(4) + 4;
904 #ifndef PKZIP_BUG_WORKAROUND
905 if (state
->nlen
> 286 || state
->ndist
> 30) {
906 strm
->msg
= (char *)"too many length or distance symbols";
911 Tracev((stderr
, "inflate: table sizes ok\n"));
913 state
->mode
= LENLENS
;
915 while (state
->have
< state
->ncode
) {
917 state
->lens
[order
[state
->have
++]] = (unsigned short)BITS(3);
920 while (state
->have
< 19)
921 state
->lens
[order
[state
->have
++]] = 0;
922 state
->next
= state
->codes
;
923 state
->lencode
= (code
const FAR
*)(state
->next
);
925 ret
= inflate_table(CODES
, state
->lens
, 19, &(state
->next
),
926 &(state
->lenbits
), state
->work
);
928 strm
->msg
= (char *)"invalid code lengths set";
932 Tracev((stderr
, "inflate: code lengths ok\n"));
934 state
->mode
= CODELENS
;
936 while (state
->have
< state
->nlen
+ state
->ndist
) {
938 here
= state
->lencode
[BITS(state
->lenbits
)];
939 if ((unsigned)(here
.bits
) <= bits
) break;
944 state
->lens
[state
->have
++] = here
.val
;
947 if (here
.val
== 16) {
948 NEEDBITS(here
.bits
+ 2);
950 if (state
->have
== 0) {
951 strm
->msg
= (char *)"invalid bit length repeat";
955 len
= state
->lens
[state
->have
- 1];
959 else if (here
.val
== 17) {
960 NEEDBITS(here
.bits
+ 3);
967 NEEDBITS(here
.bits
+ 7);
973 if (state
->have
+ copy
> state
->nlen
+ state
->ndist
) {
974 strm
->msg
= (char *)"invalid bit length repeat";
979 state
->lens
[state
->have
++] = (unsigned short)len
;
983 /* handle error breaks in while */
984 if (state
->mode
== BAD
) break;
986 /* check for end-of-block code (better have one) */
987 if (state
->lens
[256] == 0) {
988 strm
->msg
= (char *)"invalid code -- missing end-of-block";
993 /* build code tables -- note: do not change the lenbits or distbits
994 values here (9 and 6) without reading the comments in inftrees.h
995 concerning the ENOUGH constants, which depend on those values */
996 state
->next
= state
->codes
;
997 state
->lencode
= (code
const FAR
*)(state
->next
);
999 ret
= inflate_table(LENS
, state
->lens
, state
->nlen
, &(state
->next
),
1000 &(state
->lenbits
), state
->work
);
1002 strm
->msg
= (char *)"invalid literal/lengths set";
1006 state
->distcode
= (code
const FAR
*)(state
->next
);
1007 state
->distbits
= 6;
1008 ret
= inflate_table(DISTS
, state
->lens
+ state
->nlen
, state
->ndist
,
1009 &(state
->next
), &(state
->distbits
), state
->work
);
1011 strm
->msg
= (char *)"invalid distances set";
1015 Tracev((stderr
, "inflate: codes ok\n"));
1017 if (flush
== Z_TREES
) goto inf_leave
;
1021 if (have
>= 6 && left
>= 258) {
1023 inflate_fast(strm
, out
);
1025 if (state
->mode
== TYPE
)
1031 here
= state
->lencode
[BITS(state
->lenbits
)];
1032 if ((unsigned)(here
.bits
) <= bits
) break;
1035 if (here
.op
&& (here
.op
& 0xf0) == 0) {
1038 here
= state
->lencode
[last
.val
+
1039 (BITS(last
.bits
+ last
.op
) >> last
.bits
)];
1040 if ((unsigned)(last
.bits
+ here
.bits
) <= bits
) break;
1043 DROPBITS(last
.bits
);
1044 state
->back
+= last
.bits
;
1046 DROPBITS(here
.bits
);
1047 state
->back
+= here
.bits
;
1048 state
->length
= (unsigned)here
.val
;
1049 if ((int)(here
.op
) == 0) {
1050 Tracevv((stderr
, here
.val
>= 0x20 && here
.val
< 0x7f ?
1051 "inflate: literal '%c'\n" :
1052 "inflate: literal 0x%02x\n", here
.val
));
1057 Tracevv((stderr
, "inflate: end of block\n"));
1063 strm
->msg
= (char *)"invalid literal/length code";
1067 state
->extra
= (unsigned)(here
.op
) & 15;
1068 state
->mode
= LENEXT
;
1071 NEEDBITS(state
->extra
);
1072 state
->length
+= BITS(state
->extra
);
1073 DROPBITS(state
->extra
);
1074 state
->back
+= state
->extra
;
1076 Tracevv((stderr
, "inflate: length %u\n", state
->length
));
1077 state
->was
= state
->length
;
1081 here
= state
->distcode
[BITS(state
->distbits
)];
1082 if ((unsigned)(here
.bits
) <= bits
) break;
1085 if ((here
.op
& 0xf0) == 0) {
1088 here
= state
->distcode
[last
.val
+
1089 (BITS(last
.bits
+ last
.op
) >> last
.bits
)];
1090 if ((unsigned)(last
.bits
+ here
.bits
) <= bits
) break;
1093 DROPBITS(last
.bits
);
1094 state
->back
+= last
.bits
;
1096 DROPBITS(here
.bits
);
1097 state
->back
+= here
.bits
;
1099 strm
->msg
= (char *)"invalid distance code";
1103 state
->offset
= (unsigned)here
.val
;
1104 state
->extra
= (unsigned)(here
.op
) & 15;
1105 state
->mode
= DISTEXT
;
1108 NEEDBITS(state
->extra
);
1109 state
->offset
+= BITS(state
->extra
);
1110 DROPBITS(state
->extra
);
1111 state
->back
+= state
->extra
;
1113 #ifdef INFLATE_STRICT
1114 if (state
->offset
> state
->dmax
) {
1115 strm
->msg
= (char *)"invalid distance too far back";
1120 Tracevv((stderr
, "inflate: distance %u\n", state
->offset
));
1121 state
->mode
= MATCH
;
1123 if (left
== 0) goto inf_leave
;
1125 if (state
->offset
> copy
) { /* copy from window */
1126 copy
= state
->offset
- copy
;
1127 if (copy
> state
->whave
) {
1129 strm
->msg
= (char *)"invalid distance too far back";
1133 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1134 Trace((stderr
, "inflate.c too far\n"));
1135 copy
-= state
->whave
;
1136 if (copy
> state
->length
) copy
= state
->length
;
1137 if (copy
> left
) copy
= left
;
1139 state
->length
-= copy
;
1143 if (state
->length
== 0) state
->mode
= LEN
;
1147 if (copy
> state
->wnext
) {
1148 copy
-= state
->wnext
;
1149 from
= state
->window
+ (state
->wsize
- copy
);
1152 from
= state
->window
+ (state
->wnext
- copy
);
1153 if (copy
> state
->length
) copy
= state
->length
;
1155 else { /* copy from output */
1156 from
= put
- state
->offset
;
1157 copy
= state
->length
;
1159 if (copy
> left
) copy
= left
;
1161 state
->length
-= copy
;
1165 if (state
->length
== 0) state
->mode
= LEN
;
1168 if (left
== 0) goto inf_leave
;
1169 *put
++ = (unsigned char)(state
->length
);
1177 strm
->total_out
+= out
;
1178 state
->total
+= out
;
1180 strm
->adler
= state
->check
=
1181 UPDATE(state
->check
, put
- out
, out
);
1185 state
->flags
? hold
:
1187 ZSWAP32(hold
)) != state
->check
) {
1188 strm
->msg
= (char *)"incorrect data check";
1193 Tracev((stderr
, "inflate: check matches trailer\n"));
1196 state
->mode
= LENGTH
;
1198 if (state
->wrap
&& state
->flags
) {
1200 if (hold
!= (state
->total
& 0xffffffffUL
)) {
1201 strm
->msg
= (char *)"incorrect length check";
1206 Tracev((stderr
, "inflate: length matches trailer\n"));
1220 return Z_STREAM_ERROR
;
1224 Return from inflate(), updating the total counts and the check value.
1225 If there was no progress during the inflate() call, return a buffer
1226 error. Call updatewindow() to create and/or update the window state.
1227 Note: a memory error from inflate() is non-recoverable.
1231 if (state
->wsize
|| (out
!= strm
->avail_out
&& state
->mode
< BAD
&&
1232 (state
->mode
< CHECK
|| flush
!= Z_FINISH
)))
1233 if (updatewindow(strm
, out
)) {
1237 in
-= strm
->avail_in
;
1238 out
-= strm
->avail_out
;
1239 strm
->total_in
+= in
;
1240 strm
->total_out
+= out
;
1241 state
->total
+= out
;
1242 if (state
->wrap
&& out
)
1243 strm
->adler
= state
->check
=
1244 UPDATE(state
->check
, strm
->next_out
- out
, out
);
1245 strm
->data_type
= state
->bits
+ (state
->last
? 64 : 0) +
1246 (state
->mode
== TYPE
? 128 : 0) +
1247 (state
->mode
== LEN_
|| state
->mode
== COPY_
? 256 : 0);
1248 if (((in
== 0 && out
== 0) || flush
== Z_FINISH
) && ret
== Z_OK
)
1253 int ZEXPORT
inflateEnd(strm
)
1256 struct inflate_state FAR
*state
;
1257 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
|| strm
->zfree
== (free_func
)0)
1258 return Z_STREAM_ERROR
;
1259 state
= (struct inflate_state FAR
*)strm
->state
;
1260 if (state
->window
!= Z_NULL
) ZFREE(strm
, state
->window
);
1261 ZFREE(strm
, strm
->state
);
1262 strm
->state
= Z_NULL
;
1263 Tracev((stderr
, "inflate: end\n"));
1267 int ZEXPORT
inflateSetDictionary(strm
, dictionary
, dictLength
)
1269 const Bytef
*dictionary
;
1272 struct inflate_state FAR
*state
;
1273 unsigned long dictid
;
1274 unsigned char *next
;
1279 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
1280 state
= (struct inflate_state FAR
*)strm
->state
;
1281 if (state
->wrap
!= 0 && state
->mode
!= DICT
)
1282 return Z_STREAM_ERROR
;
1284 /* check for correct dictionary identifier */
1285 if (state
->mode
== DICT
) {
1286 dictid
= adler32(0L, Z_NULL
, 0);
1287 dictid
= adler32(dictid
, dictionary
, dictLength
);
1288 if (dictid
!= state
->check
)
1289 return Z_DATA_ERROR
;
1292 /* copy dictionary to window using updatewindow(), which will amend the
1293 existing dictionary if appropriate */
1294 next
= strm
->next_out
;
1295 avail
= strm
->avail_out
;
1296 strm
->next_out
= (Bytef
*)dictionary
+ dictLength
;
1297 strm
->avail_out
= 0;
1298 ret
= updatewindow(strm
, dictLength
);
1299 strm
->avail_out
= avail
;
1300 strm
->next_out
= next
;
1305 state
->havedict
= 1;
1306 Tracev((stderr
, "inflate: dictionary set\n"));
1310 int ZEXPORT
inflateGetHeader(strm
, head
)
1314 struct inflate_state FAR
*state
;
1317 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
1318 state
= (struct inflate_state FAR
*)strm
->state
;
1319 if ((state
->wrap
& 2) == 0) return Z_STREAM_ERROR
;
1321 /* save header structure */
1328 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1329 or when out of input. When called, *have is the number of pattern bytes
1330 found in order so far, in 0..3. On return *have is updated to the new
1331 state. If on return *have equals four, then the pattern was found and the
1332 return value is how many bytes were read including the last byte of the
1333 pattern. If *have is less than four, then the pattern has not been found
1334 yet and the return value is len. In the latter case, syncsearch() can be
1335 called again with more data and the *have state. *have is initialized to
1336 zero for the first call.
1338 local
unsigned syncsearch(have
, buf
, len
)
1340 unsigned char FAR
*buf
;
1348 while (next
< len
&& got
< 4) {
1349 if ((int)(buf
[next
]) == (got
< 2 ? 0 : 0xff))
1361 int ZEXPORT
inflateSync(strm
)
1364 unsigned len
; /* number of bytes to look at or looked at */
1365 unsigned long in
, out
; /* temporary to save total_in and total_out */
1366 unsigned char buf
[4]; /* to restore bit buffer to byte string */
1367 struct inflate_state FAR
*state
;
1369 /* check parameters */
1370 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
1371 state
= (struct inflate_state FAR
*)strm
->state
;
1372 if (strm
->avail_in
== 0 && state
->bits
< 8) return Z_BUF_ERROR
;
1374 /* if first time, start search in bit buffer */
1375 if (state
->mode
!= SYNC
) {
1377 state
->hold
<<= state
->bits
& 7;
1378 state
->bits
-= state
->bits
& 7;
1380 while (state
->bits
>= 8) {
1381 buf
[len
++] = (unsigned char)(state
->hold
);
1386 syncsearch(&(state
->have
), buf
, len
);
1389 /* search available input */
1390 len
= syncsearch(&(state
->have
), strm
->next_in
, strm
->avail_in
);
1391 strm
->avail_in
-= len
;
1392 strm
->next_in
+= len
;
1393 strm
->total_in
+= len
;
1395 /* return no joy or set up to restart inflate() on a new block */
1396 if (state
->have
!= 4) return Z_DATA_ERROR
;
1397 in
= strm
->total_in
; out
= strm
->total_out
;
1399 strm
->total_in
= in
; strm
->total_out
= out
;
1405 Returns true if inflate is currently at the end of a block generated by
1406 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1407 implementation to provide an additional safety check. PPP uses
1408 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1409 block. When decompressing, PPP checks that at the end of input packet,
1410 inflate is waiting for these length bytes.
1412 int ZEXPORT
inflateSyncPoint(strm
)
1415 struct inflate_state FAR
*state
;
1417 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
1418 state
= (struct inflate_state FAR
*)strm
->state
;
1419 return state
->mode
== STORED
&& state
->bits
== 0;
1422 int ZEXPORT
inflateCopy(dest
, source
)
1426 struct inflate_state FAR
*state
;
1427 struct inflate_state FAR
*copy
;
1428 unsigned char FAR
*window
;
1432 if (dest
== Z_NULL
|| source
== Z_NULL
|| source
->state
== Z_NULL
||
1433 source
->zalloc
== (alloc_func
)0 || source
->zfree
== (free_func
)0)
1434 return Z_STREAM_ERROR
;
1435 state
= (struct inflate_state FAR
*)source
->state
;
1437 /* allocate space */
1438 copy
= (struct inflate_state FAR
*)
1439 ZALLOC(source
, 1, sizeof(struct inflate_state
));
1440 if (copy
== Z_NULL
) return Z_MEM_ERROR
;
1442 if (state
->window
!= Z_NULL
) {
1443 window
= (unsigned char FAR
*)
1444 ZALLOC(source
, 1U << state
->wbits
, sizeof(unsigned char));
1445 if (window
== Z_NULL
) {
1446 ZFREE(source
, copy
);
1452 zmemcpy((voidpf
)dest
, (voidpf
)source
, sizeof(z_stream
));
1453 zmemcpy((voidpf
)copy
, (voidpf
)state
, sizeof(struct inflate_state
));
1454 if (state
->lencode
>= state
->codes
&&
1455 state
->lencode
<= state
->codes
+ ENOUGH
- 1) {
1456 copy
->lencode
= copy
->codes
+ (state
->lencode
- state
->codes
);
1457 copy
->distcode
= copy
->codes
+ (state
->distcode
- state
->codes
);
1459 copy
->next
= copy
->codes
+ (state
->next
- state
->codes
);
1460 if (window
!= Z_NULL
) {
1461 wsize
= 1U << state
->wbits
;
1462 zmemcpy(window
, state
->window
, wsize
);
1464 copy
->window
= window
;
1465 dest
->state
= (struct internal_state FAR
*)copy
;
1469 int ZEXPORT
inflateUndermine(strm
, subvert
)
1473 struct inflate_state FAR
*state
;
1475 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return Z_STREAM_ERROR
;
1476 state
= (struct inflate_state FAR
*)strm
->state
;
1477 state
->sane
= !subvert
;
1478 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1482 return Z_DATA_ERROR
;
1486 long ZEXPORT
inflateMark(strm
)
1489 struct inflate_state FAR
*state
;
1491 if (strm
== Z_NULL
|| strm
->state
== Z_NULL
) return -1L << 16;
1492 state
= (struct inflate_state FAR
*)strm
->state
;
1493 return ((long)(state
->back
) << 16) +
1494 (state
->mode
== COPY
? state
->length
:
1495 (state
->mode
== MATCH
? state
->was
- state
->length
: 0));
This page took 0.198229 seconds and 5 git commands to generate.