Import zlib-1.2.2 using new-style contrib handling.
[dragonfly.git] / contrib / zlib-1.2.2 / inflate.c
1 /* inflate.c -- zlib decompression
2  * Copyright (C) 1995-2003 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5
6 /*
7  * Change history:
8  *
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
14  *
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
21  *
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
28  *
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
40  *
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
55  *   window copying
56  *
57  * 1.2.beta5    1 Jan 2003
58  * - Improved inflateBack() interface to allow the caller to provide initial
59  *   input in strm.
60  * - Fixed stored blocks bug in inflateBack()
61  *
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 *
68  *
69  * 1.2.beta7    27 Jan 2003
70  * - Changed many types to unsigned or unsigned short to avoid warnings
71  * - Added inflateCopy() function
72  *
73  * 1.2.0        9 Mar 2003
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()
79  *
80  * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
81  */
82
83 #include "zutil.h"
84 #include "inftrees.h"
85 #include "inflate.h"
86 #include "inffast.h"
87
88 #ifdef MAKEFIXED
89 #  ifndef BUILDFIXED
90 #    define BUILDFIXED
91 #  endif
92 #endif
93
94 /* function prototypes */
95 local void fixedtables OF((struct inflate_state FAR *state));
96 local int updatewindow OF((z_streamp strm, unsigned out));
97 #ifdef BUILDFIXED
98    void makefixed OF((void));
99 #endif
100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
101                               unsigned len));
102
103 int ZEXPORT inflateReset(strm)
104 z_streamp strm;
105 {
106     struct inflate_state FAR *state;
107
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;
111     strm->msg = Z_NULL;
112     strm->adler = 1;        /* to support ill-conceived Java test suite */
113     state->mode = HEAD;
114     state->last = 0;
115     state->havedict = 0;
116     state->wsize = 0;
117     state->whave = 0;
118     state->hold = 0;
119     state->bits = 0;
120     state->lencode = state->distcode = state->next = state->codes;
121     Tracev((stderr, "inflate: reset\n"));
122     return Z_OK;
123 }
124
125 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
126 z_streamp strm;
127 int windowBits;
128 const char *version;
129 int stream_size;
130 {
131     struct inflate_state FAR *state;
132
133     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
134         stream_size != (int)(sizeof(z_stream)))
135         return Z_VERSION_ERROR;
136     if (strm == Z_NULL) return Z_STREAM_ERROR;
137     strm->msg = Z_NULL;                 /* in case we return an error */
138     if (strm->zalloc == (alloc_func)0) {
139         strm->zalloc = zcalloc;
140         strm->opaque = (voidpf)0;
141     }
142     if (strm->zfree == (free_func)0) strm->zfree = zcfree;
143     state = (struct inflate_state FAR *)
144             ZALLOC(strm, 1, sizeof(struct inflate_state));
145     if (state == Z_NULL) return Z_MEM_ERROR;
146     Tracev((stderr, "inflate: allocated\n"));
147     strm->state = (voidpf)state;
148     if (windowBits < 0) {
149         state->wrap = 0;
150         windowBits = -windowBits;
151     }
152     else {
153         state->wrap = (windowBits >> 4) + 1;
154 #ifdef GUNZIP
155         if (windowBits < 48) windowBits &= 15;
156 #endif
157     }
158     if (windowBits < 8 || windowBits > 15) {
159         ZFREE(strm, state);
160         strm->state = Z_NULL;
161         return Z_STREAM_ERROR;
162     }
163     state->wbits = (unsigned)windowBits;
164     state->window = Z_NULL;
165     return inflateReset(strm);
166 }
167
168 int ZEXPORT inflateInit_(strm, version, stream_size)
169 z_streamp strm;
170 const char *version;
171 int stream_size;
172 {
173     return inflateInit2_(strm, DEF_WBITS, version, stream_size);
174 }
175
176 /*
177    Return state with length and distance decoding tables and index sizes set to
178    fixed code decoding.  Normally this returns fixed tables from inffixed.h.
179    If BUILDFIXED is defined, then instead this routine builds the tables the
180    first time it's called, and returns those tables the first time and
181    thereafter.  This reduces the size of the code by about 2K bytes, in
182    exchange for a little execution time.  However, BUILDFIXED should not be
183    used for threaded applications, since the rewriting of the tables and virgin
184    may not be thread-safe.
185  */
186 local void fixedtables(state)
187 struct inflate_state FAR *state;
188 {
189 #ifdef BUILDFIXED
190     static int virgin = 1;
191     static code *lenfix, *distfix;
192     static code fixed[544];
193
194     /* build fixed huffman tables if first call (may not be thread safe) */
195     if (virgin) {
196         unsigned sym, bits;
197         static code *next;
198
199         /* literal/length table */
200         sym = 0;
201         while (sym < 144) state->lens[sym++] = 8;
202         while (sym < 256) state->lens[sym++] = 9;
203         while (sym < 280) state->lens[sym++] = 7;
204         while (sym < 288) state->lens[sym++] = 8;
205         next = fixed;
206         lenfix = next;
207         bits = 9;
208         inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
209
210         /* distance table */
211         sym = 0;
212         while (sym < 32) state->lens[sym++] = 5;
213         distfix = next;
214         bits = 5;
215         inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
216
217         /* do this just once */
218         virgin = 0;
219     }
220 #else /* !BUILDFIXED */
221 #   include "inffixed.h"
222 #endif /* BUILDFIXED */
223     state->lencode = lenfix;
224     state->lenbits = 9;
225     state->distcode = distfix;
226     state->distbits = 5;
227 }
228
229 #ifdef MAKEFIXED
230 #include <stdio.h>
231
232 /*
233    Write out the inffixed.h that is #include'd above.  Defining MAKEFIXED also
234    defines BUILDFIXED, so the tables are built on the fly.  makefixed() writes
235    those tables to stdout, which would be piped to inffixed.h.  A small program
236    can simply call makefixed to do this:
237
238     void makefixed(void);
239
240     int main(void)
241     {
242         makefixed();
243         return 0;
244     }
245
246    Then that can be linked with zlib built with MAKEFIXED defined and run:
247
248     a.out > inffixed.h
249  */
250 void makefixed()
251 {
252     unsigned low, size;
253     struct inflate_state state;
254
255     fixedtables(&state);
256     puts("    /* inffixed.h -- table for decoding fixed codes");
257     puts("     * Generated automatically by makefixed().");
258     puts("     */");
259     puts("");
260     puts("    /* WARNING: this file should *not* be used by applications.");
261     puts("       It is part of the implementation of this library and is");
262     puts("       subject to change. Applications should only use zlib.h.");
263     puts("     */");
264     puts("");
265     size = 1U << 9;
266     printf("    static const code lenfix[%u] = {", size);
267     low = 0;
268     for (;;) {
269         if ((low % 7) == 0) printf("\n        ");
270         printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
271                state.lencode[low].val);
272         if (++low == size) break;
273         putchar(',');
274     }
275     puts("\n    };");
276     size = 1U << 5;
277     printf("\n    static const code distfix[%u] = {", size);
278     low = 0;
279     for (;;) {
280         if ((low % 6) == 0) printf("\n        ");
281         printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
282                state.distcode[low].val);
283         if (++low == size) break;
284         putchar(',');
285     }
286     puts("\n    };");
287 }
288 #endif /* MAKEFIXED */
289
290 /*
291    Update the window with the last wsize (normally 32K) bytes written before
292    returning.  If window does not exist yet, create it.  This is only called
293    when a window is already in use, or when output has been written during this
294    inflate call, but the end of the deflate stream has not been reached yet.
295    It is also called to create a window for dictionary data when a dictionary
296    is loaded.
297
298    Providing output buffers larger than 32K to inflate() should provide a speed
299    advantage, since only the last 32K of output is copied to the sliding window
300    upon return from inflate(), and since all distances after the first 32K of
301    output will fall in the output data, making match copies simpler and faster.
302    The advantage may be dependent on the size of the processor's data caches.
303  */
304 local int updatewindow(strm, out)
305 z_streamp strm;
306 unsigned out;
307 {
308     struct inflate_state FAR *state;
309     unsigned copy, dist;
310
311     state = (struct inflate_state FAR *)strm->state;
312
313     /* if it hasn't been done already, allocate space for the window */
314     if (state->window == Z_NULL) {
315         state->window = (unsigned char FAR *)
316                         ZALLOC(strm, 1U << state->wbits,
317                                sizeof(unsigned char));
318         if (state->window == Z_NULL) return 1;
319     }
320
321     /* if window not in use yet, initialize */
322     if (state->wsize == 0) {
323         state->wsize = 1U << state->wbits;
324         state->write = 0;
325         state->whave = 0;
326     }
327
328     /* copy state->wsize or less output bytes into the circular window */
329     copy = out - strm->avail_out;
330     if (copy >= state->wsize) {
331         zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
332         state->write = 0;
333         state->whave = state->wsize;
334     }
335     else {
336         dist = state->wsize - state->write;
337         if (dist > copy) dist = copy;
338         zmemcpy(state->window + state->write, strm->next_out - copy, dist);
339         copy -= dist;
340         if (copy) {
341             zmemcpy(state->window, strm->next_out - copy, copy);
342             state->write = copy;
343             state->whave = state->wsize;
344         }
345         else {
346             state->write += dist;
347             if (state->write == state->wsize) state->write = 0;
348             if (state->whave < state->wsize) state->whave += dist;
349         }
350     }
351     return 0;
352 }
353
354 /* Macros for inflate(): */
355
356 /* check function to use adler32() for zlib or crc32() for gzip */
357 #ifdef GUNZIP
358 #  define UPDATE(check, buf, len) \
359     (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
360 #else
361 #  define UPDATE(check, buf, len) adler32(check, buf, len)
362 #endif
363
364 /* check macros for header crc */
365 #ifdef GUNZIP
366 #  define CRC2(check, word) \
367     do { \
368         hbuf[0] = (unsigned char)(word); \
369         hbuf[1] = (unsigned char)((word) >> 8); \
370         check = crc32(check, hbuf, 2); \
371     } while (0)
372
373 #  define CRC4(check, word) \
374     do { \
375         hbuf[0] = (unsigned char)(word); \
376         hbuf[1] = (unsigned char)((word) >> 8); \
377         hbuf[2] = (unsigned char)((word) >> 16); \
378         hbuf[3] = (unsigned char)((word) >> 24); \
379         check = crc32(check, hbuf, 4); \
380     } while (0)
381 #endif
382
383 /* Load registers with state in inflate() for speed */
384 #define LOAD() \
385     do { \
386         put = strm->next_out; \
387         left = strm->avail_out; \
388         next = strm->next_in; \
389         have = strm->avail_in; \
390         hold = state->hold; \
391         bits = state->bits; \
392     } while (0)
393
394 /* Restore state from registers in inflate() */
395 #define RESTORE() \
396     do { \
397         strm->next_out = put; \
398         strm->avail_out = left; \
399         strm->next_in = next; \
400         strm->avail_in = have; \
401         state->hold = hold; \
402         state->bits = bits; \
403     } while (0)
404
405 /* Clear the input bit accumulator */
406 #define INITBITS() \
407     do { \
408         hold = 0; \
409         bits = 0; \
410     } while (0)
411
412 /* Get a byte of input into the bit accumulator, or return from inflate()
413    if there is no input available. */
414 #define PULLBYTE() \
415     do { \
416         if (have == 0) goto inf_leave; \
417         have--; \
418         hold += (unsigned long)(*next++) << bits; \
419         bits += 8; \
420     } while (0)
421
422 /* Assure that there are at least n bits in the bit accumulator.  If there is
423    not enough available input to do that, then return from inflate(). */
424 #define NEEDBITS(n) \
425     do { \
426         while (bits < (unsigned)(n)) \
427             PULLBYTE(); \
428     } while (0)
429
430 /* Return the low n bits of the bit accumulator (n < 16) */
431 #define BITS(n) \
432     ((unsigned)hold & ((1U << (n)) - 1))
433
434 /* Remove n bits from the bit accumulator */
435 #define DROPBITS(n) \
436     do { \
437         hold >>= (n); \
438         bits -= (unsigned)(n); \
439     } while (0)
440
441 /* Remove zero to seven bits as needed to go to a byte boundary */
442 #define BYTEBITS() \
443     do { \
444         hold >>= bits & 7; \
445         bits -= bits & 7; \
446     } while (0)
447
448 /* Reverse the bytes in a 32-bit value */
449 #define REVERSE(q) \
450     ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
451      (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
452
453 /*
454    inflate() uses a state machine to process as much input data and generate as
455    much output data as possible before returning.  The state machine is
456    structured roughly as follows:
457
458     for (;;) switch (state) {
459     ...
460     case STATEn:
461         if (not enough input data or output space to make progress)
462             return;
463         ... make progress ...
464         state = STATEm;
465         break;
466     ...
467     }
468
469    so when inflate() is called again, the same case is attempted again, and
470    if the appropriate resources are provided, the machine proceeds to the
471    next state.  The NEEDBITS() macro is usually the way the state evaluates
472    whether it can proceed or should return.  NEEDBITS() does the return if
473    the requested bits are not available.  The typical use of the BITS macros
474    is:
475
476         NEEDBITS(n);
477         ... do something with BITS(n) ...
478         DROPBITS(n);
479
480    where NEEDBITS(n) either returns from inflate() if there isn't enough
481    input left to load n bits into the accumulator, or it continues.  BITS(n)
482    gives the low n bits in the accumulator.  When done, DROPBITS(n) drops
483    the low n bits off the accumulator.  INITBITS() clears the accumulator
484    and sets the number of available bits to zero.  BYTEBITS() discards just
485    enough bits to put the accumulator on a byte boundary.  After BYTEBITS()
486    and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
487
488    NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
489    if there is no input available.  The decoding of variable length codes uses
490    PULLBYTE() directly in order to pull just enough bytes to decode the next
491    code, and no more.
492
493    Some states loop until they get enough input, making sure that enough
494    state information is maintained to continue the loop where it left off
495    if NEEDBITS() returns in the loop.  For example, want, need, and keep
496    would all have to actually be part of the saved state in case NEEDBITS()
497    returns:
498
499     case STATEw:
500         while (want < need) {
501             NEEDBITS(n);
502             keep[want++] = BITS(n);
503             DROPBITS(n);
504         }
505         state = STATEx;
506     case STATEx:
507
508    As shown above, if the next state is also the next case, then the break
509    is omitted.
510
511    A state may also return if there is not enough output space available to
512    complete that state.  Those states are copying stored data, writing a
513    literal byte, and copying a matching string.
514
515    When returning, a "goto inf_leave" is used to update the total counters,
516    update the check value, and determine whether any progress has been made
517    during that inflate() call in order to return the proper return code.
518    Progress is defined as a change in either strm->avail_in or strm->avail_out.
519    When there is a window, goto inf_leave will update the window with the last
520    output written.  If a goto inf_leave occurs in the middle of decompression
521    and there is no window currently, goto inf_leave will create one and copy
522    output to the window for the next call of inflate().
523
524    In this implementation, the flush parameter of inflate() only affects the
525    return code (per zlib.h).  inflate() always writes as much as possible to
526    strm->next_out, given the space available and the provided input--the effect
527    documented in zlib.h of Z_SYNC_FLUSH.  Furthermore, inflate() always defers
528    the allocation of and copying into a sliding window until necessary, which
529    provides the effect documented in zlib.h for Z_FINISH when the entire input
530    stream available.  So the only thing the flush parameter actually does is:
531    when flush is set to Z_FINISH, inflate() cannot return Z_OK.  Instead it
532    will return Z_BUF_ERROR if it has not reached the end of the stream.
533  */
534
535 int ZEXPORT inflate(strm, flush)
536 z_streamp strm;
537 int flush;
538 {
539     struct inflate_state FAR *state;
540     unsigned char FAR *next;    /* next input */
541     unsigned char FAR *put;     /* next output */
542     unsigned have, left;        /* available input and output */
543     unsigned long hold;         /* bit buffer */
544     unsigned bits;              /* bits in bit buffer */
545     unsigned in, out;           /* save starting available input and output */
546     unsigned copy;              /* number of stored or match bytes to copy */
547     unsigned char FAR *from;    /* where to copy match bytes from */
548     code this;                  /* current decoding table entry */
549     code last;                  /* parent table entry */
550     unsigned len;               /* length to copy for repeats, bits to drop */
551     int ret;                    /* return code */
552 #ifdef GUNZIP
553     unsigned char hbuf[4];      /* buffer for gzip header crc calculation */
554 #endif
555     static const unsigned short order[19] = /* permutation of code lengths */
556         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
557
558     if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
559         (strm->next_in == Z_NULL && strm->avail_in != 0))
560         return Z_STREAM_ERROR;
561
562     state = (struct inflate_state FAR *)strm->state;
563     if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */
564     LOAD();
565     in = have;
566     out = left;
567     ret = Z_OK;
568     for (;;)
569         switch (state->mode) {
570         case HEAD:
571             if (state->wrap == 0) {
572                 state->mode = TYPEDO;
573                 break;
574             }
575             NEEDBITS(16);
576 #ifdef GUNZIP
577             if ((state->wrap & 2) && hold == 0x8b1f) {  /* gzip header */
578                 state->check = crc32(0L, Z_NULL, 0);
579                 CRC2(state->check, hold);
580                 INITBITS();
581                 state->mode = FLAGS;
582                 break;
583             }
584             state->flags = 0;           /* expect zlib header */
585             if (!(state->wrap & 1) ||   /* check if zlib header allowed */
586 #else
587             if (
588 #endif
589                 ((BITS(8) << 8) + (hold >> 8)) % 31) {
590                 strm->msg = (char *)"incorrect header check";
591                 state->mode = BAD;
592                 break;
593             }
594             if (BITS(4) != Z_DEFLATED) {
595                 strm->msg = (char *)"unknown compression method";
596                 state->mode = BAD;
597                 break;
598             }
599             DROPBITS(4);
600             if (BITS(4) + 8 > state->wbits) {
601                 strm->msg = (char *)"invalid window size";
602                 state->mode = BAD;
603                 break;
604             }
605             Tracev((stderr, "inflate:   zlib header ok\n"));
606             strm->adler = state->check = adler32(0L, Z_NULL, 0);
607             state->mode = hold & 0x200 ? DICTID : TYPE;
608             INITBITS();
609             break;
610 #ifdef GUNZIP
611         case FLAGS:
612             NEEDBITS(16);
613             state->flags = (int)(hold);
614             if ((state->flags & 0xff) != Z_DEFLATED) {
615                 strm->msg = (char *)"unknown compression method";
616                 state->mode = BAD;
617                 break;
618             }
619             if (state->flags & 0xe000) {
620                 strm->msg = (char *)"unknown header flags set";
621                 state->mode = BAD;
622                 break;
623             }
624             if (state->flags & 0x0200) CRC2(state->check, hold);
625             INITBITS();
626             state->mode = TIME;
627         case TIME:
628             NEEDBITS(32);
629             if (state->flags & 0x0200) CRC4(state->check, hold);
630             INITBITS();
631             state->mode = OS;
632         case OS:
633             NEEDBITS(16);
634             if (state->flags & 0x0200) CRC2(state->check, hold);
635             INITBITS();
636             state->mode = EXLEN;
637         case EXLEN:
638             if (state->flags & 0x0400) {
639                 NEEDBITS(16);
640                 state->length = (unsigned)(hold);
641                 if (state->flags & 0x0200) CRC2(state->check, hold);
642                 INITBITS();
643             }
644             state->mode = EXTRA;
645         case EXTRA:
646             if (state->flags & 0x0400) {
647                 copy = state->length;
648                 if (copy > have) copy = have;
649                 if (copy) {
650                     if (state->flags & 0x0200)
651                         state->check = crc32(state->check, next, copy);
652                     have -= copy;
653                     next += copy;
654                     state->length -= copy;
655                 }
656                 if (state->length) goto inf_leave;
657             }
658             state->mode = NAME;
659         case NAME:
660             if (state->flags & 0x0800) {
661                 if (have == 0) goto inf_leave;
662                 copy = 0;
663                 do {
664                     len = (unsigned)(next[copy++]);
665                 } while (len && copy < have);
666                 if (state->flags & 0x02000)
667                     state->check = crc32(state->check, next, copy);
668                 have -= copy;
669                 next += copy;
670                 if (len) goto inf_leave;
671             }
672             state->mode = COMMENT;
673         case COMMENT:
674             if (state->flags & 0x1000) {
675                 if (have == 0) goto inf_leave;
676                 copy = 0;
677                 do {
678                     len = (unsigned)(next[copy++]);
679                 } while (len && copy < have);
680                 if (state->flags & 0x02000)
681                     state->check = crc32(state->check, next, copy);
682                 have -= copy;
683                 next += copy;
684                 if (len) goto inf_leave;
685             }
686             state->mode = HCRC;
687         case HCRC:
688             if (state->flags & 0x0200) {
689                 NEEDBITS(16);
690                 if (hold != (state->check & 0xffff)) {
691                     strm->msg = (char *)"header crc mismatch";
692                     state->mode = BAD;
693                     break;
694                 }
695                 INITBITS();
696             }
697             strm->adler = state->check = crc32(0L, Z_NULL, 0);
698             state->mode = TYPE;
699             break;
700 #endif
701         case DICTID:
702             NEEDBITS(32);
703             strm->adler = state->check = REVERSE(hold);
704             INITBITS();
705             state->mode = DICT;
706         case DICT:
707             if (state->havedict == 0) {
708                 RESTORE();
709                 return Z_NEED_DICT;
710             }
711             strm->adler = state->check = adler32(0L, Z_NULL, 0);
712             state->mode = TYPE;
713         case TYPE:
714             if (flush == Z_BLOCK) goto inf_leave;
715         case TYPEDO:
716             if (state->last) {
717                 BYTEBITS();
718                 state->mode = CHECK;
719                 break;
720             }
721             NEEDBITS(3);
722             state->last = BITS(1);
723             DROPBITS(1);
724             switch (BITS(2)) {
725             case 0:                             /* stored block */
726                 Tracev((stderr, "inflate:     stored block%s\n",
727                         state->last ? " (last)" : ""));
728                 state->mode = STORED;
729                 break;
730             case 1:                             /* fixed block */
731                 fixedtables(state);
732                 Tracev((stderr, "inflate:     fixed codes block%s\n",
733                         state->last ? " (last)" : ""));
734                 state->mode = LEN;              /* decode codes */
735                 break;
736             case 2:                             /* dynamic block */
737                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
738                         state->last ? " (last)" : ""));
739                 state->mode = TABLE;
740                 break;
741             case 3:
742                 strm->msg = (char *)"invalid block type";
743                 state->mode = BAD;
744             }
745             DROPBITS(2);
746             break;
747         case STORED:
748             BYTEBITS();                         /* go to byte boundary */
749             NEEDBITS(32);
750             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
751                 strm->msg = (char *)"invalid stored block lengths";
752                 state->mode = BAD;
753                 break;
754             }
755             state->length = (unsigned)hold & 0xffff;
756             Tracev((stderr, "inflate:       stored length %u\n",
757                     state->length));
758             INITBITS();
759             state->mode = COPY;
760         case COPY:
761             copy = state->length;
762             if (copy) {
763                 if (copy > have) copy = have;
764                 if (copy > left) copy = left;
765                 if (copy == 0) goto inf_leave;
766                 zmemcpy(put, next, copy);
767                 have -= copy;
768                 next += copy;
769                 left -= copy;
770                 put += copy;
771                 state->length -= copy;
772                 break;
773             }
774             Tracev((stderr, "inflate:       stored end\n"));
775             state->mode = TYPE;
776             break;
777         case TABLE:
778             NEEDBITS(14);
779             state->nlen = BITS(5) + 257;
780             DROPBITS(5);
781             state->ndist = BITS(5) + 1;
782             DROPBITS(5);
783             state->ncode = BITS(4) + 4;
784             DROPBITS(4);
785 #ifndef PKZIP_BUG_WORKAROUND
786             if (state->nlen > 286 || state->ndist > 30) {
787                 strm->msg = (char *)"too many length or distance symbols";
788                 state->mode = BAD;
789                 break;
790             }
791 #endif
792             Tracev((stderr, "inflate:       table sizes ok\n"));
793             state->have = 0;
794             state->mode = LENLENS;
795         case LENLENS:
796             while (state->have < state->ncode) {
797                 NEEDBITS(3);
798                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
799                 DROPBITS(3);
800             }
801             while (state->have < 19)
802                 state->lens[order[state->have++]] = 0;
803             state->next = state->codes;
804             state->lencode = (code const FAR *)(state->next);
805             state->lenbits = 7;
806             ret = inflate_table(CODES, state->lens, 19, &(state->next),
807                                 &(state->lenbits), state->work);
808             if (ret) {
809                 strm->msg = (char *)"invalid code lengths set";
810                 state->mode = BAD;
811                 break;
812             }
813             Tracev((stderr, "inflate:       code lengths ok\n"));
814             state->have = 0;
815             state->mode = CODELENS;
816         case CODELENS:
817             while (state->have < state->nlen + state->ndist) {
818                 for (;;) {
819                     this = state->lencode[BITS(state->lenbits)];
820                     if ((unsigned)(this.bits) <= bits) break;
821                     PULLBYTE();
822                 }
823                 if (this.val < 16) {
824                     NEEDBITS(this.bits);
825                     DROPBITS(this.bits);
826                     state->lens[state->have++] = this.val;
827                 }
828                 else {
829                     if (this.val == 16) {
830                         NEEDBITS(this.bits + 2);
831                         DROPBITS(this.bits);
832                         if (state->have == 0) {
833                             strm->msg = (char *)"invalid bit length repeat";
834                             state->mode = BAD;
835                             break;
836                         }
837                         len = state->lens[state->have - 1];
838                         copy = 3 + BITS(2);
839                         DROPBITS(2);
840                     }
841                     else if (this.val == 17) {
842                         NEEDBITS(this.bits + 3);
843                         DROPBITS(this.bits);
844                         len = 0;
845                         copy = 3 + BITS(3);
846                         DROPBITS(3);
847                     }
848                     else {
849                         NEEDBITS(this.bits + 7);
850                         DROPBITS(this.bits);
851                         len = 0;
852                         copy = 11 + BITS(7);
853                         DROPBITS(7);
854                     }
855                     if (state->have + copy > state->nlen + state->ndist) {
856                         strm->msg = (char *)"invalid bit length repeat";
857                         state->mode = BAD;
858                         break;
859                     }
860                     while (copy--)
861                         state->lens[state->have++] = (unsigned short)len;
862                 }
863             }
864
865             /* handle error breaks in while */
866             if (state->mode == BAD) break;
867
868             /* build code tables */
869             state->next = state->codes;
870             state->lencode = (code const FAR *)(state->next);
871             state->lenbits = 9;
872             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
873                                 &(state->lenbits), state->work);
874             if (ret) {
875                 strm->msg = (char *)"invalid literal/lengths set";
876                 state->mode = BAD;
877                 break;
878             }
879             state->distcode = (code const FAR *)(state->next);
880             state->distbits = 6;
881             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
882                             &(state->next), &(state->distbits), state->work);
883             if (ret) {
884                 strm->msg = (char *)"invalid distances set";
885                 state->mode = BAD;
886                 break;
887             }
888             Tracev((stderr, "inflate:       codes ok\n"));
889             state->mode = LEN;
890         case LEN:
891             if (have >= 6 && left >= 258) {
892                 RESTORE();
893                 inflate_fast(strm, out);
894                 LOAD();
895                 break;
896             }
897             for (;;) {
898                 this = state->lencode[BITS(state->lenbits)];
899                 if ((unsigned)(this.bits) <= bits) break;
900                 PULLBYTE();
901             }
902             if (this.op && (this.op & 0xf0) == 0) {
903                 last = this;
904                 for (;;) {
905                     this = state->lencode[last.val +
906                             (BITS(last.bits + last.op) >> last.bits)];
907                     if ((unsigned)(last.bits + this.bits) <= bits) break;
908                     PULLBYTE();
909                 }
910                 DROPBITS(last.bits);
911             }
912             DROPBITS(this.bits);
913             state->length = (unsigned)this.val;
914             if ((int)(this.op) == 0) {
915                 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
916                         "inflate:         literal '%c'\n" :
917                         "inflate:         literal 0x%02x\n", this.val));
918                 state->mode = LIT;
919                 break;
920             }
921             if (this.op & 32) {
922                 Tracevv((stderr, "inflate:         end of block\n"));
923                 state->mode = TYPE;
924                 break;
925             }
926             if (this.op & 64) {
927                 strm->msg = (char *)"invalid literal/length code";
928                 state->mode = BAD;
929                 break;
930             }
931             state->extra = (unsigned)(this.op) & 15;
932             state->mode = LENEXT;
933         case LENEXT:
934             if (state->extra) {
935                 NEEDBITS(state->extra);
936                 state->length += BITS(state->extra);
937                 DROPBITS(state->extra);
938             }
939             Tracevv((stderr, "inflate:         length %u\n", state->length));
940             state->mode = DIST;
941         case DIST:
942             for (;;) {
943                 this = state->distcode[BITS(state->distbits)];
944                 if ((unsigned)(this.bits) <= bits) break;
945                 PULLBYTE();
946             }
947             if ((this.op & 0xf0) == 0) {
948                 last = this;
949                 for (;;) {
950                     this = state->distcode[last.val +
951                             (BITS(last.bits + last.op) >> last.bits)];
952                     if ((unsigned)(last.bits + this.bits) <= bits) break;
953                     PULLBYTE();
954                 }
955                 DROPBITS(last.bits);
956             }
957             DROPBITS(this.bits);
958             if (this.op & 64) {
959                 strm->msg = (char *)"invalid distance code";
960                 state->mode = BAD;
961                 break;
962             }
963             state->offset = (unsigned)this.val;
964             state->extra = (unsigned)(this.op) & 15;
965             state->mode = DISTEXT;
966         case DISTEXT:
967             if (state->extra) {
968                 NEEDBITS(state->extra);
969                 state->offset += BITS(state->extra);
970                 DROPBITS(state->extra);
971             }
972             if (state->offset > state->whave + out - left) {
973                 strm->msg = (char *)"invalid distance too far back";
974                 state->mode = BAD;
975                 break;
976             }
977             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
978             state->mode = MATCH;
979         case MATCH:
980             if (left == 0) goto inf_leave;
981             copy = out - left;
982             if (state->offset > copy) {         /* copy from window */
983                 copy = state->offset - copy;
984                 if (copy > state->write) {
985                     copy -= state->write;
986                     from = state->window + (state->wsize - copy);
987                 }
988                 else
989                     from = state->window + (state->write - copy);
990                 if (copy > state->length) copy = state->length;
991             }
992             else {                              /* copy from output */
993                 from = put - state->offset;
994                 copy = state->length;
995             }
996             if (copy > left) copy = left;
997             left -= copy;
998             state->length -= copy;
999             do {
1000                 *put++ = *from++;
1001             } while (--copy);
1002             if (state->length == 0) state->mode = LEN;
1003             break;
1004         case LIT:
1005             if (left == 0) goto inf_leave;
1006             *put++ = (unsigned char)(state->length);
1007             left--;
1008             state->mode = LEN;
1009             break;
1010         case CHECK:
1011             if (state->wrap) {
1012                 NEEDBITS(32);
1013                 out -= left;
1014                 strm->total_out += out;
1015                 state->total += out;
1016                 if (out)
1017                     strm->adler = state->check =
1018                         UPDATE(state->check, put - out, out);
1019                 out = left;
1020                 if ((
1021 #ifdef GUNZIP
1022                      state->flags ? hold :
1023 #endif
1024                      REVERSE(hold)) != state->check) {
1025                     strm->msg = (char *)"incorrect data check";
1026                     state->mode = BAD;
1027                     break;
1028                 }
1029                 INITBITS();
1030                 Tracev((stderr, "inflate:   check matches trailer\n"));
1031             }
1032 #ifdef GUNZIP
1033             state->mode = LENGTH;
1034         case LENGTH:
1035             if (state->wrap && state->flags) {
1036                 NEEDBITS(32);
1037                 if (hold != (state->total & 0xffffffffUL)) {
1038                     strm->msg = (char *)"incorrect length check";
1039                     state->mode = BAD;
1040                     break;
1041                 }
1042                 INITBITS();
1043                 Tracev((stderr, "inflate:   length matches trailer\n"));
1044             }
1045 #endif
1046             state->mode = DONE;
1047         case DONE:
1048             ret = Z_STREAM_END;
1049             goto inf_leave;
1050         case BAD:
1051             ret = Z_DATA_ERROR;
1052             goto inf_leave;
1053         case MEM:
1054             return Z_MEM_ERROR;
1055         case SYNC:
1056         default:
1057             return Z_STREAM_ERROR;
1058         }
1059
1060     /*
1061        Return from inflate(), updating the total counts and the check value.
1062        If there was no progress during the inflate() call, return a buffer
1063        error.  Call updatewindow() to create and/or update the window state.
1064        Note: a memory error from inflate() is non-recoverable.
1065      */
1066   inf_leave:
1067     RESTORE();
1068     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1069         if (updatewindow(strm, out)) {
1070             state->mode = MEM;
1071             return Z_MEM_ERROR;
1072         }
1073     in -= strm->avail_in;
1074     out -= strm->avail_out;
1075     strm->total_in += in;
1076     strm->total_out += out;
1077     state->total += out;
1078     if (state->wrap && out)
1079         strm->adler = state->check =
1080             UPDATE(state->check, strm->next_out - out, out);
1081     strm->data_type = state->bits + (state->last ? 64 : 0) +
1082                       (state->mode == TYPE ? 128 : 0);
1083     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1084         ret = Z_BUF_ERROR;
1085     return ret;
1086 }
1087
1088 int ZEXPORT inflateEnd(strm)
1089 z_streamp strm;
1090 {
1091     struct inflate_state FAR *state;
1092     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1093         return Z_STREAM_ERROR;
1094     state = (struct inflate_state FAR *)strm->state;
1095     if (state->window != Z_NULL) ZFREE(strm, state->window);
1096     ZFREE(strm, strm->state);
1097     strm->state = Z_NULL;
1098     Tracev((stderr, "inflate: end\n"));
1099     return Z_OK;
1100 }
1101
1102 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1103 z_streamp strm;
1104 const Bytef *dictionary;
1105 uInt dictLength;
1106 {
1107     struct inflate_state FAR *state;
1108     unsigned long id;
1109
1110     /* check state */
1111     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1112     state = (struct inflate_state FAR *)strm->state;
1113     if (state->mode != DICT) return Z_STREAM_ERROR;
1114
1115     /* check for correct dictionary id */
1116     id = adler32(0L, Z_NULL, 0);
1117     id = adler32(id, dictionary, dictLength);
1118     if (id != state->check) return Z_DATA_ERROR;
1119
1120     /* copy dictionary to window */
1121     if (updatewindow(strm, strm->avail_out)) {
1122         state->mode = MEM;
1123         return Z_MEM_ERROR;
1124     }
1125     if (dictLength > state->wsize) {
1126         zmemcpy(state->window, dictionary + dictLength - state->wsize,
1127                 state->wsize);
1128         state->whave = state->wsize;
1129     }
1130     else {
1131         zmemcpy(state->window + state->wsize - dictLength, dictionary,
1132                 dictLength);
1133         state->whave = dictLength;
1134     }
1135     state->havedict = 1;
1136     Tracev((stderr, "inflate:   dictionary set\n"));
1137     return Z_OK;
1138 }
1139
1140 /*
1141    Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff.  Return when found
1142    or when out of input.  When called, *have is the number of pattern bytes
1143    found in order so far, in 0..3.  On return *have is updated to the new
1144    state.  If on return *have equals four, then the pattern was found and the
1145    return value is how many bytes were read including the last byte of the
1146    pattern.  If *have is less than four, then the pattern has not been found
1147    yet and the return value is len.  In the latter case, syncsearch() can be
1148    called again with more data and the *have state.  *have is initialized to
1149    zero for the first call.
1150  */
1151 local unsigned syncsearch(have, buf, len)
1152 unsigned FAR *have;
1153 unsigned char FAR *buf;
1154 unsigned len;
1155 {
1156     unsigned got;
1157     unsigned next;
1158
1159     got = *have;
1160     next = 0;
1161     while (next < len && got < 4) {
1162         if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1163             got++;
1164         else if (buf[next])
1165             got = 0;
1166         else
1167             got = 4 - got;
1168         next++;
1169     }
1170     *have = got;
1171     return next;
1172 }
1173
1174 int ZEXPORT inflateSync(strm)
1175 z_streamp strm;
1176 {
1177     unsigned len;               /* number of bytes to look at or looked at */
1178     unsigned long in, out;      /* temporary to save total_in and total_out */
1179     unsigned char buf[4];       /* to restore bit buffer to byte string */
1180     struct inflate_state FAR *state;
1181
1182     /* check parameters */
1183     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1184     state = (struct inflate_state FAR *)strm->state;
1185     if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1186
1187     /* if first time, start search in bit buffer */
1188     if (state->mode != SYNC) {
1189         state->mode = SYNC;
1190         state->hold <<= state->bits & 7;
1191         state->bits -= state->bits & 7;
1192         len = 0;
1193         while (state->bits >= 8) {
1194             buf[len++] = (unsigned char)(state->hold);
1195             state->hold >>= 8;
1196             state->bits -= 8;
1197         }
1198         state->have = 0;
1199         syncsearch(&(state->have), buf, len);
1200     }
1201
1202     /* search available input */
1203     len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1204     strm->avail_in -= len;
1205     strm->next_in += len;
1206     strm->total_in += len;
1207
1208     /* return no joy or set up to restart inflate() on a new block */
1209     if (state->have != 4) return Z_DATA_ERROR;
1210     in = strm->total_in;  out = strm->total_out;
1211     inflateReset(strm);
1212     strm->total_in = in;  strm->total_out = out;
1213     state->mode = TYPE;
1214     return Z_OK;
1215 }
1216
1217 /*
1218    Returns true if inflate is currently at the end of a block generated by
1219    Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1220    implementation to provide an additional safety check. PPP uses
1221    Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1222    block. When decompressing, PPP checks that at the end of input packet,
1223    inflate is waiting for these length bytes.
1224  */
1225 int ZEXPORT inflateSyncPoint(strm)
1226 z_streamp strm;
1227 {
1228     struct inflate_state FAR *state;
1229
1230     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1231     state = (struct inflate_state FAR *)strm->state;
1232     return state->mode == STORED && state->bits == 0;
1233 }
1234
1235 int ZEXPORT inflateCopy(dest, source)
1236 z_streamp dest;
1237 z_streamp source;
1238 {
1239     struct inflate_state FAR *state;
1240     struct inflate_state FAR *copy;
1241     unsigned char FAR *window;
1242
1243     /* check input */
1244     if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1245         source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1246         return Z_STREAM_ERROR;
1247     state = (struct inflate_state FAR *)source->state;
1248
1249     /* allocate space */
1250     copy = (struct inflate_state FAR *)
1251            ZALLOC(source, 1, sizeof(struct inflate_state));
1252     if (copy == Z_NULL) return Z_MEM_ERROR;
1253     window = Z_NULL;
1254     if (state->window != Z_NULL) {
1255         window = (unsigned char FAR *)
1256                  ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1257         if (window == Z_NULL) {
1258             ZFREE(source, copy);
1259             return Z_MEM_ERROR;
1260         }
1261     }
1262
1263     /* copy state */
1264     *dest = *source;
1265     *copy = *state;
1266     copy->lencode = copy->codes + (state->lencode - state->codes);
1267     copy->distcode = copy->codes + (state->distcode - state->codes);
1268     copy->next = copy->codes + (state->next - state->codes);
1269     if (window != Z_NULL)
1270         zmemcpy(window, state->window, 1U << state->wbits);
1271     copy->window = window;
1272     dest->state = (voidpf)copy;
1273     return Z_OK;
1274 }