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 "unarchive.h"
  38
  39 typedef struct huft_s {
  40         unsigned char e;        /* number of extra bits or operation */
  41         unsigned char b;        /* number of bits in this code or subcode */
  42         union {
  43                 unsigned short n;       /* literal, length base, or distance base */
  44                 struct huft_s *t;       /* pointer to next level of table */
  45         } v;
  46 } huft_t;
  47
  48 /* Globally-visible data */
  49 off_t gunzip_bytes_out; /* number of output bytes */
  50 uint32_t gunzip_crc;
  51
  52 static int gunzip_src_fd;
  53 static unsigned gunzip_outbuf_count;    /* bytes in output buffer */
  54
  55 /* gunzip_window size--must be a power of two, and
  56  *  at least 32K for zip's deflate method */
  57 enum { gunzip_wsize = 0x8000 };
  58 static unsigned char *gunzip_window;
  59
  60 static uint32_t *gunzip_crc_table;
  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 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 bytebuffer_max = 0x8000;
  72 static unsigned char *bytebuffer = NULL;
  73 static unsigned bytebuffer_offset = 0;
  74 static unsigned 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 fill_bitbuffer(unsigned bitbuffer, unsigned *current, const unsigned 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                         bytebuffer_size = safe_read(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 8);
 120                         if (1 > bytebuffer_size)
 121 //shouldn't we propagate error?
 122                                 bb_error_msg_and_die("unexpected end of file");
 123                         bytebuffer_size += 4;
 124                         bytebuffer_offset = 4;
 125                 }
 126                 bitbuffer |= ((unsigned) bytebuffer[bytebuffer_offset]) << *current;
 127                 bytebuffer_offset++;
 128                 *current += 8;
 129         }
 130         return bitbuffer;
 131 }
 132
 133 /*
 134  * Free the malloc'ed tables built by huft_build(), which makes a linked
 135  * list of the tables it made, with the links in a dummy first entry of
 136  * each table.
 137  * t: table to free
 138  */
 139 static int huft_free(huft_t * t)
 140 {
 141         huft_t *p;
 142         huft_t *q;
 143
 144         /* Go through linked list, freeing from the malloced (t[-1]) address. */
 145         p = t;
 146         while (p != (huft_t *) NULL) {
 147                 q = (--p)->v.t;
 148                 free((char *) p);
 149                 p = q;
 150         }
 151         return 0;
 152 }
 153
 154 /* Given a list of code lengths and a maximum table size, make a set of
 155  * tables to decode that set of codes.  Return zero on success, one if
 156  * the given code set is incomplete (the tables are still built in this
 157  * case), two if the input is invalid (all zero length codes or an
 158  * oversubscribed set of lengths), and three if not enough memory.
 159  *
 160  * b:   code lengths in bits (all assumed <= BMAX)
 161  * n:   number of codes (assumed <= N_MAX)
 162  * s:   number of simple-valued codes (0..s-1)
 163  * d:   list of base values for non-simple codes
 164  * e:   list of extra bits for non-simple codes
 165  * t:   result: starting table
 166  * m:   maximum lookup bits, returns actual
 167  */
 168 static
 169 int huft_build(unsigned *b, const unsigned n,
 170                            const unsigned s, const unsigned short *d,
 171                            const unsigned char *e, huft_t ** t, unsigned *m)
 172 {
 173         unsigned a;                             /* counter for codes of length k */
 174         unsigned c[BMAX + 1];   /* bit length count table */
 175         unsigned eob_len;               /* length of end-of-block code (value 256) */
 176         unsigned f;                             /* i repeats in table every f entries */
 177         int g;                                  /* maximum code length */
 178         int htl;                                /* table level */
 179         unsigned i;                             /* counter, current code */
 180         unsigned j;                             /* counter */
 181         int k;                                  /* number of bits in current code */
 182         unsigned *p;                    /* pointer into c[], b[], or v[] */
 183         huft_t *q;                              /* points to current table */
 184         huft_t r;                               /* table entry for structure assignment */
 185         huft_t *u[BMAX];                /* table stack */
 186         unsigned v[N_MAX];              /* values in order of bit length */
 187         int ws[BMAX+1];                 /* bits decoded stack */
 188         int w;                                  /* bits decoded */
 189         unsigned x[BMAX + 1];   /* bit offsets, then code stack */
 190         unsigned *xp;                   /* pointer into x */
 191         int y;                                  /* number of dummy codes added */
 192         unsigned z;                             /* number of entries in current table */
 193
 194         /* Length of EOB code, if any */
 195         eob_len = n > 256 ? b[256] : BMAX;
 196
 197         /* Generate counts for each bit length */
 198         memset(c, 0, sizeof(c));
 199         p = b;
 200         i = n;
 201         do {
 202                 c[*p]++; /* assume all entries <= BMAX */
 203                 p++; /* Can't combine with above line (Solaris bug) */
 204         } while (--i);
 205         if (c[0] == n) { /* null input--all zero length codes */
 206                 *t = (huft_t *) NULL;
 207                 *m = 0;
 208                 return 2;
 209         }
 210
 211         /* Find minimum and maximum length, bound *m by those */
 212         for (j = 1; (c[j] == 0) && (j <= BMAX); j++);
 213         k = j; /* minimum code length */
 214         for (i = BMAX; (c[i] == 0) && i; i--);
 215         g = i; /* maximum code length */
 216         *m = (*m < j) ? j : ((*m > i) ? i : *m);
 217
 218         /* Adjust last length count to fill out codes, if needed */
 219         for (y = 1 << j; j < i; j++, y <<= 1) {
 220                 y -= c[j];
 221                 if (y < 0) {
 222                         return 2; /* bad input: more codes than bits */
 223                 }
 224         }
 225         y -= c[i];
 226         if (y < 0) {
 227                 return 2;
 228         }
 229         c[i] += y;
 230
 231         /* Generate starting offsets into the value table for each length */
 232         x[1] = j = 0;
 233         p = c + 1;
 234         xp = x + 2;
 235         while (--i) { /* note that i == g from above */
 236                 j += *p++;
 237                 *xp++ = j;
 238         }
 239
 240         /* Make a table of values in order of bit lengths */
 241         p = b;
 242         i = 0;
 243         do {
 244                 j = *p++;
 245                 if (j != 0) {
 246                         v[x[j]++] = i;
 247                 }
 248         } while (++i < n);
 249
 250         /* Generate the Huffman codes and for each, make the table entries */
 251         x[0] = i = 0;                   /* first Huffman code is zero */
 252         p = v;                                  /* grab values in bit order */
 253         htl = -1;                               /* no tables yet--level -1 */
 254         w = ws[0] = 0;                  /* bits decoded */
 255         u[0] = (huft_t *) NULL; /* just to keep compilers happy */
 256         q = (huft_t *) NULL;    /* ditto */
 257         z = 0;                                  /* ditto */
 258
 259         /* go through the bit lengths (k already is bits in shortest code) */
 260         for (; k <= g; k++) {
 261                 a = c[k];
 262                 while (a--) {
 263                         /* here i is the Huffman code of length k bits for value *p */
 264                         /* make tables up to required level */
 265                         while (k > ws[htl + 1]) {
 266                                 w = ws[++htl];
 267
 268                                 /* compute minimum size table less than or equal to *m bits */
 269                                 z = g - w;
 270                                 z = z > *m ? *m : z; /* upper limit on table size */
 271                                 j = k - w;
 272                                 f = 1 << j;
 273                                 if (f > a + 1) { /* try a k-w bit table */
 274                                         /* too few codes for k-w bit table */
 275                                         f -= a + 1; /* deduct codes from patterns left */
 276                                         xp = c + k;
 277                                         while (++j < z) { /* try smaller tables up to z bits */
 278                                                 f <<= 1;
 279                                                 if (f <= *++xp) {
 280                                                         break; /* enough codes to use up j bits */
 281                                                 }
 282                                                 f -= *xp; /* else deduct codes from patterns */
 283                                         }
 284                                 }
 285                                 j = (w + j > eob_len && w < eob_len) ? eob_len - w : j; /* make EOB code end at table */
 286                                 z = 1 << j;     /* table entries for j-bit table */
 287                                 ws[htl+1] = w + j;      /* set bits decoded in stack */
 288
 289                                 /* allocate and link in new table */
 290                                 q = xzalloc((z + 1) * sizeof(huft_t));
 291                                 *t = q + 1;     /* link to list for huft_free() */
 292                                 t = &(q->v.t);
 293                                 u[htl] = ++q;   /* table starts after link */
 294
 295                                 /* connect to last table, if there is one */
 296                                 if (htl) {
 297                                         x[htl] = i; /* save pattern for backing up */
 298                                         r.b = (unsigned char) (w - ws[htl - 1]); /* bits to dump before this table */
 299                                         r.e = (unsigned char) (16 + j); /* bits in this table */
 300                                         r.v.t = q; /* pointer to this table */
 301                                         j = (i & ((1 << w) - 1)) >> ws[htl - 1];
 302                                         u[htl - 1][j] = r; /* connect to last table */
 303                                 }
 304                         }
 305
 306                         /* set up table entry in r */
 307                         r.b = (unsigned char) (k - w);
 308                         if (p >= v + n) {
 309                                 r.e = 99; /* out of values--invalid code */
 310                         } else if (*p < s) {
 311                                 r.e = (unsigned char) (*p < 256 ? 16 : 15);     /* 256 is EOB code */
 312                                 r.v.n = (unsigned short) (*p++); /* simple code is just the value */
 313                         } else {
 314                                 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
 315                                 r.v.n = d[*p++ - s];
 316                         }
 317
 318                         /* fill code-like entries with r */
 319                         f = 1 << (k - w);
 320                         for (j = i >> w; j < z; j += f) {
 321                                 q[j] = r;
 322                         }
 323
 324                         /* backwards increment the k-bit code i */
 325                         for (j = 1 << (k - 1); i & j; j >>= 1) {
 326                                 i ^= j;
 327                         }
 328                         i ^= j;
 329
 330                         /* backup over finished tables */
 331                         while ((i & ((1 << w) - 1)) != x[htl]) {
 332                                 w = ws[--htl];
 333                         }
 334                 }
 335         }
 336
 337         /* return actual size of base table */
 338         *m = ws[1];
 339
 340         /* Return true (1) if we were given an incomplete table */
 341         return y != 0 && g != 1;
 342 }
 343
 344 /*
 345  * inflate (decompress) the codes in a deflated (compressed) block.
 346  * Return an error code or zero if it all goes ok.
 347  *
 348  * tl, td: literal/length and distance decoder tables
 349  * bl, bd: number of bits decoded by tl[] and td[]
 350  */
 351 /* called with setup==1 once from inflate_block */
 352 /* called once with setup==0 from inflate_get_next_window */
 353 static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned my_bl, const unsigned my_bd, int setup)
 354 {
 355         static unsigned e;      /* table entry flag/number of extra bits */
 356         static unsigned n, d;   /* length and index for copy */
 357         static unsigned w;      /* current gunzip_window position */
 358         static huft_t *t;                       /* pointer to table entry */
 359         static unsigned ml, md; /* masks for bl and bd bits */
 360         static unsigned b;      /* bit buffer */
 361         static unsigned k;                      /* number of bits in bit buffer */
 362         static huft_t *tl, *td;
 363         static unsigned bl, bd;
 364         static int resumeCopy = 0;
 365
 366         if (setup) { // 1st time we are called, copy in variables
 367                 tl = my_tl;
 368                 td = my_td;
 369                 bl = my_bl;
 370                 bd = my_bd;
 371                 /* make local copies of globals */
 372                 b = gunzip_bb;                          /* initialize bit buffer */
 373                 k = gunzip_bk;
 374                 w = gunzip_outbuf_count;                        /* initialize gunzip_window position */
 375
 376                 /* inflate the coded data */
 377                 ml = mask_bits[bl];     /* precompute masks for speed */
 378                 md = mask_bits[bd];
 379                 return 0; // Don't actually do anything the first time
 380         }
 381
 382         if (resumeCopy) goto do_copy;
 383
 384         while (1) {                     /* do until end of block */
 385                 b = fill_bitbuffer(b, &k, bl);
 386                 t = tl + ((unsigned) b & ml);
 387                 e = t->e;
 388                 if (e > 16)
 389                         do {
 390                                 if (e == 99) {
 391                                         bb_error_msg_and_die("inflate_codes error 1");
 392                                 }
 393                                 b >>= t->b;
 394                                 k -= t->b;
 395                                 e -= 16;
 396                                 b = fill_bitbuffer(b, &k, e);
 397                                 t = t->v.t + ((unsigned) b & mask_bits[e]);
 398                                 e = t->e;
 399                         } while (e > 16);
 400                 b >>= t->b;
 401                 k -= t->b;
 402                 if (e == 16) {  /* then it's a literal */
 403                         gunzip_window[w++] = (unsigned char) t->v.n;
 404                         if (w == gunzip_wsize) {
 405                                 gunzip_outbuf_count = (w);
 406                                 //flush_gunzip_window();
 407                                 w = 0;
 408                                 return 1; // We have a block to read
 409                         }
 410                 } else {                /* it's an EOB or a length */
 411
 412                         /* exit if end of block */
 413                         if (e == 15) {
 414                                 break;
 415                         }
 416
 417                         /* get length of block to copy */
 418                         b = fill_bitbuffer(b, &k, e);
 419                         n = t->v.n + ((unsigned) b & mask_bits[e]);
 420                         b >>= e;
 421                         k -= e;
 422
 423                         /* decode distance of block to copy */
 424                         b = fill_bitbuffer(b, &k, bd);
 425                         t = td + ((unsigned) b & md);
 426                         e = t->e;
 427                         if (e > 16)
 428                                 do {
 429                                         if (e == 99)
 430                                                 bb_error_msg_and_die("inflate_codes error 2");
 431                                         b >>= t->b;
 432                                         k -= t->b;
 433                                         e -= 16;
 434                                         b = fill_bitbuffer(b, &k, e);
 435                                         t = t->v.t + ((unsigned) b & mask_bits[e]);
 436                                         e = t->e;
 437                                 } while (e > 16);
 438                         b >>= t->b;
 439                         k -= t->b;
 440                         b = fill_bitbuffer(b, &k, e);
 441                         d = w - t->v.n - ((unsigned) b & mask_bits[e]);
 442                         b >>= e;
 443                         k -= e;
 444
 445                         /* do the copy */
 446  do_copy:
 447                         do {
 448                                 /* Was: n -= (e = (e = gunzip_wsize - ((d &= gunzip_wsize - 1) > w ? d : w)) > n ? n : e); */
 449                                 /* Who wrote THAT?? rewritten as: */
 450                                 d &= gunzip_wsize - 1;
 451                                 e = gunzip_wsize - (d > w ? d : w);
 452                                 if (e > n) e = n;
 453                                 n -= e;
 454
 455                                 /* copy to new buffer to prevent possible overwrite */
 456                                 if (w - d >= e) {       /* (this test assumes unsigned comparison) */
 457                                         memcpy(gunzip_window + w, gunzip_window + d, e);
 458                                         w += e;
 459                                         d += e;
 460                                 } else {
 461                                         /* do it slow to avoid memcpy() overlap */
 462                                         /* !NOMEMCPY */
 463                                         do {
 464                                                 gunzip_window[w++] = gunzip_window[d++];
 465                                         } while (--e);
 466                                 }
 467                                 if (w == gunzip_wsize) {
 468                                         gunzip_outbuf_count = (w);
 469                                         resumeCopy = (n != 0);
 470                                         //flush_gunzip_window();
 471                                         w = 0;
 472                                         return 1;
 473                                 }
 474                         } while (n);
 475                         resumeCopy = 0;
 476                 }
 477         }
 478
 479         /* restore the globals from the locals */
 480         gunzip_outbuf_count = w;                        /* restore global gunzip_window pointer */
 481         gunzip_bb = b;                          /* restore global bit buffer */
 482         gunzip_bk = k;
 483
 484         /* normally just after call to inflate_codes, but save code by putting it here */
 485         /* free the decoding tables, return */
 486         huft_free(tl);
 487         huft_free(td);
 488
 489         /* done */
 490         return 0;
 491 }
 492
 493 /* called once (setup==1) from inflate_block */
 494 /* and once (setup==0) from inflate_get_next_window */
 495 static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
 496 {
 497         static unsigned n, b_stored, k_stored, w;
 498
 499         if (setup) {
 500                 n = my_n;
 501                 b_stored = my_b_stored;
 502                 k_stored = my_k_stored;
 503                 w = gunzip_outbuf_count;                /* initialize gunzip_window position */
 504                 return 0; // Don't do anything first time
 505         }
 506
 507         /* read and output the compressed data */
 508         while (n--) {
 509                 b_stored = fill_bitbuffer(b_stored, &k_stored, 8);
 510                 gunzip_window[w++] = (unsigned char) b_stored;
 511                 if (w == gunzip_wsize) {
 512                         gunzip_outbuf_count = (w);
 513                         //flush_gunzip_window();
 514                         w = 0;
 515                         b_stored >>= 8;
 516                         k_stored -= 8;
 517                         return 1; // We have a block
 518                 }
 519                 b_stored >>= 8;
 520                 k_stored -= 8;
 521         }
 522
 523         /* restore the globals from the locals */
 524         gunzip_outbuf_count = w;                /* restore global gunzip_window pointer */
 525         gunzip_bb = b_stored;   /* restore global bit buffer */
 526         gunzip_bk = k_stored;
 527         return 0; // Finished
 528 }
 529
 530 /*
 531  * decompress an inflated block
 532  * e: last block flag
 533  *
 534  * GLOBAL VARIABLES: bb, kk,
 535  */
 536 /* Return values: -1 = inflate_stored, -2 = inflate_codes */
 537 /* One callsite in inflate_get_next_window */
 538 static int inflate_block(int *e)
 539 {
 540         unsigned t;                     /* block type */
 541         unsigned b;     /* bit buffer */
 542         unsigned k;     /* number of bits in bit buffer */
 543
 544         /* make local bit buffer */
 545
 546         b = gunzip_bb;
 547         k = gunzip_bk;
 548
 549         /* read in last block bit */
 550         b = fill_bitbuffer(b, &k, 1);
 551         *e = (int) b & 1;
 552         b >>= 1;
 553         k -= 1;
 554
 555         /* read in block type */
 556         b = fill_bitbuffer(b, &k, 2);
 557         t = (unsigned) b & 3;
 558         b >>= 2;
 559         k -= 2;
 560
 561         /* restore the global bit buffer */
 562         gunzip_bb = b;
 563         gunzip_bk = k;
 564
 565         /* inflate that block type */
 566         switch (t) {
 567         case 0:                 /* Inflate stored */
 568         {
 569                 unsigned n;     /* number of bytes in block */
 570                 unsigned b_stored;      /* bit buffer */
 571                 unsigned k_stored;      /* number of bits in bit buffer */
 572
 573                 /* make local copies of globals */
 574                 b_stored = gunzip_bb;   /* initialize bit buffer */
 575                 k_stored = gunzip_bk;
 576
 577                 /* go to byte boundary */
 578                 n = k_stored & 7;
 579                 b_stored >>= n;
 580                 k_stored -= n;
 581
 582                 /* get the length and its complement */
 583                 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
 584                 n = ((unsigned) b_stored & 0xffff);
 585                 b_stored >>= 16;
 586                 k_stored -= 16;
 587
 588                 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
 589                 if (n != (unsigned) ((~b_stored) & 0xffff)) {
 590                         return 1;       /* error in compressed data */
 591                 }
 592                 b_stored >>= 16;
 593                 k_stored -= 16;
 594
 595                 inflate_stored(n, b_stored, k_stored, 1); // Setup inflate_stored
 596                 return -1;
 597         }
 598         case 1:                 /* Inflate fixed
 599                                                    * decompress an inflated type 1 (fixed Huffman codes) block.  We should
 600                                                    * either replace this with a custom decoder, or at least precompute the
 601                                                    * Huffman tables.
 602                                                  */
 603         {
 604                 int i;                  /* temporary variable */
 605                 huft_t *tl;             /* literal/length code table */
 606                 huft_t *td;             /* distance code table */
 607                 unsigned bl;                    /* lookup bits for tl */
 608                 unsigned bd;                    /* lookup bits for td */
 609                 unsigned l[288];        /* length list for huft_build */
 610
 611                 /* set up literal table */
 612                 for (i = 0; i < 144; i++) {
 613                         l[i] = 8;
 614                 }
 615                 for (; i < 256; i++) {
 616                         l[i] = 9;
 617                 }
 618                 for (; i < 280; i++) {
 619                         l[i] = 7;
 620                 }
 621                 for (; i < 288; i++) {  /* make a complete, but wrong code set */
 622                         l[i] = 8;
 623                 }
 624                 bl = 7;
 625                 i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl);
 626                 if (i != 0) {
 627                         return i;
 628                 }
 629
 630                 /* set up distance table */
 631                 for (i = 0; i < 30; i++) {      /* make an incomplete code set */
 632                         l[i] = 5;
 633                 }
 634                 bd = 5;
 635                 i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd);
 636                 if (i > 1) {
 637                         huft_free(tl);
 638                         return i;
 639                 }
 640
 641                 /* decompress until an end-of-block code */
 642                 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
 643
 644                 /* huft_free code moved into inflate_codes */
 645
 646                 return -2;
 647         }
 648         case 2:                 /* Inflate dynamic */
 649         {
 650                 const int dbits = 6;    /* bits in base distance lookup table */
 651                 const int lbits = 9;    /* bits in base literal/length lookup table */
 652
 653                 huft_t *tl;             /* literal/length code table */
 654                 huft_t *td;             /* distance code table */
 655                 unsigned i;                     /* temporary variables */
 656                 unsigned j;
 657                 unsigned l;             /* last length */
 658                 unsigned m;             /* mask for bit lengths table */
 659                 unsigned n;             /* number of lengths to get */
 660                 unsigned bl;                    /* lookup bits for tl */
 661                 unsigned bd;                    /* lookup bits for td */
 662                 unsigned nb;    /* number of bit length codes */
 663                 unsigned nl;    /* number of literal/length codes */
 664                 unsigned nd;    /* number of distance codes */
 665
 666                 unsigned ll[286 + 30];  /* literal/length and distance code lengths */
 667                 unsigned b_dynamic;     /* bit buffer */
 668                 unsigned k_dynamic;     /* number of bits in bit buffer */
 669
 670                 /* make local bit buffer */
 671                 b_dynamic = gunzip_bb;
 672                 k_dynamic = gunzip_bk;
 673
 674                 /* read in table lengths */
 675                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
 676                 nl = 257 + ((unsigned) b_dynamic & 0x1f);       /* number of literal/length codes */
 677
 678                 b_dynamic >>= 5;
 679                 k_dynamic -= 5;
 680                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
 681                 nd = 1 + ((unsigned) b_dynamic & 0x1f); /* number of distance codes */
 682
 683                 b_dynamic >>= 5;
 684                 k_dynamic -= 5;
 685                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 4);
 686                 nb = 4 + ((unsigned) b_dynamic & 0xf);  /* number of bit length codes */
 687
 688                 b_dynamic >>= 4;
 689                 k_dynamic -= 4;
 690                 if (nl > 286 || nd > 30) {
 691                         return 1;       /* bad lengths */
 692                 }
 693
 694                 /* read in bit-length-code lengths */
 695                 for (j = 0; j < nb; j++) {
 696                         b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
 697                         ll[border[j]] = (unsigned) b_dynamic & 7;
 698                         b_dynamic >>= 3;
 699                         k_dynamic -= 3;
 700                 }
 701                 for (; j < 19; j++) {
 702                         ll[border[j]] = 0;
 703                 }
 704
 705                 /* build decoding table for trees--single level, 7 bit lookup */
 706                 bl = 7;
 707                 i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
 708                 if (i != 0) {
 709                         if (i == 1) {
 710                                 huft_free(tl);
 711                         }
 712                         return i;       /* incomplete code set */
 713                 }
 714
 715                 /* read in literal and distance code lengths */
 716                 n = nl + nd;
 717                 m = mask_bits[bl];
 718                 i = l = 0;
 719                 while ((unsigned) i < n) {
 720                         b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, (unsigned)bl);
 721                         j = (td = tl + ((unsigned) b_dynamic & m))->b;
 722                         b_dynamic >>= j;
 723                         k_dynamic -= j;
 724                         j = td->v.n;
 725                         if (j < 16) {   /* length of code in bits (0..15) */
 726                                 ll[i++] = l = j;        /* save last length in l */
 727                         } else if (j == 16) {   /* repeat last length 3 to 6 times */
 728                                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 2);
 729                                 j = 3 + ((unsigned) b_dynamic & 3);
 730                                 b_dynamic >>= 2;
 731                                 k_dynamic -= 2;
 732                                 if ((unsigned) i + j > n) {
 733                                         return 1;
 734                                 }
 735                                 while (j--) {
 736                                         ll[i++] = l;
 737                                 }
 738                         } else if (j == 17) {   /* 3 to 10 zero length codes */
 739                                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
 740                                 j = 3 + ((unsigned) b_dynamic & 7);
 741                                 b_dynamic >>= 3;
 742                                 k_dynamic -= 3;
 743                                 if ((unsigned) i + j > n) {
 744                                         return 1;
 745                                 }
 746                                 while (j--) {
 747                                         ll[i++] = 0;
 748                                 }
 749                                 l = 0;
 750                         } else {        /* j == 18: 11 to 138 zero length codes */
 751                                 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 7);
 752                                 j = 11 + ((unsigned) b_dynamic & 0x7f);
 753                                 b_dynamic >>= 7;
 754                                 k_dynamic -= 7;
 755                                 if ((unsigned) i + j > n) {
 756                                         return 1;
 757                                 }
 758                                 while (j--) {
 759                                         ll[i++] = 0;
 760                                 }
 761                                 l = 0;
 762                         }
 763                 }
 764
 765                 /* free decoding table for trees */
 766                 huft_free(tl);
 767
 768                 /* restore the global bit buffer */
 769                 gunzip_bb = b_dynamic;
 770                 gunzip_bk = k_dynamic;
 771
 772                 /* build the decoding tables for literal/length and distance codes */
 773                 bl = lbits;
 774
 775                 i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl);
 776                 if (i != 0) {
 777                         if (i == 1) {
 778                                 bb_error_msg_and_die("incomplete literal tree");
 779                                 /* huft_free(tl); */
 780                         }
 781                         return i;       /* incomplete code set */
 782                 }
 783
 784                 bd = dbits;
 785                 i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd);
 786                 if (i != 0) {
 787                         if (i == 1) {
 788                                 bb_error_msg_and_die("incomplete distance tree");
 789                                 /* huft_free(td); */
 790                         }
 791                         huft_free(tl);
 792                         return i;       /* incomplete code set */
 793                 }
 794
 795                 /* decompress until an end-of-block code */
 796                 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
 797
 798                 /* huft_free code moved into inflate_codes */
 799
 800                 return -2;
 801         }
 802         default:
 803                 /* bad block type */
 804                 bb_error_msg_and_die("bad block type %d", t);
 805         }
 806 }
 807
 808 /* Two callsites, both in inflate_get_next_window */
 809 static void calculate_gunzip_crc(void)
 810 {
 811         int n;
 812         for (n = 0; n < gunzip_outbuf_count; n++) {
 813                 gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
 814         }
 815         gunzip_bytes_out += gunzip_outbuf_count;
 816 }
 817
 818 /* One callsite in inflate_unzip */
 819 static int inflate_get_next_window(void)
 820 {
 821         static int method = -1; // Method == -1 for stored, -2 for codes
 822         static int e = 0;
 823         static int needAnotherBlock = 1;
 824
 825         gunzip_outbuf_count = 0;
 826
 827         while (1) {
 828                 int ret;
 829
 830                 if (needAnotherBlock) {
 831                         if(e) {
 832                                 calculate_gunzip_crc();
 833                                 e = 0;
 834                                 needAnotherBlock = 1;
 835                                 return 0;
 836                         } // Last block
 837                         method = inflate_block(&e);
 838                         needAnotherBlock = 0;
 839                 }
 840
 841                 switch (method) {
 842                 case -1:        ret = inflate_stored(0,0,0,0);
 843                                 break;
 844                 case -2:        ret = inflate_codes(0,0,0,0,0);
 845                                 break;
 846                 default:        bb_error_msg_and_die("inflate error %d", method);
 847                 }
 848
 849                 if (ret == 1) {
 850                         calculate_gunzip_crc();
 851                         return 1; // More data left
 852                 } else needAnotherBlock = 1; // End of that block
 853         }
 854         /* Doesnt get here */
 855 }
 856
 857 /* Initialize bytebuffer, be careful not to overfill the buffer */
 858 /* Called from archival/unzip.c */
 859 void inflate_init(unsigned bufsize)
 860 {
 861         /* Set the bytebuffer size, default is same as gunzip_wsize */
 862         bytebuffer_max = bufsize + 8;
 863         bytebuffer_offset = 4;
 864         bytebuffer_size = 0;
 865 }
 866
 867 /* Called from archival/unzip.c */
 868 void inflate_cleanup(void)
 869 {
 870         free(bytebuffer);
 871 }
 872
 873 /* Called from inflate_gunzip() and archival/unzip.c */
 874 USE_DESKTOP(long long) int
 875 inflate_unzip(int in, int out)
 876 {
 877         USE_DESKTOP(long long total = 0;)
 878         ssize_t nwrote;
 879         typedef void (*sig_type) (int);
 880
 881         /* Allocate all global buffers (for DYN_ALLOC option) */
 882         gunzip_window = xmalloc(gunzip_wsize);
 883         gunzip_outbuf_count = 0;
 884         gunzip_bytes_out = 0;
 885         gunzip_src_fd = in;
 886
 887         /* initialize gunzip_window, bit buffer */
 888         gunzip_bk = 0;
 889         gunzip_bb = 0;
 890
 891         /* Create the crc table */
 892         gunzip_crc_table = crc32_filltable(0);
 893         gunzip_crc = ~0;
 894
 895         /* Allocate space for buffer */
 896         bytebuffer = xmalloc(bytebuffer_max);
 897
 898         while (1) {
 899                 int ret = inflate_get_next_window();
 900                 nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
 901                 if (nwrote != gunzip_outbuf_count) {
 902                         bb_perror_msg("write");
 903                         return -1;
 904                 }
 905                 USE_DESKTOP(total += nwrote;)
 906                 if (ret == 0) break;
 907         }
 908
 909         /* Cleanup */
 910         free(gunzip_window);
 911         free(gunzip_crc_table);
 912
 913         /* Store unused bytes in a global buffer so calling applets can access it */
 914         if (gunzip_bk >= 8) {
 915                 /* Undo too much lookahead. The next read will be byte aligned
 916                  * so we can discard unused bits in the last meaningful byte. */
 917                 bytebuffer_offset--;
 918                 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
 919                 gunzip_bb >>= 8;
 920                 gunzip_bk -= 8;
 921         }
 922         return USE_DESKTOP(total) + 0;
 923 }
 924
 925 USE_DESKTOP(long long) int
 926 inflate_gunzip(int in, int out)
 927 {
 928         uint32_t stored_crc = 0;
 929         unsigned count;
 930         USE_DESKTOP(long long total = )inflate_unzip(in, out);
 931
 932         USE_DESKTOP(if (total < 0) return total;)
 933
 934         /* top up the input buffer with the rest of the trailer */
 935         count = bytebuffer_size - bytebuffer_offset;
 936         if (count < 8) {
 937                 xread(in, &bytebuffer[bytebuffer_size], 8 - count);
 938 //shouldn't we propagate error?
 939                 bytebuffer_size += 8 - count;
 940         }
 941         for (count = 0; count != 4; count++) {
 942                 stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
 943                 bytebuffer_offset++;
 944         }
 945
 946         /* Validate decompression - crc */
 947         if (stored_crc != (~gunzip_crc)) {
 948                 bb_error_msg("crc error");
 949                 return -1;
 950         }
 951
 952         /* Validate decompression - size */
 953         if (gunzip_bytes_out !=
 954                 (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
 955                 (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))
 956         ) {
 957                 bb_error_msg("incorrect length");
 958                 return -1;
 959         }
 960
 961         return USE_DESKTOP(total) + 0;
 962 }