source: rtems/cpukit/zlib/inflate.c @ 89bace6

4.104.11
Last change on this file since 89bace6 was 959f7df2, checked in by Ralf Corsepius <ralf.corsepius@…>, on Oct 28, 2005 at 7:22:42 AM

Import of zlib-1.2.2.2.tar.gz

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