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