source: trunk/sys/libz/inflate.c @ 396

Last change on this file since 396 was 1, checked in by alain, 7 years ago

First import

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