![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to zinflate.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to zinflate.c CVS log | Up to [PGP] / pgp / src |
1.1.1.6 ! root 1: /* inflate.c -- Not copyrighted 1992 by Mark Adler ! 2: version c4, 15 April 1992 */ ! 3: ! 4: ! 5: /* You can do whatever you like with this source file, though I would ! 6: prefer that if you modify it and redistribute it that you include ! 7: comments to that effect with your name and the date. Thank you. ! 8: ! 9: History: ! 10: vers date who what ! 11: ---- --------- -------------- ------------------------------------ ! 12: a ~~ Feb 92 M. Adler used full (large, one-step) lookup table ! 13: b1 21 Mar 92 M. Adler first version with partial lookup tables ! 14: b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks ! 15: b3 22 Mar 92 M. Adler sped up match copies, cleaned up some ! 16: b4 25 Mar 92 M. Adler added prototypes; removed window[] (now ! 17: is the responsibility of unzip.h--also ! 18: changed name to slide[]), so needs diffs ! 19: for unzip.c and unzip.h (this allows ! 20: compiling in the small model on MSDOS); ! 21: fixed cast of q in huft_build(); ! 22: b5 26 Mar 92 M. Adler got rid of unintended macro recursion. ! 23: b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed ! 24: bug in inflate_fixed(). ! 25: c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. ! 26: changed BMAX to 16 for explode. Removed ! 27: OUTB usage, and replaced it with flush()-- ! 28: this was a 20% speed improvement! Added ! 29: an explode.c (to replace unimplode.c) that ! 30: uses the huft routines here. Removed ! 31: register union. ! 32: c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. ! 33: c3 10 Apr 92 M. Adler reduced memory of code tables made by ! 34: huft_build significantly (factor of two to ! 35: three). ! 36: c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). ! 37: worked around a Turbo C optimization bug. ! 38: c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducing ! 39: the 32K window size for specialized ! 40: applications. ! 41: c6 27 May 92 J.loup Gailly Adapted for pgp ! 42: */ ! 43: ! 44: ! 45: /* ! 46: Inflate deflated (PKZIP's method 8 compressed) data. The compression ! 47: method searches for as much of the current string of bytes (up to a ! 48: length of 258) in the previous 32K bytes. If it doesn't find any ! 49: matches (of at least length 3), it codes the next byte. Otherwise, it ! 50: codes the length of the matched string and its distance backwards from ! 51: the current position. There is a single Huffman code that codes both ! 52: single bytes (called "literals") and match lengths. A second Huffman ! 53: code codes the distance information, which follows a length code. Each ! 54: length or distance code actually represents a base value and a number ! 55: of "extra" (sometimes zero) bits to get to add to the base value. At ! 56: the end of each deflated block is a special end-of-block (EOB) literal/ ! 57: length code. The decoding process is basically: get a literal/length ! 58: code; if EOB then done; if a literal, emit the decoded byte; if a ! 59: length then get the distance and emit the referred-to bytes from the ! 60: sliding window of previously emitted data. ! 61: ! 62: There are (currently) three kinds of inflate blocks: stored, fixed, and ! 63: dynamic. The compressor deals with some chunk of data at a time, and ! 64: decides which method to use on a chunk-by-chunk basis. A chunk might ! 65: typically be 32K or 64K. If the chunk is uncompressible, then the ! 66: "stored" method is used. In this case, the bytes are simply stored as ! 67: is, eight bits per byte, with none of the above coding. The bytes are ! 68: preceded by a count, since there is no longer an EOB code. ! 69: ! 70: If the data is compressible, then either the fixed or dynamic methods ! 71: are used. In the dynamic method, the compressed data is preceded by ! 72: an encoding of the literal/length and distance Huffman codes that are ! 73: to be used to decode this block. The representation is itself Huffman ! 74: coded, and so is preceded by a description of that code. These code ! 75: descriptions take up a little space, and so for small blocks, there is ! 76: a predefined set of codes, called the fixed codes. The fixed method is ! 77: used if the block codes up smaller that way (usually for quite small ! 78: chunks), otherwise the dynamic method is used. In the latter case, the ! 79: codes are customized to the probabilities in the current block, and so ! 80: can code it much better than the pre-determined fixed codes. ! 81: ! 82: The Huffman codes themselves are decoded using a mutli-level table ! 83: lookup, in order to maximize the speed of decoding plus the speed of ! 84: building the decoding tables. See the comments below that precede the ! 85: lbits and dbits tuning parameters. ! 86: */ ! 87: ! 88: ! 89: /* ! 90: Notes beyond the 1.93a appnote.txt: ! 91: ! 92: 1. Distance pointers never point before the beginning of the output ! 93: stream. ! 94: 2. Distance pointers can point back across blocks, up to 32k away. ! 95: 3. There is an implied maximum of 7 bits for the bit length table and ! 96: 15 bits for the actual data. ! 97: 4. If only one code exists, then it is encoded using one bit. (Zero ! 98: would be more efficient, but perhaps a little confusing.) If two ! 99: codes exist, they are coded using one bit each (0 and 1). ! 100: 5. There is no way of sending zero distance codes--a dummy must be ! 101: sent if there are none. (History: a pre 2.0 version of PKZIP would ! 102: store blocks with no distance codes, but this was discovered to be ! 103: too harsh a criterion.) ! 104: 6. There are up to 286 literal/length codes. Code 256 represents the ! 105: end-of-block. Note however that the static length tree defines ! 106: 288 codes just to fill out the Huffman codes. Codes 286 and 287 ! 107: cannot be used though, since there is no length base or extra bits ! 108: defined for them. Similarily, there are up to 30 distance codes. ! 109: However, static trees define 32 codes (all 5 bits) to fill out the ! 110: Huffman codes, but the last two had better not show up in the data. ! 111: 7. Unzip can check dynamic huffman blocks for complete code sets. ! 112: The exception is that a single code would not be complete (see #4). ! 113: 8. The five bits following the block type is really the number of ! 114: literal codes sent minus 257. ! 115: 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits ! 116: (1+6+6). Therefore, to output three times the length, you output ! 117: three codes (1+1+1), whereas to output four times the same length, ! 118: you only need two codes (1+3). Hmm. ! 119: 10. In the tree reconstruction algorithm, Code = Code + Increment ! 120: only if BitLength(i) is not zero. (Pretty obvious.) ! 121: 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) ! 122: 12. Note: length code 284 can represent 227-258, but length code 285 ! 123: really is 258. The last length deserves its own, short code ! 124: since it gets used a lot in very redundant files. The length ! 125: 258 is special since 258 - 3 (the min match length) is 255. ! 126: 13. The literal/length and distance code bit lengths are read as a ! 127: single stream of lengths. It is possible (and advantageous) for ! 128: a repeat code (16, 17, or 18) to go across the boundary between ! 129: the two sets of lengths. ! 130: */ ! 131: ! 132: #include "zunzip.h" ! 133: #include "exitpgp.h" ! 134: #define OF __ ! 135: ! 136: #ifdef MACTC5 ! 137: #include "Macutil3.h" ! 138: void err(int c, char *msg); ! 139: #endif ! 140: ! 141: #ifndef WSIZE ! 142: # define WSIZE 8192 ! 143: /* window size--must be a power of two, <= 32K, and equal to that of zip. ! 144: * On 16 bit machines (MSDOS), WSIZE must be <= 16K (32K is possible ! 145: * with a few hacks, see the zip archiver. ! 146: */ ! 147: #endif ! 148: ! 149: #ifdef DYN_ALLOC ! 150: extern char *slide; ! 151: #else ! 152: extern char slide[]; ! 153: #endif ! 154: ! 155: /* Huffman code lookup table entry--this entry is four bytes for machines ! 156: that have 16-bit pointers (e.g. PC's in the small or medium model). ! 157: Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 ! 158: means that v is a literal, 16 < e < 32 means that v is a pointer to ! 159: the next table, which codes e - 16 bits, and lastly e == 99 indicates ! 160: an unused code. If a code with e == 99 is looked up, this implies an ! 161: error in the data. */ ! 162: struct huft { ! 163: byte e; /* number of extra bits or operation */ ! 164: byte b; /* number of bits in this code or subcode */ ! 165: union { ! 166: UWORD n; /* literal, length base, or distance base */ ! 167: struct huft *t; /* pointer to next level of table */ ! 168: } v; ! 169: }; ! 170: ! 171: ! 172: /* Function prototypes */ ! 173: int huft_build OF((unsigned *, unsigned, unsigned, UWORD *, UWORD *, ! 174: struct huft **, int *)); ! 175: int huft_free OF((struct huft *)); ! 176: void flush OF((unsigned)); ! 177: int inflate_codes OF((struct huft *, struct huft *, int, int)); ! 178: int inflate_stored OF((void)); ! 179: int inflate_fixed OF((void)); ! 180: int inflate_dynamic OF((void)); ! 181: int inflate_block OF((int *)); ! 182: int inflate_entry OF((void)); ! 183: int inflate OF((void)); ! 184: ! 185: ! 186: /* The inflate algorithm uses a sliding 32K byte window on the uncompressed ! 187: stream to find repeated byte strings. This is implemented here as a ! 188: circular buffer. The index is updated simply by incrementing and then ! 189: and'ing with 0x7fff (32K-1). */ ! 190: /* It is left to other modules to supply the 32K area. It is assumed ! 191: to be usable as if it were declared "byte slide[32768];" or as just ! 192: "byte *slide;" and then malloc'ed in the latter case. The definition ! 193: must be in unzip.h, included above. */ ! 194: unsigned wp; /* current position in slide */ ! 195: ! 196: ! 197: /* Tables for deflate from PKZIP's appnote.txt. */ ! 198: static unsigned border[] = { /* Order of the bit length code lengths */ ! 199: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; ! 200: static UWORD cplens[] = { /* Copy lengths for literal codes 257..285 */ ! 201: 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, ! 202: 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; ! 203: /* note: see note #13 above about the 258 in this list. */ ! 204: static UWORD cplext[] = { /* Extra bits for literal codes 257..285 */ ! 205: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, ! 206: 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ ! 207: static UWORD cpdist[] = { /* Copy offsets for distance codes 0..29 */ ! 208: 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, ! 209: 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, ! 210: 8193, 12289, 16385, 24577}; ! 211: static UWORD cpdext[] = { /* Extra bits for distance codes */ ! 212: 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ! 213: 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, ! 214: 12, 12, 13, 13}; ! 215: ! 216: ! 217: ! 218: /* Macros for inflate() bit peeking and grabbing. ! 219: The usage is: ! 220: ! 221: NEEDBITS(j) ! 222: x = b & mask_bits[j]; ! 223: DUMPBITS(j) ! 224: ! 225: where NEEDBITS makes sure that b has at least j bits in it, and ! 226: DUMPBITS removes the bits from b. The macros use the variable k ! 227: for the number of bits in b. Normally, b and k are register ! 228: variables for speed, and are initialized at the begining of a ! 229: routine that uses these macros from a global bit buffer and count. ! 230: ! 231: If we assume that EOB will be the longest code, then we will never ! 232: ask for bits with NEEDBITS that are beyond the end of the stream. ! 233: So, NEEDBITS should not read any more bytes than are needed to ! 234: meet the request. Then no bytes need to be "returned" to the buffer ! 235: at the end of the last block. ! 236: ! 237: However, this assumption is not true for fixed blocks--the EOB code ! 238: is 7 bits, but the other literal/length codes can be 8 or 9 bits. ! 239: (Why PK made the EOB code, which can only occur once in a block, ! 240: the *shortest* code in the set, I'll never know.) However, by ! 241: making the first table have a lookup of seven bits, the EOB code ! 242: will be found in that first lookup, and so will not require that too ! 243: many bits be pulled from the stream. ! 244: */ ! 245: ! 246: ULONG bb; /* bit buffer */ ! 247: unsigned bk; /* bits in bit buffer */ ! 248: ! 249: UWORD bytebuf; ! 250: #if 0 ! 251: #define NEXTBYTE (ReadByte(&bytebuf), bytebuf) ! 252: #define NEEDBITS(n) {while(k<(n)){b|=((ULONG)NEXTBYTE)<<k;k+=8;}} ! 253: #else ! 254: #define NEEDBITS(n) \ ! 255: { while (k < (n)) { \ ! 256: if (--incnt < 0 && FillInBuf()) return 1; \ ! 257: b |= (ULONG)*inptr++ << k; \ ! 258: k += 8; \ ! 259: } } ! 260: #endif ! 261: ! 262: #define DUMPBITS(n) {b>>=(n);k-=(n);} ! 263: ! 264: ! 265: /* ! 266: Huffman code decoding is performed using a multi-level table lookup. ! 267: The fastest way to decode is to simply build a lookup table whose ! 268: size is determined by the longest code. However, the time it takes ! 269: to build this table can also be a factor if the data being decoded ! 270: is not very long. The most common codes are necessarily the ! 271: shortest codes, so those codes dominate the decoding time, and hence ! 272: the speed. The idea is you can have a shorter table that decodes the ! 273: shorter, more probable codes, and then point to subsidiary tables for ! 274: the longer codes. The time it costs to decode the longer codes is ! 275: then traded against the time it takes to make longer tables. ! 276: ! 277: This results of this trade are in the variables lbits and dbits ! 278: below. lbits is the number of bits the first level table for literal/ ! 279: length codes can decode in one step, and dbits is the same thing for ! 280: the distance codes. Subsequent tables are also less than or equal to ! 281: those sizes. These values may be adjusted either when all of the ! 282: codes are shorter than that, in which case the longest code length in ! 283: bits is used, or when the shortest code is *longer* than the requested ! 284: table size, in which case the length of the shortest code in bits is ! 285: used. ! 286: ! 287: There are two different values for the two tables, since they code a ! 288: different number of possibilities each. The literal/length table ! 289: codes 286 possible values, or in a flat code, a little over eight ! 290: bits. The distance table codes 30 possible values, or a little less ! 291: than five bits, flat. The optimum values for speed end up being ! 292: about one bit more than those, so lbits is 8+1 and dbits is 5+1. ! 293: The optimum values may differ though from machine to machine, and ! 294: possibly even between compilers. Your mileage may vary. ! 295: */ ! 296: ! 297: ! 298: int lbits = 9; /* bits in base literal/length lookup table */ ! 299: int dbits = 6; /* bits in base distance lookup table */ ! 300: ! 301: ! 302: /* If BMAX needs to be larger than 16, then h and x[] should be ULONG. */ ! 303: #define BMAX 16 /* maximum bit length of any code (16 for explode) */ ! 304: #define NMAX 288 /* maximum number of codes in any set */ ! 305: ! 306: ! 307: unsigned hufts; /* track memory usage */ ! 308: ! 309: ! 310: int huft_build(b, n, s, d, e, t, m) ! 311: unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ ! 312: unsigned n; /* number of codes (assumed <= NMAX) */ ! 313: unsigned s; /* number of simple-valued codes (0..s-1) */ ! 314: UWORD *d; /* list of base values for non-simple codes */ ! 315: UWORD *e; /* list of extra bits for non-simple codes */ ! 316: struct huft **t; /* result: starting table */ ! 317: int *m; /* maximum lookup bits, returns actual */ ! 318: /* Given a list of code lengths and a maximum table size, make a set of ! 319: tables to decode that set of codes. Return zero on success, one if ! 320: the given code set is incomplete (the tables are still built in this ! 321: case), two if the input is invalid (all zero length codes or an ! 322: oversubscribed set of lengths), and three if not enough memory. */ ! 323: { ! 324: unsigned a; /* counter for codes of length k */ ! 325: unsigned c[BMAX+1]; /* bit length count table */ ! 326: unsigned f; /* i repeats in table every f entries */ ! 327: int g; /* maximum code length */ ! 328: int h; /* table level */ ! 329: register unsigned i; /* counter, current code */ ! 330: register unsigned j; /* counter */ ! 331: register int k; /* number of bits in current code */ ! 332: int l; /* bits per table (returned in m) */ ! 333: register unsigned *p; /* pointer into c[], b[], or v[] */ ! 334: register struct huft *q; /* points to current table */ ! 335: struct huft r; /* table entry for structure assignment */ ! 336: struct huft *u[BMAX]; /* table stack */ ! 337: unsigned v[NMAX]; /* values in order of bit length */ ! 338: register int w; /* bits before this table == (l * h) */ ! 339: unsigned x[BMAX+1]; /* bit offsets, then code stack */ ! 340: unsigned *xp; /* pointer into x */ ! 341: int y; /* number of dummy codes added */ ! 342: unsigned z; /* number of entries in current table */ ! 343: ! 344: ! 345: /* Generate counts for each bit length */ ! 346: memset(c, 0, sizeof(c)); ! 347: p = b; i = n; ! 348: do { ! 349: c[*p++]++; /* assume all entries <= BMAX */ ! 350: } while (--i); ! 351: if (c[0] == n) ! 352: return 2; /* bad input--all zero length codes */ ! 353: ! 354: ! 355: /* Find minimum and maximum length, bound *m by those */ ! 356: l = *m; ! 357: for (j = 1; j <= BMAX; j++) ! 358: if (c[j]) ! 359: break; ! 360: k = j; /* minimum code length */ ! 361: if (l < j) ! 362: l = j; ! 363: for (i = BMAX; i; i--) ! 364: if (c[i]) ! 365: break; ! 366: g = i; /* maximum code length */ ! 367: if (l > i) ! 368: l = i; ! 369: *m = l; ! 370: ! 371: ! 372: /* Adjust last length count to fill out codes, if needed */ ! 373: for (y = 1 << j; j < i; j++, y <<= 1) ! 374: if ((y -= c[j]) < 0) ! 375: return 2; /* bad input: more codes than bits */ ! 376: if ((y -= c[i]) < 0) ! 377: return 2; ! 378: c[i] += y; ! 379: ! 380: ! 381: /* Generate starting offsets into the value table for each length */ ! 382: x[1] = j = 0; ! 383: p = c + 1; xp = x + 2; ! 384: while (--i) { /* note that i == g from above */ ! 385: *xp++ = (j += *p++); ! 386: } ! 387: ! 388: ! 389: /* Make a table of values in order of bit lengths */ ! 390: p = b; i = 0; ! 391: do { ! 392: if ((j = *p++) != 0) ! 393: v[x[j]++] = i; ! 394: } while (++i < n); ! 395: ! 396: ! 397: /* Generate the Huffman codes and for each, make the table entries */ ! 398: x[0] = i = 0; /* first Huffman code is zero */ ! 399: p = v; /* grab values in bit order */ ! 400: h = -1; /* no tables yet--level -1 */ ! 401: w = -l; /* bits decoded == (l * h) */ ! 402: u[0] = NULL; q = NULL; z = 0; /* just to keep compilers happy */ ! 403: ! 404: /* go through the bit lengths (k already is bits in shortest code) */ ! 405: for (; k <= g; k++) ! 406: { ! 407: a = c[k]; ! 408: while (a--) ! 409: { ! 410: /* here i is the Huffman code of length k bits for value *p */ ! 411: /* make tables up to required level */ ! 412: while (k > w + l) ! 413: { ! 414: h++; ! 415: w += l; /* previous table always l bits */ ! 416: ! 417: /* compute minimum size table less than or equal to l bits */ ! 418: z = (z = g - w) > l ? l : z; /* upper limit on table size */ ! 419: if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ ! 420: { /* too few codes for k-w bit table */ ! 421: f -= a + 1; /* deduct codes from patterns left */ ! 422: xp = c + k; ! 423: while (++j < z) /* try smaller tables up to z bits */ ! 424: { ! 425: if ((f <<= 1) <= *++xp) ! 426: break; /* enough codes to use up j bits */ ! 427: f -= *xp; /* else deduct codes from patterns */ ! 428: } ! 429: } ! 430: z = 1 << j; /* table entries for j-bit table */ ! 431: ! 432: /* allocate and link in new table */ ! 433: if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == NULL) ! 434: { ! 435: if (h) ! 436: huft_free(u[0]); ! 437: fprintf(stderr, "\n*** inflate out of memory *** "); ! 438: return 3; /* not enough memory */ ! 439: } ! 440: hufts += z + 1; /* track memory usage */ ! 441: *t = q + 1; /* link to list for huft_free() */ ! 442: *(t = &(q->v.t)) = NULL; ! 443: u[h] = ++q; /* table starts after link */ ! 444: ! 445: /* connect to last table, if there is one */ ! 446: if (h) ! 447: { ! 448: x[h] = i; /* save pattern for backing up */ ! 449: r.b = l; /* bits to dump before this table */ ! 450: r.e = 16 + j; /* bits in this table */ ! 451: r.v.t = q; /* pointer to this table */ ! 452: j = i >> (w - l); /* (get around Turbo C bug) */ ! 453: u[h-1][j] = r; /* connect to last table */ ! 454: } ! 455: } ! 456: ! 457: /* set up table entry in r */ ! 458: r.b = k - w; ! 459: if (p >= v + n) ! 460: r.e = 99; /* out of values--invalid code */ ! 461: else if (*p < s) ! 462: { ! 463: r.e = *p < 256 ? 16 : 15; /* 256 is end-of-block code */ ! 464: r.v.n = *p++; /* simple code is just the value */ ! 465: } ! 466: else ! 467: { ! 468: r.e = e[*p - s]; /* non-simple--look up in lists */ ! 469: r.v.n = d[*p++ - s]; ! 470: } ! 471: ! 472: /* fill code-like entries with r */ ! 473: f = 1 << (k - w); ! 474: for (j = i >> w; j < z; j += f) ! 475: q[j] = r; ! 476: ! 477: /* backwards increment the k-bit code i */ ! 478: for (j = 1 << (k - 1); i & j; j >>= 1) ! 479: i ^= j; ! 480: i ^= j; ! 481: ! 482: /* backup over finished tables */ ! 483: while ((i & ((1 << w) - 1)) != x[h]) ! 484: { ! 485: h--; /* don't need to update q */ ! 486: w -= l; ! 487: } ! 488: } ! 489: } ! 490: ! 491: ! 492: /* Return true (1) if we were given an incomplete table */ ! 493: return y != 0 && n != 1; ! 494: } ! 495: ! 496: ! 497: ! 498: int huft_free(t) ! 499: struct huft *t; /* table to free */ ! 500: /* Free the malloc'ed tables built by huft_build(), which makes a linked ! 501: list of the tables it made, with the links in a dummy first entry of ! 502: each table. */ ! 503: { ! 504: register struct huft *p, *q; ! 505: ! 506: ! 507: /* Go through linked list, freeing from the malloced (t[-1]) address. */ ! 508: p = t; ! 509: while (p != NULL) ! 510: { ! 511: q = (--p)->v.t; ! 512: free(p); ! 513: p = q; ! 514: } ! 515: return 0; ! 516: } ! 517: ! 518: ! 519: ! 520: void flush(w) ! 521: unsigned w; /* number of bytes to flush */ ! 522: /* Do the equivalent of OUTB for the bytes slide[0..w-1]. */ ! 523: { ! 524: unsigned n; ! 525: byte *p; ! 526: ! 527: p = (byte*)slide; ! 528: while (w) ! 529: { ! 530: n = (n = OUTBUFSIZ - outcnt) < w ? n : w; ! 531: memcpy(outptr, p, n); /* try to fill up buffer */ ! 532: outptr += n; ! 533: if ((outcnt += n) == OUTBUFSIZ) ! 534: if (FlushOutput()) /* if full, empty */ ! 535: { ! 536: fprintf(stderr, "\nWrite error.\n"); ! 537: exitPGP(1); ! 538: } ! 539: p += n; ! 540: w -= n; ! 541: } ! 542: } ! 543: ! 544: ! 545: ! 546: int inflate_codes(tl, td, bl, bd) ! 547: struct huft *tl, *td; /* literal/length and distance decoder tables */ ! 548: int bl, bd; /* number of bits decoded by tl[] and td[] */ ! 549: /* inflate (decompress) the codes in a deflated (compressed) block. ! 550: Return an error code or zero if it all goes ok. */ ! 551: { ! 552: register unsigned e; /* table entry flag/number of extra bits */ ! 553: unsigned n, d; /* length and index for copy */ ! 554: unsigned w; /* current window position */ ! 555: struct huft *t; /* pointer to table entry */ ! 556: ULONG ml, md; /* masks for bl and bd bits */ ! 557: register ULONG b; /* bit buffer */ ! 558: register unsigned k; /* number of bits in bit buffer */ ! 559: ! 560: ! 561: /* make local copies of globals */ ! 562: b = bb; /* initialize bit buffer */ ! 563: k = bk; ! 564: w = wp; /* initialize window position */ ! 565: ! 566: ! 567: /* inflate the coded data */ ! 568: ml = mask_bits[bl]; /* precompute masks for speed */ ! 569: md = mask_bits[bd]; ! 570: while (1) /* do until end of block */ ! 571: { ! 572: NEEDBITS(bl) ! 573: if ((e = (t = tl + (b & ml))->e) > 16) ! 574: do { ! 575: if (e == 99) ! 576: return 1; ! 577: DUMPBITS(t->b) ! 578: e -= 16; ! 579: NEEDBITS(e) ! 580: } while ((e = (t = t->v.t + (b & mask_bits[e]))->e) > 16); ! 581: DUMPBITS(t->b) ! 582: if (e == 16) /* then it's a literal */ ! 583: { ! 584: slide[w++] = t->v.n; ! 585: if (w == WSIZE) ! 586: { ! 587: flush(w); ! 588: w = 0; ! 589: } ! 590: } ! 591: else /* it's an EOB or a length */ ! 592: { ! 593: /* exit if end of block */ ! 594: if (e == 15) ! 595: break; ! 596: ! 597: /* get length of block to copy */ ! 598: NEEDBITS(e) ! 599: n = t->v.n + (b & mask_bits[e]); ! 600: DUMPBITS(e); ! 601: ! 602: /* decode distance of block to copy */ ! 603: NEEDBITS(bd) ! 604: if ((e = (t = td + (b & md))->e) > 16) ! 605: do { ! 606: if (e == 99) ! 607: return 1; ! 608: DUMPBITS(t->b) ! 609: e -= 16; ! 610: NEEDBITS(e) ! 611: } while ((e = (t = t->v.t + (b & mask_bits[e]))->e) > 16); ! 612: DUMPBITS(t->b) ! 613: NEEDBITS(e) ! 614: d = w - t->v.n - (b & mask_bits[e]); ! 615: DUMPBITS(e) ! 616: ! 617: /* do the copy */ ! 618: do { ! 619: n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); ! 620: #ifndef NOMEMCPY ! 621: if (w - d >= e) /* (this test assumes unsigned comparison) */ ! 622: { ! 623: memcpy(slide + w, slide + d, e); ! 624: w += e; ! 625: d += e; ! 626: } ! 627: else /* do it slow to avoid memcpy() overlap */ ! 628: #endif /* !NOMEMCPY */ ! 629: do { ! 630: slide[w++] = slide[d++]; ! 631: } while (--e); ! 632: if (w == WSIZE) ! 633: { ! 634: flush(w); ! 635: w = 0; ! 636: } ! 637: } while (n); ! 638: } ! 639: } ! 640: ! 641: ! 642: /* restore the globals from the locals */ ! 643: wp = w; /* restore global window pointer */ ! 644: bb = b; /* restore global bit buffer */ ! 645: bk = k; ! 646: ! 647: ! 648: /* done */ ! 649: return 0; ! 650: } ! 651: ! 652: ! 653: ! 654: int inflate_stored() ! 655: /* "decompress" an inflated type 0 (stored) block. */ ! 656: { ! 657: unsigned n; /* number of bytes in block */ ! 658: unsigned w; /* current window position */ ! 659: register ULONG b; /* bit buffer */ ! 660: register unsigned k; /* number of bits in bit buffer */ ! 661: ! 662: ! 663: /* make local copies of globals */ ! 664: b = bb; /* initialize bit buffer */ ! 665: k = bk; ! 666: w = wp; /* initialize window position */ ! 667: ! 668: ! 669: /* go to byte boundary */ ! 670: n = k & 7; ! 671: DUMPBITS(n); ! 672: ! 673: ! 674: /* get the length and its complement */ ! 675: NEEDBITS(16) ! 676: n = b & 0xffff; ! 677: DUMPBITS(16) ! 678: NEEDBITS(16) ! 679: if (n != ((~b) & 0xffff)) ! 680: return 1; /* error in compressed data */ ! 681: DUMPBITS(16) ! 682: ! 683: ! 684: /* read and output the compressed data */ ! 685: while (n--) ! 686: { ! 687: NEEDBITS(8) ! 688: slide[w++] = b; ! 689: if (w == WSIZE) ! 690: { ! 691: flush(w); ! 692: w = 0; ! 693: } ! 694: DUMPBITS(8) ! 695: } ! 696: ! 697: ! 698: /* restore the globals from the locals */ ! 699: wp = w; /* restore global window pointer */ ! 700: bb = b; /* restore global bit buffer */ ! 701: bk = k; ! 702: return 0; ! 703: } ! 704: ! 705: ! 706: ! 707: int inflate_fixed() ! 708: /* decompress an inflated type 1 (fixed Huffman codes) block. We should ! 709: either replace this with a custom decoder, or at least precompute the ! 710: Huffman tables. */ ! 711: { ! 712: int i; /* temporary variable */ ! 713: struct huft *tl; /* literal/length code table */ ! 714: struct huft *td; /* distance code table */ ! 715: int bl; /* lookup bits for tl */ ! 716: int bd; /* lookup bits for td */ ! 717: unsigned l[288]; /* length list for huft_build */ ! 718: ! 719: ! 720: /* set up literal table */ ! 721: for (i = 0; i < 144; i++) ! 722: l[i] = 8; ! 723: for (; i < 256; i++) ! 724: l[i] = 9; ! 725: for (; i < 280; i++) ! 726: l[i] = 7; ! 727: for (; i < 288; i++) /* make a complete, but wrong code set */ ! 728: l[i] = 8; ! 729: bl = 7; ! 730: if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) ! 731: return i; ! 732: ! 733: ! 734: /* set up distance table */ ! 735: for (i = 0; i < 30; i++) /* make an incomplete code set */ ! 736: l[i] = 5; ! 737: bd = 5; ! 738: if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) ! 739: { ! 740: huft_free(tl); ! 741: return i; ! 742: } ! 743: ! 744: ! 745: /* decompress until an end-of-block code */ ! 746: if (inflate_codes(tl, td, bl, bd)) ! 747: return 1; ! 748: ! 749: ! 750: /* free the decoding tables, return */ ! 751: huft_free(tl); ! 752: huft_free(td); ! 753: return 0; ! 754: } ! 755: ! 756: ! 757: ! 758: int inflate_dynamic() ! 759: /* decompress an inflated type 2 (dynamic Huffman codes) block. */ ! 760: { ! 761: int i; /* temporary variables */ ! 762: unsigned j; ! 763: unsigned l; /* last length */ ! 764: unsigned m; /* mask for bit lengths table */ ! 765: unsigned n; /* number of lengths to get */ ! 766: struct huft *tl; /* literal/length code table */ ! 767: struct huft *td; /* distance code table */ ! 768: int bl; /* lookup bits for tl */ ! 769: int bd; /* lookup bits for td */ ! 770: unsigned nb; /* number of bit length codes */ ! 771: unsigned nl; /* number of literal/length codes */ ! 772: unsigned nd; /* number of distance codes */ ! 773: unsigned ll[286+30]; /* literal/length and distance code lengths */ ! 774: register ULONG b; /* bit buffer */ ! 775: register unsigned k; /* number of bits in bit buffer */ ! 776: ! 777: ! 778: /* make local bit buffer */ ! 779: b = bb; ! 780: k = bk; ! 781: ! 782: ! 783: /* read in table lengths */ ! 784: NEEDBITS(5) ! 785: nl = 257 + (b & 0x1f); /* number of literal/length codes */ ! 786: DUMPBITS(5) ! 787: NEEDBITS(5) ! 788: nd = 1 + (b & 0x1f); /* number of distance codes */ ! 789: DUMPBITS(5) ! 790: NEEDBITS(4) ! 791: nb = 4 + (b & 0xf); /* number of bit length codes */ ! 792: DUMPBITS(4) ! 793: if (nl > 286 || nd > 30) ! 794: return 1; /* bad lengths */ ! 795: ! 796: ! 797: /* read in bit-length-code lengths */ ! 798: for (i = 0; i < nb; i++) ! 799: { ! 800: NEEDBITS(3) ! 801: ll[border[i]] = b & 7; ! 802: DUMPBITS(3) ! 803: } ! 804: for (; i < 19; i++) ! 805: ll[border[i]] = 0; ! 806: ! 807: ! 808: /* build decoding table for trees--single level, 7 bit lookup */ ! 809: bl = 7; ! 810: if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) ! 811: { ! 812: if (i == 1) ! 813: huft_free(tl); ! 814: return i; /* incomplete code set */ ! 815: } ! 816: ! 817: ! 818: /* read in literal and distance code lengths */ ! 819: n = nl + nd; ! 820: m = mask_bits[bl]; ! 821: i = l = 0; ! 822: while (i < n) ! 823: { ! 824: NEEDBITS(bl) ! 825: j = (td = tl + (b & m))->b; ! 826: DUMPBITS(j) ! 827: j = td->v.n; ! 828: if (j < 16) /* length of code in bits (0..15) */ ! 829: ll[i++] = l = j; /* save last length in l */ ! 830: else if (j == 16) /* repeat last length 3 to 6 times */ ! 831: { ! 832: NEEDBITS(2) ! 833: j = 3 + (b & 3); ! 834: DUMPBITS(2) ! 835: if (i + j > n) ! 836: return 1; ! 837: while (j--) ! 838: ll[i++] = l; ! 839: } ! 840: else if (j == 17) /* 3 to 10 zero length codes */ ! 841: { ! 842: NEEDBITS(3) ! 843: j = 3 + (b & 7); ! 844: DUMPBITS(3) ! 845: if (i + j > n) ! 846: return 1; ! 847: while (j--) ! 848: ll[i++] = 0; ! 849: l = 0; ! 850: } ! 851: else /* j == 18: 11 to 138 zero length codes */ ! 852: { ! 853: NEEDBITS(7) ! 854: j = 11 + (b & 0x7f); ! 855: DUMPBITS(7) ! 856: if (i + j > n) ! 857: return 1; ! 858: while (j--) ! 859: ll[i++] = 0; ! 860: l = 0; ! 861: } ! 862: } ! 863: ! 864: ! 865: /* free decoding table for trees */ ! 866: huft_free(tl); ! 867: ! 868: ! 869: /* restore the global bit buffer */ ! 870: bb = b; ! 871: bk = k; ! 872: ! 873: ! 874: /* build the decoding tables for literal/length and distance codes */ ! 875: bl = lbits; ! 876: if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) ! 877: { ! 878: if (i == 1) ! 879: huft_free(tl); ! 880: return i; /* incomplete code set */ ! 881: } ! 882: bd = dbits; ! 883: if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) ! 884: { ! 885: if (i == 1) ! 886: huft_free(td); ! 887: huft_free(tl); ! 888: return i; /* incomplete code set */ ! 889: } ! 890: ! 891: ! 892: /* decompress until an end-of-block code */ ! 893: if (inflate_codes(tl, td, bl, bd)) ! 894: return 1; ! 895: ! 896: ! 897: /* free the decoding tables, return */ ! 898: huft_free(tl); ! 899: huft_free(td); ! 900: return 0; ! 901: } ! 902: ! 903: ! 904: ! 905: int inflate_block(e) ! 906: int *e; /* last block flag */ ! 907: /* decompress an inflated block */ ! 908: { ! 909: unsigned t; /* block type */ ! 910: register ULONG b; /* bit buffer */ ! 911: register unsigned k; /* number of bits in bit buffer */ ! 912: ! 913: ! 914: /* make local bit buffer */ ! 915: b = bb; ! 916: k = bk; ! 917: ! 918: ! 919: /* read in last block bit */ ! 920: NEEDBITS(1) ! 921: *e = b & 1; ! 922: DUMPBITS(1) ! 923: ! 924: ! 925: /* read in block type */ ! 926: NEEDBITS(2) ! 927: t = b & 3; ! 928: DUMPBITS(2) ! 929: ! 930: ! 931: /* restore the global bit buffer */ ! 932: bb = b; ! 933: bk = k; ! 934: ! 935: ! 936: /* inflate that block type */ ! 937: if (t == 2) ! 938: return inflate_dynamic(); ! 939: if (t == 0) ! 940: return inflate_stored(); ! 941: if (t == 1) ! 942: return inflate_fixed(); ! 943: ! 944: ! 945: /* bad block type */ ! 946: return 2; ! 947: } ! 948: ! 949: ! 950: ! 951: int inflate_entry() ! 952: /* decompress an inflated entry */ ! 953: { ! 954: int e; /* last block flag */ ! 955: int r; /* result code */ ! 956: unsigned h; /* maximum struct huft's malloc'ed */ ! 957: ! 958: ! 959: /* initialize window, bit buffer */ ! 960: wp = 0; ! 961: bk = 0; ! 962: bb = 0; ! 963: ! 964: ! 965: /* decompress until the last block */ ! 966: h = 0; ! 967: do { ! 968: hufts = 0; ! 969: if ((r = inflate_block(&e)) != 0) ! 970: return r; ! 971: if (hufts > h) ! 972: h = hufts; ! 973: #ifdef MACTC5 ! 974: mac_poll_for_break(); ! 975: #endif ! 976: } while (!e); ! 977: ! 978: ! 979: /* flush out slide */ ! 980: flush(wp); ! 981: ! 982: ! 983: /* return success */ ! 984: #ifdef DEBUG ! 985: fprintf(stderr, "<%u> ", h); ! 986: #endif /* DEBUG */ ! 987: return 0; ! 988: } ! 989: ! 990: ! 991: int inflate() ! 992: /* ignore the return code for now ... */ ! 993: { ! 994: int status; ! 995: ! 996: #ifdef DYN_ALLOC ! 997: slide = (char*) calloc((unsigned)WSIZE, 2*sizeof(char)); ! 998: /* Note that inflate only needs WSIZE bytes, but the slide ! 999: * array is shared with deflate, which needs 2*WISZE bytes. ! 1000: */ ! 1001: if (slide==NULL) err(4, ""); ! 1002: #endif ! 1003: ! 1004: status = inflate_entry(); ! 1005: ! 1006: #ifdef DYN_ALLOC ! 1007: free(slide); ! 1008: slide = NULL; ! 1009: #endif ! 1010: ! 1011: return status; ! 1012: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.