?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
d2d1/tests: Add a basic clipping test.
[wine.git] / dlls / d3dxof / mszip.c
blob179661634f7b58e6e5ceff7079485985c380e714
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 }
Windows API implementation