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