1
/* inflate.c -- zlib decompression
2
* Copyright (C) 1995-2011 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 */
522
/* Reverse the bytes in a 32-bit value */
524
((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
525
(((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
528
inflate() uses a state machine to process as much input data and generate as
529
much output data as possible before returning. The state machine is
530
structured roughly as follows:
532
for (;;) switch (state) {
535
if (not enough input data or output space to make progress)
537
... make progress ...
543
so when inflate() is called again, the same case is attempted again, and
544
if the appropriate resources are provided, the machine proceeds to the
545
next state. The NEEDBITS() macro is usually the way the state evaluates
546
whether it can proceed or should return. NEEDBITS() does the return if
547
the requested bits are not available. The typical use of the BITS macros
551
... do something with BITS(n) ...
554
where NEEDBITS(n) either returns from inflate() if there isn't enough
555
input left to load n bits into the accumulator, or it continues. BITS(n)
556
gives the low n bits in the accumulator. When done, DROPBITS(n) drops
557
the low n bits off the accumulator. INITBITS() clears the accumulator
558
and sets the number of available bits to zero. BYTEBITS() discards just
559
enough bits to put the accumulator on a byte boundary. After BYTEBITS()
560
and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
562
NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
563
if there is no input available. The decoding of variable length codes uses
564
PULLBYTE() directly in order to pull just enough bytes to decode the next
567
Some states loop until they get enough input, making sure that enough
568
state information is maintained to continue the loop where it left off
569
if NEEDBITS() returns in the loop. For example, want, need, and keep
570
would all have to actually be part of the saved state in case NEEDBITS()
574
while (want < need) {
576
keep[want++] = BITS(n);
582
As shown above, if the next state is also the next case, then the break
585
A state may also return if there is not enough output space available to
586
complete that state. Those states are copying stored data, writing a
587
literal byte, and copying a matching string.
589
When returning, a "goto inf_leave" is used to update the total counters,
590
update the check value, and determine whether any progress has been made
591
during that inflate() call in order to return the proper return code.
592
Progress is defined as a change in either strm->avail_in or strm->avail_out.
593
When there is a window, goto inf_leave will update the window with the last
594
output written. If a goto inf_leave occurs in the middle of decompression
595
and there is no window currently, goto inf_leave will create one and copy
596
output to the window for the next call of inflate().
598
In this implementation, the flush parameter of inflate() only affects the
599
return code (per zlib.h). inflate() always writes as much as possible to
600
strm->next_out, given the space available and the provided input--the effect
601
documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
602
the allocation of and copying into a sliding window until necessary, which
603
provides the effect documented in zlib.h for Z_FINISH when the entire input
604
stream available. So the only thing the flush parameter actually does is:
605
when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
606
will return Z_BUF_ERROR if it has not reached the end of the stream.
609
int ZEXPORT inflate(strm, flush)
613
struct inflate_state FAR *state;
614
unsigned char FAR *next; /* next input */
615
unsigned char FAR *put; /* next output */
616
unsigned have, left; /* available input and output */
617
unsigned long hold; /* bit buffer */
618
unsigned bits; /* bits in bit buffer */
619
unsigned in, out; /* save starting available input and output */
620
unsigned copy; /* number of stored or match bytes to copy */
621
unsigned char FAR *from; /* where to copy match bytes from */
622
code here; /* current decoding table entry */
623
code last; /* parent table entry */
624
unsigned len; /* length to copy for repeats, bits to drop */
625
int ret; /* return code */
627
unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
629
static const unsigned short order[19] = /* permutation of code lengths */
630
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
632
if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
633
(strm->next_in == Z_NULL && strm->avail_in != 0))
634
return Z_STREAM_ERROR;
636
state = (struct inflate_state FAR *)strm->state;
637
if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
643
switch (state->mode) {
645
if (state->wrap == 0) {
646
state->mode = TYPEDO;
651
if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
652
state->check = crc32(0L, Z_NULL, 0);
653
CRC2(state->check, hold);
658
state->flags = 0; /* expect zlib header */
659
if (state->head != Z_NULL)
660
state->head->done = -1;
661
if (!(state->wrap & 1) || /* check if zlib header allowed */
665
((BITS(8) << 8) + (hold >> 8)) % 31) {
666
strm->msg = (char *)"incorrect header check";
670
if (BITS(4) != Z_DEFLATED) {
671
strm->msg = (char *)"unknown compression method";
677
if (state->wbits == 0)
679
else if (len > state->wbits) {
680
strm->msg = (char *)"invalid window size";
684
state->dmax = 1U << len;
685
Tracev((stderr, "inflate: zlib header ok\n"));
686
strm->adler = state->check = adler32(0L, Z_NULL, 0);
687
state->mode = hold & 0x200 ? DICTID : TYPE;
693
state->flags = (int)(hold);
694
if ((state->flags & 0xff) != Z_DEFLATED) {
695
strm->msg = (char *)"unknown compression method";
699
if (state->flags & 0xe000) {
700
strm->msg = (char *)"unknown header flags set";
704
if (state->head != Z_NULL)
705
state->head->text = (int)((hold >> 8) & 1);
706
if (state->flags & 0x0200) CRC2(state->check, hold);
711
if (state->head != Z_NULL)
712
state->head->time = hold;
713
if (state->flags & 0x0200) CRC4(state->check, hold);
718
if (state->head != Z_NULL) {
719
state->head->xflags = (int)(hold & 0xff);
720
state->head->os = (int)(hold >> 8);
722
if (state->flags & 0x0200) CRC2(state->check, hold);
726
if (state->flags & 0x0400) {
728
state->length = (unsigned)(hold);
729
if (state->head != Z_NULL)
730
state->head->extra_len = (unsigned)hold;
731
if (state->flags & 0x0200) CRC2(state->check, hold);
734
else if (state->head != Z_NULL)
735
state->head->extra = Z_NULL;
738
if (state->flags & 0x0400) {
739
copy = state->length;
740
if (copy > have) copy = have;
742
if (state->head != Z_NULL &&
743
state->head->extra != Z_NULL) {
744
len = state->head->extra_len - state->length;
745
zmemcpy(state->head->extra + len, next,
746
len + copy > state->head->extra_max ?
747
state->head->extra_max - len : copy);
749
if (state->flags & 0x0200)
750
state->check = crc32(state->check, next, copy);
753
state->length -= copy;
755
if (state->length) goto inf_leave;
760
if (state->flags & 0x0800) {
761
if (have == 0) goto inf_leave;
764
len = (unsigned)(next[copy++]);
765
if (state->head != Z_NULL &&
766
state->head->name != Z_NULL &&
767
state->length < state->head->name_max)
768
state->head->name[state->length++] = len;
769
} while (len && copy < have);
770
if (state->flags & 0x0200)
771
state->check = crc32(state->check, next, copy);
774
if (len) goto inf_leave;
776
else if (state->head != Z_NULL)
777
state->head->name = Z_NULL;
779
state->mode = COMMENT;
781
if (state->flags & 0x1000) {
782
if (have == 0) goto inf_leave;
785
len = (unsigned)(next[copy++]);
786
if (state->head != Z_NULL &&
787
state->head->comment != Z_NULL &&
788
state->length < state->head->comm_max)
789
state->head->comment[state->length++] = len;
790
} while (len && copy < have);
791
if (state->flags & 0x0200)
792
state->check = crc32(state->check, next, copy);
795
if (len) goto inf_leave;
797
else if (state->head != Z_NULL)
798
state->head->comment = Z_NULL;
801
if (state->flags & 0x0200) {
803
if (hold != (state->check & 0xffff)) {
804
strm->msg = (char *)"header crc mismatch";
810
if (state->head != Z_NULL) {
811
state->head->hcrc = (int)((state->flags >> 9) & 1);
812
state->head->done = 1;
814
strm->adler = state->check = crc32(0L, Z_NULL, 0);
820
strm->adler = state->check = REVERSE(hold);
824
if (state->havedict == 0) {
828
strm->adler = state->check = adler32(0L, Z_NULL, 0);
831
if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
839
state->last = BITS(1);
842
case 0: /* stored block */
843
Tracev((stderr, "inflate: stored block%s\n",
844
state->last ? " (last)" : ""));
845
state->mode = STORED;
847
case 1: /* fixed block */
849
Tracev((stderr, "inflate: fixed codes block%s\n",
850
state->last ? " (last)" : ""));
851
state->mode = LEN_; /* decode codes */
852
if (flush == Z_TREES) {
857
case 2: /* dynamic block */
858
Tracev((stderr, "inflate: dynamic codes block%s\n",
859
state->last ? " (last)" : ""));
863
strm->msg = (char *)"invalid block type";
869
BYTEBITS(); /* go to byte boundary */
871
if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
872
strm->msg = (char *)"invalid stored block lengths";
876
state->length = (unsigned)hold & 0xffff;
877
Tracev((stderr, "inflate: stored length %u\n",
881
if (flush == Z_TREES) goto inf_leave;
885
copy = state->length;
887
if (copy > have) copy = have;
888
if (copy > left) copy = left;
889
if (copy == 0) goto inf_leave;
890
zmemcpy(put, next, copy);
895
state->length -= copy;
898
Tracev((stderr, "inflate: stored end\n"));
903
state->nlen = BITS(5) + 257;
905
state->ndist = BITS(5) + 1;
907
state->ncode = BITS(4) + 4;
909
#ifndef PKZIP_BUG_WORKAROUND
910
if (state->nlen > 286 || state->ndist > 30) {
911
strm->msg = (char *)"too many length or distance symbols";
916
Tracev((stderr, "inflate: table sizes ok\n"));
918
state->mode = LENLENS;
920
while (state->have < state->ncode) {
922
state->lens[order[state->have++]] = (unsigned short)BITS(3);
925
while (state->have < 19)
926
state->lens[order[state->have++]] = 0;
927
state->next = state->codes;
928
state->lencode = (code const FAR *)(state->next);
930
ret = inflate_table(CODES, state->lens, 19, &(state->next),
931
&(state->lenbits), state->work);
933
strm->msg = (char *)"invalid code lengths set";
937
Tracev((stderr, "inflate: code lengths ok\n"));
939
state->mode = CODELENS;
941
while (state->have < state->nlen + state->ndist) {
943
here = state->lencode[BITS(state->lenbits)];
944
if ((unsigned)(here.bits) <= bits) break;
949
state->lens[state->have++] = here.val;
952
if (here.val == 16) {
953
NEEDBITS(here.bits + 2);
955
if (state->have == 0) {
956
strm->msg = (char *)"invalid bit length repeat";
960
len = state->lens[state->have - 1];
964
else if (here.val == 17) {
965
NEEDBITS(here.bits + 3);
972
NEEDBITS(here.bits + 7);
978
if (state->have + copy > state->nlen + state->ndist) {
979
strm->msg = (char *)"invalid bit length repeat";
984
state->lens[state->have++] = (unsigned short)len;
988
/* handle error breaks in while */
989
if (state->mode == BAD) break;
991
/* check for end-of-block code (better have one) */
992
if (state->lens[256] == 0) {
993
strm->msg = (char *)"invalid code -- missing end-of-block";
998
/* build code tables -- note: do not change the lenbits or distbits
999
values here (9 and 6) without reading the comments in inftrees.h
1000
concerning the ENOUGH constants, which depend on those values */
1001
state->next = state->codes;
1002
state->lencode = (code const FAR *)(state->next);
1004
ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1005
&(state->lenbits), state->work);
1007
strm->msg = (char *)"invalid literal/lengths set";
1011
state->distcode = (code const FAR *)(state->next);
1012
state->distbits = 6;
1013
ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1014
&(state->next), &(state->distbits), state->work);
1016
strm->msg = (char *)"invalid distances set";
1020
Tracev((stderr, "inflate: codes ok\n"));
1022
if (flush == Z_TREES) goto inf_leave;
1026
if (have >= 6 && left >= 258) {
1028
inflate_fast(strm, out);
1030
if (state->mode == TYPE)
1036
here = state->lencode[BITS(state->lenbits)];
1037
if ((unsigned)(here.bits) <= bits) break;
1040
if (here.op && (here.op & 0xf0) == 0) {
1043
here = state->lencode[last.val +
1044
(BITS(last.bits + last.op) >> last.bits)];
1045
if ((unsigned)(last.bits + here.bits) <= bits) break;
1048
DROPBITS(last.bits);
1049
state->back += last.bits;
1051
DROPBITS(here.bits);
1052
state->back += here.bits;
1053
state->length = (unsigned)here.val;
1054
if ((int)(here.op) == 0) {
1055
Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1056
"inflate: literal '%c'\n" :
1057
"inflate: literal 0x%02x\n", here.val));
1062
Tracevv((stderr, "inflate: end of block\n"));
1068
strm->msg = (char *)"invalid literal/length code";
1072
state->extra = (unsigned)(here.op) & 15;
1073
state->mode = LENEXT;
1076
NEEDBITS(state->extra);
1077
state->length += BITS(state->extra);
1078
DROPBITS(state->extra);
1079
state->back += state->extra;
1081
Tracevv((stderr, "inflate: length %u\n", state->length));
1082
state->was = state->length;
1086
here = state->distcode[BITS(state->distbits)];
1087
if ((unsigned)(here.bits) <= bits) break;
1090
if ((here.op & 0xf0) == 0) {
1093
here = state->distcode[last.val +
1094
(BITS(last.bits + last.op) >> last.bits)];
1095
if ((unsigned)(last.bits + here.bits) <= bits) break;
1098
DROPBITS(last.bits);
1099
state->back += last.bits;
1101
DROPBITS(here.bits);
1102
state->back += here.bits;
1104
strm->msg = (char *)"invalid distance code";
1108
state->offset = (unsigned)here.val;
1109
state->extra = (unsigned)(here.op) & 15;
1110
state->mode = DISTEXT;
1113
NEEDBITS(state->extra);
1114
state->offset += BITS(state->extra);
1115
DROPBITS(state->extra);
1116
state->back += state->extra;
1118
#ifdef INFLATE_STRICT
1119
if (state->offset > state->dmax) {
1120
strm->msg = (char *)"invalid distance too far back";
1125
Tracevv((stderr, "inflate: distance %u\n", state->offset));
1126
state->mode = MATCH;
1128
if (left == 0) goto inf_leave;
1130
if (state->offset > copy) { /* copy from window */
1131
copy = state->offset - copy;
1132
if (copy > state->whave) {
1134
strm->msg = (char *)"invalid distance too far back";
1138
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1139
Trace((stderr, "inflate.c too far\n"));
1140
copy -= state->whave;
1141
if (copy > state->length) copy = state->length;
1142
if (copy > left) copy = left;
1144
state->length -= copy;
1148
if (state->length == 0) state->mode = LEN;
1152
if (copy > state->wnext) {
1153
copy -= state->wnext;
1154
from = state->window + (state->wsize - copy);
1157
from = state->window + (state->wnext - copy);
1158
if (copy > state->length) copy = state->length;
1160
else { /* copy from output */
1161
from = put - state->offset;
1162
copy = state->length;
1164
if (copy > left) copy = left;
1166
state->length -= copy;
1170
if (state->length == 0) state->mode = LEN;
1173
if (left == 0) goto inf_leave;
1174
*put++ = (unsigned char)(state->length);
1182
strm->total_out += out;
1183
state->total += out;
1185
strm->adler = state->check =
1186
UPDATE(state->check, put - out, out);
1190
state->flags ? hold :
1192
REVERSE(hold)) != state->check) {
1193
strm->msg = (char *)"incorrect data check";
1198
Tracev((stderr, "inflate: check matches trailer\n"));
1201
state->mode = LENGTH;
1203
if (state->wrap && state->flags) {
1205
if (hold != (state->total & 0xffffffffUL)) {
1206
strm->msg = (char *)"incorrect length check";
1211
Tracev((stderr, "inflate: length matches trailer\n"));
1225
return Z_STREAM_ERROR;
1229
Return from inflate(), updating the total counts and the check value.
1230
If there was no progress during the inflate() call, return a buffer
1231
error. Call updatewindow() to create and/or update the window state.
1232
Note: a memory error from inflate() is non-recoverable.
1236
if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1237
(state->mode < CHECK || flush != Z_FINISH)))
1238
if (updatewindow(strm, out)) {
1242
in -= strm->avail_in;
1243
out -= strm->avail_out;
1244
strm->total_in += in;
1245
strm->total_out += out;
1246
state->total += out;
1247
if (state->wrap && out)
1248
strm->adler = state->check =
1249
UPDATE(state->check, strm->next_out - out, out);
1250
strm->data_type = state->bits + (state->last ? 64 : 0) +
1251
(state->mode == TYPE ? 128 : 0) +
1252
(state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1253
if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1258
int ZEXPORT inflateEnd(strm)
1261
struct inflate_state FAR *state;
1262
if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1263
return Z_STREAM_ERROR;
1264
state = (struct inflate_state FAR *)strm->state;
1265
if (state->window != Z_NULL) ZFREE(strm, state->window);
1266
ZFREE(strm, strm->state);
1267
strm->state = Z_NULL;
1268
Tracev((stderr, "inflate: end\n"));
1272
int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1274
const Bytef *dictionary;
1277
struct inflate_state FAR *state;
1279
unsigned char *next;
1284
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1285
state = (struct inflate_state FAR *)strm->state;
1286
if (state->wrap != 0 && state->mode != DICT)
1287
return Z_STREAM_ERROR;
1289
/* check for correct dictionary id */
1290
if (state->mode == DICT) {
1291
id = adler32(0L, Z_NULL, 0);
1292
id = adler32(id, dictionary, dictLength);
1293
if (id != state->check)
1294
return Z_DATA_ERROR;
1297
/* copy dictionary to window using updatewindow(), which will amend the
1298
existing dictionary if appropriate */
1299
next = strm->next_out;
1300
avail = strm->avail_out;
1301
strm->next_out = (Bytef *)dictionary + dictLength;
1302
strm->avail_out = 0;
1303
ret = updatewindow(strm, dictLength);
1304
strm->avail_out = avail;
1305
strm->next_out = next;
1310
state->havedict = 1;
1311
Tracev((stderr, "inflate: dictionary set\n"));
1315
int ZEXPORT inflateGetHeader(strm, head)
1319
struct inflate_state FAR *state;
1322
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1323
state = (struct inflate_state FAR *)strm->state;
1324
if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1326
/* save header structure */
1333
Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1334
or when out of input. When called, *have is the number of pattern bytes
1335
found in order so far, in 0..3. On return *have is updated to the new
1336
state. If on return *have equals four, then the pattern was found and the
1337
return value is how many bytes were read including the last byte of the
1338
pattern. If *have is less than four, then the pattern has not been found
1339
yet and the return value is len. In the latter case, syncsearch() can be
1340
called again with more data and the *have state. *have is initialized to
1341
zero for the first call.
1343
local unsigned syncsearch(have, buf, len)
1345
unsigned char FAR *buf;
1353
while (next < len && got < 4) {
1354
if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1366
int ZEXPORT inflateSync(strm)
1369
unsigned len; /* number of bytes to look at or looked at */
1370
unsigned long in, out; /* temporary to save total_in and total_out */
1371
unsigned char buf[4]; /* to restore bit buffer to byte string */
1372
struct inflate_state FAR *state;
1374
/* check parameters */
1375
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1376
state = (struct inflate_state FAR *)strm->state;
1377
if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1379
/* if first time, start search in bit buffer */
1380
if (state->mode != SYNC) {
1382
state->hold <<= state->bits & 7;
1383
state->bits -= state->bits & 7;
1385
while (state->bits >= 8) {
1386
buf[len++] = (unsigned char)(state->hold);
1391
syncsearch(&(state->have), buf, len);
1394
/* search available input */
1395
len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1396
strm->avail_in -= len;
1397
strm->next_in += len;
1398
strm->total_in += len;
1400
/* return no joy or set up to restart inflate() on a new block */
1401
if (state->have != 4) return Z_DATA_ERROR;
1402
in = strm->total_in; out = strm->total_out;
1404
strm->total_in = in; strm->total_out = out;
1410
Returns true if inflate is currently at the end of a block generated by
1411
Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1412
implementation to provide an additional safety check. PPP uses
1413
Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1414
block. When decompressing, PPP checks that at the end of input packet,
1415
inflate is waiting for these length bytes.
1417
int ZEXPORT inflateSyncPoint(strm)
1420
struct inflate_state FAR *state;
1422
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1423
state = (struct inflate_state FAR *)strm->state;
1424
return state->mode == STORED && state->bits == 0;
1427
int ZEXPORT inflateCopy(dest, source)
1431
struct inflate_state FAR *state;
1432
struct inflate_state FAR *copy;
1433
unsigned char FAR *window;
1437
if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1438
source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1439
return Z_STREAM_ERROR;
1440
state = (struct inflate_state FAR *)source->state;
1442
/* allocate space */
1443
copy = (struct inflate_state FAR *)
1444
ZALLOC(source, 1, sizeof(struct inflate_state));
1445
if (copy == Z_NULL) return Z_MEM_ERROR;
1447
if (state->window != Z_NULL) {
1448
window = (unsigned char FAR *)
1449
ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1450
if (window == Z_NULL) {
1451
ZFREE(source, copy);
1457
zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1458
zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1459
if (state->lencode >= state->codes &&
1460
state->lencode <= state->codes + ENOUGH - 1) {
1461
copy->lencode = copy->codes + (state->lencode - state->codes);
1462
copy->distcode = copy->codes + (state->distcode - state->codes);
1464
copy->next = copy->codes + (state->next - state->codes);
1465
if (window != Z_NULL) {
1466
wsize = 1U << state->wbits;
1467
zmemcpy(window, state->window, wsize);
1469
copy->window = window;
1470
dest->state = (struct internal_state FAR *)copy;
1474
int ZEXPORT inflateUndermine(strm, subvert)
1478
struct inflate_state FAR *state;
1480
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1481
state = (struct inflate_state FAR *)strm->state;
1482
state->sane = !subvert;
1483
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1487
return Z_DATA_ERROR;
1491
long ZEXPORT inflateMark(strm)
1494
struct inflate_state FAR *state;
1496
if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16;
1497
state = (struct inflate_state FAR *)strm->state;
1498
return ((long)(state->back) << 16) +
1499
(state->mode == COPY ? state->length :
1500
(state->mode == MATCH ? state->was - state->length : 0));