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 #define ml inflate_codes_ml
 459 #define md inflate_codes_md
 460 #define bb inflate_codes_bb
 461 #define k  inflate_codes_k
 462 #define w  inflate_codes_w
 463 #define tl inflate_codes_tl
 464 #define td inflate_codes_td
 465 #define bl inflate_codes_bl
 466 #define bd inflate_codes_bd
 467 #define nn inflate_codes_nn
 468 #define dd inflate_codes_dd
 469 static void inflate_codes_setup(STATE_PARAM huft_t * my_tl, huft_t * my_td, const unsigned my_bl, const unsigned my_bd)
 470 {
 471         tl = my_tl;
 472         td = my_td;
 473         bl = my_bl;
 474         bd = my_bd;
 475         /* make local copies of globals */
 476         bb = gunzip_bb;                 /* initialize bit buffer */
 477         k = gunzip_bk;
 478         w = gunzip_outbuf_count;        /* initialize gunzip_window position */
 479         /* inflate the coded data */
 480         ml = mask_bits[bl];             /* precompute masks for speed */
 481         md = mask_bits[bd];
 482 }
 483 /* called once from inflate_get_next_window */
 484 static int inflate_codes(STATE_PARAM_ONLY)
 485 {
 486         unsigned e;     /* table entry flag/number of extra bits */
 487         huft_t *t;      /* pointer to table entry */
 488
 489         if (resume_copy) goto do_copy;
 490
 491         while (1) {                     /* do until end of block */
 492                 bb = fill_bitbuffer(PASS_STATE bb, &k, bl);
 493                 t = tl + ((unsigned) bb & ml);
 494                 e = t->e;
 495                 if (e > 16)
 496                         do {
 497                                 if (e == 99) {
 498 //shouldn't we propagate error?
 499                                         bb_error_msg_and_die("inflate_codes error 1");
 500                                 }
 501                                 bb >>= t->b;
 502                                 k -= t->b;
 503                                 e -= 16;
 504                                 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
 505                                 t = t->v.t + ((unsigned) bb & mask_bits[e]);
 506                                 e = t->e;
 507                         } while (e > 16);
 508                 bb >>= t->b;
 509                 k -= t->b;
 510                 if (e == 16) {  /* then it's a literal */
 511                         gunzip_window[w++] = (unsigned char) t->v.n;
 512                         if (w == GUNZIP_WSIZE) {
 513                                 gunzip_outbuf_count = w;
 514                                 //flush_gunzip_window();
 515                                 w = 0;
 516                                 return 1; // We have a block to read
 517                         }
 518                 } else {                /* it's an EOB or a length */
 519                         /* exit if end of block */
 520                         if (e == 15) {
 521                                 break;
 522                         }
 523
 524                         /* get length of block to copy */
 525                         bb = fill_bitbuffer(PASS_STATE bb, &k, e);
 526                         nn = t->v.n + ((unsigned) bb & mask_bits[e]);
 527                         bb >>= e;
 528                         k -= e;
 529
 530                         /* decode distance of block to copy */
 531                         bb = fill_bitbuffer(PASS_STATE bb, &k, bd);
 532                         t = td + ((unsigned) bb & md);
 533                         e = t->e;
 534                         if (e > 16)
 535                                 do {
 536                                         if (e == 99)
 537 //shouldn't we propagate error?
 538                                                 bb_error_msg_and_die("inflate_codes error 2");
 539                                         bb >>= t->b;
 540                                         k -= t->b;
 541                                         e -= 16;
 542                                         bb = fill_bitbuffer(PASS_STATE bb, &k, e);
 543                                         t = t->v.t + ((unsigned) bb & mask_bits[e]);
 544                                         e = t->e;
 545                                 } while (e > 16);
 546                         bb >>= t->b;
 547                         k -= t->b;
 548                         bb = fill_bitbuffer(PASS_STATE bb, &k, e);
 549                         dd = w - t->v.n - ((unsigned) bb & mask_bits[e]);
 550                         bb >>= e;
 551                         k -= e;
 552
 553                         /* do the copy */
 554  do_copy:
 555                         do {
 556                                 /* Was: nn -= (e = (e = GUNZIP_WSIZE - ((dd &= GUNZIP_WSIZE - 1) > w ? dd : w)) > nn ? nn : e); */
 557                                 /* Who wrote THAT?? rewritten as: */
 558                                 dd &= GUNZIP_WSIZE - 1;
 559                                 e = GUNZIP_WSIZE - (dd > w ? dd : w);
 560                                 if (e > nn) e = nn;
 561                                 nn -= e;
 562
 563                                 /* copy to new buffer to prevent possible overwrite */
 564                                 if (w - dd >= e) {      /* (this test assumes unsigned comparison) */
 565                                         memcpy(gunzip_window + w, gunzip_window + dd, e);
 566                                         w += e;
 567                                         dd += e;
 568                                 } else {
 569                                         /* do it slow to avoid memcpy() overlap */
 570                                         /* !NOMEMCPY */
 571                                         do {
 572                                                 gunzip_window[w++] = gunzip_window[dd++];
 573                                         } while (--e);
 574                                 }
 575                                 if (w == GUNZIP_WSIZE) {
 576                                         gunzip_outbuf_count = w;
 577                                         resume_copy = (nn != 0);
 578                                         //flush_gunzip_window();
 579                                         w = 0;
 580                                         return 1;
 581                                 }
 582                         } while (nn);
 583                         resume_copy = 0;
 584                 }
 585         }
 586
 587         /* restore the globals from the locals */
 588         gunzip_outbuf_count = w;        /* restore global gunzip_window pointer */
 589         gunzip_bb = bb;                 /* restore global bit buffer */
 590         gunzip_bk = k;
 591
 592         /* normally just after call to inflate_codes, but save code by putting it here */
 593         /* free the decoding tables, return */
 594         huft_free(tl);
 595         huft_free(td);
 596
 597         /* done */
 598         return 0;
 599 }
 600 #undef ml
 601 #undef md
 602 #undef bb
 603 #undef k
 604 #undef w
 605 #undef tl
 606 #undef td
 607 #undef bl
 608 #undef bd
 609 #undef nn
 610 #undef dd
 611
 612
 613 /* called once from inflate_block */
 614 static void inflate_stored_setup(STATE_PARAM int my_n, int my_b, int my_k)
 615 {
 616         inflate_stored_n = my_n;
 617         inflate_stored_b = my_b;
 618         inflate_stored_k = my_k;
 619         /* initialize gunzip_window position */
 620         inflate_stored_w = gunzip_outbuf_count;
 621 }
 622 /* called once from inflate_get_next_window */
 623 static int inflate_stored(STATE_PARAM_ONLY)
 624 {
 625         /* read and output the compressed data */
 626         while (inflate_stored_n--) {
 627                 inflate_stored_b = fill_bitbuffer(PASS_STATE inflate_stored_b, &inflate_stored_k, 8);
 628                 gunzip_window[inflate_stored_w++] = (unsigned char) inflate_stored_b;
 629                 if (inflate_stored_w == GUNZIP_WSIZE) {
 630                         gunzip_outbuf_count = inflate_stored_w;
 631                         //flush_gunzip_window();
 632                         inflate_stored_w = 0;
 633                         inflate_stored_b >>= 8;
 634                         inflate_stored_k -= 8;
 635                         return 1; // We have a block
 636                 }
 637                 inflate_stored_b >>= 8;
 638                 inflate_stored_k -= 8;
 639         }
 640
 641         /* restore the globals from the locals */
 642         gunzip_outbuf_count = inflate_stored_w;         /* restore global gunzip_window pointer */
 643         gunzip_bb = inflate_stored_b;   /* restore global bit buffer */
 644         gunzip_bk = inflate_stored_k;
 645         return 0; // Finished
 646 }
 647
 648
 649 /*
 650  * decompress an inflated block
 651  * e: last block flag
 652  *
 653  * GLOBAL VARIABLES: bb, kk,
 654  */
 655 /* Return values: -1 = inflate_stored, -2 = inflate_codes */
 656 /* One callsite in inflate_get_next_window */
 657 static int inflate_block(STATE_PARAM smallint *e)
 658 {
 659         unsigned t;                     /* block type */
 660         unsigned b;     /* bit buffer */
 661         unsigned k;     /* number of bits in bit buffer */
 662
 663         /* make local bit buffer */
 664
 665         b = gunzip_bb;
 666         k = gunzip_bk;
 667
 668         /* read in last block bit */
 669         b = fill_bitbuffer(PASS_STATE b, &k, 1);
 670         *e = b & 1;
 671         b >>= 1;
 672         k -= 1;
 673
 674         /* read in block type */
 675         b = fill_bitbuffer(PASS_STATE b, &k, 2);
 676         t = (unsigned) b & 3;
 677         b >>= 2;
 678         k -= 2;
 679
 680         /* restore the global bit buffer */
 681         gunzip_bb = b;
 682         gunzip_bk = k;
 683
 684         /* inflate that block type */
 685         switch (t) {
 686         case 0:                 /* Inflate stored */
 687         {
 688                 unsigned n;     /* number of bytes in block */
 689                 unsigned b_stored;      /* bit buffer */
 690                 unsigned k_stored;      /* number of bits in bit buffer */
 691
 692                 /* make local copies of globals */
 693                 b_stored = gunzip_bb;   /* initialize bit buffer */
 694                 k_stored = gunzip_bk;
 695
 696                 /* go to byte boundary */
 697                 n = k_stored & 7;
 698                 b_stored >>= n;
 699                 k_stored -= n;
 700
 701                 /* get the length and its complement */
 702                 b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
 703                 n = ((unsigned) b_stored & 0xffff);
 704                 b_stored >>= 16;
 705                 k_stored -= 16;
 706
 707                 b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
 708                 if (n != (unsigned) ((~b_stored) & 0xffff)) {
 709                         return 1;       /* error in compressed data */
 710                 }
 711                 b_stored >>= 16;
 712                 k_stored -= 16;
 713
 714                 inflate_stored_setup(PASS_STATE n, b_stored, k_stored); // Setup inflate_stored
 715
 716                 return -1;
 717         }
 718         case 1:
 719         /* Inflate fixed
 720          * decompress an inflated type 1 (fixed Huffman codes) block.  We should
 721          * either replace this with a custom decoder, or at least precompute the
 722          * Huffman tables. */
 723         {
 724                 int i;                  /* temporary variable */
 725                 huft_t *tl;             /* literal/length code table */
 726                 huft_t *td;             /* distance code table */
 727                 unsigned bl;                    /* lookup bits for tl */
 728                 unsigned bd;                    /* lookup bits for td */
 729                 unsigned l[288];        /* length list for huft_build */
 730
 731                 /* set up literal table */
 732                 for (i = 0; i < 144; i++) {
 733                         l[i] = 8;
 734                 }
 735                 for (; i < 256; i++) {
 736                         l[i] = 9;
 737                 }
 738                 for (; i < 280; i++) {
 739                         l[i] = 7;
 740                 }
 741                 for (; i < 288; i++) {  /* make a complete, but wrong code set */
 742                         l[i] = 8;
 743                 }
 744                 bl = 7;
 745                 i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl);
 746                 if (i != 0) {
 747                         return i;
 748                 }
 749
 750                 /* set up distance table */
 751                 for (i = 0; i < 30; i++) {      /* make an incomplete code set */
 752                         l[i] = 5;
 753                 }
 754                 bd = 5;
 755                 i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd);
 756                 if (i > 1) {
 757                         huft_free(tl);
 758                         return i;
 759                 }
 760
 761                 /* decompress until an end-of-block code */
 762                 inflate_codes_setup(PASS_STATE tl, td, bl, bd); // Setup inflate_codes
 763
 764                 /* huft_free code moved into inflate_codes */
 765
 766                 return -2;
 767         }
 768         case 2:                 /* Inflate dynamic */
 769         {
 770                 const int dbits = 6;    /* bits in base distance lookup table */
 771                 const int lbits = 9;    /* bits in base literal/length lookup table */
 772
 773                 huft_t *tl;             /* literal/length code table */
 774                 huft_t *td;             /* distance code table */
 775                 unsigned i;                     /* temporary variables */
 776                 unsigned j;
 777                 unsigned l;             /* last length */
 778                 unsigned m;             /* mask for bit lengths table */
 779                 unsigned n;             /* number of lengths to get */
 780                 unsigned bl;                    /* lookup bits for tl */
 781                 unsigned bd;                    /* lookup bits for td */
 782                 unsigned nb;    /* number of bit length codes */
 783                 unsigned nl;    /* number of literal/length codes */
 784                 unsigned nd;    /* number of distance codes */
 785
 786                 unsigned ll[286 + 30];  /* literal/length and distance code lengths */
 787                 unsigned b_dynamic;     /* bit buffer */
 788                 unsigned k_dynamic;     /* number of bits in bit buffer */
 789
 790                 /* make local bit buffer */
 791                 b_dynamic = gunzip_bb;
 792                 k_dynamic = gunzip_bk;
 793
 794                 /* read in table lengths */
 795                 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 5);
 796                 nl = 257 + ((unsigned) b_dynamic & 0x1f);       /* number of literal/length codes */
 797
 798                 b_dynamic >>= 5;
 799                 k_dynamic -= 5;
 800                 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 5);
 801                 nd = 1 + ((unsigned) b_dynamic & 0x1f); /* number of distance codes */
 802
 803                 b_dynamic >>= 5;
 804                 k_dynamic -= 5;
 805                 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 4);
 806                 nb = 4 + ((unsigned) b_dynamic & 0xf);  /* number of bit length codes */
 807
 808                 b_dynamic >>= 4;
 809                 k_dynamic -= 4;
 810                 if (nl > 286 || nd > 30) {
 811                         return 1;       /* bad lengths */
 812                 }
 813
 814                 /* read in bit-length-code lengths */
 815                 for (j = 0; j < nb; j++) {
 816                         b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 3);
 817                         ll[border[j]] = (unsigned) b_dynamic & 7;
 818                         b_dynamic >>= 3;
 819                         k_dynamic -= 3;
 820                 }
 821                 for (; j < 19; j++) {
 822                         ll[border[j]] = 0;
 823                 }
 824
 825                 /* build decoding table for trees--single level, 7 bit lookup */
 826                 bl = 7;
 827                 i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
 828                 if (i != 0) {
 829                         if (i == 1) {
 830                                 huft_free(tl);
 831                         }
 832                         return i;       /* incomplete code set */
 833                 }
 834
 835                 /* read in literal and distance code lengths */
 836                 n = nl + nd;
 837                 m = mask_bits[bl];
 838                 i = l = 0;
 839                 while ((unsigned) i < n) {
 840                         b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, (unsigned)bl);
 841                         j = (td = tl + ((unsigned) b_dynamic & m))->b;
 842                         b_dynamic >>= j;
 843                         k_dynamic -= j;
 844                         j = td->v.n;
 845                         if (j < 16) {   /* length of code in bits (0..15) */
 846                                 ll[i++] = l = j;        /* save last length in l */
 847                         } else if (j == 16) {   /* repeat last length 3 to 6 times */
 848                                 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 2);
 849                                 j = 3 + ((unsigned) b_dynamic & 3);
 850                                 b_dynamic >>= 2;
 851                                 k_dynamic -= 2;
 852                                 if ((unsigned) i + j > n) {
 853                                         return 1;
 854                                 }
 855                                 while (j--) {
 856                                         ll[i++] = l;
 857                                 }
 858                         } else if (j == 17) {   /* 3 to 10 zero length codes */
 859                                 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 3);
 860                                 j = 3 + ((unsigned) b_dynamic & 7);
 861                                 b_dynamic >>= 3;
 862                                 k_dynamic -= 3;
 863                                 if ((unsigned) i + j > n) {
 864                                         return 1;
 865                                 }
 866                                 while (j--) {
 867                                         ll[i++] = 0;
 868                                 }
 869                                 l = 0;
 870                         } else {        /* j == 18: 11 to 138 zero length codes */
 871                                 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 7);
 872                                 j = 11 + ((unsigned) b_dynamic & 0x7f);
 873                                 b_dynamic >>= 7;
 874                                 k_dynamic -= 7;
 875                                 if ((unsigned) i + j > n) {
 876                                         return 1;
 877                                 }
 878                                 while (j--) {
 879                                         ll[i++] = 0;
 880                                 }
 881                                 l = 0;
 882                         }
 883                 }
 884
 885                 /* free decoding table for trees */
 886                 huft_free(tl);
 887
 888                 /* restore the global bit buffer */
 889                 gunzip_bb = b_dynamic;
 890                 gunzip_bk = k_dynamic;
 891
 892                 /* build the decoding tables for literal/length and distance codes */
 893                 bl = lbits;
 894
 895                 i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl);
 896                 if (i != 0) {
 897                         if (i == 1) {
 898 //shouldn't we propagate error?
 899                                 bb_error_msg_and_die("incomplete literal tree");
 900                                 /* huft_free(tl); */
 901                         }
 902                         return i;       /* incomplete code set */
 903                 }
 904
 905                 bd = dbits;
 906                 i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd);
 907                 if (i != 0) {
 908                         if (i == 1) {
 909 //shouldn't we propagate error?
 910                                 bb_error_msg_and_die("incomplete distance tree");
 911                                 /* huft_free(td); */
 912                         }
 913                         huft_free(tl);
 914                         return i;       /* incomplete code set */
 915                 }
 916
 917                 /* decompress until an end-of-block code */
 918                 inflate_codes_setup(PASS_STATE tl, td, bl, bd); // Setup inflate_codes
 919
 920                 /* huft_free code moved into inflate_codes */
 921
 922                 return -2;
 923         }
 924         default:
 925                 /* bad block type */
 926 //shouldn't we propagate error?
 927                 bb_error_msg_and_die("bad block type %d", t);
 928         }
 929 }
 930
 931 /* Two callsites, both in inflate_get_next_window */
 932 static void calculate_gunzip_crc(STATE_PARAM_ONLY)
 933 {
 934         int n;
 935         for (n = 0; n < gunzip_outbuf_count; n++) {
 936                 gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
 937         }
 938         gunzip_bytes_out += gunzip_outbuf_count;
 939 }
 940
 941 /* One callsite in inflate_unzip_internal */
 942 static int inflate_get_next_window(STATE_PARAM_ONLY)
 943 {
 944         gunzip_outbuf_count = 0;
 945
 946         while (1) {
 947                 int ret;
 948
 949                 if (need_another_block) {
 950                         if (end_reached) {
 951                                 calculate_gunzip_crc(PASS_STATE_ONLY);
 952                                 end_reached = 0;
 953                                 need_another_block = 1;
 954                                 return 0; /* Last block */
 955                         }
 956                         method = inflate_block(PASS_STATE &end_reached);
 957                         need_another_block = 0;
 958                 }
 959
 960                 switch (method) {
 961                 case -1:
 962                         ret = inflate_stored(PASS_STATE_ONLY);
 963                         break;
 964                 case -2:
 965                         ret = inflate_codes(PASS_STATE_ONLY);
 966                         break;
 967                 default:
 968 //shouldn't we propagate error?
 969                         bb_error_msg_and_die("inflate error %d", method);
 970                 }
 971
 972                 if (ret == 1) {
 973                         calculate_gunzip_crc(PASS_STATE_ONLY);
 974                         return 1; // More data left
 975                 }
 976                 need_another_block = 1; // End of that block
 977         }
 978         /* Doesnt get here */
 979 }
 980
 981
 982 /* Called from inflate_gunzip() and inflate_unzip() */
 983 /* NB: bytebuffer is allocated here but freeing it is left to the caller! */
 984 static USE_DESKTOP(long long) int
 985 inflate_unzip_internal(STATE_PARAM int in, int out)
 986 {
 987         USE_DESKTOP(long long) int n = 0;
 988         ssize_t nwrote;
 989
 990         /* Allocate all global buffers (for DYN_ALLOC option) */
 991         gunzip_window = xmalloc(GUNZIP_WSIZE);
 992         gunzip_outbuf_count = 0;
 993         gunzip_bytes_out = 0;
 994         gunzip_src_fd = in;
 995
 996         /* initialize gunzip_window, bit buffer */
 997         gunzip_bk = 0;
 998         gunzip_bb = 0;
 999
1000         /* Create the crc table */
1001         gunzip_crc_table = crc32_filltable(0);
1002         gunzip_crc = ~0;
1003
1004         /* Allocate space for buffer */
1005         bytebuffer = xmalloc(bytebuffer_max);
1006
1007         while (1) {
1008                 int r = inflate_get_next_window(PASS_STATE_ONLY);
1009                 nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
1010                 if (nwrote != gunzip_outbuf_count) {
1011                         bb_perror_msg("write");
1012                         n = -1;
1013                         goto ret;
1014                 }
1015                 USE_DESKTOP(n += nwrote;)
1016                 if (r == 0) break;
1017         }
1018
1019         /* Store unused bytes in a global buffer so calling applets can access it */
1020         if (gunzip_bk >= 8) {
1021                 /* Undo too much lookahead. The next read will be byte aligned
1022                  * so we can discard unused bits in the last meaningful byte. */
1023                 bytebuffer_offset--;
1024                 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
1025                 gunzip_bb >>= 8;
1026                 gunzip_bk -= 8;
1027         }
1028  ret:
1029         /* Cleanup */
1030         free(gunzip_window);
1031         free(gunzip_crc_table);
1032         return n;
1033 }
1034
1035
1036 USE_DESKTOP(long long) int
1037 inflate_unzip(inflate_unzip_result *res, unsigned bufsize, int in, int out)
1038 {
1039         USE_DESKTOP(long long) int n;
1040         DECLARE_STATE;
1041
1042         ALLOC_STATE;
1043
1044         bytebuffer_max = bufsize + 8;
1045         bytebuffer_offset = 4;
1046         n = inflate_unzip_internal(PASS_STATE in, out);
1047
1048         res->crc = gunzip_crc;
1049         res->bytes_out = gunzip_bytes_out;
1050         free(bytebuffer);
1051         DEALLOC_STATE;
1052         return n;
1053 }
1054
1055
1056 USE_DESKTOP(long long) int
1057 inflate_gunzip(int in, int out)
1058 {
1059         uint32_t stored_crc = 0;
1060         unsigned count;
1061         USE_DESKTOP(long long) int n;
1062         DECLARE_STATE;
1063
1064         ALLOC_STATE;
1065
1066         bytebuffer_max = 0x8000;
1067         n = inflate_unzip_internal(PASS_STATE in, out);
1068
1069         if (n < 0) goto ret;
1070
1071         /* top up the input buffer with the rest of the trailer */
1072         count = bytebuffer_size - bytebuffer_offset;
1073         if (count < 8) {
1074                 xread(in, &bytebuffer[bytebuffer_size], 8 - count);
1075 //shouldn't we propagate error?
1076                 bytebuffer_size += 8 - count;
1077         }
1078         for (count = 0; count != 4; count++) {
1079                 stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
1080                 bytebuffer_offset++;
1081         }
1082
1083         /* Validate decompression - crc */
1084         if (stored_crc != (~gunzip_crc)) {
1085                 bb_error_msg("crc error");
1086                 n = -1;
1087                 goto ret;
1088         }
1089
1090         /* Validate decompression - size */
1091         if (gunzip_bytes_out !=
1092                 (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
1093                 (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))
1094         ) {
1095                 bb_error_msg("incorrect length");
1096                 n = -1;
1097         }
1098  ret:
1099         free(bytebuffer);
1100         DEALLOC_STATE;
1101         return n;
1102 }