imgact_gzip.c revision 3348
1/* 2 * Parts of this file are not covered by: 3 * ---------------------------------------------------------------------------- 4 * "THE BEER-WARE LICENSE" (Revision 42): 5 * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 6 * can do whatever you want with this stuff. If we meet some day, and you think 7 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 8 * ---------------------------------------------------------------------------- 9 * 10 * $Id: imgact_gzip.c,v 1.2 1994/10/03 23:14:48 phk Exp $ 11 * 12 * This module handles execution of a.out files which have been run through 13 * "gzip -9". 14 * 15 * For now you need to use exactly this command to compress the binaries: 16 * 17 * gzip -9 -v < /bin/sh > /tmp/sh 18 * 19 * TODO: 20 * text-segments should be made R/O after being filled 21 * is the vm-stuff safe ? 22 * should handle the entire header of gzip'ed stuff. 23 * inflate isn't quite reentrant yet... 24 * error-handling is a mess... 25 * so is the rest... 26 */ 27 28#include <sys/param.h> 29#include <sys/systm.h> 30#include <sys/resourcevar.h> 31#include <sys/exec.h> 32#include <sys/mman.h> 33#include <sys/malloc.h> 34#include <sys/imgact.h> 35#include <sys/imgact_aout.h> 36#include <sys/kernel.h> 37#include <sys/sysent.h> 38 39#include <vm/vm.h> 40#include <vm/vm_kern.h> 41 42#define WSIZE 0x8000 43 44struct gzip { 45 struct image_params *ip; 46 struct exec a_out; 47 int error; 48 int where; 49 u_char *inbuf; 50 u_long offset; 51 u_long output; 52 u_long len; 53 int idx; 54 u_long virtual_offset, file_offset, file_end, bss_size; 55 unsigned gz_wp; 56 u_char gz_slide[WSIZE]; 57}; 58 59int inflate __P((struct gzip *)); 60 61extern struct sysentvec aout_sysvec; 62 63#define slide (gz->gz_slide) 64#define wp (gz->gz_wp) 65 66int 67exec_gzip_imgact(iparams) 68 struct image_params *iparams; 69{ 70 int error,error2=0; 71 u_char *p = (u_char *) iparams->image_header; 72 struct gzip *gz; 73 74 /* If these four are not OK, it isn't a gzip file */ 75 if (p[0] != 0x1f) return -1; /* 0 Simply magic */ 76 if (p[1] != 0x8b) return -1; /* 1 Simply magic */ 77 if (p[2] != 0x08) return -1; /* 2 Compression method */ 78 if (p[9] != 0x03) return -1; /* 9 OS compressed on */ 79 80 /* If this one contains anything but a comment or a filename 81 * marker, we don't want to chew on it 82 */ 83 if (p[3] & ~(0x18)) return ENOEXEC; /* 3 Flags */ 84 85 /* These are of no use to us */ 86 /* 4-7 Timestamp */ 87 /* 8 Extra flags */ 88 89 gz = malloc(sizeof *gz,M_TEMP,M_NOWAIT); 90 if (!gz) 91 return ENOMEM; 92 bzero(gz,sizeof *gz); /* waste of time ? */ 93 94 gz->ip = iparams; 95 gz->error = ENOEXEC; 96 gz->idx = 10; 97 98 if (p[3] & 0x08) { /* skip a filename */ 99 while (p[gz->idx++]) 100 if (gz->idx >= PAGE_SIZE) 101 goto done; 102 } 103 104 if (p[3] & 0x10) { /* skip a comment */ 105 while (p[gz->idx++]) 106 if (gz->idx >= PAGE_SIZE) 107 goto done; 108 } 109 110 gz->len = gz->ip->attr->va_size; 111 112 gz->error = 0; 113 114 error = inflate(gz); 115 116 if (gz->inbuf) { 117 error2 = 118 vm_deallocate(kernel_map, (vm_offset_t)gz->inbuf, PAGE_SIZE); 119 } 120 121 if (gz->error || error || error2) { 122 printf("Output=%lu ",gz->output); 123 printf("Inflate_error=%d gz->error=%d error2=%d where=%d\n", 124 error,gz->error,error2,gz->where); 125 if (gz->error) 126 goto done; 127 if (error) { 128 gz->error = ENOEXEC; 129 goto done; 130 } 131 if (error2) { 132 gz->error = error2; 133 goto done; 134 } 135 } 136 137 done: 138 error = gz->error; 139 free(gz,M_TEMP); 140 return error; 141} 142 143int 144do_aout_hdr(struct gzip *gz) 145{ 146 int error; 147 struct vmspace *vmspace = gz->ip->proc->p_vmspace; 148 u_long vmaddr; 149 150 /* 151 * Set file/virtual offset based on a.out variant. 152 * We do two cases: host byte order and network byte order 153 * (for NetBSD compatibility) 154 */ 155 switch ((int)(gz->a_out.a_magic & 0xffff)) { 156 case ZMAGIC: 157 gz->virtual_offset = 0; 158 if (gz->a_out.a_text) { 159 gz->file_offset = NBPG; 160 } else { 161 /* Bill's "screwball mode" */ 162 gz->file_offset = 0; 163 } 164 break; 165 case QMAGIC: 166 gz->virtual_offset = NBPG; 167 gz->file_offset = 0; 168 break; 169 default: 170 /* NetBSD compatibility */ 171 switch ((int)(ntohl(gz->a_out.a_magic) & 0xffff)) { 172 case ZMAGIC: 173 case QMAGIC: 174 gz->virtual_offset = NBPG; 175 gz->file_offset = 0; 176 break; 177 default: 178 gz->where = __LINE__; 179 return (-1); 180 } 181 } 182 183 gz->bss_size = roundup(gz->a_out.a_bss, NBPG); 184 185 /* 186 * Check various fields in header for validity/bounds. 187 */ 188 if (/* entry point must lay with text region */ 189 gz->a_out.a_entry < gz->virtual_offset || 190 gz->a_out.a_entry >= gz->virtual_offset + gz->a_out.a_text || 191 192 /* text and data size must each be page rounded */ 193 gz->a_out.a_text % NBPG || 194 gz->a_out.a_data % NBPG) { 195 gz->where = __LINE__; 196 return (-1); 197 } 198 199 /* 200 * text/data/bss must not exceed limits 201 */ 202 if (/* text can't exceed maximum text size */ 203 gz->a_out.a_text > MAXTSIZ || 204 205 /* data + bss can't exceed maximum data size */ 206 gz->a_out.a_data + gz->bss_size > MAXDSIZ || 207 208 /* data + bss can't exceed rlimit */ 209 gz->a_out.a_data + gz->bss_size > 210 gz->ip->proc->p_rlimit[RLIMIT_DATA].rlim_cur) { 211 gz->where = __LINE__; 212 return (ENOMEM); 213 } 214 215 /* Find out how far we should go */ 216 gz->file_end = gz->file_offset + gz->a_out.a_text + gz->a_out.a_data; 217 218 /* copy in arguments and/or environment from old process */ 219 error = exec_extract_strings(gz->ip); 220 if (error) { 221 gz->where = __LINE__; 222 return (error); 223 } 224 225 /* 226 * Destroy old process VM and create a new one (with a new stack) 227 */ 228 exec_new_vmspace(gz->ip); 229 230 vmaddr = gz->virtual_offset; 231 232 error = vm_mmap(&vmspace->vm_map, /* map */ 233 &vmaddr, /* address */ 234 gz->a_out.a_text, /* size */ 235 VM_PROT_READ | VM_PROT_EXECUTE | VM_PROT_WRITE, /* protection */ 236 VM_PROT_READ | VM_PROT_EXECUTE | VM_PROT_WRITE, 237 MAP_ANON | MAP_FIXED, /* flags */ 238 0, /* vnode */ 239 0); /* offset */ 240 241 if (error) { 242 gz->where = __LINE__; 243 return (error); 244 } 245 246 vmaddr = gz->virtual_offset + gz->a_out.a_text; 247 248 /* 249 * Map data read/write (if text is 0, assume text is in data area 250 * [Bill's screwball mode]) 251 */ 252 253 error = vm_mmap(&vmspace->vm_map, 254 &vmaddr, 255 gz->a_out.a_data, 256 VM_PROT_READ | VM_PROT_WRITE | (gz->a_out.a_text ? 0 : VM_PROT_EXECUTE), 257 VM_PROT_ALL, MAP_ANON | MAP_FIXED, 258 0, 259 0); 260 261 if (error) { 262 gz->where = __LINE__; 263 return (error); 264 } 265 266 /* 267 * Allocate demand-zeroed area for uninitialized data 268 * "bss" = 'block started by symbol' - named after the IBM 7090 269 * instruction of the same name. 270 */ 271 vmaddr = gz->virtual_offset + gz->a_out.a_text + gz->a_out.a_data; 272 error = vm_allocate(&vmspace->vm_map, &vmaddr, gz->bss_size, FALSE); 273 if (error) { 274 gz->where = __LINE__; 275 return (error); 276 } 277 278 /* Fill in process VM information */ 279 vmspace->vm_tsize = gz->a_out.a_text >> PAGE_SHIFT; 280 vmspace->vm_dsize = (gz->a_out.a_data + gz->bss_size) >> PAGE_SHIFT; 281 vmspace->vm_taddr = (caddr_t) gz->virtual_offset; 282 vmspace->vm_daddr = (caddr_t) gz->virtual_offset + gz->a_out.a_text; 283 284 /* Fill in image_params */ 285 gz->ip->interpreted = 0; 286 gz->ip->entry_addr = gz->a_out.a_entry; 287 288 gz->ip->proc->p_sysent = &aout_sysvec; 289 290 return 0; 291} 292 293/* 294 * Tell kern_execve.c about it, with a little help from the linker. 295 * Since `const' objects end up in the text segment, TEXT_SET is the 296 * correct directive to use. 297 */ 298static const struct execsw gzip_execsw = { exec_gzip_imgact, "gzip" }; 299TEXT_SET(execsw_set, gzip_execsw); 300 301/* Stuff to make inflate() work */ 302# define uch u_char 303# define ush u_short 304# define ulg u_long 305# define memzero(dest,len) bzero(dest,len) 306# define NOMEMCPY 307#define FPRINTF printf 308 309#define EOF -1 310#define CHECK_EOF 311static int 312NextByte(struct gzip *gz) 313{ 314 int error; 315 316 if(gz->idx >= gz->len) { 317 gz->where = __LINE__; 318 return EOF; 319 } 320 321 if((!gz->inbuf) || gz->idx >= (gz->offset+PAGE_SIZE)) { 322 if(gz->inbuf) { 323 error = vm_deallocate(kernel_map, 324 (vm_offset_t)gz->inbuf, PAGE_SIZE); 325 if(error) { 326 gz->where = __LINE__; 327 gz->error = error; 328 return EOF; 329 } 330 } 331 332 gz->offset += PAGE_SIZE; 333 334 error = vm_mmap(kernel_map, /* map */ 335 (vm_offset_t *)&gz->inbuf, /* address */ 336 PAGE_SIZE, /* size */ 337 VM_PROT_READ, /* protection */ 338 VM_PROT_READ, /* max protection */ 339 0, /* flags */ 340 (caddr_t)gz->ip->vnodep, /* vnode */ 341 gz->offset); /* offset */ 342 if(error) { 343 gz->where = __LINE__; 344 gz->error = error; 345 return EOF; 346 } 347 348 } 349 return gz->inbuf[(gz->idx++) - gz->offset]; 350} 351 352#define NEXTBYTE NextByte(gz) 353 354static int 355Flush(struct gzip *gz,u_long siz) 356{ 357 u_char *p = slide,*q; 358 int i; 359 360 /* First, find a a.out-header */ 361 if(gz->output < sizeof gz->a_out) { 362 q = (u_char*) &gz->a_out; 363 i = min(siz,sizeof gz->a_out - gz->output); 364 bcopy(p,q+gz->output,i); 365 gz->output += i; 366 p += i; 367 siz -= i; 368 if(gz->output == sizeof gz->a_out) { 369 i = do_aout_hdr(gz); 370 if (i == -1) { 371 gz->where = __LINE__; 372 gz->error = ENOEXEC; 373 return ENOEXEC; 374 } else if (i) { 375 gz->where = __LINE__; 376 gz->error = i; 377 return ENOEXEC; 378 } 379 if(gz->file_offset < sizeof gz->a_out) { 380 q = (u_char*) gz->virtual_offset + gz->output - gz->file_offset; 381 bcopy(&gz->a_out,q,sizeof gz->a_out - gz->file_offset); 382 } 383 } 384 } 385 if(gz->output >= gz->file_offset && gz->output < gz->file_end) { 386 i = min(siz, gz->file_end - gz->output); 387 q = (u_char*) gz->virtual_offset + gz->output - gz->file_offset; 388 bcopy(p,q,i); 389 gz->output += i; 390 p += i; 391 siz -= i; 392 } 393 gz->output += siz; 394 return 0; 395} 396 397#define FLUSH(x,y) {int foo = Flush(x,y); if (foo) return foo;} 398static 399void * 400myalloc(u_long size) 401{ 402 return malloc(size, M_TEMP, M_NOWAIT); 403} 404#define malloc myalloc 405 406static 407void 408myfree(void * ptr) 409{ 410 free(ptr,M_TEMP); 411} 412#define free myfree 413 414static int qflag; 415#define Trace(x) /* */ 416 417 418/* This came from unzip-5.12. I have changed it to pass a "gz" pointer 419 * around, thus hopefully making it re-entrant. Poul-Henningi 420 */ 421 422/* inflate.c -- put in the public domain by Mark Adler 423 version c14o, 23 August 1994 */ 424 425/* You can do whatever you like with this source file, though I would 426 prefer that if you modify it and redistribute it that you include 427 comments to that effect with your name and the date. Thank you. 428 429 History: 430 vers date who what 431 ---- --------- -------------- ------------------------------------ 432 a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 433 b1 21 Mar 92 M. Adler first version with partial lookup tables 434 b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 435 b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 436 b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 437 is the responsibility of unzip.h--also 438 changed name to slide[]), so needs diffs 439 for unzip.c and unzip.h (this allows 440 compiling in the small model on MSDOS); 441 fixed cast of q in huft_build(); 442 b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 443 b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 444 bug in inflate_fixed(). 445 c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 446 changed BMAX to 16 for explode. Removed 447 OUTB usage, and replaced it with flush()-- 448 this was a 20% speed improvement! Added 449 an explode.c (to replace unimplod.c) that 450 uses the huft routines here. Removed 451 register union. 452 c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 453 c3 10 Apr 92 M. Adler reduced memory of code tables made by 454 huft_build significantly (factor of two to 455 three). 456 c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 457 worked around a Turbo C optimization bug. 458 c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducing 459 the 32K window size for specialized 460 applications. 461 c6 31 May 92 M. Adler added some typecasts to eliminate warnings 462 c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 463 c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 464 c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 465 c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 466 removed old inflate, renamed inflate_entry 467 to inflate, added Mark's fix to a comment. 468 c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 469 c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 470 tables, and removed assumption that EOB is 471 the longest code (bad assumption). 472 c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 473 c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 474 outputs one zero length code for an empty 475 distance tree). 476 c14 12 Mar 93 M. Adler made inflate.c standalone with the 477 introduction of inflate.h. 478 c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 479 c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 480 to static for Amiga. 481 c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 482 c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 483 c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 484 conditional; added inflate_free(). 485 c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 486 c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 487 c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 488 G. Roelofs check NEXTBYTE macro for EOF. 489 c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 490 EOF check. 491 c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 492 c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 493 to avoid bug in Encore compiler. 494 c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 495 inflate_codes() (define ASM_INFLATECODES) 496 c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 497 c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 498 G. Roelofs added another typecast to avoid MSC warning 499 */ 500 501 502/* 503 Inflate deflated (PKZIP's method 8 compressed) data. The compression 504 method searches for as much of the current string of bytes (up to a 505 length of 258) in the previous 32K bytes. If it doesn't find any 506 matches (of at least length 3), it codes the next byte. Otherwise, it 507 codes the length of the matched string and its distance backwards from 508 the current position. There is a single Huffman code that codes both 509 single bytes (called "literals") and match lengths. A second Huffman 510 code codes the distance information, which follows a length code. Each 511 length or distance code actually represents a base value and a number 512 of "extra" (sometimes zero) bits to get to add to the base value. At 513 the end of each deflated block is a special end-of-block (EOB) literal/ 514 length code. The decoding process is basically: get a literal/length 515 code; if EOB then done; if a literal, emit the decoded byte; if a 516 length then get the distance and emit the referred-to bytes from the 517 sliding window of previously emitted data. 518 519 There are (currently) three kinds of inflate blocks: stored, fixed, and 520 dynamic. The compressor outputs a chunk of data at a time and decides 521 which method to use on a chunk-by-chunk basis. A chunk might typically 522 be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 523 "stored" method is used. In this case, the bytes are simply stored as 524 is, eight bits per byte, with none of the above coding. The bytes are 525 preceded by a count, since there is no longer an EOB code. 526 527 If the data is compressible, then either the fixed or dynamic methods 528 are used. In the dynamic method, the compressed data is preceded by 529 an encoding of the literal/length and distance Huffman codes that are 530 to be used to decode this block. The representation is itself Huffman 531 coded, and so is preceded by a description of that code. These code 532 descriptions take up a little space, and so for small blocks, there is 533 a predefined set of codes, called the fixed codes. The fixed method is 534 used if the block ends up smaller that way (usually for quite small 535 chunks); otherwise the dynamic method is used. In the latter case, the 536 codes are customized to the probabilities in the current block and so 537 can code it much better than the pre-determined fixed codes can. 538 539 The Huffman codes themselves are decoded using a mutli-level table 540 lookup, in order to maximize the speed of decoding plus the speed of 541 building the decoding tables. See the comments below that precede the 542 lbits and dbits tuning parameters. 543 */ 544 545 546/* 547 Notes beyond the 1.93a appnote.txt: 548 549 1. Distance pointers never point before the beginning of the output 550 stream. 551 2. Distance pointers can point back across blocks, up to 32k away. 552 3. There is an implied maximum of 7 bits for the bit length table and 553 15 bits for the actual data. 554 4. If only one code exists, then it is encoded using one bit. (Zero 555 would be more efficient, but perhaps a little confusing.) If two 556 codes exist, they are coded using one bit each (0 and 1). 557 5. There is no way of sending zero distance codes--a dummy must be 558 sent if there are none. (History: a pre 2.0 version of PKZIP would 559 store blocks with no distance codes, but this was discovered to be 560 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 561 zero distance codes, which is sent as one code of zero bits in 562 length. 563 6. There are up to 286 literal/length codes. Code 256 represents the 564 end-of-block. Note however that the static length tree defines 565 288 codes just to fill out the Huffman codes. Codes 286 and 287 566 cannot be used though, since there is no length base or extra bits 567 defined for them. Similarily, there are up to 30 distance codes. 568 However, static trees define 32 codes (all 5 bits) to fill out the 569 Huffman codes, but the last two had better not show up in the data. 570 7. Unzip can check dynamic Huffman blocks for complete code sets. 571 The exception is that a single code would not be complete (see #4). 572 8. The five bits following the block type is really the number of 573 literal codes sent minus 257. 574 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 575 (1+6+6). Therefore, to output three times the length, you output 576 three codes (1+1+1), whereas to output four times the same length, 577 you only need two codes (1+3). Hmm. 578 10. In the tree reconstruction algorithm, Code = Code + Increment 579 only if BitLength(i) is not zero. (Pretty obvious.) 580 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 581 12. Note: length code 284 can represent 227-258, but length code 285 582 really is 258. The last length deserves its own, short code 583 since it gets used a lot in very redundant files. The length 584 258 is special since 258 - 3 (the min match length) is 255. 585 13. The literal/length and distance code bit lengths are read as a 586 single stream of lengths. It is possible (and advantageous) for 587 a repeat code (16, 17, or 18) to go across the boundary between 588 the two sets of lengths. 589 */ 590 591 592#define PKZIP_BUG_WORKAROUND /* PKZIP 1.93a problem--live with it */ 593 594/* 595 inflate.h must supply the uch slide[WSIZE] array and the NEXTBYTE, 596 FLUSH() and memzero macros. If the window size is not 32K, it 597 should also define WSIZE. If INFMOD is defined, it can include 598 compiled functions to support the NEXTBYTE and/or FLUSH() macros. 599 There are defaults for NEXTBYTE and FLUSH() below for use as 600 examples of what those functions need to do. Normally, you would 601 also want FLUSH() to compute a crc on the data. inflate.h also 602 needs to provide these typedefs: 603 604 typedef unsigned char uch; 605 typedef unsigned short ush; 606 typedef unsigned long ulg; 607 608 This module uses the external functions malloc() and free() (and 609 probably memset() or bzero() in the memzero() macro). Their 610 prototypes are normally found in <string.h> and <stdlib.h>. 611 */ 612#define INFMOD /* tell inflate.h to include code to be compiled */ 613 614/* Huffman code lookup table entry--this entry is four bytes for machines 615 that have 16-bit pointers (e.g. PC's in the small or medium model). 616 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 617 means that v is a literal, 16 < e < 32 means that v is a pointer to 618 the next table, which codes e - 16 bits, and lastly e == 99 indicates 619 an unused code. If a code with e == 99 is looked up, this implies an 620 error in the data. */ 621struct huft { 622 uch e; /* number of extra bits or operation */ 623 uch b; /* number of bits in this code or subcode */ 624 union { 625 ush n; /* literal, length base, or distance base */ 626 struct huft *t; /* pointer to next level of table */ 627 } v; 628}; 629 630 631/* Function prototypes */ 632#ifndef OF 633# ifdef __STDC__ 634# define OF(a) a 635# else /* !__STDC__ */ 636# define OF(a) () 637# endif /* ?__STDC__ */ 638#endif 639int huft_build OF((struct gzip *,unsigned *, unsigned, unsigned, ush *, ush *, 640 struct huft **, int *)); 641int huft_free OF((struct gzip *,struct huft *)); 642int inflate_codes OF((struct gzip *,struct huft *, struct huft *, int, int)); 643int inflate_stored OF((struct gzip *)); 644int inflate_fixed OF((struct gzip *)); 645int inflate_dynamic OF((struct gzip *)); 646int inflate_block OF((struct gzip *,int *)); 647int inflate_free OF((struct gzip *)); 648 649 650/* The inflate algorithm uses a sliding 32K byte window on the uncompressed 651 stream to find repeated byte strings. This is implemented here as a 652 circular buffer. The index is updated simply by incrementing and then 653 and'ing with 0x7fff (32K-1). */ 654/* It is left to other modules to supply the 32K area. It is assumed 655 to be usable as if it were declared "uch slide[32768];" or as just 656 "uch *slide;" and then malloc'ed in the latter case. The definition 657 must be in unzip.h, included above. */ 658 659 660/* Tables for deflate from PKZIP's appnote.txt. */ 661static unsigned border[] = { /* Order of the bit length code lengths */ 662 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 663static ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 664 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 665 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 666 /* note: see note #13 above about the 258 in this list. */ 667static ush cplext[] = { /* Extra bits for literal codes 257..285 */ 668 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 669 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 670static ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 671 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 672 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 673 8193, 12289, 16385, 24577}; 674static ush cpdext[] = { /* Extra bits for distance codes */ 675 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 676 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 677 12, 12, 13, 13}; 678 679/* And'ing with mask[n] masks the lower n bits */ 680ush mask[] = { 681 0x0000, 682 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 683 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 684}; 685 686 687/* Macros for inflate() bit peeking and grabbing. 688 The usage is: 689 690 NEEDBITS(j) 691 x = b & mask[j]; 692 DUMPBITS(j) 693 694 where NEEDBITS makes sure that b has at least j bits in it, and 695 DUMPBITS removes the bits from b. The macros use the variable k 696 for the number of bits in b. Normally, b and k are register 697 variables for speed, and are initialized at the begining of a 698 routine that uses these macros from a global bit buffer and count. 699 700 In order to not ask for more bits than there are in the compressed 701 stream, the Huffman tables are constructed to only ask for just 702 enough bits to make up the end-of-block code (value 256). Then no 703 bytes need to be "returned" to the buffer at the end of the last 704 block. See the huft_build() routine. 705 */ 706 707ulg bb; /* bit buffer */ 708unsigned bk; /* bits in bit buffer */ 709 710#ifndef CHECK_EOF 711# define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE)<<k;k+=8;}} 712#else 713# define NEEDBITS(n) {while(k<(n)){int c=NEXTBYTE;if(c==EOF)return 1;\ 714 b|=((ulg)c)<<k;k+=8;}} 715#endif /* Piet Plomp: change "return 1" to "break" */ 716 717#define DUMPBITS(n) {b>>=(n);k-=(n);} 718 719 720/* 721 Huffman code decoding is performed using a multi-level table lookup. 722 The fastest way to decode is to simply build a lookup table whose 723 size is determined by the longest code. However, the time it takes 724 to build this table can also be a factor if the data being decoded 725 is not very long. The most common codes are necessarily the 726 shortest codes, so those codes dominate the decoding time, and hence 727 the speed. The idea is you can have a shorter table that decodes the 728 shorter, more probable codes, and then point to subsidiary tables for 729 the longer codes. The time it costs to decode the longer codes is 730 then traded against the time it takes to make longer tables. 731 732 This results of this trade are in the variables lbits and dbits 733 below. lbits is the number of bits the first level table for literal/ 734 length codes can decode in one step, and dbits is the same thing for 735 the distance codes. Subsequent tables are also less than or equal to 736 those sizes. These values may be adjusted either when all of the 737 codes are shorter than that, in which case the longest code length in 738 bits is used, or when the shortest code is *longer* than the requested 739 table size, in which case the length of the shortest code in bits is 740 used. 741 742 There are two different values for the two tables, since they code a 743 different number of possibilities each. The literal/length table 744 codes 286 possible values, or in a flat code, a little over eight 745 bits. The distance table codes 30 possible values, or a little less 746 than five bits, flat. The optimum values for speed end up being 747 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 748 The optimum values may differ though from machine to machine, and 749 possibly even between compilers. Your mileage may vary. 750 */ 751 752 753int lbits = 9; /* bits in base literal/length lookup table */ 754int dbits = 6; /* bits in base distance lookup table */ 755 756 757/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 758#define BMAX 16 /* maximum bit length of any code (16 for explode) */ 759#define N_MAX 288 /* maximum number of codes in any set */ 760 761 762unsigned hufts; /* track memory usage */ 763 764 765int huft_build(gz,b, n, s, d, e, t, m) 766struct gzip *gz; 767unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ 768unsigned n; /* number of codes (assumed <= N_MAX) */ 769unsigned s; /* number of simple-valued codes (0..s-1) */ 770ush *d; /* list of base values for non-simple codes */ 771ush *e; /* list of extra bits for non-simple codes */ 772struct huft **t; /* result: starting table */ 773int *m; /* maximum lookup bits, returns actual */ 774/* Given a list of code lengths and a maximum table size, make a set of 775 tables to decode that set of codes. Return zero on success, one if 776 the given code set is incomplete (the tables are still built in this 777 case), two if the input is invalid (all zero length codes or an 778 oversubscribed set of lengths), and three if not enough memory. 779 The code with value 256 is special, and the tables are constructed 780 so that no bits beyond that code are fetched when that code is 781 decoded. */ 782{ 783 unsigned a; /* counter for codes of length k */ 784 unsigned c[BMAX+1]; /* bit length count table */ 785 unsigned el; /* length of EOB code (value 256) */ 786 unsigned f; /* i repeats in table every f entries */ 787 int g; /* maximum code length */ 788 int h; /* table level */ 789 register unsigned i; /* counter, current code */ 790 register unsigned j; /* counter */ 791 register int k; /* number of bits in current code */ 792 int lx[BMAX+1]; /* memory for l[-1..BMAX-1] */ 793 int *l = lx+1; /* stack of bits per table */ 794 register unsigned *p; /* pointer into c[], b[], or v[] */ 795 register struct huft *q; /* points to current table */ 796 struct huft r; /* table entry for structure assignment */ 797 struct huft *u[BMAX]; /* table stack */ 798 static unsigned v[N_MAX]; /* values in order of bit length */ 799 register int w; /* bits before this table == (l * h) */ 800 unsigned x[BMAX+1]; /* bit offsets, then code stack */ 801 unsigned *xp; /* pointer into x */ 802 int y; /* number of dummy codes added */ 803 unsigned z; /* number of entries in current table */ 804 805 806 /* Generate counts for each bit length */ 807 el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 808 memzero((char *)c, sizeof(c)); 809 p = b; i = n; 810 do { 811 c[*p]++; p++; /* assume all entries <= BMAX */ 812 } while (--i); 813 if (c[0] == n) /* null input--all zero length codes */ 814 { 815 *t = (struct huft *)NULL; 816 *m = 0; 817 return 0; 818 } 819 820 821 /* Find minimum and maximum length, bound *m by those */ 822 for (j = 1; j <= BMAX; j++) 823 if (c[j]) 824 break; 825 k = j; /* minimum code length */ 826 if ((unsigned)*m < j) 827 *m = j; 828 for (i = BMAX; i; i--) 829 if (c[i]) 830 break; 831 g = i; /* maximum code length */ 832 if ((unsigned)*m > i) 833 *m = i; 834 835 836 /* Adjust last length count to fill out codes, if needed */ 837 for (y = 1 << j; j < i; j++, y <<= 1) 838 if ((y -= c[j]) < 0) 839 return 2; /* bad input: more codes than bits */ 840 if ((y -= c[i]) < 0) 841 return 2; 842 c[i] += y; 843 844 845 /* Generate starting offsets into the value table for each length */ 846 x[1] = j = 0; 847 p = c + 1; xp = x + 2; 848 while (--i) { /* note that i == g from above */ 849 *xp++ = (j += *p++); 850 } 851 852 853 /* Make a table of values in order of bit lengths */ 854 p = b; i = 0; 855 do { 856 if ((j = *p++) != 0) 857 v[x[j]++] = i; 858 } while (++i < n); 859 860 861 /* Generate the Huffman codes and for each, make the table entries */ 862 x[0] = i = 0; /* first Huffman code is zero */ 863 p = v; /* grab values in bit order */ 864 h = -1; /* no tables yet--level -1 */ 865 w = l[-1] = 0; /* no bits decoded yet */ 866 u[0] = (struct huft *)NULL; /* just to keep compilers happy */ 867 q = (struct huft *)NULL; /* ditto */ 868 z = 0; /* ditto */ 869 870 /* go through the bit lengths (k already is bits in shortest code) */ 871 for (; k <= g; k++) 872 { 873 a = c[k]; 874 while (a--) 875 { 876 /* here i is the Huffman code of length k bits for value *p */ 877 /* make tables up to required level */ 878 while (k > w + l[h]) 879 { 880 w += l[h++]; /* add bits already decoded */ 881 882 /* compute minimum size table less than or equal to *m bits */ 883 z = (z = g - w) > (unsigned)*m ? *m : z; /* upper limit */ 884 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 885 { /* too few codes for k-w bit table */ 886 f -= a + 1; /* deduct codes from patterns left */ 887 xp = c + k; 888 while (++j < z) /* try smaller tables up to z bits */ 889 { 890 if ((f <<= 1) <= *++xp) 891 break; /* enough codes to use up j bits */ 892 f -= *xp; /* else deduct codes from patterns */ 893 } 894 } 895 if ((unsigned)w + j > el && (unsigned)w < el) 896 j = el - w; /* make EOB code end at table */ 897 z = 1 << j; /* table entries for j-bit table */ 898 l[h] = j; /* set table size in stack */ 899 900 /* allocate and link in new table */ 901 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == 902 (struct huft *)NULL) 903 { 904 if (h) 905 huft_free(gz,u[0]); 906 return 3; /* not enough memory */ 907 } 908 hufts += z + 1; /* track memory usage */ 909 *t = q + 1; /* link to list for huft_free() */ 910 *(t = &(q->v.t)) = (struct huft *)NULL; 911 u[h] = ++q; /* table starts after link */ 912 913 /* connect to last table, if there is one */ 914 if (h) 915 { 916 x[h] = i; /* save pattern for backing up */ 917 r.b = (uch)l[h-1]; /* bits to dump before this table */ 918 r.e = (uch)(16 + j); /* bits in this table */ 919 r.v.t = q; /* pointer to this table */ 920 j = (i & ((1 << w) - 1)) >> (w - l[h-1]); 921 u[h-1][j] = r; /* connect to last table */ 922 } 923 } 924 925 /* set up table entry in r */ 926 r.b = (uch)(k - w); 927 if (p >= v + n) 928 r.e = 99; /* out of values--invalid code */ 929 else if (*p < s) 930 { 931 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 932 r.v.n = *p++; /* simple code is just the value */ 933 } 934 else 935 { 936 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ 937 r.v.n = d[*p++ - s]; 938 } 939 940 /* fill code-like entries with r */ 941 f = 1 << (k - w); 942 for (j = i >> w; j < z; j += f) 943 q[j] = r; 944 945 /* backwards increment the k-bit code i */ 946 for (j = 1 << (k - 1); i & j; j >>= 1) 947 i ^= j; 948 i ^= j; 949 950 /* backup over finished tables */ 951 while ((i & ((1 << w) - 1)) != x[h]) 952 w -= l[--h]; /* don't need to update q */ 953 } 954 } 955 956 957 /* return actual size of base table */ 958 *m = l[0]; 959 960 961 /* Return true (1) if we were given an incomplete table */ 962 return y != 0 && g != 1; 963} 964 965 966 967int huft_free(gz,t) 968struct gzip *gz; 969struct huft *t; /* table to free */ 970/* Free the malloc'ed tables built by huft_build(), which makes a linked 971 list of the tables it made, with the links in a dummy first entry of 972 each table. */ 973{ 974 register struct huft *p, *q; 975 976 977 /* Go through linked list, freeing from the malloced (t[-1]) address. */ 978 p = t; 979 while (p != (struct huft *)NULL) 980 { 981 q = (--p)->v.t; 982 free(p); 983 p = q; 984 } 985 return 0; 986} 987 988 989 990#ifdef ASM_INFLATECODES 991# define inflate_codes(tl,td,bl,bd) flate_codes(tl,td,bl,bd,(uch *)slide) 992 int flate_codes OF((struct huft *, struct huft *, int, int, uch *)); 993 994#else 995 996int inflate_codes(gz,tl, td, bl, bd) 997struct gzip *gz; 998struct huft *tl, *td; /* literal/length and distance decoder tables */ 999int bl, bd; /* number of bits decoded by tl[] and td[] */ 1000/* inflate (decompress) the codes in a deflated (compressed) block. 1001 Return an error code or zero if it all goes ok. */ 1002{ 1003 register unsigned e; /* table entry flag/number of extra bits */ 1004 unsigned n, d; /* length and index for copy */ 1005 unsigned w; /* current window position */ 1006 struct huft *t; /* pointer to table entry */ 1007 unsigned ml, md; /* masks for bl and bd bits */ 1008 register ulg b; /* bit buffer */ 1009 register unsigned k; /* number of bits in bit buffer */ 1010 1011 1012 /* make local copies of globals */ 1013 b = bb; /* initialize bit buffer */ 1014 k = bk; 1015 w = wp; /* initialize window position */ 1016 1017 1018 /* inflate the coded data */ 1019 ml = mask[bl]; /* precompute masks for speed */ 1020 md = mask[bd]; 1021 while (1) /* do until end of block */ 1022 { 1023 NEEDBITS((unsigned)bl) 1024 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) 1025 do { 1026 if (e == 99) 1027 return 1; 1028 DUMPBITS(t->b) 1029 e -= 16; 1030 NEEDBITS(e) 1031 } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 1032 DUMPBITS(t->b) 1033 if (e == 16) /* then it's a literal */ 1034 { 1035 slide[w++] = (uch)t->v.n; 1036 if (w == WSIZE) 1037 { 1038 FLUSH(gz,w); 1039 w = 0; 1040 } 1041 } 1042 else /* it's an EOB or a length */ 1043 { 1044 /* exit if end of block */ 1045 if (e == 15) 1046 break; 1047 1048 /* get length of block to copy */ 1049 NEEDBITS(e) 1050 n = t->v.n + ((unsigned)b & mask[e]); 1051 DUMPBITS(e); 1052 1053 /* decode distance of block to copy */ 1054 NEEDBITS((unsigned)bd) 1055 if ((e = (t = td + ((unsigned)b & md))->e) > 16) 1056 do { 1057 if (e == 99) 1058 return 1; 1059 DUMPBITS(t->b) 1060 e -= 16; 1061 NEEDBITS(e) 1062 } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 1063 DUMPBITS(t->b) 1064 NEEDBITS(e) 1065 d = w - t->v.n - ((unsigned)b & mask[e]); 1066 DUMPBITS(e) 1067 1068 /* do the copy */ 1069 do { 1070 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); 1071#ifndef NOMEMCPY 1072 if (w - d >= e) /* (this test assumes unsigned comparison) */ 1073 { 1074 memcpy(slide + w, slide + d, e); 1075 w += e; 1076 d += e; 1077 } 1078 else /* do it slow to avoid memcpy() overlap */ 1079#endif /* !NOMEMCPY */ 1080 do { 1081 slide[w++] = slide[d++]; 1082 } while (--e); 1083 if (w == WSIZE) 1084 { 1085 FLUSH(gz,w); 1086 w = 0; 1087 } 1088 } while (n); 1089 } 1090 } 1091 1092 1093 /* restore the globals from the locals */ 1094 wp = w; /* restore global window pointer */ 1095 bb = b; /* restore global bit buffer */ 1096 bk = k; 1097 1098 1099 /* done */ 1100 return 0; 1101} 1102 1103#endif /* ASM_INFLATECODES */ 1104 1105 1106 1107int inflate_stored(gz) 1108struct gzip *gz; 1109/* "decompress" an inflated type 0 (stored) block. */ 1110{ 1111 unsigned n; /* number of bytes in block */ 1112 unsigned w; /* current window position */ 1113 register ulg b; /* bit buffer */ 1114 register unsigned k; /* number of bits in bit buffer */ 1115 1116 1117 /* make local copies of globals */ 1118 Trace((stderr, "\nstored block")); 1119 b = bb; /* initialize bit buffer */ 1120 k = bk; 1121 w = wp; /* initialize window position */ 1122 1123 1124 /* go to byte boundary */ 1125 n = k & 7; 1126 DUMPBITS(n); 1127 1128 1129 /* get the length and its complement */ 1130 NEEDBITS(16) 1131 n = ((unsigned)b & 0xffff); 1132 DUMPBITS(16) 1133 NEEDBITS(16) 1134 if (n != (unsigned)((~b) & 0xffff)) 1135 return 1; /* error in compressed data */ 1136 DUMPBITS(16) 1137 1138 1139 /* read and output the compressed data */ 1140 while (n--) 1141 { 1142 NEEDBITS(8) 1143 slide[w++] = (uch)b; 1144 if (w == WSIZE) 1145 { 1146 FLUSH(gz,w); 1147 w = 0; 1148 } 1149 DUMPBITS(8) 1150 } 1151 1152 1153 /* restore the globals from the locals */ 1154 wp = w; /* restore global window pointer */ 1155 bb = b; /* restore global bit buffer */ 1156 bk = k; 1157 return 0; 1158} 1159 1160 1161/* Globals for literal tables (built once) */ 1162struct huft *fixed_tl = (struct huft *)NULL; 1163struct huft *fixed_td; 1164int fixed_bl, fixed_bd; 1165 1166int inflate_fixed(gz) 1167struct gzip *gz; 1168/* decompress an inflated type 1 (fixed Huffman codes) block. We should 1169 either replace this with a custom decoder, or at least precompute the 1170 Huffman tables. */ 1171{ 1172 /* if first time, set up tables for fixed blocks */ 1173 Trace((stderr, "\nliteral block")); 1174 if (fixed_tl == (struct huft *)NULL) 1175 { 1176 int i; /* temporary variable */ 1177 static unsigned l[288]; /* length list for huft_build */ 1178 1179 /* literal table */ 1180 for (i = 0; i < 144; i++) 1181 l[i] = 8; 1182 for (; i < 256; i++) 1183 l[i] = 9; 1184 for (; i < 280; i++) 1185 l[i] = 7; 1186 for (; i < 288; i++) /* make a complete, but wrong code set */ 1187 l[i] = 8; 1188 fixed_bl = 7; 1189 if ((i = huft_build(gz,l, 288, 257, cplens, cplext, 1190 &fixed_tl, &fixed_bl)) != 0) 1191 { 1192 fixed_tl = (struct huft *)NULL; 1193 return i; 1194 } 1195 1196 /* distance table */ 1197 for (i = 0; i < 30; i++) /* make an incomplete code set */ 1198 l[i] = 5; 1199 fixed_bd = 5; 1200 if ((i = huft_build(gz,l, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd)) > 1) 1201 { 1202 huft_free(gz,fixed_tl); 1203 fixed_tl = (struct huft *)NULL; 1204 return i; 1205 } 1206 } 1207 1208 1209 /* decompress until an end-of-block code */ 1210 return inflate_codes(gz,fixed_tl, fixed_td, fixed_bl, fixed_bd) != 0; 1211} 1212 1213 1214 1215int inflate_dynamic(gz) 1216struct gzip *gz; 1217/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 1218{ 1219 int i; /* temporary variables */ 1220 unsigned j; 1221 unsigned l; /* last length */ 1222 unsigned m; /* mask for bit lengths table */ 1223 unsigned n; /* number of lengths to get */ 1224 struct huft *tl; /* literal/length code table */ 1225 struct huft *td; /* distance code table */ 1226 int bl; /* lookup bits for tl */ 1227 int bd; /* lookup bits for td */ 1228 unsigned nb; /* number of bit length codes */ 1229 unsigned nl; /* number of literal/length codes */ 1230 unsigned nd; /* number of distance codes */ 1231#ifdef PKZIP_BUG_WORKAROUND 1232 static unsigned ll[288+32]; /* literal/length and distance code lengths */ 1233#else 1234 static unsigned ll[286+30]; /* literal/length and distance code lengths */ 1235#endif 1236 register ulg b; /* bit buffer */ 1237 register unsigned k; /* number of bits in bit buffer */ 1238 1239 1240 /* make local bit buffer */ 1241 Trace((stderr, "\ndynamic block")); 1242 b = bb; 1243 k = bk; 1244 1245 1246 /* read in table lengths */ 1247 NEEDBITS(5) 1248 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ 1249 DUMPBITS(5) 1250 NEEDBITS(5) 1251 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ 1252 DUMPBITS(5) 1253 NEEDBITS(4) 1254 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ 1255 DUMPBITS(4) 1256#ifdef PKZIP_BUG_WORKAROUND 1257 if (nl > 288 || nd > 32) 1258#else 1259 if (nl > 286 || nd > 30) 1260#endif 1261 return 1; /* bad lengths */ 1262 1263 1264 /* read in bit-length-code lengths */ 1265 for (j = 0; j < nb; j++) 1266 { 1267 NEEDBITS(3) 1268 ll[border[j]] = (unsigned)b & 7; 1269 DUMPBITS(3) 1270 } 1271 for (; j < 19; j++) 1272 ll[border[j]] = 0; 1273 1274 1275 /* build decoding table for trees--single level, 7 bit lookup */ 1276 bl = 7; 1277 if ((i = huft_build(gz,ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) 1278 { 1279 if (i == 1) 1280 huft_free(gz,tl); 1281 return i; /* incomplete code set */ 1282 } 1283 1284 1285 /* read in literal and distance code lengths */ 1286 n = nl + nd; 1287 m = mask[bl]; 1288 i = l = 0; 1289 while ((unsigned)i < n) 1290 { 1291 NEEDBITS((unsigned)bl) 1292 j = (td = tl + ((unsigned)b & m))->b; 1293 DUMPBITS(j) 1294 j = td->v.n; 1295 if (j < 16) /* length of code in bits (0..15) */ 1296 ll[i++] = l = j; /* save last length in l */ 1297 else if (j == 16) /* repeat last length 3 to 6 times */ 1298 { 1299 NEEDBITS(2) 1300 j = 3 + ((unsigned)b & 3); 1301 DUMPBITS(2) 1302 if ((unsigned)i + j > n) 1303 return 1; 1304 while (j--) 1305 ll[i++] = l; 1306 } 1307 else if (j == 17) /* 3 to 10 zero length codes */ 1308 { 1309 NEEDBITS(3) 1310 j = 3 + ((unsigned)b & 7); 1311 DUMPBITS(3) 1312 if ((unsigned)i + j > n) 1313 return 1; 1314 while (j--) 1315 ll[i++] = 0; 1316 l = 0; 1317 } 1318 else /* j == 18: 11 to 138 zero length codes */ 1319 { 1320 NEEDBITS(7) 1321 j = 11 + ((unsigned)b & 0x7f); 1322 DUMPBITS(7) 1323 if ((unsigned)i + j > n) 1324 return 1; 1325 while (j--) 1326 ll[i++] = 0; 1327 l = 0; 1328 } 1329 } 1330 1331 1332 /* free decoding table for trees */ 1333 huft_free(gz,tl); 1334 1335 1336 /* restore the global bit buffer */ 1337 bb = b; 1338 bk = k; 1339 1340 1341 /* build the decoding tables for literal/length and distance codes */ 1342 bl = lbits; 1343 if ((i = huft_build(gz,ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) 1344 { 1345 if (i == 1 && !qflag) { 1346 FPRINTF( "(incomplete l-tree) "); 1347 huft_free(gz,tl); 1348 } 1349 return i; /* incomplete code set */ 1350 } 1351 bd = dbits; 1352 if ((i = huft_build(gz,ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) 1353 { 1354 if (i == 1 && !qflag) { 1355 FPRINTF( "(incomplete d-tree) "); 1356#ifdef PKZIP_BUG_WORKAROUND 1357 i = 0; 1358 } 1359#else 1360 huft_free(gz,td); 1361 } 1362 huft_free(gz,tl); 1363 return i; /* incomplete code set */ 1364#endif 1365 } 1366 1367 1368 /* decompress until an end-of-block code */ 1369 if (inflate_codes(gz,tl, td, bl, bd)) 1370 return 1; 1371 1372 1373 /* free the decoding tables, return */ 1374 huft_free(gz,tl); 1375 huft_free(gz,td); 1376 return 0; 1377} 1378 1379 1380 1381int inflate_block(gz,e) 1382struct gzip *gz; 1383int *e; /* last block flag */ 1384/* decompress an inflated block */ 1385{ 1386 unsigned t; /* block type */ 1387 register ulg b; /* bit buffer */ 1388 register unsigned k; /* number of bits in bit buffer */ 1389 1390 1391 /* make local bit buffer */ 1392 b = bb; 1393 k = bk; 1394 1395 1396 /* read in last block bit */ 1397 NEEDBITS(1) 1398 *e = (int)b & 1; 1399 DUMPBITS(1) 1400 1401 1402 /* read in block type */ 1403 NEEDBITS(2) 1404 t = (unsigned)b & 3; 1405 DUMPBITS(2) 1406 1407 1408 /* restore the global bit buffer */ 1409 bb = b; 1410 bk = k; 1411 1412 1413 /* inflate that block type */ 1414 if (t == 2) 1415 return inflate_dynamic(gz); 1416 if (t == 0) 1417 return inflate_stored(gz); 1418 if (t == 1) 1419 return inflate_fixed(gz); 1420 1421 1422 /* bad block type */ 1423 return 2; 1424} 1425 1426 1427 1428int inflate(gz) 1429struct gzip *gz; 1430/* decompress an inflated entry */ 1431{ 1432 int e; /* last block flag */ 1433 int r; /* result code */ 1434 unsigned h; /* maximum struct huft's malloc'ed */ 1435 1436 1437 /* initialize window, bit buffer */ 1438 wp = 0; 1439 bk = 0; 1440 bb = 0; 1441 1442 1443 /* decompress until the last block */ 1444 h = 0; 1445 do { 1446 hufts = 0; 1447 if ((r = inflate_block(gz,&e)) != 0) 1448 return r; 1449 if (hufts > h) 1450 h = hufts; 1451 } while (!e); 1452 1453 1454 /* flush out slide */ 1455 FLUSH(gz,wp); 1456 1457 1458 /* return success */ 1459 Trace((stderr, "\n%u bytes in Huffman tables (%d/entry)\n", 1460 h * sizeof(struct huft), sizeof(struct huft))); 1461 return 0; 1462} 1463 1464 1465 1466int inflate_free(gz) 1467struct gzip *gz; 1468{ 1469 if (fixed_tl != (struct huft *)NULL) 1470 { 1471 huft_free(gz,fixed_td); 1472 huft_free(gz,fixed_tl); 1473 fixed_td = fixed_tl = (struct huft *)NULL; 1474 } 1475 return 0; 1476} 1477