source: trunk/sys/libz/infback.c @ 346

Last change on this file since 346 was 1, checked in by alain, 8 years ago

First import

File size: 21.6 KB
Line 
1/* infback.c -- inflate using a call-back interface
2 * Copyright (C) 1995-2005 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7   This code is largely copied from inflate.c.  Normally either infback.o or
8   inflate.o would be linked into an application--not both.  The interface
9   with inffast.c is retained so that optimized assembler-coded versions of
10   inflate_fast() can be used with either inflate.c or infback.c.
11 */
12
13#include "zutil.h"
14#include "inftrees.h"
15#include "inflate.h"
16#include "inffast.h"
17
18/* function prototypes */
19local void fixedtables OF((struct inflate_state FAR *state));
20
21/*
22   strm provides memory allocation functions in zalloc and zfree, or
23   Z_NULL to use the library memory allocation functions.
24
25   windowBits is in the range 8..15, and window is a user-supplied
26   window and output buffer that is 2**windowBits bytes.
27 */
28int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
29z_streamp strm;
30int windowBits;
31unsigned char FAR *window;
32const char *version;
33int stream_size;
34{
35    struct inflate_state FAR *state;
36
37    if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
38        stream_size != (int)(sizeof(z_stream)))
39        return Z_VERSION_ERROR;
40    if (strm == Z_NULL || window == Z_NULL ||
41        windowBits < 8 || windowBits > 15)
42        return Z_STREAM_ERROR;
43    strm->msg = Z_NULL;                 /* in case we return an error */
44    if (strm->zalloc == (alloc_func)0) {
45        strm->zalloc = zcalloc;
46        strm->opaque = (voidpf)0;
47    }
48    if (strm->zfree == (free_func)0) strm->zfree = zcfree;
49    state = (struct inflate_state FAR *)ZALLOC(strm, 1,
50                                               sizeof(struct inflate_state));
51    if (state == Z_NULL) return Z_MEM_ERROR;
52    Tracev((stderr, "inflate: allocated\n"));
53    strm->state = (struct internal_state FAR *)state;
54    state->dmax = 32768U;
55    state->wbits = windowBits;
56    state->wsize = 1U << windowBits;
57    state->window = window;
58    state->write = 0;
59    state->whave = 0;
60    return Z_OK;
61}
62
63/*
64   Return state with length and distance decoding tables and index sizes set to
65   fixed code decoding.  Normally this returns fixed tables from inffixed.h.
66   If BUILDFIXED is defined, then instead this routine builds the tables the
67   first time it's called, and returns those tables the first time and
68   thereafter.  This reduces the size of the code by about 2K bytes, in
69   exchange for a little execution time.  However, BUILDFIXED should not be
70   used for threaded applications, since the rewriting of the tables and virgin
71   may not be thread-safe.
72 */
73local void fixedtables(state)
74struct inflate_state FAR *state;
75{
76#ifdef BUILDFIXED
77    static int virgin = 1;
78    static code *lenfix, *distfix;
79    static code fixed[544];
80
81    /* build fixed huffman tables if first call (may not be thread safe) */
82    if (virgin) {
83        unsigned sym, bits;
84        static code *next;
85
86        /* literal/length table */
87        sym = 0;
88        while (sym < 144) state->lens[sym++] = 8;
89        while (sym < 256) state->lens[sym++] = 9;
90        while (sym < 280) state->lens[sym++] = 7;
91        while (sym < 288) state->lens[sym++] = 8;
92        next = fixed;
93        lenfix = next;
94        bits = 9;
95        inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
96
97        /* distance table */
98        sym = 0;
99        while (sym < 32) state->lens[sym++] = 5;
100        distfix = next;
101        bits = 5;
102        inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
103
104        /* do this just once */
105        virgin = 0;
106    }
107#else /* !BUILDFIXED */
108#   include "inffixed.h"
109#endif /* BUILDFIXED */
110    state->lencode = lenfix;
111    state->lenbits = 9;
112    state->distcode = distfix;
113    state->distbits = 5;
114}
115
116/* Macros for inflateBack(): */
117
118/* Load returned state from inflate_fast() */
119#define LOAD() \
120    do { \
121        put = strm->next_out; \
122        left = strm->avail_out; \
123        next = strm->next_in; \
124        have = strm->avail_in; \
125        hold = state->hold; \
126        bits = state->bits; \
127    } while (0)
128
129/* Set state from registers for inflate_fast() */
130#define RESTORE() \
131    do { \
132        strm->next_out = put; \
133        strm->avail_out = left; \
134        strm->next_in = next; \
135        strm->avail_in = have; \
136        state->hold = hold; \
137        state->bits = bits; \
138    } while (0)
139
140/* Clear the input bit accumulator */
141#define INITBITS() \
142    do { \
143        hold = 0; \
144        bits = 0; \
145    } while (0)
146
147/* Assure that some input is available.  If input is requested, but denied,
148   then return a Z_BUF_ERROR from inflateBack(). */
149#define PULL() \
150    do { \
151        if (have == 0) { \
152            have = in(in_desc, &next); \
153            if (have == 0) { \
154                next = Z_NULL; \
155                ret = Z_BUF_ERROR; \
156                goto inf_leave; \
157            } \
158        } \
159    } while (0)
160
161/* Get a byte of input into the bit accumulator, or return from inflateBack()
162   with an error if there is no input available. */
163#define PULLBYTE() \
164    do { \
165        PULL(); \
166        have--; \
167        hold += (unsigned long)(*next++) << bits; \
168        bits += 8; \
169    } while (0)
170
171/* Assure that there are at least n bits in the bit accumulator.  If there is
172   not enough available input to do that, then return from inflateBack() with
173   an error. */
174#define NEEDBITS(n) \
175    do { \
176        while (bits < (unsigned)(n)) \
177            PULLBYTE(); \
178    } while (0)
179
180/* Return the low n bits of the bit accumulator (n < 16) */
181#define BITS(n) \
182    ((unsigned)hold & ((1U << (n)) - 1))
183
184/* Remove n bits from the bit accumulator */
185#define DROPBITS(n) \
186    do { \
187        hold >>= (n); \
188        bits -= (unsigned)(n); \
189    } while (0)
190
191/* Remove zero to seven bits as needed to go to a byte boundary */
192#define BYTEBITS() \
193    do { \
194        hold >>= bits & 7; \
195        bits -= bits & 7; \
196    } while (0)
197
198/* Assure that some output space is available, by writing out the window
199   if it's full.  If the write fails, return from inflateBack() with a
200   Z_BUF_ERROR. */
201#define ROOM() \
202    do { \
203        if (left == 0) { \
204            put = state->window; \
205            left = state->wsize; \
206            state->whave = left; \
207            if (out(out_desc, put, left)) { \
208                ret = Z_BUF_ERROR; \
209                goto inf_leave; \
210            } \
211        } \
212    } while (0)
213
214/*
215   strm provides the memory allocation functions and window buffer on input,
216   and provides information on the unused input on return.  For Z_DATA_ERROR
217   returns, strm will also provide an error message.
218
219   in() and out() are the call-back input and output functions.  When
220   inflateBack() needs more input, it calls in().  When inflateBack() has
221   filled the window with output, or when it completes with data in the
222   window, it calls out() to write out the data.  The application must not
223   change the provided input until in() is called again or inflateBack()
224   returns.  The application must not change the window/output buffer until
225   inflateBack() returns.
226
227   in() and out() are called with a descriptor parameter provided in the
228   inflateBack() call.  This parameter can be a structure that provides the
229   information required to do the read or write, as well as accumulated
230   information on the input and output such as totals and check values.
231
232   in() should return zero on failure.  out() should return non-zero on
233   failure.  If either in() or out() fails, than inflateBack() returns a
234   Z_BUF_ERROR.  strm->next_in can be checked for Z_NULL to see whether it
235   was in() or out() that caused in the error.  Otherwise,  inflateBack()
236   returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
237   error, or Z_MEM_ERROR if it could not allocate memory for the state.
238   inflateBack() can also return Z_STREAM_ERROR if the input parameters
239   are not correct, i.e. strm is Z_NULL or the state was not initialized.
240 */
241int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
242z_streamp strm;
243in_func in;
244void FAR *in_desc;
245out_func out;
246void FAR *out_desc;
247{
248    struct inflate_state FAR *state;
249    unsigned char FAR *next;    /* next input */
250    unsigned char FAR *put;     /* next output */
251    unsigned have, left;        /* available input and output */
252    unsigned long hold;         /* bit buffer */
253    unsigned bits;              /* bits in bit buffer */
254    unsigned copy;              /* number of stored or match bytes to copy */
255    unsigned char FAR *from;    /* where to copy match bytes from */
256    code this;                  /* current decoding table entry */
257    code last;                  /* parent table entry */
258    unsigned len;               /* length to copy for repeats, bits to drop */
259    int ret;                    /* return code */
260    static const unsigned short order[19] = /* permutation of code lengths */
261        {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
262
263    /* Check that the strm exists and that the state was initialized */
264    if (strm == Z_NULL || strm->state == Z_NULL)
265        return Z_STREAM_ERROR;
266    state = (struct inflate_state FAR *)strm->state;
267
268    /* Reset the state */
269    strm->msg = Z_NULL;
270    state->mode = TYPE;
271    state->last = 0;
272    state->whave = 0;
273    next = strm->next_in;
274    have = next != Z_NULL ? strm->avail_in : 0;
275    hold = 0;
276    bits = 0;
277    put = state->window;
278    left = state->wsize;
279
280    /* Inflate until end of block marked as last */
281    for (;;)
282        switch (state->mode) {
283        case TYPE:
284            /* determine and dispatch block type */
285            if (state->last) {
286                BYTEBITS();
287                state->mode = DONE;
288                break;
289            }
290            NEEDBITS(3);
291            state->last = BITS(1);
292            DROPBITS(1);
293            switch (BITS(2)) {
294            case 0:                             /* stored block */
295                Tracev((stderr, "inflate:     stored block%s\n",
296                        state->last ? " (last)" : ""));
297                state->mode = STORED;
298                break;
299            case 1:                             /* fixed block */
300                fixedtables(state);
301                Tracev((stderr, "inflate:     fixed codes block%s\n",
302                        state->last ? " (last)" : ""));
303                state->mode = LEN;              /* decode codes */
304                break;
305            case 2:                             /* dynamic block */
306                Tracev((stderr, "inflate:     dynamic codes block%s\n",
307                        state->last ? " (last)" : ""));
308                state->mode = TABLE;
309                break;
310            case 3:
311                strm->msg = (char *)"invalid block type";
312                state->mode = BAD;
313            }
314            DROPBITS(2);
315            break;
316
317        case STORED:
318            /* get and verify stored block length */
319            BYTEBITS();                         /* go to byte boundary */
320            NEEDBITS(32);
321            if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
322                strm->msg = (char *)"invalid stored block lengths";
323                state->mode = BAD;
324                break;
325            }
326            state->length = (unsigned)hold & 0xffff;
327            Tracev((stderr, "inflate:       stored length %u\n",
328                    state->length));
329            INITBITS();
330
331            /* copy stored block from input to output */
332            while (state->length != 0) {
333                copy = state->length;
334                PULL();
335                ROOM();
336                if (copy > have) copy = have;
337                if (copy > left) copy = left;
338                zmemcpy(put, next, copy);
339                have -= copy;
340                next += copy;
341                left -= copy;
342                put += copy;
343                state->length -= copy;
344            }
345            Tracev((stderr, "inflate:       stored end\n"));
346            state->mode = TYPE;
347            break;
348
349        case TABLE:
350            /* get dynamic table entries descriptor */
351            NEEDBITS(14);
352            state->nlen = BITS(5) + 257;
353            DROPBITS(5);
354            state->ndist = BITS(5) + 1;
355            DROPBITS(5);
356            state->ncode = BITS(4) + 4;
357            DROPBITS(4);
358#ifndef PKZIP_BUG_WORKAROUND
359            if (state->nlen > 286 || state->ndist > 30) {
360                strm->msg = (char *)"too many length or distance symbols";
361                state->mode = BAD;
362                break;
363            }
364#endif
365            Tracev((stderr, "inflate:       table sizes ok\n"));
366
367            /* get code length code lengths (not a typo) */
368            state->have = 0;
369            while (state->have < state->ncode) {
370                NEEDBITS(3);
371                state->lens[order[state->have++]] = (unsigned short)BITS(3);
372                DROPBITS(3);
373            }
374            while (state->have < 19)
375                state->lens[order[state->have++]] = 0;
376            state->next = state->codes;
377            state->lencode = (code const FAR *)(state->next);
378            state->lenbits = 7;
379            ret = inflate_table(CODES, state->lens, 19, &(state->next),
380                                &(state->lenbits), state->work);
381            if (ret) {
382                strm->msg = (char *)"invalid code lengths set";
383                state->mode = BAD;
384                break;
385            }
386            Tracev((stderr, "inflate:       code lengths ok\n"));
387
388            /* get length and distance code code lengths */
389            state->have = 0;
390            while (state->have < state->nlen + state->ndist) {
391                for (;;) {
392                    this = state->lencode[BITS(state->lenbits)];
393                    if ((unsigned)(this.bits) <= bits) break;
394                    PULLBYTE();
395                }
396                if (this.val < 16) {
397                    NEEDBITS(this.bits);
398                    DROPBITS(this.bits);
399                    state->lens[state->have++] = this.val;
400                }
401                else {
402                    if (this.val == 16) {
403                        NEEDBITS(this.bits + 2);
404                        DROPBITS(this.bits);
405                        if (state->have == 0) {
406                            strm->msg = (char *)"invalid bit length repeat";
407                            state->mode = BAD;
408                            break;
409                        }
410                        len = (unsigned)(state->lens[state->have - 1]);
411                        copy = 3 + BITS(2);
412                        DROPBITS(2);
413                    }
414                    else if (this.val == 17) {
415                        NEEDBITS(this.bits + 3);
416                        DROPBITS(this.bits);
417                        len = 0;
418                        copy = 3 + BITS(3);
419                        DROPBITS(3);
420                    }
421                    else {
422                        NEEDBITS(this.bits + 7);
423                        DROPBITS(this.bits);
424                        len = 0;
425                        copy = 11 + BITS(7);
426                        DROPBITS(7);
427                    }
428                    if (state->have + copy > state->nlen + state->ndist) {
429                        strm->msg = (char *)"invalid bit length repeat";
430                        state->mode = BAD;
431                        break;
432                    }
433                    while (copy--)
434                        state->lens[state->have++] = (unsigned short)len;
435                }
436            }
437
438            /* handle error breaks in while */
439            if (state->mode == BAD) break;
440
441            /* build code tables */
442            state->next = state->codes;
443            state->lencode = (code const FAR *)(state->next);
444            state->lenbits = 9;
445            ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
446                                &(state->lenbits), state->work);
447            if (ret) {
448                strm->msg = (char *)"invalid literal/lengths set";
449                state->mode = BAD;
450                break;
451            }
452            state->distcode = (code const FAR *)(state->next);
453            state->distbits = 6;
454            ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
455                            &(state->next), &(state->distbits), state->work);
456            if (ret) {
457                strm->msg = (char *)"invalid distances set";
458                state->mode = BAD;
459                break;
460            }
461            Tracev((stderr, "inflate:       codes ok\n"));
462            state->mode = LEN;
463
464        case LEN:
465            /* use inflate_fast() if we have enough input and output */
466            if (have >= 6 && left >= 258) {
467                RESTORE();
468                if (state->whave < state->wsize)
469                    state->whave = state->wsize - left;
470                inflate_fast(strm, state->wsize);
471                LOAD();
472                break;
473            }
474
475            /* get a literal, length, or end-of-block code */
476            for (;;) {
477                this = state->lencode[BITS(state->lenbits)];
478                if ((unsigned)(this.bits) <= bits) break;
479                PULLBYTE();
480            }
481            if (this.op && (this.op & 0xf0) == 0) {
482                last = this;
483                for (;;) {
484                    this = state->lencode[last.val +
485                            (BITS(last.bits + last.op) >> last.bits)];
486                    if ((unsigned)(last.bits + this.bits) <= bits) break;
487                    PULLBYTE();
488                }
489                DROPBITS(last.bits);
490            }
491            DROPBITS(this.bits);
492            state->length = (unsigned)this.val;
493
494            /* process literal */
495            if (this.op == 0) {
496                Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
497                        "inflate:         literal '%c'\n" :
498                        "inflate:         literal 0x%02x\n", this.val));
499                ROOM();
500                *put++ = (unsigned char)(state->length);
501                left--;
502                state->mode = LEN;
503                break;
504            }
505
506            /* process end of block */
507            if (this.op & 32) {
508                Tracevv((stderr, "inflate:         end of block\n"));
509                state->mode = TYPE;
510                break;
511            }
512
513            /* invalid code */
514            if (this.op & 64) {
515                strm->msg = (char *)"invalid literal/length code";
516                state->mode = BAD;
517                break;
518            }
519
520            /* length code -- get extra bits, if any */
521            state->extra = (unsigned)(this.op) & 15;
522            if (state->extra != 0) {
523                NEEDBITS(state->extra);
524                state->length += BITS(state->extra);
525                DROPBITS(state->extra);
526            }
527            Tracevv((stderr, "inflate:         length %u\n", state->length));
528
529            /* get distance code */
530            for (;;) {
531                this = state->distcode[BITS(state->distbits)];
532                if ((unsigned)(this.bits) <= bits) break;
533                PULLBYTE();
534            }
535            if ((this.op & 0xf0) == 0) {
536                last = this;
537                for (;;) {
538                    this = state->distcode[last.val +
539                            (BITS(last.bits + last.op) >> last.bits)];
540                    if ((unsigned)(last.bits + this.bits) <= bits) break;
541                    PULLBYTE();
542                }
543                DROPBITS(last.bits);
544            }
545            DROPBITS(this.bits);
546            if (this.op & 64) {
547                strm->msg = (char *)"invalid distance code";
548                state->mode = BAD;
549                break;
550            }
551            state->offset = (unsigned)this.val;
552
553            /* get distance extra bits, if any */
554            state->extra = (unsigned)(this.op) & 15;
555            if (state->extra != 0) {
556                NEEDBITS(state->extra);
557                state->offset += BITS(state->extra);
558                DROPBITS(state->extra);
559            }
560            if (state->offset > state->wsize - (state->whave < state->wsize ?
561                                                left : 0)) {
562                strm->msg = (char *)"invalid distance too far back";
563                state->mode = BAD;
564                break;
565            }
566            Tracevv((stderr, "inflate:         distance %u\n", state->offset));
567
568            /* copy match from window to output */
569            do {
570                ROOM();
571                copy = state->wsize - state->offset;
572                if (copy < left) {
573                    from = put + copy;
574                    copy = left - copy;
575                }
576                else {
577                    from = put - state->offset;
578                    copy = left;
579                }
580                if (copy > state->length) copy = state->length;
581                state->length -= copy;
582                left -= copy;
583                do {
584                    *put++ = *from++;
585                } while (--copy);
586            } while (state->length != 0);
587            break;
588
589        case DONE:
590            /* inflate stream terminated properly -- write leftover output */
591            ret = Z_STREAM_END;
592            if (left < state->wsize) {
593                if (out(out_desc, state->window, state->wsize - left))
594                    ret = Z_BUF_ERROR;
595            }
596            goto inf_leave;
597
598        case BAD:
599            ret = Z_DATA_ERROR;
600            goto inf_leave;
601
602        default:                /* can't happen, but makes compilers happy */
603            ret = Z_STREAM_ERROR;
604            goto inf_leave;
605        }
606
607    /* Return unused input */
608  inf_leave:
609    strm->next_in = next;
610    strm->avail_in = have;
611    return ret;
612}
613
614int ZEXPORT inflateBackEnd(strm)
615z_streamp strm;
616{
617    if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
618        return Z_STREAM_ERROR;
619    ZFREE(strm, strm->state);
620    strm->state = Z_NULL;
621    Tracev((stderr, "inflate: end\n"));
622    return Z_OK;
623}
Note: See TracBrowser for help on using the repository browser.