1
/* inflate.c -- zlib decompression
2
* Copyright (C) 1995-2005 Mark Adler
3
* For conditions of distribution and use, see copyright notice in zlib.h
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 write == 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 const 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;
124
Tracev((stderr, "inflate: reset\n"));
128
int ZEXPORT inflatePrime(strm, bits, value)
133
struct inflate_state FAR *state;
135
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
136
state = (struct inflate_state FAR *)strm->state;
137
if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
138
value &= (1L << bits) - 1;
139
state->hold += value << state->bits;
144
int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
150
struct inflate_state FAR *state;
152
if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
153
stream_size != (int)(sizeof(z_stream)))
154
return Z_VERSION_ERROR;
155
if (strm == Z_NULL) return Z_STREAM_ERROR;
156
strm->msg = Z_NULL; /* in case we return an error */
157
if (strm->zalloc == (alloc_func)0) {
158
strm->zalloc = zcalloc;
159
strm->opaque = (voidpf)0;
161
if (strm->zfree == (free_func)0) strm->zfree = zcfree;
162
state = (struct inflate_state FAR *)
163
ZALLOC(strm, 1, sizeof(struct inflate_state));
164
if (state == Z_NULL) return Z_MEM_ERROR;
165
Tracev((stderr, "inflate: allocated\n"));
166
strm->state = (struct internal_state FAR *)state;
167
if (windowBits < 0) {
169
windowBits = -windowBits;
172
state->wrap = (windowBits >> 4) + 1;
174
if (windowBits < 48) windowBits &= 15;
177
if (windowBits < 8 || windowBits > 15) {
179
strm->state = Z_NULL;
180
return Z_STREAM_ERROR;
182
state->wbits = (unsigned)windowBits;
183
state->window = Z_NULL;
184
return inflateReset(strm);
187
int ZEXPORT inflateInit_(strm, version, stream_size)
192
return inflateInit2_(strm, DEF_WBITS, version, stream_size);
196
Return state with length and distance decoding tables and index sizes set to
197
fixed code decoding. Normally this returns fixed tables from inffixed.h.
198
If BUILDFIXED is defined, then instead this routine builds the tables the
199
first time it's called, and returns those tables the first time and
200
thereafter. This reduces the size of the code by about 2K bytes, in
201
exchange for a little execution time. However, BUILDFIXED should not be
202
used for threaded applications, since the rewriting of the tables and virgin
203
may not be thread-safe.
205
local void fixedtables(state)
206
struct inflate_state FAR *state;
209
static int virgin = 1;
210
static code *lenfix, *distfix;
211
static code fixed[544];
213
/* build fixed huffman tables if first call (may not be thread safe) */
218
/* literal/length table */
220
while (sym < 144) state->lens[sym++] = 8;
221
while (sym < 256) state->lens[sym++] = 9;
222
while (sym < 280) state->lens[sym++] = 7;
223
while (sym < 288) state->lens[sym++] = 8;
227
inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
231
while (sym < 32) state->lens[sym++] = 5;
234
inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
236
/* do this just once */
239
#else /* !BUILDFIXED */
240
# include "inffixed.h"
241
#endif /* BUILDFIXED */
242
state->lencode = lenfix;
244
state->distcode = distfix;
252
Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
253
defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
254
those tables to stdout, which would be piped to inffixed.h. A small program
255
can simply call makefixed to do this:
257
void makefixed(void);
265
Then that can be linked with zlib built with MAKEFIXED defined and run:
272
struct inflate_state state;
275
puts(" /* inffixed.h -- table for decoding fixed codes");
276
puts(" * Generated automatically by makefixed().");
279
puts(" /* WARNING: this file should *not* be used by applications.");
280
puts(" It is part of the implementation of this library and is");
281
puts(" subject to change. Applications should only use zlib.h.");
285
printf(" static const code lenfix[%u] = {", size);
288
if ((low % 7) == 0) printf("\n ");
289
printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
290
state.lencode[low].val);
291
if (++low == size) break;
296
printf("\n static const code distfix[%u] = {", size);
299
if ((low % 6) == 0) printf("\n ");
300
printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
301
state.distcode[low].val);
302
if (++low == size) break;
307
#endif /* MAKEFIXED */
310
Update the window with the last wsize (normally 32K) bytes written before
311
returning. If window does not exist yet, create it. This is only called
312
when a window is already in use, or when output has been written during this
313
inflate call, but the end of the deflate stream has not been reached yet.
314
It is also called to create a window for dictionary data when a dictionary
317
Providing output buffers larger than 32K to inflate() should provide a speed
318
advantage, since only the last 32K of output is copied to the sliding window
319
upon return from inflate(), and since all distances after the first 32K of
320
output will fall in the output data, making match copies simpler and faster.
321
The advantage may be dependent on the size of the processor's data caches.
323
local int updatewindow(strm, out)
327
struct inflate_state FAR *state;
330
state = (struct inflate_state FAR *)strm->state;
332
/* if it hasn't been done already, allocate space for the window */
333
if (state->window == Z_NULL) {
334
state->window = (unsigned char FAR *)
335
ZALLOC(strm, 1U << state->wbits,
336
sizeof(unsigned char));
337
if (state->window == Z_NULL) return 1;
340
/* if window not in use yet, initialize */
341
if (state->wsize == 0) {
342
state->wsize = 1U << state->wbits;
347
/* copy state->wsize or less output bytes into the circular window */
348
copy = out - strm->avail_out;
349
if (copy >= state->wsize) {
350
zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
352
state->whave = state->wsize;
355
dist = state->wsize - state->write;
356
if (dist > copy) dist = copy;
357
zmemcpy(state->window + state->write, strm->next_out - copy, dist);
360
zmemcpy(state->window, strm->next_out - copy, copy);
362
state->whave = state->wsize;
365
state->write += dist;
366
if (state->write == state->wsize) state->write = 0;
367
if (state->whave < state->wsize) state->whave += dist;
373
/* Macros for inflate(): */
375
/* check function to use adler32() for zlib or crc32() for gzip */
377
# define UPDATE(check, buf, len) \
378
(state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
380
# define UPDATE(check, buf, len) adler32(check, buf, len)
383
/* check macros for header crc */
385
# define CRC2(check, word) \
387
hbuf[0] = (unsigned char)(word); \
388
hbuf[1] = (unsigned char)((word) >> 8); \
389
check = crc32(check, hbuf, 2); \
392
# define CRC4(check, word) \
394
hbuf[0] = (unsigned char)(word); \
395
hbuf[1] = (unsigned char)((word) >> 8); \
396
hbuf[2] = (unsigned char)((word) >> 16); \
397
hbuf[3] = (unsigned char)((word) >> 24); \
398
check = crc32(check, hbuf, 4); \
402
/* Load registers with state in inflate() for speed */
405
put = strm->next_out; \
406
left = strm->avail_out; \
407
next = strm->next_in; \
408
have = strm->avail_in; \
409
hold = state->hold; \
410
bits = state->bits; \
413
/* Restore state from registers in inflate() */
416
strm->next_out = put; \
417
strm->avail_out = left; \
418
strm->next_in = next; \
419
strm->avail_in = have; \
420
state->hold = hold; \
421
state->bits = bits; \
424
/* Clear the input bit accumulator */
431
/* Get a byte of input into the bit accumulator, or return from inflate()
432
if there is no input available. */
435
if (have == 0) goto inf_leave; \
437
hold += (unsigned long)(*next++) << bits; \
441
/* Assure that there are at least n bits in the bit accumulator. If there is
442
not enough available input to do that, then return from inflate(). */
443
#define NEEDBITS(n) \
445
while (bits < (unsigned)(n)) \
449
/* Return the low n bits of the bit accumulator (n < 16) */
451
((unsigned)hold & ((1U << (n)) - 1))
453
/* Remove n bits from the bit accumulator */
454
#define DROPBITS(n) \
457
bits -= (unsigned)(n); \
460
/* Remove zero to seven bits as needed to go to a byte boundary */
467
/* Reverse the bytes in a 32-bit value */
469
((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
470
(((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
473
inflate() uses a state machine to process as much input data and generate as
474
much output data as possible before returning. The state machine is
475
structured roughly as follows:
477
for (;;) switch (state) {
480
if (not enough input data or output space to make progress)
482
... make progress ...
488
so when inflate() is called again, the same case is attempted again, and
489
if the appropriate resources are provided, the machine proceeds to the
490
next state. The NEEDBITS() macro is usually the way the state evaluates
491
whether it can proceed or should return. NEEDBITS() does the return if
492
the requested bits are not available. The typical use of the BITS macros
496
... do something with BITS(n) ...
499
where NEEDBITS(n) either returns from inflate() if there isn't enough
500
input left to load n bits into the accumulator, or it continues. BITS(n)
501
gives the low n bits in the accumulator. When done, DROPBITS(n) drops
502
the low n bits off the accumulator. INITBITS() clears the accumulator
503
and sets the number of available bits to zero. BYTEBITS() discards just
504
enough bits to put the accumulator on a byte boundary. After BYTEBITS()
505
and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
507
NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
508
if there is no input available. The decoding of variable length codes uses
509
PULLBYTE() directly in order to pull just enough bytes to decode the next
512
Some states loop until they get enough input, making sure that enough
513
state information is maintained to continue the loop where it left off
514
if NEEDBITS() returns in the loop. For example, want, need, and keep
515
would all have to actually be part of the saved state in case NEEDBITS()
519
while (want < need) {
521
keep[want++] = BITS(n);
527
As shown above, if the next state is also the next case, then the break
530
A state may also return if there is not enough output space available to
531
complete that state. Those states are copying stored data, writing a
532
literal byte, and copying a matching string.
534
When returning, a "goto inf_leave" is used to update the total counters,
535
update the check value, and determine whether any progress has been made
536
during that inflate() call in order to return the proper return code.
537
Progress is defined as a change in either strm->avail_in or strm->avail_out.
538
When there is a window, goto inf_leave will update the window with the last
539
output written. If a goto inf_leave occurs in the middle of decompression
540
and there is no window currently, goto inf_leave will create one and copy
541
output to the window for the next call of inflate().
543
In this implementation, the flush parameter of inflate() only affects the
544
return code (per zlib.h). inflate() always writes as much as possible to
545
strm->next_out, given the space available and the provided input--the effect
546
documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
547
the allocation of and copying into a sliding window until necessary, which
548
provides the effect documented in zlib.h for Z_FINISH when the entire input
549
stream available. So the only thing the flush parameter actually does is:
550
when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
551
will return Z_BUF_ERROR if it has not reached the end of the stream.
554
int ZEXPORT inflate(strm, flush)
558
struct inflate_state FAR *state;
559
unsigned const char FAR *next; /* next input */
560
unsigned char FAR *put; /* next output */
561
unsigned have, left; /* available input and output */
562
unsigned long hold; /* bit buffer */
563
unsigned bits; /* bits in bit buffer */
564
unsigned in, out; /* save starting available input and output */
565
unsigned copy; /* number of stored or match bytes to copy */
566
unsigned char FAR *from; /* where to copy match bytes from */
567
code this; /* current decoding table entry */
568
code last; /* parent table entry */
569
unsigned len; /* length to copy for repeats, bits to drop */
570
int ret; /* return code */
572
unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
574
static const unsigned short order[19] = /* permutation of code lengths */
575
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
577
if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
578
(strm->next_in == Z_NULL && strm->avail_in != 0))
579
return Z_STREAM_ERROR;
581
state = (struct inflate_state FAR *)strm->state;
582
if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
588
switch (state->mode) {
590
if (state->wrap == 0) {
591
state->mode = TYPEDO;
596
if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
597
state->check = crc32(0L, Z_NULL, 0);
598
CRC2(state->check, hold);
603
state->flags = 0; /* expect zlib header */
604
if (state->head != Z_NULL)
605
state->head->done = -1;
606
if (!(state->wrap & 1) || /* check if zlib header allowed */
610
((BITS(8) << 8) + (hold >> 8)) % 31) {
611
strm->msg = "incorrect header check";
612
state->mode = BAD_DATA;
615
if (BITS(4) != Z_DEFLATED) {
616
strm->msg = "unknown compression method";
617
state->mode = BAD_DATA;
622
if (len > state->wbits) {
623
strm->msg = "invalid window size";
624
state->mode = BAD_DATA;
627
state->dmax = 1U << len;
628
Tracev((stderr, "inflate: zlib header ok\n"));
629
strm->adler = state->check = adler32(0L, Z_NULL, 0);
630
state->mode = hold & 0x200 ? DICTID : TYPE;
636
state->flags = (int)(hold);
637
if ((state->flags & 0xff) != Z_DEFLATED) {
638
strm->msg = "unknown compression method";
639
state->mode = BAD_DATA;
642
if (state->flags & 0xe000) {
643
strm->msg = "unknown header flags set";
644
state->mode = BAD_DATA;
647
if (state->head != Z_NULL)
648
state->head->text = (int)((hold >> 8) & 1);
649
if (state->flags & 0x0200) CRC2(state->check, hold);
654
if (state->head != Z_NULL)
655
state->head->time = hold;
656
if (state->flags & 0x0200) CRC4(state->check, hold);
661
if (state->head != Z_NULL) {
662
state->head->xflags = (int)(hold & 0xff);
663
state->head->os = (int)(hold >> 8);
665
if (state->flags & 0x0200) CRC2(state->check, hold);
669
if (state->flags & 0x0400) {
671
state->length = (unsigned)(hold);
672
if (state->head != Z_NULL)
673
state->head->extra_len = (unsigned)hold;
674
if (state->flags & 0x0200) CRC2(state->check, hold);
677
else if (state->head != Z_NULL)
678
state->head->extra = Z_NULL;
681
if (state->flags & 0x0400) {
682
copy = state->length;
683
if (copy > have) copy = have;
685
if (state->head != Z_NULL &&
686
state->head->extra != Z_NULL) {
687
len = state->head->extra_len - state->length;
688
zmemcpy(state->head->extra + len, next,
689
len + copy > state->head->extra_max ?
690
state->head->extra_max - len : copy);
692
if (state->flags & 0x0200)
693
state->check = crc32(state->check, next, copy);
696
state->length -= copy;
698
if (state->length) goto inf_leave;
703
if (state->flags & 0x0800) {
704
if (have == 0) goto inf_leave;
707
len = (unsigned)(next[copy++]);
708
if (state->head != Z_NULL &&
709
state->head->name != Z_NULL &&
710
state->length < state->head->name_max)
711
state->head->name[state->length++] = len;
712
} while (len && copy < have);
713
if (state->flags & 0x0200)
714
state->check = crc32(state->check, next, copy);
717
if (len) goto inf_leave;
719
else if (state->head != Z_NULL)
720
state->head->name = Z_NULL;
722
state->mode = COMMENT;
724
if (state->flags & 0x1000) {
725
if (have == 0) goto inf_leave;
728
len = (unsigned)(next[copy++]);
729
if (state->head != Z_NULL &&
730
state->head->comment != Z_NULL &&
731
state->length < state->head->comm_max)
732
state->head->comment[state->length++] = len;
733
} while (len && copy < have);
734
if (state->flags & 0x0200)
735
state->check = crc32(state->check, next, copy);
738
if (len) goto inf_leave;
740
else if (state->head != Z_NULL)
741
state->head->comment = Z_NULL;
744
if (state->flags & 0x0200) {
746
if (hold != (state->check & 0xffff)) {
747
strm->msg = "header crc mismatch";
748
state->mode = BAD_DATA;
753
if (state->head != Z_NULL) {
754
state->head->hcrc = (int)((state->flags >> 9) & 1);
755
state->head->done = 1;
757
strm->adler = state->check = crc32(0L, Z_NULL, 0);
763
strm->adler = state->check = REVERSE(hold);
767
if (state->havedict == 0) {
771
strm->adler = state->check = adler32(0L, Z_NULL, 0);
774
if (flush == Z_BLOCK) goto inf_leave;
782
state->last = BITS(1);
785
case 0: /* stored block */
786
Tracev((stderr, "inflate: stored block%s\n",
787
state->last ? " (last)" : ""));
788
state->mode = STORED;
790
case 1: /* fixed block */
792
Tracev((stderr, "inflate: fixed codes block%s\n",
793
state->last ? " (last)" : ""));
794
state->mode = LEN; /* decode codes */
796
case 2: /* dynamic block */
797
Tracev((stderr, "inflate: dynamic codes block%s\n",
798
state->last ? " (last)" : ""));
802
strm->msg = "invalid block type";
803
state->mode = BAD_DATA;
808
BYTEBITS(); /* go to byte boundary */
810
if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
811
strm->msg = "invalid stored block lengths";
812
state->mode = BAD_DATA;
815
state->length = (unsigned)hold & 0xffff;
816
Tracev((stderr, "inflate: stored length %u\n",
821
copy = state->length;
823
if (copy > have) copy = have;
824
if (copy > left) copy = left;
825
if (copy == 0) goto inf_leave;
826
zmemcpy(put, next, copy);
831
state->length -= copy;
834
Tracev((stderr, "inflate: stored end\n"));
839
state->nlen = BITS(5) + 257;
841
state->ndist = BITS(5) + 1;
843
state->ncode = BITS(4) + 4;
845
#ifndef PKZIP_BUG_WORKAROUND
846
if (state->nlen > 286 || state->ndist > 30) {
847
strm->msg = "too many length or distance symbols";
848
state->mode = BAD_DATA;
852
Tracev((stderr, "inflate: table sizes ok\n"));
854
state->mode = LENLENS;
856
while (state->have < state->ncode) {
858
state->lens[order[state->have++]] = (unsigned short)BITS(3);
861
while (state->have < 19)
862
state->lens[order[state->have++]] = 0;
863
state->next = state->codes;
864
state->lencode = (code const FAR *)(state->next);
866
ret = inflate_table(CODES, state->lens, 19, &(state->next),
867
&(state->lenbits), state->work);
869
strm->msg = "invalid code lengths set";
870
state->mode = BAD_DATA;
873
Tracev((stderr, "inflate: code lengths ok\n"));
875
state->mode = CODELENS;
877
while (state->have < state->nlen + state->ndist) {
879
this = state->lencode[BITS(state->lenbits)];
880
if ((unsigned)(this.bits) <= bits) break;
886
state->lens[state->have++] = this.val;
889
if (this.val == 16) {
890
NEEDBITS(this.bits + 2);
892
if (state->have == 0) {
893
strm->msg = "invalid bit length repeat";
894
state->mode = BAD_DATA;
897
len = state->lens[state->have - 1];
901
else if (this.val == 17) {
902
NEEDBITS(this.bits + 3);
909
NEEDBITS(this.bits + 7);
915
if (state->have + copy > state->nlen + state->ndist) {
916
strm->msg = "invalid bit length repeat";
917
state->mode = BAD_DATA;
921
state->lens[state->have++] = (unsigned short)len;
925
/* handle error breaks in while */
926
if (state->mode == BAD_DATA) break;
928
/* build code tables */
929
state->next = state->codes;
930
state->lencode = (code const FAR *)(state->next);
932
ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
933
&(state->lenbits), state->work);
935
strm->msg = "invalid literal/lengths set";
936
state->mode = BAD_DATA;
939
state->distcode = (code const FAR *)(state->next);
941
ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
942
&(state->next), &(state->distbits), state->work);
944
strm->msg = "invalid distances set";
945
state->mode = BAD_DATA;
948
Tracev((stderr, "inflate: codes ok\n"));
951
if (have >= 6 && left >= 258) {
953
inflate_fast(strm, out);
958
this = state->lencode[BITS(state->lenbits)];
959
if ((unsigned)(this.bits) <= bits) break;
962
if (this.op && (this.op & 0xf0) == 0) {
965
this = state->lencode[last.val +
966
(BITS(last.bits + last.op) >> last.bits)];
967
if ((unsigned)(last.bits + this.bits) <= bits) break;
973
state->length = (unsigned)this.val;
974
if ((int)(this.op) == 0) {
975
Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
976
"inflate: literal '%c'\n" :
977
"inflate: literal 0x%02x\n", this.val));
982
Tracevv((stderr, "inflate: end of block\n"));
987
strm->msg = "invalid literal/length code";
988
state->mode = BAD_DATA;
991
state->extra = (unsigned)(this.op) & 15;
992
state->mode = LENEXT;
995
NEEDBITS(state->extra);
996
state->length += BITS(state->extra);
997
DROPBITS(state->extra);
999
Tracevv((stderr, "inflate: length %u\n", state->length));
1003
this = state->distcode[BITS(state->distbits)];
1004
if ((unsigned)(this.bits) <= bits) break;
1007
if ((this.op & 0xf0) == 0) {
1010
this = state->distcode[last.val +
1011
(BITS(last.bits + last.op) >> last.bits)];
1012
if ((unsigned)(last.bits + this.bits) <= bits) break;
1015
DROPBITS(last.bits);
1017
DROPBITS(this.bits);
1019
strm->msg = "invalid distance code";
1020
state->mode = BAD_DATA;
1023
state->offset = (unsigned)this.val;
1024
state->extra = (unsigned)(this.op) & 15;
1025
state->mode = DISTEXT;
1028
NEEDBITS(state->extra);
1029
state->offset += BITS(state->extra);
1030
DROPBITS(state->extra);
1032
#ifdef INFLATE_STRICT
1033
if (state->offset > state->dmax) {
1034
strm->msg = "invalid distance too far back";
1035
state->mode = BAD_DATA;
1039
if (state->offset > state->whave + out - left) {
1040
strm->msg = "invalid distance too far back";
1041
state->mode = BAD_DATA;
1044
Tracevv((stderr, "inflate: distance %u\n", state->offset));
1045
state->mode = MATCH;
1047
if (left == 0) goto inf_leave;
1049
if (state->offset > copy) { /* copy from window */
1050
copy = state->offset - copy;
1051
if (copy > state->write) {
1052
copy -= state->write;
1053
from = state->window + (state->wsize - copy);
1056
from = state->window + (state->write - copy);
1057
if (copy > state->length) copy = state->length;
1059
else { /* copy from output */
1060
from = put - state->offset;
1061
copy = state->length;
1063
if (copy > left) copy = left;
1065
state->length -= copy;
1069
if (state->length == 0) state->mode = LEN;
1072
if (left == 0) goto inf_leave;
1073
*put++ = (unsigned char)(state->length);
1081
strm->total_out += out;
1082
state->total += out;
1084
strm->adler = state->check =
1085
UPDATE(state->check, put - out, out);
1089
state->flags ? hold :
1091
REVERSE(hold)) != state->check) {
1092
strm->msg = "incorrect data check";
1093
state->mode = BAD_DATA;
1097
Tracev((stderr, "inflate: check matches trailer\n"));
1100
state->mode = LENGTH;
1102
if (state->wrap && state->flags) {
1104
if (hold != (state->total & 0xffffffffUL)) {
1105
strm->msg = "incorrect length check";
1106
state->mode = BAD_DATA;
1110
Tracev((stderr, "inflate: length matches trailer\n"));
1124
return Z_STREAM_ERROR;
1128
Return from inflate(), updating the total counts and the check value.
1129
If there was no progress during the inflate() call, return a buffer
1130
error. Call updatewindow() to create and/or update the window state.
1131
Note: a memory error from inflate() is non-recoverable.
1135
if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1136
if (updatewindow(strm, out)) {
1140
in -= strm->avail_in;
1141
out -= strm->avail_out;
1142
strm->total_in += in;
1143
strm->total_out += out;
1144
state->total += out;
1145
if (state->wrap && out)
1146
strm->adler = state->check =
1147
UPDATE(state->check, strm->next_out - out, out);
1148
strm->data_type = state->bits + (state->last ? 64 : 0) +
1149
(state->mode == TYPE ? 128 : 0);
1150
if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1155
int ZEXPORT inflateEnd(strm)
1158
struct inflate_state FAR *state;
1159
if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1160
return Z_STREAM_ERROR;
1161
state = (struct inflate_state FAR *)strm->state;
1162
if (state->window != Z_NULL) ZFREE(strm, state->window);
1163
ZFREE(strm, strm->state);
1164
strm->state = Z_NULL;
1165
Tracev((stderr, "inflate: end\n"));
1169
int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1171
const Bytef *dictionary;
1174
struct inflate_state FAR *state;
1178
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1179
state = (struct inflate_state FAR *)strm->state;
1180
if (state->wrap != 0 && state->mode != DICT)
1181
return Z_STREAM_ERROR;
1183
/* check for correct dictionary id */
1184
if (state->mode == DICT) {
1185
id = adler32(0L, Z_NULL, 0);
1186
id = adler32(id, dictionary, dictLength);
1187
if (id != state->check)
1188
return Z_DATA_ERROR;
1191
/* copy dictionary to window */
1192
if (updatewindow(strm, strm->avail_out)) {
1196
if (dictLength > state->wsize) {
1197
zmemcpy(state->window, dictionary + dictLength - state->wsize,
1199
state->whave = state->wsize;
1202
zmemcpy(state->window + state->wsize - dictLength, dictionary,
1204
state->whave = dictLength;
1206
state->havedict = 1;
1207
Tracev((stderr, "inflate: dictionary set\n"));
1211
int ZEXPORT inflateGetHeader(strm, head)
1215
struct inflate_state FAR *state;
1218
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1219
state = (struct inflate_state FAR *)strm->state;
1220
if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1222
/* save header structure */
1229
Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1230
or when out of input. When called, *have is the number of pattern bytes
1231
found in order so far, in 0..3. On return *have is updated to the new
1232
state. If on return *have equals four, then the pattern was found and the
1233
return value is how many bytes were read including the last byte of the
1234
pattern. If *have is less than four, then the pattern has not been found
1235
yet and the return value is len. In the latter case, syncsearch() can be
1236
called again with more data and the *have state. *have is initialized to
1237
zero for the first call.
1239
local unsigned syncsearch(have, buf, len)
1241
unsigned const char FAR *buf;
1249
while (next < len && got < 4) {
1250
if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1262
int ZEXPORT inflateSync(strm)
1265
unsigned len; /* number of bytes to look at or looked at */
1266
unsigned long in, out; /* temporary to save total_in and total_out */
1267
unsigned char buf[4]; /* to restore bit buffer to byte string */
1268
struct inflate_state FAR *state;
1270
/* check parameters */
1271
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1272
state = (struct inflate_state FAR *)strm->state;
1273
if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1275
/* if first time, start search in bit buffer */
1276
if (state->mode != SYNC) {
1278
state->hold <<= state->bits & 7;
1279
state->bits -= state->bits & 7;
1281
while (state->bits >= 8) {
1282
buf[len++] = (unsigned char)(state->hold);
1287
syncsearch(&(state->have), buf, len);
1290
/* search available input */
1291
len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1292
strm->avail_in -= len;
1293
strm->next_in += len;
1294
strm->total_in += len;
1296
/* return no joy or set up to restart inflate() on a new block */
1297
if (state->have != 4) return Z_DATA_ERROR;
1298
in = strm->total_in; out = strm->total_out;
1300
strm->total_in = in; strm->total_out = out;
1306
Returns true if inflate is currently at the end of a block generated by
1307
Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1308
implementation to provide an additional safety check. PPP uses
1309
Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1310
block. When decompressing, PPP checks that at the end of input packet,
1311
inflate is waiting for these length bytes.
1313
int ZEXPORT inflateSyncPoint(strm)
1316
struct inflate_state FAR *state;
1318
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1319
state = (struct inflate_state FAR *)strm->state;
1320
return state->mode == STORED && state->bits == 0;
1323
int ZEXPORT inflateCopy(dest, source)
1327
struct inflate_state FAR *state;
1328
struct inflate_state FAR *copy;
1329
unsigned char FAR *window;
1333
if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1334
source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1335
return Z_STREAM_ERROR;
1336
state = (struct inflate_state FAR *)source->state;
1338
/* allocate space */
1339
copy = (struct inflate_state FAR *)
1340
ZALLOC(source, 1, sizeof(struct inflate_state));
1341
if (copy == Z_NULL) return Z_MEM_ERROR;
1343
if (state->window != Z_NULL) {
1344
window = (unsigned char FAR *)
1345
ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1346
if (window == Z_NULL) {
1347
ZFREE(source, copy);
1353
zmemcpy(dest, source, sizeof(z_stream));
1354
zmemcpy(copy, state, sizeof(struct inflate_state));
1355
if (state->lencode >= state->codes &&
1356
state->lencode <= state->codes + ENOUGH - 1) {
1357
copy->lencode = copy->codes + (state->lencode - state->codes);
1358
copy->distcode = copy->codes + (state->distcode - state->codes);
1360
copy->next = copy->codes + (state->next - state->codes);
1361
if (window != Z_NULL) {
1362
wsize = 1U << state->wbits;
1363
zmemcpy(window, state->window, wsize);
1365
copy->window = window;
1366
dest->state = (struct internal_state FAR *)copy;
added
removed
lib/zlib/inflate.c
