![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to explode.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / bin / unzip|
Return to explode.c CVS log | Up to [MW Coherent from dump] / coherent / b / bin / unzip |
1.1 ! root 1: /* explode.c -- Not copyrighted 1992 by Mark Adler ! 2: version c7, 27 June 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: c1 30 Mar 92 M. Adler explode that uses huft_build from inflate ! 13: (this gives over a 70% speed improvement ! 14: over the original unimplode.c, which ! 15: decoded a bit at a time) ! 16: c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. ! 17: c3 10 Apr 92 M. Adler added a little memory tracking if DEBUG ! 18: c4 11 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy() ! 19: c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducing ! 20: the 32K window size for specialized ! 21: applications. ! 22: c6 31 May 92 M. Adler added typecasts to eliminate some warnings ! 23: c7 27 Jun 92 G. Roelofs added more typecasts ! 24: */ ! 25: ! 26: ! 27: /* ! 28: Explode imploded (PKZIP method 6 compressed) data. This compression ! 29: method searches for as much of the current string of bytes (up to a length ! 30: of ~320) in the previous 4K or 8K bytes. If it doesn't find any matches ! 31: (of at least length 2 or 3), it codes the next byte. Otherwise, it codes ! 32: the length of the matched string and its distance backwards from the ! 33: current position. Single bytes ("literals") are preceded by a one (a ! 34: single bit) and are either uncoded (the eight bits go directly into the ! 35: compressed stream for a total of nine bits) or Huffman coded with a ! 36: supplied literal code tree. If literals are coded, then the minimum match ! 37: length is three, otherwise it is two. ! 38: ! 39: There are therefore four kinds of imploded streams: 8K search with coded ! 40: literals (min match = 3), 4K search with coded literals (min match = 3), ! 41: 8K with uncoded literals (min match = 2), and 4K with uncoded literals ! 42: (min match = 2). The kind of stream is identified in two bits of a ! 43: general purpose bit flag that is outside of the compressed stream. ! 44: ! 45: Distance-length pairs are always coded. Distance-length pairs for matched ! 46: strings are preceded by a zero bit (to distinguish them from literals) and ! 47: are always coded. The distance comes first and is either the low six (4K) ! 48: or low seven (8K) bits of the distance (uncoded), followed by the high six ! 49: bits of the distance coded. Then the length is six bits coded (0..63 + ! 50: min match length), and if the maximum such length is coded, then it's ! 51: followed by another eight bits (uncoded) to be added to the coded length. ! 52: This gives a match length range of 2..320 or 3..321 bytes. ! 53: ! 54: The literal, length, and distance codes are all represented in a slightly ! 55: compressed form themselves. What is sent are the lengths of the codes for ! 56: each value, which is sufficient to construct the codes. Each byte of the ! 57: code representation is the code length (the low four bits representing ! 58: 1..16), and the number of values sequentially with that length (the high ! 59: four bits also representing 1..16). There are 256 literal code values (if ! 60: literals are coded), 64 length code values, and 64 distance code values, ! 61: in that order at the beginning of the compressed stream. Each set of code ! 62: values is preceded (redundantly) with a byte indicating how many bytes are ! 63: in the code description that follows, in the range 1..256. ! 64: ! 65: The codes themselves are decoded using tables made by huft_build() from ! 66: the bit lengths. That routine and its comments are in the inflate.c ! 67: module. ! 68: */ ! 69: ! 70: #include "unzip.h" /* this must supply the slide[] (byte) array */ ! 71: ! 72: #ifndef WSIZE ! 73: # define WSIZE 0x8000 /* window size--must be a power of two, and at least ! 74: 8K for zip's implode method */ ! 75: #endif /* !WSIZE */ ! 76: ! 77: ! 78: struct huft { ! 79: byte e; /* number of extra bits or operation */ ! 80: byte b; /* number of bits in this code or subcode */ ! 81: union { ! 82: UWORD n; /* literal, length base, or distance base */ ! 83: struct huft *t; /* pointer to next level of table */ ! 84: } v; ! 85: }; ! 86: ! 87: /* Function prototypes */ ! 88: /* routines from inflate.c */ ! 89: extern unsigned hufts; ! 90: int huft_build OF((unsigned *, unsigned, unsigned, UWORD *, UWORD *, ! 91: struct huft **, int *)); ! 92: int huft_free OF((struct huft *)); ! 93: void flush OF((unsigned)); ! 94: ! 95: /* routines here */ ! 96: int get_tree OF((unsigned *, unsigned)); ! 97: int explode_lit8 OF((struct huft *, struct huft *, struct huft *, ! 98: int, int, int)); ! 99: int explode_lit4 OF((struct huft *, struct huft *, struct huft *, ! 100: int, int, int)); ! 101: int explode_nolit8 OF((struct huft *, struct huft *, int, int)); ! 102: int explode_nolit4 OF((struct huft *, struct huft *, int, int)); ! 103: int explode OF((void)); ! 104: ! 105: ! 106: /* The implode algorithm uses a sliding 4K or 8K byte window on the ! 107: uncompressed stream to find repeated byte strings. This is implemented ! 108: here as a circular buffer. The index is updated simply by incrementing ! 109: and then and'ing with 0x0fff (4K-1) or 0x1fff (8K-1). Here, the 32K ! 110: buffer of inflate is used, and it works just as well to always have ! 111: a 32K circular buffer, so the index is anded with 0x7fff. This is ! 112: done to allow the window to also be used as the output buffer. */ ! 113: /* This must be supplied in an external module useable like "byte slide[8192];" ! 114: or "byte *slide;", where the latter would be malloc'ed. In unzip, slide[] ! 115: is actually a 32K area for use by inflate, which uses a 32K sliding window. ! 116: */ ! 117: ! 118: ! 119: /* Tables for length and distance */ ! 120: UWORD cplen2[] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ! 121: 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, ! 122: 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, ! 123: 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65}; ! 124: UWORD cplen3[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ! 125: 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, ! 126: 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, ! 127: 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66}; ! 128: UWORD extra[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ! 129: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ! 130: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ! 131: 8}; ! 132: UWORD cpdist4[] = {1, 65, 129, 193, 257, 321, 385, 449, 513, 577, 641, 705, ! 133: 769, 833, 897, 961, 1025, 1089, 1153, 1217, 1281, 1345, 1409, 1473, ! 134: 1537, 1601, 1665, 1729, 1793, 1857, 1921, 1985, 2049, 2113, 2177, ! 135: 2241, 2305, 2369, 2433, 2497, 2561, 2625, 2689, 2753, 2817, 2881, ! 136: 2945, 3009, 3073, 3137, 3201, 3265, 3329, 3393, 3457, 3521, 3585, ! 137: 3649, 3713, 3777, 3841, 3905, 3969, 4033}; ! 138: UWORD cpdist8[] = {1, 129, 257, 385, 513, 641, 769, 897, 1025, 1153, 1281, ! 139: 1409, 1537, 1665, 1793, 1921, 2049, 2177, 2305, 2433, 2561, 2689, ! 140: 2817, 2945, 3073, 3201, 3329, 3457, 3585, 3713, 3841, 3969, 4097, ! 141: 4225, 4353, 4481, 4609, 4737, 4865, 4993, 5121, 5249, 5377, 5505, ! 142: 5633, 5761, 5889, 6017, 6145, 6273, 6401, 6529, 6657, 6785, 6913, ! 143: 7041, 7169, 7297, 7425, 7553, 7681, 7809, 7937, 8065}; ! 144: ! 145: ! 146: /* Macros for inflate() bit peeking and grabbing. ! 147: The usage is: ! 148: ! 149: NEEDBITS(j) ! 150: x = b & mask_bits[j]; ! 151: DUMPBITS(j) ! 152: ! 153: where NEEDBITS makes sure that b has at least j bits in it, and ! 154: DUMPBITS removes the bits from b. The macros use the variable k ! 155: for the number of bits in b. Normally, b and k are register ! 156: variables for speed. ! 157: */ ! 158: ! 159: extern UWORD bytebuf; /* (use the one in inflate.c) */ ! 160: #define NEXTBYTE (ReadByte(&bytebuf), bytebuf) ! 161: #define NEEDBITS(n) {while(k<(n)){b|=((ULONG)NEXTBYTE)<<k;k+=8;}} ! 162: #define DUMPBITS(n) {b>>=(n);k-=(n);} ! 163: ! 164: ! 165: ! 166: int get_tree(l, n) ! 167: unsigned *l; /* bit lengths */ ! 168: unsigned n; /* number expected */ ! 169: /* Get the bit lengths for a code representation from the compressed ! 170: stream. If get_tree() returns 4, then there is an error in the data. ! 171: Otherwise zero is returned. */ ! 172: { ! 173: unsigned i; /* bytes remaining in list */ ! 174: unsigned k; /* lengths entered */ ! 175: unsigned j; /* number of codes */ ! 176: unsigned b; /* bit length for those codes */ ! 177: ! 178: ! 179: /* get bit lengths */ ! 180: ReadByte(&bytebuf); ! 181: i = bytebuf + 1; /* length/count pairs to read */ ! 182: k = 0; /* next code */ ! 183: do { ! 184: ReadByte(&bytebuf); ! 185: b = ((j = bytebuf) & 0xf) + 1; /* bits in code (1..16) */ ! 186: j = ((j & 0xf0) >> 4) + 1; /* codes with those bits (1..16) */ ! 187: if (k + j > n) ! 188: return 4; /* don't overflow l[] */ ! 189: do { ! 190: l[k++] = b; ! 191: } while (--j); ! 192: } while (--i); ! 193: return k != n ? 4 : 0; /* should have read n of them */ ! 194: } ! 195: ! 196: ! 197: ! 198: int explode_lit8(tb, tl, td, bb, bl, bd) ! 199: struct huft *tb, *tl, *td; /* literal, length, and distance tables */ ! 200: int bb, bl, bd; /* number of bits decoded by those */ ! 201: /* Decompress the imploded data using coded literals and an 8K sliding ! 202: window. */ ! 203: { ! 204: longint s; /* bytes to decompress */ ! 205: register unsigned e; /* table entry flag/number of extra bits */ ! 206: unsigned n, d; /* length and index for copy */ ! 207: unsigned w; /* current window position */ ! 208: struct huft *t; /* pointer to table entry */ ! 209: unsigned mb, ml, md; /* masks for bb, bl, and bd bits */ ! 210: register ULONG b; /* bit buffer */ ! 211: register unsigned k; /* number of bits in bit buffer */ ! 212: unsigned u; /* true if unflushed */ ! 213: ! 214: ! 215: /* explode the coded data */ ! 216: b = k = w = 0; /* initialize bit buffer, window */ ! 217: u = 1; /* buffer unflushed */ ! 218: mb = mask_bits[bb]; /* precompute masks for speed */ ! 219: ml = mask_bits[bl]; ! 220: md = mask_bits[bd]; ! 221: s = ucsize; ! 222: while (s > 0) /* do until ucsize bytes uncompressed */ ! 223: { ! 224: NEEDBITS(1) ! 225: if (b & 1) /* then literal--decode it */ ! 226: { ! 227: DUMPBITS(1) ! 228: s--; ! 229: NEEDBITS((unsigned)bb) /* get coded literal */ ! 230: if ((e = (t = tb + ((~(unsigned)b) & mb))->e) > 16) ! 231: do { ! 232: if (e == 99) ! 233: return 1; ! 234: DUMPBITS(t->b) ! 235: e -= 16; ! 236: NEEDBITS(e) ! 237: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 238: DUMPBITS(t->b) ! 239: slide[w++] = (byte)t->v.n; ! 240: if (w == WSIZE) ! 241: { ! 242: flush(w); ! 243: w = u = 0; ! 244: } ! 245: } ! 246: else /* else distance/length */ ! 247: { ! 248: DUMPBITS(1) ! 249: NEEDBITS(7) /* get distance low bits */ ! 250: d = (unsigned)b & 0x7f; ! 251: DUMPBITS(7) ! 252: NEEDBITS((unsigned)bd) /* get coded distance high bits */ ! 253: if ((e = (t = td + ((~(unsigned)b) & md))->e) > 16) ! 254: do { ! 255: if (e == 99) ! 256: return 1; ! 257: DUMPBITS(t->b) ! 258: e -= 16; ! 259: NEEDBITS(e) ! 260: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 261: DUMPBITS(t->b) ! 262: d = w - d - t->v.n; /* construct offset */ ! 263: NEEDBITS((unsigned)bl) /* get coded length */ ! 264: if ((e = (t = tl + ((~(unsigned)b) & ml))->e) > 16) ! 265: do { ! 266: if (e == 99) ! 267: return 1; ! 268: DUMPBITS(t->b) ! 269: e -= 16; ! 270: NEEDBITS(e) ! 271: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 272: DUMPBITS(t->b) ! 273: n = t->v.n; ! 274: if (e) /* get length extra bits */ ! 275: { ! 276: NEEDBITS(8) ! 277: n += (unsigned)b & 0xff; ! 278: DUMPBITS(8) ! 279: } ! 280: ! 281: /* do the copy */ ! 282: s -= n; ! 283: do { ! 284: n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); ! 285: if (u && w <= d) ! 286: { ! 287: memset(slide + w, 0, e); ! 288: w += e; ! 289: d += e; ! 290: } ! 291: else ! 292: #ifndef NOMEMCPY ! 293: if (w - d >= e) /* (this test assumes unsigned comparison) */ ! 294: { ! 295: memcpy(slide + w, slide + d, e); ! 296: w += e; ! 297: d += e; ! 298: } ! 299: else /* do it slow to avoid memcpy() overlap */ ! 300: #endif /* !NOMEMCPY */ ! 301: do { ! 302: slide[w++] = slide[d++]; ! 303: } while (--e); ! 304: if (w == WSIZE) ! 305: { ! 306: flush(w); ! 307: w = u = 0; ! 308: } ! 309: } while (n); ! 310: } ! 311: } ! 312: ! 313: /* flush out slide */ ! 314: flush(w); ! 315: return csize ? 5 : 0; /* should have read csize bytes */ ! 316: } ! 317: ! 318: ! 319: ! 320: int explode_lit4(tb, tl, td, bb, bl, bd) ! 321: struct huft *tb, *tl, *td; /* literal, length, and distance tables */ ! 322: int bb, bl, bd; /* number of bits decoded by those */ ! 323: /* Decompress the imploded data using coded literals and a 4K sliding ! 324: window. */ ! 325: { ! 326: longint s; /* bytes to decompress */ ! 327: register unsigned e; /* table entry flag/number of extra bits */ ! 328: unsigned n, d; /* length and index for copy */ ! 329: unsigned w; /* current window position */ ! 330: struct huft *t; /* pointer to table entry */ ! 331: unsigned mb, ml, md; /* masks for bb, bl, and bd bits */ ! 332: register ULONG b; /* bit buffer */ ! 333: register unsigned k; /* number of bits in bit buffer */ ! 334: unsigned u; /* true if unflushed */ ! 335: ! 336: ! 337: /* explode the coded data */ ! 338: b = k = w = 0; /* initialize bit buffer, window */ ! 339: u = 1; /* buffer unflushed */ ! 340: mb = mask_bits[bb]; /* precompute masks for speed */ ! 341: ml = mask_bits[bl]; ! 342: md = mask_bits[bd]; ! 343: s = ucsize; ! 344: while (s > 0) /* do until ucsize bytes uncompressed */ ! 345: { ! 346: NEEDBITS(1) ! 347: if (b & 1) /* then literal--decode it */ ! 348: { ! 349: DUMPBITS(1) ! 350: s--; ! 351: NEEDBITS((unsigned)bb) /* get coded literal */ ! 352: if ((e = (t = tb + ((~(unsigned)b) & mb))->e) > 16) ! 353: do { ! 354: if (e == 99) ! 355: return 1; ! 356: DUMPBITS(t->b) ! 357: e -= 16; ! 358: NEEDBITS(e) ! 359: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 360: DUMPBITS(t->b) ! 361: slide[w++] = (byte)t->v.n; ! 362: if (w == WSIZE) ! 363: { ! 364: flush(w); ! 365: w = u = 0; ! 366: } ! 367: } ! 368: else /* else distance/length */ ! 369: { ! 370: DUMPBITS(1) ! 371: NEEDBITS(6) /* get distance low bits */ ! 372: d = (unsigned)b & 0x3f; ! 373: DUMPBITS(6) ! 374: NEEDBITS((unsigned)bd) /* get coded distance high bits */ ! 375: if ((e = (t = td + ((~(unsigned)b) & md))->e) > 16) ! 376: do { ! 377: if (e == 99) ! 378: return 1; ! 379: DUMPBITS(t->b) ! 380: e -= 16; ! 381: NEEDBITS(e) ! 382: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 383: DUMPBITS(t->b) ! 384: d = w - d - t->v.n; /* construct offset */ ! 385: NEEDBITS((unsigned)bl) /* get coded length */ ! 386: if ((e = (t = tl + ((~(unsigned)b) & ml))->e) > 16) ! 387: do { ! 388: if (e == 99) ! 389: return 1; ! 390: DUMPBITS(t->b) ! 391: e -= 16; ! 392: NEEDBITS(e) ! 393: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 394: DUMPBITS(t->b) ! 395: n = t->v.n; ! 396: if (e) /* get length extra bits */ ! 397: { ! 398: NEEDBITS(8) ! 399: n += (unsigned)b & 0xff; ! 400: DUMPBITS(8) ! 401: } ! 402: ! 403: /* do the copy */ ! 404: s -= n; ! 405: do { ! 406: n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); ! 407: if (u && w <= d) ! 408: { ! 409: memset(slide + w, 0, e); ! 410: w += e; ! 411: d += e; ! 412: } ! 413: else ! 414: #ifndef NOMEMCPY ! 415: if (w - d >= e) /* (this test assumes unsigned comparison) */ ! 416: { ! 417: memcpy(slide + w, slide + d, e); ! 418: w += e; ! 419: d += e; ! 420: } ! 421: else /* do it slow to avoid memcpy() overlap */ ! 422: #endif /* !NOMEMCPY */ ! 423: do { ! 424: slide[w++] = slide[d++]; ! 425: } while (--e); ! 426: if (w == WSIZE) ! 427: { ! 428: flush(w); ! 429: w = u = 0; ! 430: } ! 431: } while (n); ! 432: } ! 433: } ! 434: ! 435: /* flush out slide */ ! 436: flush(w); ! 437: return csize ? 5 : 0; /* should have read csize bytes */ ! 438: } ! 439: ! 440: ! 441: ! 442: int explode_nolit8(tl, td, bl, bd) ! 443: struct huft *tl, *td; /* length and distance decoder tables */ ! 444: int bl, bd; /* number of bits decoded by tl[] and td[] */ ! 445: /* Decompress the imploded data using uncoded literals and an 8K sliding ! 446: window. */ ! 447: { ! 448: longint s; /* bytes to decompress */ ! 449: register unsigned e; /* table entry flag/number of extra bits */ ! 450: unsigned n, d; /* length and index for copy */ ! 451: unsigned w; /* current window position */ ! 452: struct huft *t; /* pointer to table entry */ ! 453: unsigned ml, md; /* masks for bl and bd bits */ ! 454: register ULONG b; /* bit buffer */ ! 455: register unsigned k; /* number of bits in bit buffer */ ! 456: unsigned u; /* true if unflushed */ ! 457: ! 458: ! 459: /* explode the coded data */ ! 460: b = k = w = 0; /* initialize bit buffer, window */ ! 461: u = 1; /* buffer unflushed */ ! 462: ml = mask_bits[bl]; /* precompute masks for speed */ ! 463: md = mask_bits[bd]; ! 464: s = ucsize; ! 465: while (s > 0) /* do until ucsize bytes uncompressed */ ! 466: { ! 467: NEEDBITS(1) ! 468: if (b & 1) /* then literal--get eight bits */ ! 469: { ! 470: DUMPBITS(1) ! 471: s--; ! 472: NEEDBITS(8) ! 473: slide[w++] = (byte)b; ! 474: if (w == WSIZE) ! 475: { ! 476: flush(w); ! 477: w = u = 0; ! 478: } ! 479: DUMPBITS(8) ! 480: } ! 481: else /* else distance/length */ ! 482: { ! 483: DUMPBITS(1) ! 484: NEEDBITS(7) /* get distance low bits */ ! 485: d = (unsigned)b & 0x7f; ! 486: DUMPBITS(7) ! 487: NEEDBITS((unsigned)bd) /* get coded distance high bits */ ! 488: if ((e = (t = td + ((~(unsigned)b) & md))->e) > 16) ! 489: do { ! 490: if (e == 99) ! 491: return 1; ! 492: DUMPBITS(t->b) ! 493: e -= 16; ! 494: NEEDBITS(e) ! 495: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 496: DUMPBITS(t->b) ! 497: d = w - d - t->v.n; /* construct offset */ ! 498: NEEDBITS((unsigned)bl) /* get coded length */ ! 499: if ((e = (t = tl + ((~(unsigned)b) & ml))->e) > 16) ! 500: do { ! 501: if (e == 99) ! 502: return 1; ! 503: DUMPBITS(t->b) ! 504: e -= 16; ! 505: NEEDBITS(e) ! 506: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 507: DUMPBITS(t->b) ! 508: n = t->v.n; ! 509: if (e) /* get length extra bits */ ! 510: { ! 511: NEEDBITS(8) ! 512: n += (unsigned)b & 0xff; ! 513: DUMPBITS(8) ! 514: } ! 515: ! 516: /* do the copy */ ! 517: s -= n; ! 518: do { ! 519: n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); ! 520: if (u && w <= d) ! 521: { ! 522: memset(slide + w, 0, e); ! 523: w += e; ! 524: d += e; ! 525: } ! 526: else ! 527: #ifndef NOMEMCPY ! 528: if (w - d >= e) /* (this test assumes unsigned comparison) */ ! 529: { ! 530: memcpy(slide + w, slide + d, e); ! 531: w += e; ! 532: d += e; ! 533: } ! 534: else /* do it slow to avoid memcpy() overlap */ ! 535: #endif /* !NOMEMCPY */ ! 536: do { ! 537: slide[w++] = slide[d++]; ! 538: } while (--e); ! 539: if (w == WSIZE) ! 540: { ! 541: flush(w); ! 542: w = u = 0; ! 543: } ! 544: } while (n); ! 545: } ! 546: } ! 547: ! 548: /* flush out slide */ ! 549: flush(w); ! 550: return csize ? 5 : 0; /* should have read csize bytes */ ! 551: } ! 552: ! 553: ! 554: ! 555: int explode_nolit4(tl, td, bl, bd) ! 556: struct huft *tl, *td; /* length and distance decoder tables */ ! 557: int bl, bd; /* number of bits decoded by tl[] and td[] */ ! 558: /* Decompress the imploded data using uncoded literals and a 4K sliding ! 559: window. */ ! 560: { ! 561: longint s; /* bytes to decompress */ ! 562: register unsigned e; /* table entry flag/number of extra bits */ ! 563: unsigned n, d; /* length and index for copy */ ! 564: unsigned w; /* current window position */ ! 565: struct huft *t; /* pointer to table entry */ ! 566: unsigned ml, md; /* masks for bl and bd bits */ ! 567: register ULONG b; /* bit buffer */ ! 568: register unsigned k; /* number of bits in bit buffer */ ! 569: unsigned u; /* true if unflushed */ ! 570: ! 571: ! 572: /* explode the coded data */ ! 573: b = k = w = 0; /* initialize bit buffer, window */ ! 574: u = 1; /* buffer unflushed */ ! 575: ml = mask_bits[bl]; /* precompute masks for speed */ ! 576: md = mask_bits[bd]; ! 577: s = ucsize; ! 578: while (s > 0) /* do until ucsize bytes uncompressed */ ! 579: { ! 580: NEEDBITS(1) ! 581: if (b & 1) /* then literal--get eight bits */ ! 582: { ! 583: DUMPBITS(1) ! 584: s--; ! 585: NEEDBITS(8) ! 586: slide[w++] = (byte)b; ! 587: if (w == WSIZE) ! 588: { ! 589: flush(w); ! 590: w = u = 0; ! 591: } ! 592: DUMPBITS(8) ! 593: } ! 594: else /* else distance/length */ ! 595: { ! 596: DUMPBITS(1) ! 597: NEEDBITS(6) /* get distance low bits */ ! 598: d = (unsigned)b & 0x3f; ! 599: DUMPBITS(6) ! 600: NEEDBITS((unsigned)bd) /* get coded distance high bits */ ! 601: if ((e = (t = td + ((~(unsigned)b) & md))->e) > 16) ! 602: do { ! 603: if (e == 99) ! 604: return 1; ! 605: DUMPBITS(t->b) ! 606: e -= 16; ! 607: NEEDBITS(e) ! 608: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 609: DUMPBITS(t->b) ! 610: d = w - d - t->v.n; /* construct offset */ ! 611: NEEDBITS((unsigned)bl) /* get coded length */ ! 612: if ((e = (t = tl + ((~(unsigned)b) & ml))->e) > 16) ! 613: do { ! 614: if (e == 99) ! 615: return 1; ! 616: DUMPBITS(t->b) ! 617: e -= 16; ! 618: NEEDBITS(e) ! 619: } while ((e = (t = t->v.t + ((~(unsigned)b) & mask_bits[e]))->e) > 16); ! 620: DUMPBITS(t->b) ! 621: n = t->v.n; ! 622: if (e) /* get length extra bits */ ! 623: { ! 624: NEEDBITS(8) ! 625: n += (unsigned)b & 0xff; ! 626: DUMPBITS(8) ! 627: } ! 628: ! 629: /* do the copy */ ! 630: s -= n; ! 631: do { ! 632: n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); ! 633: if (u && w <= d) ! 634: { ! 635: memset(slide + w, 0, e); ! 636: w += e; ! 637: d += e; ! 638: } ! 639: else ! 640: #ifndef NOMEMCPY ! 641: if (w - d >= e) /* (this test assumes unsigned comparison) */ ! 642: { ! 643: memcpy(slide + w, slide + d, e); ! 644: w += e; ! 645: d += e; ! 646: } ! 647: else /* do it slow to avoid memcpy() overlap */ ! 648: #endif /* !NOMEMCPY */ ! 649: do { ! 650: slide[w++] = slide[d++]; ! 651: } while (--e); ! 652: if (w == WSIZE) ! 653: { ! 654: flush(w); ! 655: w = u = 0; ! 656: } ! 657: } while (n); ! 658: } ! 659: } ! 660: ! 661: /* flush out slide */ ! 662: flush(w); ! 663: return csize ? 5 : 0; /* should have read csize bytes */ ! 664: } ! 665: ! 666: ! 667: ! 668: int explode() ! 669: /* Explode an imploded compressed stream. Based on the general purpose ! 670: bit flag, decide on coded or uncoded literals, and an 8K or 4K sliding ! 671: window. Construct the literal (if any), length, and distance codes and ! 672: the tables needed to decode them (using huft_build() from inflate.c), ! 673: and call the appropriate routine for the type of data in the remainder ! 674: of the stream. The four routines are nearly identical, differing only ! 675: in whether the literal is decoded or simply read in, and in how many ! 676: bits are read in, uncoded, for the low distance bits. */ ! 677: { ! 678: unsigned r; /* return codes */ ! 679: struct huft *tb; /* literal code table */ ! 680: struct huft *tl; /* length code table */ ! 681: struct huft *td; /* distance code table */ ! 682: int bb; /* bits for tb */ ! 683: int bl; /* bits for tl */ ! 684: int bd; /* bits for td */ ! 685: unsigned l[256]; /* bit lengths for codes */ ! 686: ! 687: ! 688: /* Tune base table sizes. Note: I thought that to truly optimize speed, ! 689: I would have to select different bl, bd, and bb values for different ! 690: compressed file sizes. I was suprised to find out the the values of ! 691: 7, 7, and 9 worked best over a very wide range of sizes, except that ! 692: bd = 8 worked marginally better for large compressed sizes. */ ! 693: bl = 7; ! 694: bd = csize > 200000L ? 8 : 7; ! 695: ! 696: ! 697: /* With literal tree--minimum match length is 3 */ ! 698: hufts = 0; /* initialze huft's malloc'ed */ ! 699: if (lrec.general_purpose_bit_flag & 4) ! 700: { ! 701: bb = 9; /* base table size for literals */ ! 702: if ((r = get_tree(l, 256)) != 0) ! 703: return r; ! 704: if ((r = huft_build(l, 256, 256, NULL, NULL, &tb, &bb)) != 0) ! 705: { ! 706: if (r == 1) ! 707: huft_free(tb); ! 708: return r; ! 709: } ! 710: if ((r = get_tree(l, 64)) != 0) ! 711: return r; ! 712: if ((r = huft_build(l, 64, 0, cplen3, extra, &tl, &bl)) != 0) ! 713: { ! 714: if (r == 1) ! 715: huft_free(tl); ! 716: huft_free(tb); ! 717: return r; ! 718: } ! 719: if ((r = get_tree(l, 64)) != 0) ! 720: return r; ! 721: if (lrec.general_purpose_bit_flag & 2) /* true if 8K */ ! 722: { ! 723: if ((r = huft_build(l, 64, 0, cpdist8, extra, &td, &bd)) != 0) ! 724: { ! 725: if (r == 1) ! 726: huft_free(td); ! 727: huft_free(tl); ! 728: huft_free(tb); ! 729: return r; ! 730: } ! 731: r = explode_lit8(tb, tl, td, bb, bl, bd); ! 732: } ! 733: else /* else 4K */ ! 734: { ! 735: if ((r = huft_build(l, 64, 0, cpdist4, extra, &td, &bd)) != 0) ! 736: { ! 737: if (r == 1) ! 738: huft_free(td); ! 739: huft_free(tl); ! 740: huft_free(tb); ! 741: return r; ! 742: } ! 743: r = explode_lit4(tb, tl, td, bb, bl, bd); ! 744: } ! 745: huft_free(td); ! 746: huft_free(tl); ! 747: huft_free(tb); ! 748: } ! 749: else ! 750: ! 751: ! 752: /* No literal tree--minimum match length is 2 */ ! 753: { ! 754: if ((r = get_tree(l, 64)) != 0) ! 755: return r; ! 756: if ((r = huft_build(l, 64, 0, cplen2, extra, &tl, &bl)) != 0) ! 757: { ! 758: if (r == 1) ! 759: huft_free(tl); ! 760: return r; ! 761: } ! 762: if ((r = get_tree(l, 64)) != 0) ! 763: return r; ! 764: if (lrec.general_purpose_bit_flag & 2) /* true if 8K */ ! 765: { ! 766: if ((r = huft_build(l, 64, 0, cpdist8, extra, &td, &bd)) != 0) ! 767: { ! 768: if (r == 1) ! 769: huft_free(td); ! 770: huft_free(tl); ! 771: return r; ! 772: } ! 773: r = explode_nolit8(tl, td, bl, bd); ! 774: } ! 775: else /* else 4K */ ! 776: { ! 777: if ((r = huft_build(l, 64, 0, cpdist4, extra, &td, &bd)) != 0) ! 778: { ! 779: if (r == 1) ! 780: huft_free(td); ! 781: huft_free(tl); ! 782: return r; ! 783: } ! 784: r = explode_nolit4(tl, td, bl, bd); ! 785: } ! 786: huft_free(td); ! 787: huft_free(tl); ! 788: } ! 789: #ifdef DEBUG ! 790: fprintf(stderr, "<%u > ", hufts); ! 791: #endif /* DEBUG */ ! 792: return r; ! 793: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.