wmiutils: Implement IWbemPath::SetNamespaceAt.
[wine] / dlls / d3dxof / mszip.c
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 }