source: MondoRescue/branches/stable/mindi-busybox/archival/libunarchive/decompress_unzip.c @ 821

Last change on this file since 821 was 821, checked in by Bruno Cornec, 14 years ago

Addition of busybox 1.2.1 as a mindi-busybox new package
This should avoid delivering binary files in mindi not built there (Fedora and Debian are quite serious about that)

File size: 25.7 KB
Line 
1/* vi: set sw=4 ts=4: */
2/*
3 * gunzip implementation for busybox
4 *
5 * Based on GNU gzip v1.2.4 Copyright (C) 1992-1993 Jean-loup Gailly.
6 *
7 * Originally adjusted for busybox by Sven Rudolph <sr1@inf.tu-dresden.de>
8 * based on gzip sources
9 *
10 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
11 * files as well as stdin/stdout, and to generally behave itself wrt
12 * command line handling.
13 *
14 * General cleanup to better adhere to the style guide and make use of standard
15 * busybox functions by Glenn McGrath <bug1@iinet.net.au>
16 *
17 * read_gz interface + associated hacking by Laurence Anderson
18 *
19 * Fixed huft_build() so decoding end-of-block code does not grab more bits
20 * than necessary (this is required by unzip applet), added inflate_cleanup()
21 * to free leaked bytebuffer memory (used in unzip.c), and some minor style
22 * guide cleanups by Ed Clark
23 *
24 * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
25 * Copyright (C) 1992-1993 Jean-loup Gailly
26 * The unzip code was written and put in the public domain by Mark Adler.
27 * Portions of the lzw code are derived from the public domain 'compress'
28 * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
29 * Ken Turkowski, Dave Mack and Peter Jannesen.
30 *
31 * See the file algorithm.doc for the compression algorithms and file formats.
32 *
33 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
34 */
35
36#include "libbb.h"
37#include <sys/wait.h>
38#include <signal.h>
39#include "unarchive.h"
40
41typedef struct huft_s {
42    unsigned char e;    /* number of extra bits or operation */
43    unsigned char b;    /* number of bits in this code or subcode */
44    union {
45        unsigned short n;   /* literal, length base, or distance base */
46        struct huft_s *t;   /* pointer to next level of table */
47    } v;
48} huft_t;
49
50static int gunzip_src_fd;
51unsigned int gunzip_bytes_out;  /* number of output bytes */
52static unsigned int gunzip_outbuf_count;    /* bytes in output buffer */
53
54/* gunzip_window size--must be a power of two, and
55 *  at least 32K for zip's deflate method */
56enum { gunzip_wsize = 0x8000 };
57static unsigned char *gunzip_window;
58
59static uint32_t *gunzip_crc_table;
60uint32_t gunzip_crc;
61
62/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
63#define BMAX 16 /* maximum bit length of any code (16 for explode) */
64#define N_MAX 288   /* maximum number of codes in any set */
65
66/* bitbuffer */
67static unsigned int gunzip_bb;  /* bit buffer */
68static unsigned char gunzip_bk; /* bits in bit buffer */
69
70/* These control the size of the bytebuffer */
71static unsigned int bytebuffer_max = 0x8000;
72static unsigned char *bytebuffer = NULL;
73static unsigned int bytebuffer_offset = 0;
74static unsigned int bytebuffer_size = 0;
75
76static const unsigned short mask_bits[] = {
77    0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
78    0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
79};
80
81/* Copy lengths for literal codes 257..285 */
82static const unsigned short cplens[] = {
83    3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
84    67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
85};
86
87/* note: see note #13 above about the 258 in this list. */
88/* Extra bits for literal codes 257..285 */
89static const unsigned char cplext[] = {
90    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5,
91    5, 5, 5, 0, 99, 99
92};                      /* 99==invalid */
93
94/* Copy offsets for distance codes 0..29 */
95static const unsigned short cpdist[] = {
96    1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
97    769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
98};
99
100/* Extra bits for distance codes */
101static const unsigned char cpdext[] = {
102    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
103    11, 11, 12, 12, 13, 13
104};
105
106/* Tables for deflate from PKZIP's appnote.txt. */
107/* Order of the bit length code lengths */
108static const unsigned char border[] = {
109    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
110};
111
112static unsigned int fill_bitbuffer(unsigned int bitbuffer, unsigned int *current, const unsigned int required)
113{
114    while (*current < required) {
115        if (bytebuffer_offset >= bytebuffer_size) {
116            /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
117             * to the front of the bytebuffer, leave 4 bytes free at end of tail
118             * so we can easily top up buffer in check_trailer_gzip() */
119            if (!(bytebuffer_size = bb_xread(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 8))) {
120                bb_error_msg_and_die("unexpected end of file");
121            }
122            bytebuffer_size += 4;
123            bytebuffer_offset = 4;
124        }
125        bitbuffer |= ((unsigned int) bytebuffer[bytebuffer_offset]) << *current;
126        bytebuffer_offset++;
127        *current += 8;
128    }
129    return(bitbuffer);
130}
131
132/*
133 * Free the malloc'ed tables built by huft_build(), which makes a linked
134 * list of the tables it made, with the links in a dummy first entry of
135 * each table.
136 * t: table to free
137 */
138static int huft_free(huft_t * t)
139{
140    huft_t *p;
141    huft_t *q;
142
143    /* Go through linked list, freeing from the malloced (t[-1]) address. */
144    p = t;
145    while (p != (huft_t *) NULL) {
146        q = (--p)->v.t;
147        free((char *) p);
148        p = q;
149    }
150    return 0;
151}
152
153/* Given a list of code lengths and a maximum table size, make a set of
154 * tables to decode that set of codes.  Return zero on success, one if
155 * the given code set is incomplete (the tables are still built in this
156 * case), two if the input is invalid (all zero length codes or an
157 * oversubscribed set of lengths), and three if not enough memory.
158 *
159 * b:   code lengths in bits (all assumed <= BMAX)
160 * n:   number of codes (assumed <= N_MAX)
161 * s:   number of simple-valued codes (0..s-1)
162 * d:   list of base values for non-simple codes
163 * e:   list of extra bits for non-simple codes
164 * t:   result: starting table
165 * m:   maximum lookup bits, returns actual
166 */
167static
168int huft_build(unsigned int *b, const unsigned int n,
169               const unsigned int s, const unsigned short *d,
170               const unsigned char *e, huft_t ** t, unsigned int *m)
171{
172    unsigned a;             /* counter for codes of length k */
173    unsigned c[BMAX + 1];   /* bit length count table */
174    unsigned eob_len;       /* length of end-of-block code (value 256) */
175    unsigned f;             /* i repeats in table every f entries */
176    int g;                  /* maximum code length */
177    int htl;                /* table level */
178    unsigned i;             /* counter, current code */
179    unsigned j;             /* counter */
180    int k;                  /* number of bits in current code */
181    unsigned *p;            /* pointer into c[], b[], or v[] */
182    huft_t *q;              /* points to current table */
183    huft_t r;               /* table entry for structure assignment */
184    huft_t *u[BMAX];        /* table stack */
185    unsigned v[N_MAX];      /* values in order of bit length */
186    int ws[BMAX+1];         /* bits decoded stack */
187    int w;                  /* bits decoded */
188    unsigned x[BMAX + 1];   /* bit offsets, then code stack */
189    unsigned *xp;           /* pointer into x */
190    int y;                  /* number of dummy codes added */
191    unsigned z;             /* number of entries in current table */
192
193    /* Length of EOB code, if any */
194    eob_len = n > 256 ? b[256] : BMAX;
195
196    /* Generate counts for each bit length */
197    memset((void *)c, 0, sizeof(c));
198    p = b;
199    i = n;
200    do {
201        c[*p]++; /* assume all entries <= BMAX */
202        p++; /* Can't combine with above line (Solaris bug) */
203    } while (--i);
204    if (c[0] == n) { /* null input--all zero length codes */
205        *t = (huft_t *) NULL;
206        *m = 0;
207        return 2;
208    }
209
210    /* Find minimum and maximum length, bound *m by those */
211    for (j = 1; (c[j] == 0) && (j <= BMAX); j++);
212    k = j; /* minimum code length */
213    for (i = BMAX; (c[i] == 0) && i; i--);
214    g = i; /* maximum code length */
215    *m = (*m < j) ? j : ((*m > i) ? i : *m);
216
217    /* Adjust last length count to fill out codes, if needed */
218    for (y = 1 << j; j < i; j++, y <<= 1) {
219        if ((y -= c[j]) < 0) {
220            return 2; /* bad input: more codes than bits */
221        }
222    }
223    if ((y -= c[i]) < 0) {
224        return 2;
225    }
226    c[i] += y;
227
228    /* Generate starting offsets into the value table for each length */
229    x[1] = j = 0;
230    p = c + 1;
231    xp = x + 2;
232    while (--i) { /* note that i == g from above */
233        *xp++ = (j += *p++);
234    }
235
236    /* Make a table of values in order of bit lengths */
237    p = b;
238    i = 0;
239    do {
240        if ((j = *p++) != 0) {
241            v[x[j]++] = i;
242        }
243    } while (++i < n);
244
245    /* Generate the Huffman codes and for each, make the table entries */
246    x[0] = i = 0;           /* first Huffman code is zero */
247    p = v;                  /* grab values in bit order */
248    htl = -1;               /* no tables yet--level -1 */
249    w = ws[0] = 0;          /* bits decoded */
250    u[0] = (huft_t *) NULL; /* just to keep compilers happy */
251    q = (huft_t *) NULL;    /* ditto */
252    z = 0;                  /* ditto */
253
254    /* go through the bit lengths (k already is bits in shortest code) */
255    for (; k <= g; k++) {
256        a = c[k];
257        while (a--) {
258            /* here i is the Huffman code of length k bits for value *p */
259            /* make tables up to required level */
260            while (k > ws[htl + 1]) {
261                w = ws[++htl];
262
263                /* compute minimum size table less than or equal to *m bits */
264                z = (z = g - w) > *m ? *m : z; /* upper limit on table size */
265                if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table */
266                    /* too few codes for k-w bit table */
267                    f -= a + 1; /* deduct codes from patterns left */
268                    xp = c + k;
269                    while (++j < z) { /* try smaller tables up to z bits */
270                        if ((f <<= 1) <= *++xp) {
271                            break; /* enough codes to use up j bits */
272                        }
273                        f -= *xp; /* else deduct codes from patterns */
274                    }
275                }
276                j = (w + j > eob_len && w < eob_len) ? eob_len - w : j; /* make EOB code end at table */
277                z = 1 << j; /* table entries for j-bit table */
278                ws[htl+1] = w + j;  /* set bits decoded in stack */
279
280                /* allocate and link in new table */
281                q = (huft_t *) xzalloc((z + 1) * sizeof(huft_t));
282                *t = q + 1; /* link to list for huft_free() */
283                t = &(q->v.t);
284                u[htl] = ++q;   /* table starts after link */
285
286                /* connect to last table, if there is one */
287                if (htl) {
288                    x[htl] = i; /* save pattern for backing up */
289                    r.b = (unsigned char) (w - ws[htl - 1]); /* bits to dump before this table */
290                    r.e = (unsigned char) (16 + j); /* bits in this table */
291                    r.v.t = q; /* pointer to this table */
292                    j = (i & ((1 << w) - 1)) >> ws[htl - 1];
293                    u[htl - 1][j] = r; /* connect to last table */
294                }
295            }
296
297            /* set up table entry in r */
298            r.b = (unsigned char) (k - w);
299            if (p >= v + n) {
300                r.e = 99; /* out of values--invalid code */
301            } else if (*p < s) {
302                r.e = (unsigned char) (*p < 256 ? 16 : 15); /* 256 is EOB code */
303                r.v.n = (unsigned short) (*p++); /* simple code is just the value */
304            } else {
305                r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
306                r.v.n = d[*p++ - s];
307            }
308
309            /* fill code-like entries with r */
310            f = 1 << (k - w);
311            for (j = i >> w; j < z; j += f) {
312                q[j] = r;
313            }
314
315            /* backwards increment the k-bit code i */
316            for (j = 1 << (k - 1); i & j; j >>= 1) {
317                i ^= j;
318            }
319            i ^= j;
320
321            /* backup over finished tables */
322            while ((i & ((1 << w) - 1)) != x[htl]) {
323                w = ws[--htl];
324            }
325        }
326    }
327
328    /* return actual size of base table */
329    *m = ws[1];
330
331    /* Return true (1) if we were given an incomplete table */
332    return y != 0 && g != 1;
333}
334
335/*
336 * inflate (decompress) the codes in a deflated (compressed) block.
337 * Return an error code or zero if it all goes ok.
338 *
339 * tl, td: literal/length and distance decoder tables
340 * bl, bd: number of bits decoded by tl[] and td[]
341 */
342static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_bl, const unsigned int my_bd, int setup)
343{
344    static unsigned int e;  /* table entry flag/number of extra bits */
345    static unsigned int n, d;   /* length and index for copy */
346    static unsigned int w;  /* current gunzip_window position */
347    static huft_t *t;           /* pointer to table entry */
348    static unsigned int ml, md; /* masks for bl and bd bits */
349    static unsigned int b;  /* bit buffer */
350    static unsigned int k;          /* number of bits in bit buffer */
351    static huft_t *tl, *td;
352    static unsigned int bl, bd;
353    static int resumeCopy = 0;
354
355    if (setup) { // 1st time we are called, copy in variables
356        tl = my_tl;
357        td = my_td;
358        bl = my_bl;
359        bd = my_bd;
360        /* make local copies of globals */
361        b = gunzip_bb;              /* initialize bit buffer */
362        k = gunzip_bk;
363        w = gunzip_outbuf_count;            /* initialize gunzip_window position */
364
365        /* inflate the coded data */
366        ml = mask_bits[bl]; /* precompute masks for speed */
367        md = mask_bits[bd];
368        return 0; // Don't actually do anything the first time
369    }
370
371    if (resumeCopy) goto do_copy;
372
373    while (1) {         /* do until end of block */
374        b = fill_bitbuffer(b, &k, bl);
375        if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
376            do {
377                if (e == 99) {
378                    bb_error_msg_and_die("inflate_codes error 1");
379                }
380                b >>= t->b;
381                k -= t->b;
382                e -= 16;
383                b = fill_bitbuffer(b, &k, e);
384            } while ((e =
385                      (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
386        b >>= t->b;
387        k -= t->b;
388        if (e == 16) {  /* then it's a literal */
389            gunzip_window[w++] = (unsigned char) t->v.n;
390            if (w == gunzip_wsize) {
391                gunzip_outbuf_count = (w);
392                //flush_gunzip_window();
393                w = 0;
394                return 1; // We have a block to read
395            }
396        } else {        /* it's an EOB or a length */
397
398            /* exit if end of block */
399            if (e == 15) {
400                break;
401            }
402
403            /* get length of block to copy */
404            b = fill_bitbuffer(b, &k, e);
405            n = t->v.n + ((unsigned) b & mask_bits[e]);
406            b >>= e;
407            k -= e;
408
409            /* decode distance of block to copy */
410            b = fill_bitbuffer(b, &k, bd);
411            if ((e = (t = td + ((unsigned) b & md))->e) > 16)
412                do {
413                    if (e == 99)
414                        bb_error_msg_and_die("inflate_codes error 2");
415                    b >>= t->b;
416                    k -= t->b;
417                    e -= 16;
418                    b = fill_bitbuffer(b, &k, e);
419                } while ((e =
420                          (t =
421                           t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
422            b >>= t->b;
423            k -= t->b;
424            b = fill_bitbuffer(b, &k, e);
425            d = w - t->v.n - ((unsigned) b & mask_bits[e]);
426            b >>= e;
427            k -= e;
428
429            /* do the copy */
430do_copy:        do {
431                n -= (e =
432                      (e =
433                       gunzip_wsize - ((d &= gunzip_wsize - 1) > w ? d : w)) > n ? n : e);
434               /* copy to new buffer to prevent possible overwrite */
435                if (w - d >= e) {   /* (this test assumes unsigned comparison) */
436                    memcpy(gunzip_window + w, gunzip_window + d, e);
437                    w += e;
438                    d += e;
439                } else {
440                   /* do it slow to avoid memcpy() overlap */
441                   /* !NOMEMCPY */
442                    do {
443                        gunzip_window[w++] = gunzip_window[d++];
444                    } while (--e);
445                }
446                if (w == gunzip_wsize) {
447                    gunzip_outbuf_count = (w);
448                    if (n) resumeCopy = 1;
449                    else resumeCopy = 0;
450                    //flush_gunzip_window();
451                    w = 0;
452                    return 1;
453                }
454            } while (n);
455            resumeCopy = 0;
456        }
457    }
458
459    /* restore the globals from the locals */
460    gunzip_outbuf_count = w;            /* restore global gunzip_window pointer */
461    gunzip_bb = b;              /* restore global bit buffer */
462    gunzip_bk = k;
463
464    /* normally just after call to inflate_codes, but save code by putting it here */
465    /* free the decoding tables, return */
466    huft_free(tl);
467    huft_free(td);
468
469    /* done */
470    return 0;
471}
472
473static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
474{
475    static unsigned int n, b_stored, k_stored, w;
476    if (setup) {
477        n = my_n;
478        b_stored = my_b_stored;
479        k_stored = my_k_stored;
480        w = gunzip_outbuf_count;        /* initialize gunzip_window position */
481        return 0; // Don't do anything first time
482    }
483
484    /* read and output the compressed data */
485    while (n--) {
486        b_stored = fill_bitbuffer(b_stored, &k_stored, 8);
487        gunzip_window[w++] = (unsigned char) b_stored;
488        if (w == gunzip_wsize) {
489            gunzip_outbuf_count = (w);
490            //flush_gunzip_window();
491            w = 0;
492            b_stored >>= 8;
493            k_stored -= 8;
494            return 1; // We have a block
495        }
496        b_stored >>= 8;
497        k_stored -= 8;
498    }
499
500    /* restore the globals from the locals */
501    gunzip_outbuf_count = w;        /* restore global gunzip_window pointer */
502    gunzip_bb = b_stored;   /* restore global bit buffer */
503    gunzip_bk = k_stored;
504    return 0; // Finished
505}
506
507/*
508 * decompress an inflated block
509 * e: last block flag
510 *
511 * GLOBAL VARIABLES: bb, kk,
512 */
513 // Return values: -1 = inflate_stored, -2 = inflate_codes
514static int inflate_block(int *e)
515{
516    unsigned t;         /* block type */
517    register unsigned int b;    /* bit buffer */
518    unsigned int k; /* number of bits in bit buffer */
519
520    /* make local bit buffer */
521
522    b = gunzip_bb;
523    k = gunzip_bk;
524
525    /* read in last block bit */
526    b = fill_bitbuffer(b, &k, 1);
527    *e = (int) b & 1;
528    b >>= 1;
529    k -= 1;
530
531    /* read in block type */
532    b = fill_bitbuffer(b, &k, 2);
533    t = (unsigned) b & 3;
534    b >>= 2;
535    k -= 2;
536
537    /* restore the global bit buffer */
538    gunzip_bb = b;
539    gunzip_bk = k;
540
541    /* inflate that block type */
542    switch (t) {
543    case 0:         /* Inflate stored */
544    {
545        unsigned int n; /* number of bytes in block */
546        unsigned int b_stored;  /* bit buffer */
547        unsigned int k_stored;  /* number of bits in bit buffer */
548
549        /* make local copies of globals */
550        b_stored = gunzip_bb;   /* initialize bit buffer */
551        k_stored = gunzip_bk;
552
553        /* go to byte boundary */
554        n = k_stored & 7;
555        b_stored >>= n;
556        k_stored -= n;
557
558        /* get the length and its complement */
559        b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
560        n = ((unsigned) b_stored & 0xffff);
561        b_stored >>= 16;
562        k_stored -= 16;
563
564        b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
565        if (n != (unsigned) ((~b_stored) & 0xffff)) {
566            return 1;   /* error in compressed data */
567        }
568        b_stored >>= 16;
569        k_stored -= 16;
570
571        inflate_stored(n, b_stored, k_stored, 1); // Setup inflate_stored
572        return -1;
573    }
574    case 1:         /* Inflate fixed
575                           * decompress an inflated type 1 (fixed Huffman codes) block.  We should
576                           * either replace this with a custom decoder, or at least precompute the
577                           * Huffman tables.
578                         */
579    {
580        int i;          /* temporary variable */
581        huft_t *tl;     /* literal/length code table */
582        huft_t *td;     /* distance code table */
583        unsigned int bl;            /* lookup bits for tl */
584        unsigned int bd;            /* lookup bits for td */
585        unsigned int l[288];    /* length list for huft_build */
586
587        /* set up literal table */
588        for (i = 0; i < 144; i++) {
589            l[i] = 8;
590        }
591        for (; i < 256; i++) {
592            l[i] = 9;
593        }
594        for (; i < 280; i++) {
595            l[i] = 7;
596        }
597        for (; i < 288; i++) {  /* make a complete, but wrong code set */
598            l[i] = 8;
599        }
600        bl = 7;
601        if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
602            return i;
603        }
604
605        /* set up distance table */
606        for (i = 0; i < 30; i++) {  /* make an incomplete code set */
607            l[i] = 5;
608        }
609        bd = 5;
610        if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
611            huft_free(tl);
612            return i;
613        }
614
615        /* decompress until an end-of-block code */
616        inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
617
618        /* huft_free code moved into inflate_codes */
619
620        return -2;
621    }
622    case 2:         /* Inflate dynamic */
623    {
624        const int dbits = 6;    /* bits in base distance lookup table */
625        const int lbits = 9;    /* bits in base literal/length lookup table */
626
627        huft_t *tl;     /* literal/length code table */
628        huft_t *td;     /* distance code table */
629        unsigned int i;         /* temporary variables */
630        unsigned int j;
631        unsigned int l;     /* last length */
632        unsigned int m;     /* mask for bit lengths table */
633        unsigned int n;     /* number of lengths to get */
634        unsigned int bl;            /* lookup bits for tl */
635        unsigned int bd;            /* lookup bits for td */
636        unsigned int nb;    /* number of bit length codes */
637        unsigned int nl;    /* number of literal/length codes */
638        unsigned int nd;    /* number of distance codes */
639
640        unsigned int ll[286 + 30];  /* literal/length and distance code lengths */
641        unsigned int b_dynamic; /* bit buffer */
642        unsigned int k_dynamic; /* number of bits in bit buffer */
643
644        /* make local bit buffer */
645        b_dynamic = gunzip_bb;
646        k_dynamic = gunzip_bk;
647
648        /* read in table lengths */
649        b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
650        nl = 257 + ((unsigned int) b_dynamic & 0x1f);   /* number of literal/length codes */
651
652        b_dynamic >>= 5;
653        k_dynamic -= 5;
654        b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
655        nd = 1 + ((unsigned int) b_dynamic & 0x1f); /* number of distance codes */
656
657        b_dynamic >>= 5;
658        k_dynamic -= 5;
659        b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 4);
660        nb = 4 + ((unsigned int) b_dynamic & 0xf);  /* number of bit length codes */
661
662        b_dynamic >>= 4;
663        k_dynamic -= 4;
664        if (nl > 286 || nd > 30) {
665            return 1;   /* bad lengths */
666        }
667
668        /* read in bit-length-code lengths */
669        for (j = 0; j < nb; j++) {
670            b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
671            ll[border[j]] = (unsigned int) b_dynamic & 7;
672            b_dynamic >>= 3;
673            k_dynamic -= 3;
674        }
675        for (; j < 19; j++) {
676            ll[border[j]] = 0;
677        }
678
679        /* build decoding table for trees--single level, 7 bit lookup */
680        bl = 7;
681        i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
682        if (i != 0) {
683            if (i == 1) {
684                huft_free(tl);
685            }
686            return i;   /* incomplete code set */
687        }
688
689        /* read in literal and distance code lengths */
690        n = nl + nd;
691        m = mask_bits[bl];
692        i = l = 0;
693        while ((unsigned int) i < n) {
694            b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, (unsigned int)bl);
695            j = (td = tl + ((unsigned int) b_dynamic & m))->b;
696            b_dynamic >>= j;
697            k_dynamic -= j;
698            j = td->v.n;
699            if (j < 16) {   /* length of code in bits (0..15) */
700                ll[i++] = l = j;    /* save last length in l */
701            } else if (j == 16) {   /* repeat last length 3 to 6 times */
702                b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 2);
703                j = 3 + ((unsigned int) b_dynamic & 3);
704                b_dynamic >>= 2;
705                k_dynamic -= 2;
706                if ((unsigned int) i + j > n) {
707                    return 1;
708                }
709                while (j--) {
710                    ll[i++] = l;
711                }
712            } else if (j == 17) {   /* 3 to 10 zero length codes */
713                b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
714                j = 3 + ((unsigned int) b_dynamic & 7);
715                b_dynamic >>= 3;
716                k_dynamic -= 3;
717                if ((unsigned int) i + j > n) {
718                    return 1;
719                }
720                while (j--) {
721                    ll[i++] = 0;
722                }
723                l = 0;
724            } else {    /* j == 18: 11 to 138 zero length codes */
725                b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 7);
726                j = 11 + ((unsigned int) b_dynamic & 0x7f);
727                b_dynamic >>= 7;
728                k_dynamic -= 7;
729                if ((unsigned int) i + j > n) {
730                    return 1;
731                }
732                while (j--) {
733                    ll[i++] = 0;
734                }
735                l = 0;
736            }
737        }
738
739        /* free decoding table for trees */
740        huft_free(tl);
741
742        /* restore the global bit buffer */
743        gunzip_bb = b_dynamic;
744        gunzip_bk = k_dynamic;
745
746        /* build the decoding tables for literal/length and distance codes */
747        bl = lbits;
748
749        if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
750            if (i == 1) {
751                bb_error_msg_and_die("Incomplete literal tree");
752                huft_free(tl);
753            }
754            return i;   /* incomplete code set */
755        }
756
757        bd = dbits;
758        if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
759            if (i == 1) {
760                bb_error_msg_and_die("incomplete distance tree");
761                huft_free(td);
762            }
763            huft_free(tl);
764            return i;   /* incomplete code set */
765        }
766
767        /* decompress until an end-of-block code */
768        inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
769
770        /* huft_free code moved into inflate_codes */
771
772        return -2;
773    }
774    default:
775        /* bad block type */
776        bb_error_msg_and_die("bad block type %d\n", t);
777    }
778}
779
780static void calculate_gunzip_crc(void)
781{
782    int n;
783    for (n = 0; n < gunzip_outbuf_count; n++) {
784        gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
785    }
786    gunzip_bytes_out += gunzip_outbuf_count;
787}
788
789static int inflate_get_next_window(void)
790{
791    static int method = -1; // Method == -1 for stored, -2 for codes
792    static int e = 0;
793    static int needAnotherBlock = 1;
794
795    gunzip_outbuf_count = 0;
796
797    while(1) {
798        int ret;
799
800        if (needAnotherBlock) {
801            if(e) {
802                calculate_gunzip_crc();
803                e = 0;
804                needAnotherBlock = 1;
805                return 0;
806            } // Last block
807            method = inflate_block(&e);
808            needAnotherBlock = 0;
809        }
810
811        switch (method) {
812            case -1:    ret = inflate_stored(0,0,0,0);
813                    break;
814            case -2:    ret = inflate_codes(0,0,0,0,0);
815                    break;
816            default:    bb_error_msg_and_die("inflate error %d", method);
817        }
818
819        if (ret == 1) {
820            calculate_gunzip_crc();
821            return 1; // More data left
822        } else needAnotherBlock = 1; // End of that block
823    }
824    /* Doesnt get here */
825}
826
827/* Initialise bytebuffer, be careful not to overfill the buffer */
828void inflate_init(unsigned int bufsize)
829{
830    /* Set the bytebuffer size, default is same as gunzip_wsize */
831    bytebuffer_max = bufsize + 8;
832    bytebuffer_offset = 4;
833    bytebuffer_size = 0;
834}
835
836void inflate_cleanup(void)
837{
838    free(bytebuffer);
839}
840
841int inflate_unzip(int in, int out)
842{
843    ssize_t nwrote;
844    typedef void (*sig_type) (int);
845
846    /* Allocate all global buffers (for DYN_ALLOC option) */
847    gunzip_window = xmalloc(gunzip_wsize);
848    gunzip_outbuf_count = 0;
849    gunzip_bytes_out = 0;
850    gunzip_src_fd = in;
851
852    /* initialize gunzip_window, bit buffer */
853    gunzip_bk = 0;
854    gunzip_bb = 0;
855
856    /* Create the crc table */
857    gunzip_crc_table = bb_crc32_filltable(0);
858    gunzip_crc = ~0;
859   
860    /* Allocate space for buffer */
861    bytebuffer = xmalloc(bytebuffer_max);
862
863    while(1) {
864        int ret = inflate_get_next_window();
865        nwrote = bb_full_write(out, gunzip_window, gunzip_outbuf_count);
866        if (nwrote == -1) {
867            bb_perror_msg("write");
868            return -1;
869        }
870        if (ret == 0) break;
871    }
872
873    /* Cleanup */
874    free(gunzip_window);
875    free(gunzip_crc_table);
876
877    /* Store unused bytes in a global buffer so calling applets can access it */
878    if (gunzip_bk >= 8) {
879        /* Undo too much lookahead. The next read will be byte aligned
880         * so we can discard unused bits in the last meaningful byte. */
881        bytebuffer_offset--;
882        bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
883        gunzip_bb >>= 8;
884        gunzip_bk -= 8;
885    }
886    return 0;
887}
888
889int inflate_gunzip(int in, int out)
890{
891    uint32_t stored_crc = 0;
892    unsigned int count;
893
894    inflate_unzip(in, out);
895
896    /* top up the input buffer with the rest of the trailer */
897    count = bytebuffer_size - bytebuffer_offset;
898    if (count < 8) {
899        bb_xread_all(in, &bytebuffer[bytebuffer_size], 8 - count);
900        bytebuffer_size += 8 - count;
901    }
902    for (count = 0; count != 4; count++) {
903        stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
904        bytebuffer_offset++;
905    }
906
907    /* Validate decompression - crc */
908    if (stored_crc != (~gunzip_crc)) {
909        bb_error_msg("crc error");
910        return -1;
911    }
912
913    /* Validate decompression - size */
914    if (gunzip_bytes_out !=
915        (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
916        (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))) {
917        bb_error_msg("Incorrect length");
918        return -1;
919    }
920
921    return 0;
922}
Note: See TracBrowser for help on using the repository browser.