2 * MSZIP decompression (taken from fdi.c of cabinet dll)
4 * Copyright 2000-2002 Stuart Caie
5 * Copyright 2002 Patrik Stridvall
6 * Copyright 2003 Greg Turner
7 * Copyright 2010 Christian Costa
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.
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.
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
29 #include "wine/debug.h"
33 WINE_DEFAULT_DEBUG_CHANNEL(d3dxof
);
37 /********************************************************
38 * Ziphuft_free (internal)
40 static void fdi_Ziphuft_free(HFDI hfdi
, struct Ziphuft
*t
)
42 register struct Ziphuft
*p
, *q
;
44 /* Go through linked list, freeing from the allocated (t[-1]) address. */
54 /*********************************************************
55 * fdi_Ziphuft_build (internal)
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
)
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 */
79 /* Generate counts for each bit length */
80 el
= n
> 256 ? b
[256] : ZIPBMAX
; /* set length of EOB code, if any */
82 for(i
= 0; i
< ZIPBMAX
+1; ++i
)
87 ZIP(c
)[*p
]++; p
++; /* assume all entries <= ZIPBMAX */
89 if (ZIP(c
)[0] == n
) /* null input--all zero length codes */
96 /* Find minimum and maximum length, bound *m by those */
97 for (j
= 1; j
<= ZIPBMAX
; j
++)
100 k
= j
; /* minimum code length */
101 if ((cab_ULONG
)*m
< j
)
103 for (i
= ZIPBMAX
; i
; i
--)
106 g
= i
; /* maximum code length */
107 if ((cab_ULONG
)*m
> i
)
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)
118 /* Generate starting offsets LONGo the value table for each length */
120 p
= ZIP(c
) + 1; xp
= ZIP(x
) + 2;
122 { /* note that i == g from above */
126 /* Make a table of values in order of bit lengths */
130 ZIP(v
)[ZIP(x
)[j
]++] = i
;
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 */
143 /* go through the bit lengths (k already is bits in shortest code) */
149 /* here i is the Huffman code of length k bits for value *p */
150 /* make tables up to required level */
153 w
+= l
[h
++]; /* add bits already decoded */
155 /* compute minimum size table less than or equal to *m bits */
156 if ((z
= g
- w
) > (cab_ULONG
)*m
) /* upper limit */
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 */
162 while (++j
< z
) /* try smaller tables up to z bits */
164 if ((f
<<= 1) <= *++xp
)
165 break; /* enough codes to use up j bits */
166 f
-= *xp
; /* else deduct codes from patterns */
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 */
174 /* allocate and link in new table */
175 if (!(q
= PFDI_ALLOC(CAB(hfdi
), (z
+ 1)*sizeof(struct Ziphuft
))))
178 fdi_Ziphuft_free(CAB(hfdi
), ZIP(u
)[0]);
179 return 3; /* not enough memory */
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 */
185 /* connect to last table, if there is one */
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 */
197 /* set up table entry in r */
198 r
.b
= (cab_UBYTE
)(k
- w
);
200 r
.e
= 99; /* out of values--invalid code */
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 */
208 r
.e
= (cab_UBYTE
)e
[*p
- s
]; /* non-simple--look up in lists */
212 /* fill code-like entries with r */
214 for (j
= i
>> w
; j
< z
; j
+= f
)
217 /* backwards increment the k-bit code i */
218 for (j
= 1 << (k
- 1); i
& j
; j
>>= 1)
222 /* backup over finished tables */
223 while ((i
& ((1 << w
) - 1)) != ZIP(x
)[h
])
224 w
-= l
[--h
]; /* don't need to update q */
228 /* return actual size of base table */
231 /* Return true (1) if we were given an incomplete table */
232 return y
!= 0 && g
!= 1;
235 /*********************************************************
236 * fdi_Zipinflate_codes (internal)
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
)
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 */
249 /* make local copies of globals */
250 b
= ZIP(bb
); /* initialize bit buffer */
252 w
= ZIP(window_posn
); /* initialize window position */
254 /* inflate the coded data */
255 ml
= Zipmask
[bl
]; /* precompute masks for speed */
260 ZIPNEEDBITS((cab_ULONG
)bl
)
261 if((e
= (t
= tl
+ (b
& ml
))->e
) > 16)
269 } while ((e
= (t
= t
->v
.t
+ (b
& Zipmask
[e
]))->e
) > 16);
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 */
275 /* exit if end of block */
279 /* get length of block to copy */
281 n
= t
->v
.n
+ (b
& Zipmask
[e
]);
284 /* decode distance of block to copy */
285 ZIPNEEDBITS((cab_ULONG
)bd
)
286 if ((e
= (t
= td
+ (b
& md
))->e
) > 16)
293 } while ((e
= (t
= t
->v
.t
+ (b
& Zipmask
[e
]))->e
) > 16);
296 d
= w
- t
->v
.n
- (b
& Zipmask
[e
]);
301 e
= ZIPWSIZE
- max(d
, w
);
306 CAB(outbuf
)[w
++] = CAB(outbuf
)[d
++];
312 /* restore the globals from the locals */
313 ZIP(window_posn
) = w
; /* restore global window pointer */
314 ZIP(bb
) = b
; /* restore global bit buffer */
321 /***********************************************************
322 * Zipinflate_stored (internal)
324 static cab_LONG
fdi_Zipinflate_stored(fdi_decomp_state
*decomp_state
)
325 /* "decompress" an inflated type 0 (stored) block. */
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 */
332 /* make local copies of globals */
333 b
= ZIP(bb
); /* initialize bit buffer */
335 w
= ZIP(window_posn
); /* initialize window position */
337 /* go to byte boundary */
341 /* get the length and its complement */
346 if (n
!= ((~b
) & 0xffff))
347 return 1; /* error in compressed data */
350 /* read and output the compressed data */
354 CAB(outbuf
)[w
++] = (cab_UBYTE
)b
;
358 /* restore the globals from the locals */
359 ZIP(window_posn
) = w
; /* restore global window pointer */
360 ZIP(bb
) = b
; /* restore global bit buffer */
365 /******************************************************
366 * fdi_Zipinflate_fixed (internal)
368 static cab_LONG
fdi_Zipinflate_fixed(fdi_decomp_state
*decomp_state
)
370 struct Ziphuft
*fixed_tl
;
371 struct Ziphuft
*fixed_td
;
372 cab_LONG fixed_bl
, fixed_bd
;
373 cab_LONG i
; /* temporary variable */
379 for(i
= 0; i
< 144; i
++)
385 for(; i
< 288; i
++) /* make a complete, but wrong code set */
388 if((i
= fdi_Ziphuft_build(l
, 288, 257, Zipcplens
, Zipcplext
, &fixed_tl
, &fixed_bl
, decomp_state
)))
392 for(i
= 0; i
< 30; i
++) /* make an incomplete code set */
395 if((i
= fdi_Ziphuft_build(l
, 30, 0, Zipcpdist
, Zipcpdext
, &fixed_td
, &fixed_bd
, decomp_state
)) > 1)
397 fdi_Ziphuft_free(CAB(hfdi
), fixed_tl
);
401 /* decompress until an end-of-block code */
402 i
= fdi_Zipinflate_codes(fixed_tl
, fixed_td
, fixed_bl
, fixed_bd
, decomp_state
);
404 fdi_Ziphuft_free(CAB(hfdi
), fixed_td
);
405 fdi_Ziphuft_free(CAB(hfdi
), fixed_tl
);
409 /**************************************************************
410 * fdi_Zipinflate_dynamic (internal)
412 static cab_LONG
fdi_Zipinflate_dynamic(fdi_decomp_state
*decomp_state
)
413 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
415 cab_LONG i
; /* temporary variables */
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 */
431 /* make local bit buffer */
436 /* read in table lengths */
438 nl
= 257 + (b
& 0x1f); /* number of literal/length codes */
441 nd
= 1 + (b
& 0x1f); /* number of distance codes */
444 nb
= 4 + (b
& 0xf); /* number of bit length codes */
446 if(nl
> 288 || nd
> 32)
447 return 1; /* bad lengths */
449 /* read in bit-length-code lengths */
450 for(j
= 0; j
< nb
; j
++)
453 ll
[Zipborder
[j
]] = b
& 7;
457 ll
[Zipborder
[j
]] = 0;
459 /* build decoding table for trees--single level, 7 bit lookup */
461 if((i
= fdi_Ziphuft_build(ll
, 19, 19, NULL
, NULL
, &tl
, &bl
, decomp_state
)) != 0)
464 fdi_Ziphuft_free(CAB(hfdi
), tl
);
465 return i
; /* incomplete code set */
468 /* read in literal and distance code lengths */
472 while((cab_ULONG
)i
< n
)
474 ZIPNEEDBITS((cab_ULONG
)bl
)
475 j
= (td
= tl
+ (b
& m
))->b
;
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 */
485 if((cab_ULONG
)i
+ j
> n
)
490 else if (j
== 17) /* 3 to 10 zero length codes */
495 if ((cab_ULONG
)i
+ j
> n
)
501 else /* j == 18: 11 to 138 zero length codes */
506 if ((cab_ULONG
)i
+ j
> n
)
514 /* free decoding table for trees */
515 fdi_Ziphuft_free(CAB(hfdi
), tl
);
517 /* restore the global bit buffer */
521 /* build the decoding tables for literal/length and distance codes */
523 if((i
= fdi_Ziphuft_build(ll
, nl
, 257, Zipcplens
, Zipcplext
, &tl
, &bl
, decomp_state
)) != 0)
526 fdi_Ziphuft_free(CAB(hfdi
), tl
);
527 return i
; /* incomplete code set */
530 fdi_Ziphuft_build(ll
+ nl
, nd
, 0, Zipcpdist
, Zipcpdext
, &td
, &bd
, decomp_state
);
532 /* decompress until an end-of-block code */
533 if(fdi_Zipinflate_codes(tl
, td
, bl
, bd
, decomp_state
))
536 /* free the decoding tables, return */
537 fdi_Ziphuft_free(CAB(hfdi
), tl
);
538 fdi_Ziphuft_free(CAB(hfdi
), td
);
542 /*****************************************************
543 * fdi_Zipinflate_block (internal)
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 */
551 /* make local bit buffer */
555 /* read in last block bit */
557 *e
= (cab_LONG
)b
& 1;
560 /* read in block type */
565 /* restore the global bit buffer */
569 /* inflate that block type */
571 return fdi_Zipinflate_dynamic(decomp_state
);
573 return fdi_Zipinflate_stored(decomp_state
);
575 return fdi_Zipinflate_fixed(decomp_state
);
580 /****************************************************
581 * ZIPfdi_decomp(internal)
583 static int ZIPfdi_decomp(int inlen
, int outlen
, fdi_decomp_state
*decomp_state
)
585 cab_LONG e
; /* last block flag */
587 TRACE("(inlen == %d, outlen == %d)\n", inlen
, outlen
);
589 ZIP(inpos
) = CAB(inbuf
);
590 ZIP(bb
) = ZIP(bk
) = ZIP(window_posn
) = 0;
592 if(outlen
> ZIPWSIZE
)
593 return DECR_DATAFORMAT
;
595 /* CK = Chris Kirmse, official Microsoft purloiner */
596 if(ZIP(inpos
)[0] != 0x43 || ZIP(inpos
)[1] != 0x4B)
597 return DECR_ILLEGALDATA
;
602 if(fdi_Zipinflate_block(&e
, decomp_state
))
603 return DECR_ILLEGALDATA
;
610 void * __cdecl
fdi_alloc(ULONG cb
)
612 return HeapAlloc(GetProcessHeap(), 0, cb
);
615 void __cdecl
fdi_free(void *pv
)
617 HeapFree(GetProcessHeap(), 0, pv
);
620 int mszip_decompress(unsigned int inlen
, unsigned int outlen
, char* inbuffer
, char* outbuffer
)
623 fdi_decomp_state decomp_state
;
626 TRACE("(%u, %u, %p, %p)\n", inlen
, outlen
, inbuffer
, outbuffer
);
628 if ((inlen
> CAB_INPUTMAX
) || (outlen
> CAB_BLOCKMAX
))
630 FIXME("Big file not supported yet (inlen = %u, outlen = %u)\n", inlen
, outlen
);
631 return DECR_DATAFORMAT
;
634 fdi
.pfnalloc
= fdi_alloc
;
635 fdi
.pfnfree
= fdi_free
;
636 decomp_state
.hfdi
= (void*)&fdi
;
638 memcpy(decomp_state
.inbuf
, inbuffer
, inlen
);
640 ret
= ZIPfdi_decomp(inlen
, outlen
, &decomp_state
);
642 memcpy(outbuffer
, decomp_state
.outbuf
, outlen
);