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