archival/libunarchive/decompress_unzip.c

   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
  41 typedef 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
  50 static int gunzip_src_fd;
  51 unsigned int gunzip_bytes_out;  /* number of output bytes */
  52 static 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 */
  56 enum { gunzip_wsize = 0x8000 };
  57 static unsigned char *gunzip_window;
  58
  59 static uint32_t *gunzip_crc_table;
  60 uint32_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 */
  67 static unsigned int gunzip_bb;  /* bit buffer */
  68 static unsigned char gunzip_bk; /* bits in bit buffer */
  69
  70 /* These control the size of the bytebuffer */
  71 static unsigned int bytebuffer_max = 0x8000;
  72 static unsigned char *bytebuffer = NULL;
  73 static unsigned int bytebuffer_offset = 0;
  74 static unsigned int bytebuffer_size = 0;
  75
  76 static 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 */
  82 static 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 */
  89 static 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 */
  95 static 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 */
 101 static 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 */
 108 static 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
 112 static 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  */
 138 static 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  */
 167 static
 168 int 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  */
 342 static 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 */
 430 do_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
 473 static 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
 514 static int inflate_block(int *e)
 515 {
 516         unsigned t;                     /* block type */
 517         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
 780 static 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
 789 static 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 */
 828 void 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
 836 void inflate_cleanup(void)
 837 {
 838         free(bytebuffer);
 839 }
 840
 841 int 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
 889 int 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 }