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