1 #define DEBG(x) 2 #define DEBG1(x) 3 /* inflate.c -- Not copyrighted 1992 by Mark Adler 4 version c10p1, 10 January 1993 */ 5 6 /* 7 * Adapted for booting Linux by Hannu Savolainen 1993 8 * based on gzip-1.0.3 9 * 10 * Nicolas Pitre <nico@fluxnic.net>, 1999/04/14 : 11 * Little mods for all variable to reside either into rodata or bss segments 12 * by marking constant variables with 'const' and initializing all the others 13 * at run-time only. This allows for the kernel uncompressor to run 14 * directly from Flash or ROM memory on embedded systems. 15 */ 16 17 /* 18 Inflate deflated (PKZIP's method 8 compressed) data. The compression 19 method searches for as much of the current string of bytes (up to a 20 length of 258) in the previous 32 K bytes. If it doesn't find any 21 matches (of at least length 3), it codes the next byte. Otherwise, it 22 codes the length of the matched string and its distance backwards from 23 the current position. There is a single Huffman code that codes both 24 single bytes (called "literals") and match lengths. A second Huffman 25 code codes the distance information, which follows a length code. Each 26 length or distance code actually represents a base value and a number 27 of "extra" (sometimes zero) bits to get to add to the base value. At 28 the end of each deflated block is a special end-of-block (EOB) literal/ 29 length code. The decoding process is basically: get a literal/length 30 code; if EOB then done; if a literal, emit the decoded byte; if a 31 length then get the distance and emit the referred-to bytes from the 32 sliding window of previously emitted data. 33 34 There are (currently) three kinds of inflate blocks: stored, fixed, and 35 dynamic. The compressor deals with some chunk of data at a time, and 36 decides which method to use on a chunk-by-chunk basis. A chunk might 37 typically be 32 K or 64 K. If the chunk is incompressible, then the 38 "stored" method is used. In this case, the bytes are simply stored as 39 is, eight bits per byte, with none of the above coding. The bytes are 40 preceded by a count, since there is no longer an EOB code. 41 42 If the data is compressible, then either the fixed or dynamic methods 43 are used. In the dynamic method, the compressed data is preceded by 44 an encoding of the literal/length and distance Huffman codes that are 45 to be used to decode this block. The representation is itself Huffman 46 coded, and so is preceded by a description of that code. These code 47 descriptions take up a little space, and so for small blocks, there is 48 a predefined set of codes, called the fixed codes. The fixed method is 49 used if the block codes up smaller that way (usually for quite small 50 chunks), otherwise the dynamic method is used. In the latter case, the 51 codes are customized to the probabilities in the current block, and so 52 can code it much better than the pre-determined fixed codes. 53 54 The Huffman codes themselves are decoded using a multi-level table 55 lookup, in order to maximize the speed of decoding plus the speed of 56 building the decoding tables. See the comments below that precede the 57 lbits and dbits tuning parameters. 58 */ 59 60 61 /* 62 Notes beyond the 1.93a appnote.txt: 63 64 1. Distance pointers never point before the beginning of the output 65 stream. 66 2. Distance pointers can point back across blocks, up to 32k away. 67 3. There is an implied maximum of 7 bits for the bit length table and 68 15 bits for the actual data. 69 4. If only one code exists, then it is encoded using one bit. (Zero 70 would be more efficient, but perhaps a little confusing.) If two 71 codes exist, they are coded using one bit each (0 and 1). 72 5. There is no way of sending zero distance codes--a dummy must be 73 sent if there are none. (History: a pre 2.0 version of PKZIP would 74 store blocks with no distance codes, but this was discovered to be 75 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 76 zero distance codes, which is sent as one code of zero bits in 77 length. 78 6. There are up to 286 literal/length codes. Code 256 represents the 79 end-of-block. Note however that the static length tree defines 80 288 codes just to fill out the Huffman codes. Codes 286 and 287 81 cannot be used though, since there is no length base or extra bits 82 defined for them. Similarly, there are up to 30 distance codes. 83 However, static trees define 32 codes (all 5 bits) to fill out the 84 Huffman codes, but the last two had better not show up in the data. 85 7. Unzip can check dynamic Huffman blocks for complete code sets. 86 The exception is that a single code would not be complete (see #4). 87 8. The five bits following the block type is really the number of 88 literal codes sent minus 257. 89 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 90 (1+6+6). Therefore, to output three times the length, you output 91 three codes (1+1+1), whereas to output four times the same length, 92 you only need two codes (1+3). Hmm. 93 10. In the tree reconstruction algorithm, Code = Code + Increment 94 only if BitLength(i) is not zero. (Pretty obvious.) 95 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 96 12. Note: length code 284 can represent 227-258, but length code 285 97 really is 258. The last length deserves its own, short code 98 since it gets used a lot in very redundant files. The length 99 258 is special since 258 - 3 (the min match length) is 255. 100 13. The literal/length and distance code bit lengths are read as a 101 single stream of lengths. It is possible (and advantageous) for 102 a repeat code (16, 17, or 18) to go across the boundary between 103 the two sets of lengths. 104 */ 105 #include <linux/compiler.h> 106 #include <linux/slab.h> 107 108 #ifdef RCSID 109 static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #"; 110 #endif 111 112 #ifndef STATIC 113 114 #if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H) 115 # include <sys/types.h> 116 # include <stdlib.h> 117 #endif 118 119 #include "gzip.h" 120 #define STATIC 121 #endif /* !STATIC */ 122 123 #ifndef INIT 124 #define INIT 125 #endif 126 127 #define slide window 128 129 /* Huffman code lookup table entry--this entry is four bytes for machines 130 that have 16-bit pointers (e.g. PC's in the small or medium model). 131 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 132 means that v is a literal, 16 < e < 32 means that v is a pointer to 133 the next table, which codes e - 16 bits, and lastly e == 99 indicates 134 an unused code. If a code with e == 99 is looked up, this implies an 135 error in the data. */ 136 struct huft { 137 uch e; /* number of extra bits or operation */ 138 uch b; /* number of bits in this code or subcode */ 139 union { 140 ush n; /* literal, length base, or distance base */ 141 struct huft *t; /* pointer to next level of table */ 142 } v; 143 }; 144 145 146 /* Function prototypes */ 147 STATIC int INIT huft_build OF((unsigned *, unsigned, unsigned, 148 const ush *, const ush *, struct huft **, int *)); 149 STATIC int INIT huft_free OF((struct huft *)); 150 STATIC int INIT inflate_codes OF((struct huft *, struct huft *, int, int)); 151 STATIC int INIT inflate_stored OF((void)); 152 STATIC int INIT inflate_fixed OF((void)); 153 STATIC int INIT inflate_dynamic OF((void)); 154 STATIC int INIT inflate_block OF((int *)); 155 STATIC int INIT inflate OF((void)); 156 157 158 /* The inflate algorithm uses a sliding 32 K byte window on the uncompressed 159 stream to find repeated byte strings. This is implemented here as a 160 circular buffer. The index is updated simply by incrementing and then 161 ANDing with 0x7fff (32K-1). */ 162 /* It is left to other modules to supply the 32 K area. It is assumed 163 to be usable as if it were declared "uch slide[32768];" or as just 164 "uch *slide;" and then malloc'ed in the latter case. The definition 165 must be in unzip.h, included above. */ 166 /* unsigned wp; current position in slide */ 167 #define wp outcnt 168 #define flush_output(w) (wp=(w),flush_window()) 169 170 /* Tables for deflate from PKZIP's appnote.txt. */ 171 static const unsigned border[] = { /* Order of the bit length code lengths */ 172 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 173 static const ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 174 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 175 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 176 /* note: see note #13 above about the 258 in this list. */ 177 static const ush cplext[] = { /* Extra bits for literal codes 257..285 */ 178 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 179 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 180 static const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 181 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 182 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 183 8193, 12289, 16385, 24577}; 184 static const ush cpdext[] = { /* Extra bits for distance codes */ 185 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 186 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 187 12, 12, 13, 13}; 188 189 190 191 /* Macros for inflate() bit peeking and grabbing. 192 The usage is: 193 194 NEEDBITS(j) 195 x = b & mask_bits[j]; 196 DUMPBITS(j) 197 198 where NEEDBITS makes sure that b has at least j bits in it, and 199 DUMPBITS removes the bits from b. The macros use the variable k 200 for the number of bits in b. Normally, b and k are register 201 variables for speed, and are initialized at the beginning of a 202 routine that uses these macros from a global bit buffer and count. 203 204 If we assume that EOB will be the longest code, then we will never 205 ask for bits with NEEDBITS that are beyond the end of the stream. 206 So, NEEDBITS should not read any more bytes than are needed to 207 meet the request. Then no bytes need to be "returned" to the buffer 208 at the end of the last block. 209 210 However, this assumption is not true for fixed blocks--the EOB code 211 is 7 bits, but the other literal/length codes can be 8 or 9 bits. 212 (The EOB code is shorter than other codes because fixed blocks are 213 generally short. So, while a block always has an EOB, many other 214 literal/length codes have a significantly lower probability of 215 showing up at all.) However, by making the first table have a 216 lookup of seven bits, the EOB code will be found in that first 217 lookup, and so will not require that too many bits be pulled from 218 the stream. 219 */ 220 221 STATIC ulg bb; /* bit buffer */ 222 STATIC unsigned bk; /* bits in bit buffer */ 223 224 STATIC const ush mask_bits[] = { 225 0x0000, 226 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 227 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 228 }; 229 230 #define NEXTBYTE() ({ int v = get_byte(); if (v < 0) goto underrun; (uch)v; }) 231 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}} 232 #define DUMPBITS(n) {b>>=(n);k-=(n);} 233 234 #ifndef NO_INFLATE_MALLOC 235 /* A trivial malloc implementation, adapted from 236 * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994 237 */ 238 239 static unsigned long malloc_ptr; 240 static int malloc_count; 241 242 static void *malloc(int size) 243 { 244 void *p; 245 246 if (size < 0) 247 error("Malloc error"); 248 if (!malloc_ptr) 249 malloc_ptr = free_mem_ptr; 250 251 malloc_ptr = (malloc_ptr + 3) & ~3; /* Align */ 252 253 p = (void *)malloc_ptr; 254 malloc_ptr += size; 255 256 if (free_mem_end_ptr && malloc_ptr >= free_mem_end_ptr) 257 error("Out of memory"); 258 259 malloc_count++; 260 return p; 261 } 262 263 static void free(void *where) 264 { 265 malloc_count--; 266 if (!malloc_count) 267 malloc_ptr = free_mem_ptr; 268 } 269 #else 270 #define malloc(a) kmalloc(a, GFP_KERNEL) 271 #define free(a) kfree(a) 272 #endif 273 274 /* 275 Huffman code decoding is performed using a multi-level table lookup. 276 The fastest way to decode is to simply build a lookup table whose 277 size is determined by the longest code. However, the time it takes 278 to build this table can also be a factor if the data being decoded 279 is not very long. The most common codes are necessarily the 280 shortest codes, so those codes dominate the decoding time, and hence 281 the speed. The idea is you can have a shorter table that decodes the 282 shorter, more probable codes, and then point to subsidiary tables for 283 the longer codes. The time it costs to decode the longer codes is 284 then traded against the time it takes to make longer tables. 285 286 This results of this trade are in the variables lbits and dbits 287 below. lbits is the number of bits the first level table for literal/ 288 length codes can decode in one step, and dbits is the same thing for 289 the distance codes. Subsequent tables are also less than or equal to 290 those sizes. These values may be adjusted either when all of the 291 codes are shorter than that, in which case the longest code length in 292 bits is used, or when the shortest code is *longer* than the requested 293 table size, in which case the length of the shortest code in bits is 294 used. 295 296 There are two different values for the two tables, since they code a 297 different number of possibilities each. The literal/length table 298 codes 286 possible values, or in a flat code, a little over eight 299 bits. The distance table codes 30 possible values, or a little less 300 than five bits, flat. The optimum values for speed end up being 301 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 302 The optimum values may differ though from machine to machine, and 303 possibly even between compilers. Your mileage may vary. 304 */ 305 306 307 STATIC const int lbits = 9; /* bits in base literal/length lookup table */ 308 STATIC const int dbits = 6; /* bits in base distance lookup table */ 309 310 311 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 312 #define BMAX 16 /* maximum bit length of any code (16 for explode) */ 313 #define N_MAX 288 /* maximum number of codes in any set */ 314 315 316 STATIC unsigned hufts; /* track memory usage */ 317 318 319 STATIC int INIT huft_build( 320 unsigned *b, /* code lengths in bits (all assumed <= BMAX) */ 321 unsigned n, /* number of codes (assumed <= N_MAX) */ 322 unsigned s, /* number of simple-valued codes (0..s-1) */ 323 const ush *d, /* list of base values for non-simple codes */ 324 const ush *e, /* list of extra bits for non-simple codes */ 325 struct huft **t, /* result: starting table */ 326 int *m /* maximum lookup bits, returns actual */ 327 ) 328 /* Given a list of code lengths and a maximum table size, make a set of 329 tables to decode that set of codes. Return zero on success, one if 330 the given code set is incomplete (the tables are still built in this 331 case), two if the input is invalid (all zero length codes or an 332 oversubscribed set of lengths), and three if not enough memory. */ 333 { 334 unsigned a; /* counter for codes of length k */ 335 unsigned f; /* i repeats in table every f entries */ 336 int g; /* maximum code length */ 337 int h; /* table level */ 338 register unsigned i; /* counter, current code */ 339 register unsigned j; /* counter */ 340 register int k; /* number of bits in current code */ 341 int l; /* bits per table (returned in m) */ 342 register unsigned *p; /* pointer into c[], b[], or v[] */ 343 register struct huft *q; /* points to current table */ 344 struct huft r; /* table entry for structure assignment */ 345 register int w; /* bits before this table == (l * h) */ 346 unsigned *xp; /* pointer into x */ 347 int y; /* number of dummy codes added */ 348 unsigned z; /* number of entries in current table */ 349 struct { 350 unsigned c[BMAX+1]; /* bit length count table */ 351 struct huft *u[BMAX]; /* table stack */ 352 unsigned v[N_MAX]; /* values in order of bit length */ 353 unsigned x[BMAX+1]; /* bit offsets, then code stack */ 354 } *stk; 355 unsigned *c, *v, *x; 356 struct huft **u; 357 int ret; 358 359 DEBG("huft1 "); 360 361 stk = malloc(sizeof(*stk)); 362 if (stk == NULL) 363 return 3; /* out of memory */ 364 365 c = stk->c; 366 v = stk->v; 367 x = stk->x; 368 u = stk->u; 369 370 /* Generate counts for each bit length */ 371 memzero(stk->c, sizeof(stk->c)); 372 p = b; i = n; 373 do { 374 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), 375 n-i, *p)); 376 c[*p]++; /* assume all entries <= BMAX */ 377 p++; /* Can't combine with above line (Solaris bug) */ 378 } while (--i); 379 if (c[0] == n) /* null input--all zero length codes */ 380 { 381 *t = (struct huft *)NULL; 382 *m = 0; 383 ret = 2; 384 goto out; 385 } 386 387 DEBG("huft2 "); 388 389 /* Find minimum and maximum length, bound *m by those */ 390 l = *m; 391 for (j = 1; j <= BMAX; j++) 392 if (c[j]) 393 break; 394 k = j; /* minimum code length */ 395 if ((unsigned)l < j) 396 l = j; 397 for (i = BMAX; i; i--) 398 if (c[i]) 399 break; 400 g = i; /* maximum code length */ 401 if ((unsigned)l > i) 402 l = i; 403 *m = l; 404 405 DEBG("huft3 "); 406 407 /* Adjust last length count to fill out codes, if needed */ 408 for (y = 1 << j; j < i; j++, y <<= 1) 409 if ((y -= c[j]) < 0) { 410 ret = 2; /* bad input: more codes than bits */ 411 goto out; 412 } 413 if ((y -= c[i]) < 0) { 414 ret = 2; 415 goto out; 416 } 417 c[i] += y; 418 419 DEBG("huft4 "); 420 421 /* Generate starting offsets into the value table for each length */ 422 x[1] = j = 0; 423 p = c + 1; xp = x + 2; 424 while (--i) { /* note that i == g from above */ 425 *xp++ = (j += *p++); 426 } 427 428 DEBG("huft5 "); 429 430 /* Make a table of values in order of bit lengths */ 431 p = b; i = 0; 432 do { 433 if ((j = *p++) != 0) 434 v[x[j]++] = i; 435 } while (++i < n); 436 n = x[g]; /* set n to length of v */ 437 438 DEBG("h6 "); 439 440 /* Generate the Huffman codes and for each, make the table entries */ 441 x[0] = i = 0; /* first Huffman code is zero */ 442 p = v; /* grab values in bit order */ 443 h = -1; /* no tables yet--level -1 */ 444 w = -l; /* bits decoded == (l * h) */ 445 u[0] = (struct huft *)NULL; /* just to keep compilers happy */ 446 q = (struct huft *)NULL; /* ditto */ 447 z = 0; /* ditto */ 448 DEBG("h6a "); 449 450 /* go through the bit lengths (k already is bits in shortest code) */ 451 for (; k <= g; k++) 452 { 453 DEBG("h6b "); 454 a = c[k]; 455 while (a--) 456 { 457 DEBG("h6b1 "); 458 /* here i is the Huffman code of length k bits for value *p */ 459 /* make tables up to required level */ 460 while (k > w + l) 461 { 462 DEBG1("1 "); 463 h++; 464 w += l; /* previous table always l bits */ 465 466 /* compute minimum size table less than or equal to l bits */ 467 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */ 468 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 469 { /* too few codes for k-w bit table */ 470 DEBG1("2 "); 471 f -= a + 1; /* deduct codes from patterns left */ 472 xp = c + k; 473 if (j < z) 474 while (++j < z) /* try smaller tables up to z bits */ 475 { 476 if ((f <<= 1) <= *++xp) 477 break; /* enough codes to use up j bits */ 478 f -= *xp; /* else deduct codes from patterns */ 479 } 480 } 481 DEBG1("3 "); 482 z = 1 << j; /* table entries for j-bit table */ 483 484 /* allocate and link in new table */ 485 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == 486 (struct huft *)NULL) 487 { 488 if (h) 489 huft_free(u[0]); 490 ret = 3; /* not enough memory */ 491 goto out; 492 } 493 DEBG1("4 "); 494 hufts += z + 1; /* track memory usage */ 495 *t = q + 1; /* link to list for huft_free() */ 496 *(t = &(q->v.t)) = (struct huft *)NULL; 497 u[h] = ++q; /* table starts after link */ 498 499 DEBG1("5 "); 500 /* connect to last table, if there is one */ 501 if (h) 502 { 503 x[h] = i; /* save pattern for backing up */ 504 r.b = (uch)l; /* bits to dump before this table */ 505 r.e = (uch)(16 + j); /* bits in this table */ 506 r.v.t = q; /* pointer to this table */ 507 j = i >> (w - l); /* (get around Turbo C bug) */ 508 u[h-1][j] = r; /* connect to last table */ 509 } 510 DEBG1("6 "); 511 } 512 DEBG("h6c "); 513 514 /* set up table entry in r */ 515 r.b = (uch)(k - w); 516 if (p >= v + n) 517 r.e = 99; /* out of values--invalid code */ 518 else if (*p < s) 519 { 520 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 521 r.v.n = (ush)(*p); /* simple code is just the value */ 522 p++; /* one compiler does not like *p++ */ 523 } 524 else 525 { 526 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ 527 r.v.n = d[*p++ - s]; 528 } 529 DEBG("h6d "); 530 531 /* fill code-like entries with r */ 532 f = 1 << (k - w); 533 for (j = i >> w; j < z; j += f) 534 q[j] = r; 535 536 /* backwards increment the k-bit code i */ 537 for (j = 1 << (k - 1); i & j; j >>= 1) 538 i ^= j; 539 i ^= j; 540 541 /* backup over finished tables */ 542 while ((i & ((1 << w) - 1)) != x[h]) 543 { 544 h--; /* don't need to update q */ 545 w -= l; 546 } 547 DEBG("h6e "); 548 } 549 DEBG("h6f "); 550 } 551 552 DEBG("huft7 "); 553 554 /* Return true (1) if we were given an incomplete table */ 555 ret = y != 0 && g != 1; 556 557 out: 558 free(stk); 559 return ret; 560 } 561 562 563 564 STATIC int INIT huft_free( 565 struct huft *t /* table to free */ 566 ) 567 /* Free the malloc'ed tables built by huft_build(), which makes a linked 568 list of the tables it made, with the links in a dummy first entry of 569 each table. */ 570 { 571 register struct huft *p, *q; 572 573 574 /* Go through linked list, freeing from the malloced (t[-1]) address. */ 575 p = t; 576 while (p != (struct huft *)NULL) 577 { 578 q = (--p)->v.t; 579 free((char*)p); 580 p = q; 581 } 582 return 0; 583 } 584 585 586 STATIC int INIT inflate_codes( 587 struct huft *tl, /* literal/length decoder tables */ 588 struct huft *td, /* distance decoder tables */ 589 int bl, /* number of bits decoded by tl[] */ 590 int bd /* number of bits decoded by td[] */ 591 ) 592 /* inflate (decompress) the codes in a deflated (compressed) block. 593 Return an error code or zero if it all goes ok. */ 594 { 595 register unsigned e; /* table entry flag/number of extra bits */ 596 unsigned n, d; /* length and index for copy */ 597 unsigned w; /* current window position */ 598 struct huft *t; /* pointer to table entry */ 599 unsigned ml, md; /* masks for bl and bd bits */ 600 register ulg b; /* bit buffer */ 601 register unsigned k; /* number of bits in bit buffer */ 602 603 604 /* make local copies of globals */ 605 b = bb; /* initialize bit buffer */ 606 k = bk; 607 w = wp; /* initialize window position */ 608 609 /* inflate the coded data */ 610 ml = mask_bits[bl]; /* precompute masks for speed */ 611 md = mask_bits[bd]; 612 for (;;) /* do until end of block */ 613 { 614 NEEDBITS((unsigned)bl) 615 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) 616 do { 617 if (e == 99) 618 return 1; 619 DUMPBITS(t->b) 620 e -= 16; 621 NEEDBITS(e) 622 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); 623 DUMPBITS(t->b) 624 if (e == 16) /* then it's a literal */ 625 { 626 slide[w++] = (uch)t->v.n; 627 Tracevv((stderr, "%c", slide[w-1])); 628 if (w == WSIZE) 629 { 630 flush_output(w); 631 w = 0; 632 } 633 } 634 else /* it's an EOB or a length */ 635 { 636 /* exit if end of block */ 637 if (e == 15) 638 break; 639 640 /* get length of block to copy */ 641 NEEDBITS(e) 642 n = t->v.n + ((unsigned)b & mask_bits[e]); 643 DUMPBITS(e); 644 645 /* decode distance of block to copy */ 646 NEEDBITS((unsigned)bd) 647 if ((e = (t = td + ((unsigned)b & md))->e) > 16) 648 do { 649 if (e == 99) 650 return 1; 651 DUMPBITS(t->b) 652 e -= 16; 653 NEEDBITS(e) 654 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); 655 DUMPBITS(t->b) 656 NEEDBITS(e) 657 d = w - t->v.n - ((unsigned)b & mask_bits[e]); 658 DUMPBITS(e) 659 Tracevv((stderr,"\\[%d,%d]", w-d, n)); 660 661 /* do the copy */ 662 do { 663 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); 664 #if !defined(NOMEMCPY) && !defined(DEBUG) 665 if (w - d >= e) /* (this test assumes unsigned comparison) */ 666 { 667 memcpy(slide + w, slide + d, e); 668 w += e; 669 d += e; 670 } 671 else /* do it slow to avoid memcpy() overlap */ 672 #endif /* !NOMEMCPY */ 673 do { 674 slide[w++] = slide[d++]; 675 Tracevv((stderr, "%c", slide[w-1])); 676 } while (--e); 677 if (w == WSIZE) 678 { 679 flush_output(w); 680 w = 0; 681 } 682 } while (n); 683 } 684 } 685 686 687 /* restore the globals from the locals */ 688 wp = w; /* restore global window pointer */ 689 bb = b; /* restore global bit buffer */ 690 bk = k; 691 692 /* done */ 693 return 0; 694 695 underrun: 696 return 4; /* Input underrun */ 697 } 698 699 700 701 STATIC int INIT inflate_stored(void) 702 /* "decompress" an inflated type 0 (stored) block. */ 703 { 704 unsigned n; /* number of bytes in block */ 705 unsigned w; /* current window position */ 706 register ulg b; /* bit buffer */ 707 register unsigned k; /* number of bits in bit buffer */ 708 709 DEBG("<stor"); 710 711 /* make local copies of globals */ 712 b = bb; /* initialize bit buffer */ 713 k = bk; 714 w = wp; /* initialize window position */ 715 716 717 /* go to byte boundary */ 718 n = k & 7; 719 DUMPBITS(n); 720 721 722 /* get the length and its complement */ 723 NEEDBITS(16) 724 n = ((unsigned)b & 0xffff); 725 DUMPBITS(16) 726 NEEDBITS(16) 727 if (n != (unsigned)((~b) & 0xffff)) 728 return 1; /* error in compressed data */ 729 DUMPBITS(16) 730 731 732 /* read and output the compressed data */ 733 while (n--) 734 { 735 NEEDBITS(8) 736 slide[w++] = (uch)b; 737 if (w == WSIZE) 738 { 739 flush_output(w); 740 w = 0; 741 } 742 DUMPBITS(8) 743 } 744 745 746 /* restore the globals from the locals */ 747 wp = w; /* restore global window pointer */ 748 bb = b; /* restore global bit buffer */ 749 bk = k; 750 751 DEBG(">"); 752 return 0; 753 754 underrun: 755 return 4; /* Input underrun */ 756 } 757 758 759 /* 760 * We use `noinline' here to prevent gcc-3.5 from using too much stack space 761 */ 762 STATIC int noinline INIT inflate_fixed(void) 763 /* decompress an inflated type 1 (fixed Huffman codes) block. We should 764 either replace this with a custom decoder, or at least precompute the 765 Huffman tables. */ 766 { 767 int i; /* temporary variable */ 768 struct huft *tl; /* literal/length code table */ 769 struct huft *td; /* distance code table */ 770 int bl; /* lookup bits for tl */ 771 int bd; /* lookup bits for td */ 772 unsigned *l; /* length list for huft_build */ 773 774 DEBG("<fix"); 775 776 l = malloc(sizeof(*l) * 288); 777 if (l == NULL) 778 return 3; /* out of memory */ 779 780 /* set up literal table */ 781 for (i = 0; i < 144; i++) 782 l[i] = 8; 783 for (; i < 256; i++) 784 l[i] = 9; 785 for (; i < 280; i++) 786 l[i] = 7; 787 for (; i < 288; i++) /* make a complete, but wrong code set */ 788 l[i] = 8; 789 bl = 7; 790 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) { 791 free(l); 792 return i; 793 } 794 795 /* set up distance table */ 796 for (i = 0; i < 30; i++) /* make an incomplete code set */ 797 l[i] = 5; 798 bd = 5; 799 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) 800 { 801 huft_free(tl); 802 free(l); 803 804 DEBG(">"); 805 return i; 806 } 807 808 809 /* decompress until an end-of-block code */ 810 if (inflate_codes(tl, td, bl, bd)) { 811 free(l); 812 return 1; 813 } 814 815 /* free the decoding tables, return */ 816 free(l); 817 huft_free(tl); 818 huft_free(td); 819 return 0; 820 } 821 822 823 /* 824 * We use `noinline' here to prevent gcc-3.5 from using too much stack space 825 */ 826 STATIC int noinline INIT inflate_dynamic(void) 827 /* decompress an inflated type 2 (dynamic Huffman codes) block. */ 828 { 829 int i; /* temporary variables */ 830 unsigned j; 831 unsigned l; /* last length */ 832 unsigned m; /* mask for bit lengths table */ 833 unsigned n; /* number of lengths to get */ 834 struct huft *tl; /* literal/length code table */ 835 struct huft *td; /* distance code table */ 836 int bl; /* lookup bits for tl */ 837 int bd; /* lookup bits for td */ 838 unsigned nb; /* number of bit length codes */ 839 unsigned nl; /* number of literal/length codes */ 840 unsigned nd; /* number of distance codes */ 841 unsigned *ll; /* literal/length and distance code lengths */ 842 register ulg b; /* bit buffer */ 843 register unsigned k; /* number of bits in bit buffer */ 844 int ret; 845 846 DEBG("<dyn"); 847 848 #ifdef PKZIP_BUG_WORKAROUND 849 ll = malloc(sizeof(*ll) * (288+32)); /* literal/length and distance code lengths */ 850 #else 851 ll = malloc(sizeof(*ll) * (286+30)); /* literal/length and distance code lengths */ 852 #endif 853 854 if (ll == NULL) 855 return 1; 856 857 /* make local bit buffer */ 858 b = bb; 859 k = bk; 860 861 862 /* read in table lengths */ 863 NEEDBITS(5) 864 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ 865 DUMPBITS(5) 866 NEEDBITS(5) 867 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ 868 DUMPBITS(5) 869 NEEDBITS(4) 870 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ 871 DUMPBITS(4) 872 #ifdef PKZIP_BUG_WORKAROUND 873 if (nl > 288 || nd > 32) 874 #else 875 if (nl > 286 || nd > 30) 876 #endif 877 { 878 ret = 1; /* bad lengths */ 879 goto out; 880 } 881 882 DEBG("dyn1 "); 883 884 /* read in bit-length-code lengths */ 885 for (j = 0; j < nb; j++) 886 { 887 NEEDBITS(3) 888 ll[border[j]] = (unsigned)b & 7; 889 DUMPBITS(3) 890 } 891 for (; j < 19; j++) 892 ll[border[j]] = 0; 893 894 DEBG("dyn2 "); 895 896 /* build decoding table for trees--single level, 7 bit lookup */ 897 bl = 7; 898 if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) 899 { 900 if (i == 1) 901 huft_free(tl); 902 ret = i; /* incomplete code set */ 903 goto out; 904 } 905 906 DEBG("dyn3 "); 907 908 /* read in literal and distance code lengths */ 909 n = nl + nd; 910 m = mask_bits[bl]; 911 i = l = 0; 912 while ((unsigned)i < n) 913 { 914 NEEDBITS((unsigned)bl) 915 j = (td = tl + ((unsigned)b & m))->b; 916 DUMPBITS(j) 917 j = td->v.n; 918 if (j < 16) /* length of code in bits (0..15) */ 919 ll[i++] = l = j; /* save last length in l */ 920 else if (j == 16) /* repeat last length 3 to 6 times */ 921 { 922 NEEDBITS(2) 923 j = 3 + ((unsigned)b & 3); 924 DUMPBITS(2) 925 if ((unsigned)i + j > n) { 926 ret = 1; 927 goto out; 928 } 929 while (j--) 930 ll[i++] = l; 931 } 932 else if (j == 17) /* 3 to 10 zero length codes */ 933 { 934 NEEDBITS(3) 935 j = 3 + ((unsigned)b & 7); 936 DUMPBITS(3) 937 if ((unsigned)i + j > n) { 938 ret = 1; 939 goto out; 940 } 941 while (j--) 942 ll[i++] = 0; 943 l = 0; 944 } 945 else /* j == 18: 11 to 138 zero length codes */ 946 { 947 NEEDBITS(7) 948 j = 11 + ((unsigned)b & 0x7f); 949 DUMPBITS(7) 950 if ((unsigned)i + j > n) { 951 ret = 1; 952 goto out; 953 } 954 while (j--) 955 ll[i++] = 0; 956 l = 0; 957 } 958 } 959 960 DEBG("dyn4 "); 961 962 /* free decoding table for trees */ 963 huft_free(tl); 964 965 DEBG("dyn5 "); 966 967 /* restore the global bit buffer */ 968 bb = b; 969 bk = k; 970 971 DEBG("dyn5a "); 972 973 /* build the decoding tables for literal/length and distance codes */ 974 bl = lbits; 975 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) 976 { 977 DEBG("dyn5b "); 978 if (i == 1) { 979 error("incomplete literal tree"); 980 huft_free(tl); 981 } 982 ret = i; /* incomplete code set */ 983 goto out; 984 } 985 DEBG("dyn5c "); 986 bd = dbits; 987 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) 988 { 989 DEBG("dyn5d "); 990 if (i == 1) { 991 error("incomplete distance tree"); 992 #ifdef PKZIP_BUG_WORKAROUND 993 i = 0; 994 } 995 #else 996 huft_free(td); 997 } 998 huft_free(tl); 999 ret = i; /* incomplete code set */ 1000 goto out; 1001 #endif 1002 } 1003 1004 DEBG("dyn6 "); 1005 1006 /* decompress until an end-of-block code */ 1007 if (inflate_codes(tl, td, bl, bd)) { 1008 ret = 1; 1009 goto out; 1010 } 1011 1012 DEBG("dyn7 "); 1013 1014 /* free the decoding tables, return */ 1015 huft_free(tl); 1016 huft_free(td); 1017 1018 DEBG(">"); 1019 ret = 0; 1020 out: 1021 free(ll); 1022 return ret; 1023 1024 underrun: 1025 ret = 4; /* Input underrun */ 1026 goto out; 1027 } 1028 1029 1030 1031 STATIC int INIT inflate_block( 1032 int *e /* last block flag */ 1033 ) 1034 /* decompress an inflated block */ 1035 { 1036 unsigned t; /* block type */ 1037 register ulg b; /* bit buffer */ 1038 register unsigned k; /* number of bits in bit buffer */ 1039 1040 DEBG("<blk"); 1041 1042 /* make local bit buffer */ 1043 b = bb; 1044 k = bk; 1045 1046 1047 /* read in last block bit */ 1048 NEEDBITS(1) 1049 *e = (int)b & 1; 1050 DUMPBITS(1) 1051 1052 1053 /* read in block type */ 1054 NEEDBITS(2) 1055 t = (unsigned)b & 3; 1056 DUMPBITS(2) 1057 1058 1059 /* restore the global bit buffer */ 1060 bb = b; 1061 bk = k; 1062 1063 /* inflate that block type */ 1064 if (t == 2) 1065 return inflate_dynamic(); 1066 if (t == 0) 1067 return inflate_stored(); 1068 if (t == 1) 1069 return inflate_fixed(); 1070 1071 DEBG(">"); 1072 1073 /* bad block type */ 1074 return 2; 1075 1076 underrun: 1077 return 4; /* Input underrun */ 1078 } 1079 1080 1081 1082 STATIC int INIT inflate(void) 1083 /* decompress an inflated entry */ 1084 { 1085 int e; /* last block flag */ 1086 int r; /* result code */ 1087 unsigned h; /* maximum struct huft's malloc'ed */ 1088 1089 /* initialize window, bit buffer */ 1090 wp = 0; 1091 bk = 0; 1092 bb = 0; 1093 1094 1095 /* decompress until the last block */ 1096 h = 0; 1097 do { 1098 hufts = 0; 1099 #ifdef ARCH_HAS_DECOMP_WDOG 1100 arch_decomp_wdog(); 1101 #endif 1102 r = inflate_block(&e); 1103 if (r) 1104 return r; 1105 if (hufts > h) 1106 h = hufts; 1107 } while (!e); 1108 1109 /* Undo too much lookahead. The next read will be byte aligned so we 1110 * can discard unused bits in the last meaningful byte. 1111 */ 1112 while (bk >= 8) { 1113 bk -= 8; 1114 inptr--; 1115 } 1116 1117 /* flush out slide */ 1118 flush_output(wp); 1119 1120 1121 /* return success */ 1122 #ifdef DEBUG 1123 fprintf(stderr, "<%u> ", h); 1124 #endif /* DEBUG */ 1125 return 0; 1126 } 1127 1128 /********************************************************************** 1129 * 1130 * The following are support routines for inflate.c 1131 * 1132 **********************************************************************/ 1133 1134 static ulg crc_32_tab[256]; 1135 static ulg crc; /* initialized in makecrc() so it'll reside in bss */ 1136 #define CRC_VALUE (crc ^ 0xffffffffUL) 1137 1138 /* 1139 * Code to compute the CRC-32 table. Borrowed from 1140 * gzip-1.0.3/makecrc.c. 1141 */ 1142 1143 static void INIT 1144 makecrc(void) 1145 { 1146 /* Not copyrighted 1990 Mark Adler */ 1147 1148 unsigned long c; /* crc shift register */ 1149 unsigned long e; /* polynomial exclusive-or pattern */ 1150 int i; /* counter for all possible eight bit values */ 1151 int k; /* byte being shifted into crc apparatus */ 1152 1153 /* terms of polynomial defining this crc (except x^32): */ 1154 static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 1155 1156 /* Make exclusive-or pattern from polynomial */ 1157 e = 0; 1158 for (i = 0; i < sizeof(p)/sizeof(int); i++) 1159 e |= 1L << (31 - p[i]); 1160 1161 crc_32_tab[0] = 0; 1162 1163 for (i = 1; i < 256; i++) 1164 { 1165 c = 0; 1166 for (k = i | 256; k != 1; k >>= 1) 1167 { 1168 c = c & 1 ? (c >> 1) ^ e : c >> 1; 1169 if (k & 1) 1170 c ^= e; 1171 } 1172 crc_32_tab[i] = c; 1173 } 1174 1175 /* this is initialized here so this code could reside in ROM */ 1176 crc = (ulg)0xffffffffUL; /* shift register contents */ 1177 } 1178 1179 /* gzip flag byte */ 1180 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ASCII text */ 1181 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */ 1182 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */ 1183 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */ 1184 #define COMMENT 0x10 /* bit 4 set: file comment present */ 1185 #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */ 1186 #define RESERVED 0xC0 /* bit 6,7: reserved */ 1187 1188 /* 1189 * Do the uncompression! 1190 */ 1191 static int INIT gunzip(void) 1192 { 1193 uch flags; 1194 unsigned char magic[2]; /* magic header */ 1195 char method; 1196 ulg orig_crc = 0; /* original crc */ 1197 ulg orig_len = 0; /* original uncompressed length */ 1198 int res; 1199 1200 magic[0] = NEXTBYTE(); 1201 magic[1] = NEXTBYTE(); 1202 method = NEXTBYTE(); 1203 1204 if (magic[0] != 037 || 1205 ((magic[1] != 0213) && (magic[1] != 0236))) { 1206 error("bad gzip magic numbers"); 1207 return -1; 1208 } 1209 1210 /* We only support method #8, DEFLATED */ 1211 if (method != 8) { 1212 error("internal error, invalid method"); 1213 return -1; 1214 } 1215 1216 flags = (uch)get_byte(); 1217 if ((flags & ENCRYPTED) != 0) { 1218 error("Input is encrypted"); 1219 return -1; 1220 } 1221 if ((flags & CONTINUATION) != 0) { 1222 error("Multi part input"); 1223 return -1; 1224 } 1225 if ((flags & RESERVED) != 0) { 1226 error("Input has invalid flags"); 1227 return -1; 1228 } 1229 NEXTBYTE(); /* Get timestamp */ 1230 NEXTBYTE(); 1231 NEXTBYTE(); 1232 NEXTBYTE(); 1233 1234 (void)NEXTBYTE(); /* Ignore extra flags for the moment */ 1235 (void)NEXTBYTE(); /* Ignore OS type for the moment */ 1236 1237 if ((flags & EXTRA_FIELD) != 0) { 1238 unsigned len = (unsigned)NEXTBYTE(); 1239 len |= ((unsigned)NEXTBYTE())<<8; 1240 while (len--) (void)NEXTBYTE(); 1241 } 1242 1243 /* Get original file name if it was truncated */ 1244 if ((flags & ORIG_NAME) != 0) { 1245 /* Discard the old name */ 1246 while (NEXTBYTE() != 0) /* null */ ; 1247 } 1248 1249 /* Discard file comment if any */ 1250 if ((flags & COMMENT) != 0) { 1251 while (NEXTBYTE() != 0) /* null */ ; 1252 } 1253 1254 /* Decompress */ 1255 if ((res = inflate())) { 1256 switch (res) { 1257 case 0: 1258 break; 1259 case 1: 1260 error("invalid compressed format (err=1)"); 1261 break; 1262 case 2: 1263 error("invalid compressed format (err=2)"); 1264 break; 1265 case 3: 1266 error("out of memory"); 1267 break; 1268 case 4: 1269 error("out of input data"); 1270 break; 1271 default: 1272 error("invalid compressed format (other)"); 1273 } 1274 return -1; 1275 } 1276 1277 /* Get the crc and original length */ 1278 /* crc32 (see algorithm.doc) 1279 * uncompressed input size modulo 2^32 1280 */ 1281 orig_crc = (ulg) NEXTBYTE(); 1282 orig_crc |= (ulg) NEXTBYTE() << 8; 1283 orig_crc |= (ulg) NEXTBYTE() << 16; 1284 orig_crc |= (ulg) NEXTBYTE() << 24; 1285 1286 orig_len = (ulg) NEXTBYTE(); 1287 orig_len |= (ulg) NEXTBYTE() << 8; 1288 orig_len |= (ulg) NEXTBYTE() << 16; 1289 orig_len |= (ulg) NEXTBYTE() << 24; 1290 1291 /* Validate decompression */ 1292 if (orig_crc != CRC_VALUE) { 1293 error("crc error"); 1294 return -1; 1295 } 1296 if (orig_len != bytes_out) { 1297 error("length error"); 1298 return -1; 1299 } 1300 return 0; 1301 1302 underrun: /* NEXTBYTE() goto's here if needed */ 1303 error("out of input data"); 1304 return -1; 1305 } 1306 1307 1308