1
/* inflate.c -- zlib decompression
2
* Copyright (C) 1995-2010 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 inflateReset(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
strm->adler = 1; /* to support ill-conceived Java test suite */
116
state->dmax = 32768U;
117
state->head = Z_NULL;
123
state->lencode = state->distcode = state->next = state->codes;
126
Tracev((stderr, "inflate: reset\n"));
130
int ZEXPORT inflateReset2(strm, windowBits)
135
struct inflate_state FAR *state;
138
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
139
state = (struct inflate_state FAR *)strm->state;
141
/* extract wrap request from windowBits parameter */
142
if (windowBits < 0) {
144
windowBits = -windowBits;
147
wrap = (windowBits >> 4) + 1;
154
/* set number of window bits, free window if different */
155
if (windowBits && (windowBits < 8 || windowBits > 15))
156
return Z_STREAM_ERROR;
157
if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
158
ZFREE(strm, state->window);
159
state->window = Z_NULL;
162
/* update state and reset the rest of it */
164
state->wbits = (unsigned)windowBits;
165
return inflateReset(strm);
168
int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
175
struct inflate_state FAR *state;
177
if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
178
stream_size != (int)(sizeof(z_stream)))
179
return Z_VERSION_ERROR;
180
if (strm == Z_NULL) return Z_STREAM_ERROR;
181
strm->msg = Z_NULL; /* in case we return an error */
182
if (strm->zalloc == (alloc_func)0) {
183
strm->zalloc = zcalloc;
184
strm->opaque = (voidpf)0;
186
if (strm->zfree == (free_func)0) strm->zfree = zcfree;
187
state = (struct inflate_state FAR *)
188
ZALLOC(strm, 1, sizeof(struct inflate_state));
189
if (state == Z_NULL) return Z_MEM_ERROR;
190
Tracev((stderr, "inflate: allocated\n"));
191
strm->state = (struct internal_state FAR *)state;
192
state->window = Z_NULL;
193
ret = inflateReset2(strm, windowBits);
196
strm->state = Z_NULL;
201
int ZEXPORT inflateInit_(strm, version, stream_size)
206
return inflateInit2_(strm, DEF_WBITS, version, stream_size);
209
int ZEXPORT inflatePrime(strm, bits, value)
214
struct inflate_state FAR *state;
216
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
217
state = (struct inflate_state FAR *)strm->state;
223
if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
224
value &= (1L << bits) - 1;
225
state->hold += value << state->bits;
231
Return state with length and distance decoding tables and index sizes set to
232
fixed code decoding. Normally this returns fixed tables from inffixed.h.
233
If BUILDFIXED is defined, then instead this routine builds the tables the
234
first time it's called, and returns those tables the first time and
235
thereafter. This reduces the size of the code by about 2K bytes, in
236
exchange for a little execution time. However, BUILDFIXED should not be
237
used for threaded applications, since the rewriting of the tables and virgin
238
may not be thread-safe.
240
local void fixedtables(state)
241
struct inflate_state FAR *state;
244
static int virgin = 1;
245
static code *lenfix, *distfix;
246
static code fixed[544];
248
/* build fixed huffman tables if first call (may not be thread safe) */
253
/* literal/length table */
255
while (sym < 144) state->lens[sym++] = 8;
256
while (sym < 256) state->lens[sym++] = 9;
257
while (sym < 280) state->lens[sym++] = 7;
258
while (sym < 288) state->lens[sym++] = 8;
262
inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
266
while (sym < 32) state->lens[sym++] = 5;
269
inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
271
/* do this just once */
274
#else /* !BUILDFIXED */
275
# include "inffixed.h"
276
#endif /* BUILDFIXED */
277
state->lencode = lenfix;
279
state->distcode = distfix;
287
Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
288
defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
289
those tables to stdout, which would be piped to inffixed.h. A small program
290
can simply call makefixed to do this:
292
void makefixed(void);
300
Then that can be linked with zlib built with MAKEFIXED defined and run:
307
struct inflate_state state;
310
puts(" /* inffixed.h -- table for decoding fixed codes");
311
puts(" * Generated automatically by makefixed().");
314
puts(" /* WARNING: this file should *not* be used by applications.");
315
puts(" It is part of the implementation of this library and is");
316
puts(" subject to change. Applications should only use zlib.h.");
320
printf(" static const code lenfix[%u] = {", size);
323
if ((low % 7) == 0) printf("\n ");
324
printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
325
state.lencode[low].val);
326
if (++low == size) break;
331
printf("\n static const code distfix[%u] = {", size);
334
if ((low % 6) == 0) printf("\n ");
335
printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
336
state.distcode[low].val);
337
if (++low == size) break;
342
#endif /* MAKEFIXED */
345
Update the window with the last wsize (normally 32K) bytes written before
346
returning. If window does not exist yet, create it. This is only called
347
when a window is already in use, or when output has been written during this
348
inflate call, but the end of the deflate stream has not been reached yet.
349
It is also called to create a window for dictionary data when a dictionary
352
Providing output buffers larger than 32K to inflate() should provide a speed
353
advantage, since only the last 32K of output is copied to the sliding window
354
upon return from inflate(), and since all distances after the first 32K of
355
output will fall in the output data, making match copies simpler and faster.
356
The advantage may be dependent on the size of the processor's data caches.
358
local int updatewindow(strm, out)
362
struct inflate_state FAR *state;
365
state = (struct inflate_state FAR *)strm->state;
367
/* if it hasn't been done already, allocate space for the window */
368
if (state->window == Z_NULL) {
369
state->window = (unsigned char FAR *)
370
ZALLOC(strm, 1U << state->wbits,
371
sizeof(unsigned char));
372
if (state->window == Z_NULL) return 1;
375
/* if window not in use yet, initialize */
376
if (state->wsize == 0) {
377
state->wsize = 1U << state->wbits;
382
/* copy state->wsize or less output bytes into the circular window */
383
copy = out - strm->avail_out;
384
if (copy >= state->wsize) {
385
zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
387
state->whave = state->wsize;
390
dist = state->wsize - state->wnext;
391
if (dist > copy) dist = copy;
392
zmemcpy(state->window + state->wnext, strm->next_out - copy, dist);
395
zmemcpy(state->window, strm->next_out - copy, copy);
397
state->whave = state->wsize;
400
state->wnext += dist;
401
if (state->wnext == state->wsize) state->wnext = 0;
402
if (state->whave < state->wsize) state->whave += dist;
408
/* Macros for inflate(): */
410
/* check function to use adler32() for zlib or crc32() for gzip */
412
# define UPDATE(check, buf, len) \
413
(state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
415
# define UPDATE(check, buf, len) adler32(check, buf, len)
418
/* check macros for header crc */
420
# define CRC2(check, word) \
422
hbuf[0] = (unsigned char)(word); \
423
hbuf[1] = (unsigned char)((word) >> 8); \
424
check = crc32(check, hbuf, 2); \
427
# define CRC4(check, word) \
429
hbuf[0] = (unsigned char)(word); \
430
hbuf[1] = (unsigned char)((word) >> 8); \
431
hbuf[2] = (unsigned char)((word) >> 16); \
432
hbuf[3] = (unsigned char)((word) >> 24); \
433
check = crc32(check, hbuf, 4); \
437
/* Load registers with state in inflate() for speed */
440
put = strm->next_out; \
441
left = strm->avail_out; \
442
next = strm->next_in; \
443
have = strm->avail_in; \
444
hold = state->hold; \
445
bits = state->bits; \
448
/* Restore state from registers in inflate() */
451
strm->next_out = put; \
452
strm->avail_out = left; \
453
strm->next_in = next; \
454
strm->avail_in = have; \
455
state->hold = hold; \
456
state->bits = bits; \
459
/* Clear the input bit accumulator */
466
/* Get a byte of input into the bit accumulator, or return from inflate()
467
if there is no input available. */
470
if (have == 0) goto inf_leave; \
472
hold += (unsigned long)(*next++) << bits; \
476
/* Assure that there are at least n bits in the bit accumulator. If there is
477
not enough available input to do that, then return from inflate(). */
478
#define NEEDBITS(n) \
480
while (bits < (unsigned)(n)) \
484
/* Return the low n bits of the bit accumulator (n < 16) */
486
((unsigned)hold & ((1U << (n)) - 1))
488
/* Remove n bits from the bit accumulator */
489
#define DROPBITS(n) \
492
bits -= (unsigned)(n); \
495
/* Remove zero to seven bits as needed to go to a byte boundary */
502
/* Reverse the bytes in a 32-bit value */
504
((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
505
(((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
508
inflate() uses a state machine to process as much input data and generate as
509
much output data as possible before returning. The state machine is
510
structured roughly as follows:
512
for (;;) switch (state) {
515
if (not enough input data or output space to make progress)
517
... make progress ...
523
so when inflate() is called again, the same case is attempted again, and
524
if the appropriate resources are provided, the machine proceeds to the
525
next state. The NEEDBITS() macro is usually the way the state evaluates
526
whether it can proceed or should return. NEEDBITS() does the return if
527
the requested bits are not available. The typical use of the BITS macros
531
... do something with BITS(n) ...
534
where NEEDBITS(n) either returns from inflate() if there isn't enough
535
input left to load n bits into the accumulator, or it continues. BITS(n)
536
gives the low n bits in the accumulator. When done, DROPBITS(n) drops
537
the low n bits off the accumulator. INITBITS() clears the accumulator
538
and sets the number of available bits to zero. BYTEBITS() discards just
539
enough bits to put the accumulator on a byte boundary. After BYTEBITS()
540
and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
542
NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
543
if there is no input available. The decoding of variable length codes uses
544
PULLBYTE() directly in order to pull just enough bytes to decode the next
547
Some states loop until they get enough input, making sure that enough
548
state information is maintained to continue the loop where it left off
549
if NEEDBITS() returns in the loop. For example, want, need, and keep
550
would all have to actually be part of the saved state in case NEEDBITS()
554
while (want < need) {
556
keep[want++] = BITS(n);
562
As shown above, if the next state is also the next case, then the break
565
A state may also return if there is not enough output space available to
566
complete that state. Those states are copying stored data, writing a
567
literal byte, and copying a matching string.
569
When returning, a "goto inf_leave" is used to update the total counters,
570
update the check value, and determine whether any progress has been made
571
during that inflate() call in order to return the proper return code.
572
Progress is defined as a change in either strm->avail_in or strm->avail_out.
573
When there is a window, goto inf_leave will update the window with the last
574
output written. If a goto inf_leave occurs in the middle of decompression
575
and there is no window currently, goto inf_leave will create one and copy
576
output to the window for the next call of inflate().
578
In this implementation, the flush parameter of inflate() only affects the
579
return code (per zlib.h). inflate() always writes as much as possible to
580
strm->next_out, given the space available and the provided input--the effect
581
documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
582
the allocation of and copying into a sliding window until necessary, which
583
provides the effect documented in zlib.h for Z_FINISH when the entire input
584
stream available. So the only thing the flush parameter actually does is:
585
when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
586
will return Z_BUF_ERROR if it has not reached the end of the stream.
589
int ZEXPORT inflate(strm, flush)
593
struct inflate_state FAR *state;
594
unsigned char FAR *next; /* next input */
595
unsigned char FAR *put; /* next output */
596
unsigned have, left; /* available input and output */
597
unsigned long hold; /* bit buffer */
598
unsigned bits; /* bits in bit buffer */
599
unsigned in, out; /* save starting available input and output */
600
unsigned copy; /* number of stored or match bytes to copy */
601
unsigned char FAR *from; /* where to copy match bytes from */
602
code here; /* current decoding table entry */
603
code last; /* parent table entry */
604
unsigned len; /* length to copy for repeats, bits to drop */
605
int ret; /* return code */
607
unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
609
static const unsigned short order[19] = /* permutation of code lengths */
610
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
612
if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
613
(strm->next_in == Z_NULL && strm->avail_in != 0))
614
return Z_STREAM_ERROR;
616
state = (struct inflate_state FAR *)strm->state;
617
if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
623
switch (state->mode) {
625
if (state->wrap == 0) {
626
state->mode = TYPEDO;
631
if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
632
state->check = crc32(0L, Z_NULL, 0);
633
CRC2(state->check, hold);
638
state->flags = 0; /* expect zlib header */
639
if (state->head != Z_NULL)
640
state->head->done = -1;
641
if (!(state->wrap & 1) || /* check if zlib header allowed */
645
((BITS(8) << 8) + (hold >> 8)) % 31) {
646
strm->msg = (char *)"incorrect header check";
650
if (BITS(4) != Z_DEFLATED) {
651
strm->msg = (char *)"unknown compression method";
657
if (state->wbits == 0)
659
else if (len > state->wbits) {
660
strm->msg = (char *)"invalid window size";
664
state->dmax = 1U << len;
665
Tracev((stderr, "inflate: zlib header ok\n"));
666
strm->adler = state->check = adler32(0L, Z_NULL, 0);
667
state->mode = hold & 0x200 ? DICTID : TYPE;
673
state->flags = (int)(hold);
674
if ((state->flags & 0xff) != Z_DEFLATED) {
675
strm->msg = (char *)"unknown compression method";
679
if (state->flags & 0xe000) {
680
strm->msg = (char *)"unknown header flags set";
684
if (state->head != Z_NULL)
685
state->head->text = (int)((hold >> 8) & 1);
686
if (state->flags & 0x0200) CRC2(state->check, hold);
691
if (state->head != Z_NULL)
692
state->head->time = hold;
693
if (state->flags & 0x0200) CRC4(state->check, hold);
698
if (state->head != Z_NULL) {
699
state->head->xflags = (int)(hold & 0xff);
700
state->head->os = (int)(hold >> 8);
702
if (state->flags & 0x0200) CRC2(state->check, hold);
706
if (state->flags & 0x0400) {
708
state->length = (unsigned)(hold);
709
if (state->head != Z_NULL)
710
state->head->extra_len = (unsigned)hold;
711
if (state->flags & 0x0200) CRC2(state->check, hold);
714
else if (state->head != Z_NULL)
715
state->head->extra = Z_NULL;
718
if (state->flags & 0x0400) {
719
copy = state->length;
720
if (copy > have) copy = have;
722
if (state->head != Z_NULL &&
723
state->head->extra != Z_NULL) {
724
len = state->head->extra_len - state->length;
725
zmemcpy(state->head->extra + len, next,
726
len + copy > state->head->extra_max ?
727
state->head->extra_max - len : copy);
729
if (state->flags & 0x0200)
730
state->check = crc32(state->check, next, copy);
733
state->length -= copy;
735
if (state->length) goto inf_leave;
740
if (state->flags & 0x0800) {
741
if (have == 0) goto inf_leave;
744
len = (unsigned)(next[copy++]);
745
if (state->head != Z_NULL &&
746
state->head->name != Z_NULL &&
747
state->length < state->head->name_max)
748
state->head->name[state->length++] = len;
749
} while (len && copy < have);
750
if (state->flags & 0x0200)
751
state->check = crc32(state->check, next, copy);
754
if (len) goto inf_leave;
756
else if (state->head != Z_NULL)
757
state->head->name = Z_NULL;
759
state->mode = COMMENT;
761
if (state->flags & 0x1000) {
762
if (have == 0) goto inf_leave;
765
len = (unsigned)(next[copy++]);
766
if (state->head != Z_NULL &&
767
state->head->comment != Z_NULL &&
768
state->length < state->head->comm_max)
769
state->head->comment[state->length++] = len;
770
} while (len && copy < have);
771
if (state->flags & 0x0200)
772
state->check = crc32(state->check, next, copy);
775
if (len) goto inf_leave;
777
else if (state->head != Z_NULL)
778
state->head->comment = Z_NULL;
781
if (state->flags & 0x0200) {
783
if (hold != (state->check & 0xffff)) {
784
strm->msg = (char *)"header crc mismatch";
790
if (state->head != Z_NULL) {
791
state->head->hcrc = (int)((state->flags >> 9) & 1);
792
state->head->done = 1;
794
strm->adler = state->check = crc32(0L, Z_NULL, 0);
800
strm->adler = state->check = REVERSE(hold);
804
if (state->havedict == 0) {
808
strm->adler = state->check = adler32(0L, Z_NULL, 0);
811
if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
819
state->last = BITS(1);
822
case 0: /* stored block */
823
Tracev((stderr, "inflate: stored block%s\n",
824
state->last ? " (last)" : ""));
825
state->mode = STORED;
827
case 1: /* fixed block */
829
Tracev((stderr, "inflate: fixed codes block%s\n",
830
state->last ? " (last)" : ""));
831
state->mode = LEN_; /* decode codes */
832
if (flush == Z_TREES) {
837
case 2: /* dynamic block */
838
Tracev((stderr, "inflate: dynamic codes block%s\n",
839
state->last ? " (last)" : ""));
843
strm->msg = (char *)"invalid block type";
849
BYTEBITS(); /* go to byte boundary */
851
if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
852
strm->msg = (char *)"invalid stored block lengths";
856
state->length = (unsigned)hold & 0xffff;
857
Tracev((stderr, "inflate: stored length %u\n",
861
if (flush == Z_TREES) goto inf_leave;
865
copy = state->length;
867
if (copy > have) copy = have;
868
if (copy > left) copy = left;
869
if (copy == 0) goto inf_leave;
870
zmemcpy(put, next, copy);
875
state->length -= copy;
878
Tracev((stderr, "inflate: stored end\n"));
883
state->nlen = BITS(5) + 257;
885
state->ndist = BITS(5) + 1;
887
state->ncode = BITS(4) + 4;
889
#ifndef PKZIP_BUG_WORKAROUND
890
if (state->nlen > 286 || state->ndist > 30) {
891
strm->msg = (char *)"too many length or distance symbols";
896
Tracev((stderr, "inflate: table sizes ok\n"));
898
state->mode = LENLENS;
900
while (state->have < state->ncode) {
902
state->lens[order[state->have++]] = (unsigned short)BITS(3);
905
while (state->have < 19)
906
state->lens[order[state->have++]] = 0;
907
state->next = state->codes;
908
state->lencode = (code const FAR *)(state->next);
910
ret = inflate_table(CODES, state->lens, 19, &(state->next),
911
&(state->lenbits), state->work);
913
strm->msg = (char *)"invalid code lengths set";
917
Tracev((stderr, "inflate: code lengths ok\n"));
919
state->mode = CODELENS;
921
while (state->have < state->nlen + state->ndist) {
923
here = state->lencode[BITS(state->lenbits)];
924
if ((unsigned)(here.bits) <= bits) break;
930
state->lens[state->have++] = here.val;
933
if (here.val == 16) {
934
NEEDBITS(here.bits + 2);
936
if (state->have == 0) {
937
strm->msg = (char *)"invalid bit length repeat";
941
len = state->lens[state->have - 1];
945
else if (here.val == 17) {
946
NEEDBITS(here.bits + 3);
953
NEEDBITS(here.bits + 7);
959
if (state->have + copy > state->nlen + state->ndist) {
960
strm->msg = (char *)"invalid bit length repeat";
965
state->lens[state->have++] = (unsigned short)len;
969
/* handle error breaks in while */
970
if (state->mode == BAD) break;
972
/* check for end-of-block code (better have one) */
973
if (state->lens[256] == 0) {
974
strm->msg = (char *)"invalid code -- missing end-of-block";
979
/* build code tables -- note: do not change the lenbits or distbits
980
values here (9 and 6) without reading the comments in inftrees.h
981
concerning the ENOUGH constants, which depend on those values */
982
state->next = state->codes;
983
state->lencode = (code const FAR *)(state->next);
985
ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
986
&(state->lenbits), state->work);
988
strm->msg = (char *)"invalid literal/lengths set";
992
state->distcode = (code const FAR *)(state->next);
994
ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
995
&(state->next), &(state->distbits), state->work);
997
strm->msg = (char *)"invalid distances set";
1001
Tracev((stderr, "inflate: codes ok\n"));
1003
if (flush == Z_TREES) goto inf_leave;
1007
if (have >= 6 && left >= 258) {
1009
inflate_fast(strm, out);
1011
if (state->mode == TYPE)
1017
here = state->lencode[BITS(state->lenbits)];
1018
if ((unsigned)(here.bits) <= bits) break;
1021
if (here.op && (here.op & 0xf0) == 0) {
1024
here = state->lencode[last.val +
1025
(BITS(last.bits + last.op) >> last.bits)];
1026
if ((unsigned)(last.bits + here.bits) <= bits) break;
1029
DROPBITS(last.bits);
1030
state->back += last.bits;
1032
DROPBITS(here.bits);
1033
state->back += here.bits;
1034
state->length = (unsigned)here.val;
1035
if ((int)(here.op) == 0) {
1036
Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1037
"inflate: literal '%c'\n" :
1038
"inflate: literal 0x%02x\n", here.val));
1043
Tracevv((stderr, "inflate: end of block\n"));
1049
strm->msg = (char *)"invalid literal/length code";
1053
state->extra = (unsigned)(here.op) & 15;
1054
state->mode = LENEXT;
1057
NEEDBITS(state->extra);
1058
state->length += BITS(state->extra);
1059
DROPBITS(state->extra);
1060
state->back += state->extra;
1062
Tracevv((stderr, "inflate: length %u\n", state->length));
1063
state->was = state->length;
1067
here = state->distcode[BITS(state->distbits)];
1068
if ((unsigned)(here.bits) <= bits) break;
1071
if ((here.op & 0xf0) == 0) {
1074
here = state->distcode[last.val +
1075
(BITS(last.bits + last.op) >> last.bits)];
1076
if ((unsigned)(last.bits + here.bits) <= bits) break;
1079
DROPBITS(last.bits);
1080
state->back += last.bits;
1082
DROPBITS(here.bits);
1083
state->back += here.bits;
1085
strm->msg = (char *)"invalid distance code";
1089
state->offset = (unsigned)here.val;
1090
state->extra = (unsigned)(here.op) & 15;
1091
state->mode = DISTEXT;
1094
NEEDBITS(state->extra);
1095
state->offset += BITS(state->extra);
1096
DROPBITS(state->extra);
1097
state->back += state->extra;
1099
#ifdef INFLATE_STRICT
1100
if (state->offset > state->dmax) {
1101
strm->msg = (char *)"invalid distance too far back";
1106
Tracevv((stderr, "inflate: distance %u\n", state->offset));
1107
state->mode = MATCH;
1109
if (left == 0) goto inf_leave;
1111
if (state->offset > copy) { /* copy from window */
1112
copy = state->offset - copy;
1113
if (copy > state->whave) {
1115
strm->msg = (char *)"invalid distance too far back";
1119
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1120
Trace((stderr, "inflate.c too far\n"));
1121
copy -= state->whave;
1122
if (copy > state->length) copy = state->length;
1123
if (copy > left) copy = left;
1125
state->length -= copy;
1129
if (state->length == 0) state->mode = LEN;
1133
if (copy > state->wnext) {
1134
copy -= state->wnext;
1135
from = state->window + (state->wsize - copy);
1138
from = state->window + (state->wnext - copy);
1139
if (copy > state->length) copy = state->length;
1141
else { /* copy from output */
1142
from = put - state->offset;
1143
copy = state->length;
1145
if (copy > left) copy = left;
1147
state->length -= copy;
1151
if (state->length == 0) state->mode = LEN;
1154
if (left == 0) goto inf_leave;
1155
*put++ = (unsigned char)(state->length);
1163
strm->total_out += out;
1164
state->total += out;
1166
strm->adler = state->check =
1167
UPDATE(state->check, put - out, out);
1171
state->flags ? hold :
1173
REVERSE(hold)) != state->check) {
1174
strm->msg = (char *)"incorrect data check";
1179
Tracev((stderr, "inflate: check matches trailer\n"));
1182
state->mode = LENGTH;
1184
if (state->wrap && state->flags) {
1186
if (hold != (state->total & 0xffffffffUL)) {
1187
strm->msg = (char *)"incorrect length check";
1192
Tracev((stderr, "inflate: length matches trailer\n"));
1206
return Z_STREAM_ERROR;
1210
Return from inflate(), updating the total counts and the check value.
1211
If there was no progress during the inflate() call, return a buffer
1212
error. Call updatewindow() to create and/or update the window state.
1213
Note: a memory error from inflate() is non-recoverable.
1217
if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1218
if (updatewindow(strm, out)) {
1222
in -= strm->avail_in;
1223
out -= strm->avail_out;
1224
strm->total_in += in;
1225
strm->total_out += out;
1226
state->total += out;
1227
if (state->wrap && out)
1228
strm->adler = state->check =
1229
UPDATE(state->check, strm->next_out - out, out);
1230
strm->data_type = state->bits + (state->last ? 64 : 0) +
1231
(state->mode == TYPE ? 128 : 0) +
1232
(state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1233
if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1238
int ZEXPORT inflateEnd(strm)
1241
struct inflate_state FAR *state;
1242
if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1243
return Z_STREAM_ERROR;
1244
state = (struct inflate_state FAR *)strm->state;
1245
if (state->window != Z_NULL) ZFREE(strm, state->window);
1246
ZFREE(strm, strm->state);
1247
strm->state = Z_NULL;
1248
Tracev((stderr, "inflate: end\n"));
1252
int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1254
const Bytef *dictionary;
1257
struct inflate_state FAR *state;
1261
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1262
state = (struct inflate_state FAR *)strm->state;
1263
if (state->wrap != 0 && state->mode != DICT)
1264
return Z_STREAM_ERROR;
1266
/* check for correct dictionary id */
1267
if (state->mode == DICT) {
1268
id = adler32(0L, Z_NULL, 0);
1269
id = adler32(id, dictionary, dictLength);
1270
if (id != state->check)
1271
return Z_DATA_ERROR;
1274
/* copy dictionary to window */
1275
if (updatewindow(strm, strm->avail_out)) {
1279
if (dictLength > state->wsize) {
1280
zmemcpy(state->window, dictionary + dictLength - state->wsize,
1282
state->whave = state->wsize;
1285
zmemcpy(state->window + state->wsize - dictLength, dictionary,
1287
state->whave = dictLength;
1289
state->havedict = 1;
1290
Tracev((stderr, "inflate: dictionary set\n"));
1294
int ZEXPORT inflateGetHeader(strm, head)
1298
struct inflate_state FAR *state;
1301
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1302
state = (struct inflate_state FAR *)strm->state;
1303
if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1305
/* save header structure */
1312
Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1313
or when out of input. When called, *have is the number of pattern bytes
1314
found in order so far, in 0..3. On return *have is updated to the new
1315
state. If on return *have equals four, then the pattern was found and the
1316
return value is how many bytes were read including the last byte of the
1317
pattern. If *have is less than four, then the pattern has not been found
1318
yet and the return value is len. In the latter case, syncsearch() can be
1319
called again with more data and the *have state. *have is initialized to
1320
zero for the first call.
1322
local unsigned syncsearch(have, buf, len)
1324
unsigned char FAR *buf;
1332
while (next < len && got < 4) {
1333
if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1345
int ZEXPORT inflateSync(strm)
1348
unsigned len; /* number of bytes to look at or looked at */
1349
unsigned long in, out; /* temporary to save total_in and total_out */
1350
unsigned char buf[4]; /* to restore bit buffer to byte string */
1351
struct inflate_state FAR *state;
1353
/* check parameters */
1354
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1355
state = (struct inflate_state FAR *)strm->state;
1356
if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1358
/* if first time, start search in bit buffer */
1359
if (state->mode != SYNC) {
1361
state->hold <<= state->bits & 7;
1362
state->bits -= state->bits & 7;
1364
while (state->bits >= 8) {
1365
buf[len++] = (unsigned char)(state->hold);
1370
syncsearch(&(state->have), buf, len);
1373
/* search available input */
1374
len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1375
strm->avail_in -= len;
1376
strm->next_in += len;
1377
strm->total_in += len;
1379
/* return no joy or set up to restart inflate() on a new block */
1380
if (state->have != 4) return Z_DATA_ERROR;
1381
in = strm->total_in; out = strm->total_out;
1383
strm->total_in = in; strm->total_out = out;
1389
Returns true if inflate is currently at the end of a block generated by
1390
Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1391
implementation to provide an additional safety check. PPP uses
1392
Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1393
block. When decompressing, PPP checks that at the end of input packet,
1394
inflate is waiting for these length bytes.
1396
int ZEXPORT inflateSyncPoint(strm)
1399
struct inflate_state FAR *state;
1401
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1402
state = (struct inflate_state FAR *)strm->state;
1403
return state->mode == STORED && state->bits == 0;
1406
int ZEXPORT inflateCopy(dest, source)
1410
struct inflate_state FAR *state;
1411
struct inflate_state FAR *copy;
1412
unsigned char FAR *window;
1416
if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1417
source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1418
return Z_STREAM_ERROR;
1419
state = (struct inflate_state FAR *)source->state;
1421
/* allocate space */
1422
copy = (struct inflate_state FAR *)
1423
ZALLOC(source, 1, sizeof(struct inflate_state));
1424
if (copy == Z_NULL) return Z_MEM_ERROR;
1426
if (state->window != Z_NULL) {
1427
window = (unsigned char FAR *)
1428
ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1429
if (window == Z_NULL) {
1430
ZFREE(source, copy);
1436
zmemcpy(dest, source, sizeof(z_stream));
1437
zmemcpy(copy, state, sizeof(struct inflate_state));
1438
if (state->lencode >= state->codes &&
1439
state->lencode <= state->codes + ENOUGH - 1) {
1440
copy->lencode = copy->codes + (state->lencode - state->codes);
1441
copy->distcode = copy->codes + (state->distcode - state->codes);
1443
copy->next = copy->codes + (state->next - state->codes);
1444
if (window != Z_NULL) {
1445
wsize = 1U << state->wbits;
1446
zmemcpy(window, state->window, wsize);
1448
copy->window = window;
1449
dest->state = (struct internal_state FAR *)copy;
1453
int ZEXPORT inflateUndermine(strm, subvert)
1457
struct inflate_state FAR *state;
1459
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1460
state = (struct inflate_state FAR *)strm->state;
1461
state->sane = !subvert;
1462
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1466
return Z_DATA_ERROR;
1470
long ZEXPORT inflateMark(strm)
1473
struct inflate_state FAR *state;
1475
if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16;
1476
state = (struct inflate_state FAR *)strm->state;
1477
return ((long)(state->back) << 16) +
1478
(state->mode == COPY ? state->length :
1479
(state->mode == MATCH ? state->was - state->length : 0));