1 /* 2 * MSZIP decompression (taken from fdi.c of cabinet dll) 3 * 4 * Copyright 2000-2002 Stuart Caie 5 * Copyright 2002 Patrik Stridvall 6 * Copyright 2003 Greg Turner 7 * Copyright 2010 Christian Costa 8 * 9 * This library is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU Lesser General Public 11 * License as published by the Free Software Foundation; either 12 * version 2.1 of the License, or (at your option) any later version. 13 * 14 * This library is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * Lesser General Public License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public 20 * License along with this library; if not, write to the Free Software 21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA 22 */ 23 24 #include <stdarg.h> 25 26 #include "windef.h" 27 #include "winbase.h" 28 29 #include "wine/debug.h" 30 31 #include "mszip.h" 32 33 WINE_DEFAULT_DEBUG_CHANNEL(d3dxof); 34 35 THOSE_ZIP_CONSTS; 36 37 /******************************************************** 38 * Ziphuft_free (internal) 39 */ 40 static void fdi_Ziphuft_free(HFDI hfdi, struct Ziphuft *t) 41 { 42 register struct Ziphuft *p, *q; 43 44 /* Go through linked list, freeing from the allocated (t[-1]) address. */ 45 p = t; 46 while (p != NULL) 47 { 48 q = (--p)->v.t; 49 PFDI_FREE(hfdi, p); 50 p = q; 51 } 52 } 53 54 /********************************************************* 55 * fdi_Ziphuft_build (internal) 56 */ 57 static cab_LONG fdi_Ziphuft_build(cab_ULONG *b, cab_ULONG n, cab_ULONG s, const cab_UWORD *d, const cab_UWORD *e, 58 struct Ziphuft **t, cab_LONG *m, fdi_decomp_state *decomp_state) 59 { 60 cab_ULONG a; /* counter for codes of length k */ 61 cab_ULONG el; /* length of EOB code (value 256) */ 62 cab_ULONG f; /* i repeats in table every f entries */ 63 cab_LONG g; /* maximum code length */ 64 cab_LONG h; /* table level */ 65 register cab_ULONG i; /* counter, current code */ 66 register cab_ULONG j; /* counter */ 67 register cab_LONG k; /* number of bits in current code */ 68 cab_LONG *l; /* stack of bits per table */ 69 register cab_ULONG *p; /* pointer into ZIP(c)[],ZIP(b)[],ZIP(v)[] */ 70 register struct Ziphuft *q; /* points to current table */ 71 struct Ziphuft r; /* table entry for structure assignment */ 72 register cab_LONG w; /* bits before this table == (l * h) */ 73 cab_ULONG *xp; /* pointer into x */ 74 cab_LONG y; /* number of dummy codes added */ 75 cab_ULONG z; /* number of entries in current table */ 76 77 l = ZIP(lx)+1; 78 79 /* Generate counts for each bit length */ 80 el = n > 256 ? b[256] : ZIPBMAX; /* set length of EOB code, if any */ 81 82 for(i = 0; i < ZIPBMAX+1; ++i) 83 ZIP(c)[i] = 0; 84 p = b; i = n; 85 do 86 { 87 ZIP(c)[*p]++; p++; /* assume all entries <= ZIPBMAX */ 88 } while (--i); 89 if (ZIP(c)[0] == n) /* null input--all zero length codes */ 90 { 91 *t = NULL; 92 *m = 0; 93 return 0; 94 } 95 96 /* Find minimum and maximum length, bound *m by those */ 97 for (j = 1; j <= ZIPBMAX; j++) 98 if (ZIP(c)[j]) 99 break; 100 k = j; /* minimum code length */ 101 if ((cab_ULONG)*m < j) 102 *m = j; 103 for (i = ZIPBMAX; i; i--) 104 if (ZIP(c)[i]) 105 break; 106 g = i; /* maximum code length */ 107 if ((cab_ULONG)*m > i) 108 *m = i; 109 110 /* Adjust last length count to fill out codes, if needed */ 111 for (y = 1 << j; j < i; j++, y <<= 1) 112 if ((y -= ZIP(c)[j]) < 0) 113 return 2; /* bad input: more codes than bits */ 114 if ((y -= ZIP(c)[i]) < 0) 115 return 2; 116 ZIP(c)[i] += y; 117 118 /* Generate starting offsets LONGo the value table for each length */ 119 ZIP(x)[1] = j = 0; 120 p = ZIP(c) + 1; xp = ZIP(x) + 2; 121 while (--i) 122 { /* note that i == g from above */ 123 *xp++ = (j += *p++); 124 } 125 126 /* Make a table of values in order of bit lengths */ 127 p = b; i = 0; 128 do{ 129 if ((j = *p++) != 0) 130 ZIP(v)[ZIP(x)[j]++] = i; 131 } while (++i < n); 132 133 134 /* Generate the Huffman codes and for each, make the table entries */ 135 ZIP(x)[0] = i = 0; /* first Huffman code is zero */ 136 p = ZIP(v); /* grab values in bit order */ 137 h = -1; /* no tables yet--level -1 */ 138 w = l[-1] = 0; /* no bits decoded yet */ 139 ZIP(u)[0] = NULL; /* just to keep compilers happy */ 140 q = NULL; /* ditto */ 141 z = 0; /* ditto */ 142 143 /* go through the bit lengths (k already is bits in shortest code) */ 144 for (; k <= g; k++) 145 { 146 a = ZIP(c)[k]; 147 while (a--) 148 { 149 /* here i is the Huffman code of length k bits for value *p */ 150 /* make tables up to required level */ 151 while (k > w + l[h]) 152 { 153 w += l[h++]; /* add bits already decoded */ 154 155 /* compute minimum size table less than or equal to *m bits */ 156 if ((z = g - w) > (cab_ULONG)*m) /* upper limit */ 157 z = *m; 158 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 159 { /* too few codes for k-w bit table */ 160 f -= a + 1; /* deduct codes from patterns left */ 161 xp = ZIP(c) + k; 162 while (++j < z) /* try smaller tables up to z bits */ 163 { 164 if ((f <<= 1) <= *++xp) 165 break; /* enough codes to use up j bits */ 166 f -= *xp; /* else deduct codes from patterns */ 167 } 168 } 169 if ((cab_ULONG)w + j > el && (cab_ULONG)w < el) 170 j = el - w; /* make EOB code end at table */ 171 z = 1 << j; /* table entries for j-bit table */ 172 l[h] = j; /* set table size in stack */ 173 174 /* allocate and link in new table */ 175 if (!(q = PFDI_ALLOC(CAB(hfdi), (z + 1)*sizeof(struct Ziphuft)))) 176 { 177 if(h) 178 fdi_Ziphuft_free(CAB(hfdi), ZIP(u)[0]); 179 return 3; /* not enough memory */ 180 } 181 *t = q + 1; /* link to list for Ziphuft_free() */ 182 *(t = &(q->v.t)) = NULL; 183 ZIP(u)[h] = ++q; /* table starts after link */ 184 185 /* connect to last table, if there is one */ 186 if (h) 187 { 188 ZIP(x)[h] = i; /* save pattern for backing up */ 189 r.b = (cab_UBYTE)l[h-1]; /* bits to dump before this table */ 190 r.e = (cab_UBYTE)(16 + j); /* bits in this table */ 191 r.v.t = q; /* pointer to this table */ 192 j = (i & ((1 << w) - 1)) >> (w - l[h-1]); 193 ZIP(u)[h-1][j] = r; /* connect to last table */ 194 } 195 } 196 197 /* set up table entry in r */ 198 r.b = (cab_UBYTE)(k - w); 199 if (p >= ZIP(v) + n) 200 r.e = 99; /* out of values--invalid code */ 201 else if (*p < s) 202 { 203 r.e = (cab_UBYTE)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 204 r.v.n = *p++; /* simple code is just the value */ 205 } 206 else 207 { 208 r.e = (cab_UBYTE)e[*p - s]; /* non-simple--look up in lists */ 209 r.v.n = d[*p++ - s]; 210 } 211 212 /* fill code-like entries with r */ 213 f = 1 << (k - w); 214 for (j = i >> w; j < z; j += f) 215 q[j] = r; 216 217 /* backwards increment the k-bit code i */ 218 for (j = 1 << (k - 1); i & j; j >>= 1) 219 i ^= j; 220 i ^= j; 221 222 /* backup over finished tables */ 223 while ((i & ((1 << w) - 1)) != ZIP(x)[h]) 224 w -= l[--h]; /* don't need to update q */ 225 } 226 } 227 228 /* return actual size of base table */ 229 *m = l[0]; 230 231 /* Return true (1) if we were given an incomplete table */ 232 return y != 0 && g != 1; 233 } 234 235 /********************************************************* 236 * fdi_Zipinflate_codes (internal) 237 */ 238 static cab_LONG fdi_Zipinflate_codes(const struct Ziphuft *tl, const struct Ziphuft *td, 239 cab_LONG bl, cab_LONG bd, fdi_decomp_state *decomp_state) 240 { 241 register cab_ULONG e; /* table entry flag/number of extra bits */ 242 cab_ULONG n, d; /* length and index for copy */ 243 cab_ULONG w; /* current window position */ 244 const struct Ziphuft *t; /* pointer to table entry */ 245 cab_ULONG ml, md; /* masks for bl and bd bits */ 246 register cab_ULONG b; /* bit buffer */ 247 register cab_ULONG k; /* number of bits in bit buffer */ 248 249 /* make local copies of globals */ 250 b = ZIP(bb); /* initialize bit buffer */ 251 k = ZIP(bk); 252 w = ZIP(window_posn); /* initialize window position */ 253 254 /* inflate the coded data */ 255 ml = Zipmask[bl]; /* precompute masks for speed */ 256 md = Zipmask[bd]; 257 258 for(;;) 259 { 260 ZIPNEEDBITS((cab_ULONG)bl) 261 if((e = (t = tl + (b & ml))->e) > 16) 262 do 263 { 264 if (e == 99) 265 return 1; 266 ZIPDUMPBITS(t->b) 267 e -= 16; 268 ZIPNEEDBITS(e) 269 } while ((e = (t = t->v.t + (b & Zipmask[e]))->e) > 16); 270 ZIPDUMPBITS(t->b) 271 if (e == 16) /* then it's a literal */ 272 CAB(outbuf)[w++] = (cab_UBYTE)t->v.n; 273 else /* it's an EOB or a length */ 274 { 275 /* exit if end of block */ 276 if(e == 15) 277 break; 278 279 /* get length of block to copy */ 280 ZIPNEEDBITS(e) 281 n = t->v.n + (b & Zipmask[e]); 282 ZIPDUMPBITS(e); 283 284 /* decode distance of block to copy */ 285 ZIPNEEDBITS((cab_ULONG)bd) 286 if ((e = (t = td + (b & md))->e) > 16) 287 do { 288 if (e == 99) 289 return 1; 290 ZIPDUMPBITS(t->b) 291 e -= 16; 292 ZIPNEEDBITS(e) 293 } while ((e = (t = t->v.t + (b & Zipmask[e]))->e) > 16); 294 ZIPDUMPBITS(t->b) 295 ZIPNEEDBITS(e) 296 d = w - t->v.n - (b & Zipmask[e]); 297 ZIPDUMPBITS(e) 298 do 299 { 300 d &= ZIPWSIZE - 1; 301 e = ZIPWSIZE - max(d, w); 302 e = min(e, n); 303 n -= e; 304 do 305 { 306 CAB(outbuf)[w++] = CAB(outbuf)[d++]; 307 } while (--e); 308 } while (n); 309 } 310 } 311 312 /* restore the globals from the locals */ 313 ZIP(window_posn) = w; /* restore global window pointer */ 314 ZIP(bb) = b; /* restore global bit buffer */ 315 ZIP(bk) = k; 316 317 /* done */ 318 return 0; 319 } 320 321 /*********************************************************** 322 * Zipinflate_stored (internal) 323 */ 324 static cab_LONG fdi_Zipinflate_stored(fdi_decomp_state *decomp_state) 325 /* "decompress" an inflated type 0 (stored) block. */ 326 { 327 cab_ULONG n; /* number of bytes in block */ 328 cab_ULONG w; /* current window position */ 329 register cab_ULONG b; /* bit buffer */ 330 register cab_ULONG k; /* number of bits in bit buffer */ 331 332 /* make local copies of globals */ 333 b = ZIP(bb); /* initialize bit buffer */ 334 k = ZIP(bk); 335 w = ZIP(window_posn); /* initialize window position */ 336 337 /* go to byte boundary */ 338 n = k & 7; 339 ZIPDUMPBITS(n); 340 341 /* get the length and its complement */ 342 ZIPNEEDBITS(16) 343 n = (b & 0xffff); 344 ZIPDUMPBITS(16) 345 ZIPNEEDBITS(16) 346 if (n != ((~b) & 0xffff)) 347 return 1; /* error in compressed data */ 348 ZIPDUMPBITS(16) 349 350 /* read and output the compressed data */ 351 while(n--) 352 { 353 ZIPNEEDBITS(8) 354 CAB(outbuf)[w++] = (cab_UBYTE)b; 355 ZIPDUMPBITS(8) 356 } 357 358 /* restore the globals from the locals */ 359 ZIP(window_posn) = w; /* restore global window pointer */ 360 ZIP(bb) = b; /* restore global bit buffer */ 361 ZIP(bk) = k; 362 return 0; 363 } 364 365 /****************************************************** 366 * fdi_Zipinflate_fixed (internal) 367 */ 368 static cab_LONG fdi_Zipinflate_fixed(fdi_decomp_state *decomp_state) 369 { 370 struct Ziphuft *fixed_tl; 371 struct Ziphuft *fixed_td; 372 cab_LONG fixed_bl, fixed_bd; 373 cab_LONG i; /* temporary variable */ 374 cab_ULONG *l; 375 376 l = ZIP(ll); 377 378 /* literal table */ 379 for(i = 0; i < 144; i++) 380 l[i] = 8; 381 for(; i < 256; i++) 382 l[i] = 9; 383 for(; i < 280; i++) 384 l[i] = 7; 385 for(; i < 288; i++) /* make a complete, but wrong code set */ 386 l[i] = 8; 387 fixed_bl = 7; 388 if((i = fdi_Ziphuft_build(l, 288, 257, Zipcplens, Zipcplext, &fixed_tl, &fixed_bl, decomp_state))) 389 return i; 390 391 /* distance table */ 392 for(i = 0; i < 30; i++) /* make an incomplete code set */ 393 l[i] = 5; 394 fixed_bd = 5; 395 if((i = fdi_Ziphuft_build(l, 30, 0, Zipcpdist, Zipcpdext, &fixed_td, &fixed_bd, decomp_state)) > 1) 396 { 397 fdi_Ziphuft_free(CAB(hfdi), fixed_tl); 398 return i; 399 } 400 401 /* decompress until an end-of-block code */ 402 i = fdi_Zipinflate_codes(fixed_tl, fixed_td, fixed_bl, fixed_bd, decomp_state); 403 404 fdi_Ziphuft_free(CAB(hfdi), fixed_td); 405 fdi_Ziphuft_free(CAB(hfdi), fixed_tl); 406 return i; 407 } 408 409 /************************************************************** 410 * fdi_Zipinflate_dynamic (internal) 411 */ 412 static cab_LONG fdi_Zipinflate_dynamic(fdi_decomp_state *decomp_state) 413 /* decompress an inflated type 2 (dynamic Huffman codes) block. */ 414 { 415 cab_LONG i; /* temporary variables */ 416 cab_ULONG j; 417 cab_ULONG *ll; 418 cab_ULONG l; /* last length */ 419 cab_ULONG m; /* mask for bit lengths table */ 420 cab_ULONG n; /* number of lengths to get */ 421 struct Ziphuft *tl; /* literal/length code table */ 422 struct Ziphuft *td; /* distance code table */ 423 cab_LONG bl; /* lookup bits for tl */ 424 cab_LONG bd; /* lookup bits for td */ 425 cab_ULONG nb; /* number of bit length codes */ 426 cab_ULONG nl; /* number of literal/length codes */ 427 cab_ULONG nd; /* number of distance codes */ 428 register cab_ULONG b; /* bit buffer */ 429 register cab_ULONG k; /* number of bits in bit buffer */ 430 431 /* make local bit buffer */ 432 b = ZIP(bb); 433 k = ZIP(bk); 434 ll = ZIP(ll); 435 436 /* read in table lengths */ 437 ZIPNEEDBITS(5) 438 nl = 257 + (b & 0x1f); /* number of literal/length codes */ 439 ZIPDUMPBITS(5) 440 ZIPNEEDBITS(5) 441 nd = 1 + (b & 0x1f); /* number of distance codes */ 442 ZIPDUMPBITS(5) 443 ZIPNEEDBITS(4) 444 nb = 4 + (b & 0xf); /* number of bit length codes */ 445 ZIPDUMPBITS(4) 446 if(nl > 288 || nd > 32) 447 return 1; /* bad lengths */ 448 449 /* read in bit-length-code lengths */ 450 for(j = 0; j < nb; j++) 451 { 452 ZIPNEEDBITS(3) 453 ll[Zipborder[j]] = b & 7; 454 ZIPDUMPBITS(3) 455 } 456 for(; j < 19; j++) 457 ll[Zipborder[j]] = 0; 458 459 /* build decoding table for trees--single level, 7 bit lookup */ 460 bl = 7; 461 if((i = fdi_Ziphuft_build(ll, 19, 19, NULL, NULL, &tl, &bl, decomp_state)) != 0) 462 { 463 if(i == 1) 464 fdi_Ziphuft_free(CAB(hfdi), tl); 465 return i; /* incomplete code set */ 466 } 467 468 /* read in literal and distance code lengths */ 469 n = nl + nd; 470 m = Zipmask[bl]; 471 i = l = 0; 472 while((cab_ULONG)i < n) 473 { 474 ZIPNEEDBITS((cab_ULONG)bl) 475 j = (td = tl + (b & m))->b; 476 ZIPDUMPBITS(j) 477 j = td->v.n; 478 if (j < 16) /* length of code in bits (0..15) */ 479 ll[i++] = l = j; /* save last length in l */ 480 else if (j == 16) /* repeat last length 3 to 6 times */ 481 { 482 ZIPNEEDBITS(2) 483 j = 3 + (b & 3); 484 ZIPDUMPBITS(2) 485 if((cab_ULONG)i + j > n) 486 return 1; 487 while (j--) 488 ll[i++] = l; 489 } 490 else if (j == 17) /* 3 to 10 zero length codes */ 491 { 492 ZIPNEEDBITS(3) 493 j = 3 + (b & 7); 494 ZIPDUMPBITS(3) 495 if ((cab_ULONG)i + j > n) 496 return 1; 497 while (j--) 498 ll[i++] = 0; 499 l = 0; 500 } 501 else /* j == 18: 11 to 138 zero length codes */ 502 { 503 ZIPNEEDBITS(7) 504 j = 11 + (b & 0x7f); 505 ZIPDUMPBITS(7) 506 if ((cab_ULONG)i + j > n) 507 return 1; 508 while (j--) 509 ll[i++] = 0; 510 l = 0; 511 } 512 } 513 514 /* free decoding table for trees */ 515 fdi_Ziphuft_free(CAB(hfdi), tl); 516 517 /* restore the global bit buffer */ 518 ZIP(bb) = b; 519 ZIP(bk) = k; 520 521 /* build the decoding tables for literal/length and distance codes */ 522 bl = ZIPLBITS; 523 if((i = fdi_Ziphuft_build(ll, nl, 257, Zipcplens, Zipcplext, &tl, &bl, decomp_state)) != 0) 524 { 525 if(i == 1) 526 fdi_Ziphuft_free(CAB(hfdi), tl); 527 return i; /* incomplete code set */ 528 } 529 bd = ZIPDBITS; 530 fdi_Ziphuft_build(ll + nl, nd, 0, Zipcpdist, Zipcpdext, &td, &bd, decomp_state); 531 532 /* decompress until an end-of-block code */ 533 if(fdi_Zipinflate_codes(tl, td, bl, bd, decomp_state)) 534 return 1; 535 536 /* free the decoding tables, return */ 537 fdi_Ziphuft_free(CAB(hfdi), tl); 538 fdi_Ziphuft_free(CAB(hfdi), td); 539 return 0; 540 } 541 542 /***************************************************** 543 * fdi_Zipinflate_block (internal) 544 */ 545 static cab_LONG fdi_Zipinflate_block(cab_LONG *e, fdi_decomp_state *decomp_state) /* e == last block flag */ 546 { /* decompress an inflated block */ 547 cab_ULONG t; /* block type */ 548 register cab_ULONG b; /* bit buffer */ 549 register cab_ULONG k; /* number of bits in bit buffer */ 550 551 /* make local bit buffer */ 552 b = ZIP(bb); 553 k = ZIP(bk); 554 555 /* read in last block bit */ 556 ZIPNEEDBITS(1) 557 *e = (cab_LONG)b & 1; 558 ZIPDUMPBITS(1) 559 560 /* read in block type */ 561 ZIPNEEDBITS(2) 562 t = b & 3; 563 ZIPDUMPBITS(2) 564 565 /* restore the global bit buffer */ 566 ZIP(bb) = b; 567 ZIP(bk) = k; 568 569 /* inflate that block type */ 570 if(t == 2) 571 return fdi_Zipinflate_dynamic(decomp_state); 572 if(t == 0) 573 return fdi_Zipinflate_stored(decomp_state); 574 if(t == 1) 575 return fdi_Zipinflate_fixed(decomp_state); 576 /* bad block type */ 577 return 2; 578 } 579 580 /**************************************************** 581 * ZIPfdi_decomp(internal) 582 */ 583 static int ZIPfdi_decomp(int inlen, int outlen, fdi_decomp_state *decomp_state) 584 { 585 cab_LONG e; /* last block flag */ 586 587 TRACE("(inlen == %d, outlen == %d)\n", inlen, outlen); 588 589 ZIP(inpos) = CAB(inbuf); 590 ZIP(bb) = ZIP(bk) = ZIP(window_posn) = 0; 591 592 if(outlen > ZIPWSIZE) 593 return DECR_DATAFORMAT; 594 595 /* CK = Chris Kirmse, official Microsoft purloiner */ 596 if(ZIP(inpos)[0] != 0x43 || ZIP(inpos)[1] != 0x4B) 597 return DECR_ILLEGALDATA; 598 599 ZIP(inpos) += 2; 600 601 do { 602 if(fdi_Zipinflate_block(&e, decomp_state)) 603 return DECR_ILLEGALDATA; 604 } while(!e); 605 606 /* return success */ 607 return DECR_OK; 608 } 609 610 static void * __cdecl fdi_alloc(ULONG cb) 611 { 612 return HeapAlloc(GetProcessHeap(), 0, cb); 613 } 614 615 static void __cdecl fdi_free(void *pv) 616 { 617 HeapFree(GetProcessHeap(), 0, pv); 618 } 619 620 int mszip_decompress(unsigned int inlen, unsigned int outlen, char* inbuffer, char* outbuffer) 621 { 622 int ret; 623 fdi_decomp_state decomp_state; 624 FDI_Int fdi; 625 626 TRACE("(%u, %u, %p, %p)\n", inlen, outlen, inbuffer, outbuffer); 627 628 if ((inlen > CAB_INPUTMAX) || (outlen > CAB_BLOCKMAX)) 629 { 630 FIXME("Big file not supported yet (inlen = %u, outlen = %u)\n", inlen, outlen); 631 return DECR_DATAFORMAT; 632 } 633 634 fdi.pfnalloc = fdi_alloc; 635 fdi.pfnfree = fdi_free; 636 decomp_state.hfdi = (void*)&fdi; 637 638 memcpy(decomp_state.inbuf, inbuffer, inlen); 639 640 ret = ZIPfdi_decomp(inlen, outlen, &decomp_state); 641 642 memcpy(outbuffer, decomp_state.outbuf, outlen); 643 644 return ret; 645 } 646