![[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.