1 /*
2 * Adapted from Wine fdi.c: File Decompression Interface
3 *
4 * Copyright 2000-2002 Stuart Caie
5 * Copyright 2002 Patrik Stridvall
6 * Copyright 2003 Greg Turner
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 */
22
23 #include "config.h"
24
25 #include <string.h>
26 #include "decomp.h"
27
28 #ifndef max
29 #define max(a,b) (((a) > (b)) ? (a) : (b))
30 #endif
31 #ifndef min
32 #define min(a,b) (((a) < (b)) ? (a) : (b))
33 #endif
34
35 /* Tables for deflate from PKZIP's appnote.txt. */
36
37 #define THOSE_ZIP_CONSTS \
38 static const cab_UBYTE Zipborder[] = /* Order of the bit length code lengths */ \
39 { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; \
40 static const cab_UWORD Zipcplens[] = /* Copy lengths for literal codes 257..285 */ \
41 { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, \
42 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; \
43 static const cab_UWORD Zipcplext[] = /* Extra bits for literal codes 257..285 */ \
44 { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, \
45 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ \
46 static const cab_UWORD Zipcpdist[] = /* Copy offsets for distance codes 0..29 */ \
47 { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, \
48 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577}; \
49 static const cab_UWORD Zipcpdext[] = /* Extra bits for distance codes */ \
50 { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, \
51 10, 11, 11, 12, 12, 13, 13}; \
52 /* And'ing with Zipmask[n] masks the lower n bits */ \
53 static const cab_UWORD Zipmask[17] = { \
54 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, \
55 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff \
56 }
57
58 THOSE_ZIP_CONSTS;
59
60 #define CAB(x) (decomp_state->x)
61 #define ZIP(x) (decomp_state->methods.zip.x)
62 #define LZX(x) (decomp_state->methods.lzx.x)
63
64 #define ZIPNEEDBITS(n) {while(k<(n)){cab_LONG c=*(ZIP(inpos)++);\
65 b|=((cab_ULONG)c)<<k;k+=8;}}
66 #define ZIPDUMPBITS(n) {b>>=(n);k-=(n);}
67
68 /********************************************************
69 * Ziphuft_free (internal)
70 */
fdi_Ziphuft_free(FDI_Int * fdi,struct Ziphuft * t)71 static void fdi_Ziphuft_free(FDI_Int *fdi, struct Ziphuft *t)
72 {
73 register struct Ziphuft *p, *q;
74
75 /* Go through linked list, freeing from the allocated (t[-1]) address. */
76 p = t;
77 while (p != NULL)
78 {
79 q = (--p)->v.t;
80 fdi->free(p);
81 p = q;
82 }
83 }
84
85 /*********************************************************
86 * fdi_Ziphuft_build (internal)
87 */
fdi_Ziphuft_build(cab_ULONG * b,cab_ULONG n,cab_ULONG s,const cab_UWORD * d,const cab_UWORD * e,struct Ziphuft ** t,cab_LONG * m,fdi_decomp_state * decomp_state)88 static cab_LONG fdi_Ziphuft_build(cab_ULONG *b, cab_ULONG n, cab_ULONG s, const cab_UWORD *d, const cab_UWORD *e,
89 struct Ziphuft **t, cab_LONG *m, fdi_decomp_state *decomp_state)
90 {
91 cab_ULONG a; /* counter for codes of length k */
92 cab_ULONG el; /* length of EOB code (value 256) */
93 cab_ULONG f; /* i repeats in table every f entries */
94 cab_LONG g; /* maximum code length */
95 cab_LONG h; /* table level */
96 register cab_ULONG i; /* counter, current code */
97 register cab_ULONG j; /* counter */
98 register cab_LONG k; /* number of bits in current code */
99 cab_LONG *l; /* stack of bits per table */
100 register cab_ULONG *p; /* pointer into ZIP(c)[],ZIP(b)[],ZIP(v)[] */
101 register struct Ziphuft *q; /* points to current table */
102 struct Ziphuft r; /* table entry for structure assignment */
103 register cab_LONG w; /* bits before this table == (l * h) */
104 cab_ULONG *xp; /* pointer into x */
105 cab_LONG y; /* number of dummy codes added */
106 cab_ULONG z; /* number of entries in current table */
107
108 l = ZIP(lx)+1;
109
110 /* Generate counts for each bit length */
111 el = n > 256 ? b[256] : ZIPBMAX; /* set length of EOB code, if any */
112
113 for(i = 0; i < ZIPBMAX+1; ++i)
114 ZIP(c)[i] = 0;
115 p = b; i = n;
116 do
117 {
118 ZIP(c)[*p]++; p++; /* assume all entries <= ZIPBMAX */
119 } while (--i);
120 if (ZIP(c)[0] == n) /* null input--all zero length codes */
121 {
122 *t = NULL;
123 *m = 0;
124 return 0;
125 }
126
127 /* Find minimum and maximum length, bound *m by those */
128 for (j = 1; j <= ZIPBMAX; j++)
129 if (ZIP(c)[j])
130 break;
131 k = j; /* minimum code length */
132 if ((cab_ULONG)*m < j)
133 *m = j;
134 for (i = ZIPBMAX; i; i--)
135 if (ZIP(c)[i])
136 break;
137 g = i; /* maximum code length */
138 if ((cab_ULONG)*m > i)
139 *m = i;
140
141 /* Adjust last length count to fill out codes, if needed */
142 for (y = 1 << j; j < i; j++, y <<= 1)
143 if ((y -= ZIP(c)[j]) < 0)
144 return 2; /* bad input: more codes than bits */
145 if ((y -= ZIP(c)[i]) < 0)
146 return 2;
147 ZIP(c)[i] += y;
148
149 /* Generate starting offsets LONGo the value table for each length */
150 ZIP(x)[1] = j = 0;
151 p = ZIP(c) + 1; xp = ZIP(x) + 2;
152 while (--i)
153 { /* note that i == g from above */
154 *xp++ = (j += *p++);
155 }
156
157 /* Make a table of values in order of bit lengths */
158 p = b; i = 0;
159 do{
160 if ((j = *p++) != 0)
161 ZIP(v)[ZIP(x)[j]++] = i;
162 } while (++i < n);
163
164
165 /* Generate the Huffman codes and for each, make the table entries */
166 ZIP(x)[0] = i = 0; /* first Huffman code is zero */
167 p = ZIP(v); /* grab values in bit order */
168 h = -1; /* no tables yet--level -1 */
169 w = l[-1] = 0; /* no bits decoded yet */
170 ZIP(u)[0] = NULL; /* just to keep compilers happy */
171 q = NULL; /* ditto */
172 z = 0; /* ditto */
173
174 /* go through the bit lengths (k already is bits in shortest code) */
175 for (; k <= g; k++)
176 {
177 a = ZIP(c)[k];
178 while (a--)
179 {
180 /* here i is the Huffman code of length k bits for value *p */
181 /* make tables up to required level */
182 while (k > w + l[h])
183 {
184 w += l[h++]; /* add bits already decoded */
185
186 /* compute minimum size table less than or equal to *m bits */
187 if ((z = g - w) > (cab_ULONG)*m) /* upper limit */
188 z = *m;
189 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
190 { /* too few codes for k-w bit table */
191 f -= a + 1; /* deduct codes from patterns left */
192 xp = ZIP(c) + k;
193 while (++j < z) /* try smaller tables up to z bits */
194 {
195 if (*++xp > ZIPBMAX)
196 return 2; /* corrupt */
197 if ((f <<= 1) <= *xp)
198 break; /* enough codes to use up j bits */
199 f -= *xp; /* else deduct codes from patterns */
200 }
201 }
202 if ((cab_ULONG)w + j > el && (cab_ULONG)w < el)
203 j = el - w; /* make EOB code end at table */
204 z = 1 << j; /* table entries for j-bit table */
205 l[h] = j; /* set table size in stack */
206
207 /* allocate and link in new table */
208 if (!(q = CAB(fdi)->alloc((z + 1)*sizeof(struct Ziphuft))))
209 {
210 if(h)
211 fdi_Ziphuft_free(CAB(fdi), ZIP(u)[0]);
212 return 3; /* not enough memory */
213 }
214 *t = q + 1; /* link to list for Ziphuft_free() */
215 *(t = &(q->v.t)) = NULL;
216 ZIP(u)[h] = ++q; /* table starts after link */
217
218 /* connect to last table, if there is one */
219 if (h)
220 {
221 ZIP(x)[h] = i; /* save pattern for backing up */
222 r.b = (cab_UBYTE)l[h-1]; /* bits to dump before this table */
223 r.e = (cab_UBYTE)(16 + j); /* bits in this table */
224 r.v.t = q; /* pointer to this table */
225 j = (i & ((1 << w) - 1)) >> (w - l[h-1]);
226 ZIP(u)[h-1][j] = r; /* connect to last table */
227 }
228 }
229
230 /* set up table entry in r */
231 r.b = (cab_UBYTE)(k - w);
232 if (p >= ZIP(v) + n)
233 r.e = 99; /* out of values--invalid code */
234 else if (*p < s)
235 {
236 r.e = (cab_UBYTE)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */
237 r.v.n = *p++; /* simple code is just the value */
238 }
239 else
240 {
241 r.e = (cab_UBYTE)e[*p - s]; /* non-simple--look up in lists */
242 r.v.n = d[*p++ - s];
243 }
244
245 /* fill code-like entries with r */
246 f = 1 << (k - w);
247 for (j = i >> w; j < z; j += f)
248 q[j] = r;
249
250 /* backwards increment the k-bit code i */
251 for (j = 1 << (k - 1); i & j; j >>= 1)
252 i ^= j;
253 i ^= j;
254
255 /* no tables */
256 if (h < 0)
257 return 2; /* corrupt */
258
259 /* backup over finished tables */
260 while ((i & ((1 << w) - 1)) != ZIP(x)[h])
261 w -= l[--h]; /* don't need to update q */
262 }
263 }
264
265 /* return actual size of base table */
266 *m = l[0];
267
268 /* Return true (1) if we were given an incomplete table */
269 return y != 0 && g != 1;
270 }
271
272 /*********************************************************
273 * fdi_Zipinflate_codes (internal)
274 */
fdi_Zipinflate_codes(const struct Ziphuft * tl,const struct Ziphuft * td,cab_LONG bl,cab_LONG bd,fdi_decomp_state * decomp_state)275 static cab_LONG fdi_Zipinflate_codes(const struct Ziphuft *tl, const struct Ziphuft *td,
276 cab_LONG bl, cab_LONG bd, fdi_decomp_state *decomp_state)
277 {
278 register cab_ULONG e; /* table entry flag/number of extra bits */
279 cab_ULONG n, d; /* length and index for copy */
280 cab_ULONG w; /* current window position */
281 const struct Ziphuft *t; /* pointer to table entry */
282 cab_ULONG ml, md; /* masks for bl and bd bits */
283 register cab_ULONG b; /* bit buffer */
284 register cab_ULONG k; /* number of bits in bit buffer */
285
286 /* make local copies of globals */
287 b = ZIP(bb); /* initialize bit buffer */
288 k = ZIP(bk);
289 w = ZIP(window_posn); /* initialize window position */
290
291 /* inflate the coded data */
292 ml = Zipmask[bl]; /* precompute masks for speed */
293 md = Zipmask[bd];
294
295 for(;;)
296 {
297 ZIPNEEDBITS((cab_ULONG)bl)
298 if((e = (t = tl + (b & ml))->e) > 16)
299 do
300 {
301 if (e == 99)
302 return 1;
303 ZIPDUMPBITS(t->b)
304 e -= 16;
305 ZIPNEEDBITS(e)
306 } while ((e = (t = t->v.t + (b & Zipmask[e]))->e) > 16);
307 ZIPDUMPBITS(t->b)
308 if (e == 16) /* then it's a literal */
309 CAB(outbuf)[w++] = (cab_UBYTE)t->v.n;
310 else /* it's an EOB or a length */
311 {
312 /* exit if end of block */
313 if(e == 15)
314 break;
315
316 /* get length of block to copy */
317 ZIPNEEDBITS(e)
318 n = t->v.n + (b & Zipmask[e]);
319 ZIPDUMPBITS(e);
320
321 /* decode distance of block to copy */
322 ZIPNEEDBITS((cab_ULONG)bd)
323 if ((e = (t = td + (b & md))->e) > 16)
324 do {
325 if (e == 99)
326 return 1;
327 ZIPDUMPBITS(t->b)
328 e -= 16;
329 ZIPNEEDBITS(e)
330 } while ((e = (t = t->v.t + (b & Zipmask[e]))->e) > 16);
331 ZIPDUMPBITS(t->b)
332 ZIPNEEDBITS(e)
333 d = w - t->v.n - (b & Zipmask[e]);
334 ZIPDUMPBITS(e)
335 do
336 {
337 d &= ZIPWSIZE - 1;
338 e = ZIPWSIZE - max(d, w);
339 e = min(e, n);
340 n -= e;
341 do
342 {
343 CAB(outbuf)[w++] = CAB(outbuf)[d++];
344 } while (--e);
345 } while (n);
346 }
347 }
348
349 /* restore the globals from the locals */
350 ZIP(window_posn) = w; /* restore global window pointer */
351 ZIP(bb) = b; /* restore global bit buffer */
352 ZIP(bk) = k;
353
354 /* done */
355 return 0;
356 }
357
358 /***********************************************************
359 * Zipinflate_stored (internal)
360 */
fdi_Zipinflate_stored(fdi_decomp_state * decomp_state)361 static cab_LONG fdi_Zipinflate_stored(fdi_decomp_state *decomp_state)
362 /* "decompress" an inflated type 0 (stored) block. */
363 {
364 cab_ULONG n; /* number of bytes in block */
365 cab_ULONG w; /* current window position */
366 register cab_ULONG b; /* bit buffer */
367 register cab_ULONG k; /* number of bits in bit buffer */
368
369 /* make local copies of globals */
370 b = ZIP(bb); /* initialize bit buffer */
371 k = ZIP(bk);
372 w = ZIP(window_posn); /* initialize window position */
373
374 /* go to byte boundary */
375 n = k & 7;
376 ZIPDUMPBITS(n);
377
378 /* get the length and its complement */
379 ZIPNEEDBITS(16)
380 n = (b & 0xffff);
381 ZIPDUMPBITS(16)
382 ZIPNEEDBITS(16)
383 if (n != ((~b) & 0xffff))
384 return 1; /* error in compressed data */
385 ZIPDUMPBITS(16)
386
387 /* read and output the compressed data */
388 while(n--)
389 {
390 ZIPNEEDBITS(8)
391 CAB(outbuf)[w++] = (cab_UBYTE)b;
392 ZIPDUMPBITS(8)
393 }
394
395 /* restore the globals from the locals */
396 ZIP(window_posn) = w; /* restore global window pointer */
397 ZIP(bb) = b; /* restore global bit buffer */
398 ZIP(bk) = k;
399 return 0;
400 }
401
402 /******************************************************
403 * fdi_Zipinflate_fixed (internal)
404 */
fdi_Zipinflate_fixed(fdi_decomp_state * decomp_state)405 static cab_LONG fdi_Zipinflate_fixed(fdi_decomp_state *decomp_state)
406 {
407 struct Ziphuft *fixed_tl;
408 struct Ziphuft *fixed_td;
409 cab_LONG fixed_bl, fixed_bd;
410 cab_LONG i; /* temporary variable */
411 cab_ULONG *l;
412
413 l = ZIP(ll);
414
415 /* literal table */
416 for(i = 0; i < 144; i++)
417 l[i] = 8;
418 for(; i < 256; i++)
419 l[i] = 9;
420 for(; i < 280; i++)
421 l[i] = 7;
422 for(; i < 288; i++) /* make a complete, but wrong code set */
423 l[i] = 8;
424 fixed_bl = 7;
425 if((i = fdi_Ziphuft_build(l, 288, 257, Zipcplens, Zipcplext, &fixed_tl, &fixed_bl, decomp_state)))
426 return i;
427
428 /* distance table */
429 for(i = 0; i < 30; i++) /* make an incomplete code set */
430 l[i] = 5;
431 fixed_bd = 5;
432 if((i = fdi_Ziphuft_build(l, 30, 0, Zipcpdist, Zipcpdext, &fixed_td, &fixed_bd, decomp_state)) > 1)
433 {
434 fdi_Ziphuft_free(CAB(fdi), fixed_tl);
435 return i;
436 }
437
438 /* decompress until an end-of-block code */
439 i = fdi_Zipinflate_codes(fixed_tl, fixed_td, fixed_bl, fixed_bd, decomp_state);
440
441 fdi_Ziphuft_free(CAB(fdi), fixed_td);
442 fdi_Ziphuft_free(CAB(fdi), fixed_tl);
443 return i;
444 }
445
446 /**************************************************************
447 * fdi_Zipinflate_dynamic (internal)
448 */
fdi_Zipinflate_dynamic(fdi_decomp_state * decomp_state)449 static cab_LONG fdi_Zipinflate_dynamic(fdi_decomp_state *decomp_state)
450 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
451 {
452 cab_LONG i; /* temporary variables */
453 cab_ULONG j;
454 cab_ULONG *ll;
455 cab_ULONG l; /* last length */
456 cab_ULONG m; /* mask for bit lengths table */
457 cab_ULONG n; /* number of lengths to get */
458 struct Ziphuft *tl; /* literal/length code table */
459 struct Ziphuft *td; /* distance code table */
460 cab_LONG bl; /* lookup bits for tl */
461 cab_LONG bd; /* lookup bits for td */
462 cab_ULONG nb; /* number of bit length codes */
463 cab_ULONG nl; /* number of literal/length codes */
464 cab_ULONG nd; /* number of distance codes */
465 register cab_ULONG b; /* bit buffer */
466 register cab_ULONG k; /* number of bits in bit buffer */
467
468 /* make local bit buffer */
469 b = ZIP(bb);
470 k = ZIP(bk);
471 ll = ZIP(ll);
472
473 /* read in table lengths */
474 ZIPNEEDBITS(5)
475 nl = 257 + (b & 0x1f); /* number of literal/length codes */
476 ZIPDUMPBITS(5)
477 ZIPNEEDBITS(5)
478 nd = 1 + (b & 0x1f); /* number of distance codes */
479 ZIPDUMPBITS(5)
480 ZIPNEEDBITS(4)
481 nb = 4 + (b & 0xf); /* number of bit length codes */
482 ZIPDUMPBITS(4)
483 if(nl > 288 || nd > 32)
484 return 1; /* bad lengths */
485
486 /* read in bit-length-code lengths */
487 for(j = 0; j < nb; j++)
488 {
489 ZIPNEEDBITS(3)
490 ll[Zipborder[j]] = b & 7;
491 ZIPDUMPBITS(3)
492 }
493 for(; j < 19; j++)
494 ll[Zipborder[j]] = 0;
495
496 /* build decoding table for trees--single level, 7 bit lookup */
497 bl = 7;
498 if((i = fdi_Ziphuft_build(ll, 19, 19, NULL, NULL, &tl, &bl, decomp_state)) != 0)
499 {
500 if(i == 1)
501 fdi_Ziphuft_free(CAB(fdi), tl);
502 return i; /* incomplete code set */
503 }
504
505 /* read in literal and distance code lengths */
506 n = nl + nd;
507 m = Zipmask[bl];
508 i = l = 0;
509 while((cab_ULONG)i < n)
510 {
511 ZIPNEEDBITS((cab_ULONG)bl)
512 j = (td = tl + (b & m))->b;
513 ZIPDUMPBITS(j)
514 j = td->v.n;
515 if (j < 16) /* length of code in bits (0..15) */
516 ll[i++] = l = j; /* save last length in l */
517 else if (j == 16) /* repeat last length 3 to 6 times */
518 {
519 ZIPNEEDBITS(2)
520 j = 3 + (b & 3);
521 ZIPDUMPBITS(2)
522 if((cab_ULONG)i + j > n)
523 return 1;
524 while (j--)
525 ll[i++] = l;
526 }
527 else if (j == 17) /* 3 to 10 zero length codes */
528 {
529 ZIPNEEDBITS(3)
530 j = 3 + (b & 7);
531 ZIPDUMPBITS(3)
532 if ((cab_ULONG)i + j > n)
533 return 1;
534 while (j--)
535 ll[i++] = 0;
536 l = 0;
537 }
538 else /* j == 18: 11 to 138 zero length codes */
539 {
540 ZIPNEEDBITS(7)
541 j = 11 + (b & 0x7f);
542 ZIPDUMPBITS(7)
543 if ((cab_ULONG)i + j > n)
544 return 1;
545 while (j--)
546 ll[i++] = 0;
547 l = 0;
548 }
549 }
550
551 /* free decoding table for trees */
552 fdi_Ziphuft_free(CAB(fdi), tl);
553
554 /* restore the global bit buffer */
555 ZIP(bb) = b;
556 ZIP(bk) = k;
557
558 /* build the decoding tables for literal/length and distance codes */
559 bl = ZIPLBITS;
560 if((i = fdi_Ziphuft_build(ll, nl, 257, Zipcplens, Zipcplext, &tl, &bl, decomp_state)) != 0)
561 {
562 if(i == 1)
563 fdi_Ziphuft_free(CAB(fdi), tl);
564 return i; /* incomplete code set */
565 }
566 bd = ZIPDBITS;
567 fdi_Ziphuft_build(ll + nl, nd, 0, Zipcpdist, Zipcpdext, &td, &bd, decomp_state);
568
569 /* decompress until an end-of-block code */
570 if(fdi_Zipinflate_codes(tl, td, bl, bd, decomp_state))
571 return 1;
572
573 /* free the decoding tables, return */
574 fdi_Ziphuft_free(CAB(fdi), tl);
575 fdi_Ziphuft_free(CAB(fdi), td);
576 return 0;
577 }
578
579 /*****************************************************
580 * fdi_Zipinflate_block (internal)
581 */
fdi_Zipinflate_block(cab_LONG * e,fdi_decomp_state * decomp_state)582 static cab_LONG fdi_Zipinflate_block(cab_LONG *e, fdi_decomp_state *decomp_state) /* e == last block flag */
583 { /* decompress an inflated block */
584 cab_ULONG t; /* block type */
585 register cab_ULONG b; /* bit buffer */
586 register cab_ULONG k; /* number of bits in bit buffer */
587
588 /* make local bit buffer */
589 b = ZIP(bb);
590 k = ZIP(bk);
591
592 /* read in last block bit */
593 ZIPNEEDBITS(1)
594 *e = (cab_LONG)b & 1;
595 ZIPDUMPBITS(1)
596
597 /* read in block type */
598 ZIPNEEDBITS(2)
599 t = b & 3;
600 ZIPDUMPBITS(2)
601
602 /* restore the global bit buffer */
603 ZIP(bb) = b;
604 ZIP(bk) = k;
605
606 /* inflate that block type */
607 if(t == 2)
608 return fdi_Zipinflate_dynamic(decomp_state);
609 if(t == 0)
610 return fdi_Zipinflate_stored(decomp_state);
611 if(t == 1)
612 return fdi_Zipinflate_fixed(decomp_state);
613 /* bad block type */
614 return 2;
615 }
616
617 /****************************************************
618 * ZIPfdi_decomp(internal)
619 */
ZIPfdi_decomp(int inlen,int outlen,fdi_decomp_state * decomp_state)620 int ZIPfdi_decomp(int inlen, int outlen, fdi_decomp_state *decomp_state)
621 {
622 cab_LONG e; /* last block flag */
623
624 ZIP(inpos) = CAB(inbuf);
625 ZIP(bb) = ZIP(bk) = ZIP(window_posn) = 0;
626 if(outlen > ZIPWSIZE)
627 return -1;
628
629 /* CK = Chris Kirmse, official Microsoft purloiner */
630 if(ZIP(inpos)[0] != 0x43 || ZIP(inpos)[1] != 0x4B)
631 return -1;
632 ZIP(inpos) += 2;
633
634 do {
635 if(fdi_Zipinflate_block(&e, decomp_state))
636 return -1;
637 } while(!e);
638
639 /* return success */
640 return 1;
641 }
642
643 /*************************************************************************
644 * make_decode_table (internal)
645 *
646 * This function was coded by David Tritscher. It builds a fast huffman
647 * decoding table out of just a canonical huffman code lengths table.
648 *
649 * PARAMS
650 * nsyms: total number of symbols in this huffman tree.
651 * nbits: any symbols with a code length of nbits or less can be decoded
652 * in one lookup of the table.
653 * length: A table to get code lengths from [0 to syms-1]
654 * table: The table to fill up with decoded symbols and pointers.
655 *
656 * RETURNS
657 * OK: 0
658 * error: 1
659 */
make_decode_table(cab_ULONG nsyms,cab_ULONG nbits,const cab_UBYTE * length,cab_UWORD * table)660 static int make_decode_table(cab_ULONG nsyms, cab_ULONG nbits,
661 const cab_UBYTE *length, cab_UWORD *table) {
662 register cab_UWORD sym;
663 register cab_ULONG leaf;
664 register cab_UBYTE bit_num = 1;
665 cab_ULONG fill;
666 cab_ULONG pos = 0; /* the current position in the decode table */
667 cab_ULONG table_mask = 1 << nbits;
668 cab_ULONG bit_mask = table_mask >> 1; /* don't do 0 length codes */
669 cab_ULONG next_symbol = bit_mask; /* base of allocation for long codes */
670
671 /* fill entries for codes short enough for a direct mapping */
672 while (bit_num <= nbits) {
673 for (sym = 0; sym < nsyms; sym++) {
674 if (length[sym] == bit_num) {
675 leaf = pos;
676
677 if((pos += bit_mask) > table_mask) return 1; /* table overrun */
678
679 /* fill all possible lookups of this symbol with the symbol itself */
680 fill = bit_mask;
681 while (fill-- > 0) table[leaf++] = sym;
682 }
683 }
684 bit_mask >>= 1;
685 bit_num++;
686 }
687
688 /* if there are any codes longer than nbits */
689 if (pos != table_mask) {
690 /* clear the remainder of the table */
691 for (sym = pos; sym < table_mask; sym++) table[sym] = 0;
692
693 /* give ourselves room for codes to grow by up to 16 more bits */
694 pos <<= 16;
695 table_mask <<= 16;
696 bit_mask = 1 << 15;
697
698 while (bit_num <= 16) {
699 for (sym = 0; sym < nsyms; sym++) {
700 if (length[sym] == bit_num) {
701 leaf = pos >> 16;
702 for (fill = 0; fill < bit_num - nbits; fill++) {
703 /* if this path hasn't been taken yet, 'allocate' two entries */
704 if (table[leaf] == 0) {
705 table[(next_symbol << 1)] = 0;
706 table[(next_symbol << 1) + 1] = 0;
707 table[leaf] = next_symbol++;
708 }
709 /* follow the path and select either left or right for next bit */
710 leaf = table[leaf] << 1;
711 if ((pos >> (15-fill)) & 1) leaf++;
712 }
713 table[leaf] = sym;
714
715 if ((pos += bit_mask) > table_mask) return 1; /* table overflow */
716 }
717 }
718 bit_mask >>= 1;
719 bit_num++;
720 }
721 }
722
723 /* full table? */
724 if (pos == table_mask) return 0;
725
726 /* either erroneous table, or all elements are 0 - let's find out. */
727 for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
728 return 0;
729 }
730
731 /************************************************************
732 * fdi_lzx_read_lens (internal)
733 */
fdi_lzx_read_lens(cab_UBYTE * lens,cab_ULONG first,cab_ULONG last,struct lzx_bits * lb,fdi_decomp_state * decomp_state)734 static int fdi_lzx_read_lens(cab_UBYTE *lens, cab_ULONG first, cab_ULONG last, struct lzx_bits *lb,
735 fdi_decomp_state *decomp_state) {
736 cab_ULONG i,j, x,y;
737 int z;
738
739 register cab_ULONG bitbuf = lb->bb;
740 register int bitsleft = lb->bl;
741 cab_UBYTE *inpos = lb->ip;
742 cab_UWORD *hufftbl;
743
744 for (x = 0; x < 20; x++) {
745 READ_BITS(y, 4);
746 LENTABLE(PRETREE)[x] = y;
747 }
748 BUILD_TABLE(PRETREE);
749
750 for (x = first; x < last; ) {
751 READ_HUFFSYM(PRETREE, z);
752 if (z == 17) {
753 READ_BITS(y, 4); y += 4;
754 while (y--) lens[x++] = 0;
755 }
756 else if (z == 18) {
757 READ_BITS(y, 5); y += 20;
758 while (y--) lens[x++] = 0;
759 }
760 else if (z == 19) {
761 READ_BITS(y, 1); y += 4;
762 READ_HUFFSYM(PRETREE, z);
763 z = lens[x] - z; if (z < 0) z += 17;
764 while (y--) lens[x++] = z;
765 }
766 else {
767 z = lens[x] - z; if (z < 0) z += 17;
768 lens[x++] = z;
769 }
770 }
771
772 lb->bb = bitbuf;
773 lb->bl = bitsleft;
774 lb->ip = inpos;
775 return 0;
776 }
777
778 /************************************************************
779 * LZXfdi_init (internal)
780 */
LZXfdi_init(int window,fdi_decomp_state * decomp_state)781 int LZXfdi_init(int window, fdi_decomp_state *decomp_state) {
782 static const cab_UBYTE bits[] =
783 { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
784 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14,
785 15, 15, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
786 17, 17, 17};
787 static const cab_ULONG base[] =
788 { 0, 1, 2, 3, 4, 6, 8, 12,
789 16, 24, 32, 48, 64, 96, 128, 192,
790 256, 384, 512, 768, 1024, 1536, 2048, 3072,
791 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152,
792 65536, 98304, 131072, 196608, 262144, 393216, 524288, 655360,
793 786432, 917504, 1048576, 1179648, 1310720, 1441792, 1572864, 1703936,
794 1835008, 1966080, 2097152};
795 cab_ULONG wndsize = 1 << window;
796 int posn_slots;
797
798 /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
799 /* if a previously allocated window is big enough, keep it */
800 if (window < 15 || window > 21) return DECR_DATAFORMAT;
801 if (LZX(actual_size) < wndsize) {
802 if (LZX(window)) CAB(fdi)->free(LZX(window));
803 LZX(window) = NULL;
804 }
805 if (!LZX(window)) {
806 if (!(LZX(window) = CAB(fdi)->alloc(wndsize))) return DECR_NOMEMORY;
807 LZX(actual_size) = wndsize;
808 }
809 LZX(window_size) = wndsize;
810
811 /* initialize static tables */
812 memcpy(CAB(extra_bits), bits, sizeof(bits));
813 memcpy(CAB(lzx_position_base), base, sizeof(base));
814
815 /* calculate required position slots */
816 if (window == 20) posn_slots = 42;
817 else if (window == 21) posn_slots = 50;
818 else posn_slots = window << 1;
819
820 /*posn_slots=i=0; while (i < wndsize) i += 1 << CAB(extra_bits)[posn_slots++]; */
821
822 LZX(R0) = LZX(R1) = LZX(R2) = 1;
823 LZX(main_elements) = LZX_NUM_CHARS + (posn_slots << 3);
824 LZX(header_read) = 0;
825 LZX(frames_read) = 0;
826 LZX(block_remaining) = 0;
827 LZX(block_type) = LZX_BLOCKTYPE_INVALID;
828 LZX(intel_curpos) = 0;
829 LZX(intel_started) = 0;
830 LZX(window_posn) = 0;
831
832 /* initialize tables to 0 (because deltas will be applied to them) */
833 memset(LZX(MAINTREE_len), 0, sizeof(LZX(MAINTREE_len)));
834 memset(LZX(LENGTH_len), 0, sizeof(LZX(LENGTH_len)));
835
836 return DECR_OK;
837 }
838
LZXfdi_clear(fdi_decomp_state * decomp_state)839 void LZXfdi_clear(fdi_decomp_state *decomp_state) {
840 cab_UBYTE *window = LZX(window);
841 CAB(fdi)->free(window);
842 }
843
844 /*******************************************************
845 * LZXfdi_decomp(internal)
846 */
LZXfdi_decomp(int inlen,int outlen,fdi_decomp_state * decomp_state)847 int LZXfdi_decomp(int inlen, int outlen, fdi_decomp_state *decomp_state) {
848 cab_UBYTE *inpos = CAB(inbuf);
849 const cab_UBYTE *endinp = inpos + inlen;
850 cab_UBYTE *window = LZX(window);
851 cab_UBYTE *runsrc, *rundest;
852 cab_UWORD *hufftbl; /* used in READ_HUFFSYM macro as chosen decoding table */
853
854 cab_ULONG window_posn = LZX(window_posn);
855 cab_ULONG window_size = LZX(window_size);
856 cab_ULONG R0 = LZX(R0);
857 cab_ULONG R1 = LZX(R1);
858 cab_ULONG R2 = LZX(R2);
859
860 register cab_ULONG bitbuf;
861 register int bitsleft;
862 cab_ULONG match_offset, i,j,k; /* ijk used in READ_HUFFSYM macro */
863 struct lzx_bits lb; /* used in READ_LENGTHS macro */
864
865 int togo = outlen, this_run, main_element, aligned_bits;
866 int match_length, copy_length, length_footer, extra, verbatim_bits;
867
868 INIT_BITSTREAM;
869
870 /* read header if necessary */
871 if (!LZX(header_read)) {
872 i = j = 0;
873 READ_BITS(k, 1); if (k) { READ_BITS(i,16); READ_BITS(j,16); }
874 LZX(intel_filesize) = (i << 16) | j; /* or 0 if not encoded */
875 LZX(header_read) = 1;
876 }
877
878 /* main decoding loop */
879 while (togo > 0) {
880 /* last block finished, new block expected */
881 if (LZX(block_remaining) == 0) {
882 if (LZX(block_type) == LZX_BLOCKTYPE_UNCOMPRESSED) {
883 if (LZX(block_length) & 1) inpos++; /* realign bitstream to word */
884 INIT_BITSTREAM;
885 }
886
887 READ_BITS(LZX(block_type), 3);
888 READ_BITS(i, 16);
889 READ_BITS(j, 8);
890 LZX(block_remaining) = LZX(block_length) = (i << 8) | j;
891
892 switch (LZX(block_type)) {
893 case LZX_BLOCKTYPE_ALIGNED:
894 for (i = 0; i < 8; i++) { READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j; }
895 BUILD_TABLE(ALIGNED);
896 /* rest of aligned header is same as verbatim */
897 /* fall-thru */
898
899 case LZX_BLOCKTYPE_VERBATIM:
900 READ_LENGTHS(MAINTREE, 0, 256, fdi_lzx_read_lens);
901 READ_LENGTHS(MAINTREE, 256, LZX(main_elements), fdi_lzx_read_lens);
902 BUILD_TABLE(MAINTREE);
903 if (LENTABLE(MAINTREE)[0xE8] != 0) LZX(intel_started) = 1;
904
905 READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS, fdi_lzx_read_lens);
906 BUILD_TABLE(LENGTH);
907 break;
908
909 case LZX_BLOCKTYPE_UNCOMPRESSED:
910 LZX(intel_started) = 1; /* because we can't assume otherwise */
911 ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */
912 if (bitsleft > 16) inpos -= 2; /* and align the bitstream! */
913 R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
914 R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
915 R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
916 break;
917
918 default:
919 return DECR_ILLEGALDATA;
920 }
921 }
922
923 /* buffer exhaustion check */
924 if (inpos > endinp) {
925 /* it's possible to have a file where the next run is less than
926 * 16 bits in size. In this case, the READ_HUFFSYM() macro used
927 * in building the tables will exhaust the buffer, so we should
928 * allow for this, but not allow those accidentally read bits to
929 * be used (so we check that there are at least 16 bits
930 * remaining - in this boundary case they aren't really part of
931 * the compressed data)
932 */
933 if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA;
934 }
935
936 while ((this_run = LZX(block_remaining)) > 0 && togo > 0) {
937 if (this_run > togo) this_run = togo;
938 togo -= this_run;
939 LZX(block_remaining) -= this_run;
940
941 /* apply 2^x-1 mask */
942 window_posn &= window_size - 1;
943 /* runs can't straddle the window wraparound */
944 if ((window_posn + this_run) > window_size)
945 return DECR_DATAFORMAT;
946
947 switch (LZX(block_type)) {
948
949 case LZX_BLOCKTYPE_VERBATIM:
950 while (this_run > 0) {
951 READ_HUFFSYM(MAINTREE, main_element);
952
953 if (main_element < LZX_NUM_CHARS) {
954 /* literal: 0 to LZX_NUM_CHARS-1 */
955 window[window_posn++] = main_element;
956 this_run--;
957 }
958 else {
959 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
960 main_element -= LZX_NUM_CHARS;
961
962 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
963 if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
964 READ_HUFFSYM(LENGTH, length_footer);
965 match_length += length_footer;
966 }
967 match_length += LZX_MIN_MATCH;
968
969 match_offset = main_element >> 3;
970
971 if (match_offset > 2) {
972 /* not repeated offset */
973 if (match_offset != 3) {
974 extra = CAB(extra_bits)[match_offset];
975 READ_BITS(verbatim_bits, extra);
976 match_offset = CAB(lzx_position_base)[match_offset]
977 - 2 + verbatim_bits;
978 }
979 else {
980 match_offset = 1;
981 }
982
983 /* update repeated offset LRU queue */
984 R2 = R1; R1 = R0; R0 = match_offset;
985 }
986 else if (match_offset == 0) {
987 match_offset = R0;
988 }
989 else if (match_offset == 1) {
990 match_offset = R1;
991 R1 = R0; R0 = match_offset;
992 }
993 else /* match_offset == 2 */ {
994 match_offset = R2;
995 R2 = R0; R0 = match_offset;
996 }
997
998 rundest = window + window_posn;
999 this_run -= match_length;
1000
1001 /* copy any wrapped around source data */
1002 if (window_posn >= match_offset) {
1003 /* no wrap */
1004 runsrc = rundest - match_offset;
1005 } else {
1006 runsrc = rundest + (window_size - match_offset);
1007 copy_length = match_offset - window_posn;
1008 if (copy_length < match_length) {
1009 match_length -= copy_length;
1010 window_posn += copy_length;
1011 while (copy_length-- > 0) *rundest++ = *runsrc++;
1012 runsrc = window;
1013 }
1014 }
1015 window_posn += match_length;
1016
1017 /* copy match data - no worries about destination wraps */
1018 while (match_length-- > 0) *rundest++ = *runsrc++;
1019 }
1020 }
1021 break;
1022
1023 case LZX_BLOCKTYPE_ALIGNED:
1024 while (this_run > 0) {
1025 READ_HUFFSYM(MAINTREE, main_element);
1026
1027 if (main_element < LZX_NUM_CHARS) {
1028 /* literal: 0 to LZX_NUM_CHARS-1 */
1029 window[window_posn++] = main_element;
1030 this_run--;
1031 }
1032 else {
1033 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
1034 main_element -= LZX_NUM_CHARS;
1035
1036 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
1037 if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
1038 READ_HUFFSYM(LENGTH, length_footer);
1039 match_length += length_footer;
1040 }
1041 match_length += LZX_MIN_MATCH;
1042
1043 match_offset = main_element >> 3;
1044
1045 if (match_offset > 2) {
1046 /* not repeated offset */
1047 extra = CAB(extra_bits)[match_offset];
1048 match_offset = CAB(lzx_position_base)[match_offset] - 2;
1049 if (extra > 3) {
1050 /* verbatim and aligned bits */
1051 extra -= 3;
1052 READ_BITS(verbatim_bits, extra);
1053 match_offset += (verbatim_bits << 3);
1054 READ_HUFFSYM(ALIGNED, aligned_bits);
1055 match_offset += aligned_bits;
1056 }
1057 else if (extra == 3) {
1058 /* aligned bits only */
1059 READ_HUFFSYM(ALIGNED, aligned_bits);
1060 match_offset += aligned_bits;
1061 }
1062 else if (extra > 0) { /* extra==1, extra==2 */
1063 /* verbatim bits only */
1064 READ_BITS(verbatim_bits, extra);
1065 match_offset += verbatim_bits;
1066 }
1067 else /* extra == 0 */ {
1068 /* ??? */
1069 match_offset = 1;
1070 }
1071
1072 /* update repeated offset LRU queue */
1073 R2 = R1; R1 = R0; R0 = match_offset;
1074 }
1075 else if (match_offset == 0) {
1076 match_offset = R0;
1077 }
1078 else if (match_offset == 1) {
1079 match_offset = R1;
1080 R1 = R0; R0 = match_offset;
1081 }
1082 else /* match_offset == 2 */ {
1083 match_offset = R2;
1084 R2 = R0; R0 = match_offset;
1085 }
1086
1087 rundest = window + window_posn;
1088 this_run -= match_length;
1089
1090 /* copy any wrapped around source data */
1091 if (window_posn >= match_offset) {
1092 /* no wrap */
1093 runsrc = rundest - match_offset;
1094 } else {
1095 runsrc = rundest + (window_size - match_offset);
1096 copy_length = match_offset - window_posn;
1097 if (copy_length < match_length) {
1098 match_length -= copy_length;
1099 window_posn += copy_length;
1100 while (copy_length-- > 0) *rundest++ = *runsrc++;
1101 runsrc = window;
1102 }
1103 }
1104 window_posn += match_length;
1105
1106 /* copy match data - no worries about destination wraps */
1107 while (match_length-- > 0) *rundest++ = *runsrc++;
1108 }
1109 }
1110 break;
1111
1112 case LZX_BLOCKTYPE_UNCOMPRESSED:
1113 if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA;
1114 memcpy(window + window_posn, inpos, (size_t) this_run);
1115 inpos += this_run; window_posn += this_run;
1116 break;
1117
1118 default:
1119 return DECR_ILLEGALDATA; /* might as well */
1120 }
1121
1122 }
1123 }
1124
1125 if (togo != 0) return DECR_ILLEGALDATA;
1126 memcpy(CAB(outbuf), window + ((!window_posn) ? window_size : window_posn) -
1127 outlen, (size_t) outlen);
1128
1129 LZX(window_posn) = window_posn;
1130 LZX(R0) = R0;
1131 LZX(R1) = R1;
1132 LZX(R2) = R2;
1133
1134 /* intel E8 decoding */
1135 if ((LZX(frames_read)++ < 32768) && LZX(intel_filesize) != 0) {
1136 if (outlen <= 6 || !LZX(intel_started)) {
1137 LZX(intel_curpos) += outlen;
1138 }
1139 else {
1140 cab_UBYTE *data = CAB(outbuf);
1141 cab_UBYTE *dataend = data + outlen - 10;
1142 cab_LONG curpos = LZX(intel_curpos);
1143 cab_LONG filesize = LZX(intel_filesize);
1144 cab_LONG abs_off, rel_off;
1145
1146 LZX(intel_curpos) = curpos + outlen;
1147
1148 while (data < dataend) {
1149 if (*data++ != 0xE8) { curpos++; continue; }
1150 abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
1151 if ((abs_off >= -curpos) && (abs_off < filesize)) {
1152 rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
1153 data[0] = (cab_UBYTE) rel_off;
1154 data[1] = (cab_UBYTE) (rel_off >> 8);
1155 data[2] = (cab_UBYTE) (rel_off >> 16);
1156 data[3] = (cab_UBYTE) (rel_off >> 24);
1157 }
1158 data += 4;
1159 curpos += 5;
1160 }
1161 }
1162 }
1163 return DECR_OK;
1164 }
1165