1 /* 2 * GRUB -- GRand Unified Bootloader 3 * Copyright (C) 1999 Free Software Foundation, Inc. 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation; either version 2 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, write to the Free Software 17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 18 */ 19 20 /* 21 * Most of this file was originally the source file "inflate.c", written 22 * by Mark Adler. It has been very heavily modified. In particular, the 23 * original would run through the whole file at once, and this version can 24 * be stopped and restarted on any boundary during the decompression process. 25 * 26 * The license and header comments that file are included here. 27 */ 28 29 /* inflate.c -- Not copyrighted 1992 by Mark Adler 30 version c10p1, 10 January 1993 */ 31 32 /* You can do whatever you like with this source file, though I would 33 prefer that if you modify it and redistribute it that you include 34 comments to that effect with your name and the date. Thank you. 35 */ 36 37 /* 38 Inflate deflated (PKZIP's method 8 compressed) data. The compression 39 method searches for as much of the current string of bytes (up to a 40 length of 258) in the previous 32K bytes. If it doesn't find any 41 matches (of at least length 3), it codes the next byte. Otherwise, it 42 codes the length of the matched string and its distance backwards from 43 the current position. There is a single Huffman code that codes both 44 single bytes (called "literals") and match lengths. A second Huffman 45 code codes the distance information, which follows a length code. Each 46 length or distance code actually represents a base value and a number 47 of "extra" (sometimes zero) bits to get to add to the base value. At 48 the end of each deflated block is a special end-of-block (EOB) literal/ 49 length code. The decoding process is basically: get a literal/length 50 code; if EOB then done; if a literal, emit the decoded byte; if a 51 length then get the distance and emit the referred-to bytes from the 52 sliding window of previously emitted data. 53 54 There are (currently) three kinds of inflate blocks: stored, fixed, and 55 dynamic. The compressor deals with some chunk of data at a time, and 56 decides which method to use on a chunk-by-chunk basis. A chunk might 57 typically be 32K or 64K. If the chunk is uncompressible, then the 58 "stored" method is used. In this case, the bytes are simply stored as 59 is, eight bits per byte, with none of the above coding. The bytes are 60 preceded by a count, since there is no longer an EOB code. 61 62 If the data is compressible, then either the fixed or dynamic methods 63 are used. In the dynamic method, the compressed data is preceded by 64 an encoding of the literal/length and distance Huffman codes that are 65 to be used to decode this block. The representation is itself Huffman 66 coded, and so is preceded by a description of that code. These code 67 descriptions take up a little space, and so for small blocks, there is 68 a predefined set of codes, called the fixed codes. The fixed method is 69 used if the block codes up smaller that way (usually for quite small 70 chunks), otherwise the dynamic method is used. In the latter case, the 71 codes are customized to the probabilities in the current block, and so 72 can code it much better than the pre-determined fixed codes. 73 74 The Huffman codes themselves are decoded using a mutli-level table 75 lookup, in order to maximize the speed of decoding plus the speed of 76 building the decoding tables. See the comments below that precede the 77 lbits and dbits tuning parameters. 78 */ 79 80 81 /* 82 Notes beyond the 1.93a appnote.txt: 83 84 1. Distance pointers never point before the beginning of the output 85 stream. 86 2. Distance pointers can point back across blocks, up to 32k away. 87 3. There is an implied maximum of 7 bits for the bit length table and 88 15 bits for the actual data. 89 4. If only one code exists, then it is encoded using one bit. (Zero 90 would be more efficient, but perhaps a little confusing.) If two 91 codes exist, they are coded using one bit each (0 and 1). 92 5. There is no way of sending zero distance codes--a dummy must be 93 sent if there are none. (History: a pre 2.0 version of PKZIP would 94 store blocks with no distance codes, but this was discovered to be 95 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 96 zero distance codes, which is sent as one code of zero bits in 97 length. 98 6. There are up to 286 literal/length codes. Code 256 represents the 99 end-of-block. Note however that the static length tree defines 100 288 codes just to fill out the Huffman codes. Codes 286 and 287 101 cannot be used though, since there is no length base or extra bits 102 defined for them. Similarly, there are up to 30 distance codes. 103 However, static trees define 32 codes (all 5 bits) to fill out the 104 Huffman codes, but the last two had better not show up in the data. 105 7. Unzip can check dynamic Huffman blocks for complete code sets. 106 The exception is that a single code would not be complete (see #4). 107 8. The five bits following the block type is really the number of 108 literal codes sent minus 257. 109 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 110 (1+6+6). Therefore, to output three times the length, you output 111 three codes (1+1+1), whereas to output four times the same length, 112 you only need two codes (1+3). Hmm. 113 10. In the tree reconstruction algorithm, Code = Code + Increment 114 only if BitLength(i) is not zero. (Pretty obvious.) 115 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 116 12. Note: length code 284 can represent 227-258, but length code 285 117 really is 258. The last length deserves its own, short code 118 since it gets used a lot in very redundant files. The length 119 258 is special since 258 - 3 (the min match length) is 255. 120 13. The literal/length and distance code bit lengths are read as a 121 single stream of lengths. It is possible (and advantageous) for 122 a repeat code (16, 17, or 18) to go across the boundary between 123 the two sets of lengths. 124 */ 125 126 #ifndef NO_DECOMPRESSION 127 128 #include "shared.h" 129 130 #include "filesys.h" 131 132 /* so we can disable decompression */ 133 int no_decompression = 0; 134 135 /* used to tell if "read" should be redirected to "gunzip_read" */ 136 int compressed_file; 137 138 /* internal variables only */ 139 static int gzip_data_offset; 140 static int gzip_filepos; 141 static int gzip_filemax; 142 static int gzip_fsmax; 143 static int saved_filepos; 144 static unsigned long gzip_crc; 145 146 static unsigned long crc; 147 148 149 /* internal extra variables for use of inflate code */ 150 static int block_type; 151 static int block_len; 152 static int last_block; 153 static int code_state; 154 155 156 /* Function prototypes */ 157 static void initialize_tables (void); 158 static unsigned long updcrc(unsigned char *, unsigned); 159 160 /* 161 * Linear allocator. 162 */ 163 164 static unsigned long linalloc_topaddr; 165 166 static void * 167 linalloc (int size) 168 { 169 linalloc_topaddr = (linalloc_topaddr - size) & ~3; 170 return (void *) linalloc_topaddr; 171 } 172 173 static void 174 reset_linalloc (void) 175 { 176 linalloc_topaddr = RAW_ADDR ((mbi.mem_upper << 10) + 0x100000); 177 linalloc_topaddr -= ZFS_SCRATCH_SIZE; 178 } 179 180 181 /* internal variable swap function */ 182 static void 183 gunzip_swap_values (void) 184 { 185 register int itmp; 186 187 /* swap filepos */ 188 itmp = filepos; 189 filepos = gzip_filepos; 190 gzip_filepos = itmp; 191 192 /* swap filemax */ 193 itmp = filemax; 194 filemax = gzip_filemax; 195 gzip_filemax = itmp; 196 197 /* swap fsmax */ 198 itmp = fsmax; 199 fsmax = gzip_fsmax; 200 gzip_fsmax = itmp; 201 } 202 203 204 /* internal function for eating variable-length header fields */ 205 static int 206 bad_field (int len) 207 { 208 char ch = 1; 209 int not_retval = 1; 210 211 do 212 { 213 if (len >= 0) 214 { 215 if (!(len--)) 216 break; 217 } 218 else 219 { 220 if (!ch) 221 break; 222 } 223 } 224 while ((not_retval = grub_read (&ch, 1)) == 1); 225 226 return (!not_retval); 227 } 228 229 230 /* Little-Endian defines for the 2-byte magic number for gzip files */ 231 #define GZIP_HDR_LE 0x8B1F 232 #define OLD_GZIP_HDR_LE 0x9E1F 233 234 /* Compression methods (see algorithm.doc) */ 235 #define STORED 0 236 #define COMPRESSED 1 237 #define PACKED 2 238 #define LZHED 3 239 /* methods 4 to 7 reserved */ 240 #define DEFLATED 8 241 #define MAX_METHODS 9 242 243 /* gzip flag byte */ 244 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */ 245 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */ 246 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */ 247 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */ 248 #define COMMENT 0x10 /* bit 4 set: file comment present */ 249 #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */ 250 #define RESERVED 0xC0 /* bit 6,7: reserved */ 251 252 #define UNSUPP_FLAGS (CONTINUATION|ENCRYPTED|RESERVED) 253 254 /* inflate block codes */ 255 #define INFLATE_STORED 0 256 #define INFLATE_FIXED 1 257 #define INFLATE_DYNAMIC 2 258 259 typedef unsigned char uch; 260 typedef unsigned short ush; 261 typedef unsigned long ulg; 262 263 /* 264 * Window Size 265 * 266 * This must be a power of two, and at least 32K for zip's deflate method 267 */ 268 269 #define WSIZE 0x8000 270 271 272 int 273 gunzip_test_header (void) 274 { 275 unsigned char buf[10]; 276 277 /* "compressed_file" is already reset to zero by this point */ 278 279 /* 280 * This checks if the file is gzipped. If a problem occurs here 281 * (other than a real error with the disk) then we don't think it 282 * is a compressed file, and simply mark it as such. 283 */ 284 if (no_decompression 285 || grub_read (buf, 10) != 10 286 || ((*((unsigned short *) buf) != GZIP_HDR_LE) 287 && (*((unsigned short *) buf) != OLD_GZIP_HDR_LE))) 288 { 289 filepos = 0; 290 return ! errnum; 291 } 292 293 /* 294 * This does consistency checking on the header data. If a 295 * problem occurs from here on, then we have corrupt or otherwise 296 * bad data, and the error should be reported to the user. 297 */ 298 if (buf[2] != DEFLATED 299 || (buf[3] & UNSUPP_FLAGS) 300 || ((buf[3] & EXTRA_FIELD) 301 && (grub_read (buf, 2) != 2 302 || bad_field (*((unsigned short *) buf)))) 303 || ((buf[3] & ORIG_NAME) && bad_field (-1)) 304 || ((buf[3] & COMMENT) && bad_field (-1))) 305 { 306 if (! errnum) 307 errnum = ERR_BAD_GZIP_HEADER; 308 309 return 0; 310 } 311 312 gzip_data_offset = filepos; 313 314 /* We could read the last 8 bytes of the file to get the uncompressed 315 * size. Doing so under tftp would cause the file to be downloaded 316 * twice, which can be problem with large files. So we set it to 317 * MAXINT and correct it later when we get to the end of the file 318 * in get_byte(). 319 */ 320 gzip_fsmax = gzip_filemax = MAXINT; 321 322 initialize_tables (); 323 324 compressed_file = 1; 325 gunzip_swap_values (); 326 /* 327 * Now "gzip_*" values refer to the compressed data. 328 */ 329 330 filepos = 0; 331 332 crc = (ulg)0xffffffffUL; 333 334 return 1; 335 } 336 337 338 /* Huffman code lookup table entry--this entry is four bytes for machines 339 that have 16-bit pointers (e.g. PC's in the small or medium model). 340 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 341 means that v is a literal, 16 < e < 32 means that v is a pointer to 342 the next table, which codes e - 16 bits, and lastly e == 99 indicates 343 an unused code. If a code with e == 99 is looked up, this implies an 344 error in the data. */ 345 struct huft 346 { 347 uch e; /* number of extra bits or operation */ 348 uch b; /* number of bits in this code or subcode */ 349 union 350 { 351 ush n; /* literal, length base, or distance base */ 352 struct huft *t; /* pointer to next level of table */ 353 } 354 v; 355 }; 356 357 358 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed 359 stream to find repeated byte strings. This is implemented here as a 360 circular buffer. The index is updated simply by incrementing and then 361 and'ing with 0x7fff (32K-1). */ 362 /* It is left to other modules to supply the 32K area. It is assumed 363 to be usable as if it were declared "uch slide[32768];" or as just 364 "uch *slide;" and then malloc'ed in the latter case. The definition 365 must be in unzip.h, included above. */ 366 367 368 /* sliding window in uncompressed data */ 369 static uch slide[WSIZE]; 370 371 /* current position in slide */ 372 static unsigned wp; 373 374 375 /* Tables for deflate from PKZIP's appnote.txt. */ 376 static unsigned bitorder[] = 377 { /* Order of the bit length code lengths */ 378 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 379 static ush cplens[] = 380 { /* Copy lengths for literal codes 257..285 */ 381 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 382 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 383 /* note: see note #13 above about the 258 in this list. */ 384 static ush cplext[] = 385 { /* Extra bits for literal codes 257..285 */ 386 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 387 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 388 static ush cpdist[] = 389 { /* Copy offsets for distance codes 0..29 */ 390 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 391 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 392 8193, 12289, 16385, 24577}; 393 static ush cpdext[] = 394 { /* Extra bits for distance codes */ 395 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 396 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 397 12, 12, 13, 13}; 398 399 400 /* 401 Huffman code decoding is performed using a multi-level table lookup. 402 The fastest way to decode is to simply build a lookup table whose 403 size is determined by the longest code. However, the time it takes 404 to build this table can also be a factor if the data being decoded 405 is not very long. The most common codes are necessarily the 406 shortest codes, so those codes dominate the decoding time, and hence 407 the speed. The idea is you can have a shorter table that decodes the 408 shorter, more probable codes, and then point to subsidiary tables for 409 the longer codes. The time it costs to decode the longer codes is 410 then traded against the time it takes to make longer tables. 411 412 This results of this trade are in the variables lbits and dbits 413 below. lbits is the number of bits the first level table for literal/ 414 length codes can decode in one step, and dbits is the same thing for 415 the distance codes. Subsequent tables are also less than or equal to 416 those sizes. These values may be adjusted either when all of the 417 codes are shorter than that, in which case the longest code length in 418 bits is used, or when the shortest code is *longer* than the requested 419 table size, in which case the length of the shortest code in bits is 420 used. 421 422 There are two different values for the two tables, since they code a 423 different number of possibilities each. The literal/length table 424 codes 286 possible values, or in a flat code, a little over eight 425 bits. The distance table codes 30 possible values, or a little less 426 than five bits, flat. The optimum values for speed end up being 427 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 428 The optimum values may differ though from machine to machine, and 429 possibly even between compilers. Your mileage may vary. 430 */ 431 432 433 static int lbits = 9; /* bits in base literal/length lookup table */ 434 static int dbits = 6; /* bits in base distance lookup table */ 435 436 437 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 438 #define BMAX 16 /* maximum bit length of any code (16 for explode) */ 439 #define N_MAX 288 /* maximum number of codes in any set */ 440 441 442 static unsigned hufts; /* track memory usage */ 443 444 445 /* Macros for inflate() bit peeking and grabbing. 446 The usage is: 447 448 NEEDBITS(j) 449 x = b & mask_bits[j]; 450 DUMPBITS(j) 451 452 where NEEDBITS makes sure that b has at least j bits in it, and 453 DUMPBITS removes the bits from b. The macros use the variable k 454 for the number of bits in b. Normally, b and k are register 455 variables for speed, and are initialized at the beginning of a 456 routine that uses these macros from a global bit buffer and count. 457 458 If we assume that EOB will be the longest code, then we will never 459 ask for bits with NEEDBITS that are beyond the end of the stream. 460 So, NEEDBITS should not read any more bytes than are needed to 461 meet the request. Then no bytes need to be "returned" to the buffer 462 at the end of the last block. 463 464 However, this assumption is not true for fixed blocks--the EOB code 465 is 7 bits, but the other literal/length codes can be 8 or 9 bits. 466 (The EOB code is shorter than other codes because fixed blocks are 467 generally short. So, while a block always has an EOB, many other 468 literal/length codes have a significantly lower probability of 469 showing up at all.) However, by making the first table have a 470 lookup of seven bits, the EOB code will be found in that first 471 lookup, and so will not require that too many bits be pulled from 472 the stream. 473 */ 474 475 static ulg bb; /* bit buffer */ 476 static unsigned bk; /* bits in bit buffer */ 477 478 static ush mask_bits[] = 479 { 480 0x0000, 481 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 482 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 483 }; 484 485 #define NEEDBITS(n) do {while(k<(n)){b|=((ulg)get_byte())<<k;k+=8;}} while (0) 486 #define DUMPBITS(n) do {b>>=(n);k-=(n);} while (0) 487 488 #define INBUFSIZ 0x2000 489 490 static uch inbuf[INBUFSIZ]; 491 static int bufloc; 492 static uch endbuf[8]; 493 494 static int 495 get_byte (void) 496 { 497 if (filepos == gzip_data_offset || bufloc == INBUFSIZ) 498 { 499 int pos; 500 int old_filepos = filepos; 501 bufloc = 0; 502 grub_read (inbuf, INBUFSIZ); 503 /* If there are 8 bytes or less left, we have read in all the 504 * the file content. So get the last 8 bytes and get the crc 505 * and uncompressed size. This is important for the loop in 506 * gunzip_read() to terminate properly. 507 */ 508 if (filepos >= filemax - 8) { 509 uch *eb = endbuf; 510 for (pos = filemax - 8; pos < filepos; pos++) 511 *eb++ = inbuf[pos - old_filepos]; 512 if (filemax > filepos) 513 grub_read(eb, filemax - filepos); 514 gzip_crc = *((unsigned long *) endbuf); 515 gzip_filemax = *((unsigned long *) (endbuf + 4)); 516 } 517 } 518 519 return inbuf[bufloc++]; 520 } 521 522 /* decompression global pointers */ 523 static struct huft *tl; /* literal/length code table */ 524 static struct huft *td; /* distance code table */ 525 static int bl; /* lookup bits for tl */ 526 static int bd; /* lookup bits for td */ 527 528 529 /* more function prototypes */ 530 static int huft_build (unsigned *, unsigned, unsigned, ush *, ush *, 531 struct huft **, int *); 532 static int inflate_codes_in_window (void); 533 534 535 /* Given a list of code lengths and a maximum table size, make a set of 536 tables to decode that set of codes. Return zero on success, one if 537 the given code set is incomplete (the tables are still built in this 538 case), two if the input is invalid (all zero length codes or an 539 oversubscribed set of lengths), and three if not enough memory. */ 540 541 static int 542 huft_build (unsigned *b, /* code lengths in bits (all assumed <= BMAX) */ 543 unsigned n, /* number of codes (assumed <= N_MAX) */ 544 unsigned s, /* number of simple-valued codes (0..s-1) */ 545 ush * d, /* list of base values for non-simple codes */ 546 ush * e, /* list of extra bits for non-simple codes */ 547 struct huft **t, /* result: starting table */ 548 int *m) /* maximum lookup bits, returns actual */ 549 { 550 unsigned a; /* counter for codes of length k */ 551 unsigned c[BMAX + 1]; /* bit length count table */ 552 unsigned f; /* i repeats in table every f entries */ 553 int g; /* maximum code length */ 554 int h; /* table level */ 555 register unsigned i; /* counter, current code */ 556 register unsigned j; /* counter */ 557 register int k; /* number of bits in current code */ 558 int l; /* bits per table (returned in m) */ 559 register unsigned *p; /* pointer into c[], b[], or v[] */ 560 register struct huft *q; /* points to current table */ 561 struct huft r; /* table entry for structure assignment */ 562 struct huft *u[BMAX]; /* table stack */ 563 unsigned v[N_MAX]; /* values in order of bit length */ 564 register int w; /* bits before this table == (l * h) */ 565 unsigned x[BMAX + 1]; /* bit offsets, then code stack */ 566 unsigned *xp; /* pointer into x */ 567 int y; /* number of dummy codes added */ 568 unsigned z; /* number of entries in current table */ 569 570 /* Generate counts for each bit length */ 571 memset ((char *) c, 0, sizeof (c)); 572 p = b; 573 i = n; 574 do 575 { 576 c[*p]++; /* assume all entries <= BMAX */ 577 p++; /* Can't combine with above line (Solaris bug) */ 578 } 579 while (--i); 580 if (c[0] == n) /* null input--all zero length codes */ 581 { 582 *t = (struct huft *) NULL; 583 *m = 0; 584 return 0; 585 } 586 587 /* Find minimum and maximum length, bound *m by those */ 588 l = *m; 589 for (j = 1; j <= BMAX; j++) 590 if (c[j]) 591 break; 592 k = j; /* minimum code length */ 593 if ((unsigned) l < j) 594 l = j; 595 for (i = BMAX; i; i--) 596 if (c[i]) 597 break; 598 g = i; /* maximum code length */ 599 if ((unsigned) l > i) 600 l = i; 601 *m = l; 602 603 /* Adjust last length count to fill out codes, if needed */ 604 for (y = 1 << j; j < i; j++, y <<= 1) 605 if ((y -= c[j]) < 0) 606 return 2; /* bad input: more codes than bits */ 607 if ((y -= c[i]) < 0) 608 return 2; 609 c[i] += y; 610 611 /* Generate starting offsets into the value table for each length */ 612 x[1] = j = 0; 613 p = c + 1; 614 xp = x + 2; 615 while (--i) 616 { /* note that i == g from above */ 617 *xp++ = (j += *p++); 618 } 619 620 /* Make a table of values in order of bit lengths */ 621 p = b; 622 i = 0; 623 do 624 { 625 if ((j = *p++) != 0) 626 v[x[j]++] = i; 627 } 628 while (++i < n); 629 630 /* Generate the Huffman codes and for each, make the table entries */ 631 x[0] = i = 0; /* first Huffman code is zero */ 632 p = v; /* grab values in bit order */ 633 h = -1; /* no tables yet--level -1 */ 634 w = -l; /* bits decoded == (l * h) */ 635 u[0] = (struct huft *) NULL; /* just to keep compilers happy */ 636 q = (struct huft *) NULL; /* ditto */ 637 z = 0; /* ditto */ 638 639 /* go through the bit lengths (k already is bits in shortest code) */ 640 for (; k <= g; k++) 641 { 642 a = c[k]; 643 while (a--) 644 { 645 /* here i is the Huffman code of length k bits for value *p */ 646 /* make tables up to required level */ 647 while (k > w + l) 648 { 649 h++; 650 w += l; /* previous table always l bits */ 651 652 /* compute minimum size table less than or equal to l bits */ 653 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */ 654 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 655 { /* too few codes for k-w bit table */ 656 f -= a + 1; /* deduct codes from patterns left */ 657 xp = c + k; 658 while (++j < z) /* try smaller tables up to z bits */ 659 { 660 if ((f <<= 1) <= *++xp) 661 break; /* enough codes to use up j bits */ 662 f -= *xp; /* else deduct codes from patterns */ 663 } 664 } 665 z = 1 << j; /* table entries for j-bit table */ 666 667 /* allocate and link in new table */ 668 q = (struct huft *) linalloc ((z + 1) * sizeof (struct huft)); 669 670 hufts += z + 1; /* track memory usage */ 671 *t = q + 1; /* link to list for huft_free() */ 672 *(t = &(q->v.t)) = (struct huft *) NULL; 673 u[h] = ++q; /* table starts after link */ 674 675 /* connect to last table, if there is one */ 676 if (h) 677 { 678 x[h] = i; /* save pattern for backing up */ 679 r.b = (uch) l; /* bits to dump before this table */ 680 r.e = (uch) (16 + j); /* bits in this table */ 681 r.v.t = q; /* pointer to this table */ 682 j = i >> (w - l); /* (get around Turbo C bug) */ 683 u[h - 1][j] = r; /* connect to last table */ 684 } 685 } 686 687 /* set up table entry in r */ 688 r.b = (uch) (k - w); 689 if (p >= v + n) 690 r.e = 99; /* out of values--invalid code */ 691 else if (*p < s) 692 { 693 r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 694 r.v.n = (ush) (*p); /* simple code is just the value */ 695 p++; /* one compiler does not like *p++ */ 696 } 697 else 698 { 699 r.e = (uch) e[*p - s]; /* non-simple--look up in lists */ 700 r.v.n = d[*p++ - s]; 701 } 702 703 /* fill code-like entries with r */ 704 f = 1 << (k - w); 705 for (j = i >> w; j < z; j += f) 706 q[j] = r; 707 708 /* backwards increment the k-bit code i */ 709 for (j = 1 << (k - 1); i & j; j >>= 1) 710 i ^= j; 711 i ^= j; 712 713 /* backup over finished tables */ 714 while ((i & ((1 << w) - 1)) != x[h]) 715 { 716 h--; /* don't need to update q */ 717 w -= l; 718 } 719 } 720 } 721 722 /* Return true (1) if we were given an incomplete table */ 723 return y != 0 && g != 1; 724 } 725 726 727 /* 728 * inflate (decompress) the codes in a deflated (compressed) block. 729 * Return an error code or zero if it all goes ok. 730 */ 731 732 static unsigned inflate_n, inflate_d; 733 734 static int 735 inflate_codes_in_window (void) 736 { 737 register unsigned e; /* table entry flag/number of extra bits */ 738 unsigned n, d; /* length and index for copy */ 739 unsigned w; /* current window position */ 740 struct huft *t; /* pointer to table entry */ 741 unsigned ml, md; /* masks for bl and bd bits */ 742 register ulg b; /* bit buffer */ 743 register unsigned k; /* number of bits in bit buffer */ 744 745 /* make local copies of globals */ 746 d = inflate_d; 747 n = inflate_n; 748 b = bb; /* initialize bit buffer */ 749 k = bk; 750 w = wp; /* initialize window position */ 751 752 /* inflate the coded data */ 753 ml = mask_bits[bl]; /* precompute masks for speed */ 754 md = mask_bits[bd]; 755 for (;;) /* do until end of block */ 756 { 757 if (!code_state) 758 { 759 NEEDBITS ((unsigned) bl); 760 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16) 761 do 762 { 763 if (e == 99) 764 { 765 errnum = ERR_BAD_GZIP_DATA; 766 return 0; 767 } 768 DUMPBITS (t->b); 769 e -= 16; 770 NEEDBITS (e); 771 } 772 while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16); 773 DUMPBITS (t->b); 774 775 if (e == 16) /* then it's a literal */ 776 { 777 slide[w++] = (uch) t->v.n; 778 if (w == WSIZE) 779 break; 780 } 781 else 782 /* it's an EOB or a length */ 783 { 784 /* exit if end of block */ 785 if (e == 15) 786 { 787 block_len = 0; 788 break; 789 } 790 791 /* get length of block to copy */ 792 NEEDBITS (e); 793 n = t->v.n + ((unsigned) b & mask_bits[e]); 794 DUMPBITS (e); 795 796 /* decode distance of block to copy */ 797 NEEDBITS ((unsigned) bd); 798 if ((e = (t = td + ((unsigned) b & md))->e) > 16) 799 do 800 { 801 if (e == 99) 802 { 803 errnum = ERR_BAD_GZIP_DATA; 804 return 0; 805 } 806 DUMPBITS (t->b); 807 e -= 16; 808 NEEDBITS (e); 809 } 810 while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) 811 > 16); 812 DUMPBITS (t->b); 813 NEEDBITS (e); 814 d = w - t->v.n - ((unsigned) b & mask_bits[e]); 815 DUMPBITS (e); 816 code_state++; 817 } 818 } 819 820 if (code_state) 821 { 822 /* do the copy */ 823 do 824 { 825 n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n 826 : e); 827 if (w - d >= e) 828 { 829 memmove (slide + w, slide + d, e); 830 w += e; 831 d += e; 832 } 833 else 834 /* purposefully use the overlap for extra copies here!! */ 835 { 836 while (e--) 837 slide[w++] = slide[d++]; 838 } 839 if (w == WSIZE) 840 break; 841 } 842 while (n); 843 844 if (!n) 845 code_state--; 846 847 /* did we break from the loop too soon? */ 848 if (w == WSIZE) 849 break; 850 } 851 } 852 853 /* restore the globals from the locals */ 854 inflate_d = d; 855 inflate_n = n; 856 wp = w; /* restore global window pointer */ 857 bb = b; /* restore global bit buffer */ 858 bk = k; 859 860 return !block_len; 861 } 862 863 864 /* get header for an inflated type 0 (stored) block. */ 865 866 static void 867 init_stored_block (void) 868 { 869 register ulg b; /* bit buffer */ 870 register unsigned k; /* number of bits in bit buffer */ 871 872 /* make local copies of globals */ 873 b = bb; /* initialize bit buffer */ 874 k = bk; 875 876 /* go to byte boundary */ 877 DUMPBITS (k & 7); 878 879 /* get the length and its complement */ 880 NEEDBITS (16); 881 block_len = ((unsigned) b & 0xffff); 882 DUMPBITS (16); 883 NEEDBITS (16); 884 if (block_len != (unsigned) ((~b) & 0xffff)) 885 errnum = ERR_BAD_GZIP_DATA; 886 DUMPBITS (16); 887 888 /* restore global variables */ 889 bb = b; 890 bk = k; 891 } 892 893 894 /* get header for an inflated type 1 (fixed Huffman codes) block. We should 895 either replace this with a custom decoder, or at least precompute the 896 Huffman tables. */ 897 898 static void 899 init_fixed_block () 900 { 901 int i; /* temporary variable */ 902 unsigned l[288]; /* length list for huft_build */ 903 904 /* set up literal table */ 905 for (i = 0; i < 144; i++) 906 l[i] = 8; 907 for (; i < 256; i++) 908 l[i] = 9; 909 for (; i < 280; i++) 910 l[i] = 7; 911 for (; i < 288; i++) /* make a complete, but wrong code set */ 912 l[i] = 8; 913 bl = 7; 914 if ((i = huft_build (l, 288, 257, cplens, cplext, &tl, &bl)) != 0) 915 { 916 errnum = ERR_BAD_GZIP_DATA; 917 return; 918 } 919 920 /* set up distance table */ 921 for (i = 0; i < 30; i++) /* make an incomplete code set */ 922 l[i] = 5; 923 bd = 5; 924 if ((i = huft_build (l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) 925 { 926 errnum = ERR_BAD_GZIP_DATA; 927 return; 928 } 929 930 /* indicate we're now working on a block */ 931 code_state = 0; 932 block_len++; 933 } 934 935 936 /* get header for an inflated type 2 (dynamic Huffman codes) block. */ 937 938 static void 939 init_dynamic_block (void) 940 { 941 int i; /* temporary variables */ 942 unsigned j; 943 unsigned l; /* last length */ 944 unsigned m; /* mask for bit lengths table */ 945 unsigned n; /* number of lengths to get */ 946 unsigned nb; /* number of bit length codes */ 947 unsigned nl; /* number of literal/length codes */ 948 unsigned nd; /* number of distance codes */ 949 unsigned ll[286 + 30]; /* literal/length and distance code lengths */ 950 register ulg b; /* bit buffer */ 951 register unsigned k; /* number of bits in bit buffer */ 952 953 /* make local bit buffer */ 954 b = bb; 955 k = bk; 956 957 /* read in table lengths */ 958 NEEDBITS (5); 959 nl = 257 + ((unsigned) b & 0x1f); /* number of literal/length codes */ 960 DUMPBITS (5); 961 NEEDBITS (5); 962 nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */ 963 DUMPBITS (5); 964 NEEDBITS (4); 965 nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */ 966 DUMPBITS (4); 967 if (nl > 286 || nd > 30) 968 { 969 errnum = ERR_BAD_GZIP_DATA; 970 return; 971 } 972 973 /* read in bit-length-code lengths */ 974 for (j = 0; j < nb; j++) 975 { 976 NEEDBITS (3); 977 ll[bitorder[j]] = (unsigned) b & 7; 978 DUMPBITS (3); 979 } 980 for (; j < 19; j++) 981 ll[bitorder[j]] = 0; 982 983 /* build decoding table for trees--single level, 7 bit lookup */ 984 bl = 7; 985 if ((i = huft_build (ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) 986 { 987 errnum = ERR_BAD_GZIP_DATA; 988 return; 989 } 990 991 /* read in literal and distance code lengths */ 992 n = nl + nd; 993 m = mask_bits[bl]; 994 i = l = 0; 995 while ((unsigned) i < n) 996 { 997 NEEDBITS ((unsigned) bl); 998 j = (td = tl + ((unsigned) b & m))->b; 999 DUMPBITS (j); 1000 j = td->v.n; 1001 if (j < 16) /* length of code in bits (0..15) */ 1002 ll[i++] = l = j; /* save last length in l */ 1003 else if (j == 16) /* repeat last length 3 to 6 times */ 1004 { 1005 NEEDBITS (2); 1006 j = 3 + ((unsigned) b & 3); 1007 DUMPBITS (2); 1008 if ((unsigned) i + j > n) 1009 { 1010 errnum = ERR_BAD_GZIP_DATA; 1011 return; 1012 } 1013 while (j--) 1014 ll[i++] = l; 1015 } 1016 else if (j == 17) /* 3 to 10 zero length codes */ 1017 { 1018 NEEDBITS (3); 1019 j = 3 + ((unsigned) b & 7); 1020 DUMPBITS (3); 1021 if ((unsigned) i + j > n) 1022 { 1023 errnum = ERR_BAD_GZIP_DATA; 1024 return; 1025 } 1026 while (j--) 1027 ll[i++] = 0; 1028 l = 0; 1029 } 1030 else 1031 /* j == 18: 11 to 138 zero length codes */ 1032 { 1033 NEEDBITS (7); 1034 j = 11 + ((unsigned) b & 0x7f); 1035 DUMPBITS (7); 1036 if ((unsigned) i + j > n) 1037 { 1038 errnum = ERR_BAD_GZIP_DATA; 1039 return; 1040 } 1041 while (j--) 1042 ll[i++] = 0; 1043 l = 0; 1044 } 1045 } 1046 1047 /* free decoding table for trees */ 1048 reset_linalloc (); 1049 1050 /* restore the global bit buffer */ 1051 bb = b; 1052 bk = k; 1053 1054 /* build the decoding tables for literal/length and distance codes */ 1055 bl = lbits; 1056 if ((i = huft_build (ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) 1057 { 1058 #if 0 1059 if (i == 1) 1060 printf ("gunzip: incomplete literal tree\n"); 1061 #endif 1062 1063 errnum = ERR_BAD_GZIP_DATA; 1064 return; 1065 } 1066 bd = dbits; 1067 if ((i = huft_build (ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) 1068 { 1069 #if 0 1070 if (i == 1) 1071 printf ("gunzip: incomplete distance tree\n"); 1072 #endif 1073 1074 errnum = ERR_BAD_GZIP_DATA; 1075 return; 1076 } 1077 1078 /* indicate we're now working on a block */ 1079 code_state = 0; 1080 block_len++; 1081 } 1082 1083 1084 static void 1085 get_new_block (void) 1086 { 1087 register ulg b; /* bit buffer */ 1088 register unsigned k; /* number of bits in bit buffer */ 1089 1090 hufts = 0; 1091 1092 /* make local bit buffer */ 1093 b = bb; 1094 k = bk; 1095 1096 /* read in last block bit */ 1097 NEEDBITS (1); 1098 last_block = (int) b & 1; 1099 DUMPBITS (1); 1100 1101 /* read in block type */ 1102 NEEDBITS (2); 1103 block_type = (unsigned) b & 3; 1104 DUMPBITS (2); 1105 1106 /* restore the global bit buffer */ 1107 bb = b; 1108 bk = k; 1109 1110 if (block_type == INFLATE_STORED) 1111 init_stored_block (); 1112 if (block_type == INFLATE_FIXED) 1113 init_fixed_block (); 1114 if (block_type == INFLATE_DYNAMIC) 1115 init_dynamic_block (); 1116 } 1117 1118 1119 static void 1120 inflate_window (void) 1121 { 1122 /* initialize window */ 1123 wp = 0; 1124 1125 /* 1126 * Main decompression loop. 1127 */ 1128 1129 while (wp < WSIZE && !errnum) 1130 { 1131 if (!block_len) 1132 { 1133 if (last_block) 1134 break; 1135 1136 get_new_block (); 1137 } 1138 1139 if (block_type > INFLATE_DYNAMIC) 1140 errnum = ERR_BAD_GZIP_DATA; 1141 1142 if (errnum) 1143 return; 1144 1145 /* 1146 * Expand stored block here. 1147 */ 1148 if (block_type == INFLATE_STORED) 1149 { 1150 int w = wp; 1151 1152 /* 1153 * This is basically a glorified pass-through 1154 */ 1155 1156 while (block_len && w < WSIZE && !errnum) 1157 { 1158 slide[w++] = get_byte (); 1159 block_len--; 1160 } 1161 1162 wp = w; 1163 1164 continue; 1165 } 1166 1167 /* 1168 * Expand other kind of block. 1169 */ 1170 1171 if (inflate_codes_in_window ()) 1172 reset_linalloc (); 1173 } 1174 1175 saved_filepos += WSIZE; 1176 } 1177 1178 1179 static void 1180 initialize_tables (void) 1181 { 1182 saved_filepos = 0; 1183 filepos = gzip_data_offset; 1184 1185 /* initialize window, bit buffer */ 1186 bk = 0; 1187 bb = 0; 1188 1189 /* reset partial decompression code */ 1190 last_block = 0; 1191 block_len = 0; 1192 1193 /* reset memory allocation stuff */ 1194 reset_linalloc (); 1195 } 1196 1197 1198 int 1199 gunzip_read (char *buf, int len) 1200 { 1201 int ret = 0; 1202 int check_crc; 1203 ulg crc_value = 0xffffffffUL; 1204 1205 compressed_file = 0; 1206 gunzip_swap_values (); 1207 /* 1208 * Now "gzip_*" values refer to the uncompressed data. 1209 */ 1210 1211 /* do we reset decompression to the beginning of the file? */ 1212 if (saved_filepos > gzip_filepos + WSIZE) 1213 initialize_tables (); 1214 1215 /* perform CRC check only if reading the entire file */ 1216 check_crc = (saved_filepos == 0 && len == MAXINT); 1217 1218 /* 1219 * This loop operates upon uncompressed data only. The only 1220 * special thing it does is to make sure the decompression 1221 * window is within the range of data it needs. 1222 */ 1223 1224 while (len > 0 && !errnum) 1225 { 1226 register int size; 1227 register char *srcaddr; 1228 1229 while (gzip_filepos >= saved_filepos && !errnum) 1230 inflate_window (); 1231 1232 if (errnum) 1233 break; 1234 1235 /* We could have started with an unknown gzip_filemax (MAXINT) 1236 * which has been updated in get_byte(). If so, update len 1237 * to avoid reading beyond the end. 1238 */ 1239 if (len > (gzip_filemax - gzip_filepos)) { 1240 len = gzip_filemax - gzip_filepos; 1241 if (len < 0) { 1242 errnum = ERR_BAD_GZIP_DATA; 1243 break; 1244 } 1245 } 1246 1247 srcaddr = (char *) ((gzip_filepos & (WSIZE - 1)) + slide); 1248 size = saved_filepos - gzip_filepos; 1249 if (size > len) 1250 size = len; 1251 1252 memmove (buf, srcaddr, size); 1253 1254 /* do CRC calculation here! */ 1255 crc_value = updcrc(buf, (unsigned)size); 1256 1257 buf += size; 1258 len -= size; 1259 gzip_filepos += size; 1260 ret += size; 1261 } 1262 1263 /* check for CRC error if reading entire file */ 1264 if (!errnum && check_crc && gzip_crc != crc_value) { 1265 #if 0 1266 printf ("gunzip: crc value 0x%x, expected 0x%x\n", crc_value, gzip_crc); 1267 #endif 1268 errnum = ERR_BAD_GZIP_CRC; 1269 } 1270 1271 compressed_file = 1; 1272 gunzip_swap_values (); 1273 /* 1274 * Now "gzip_*" values refer to the compressed data. 1275 */ 1276 1277 if (errnum) 1278 ret = 0; 1279 1280 return ret; 1281 } 1282 1283 /* The crc_23_tab and updcrc() are adapted from gzip 1.3.3 */ 1284 1285 /* ======================================================================== 1286 * Table of CRC-32's of all single-byte values (made by makecrc.c) 1287 */ 1288 static ulg crc_32_tab[] = { 1289 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, 1290 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, 1291 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 1292 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL, 1293 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L, 1294 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L, 1295 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, 1296 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL, 1297 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L, 1298 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL, 1299 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 1300 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L, 1301 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L, 1302 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL, 1303 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, 1304 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L, 1305 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL, 1306 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L, 1307 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, 1308 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L, 1309 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL, 1310 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L, 1311 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L, 1312 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL, 1313 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L, 1314 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L, 1315 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L, 1316 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L, 1317 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L, 1318 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL, 1319 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, 1320 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L, 1321 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L, 1322 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL, 1323 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 1324 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L, 1325 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL, 1326 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L, 1327 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, 1328 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L, 1329 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL, 1330 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, 1331 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, 1332 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL, 1333 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L, 1334 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, 1335 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 1336 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, 1337 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L, 1338 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L, 1339 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, 1340 0x2d02ef8dL 1341 }; 1342 1343 /* =========================================================================== 1344 * Run a set of bytes through the crc shift register. If s is a NULL 1345 * pointer, then initialize the crc shift register contents instead. 1346 * Return the current crc in either case. 1347 */ 1348 static ulg updcrc(s, n) 1349 uch *s; /* pointer to bytes to pump through */ 1350 unsigned n; /* number of bytes in s[] */ 1351 { 1352 register ulg c; /* temporary variable */ 1353 1354 c = crc; 1355 if (n) do { 1356 c = crc_32_tab[((int)c ^ (*s++)) & 0xff] ^ (c >> 8); 1357 } while (--n); 1358 crc = c; 1359 return c ^ 0xffffffffL; /* (instead of ~c for 64-bit machines) */ 1360 } 1361 1362 #endif /* ! NO_DECOMPRESSION */ 1363