ReactOS  0.4.12-dev-418-g3df31a8
lzx.c
Go to the documentation of this file.
1 /***************************************************************************
2  * lzx.c - LZX decompression routines *
3  * ------------------- *
4  * *
5  * maintainer: Jed Wing <jedwin@ugcs.caltech.edu> *
6  * source: modified lzx.c from cabextract v0.5 *
7  * notes: This file was taken from cabextract v0.5, which was, *
8  * itself, a modified version of the lzx decompression code *
9  * from unlzx. *
10  * *
11  * platforms: In its current incarnation, this file has been tested on *
12  * two different Linux platforms (one, redhat-based, with a *
13  * 2.1.2 glibc and gcc 2.95.x, and the other, Debian, with *
14  * 2.2.4 glibc and both gcc 2.95.4 and gcc 3.0.2). Both were *
15  * Intel x86 compatible machines. *
16  ***************************************************************************/
17 
18 /***************************************************************************
19  *
20  * Copyright(C) Stuart Caie
21  *
22  * This library is free software; you can redistribute it and/or
23  * modify it under the terms of the GNU Lesser General Public
24  * License as published by the Free Software Foundation; either
25  * version 2.1 of the License, or (at your option) any later version.
26  *
27  * This library is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
30  * Lesser General Public License for more details.
31  *
32  * You should have received a copy of the GNU Lesser General Public
33  * License along with this library; if not, write to the Free Software
34  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
35  *
36  ***************************************************************************/
37 
38 #include "lzx.h"
39 #include <stdarg.h>
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43 
44 #include "windef.h"
45 #include "winbase.h"
46 
47 /* sized types */
48 typedef unsigned char UBYTE; /* 8 bits exactly */
49 typedef unsigned short UWORD; /* 16 bits (or more) */
50 
51 /* some constants defined by the LZX specification */
52 #define LZX_MIN_MATCH (2)
53 #define LZX_MAX_MATCH (257)
54 #define LZX_NUM_CHARS (256)
55 #define LZX_BLOCKTYPE_INVALID (0) /* also blocktypes 4-7 invalid */
56 #define LZX_BLOCKTYPE_VERBATIM (1)
57 #define LZX_BLOCKTYPE_ALIGNED (2)
58 #define LZX_BLOCKTYPE_UNCOMPRESSED (3)
59 #define LZX_PRETREE_NUM_ELEMENTS (20)
60 #define LZX_ALIGNED_NUM_ELEMENTS (8) /* aligned offset tree #elements */
61 #define LZX_NUM_PRIMARY_LENGTHS (7) /* this one missing from spec! */
62 #define LZX_NUM_SECONDARY_LENGTHS (249) /* length tree #elements */
63 
64 /* LZX huffman defines: tweak tablebits as desired */
65 #define LZX_PRETREE_MAXSYMBOLS (LZX_PRETREE_NUM_ELEMENTS)
66 #define LZX_PRETREE_TABLEBITS (6)
67 #define LZX_MAINTREE_MAXSYMBOLS (LZX_NUM_CHARS + 50*8)
68 #define LZX_MAINTREE_TABLEBITS (12)
69 #define LZX_LENGTH_MAXSYMBOLS (LZX_NUM_SECONDARY_LENGTHS+1)
70 #define LZX_LENGTH_TABLEBITS (12)
71 #define LZX_ALIGNED_MAXSYMBOLS (LZX_ALIGNED_NUM_ELEMENTS)
72 #define LZX_ALIGNED_TABLEBITS (7)
73 
74 #define LZX_LENTABLE_SAFETY (64) /* we allow length table decoding overruns */
75 
76 #define LZX_DECLARE_TABLE(tbl) \
77  UWORD tbl##_table[(1<<LZX_##tbl##_TABLEBITS) + (LZX_##tbl##_MAXSYMBOLS<<1)];\
78  UBYTE tbl##_len [LZX_##tbl##_MAXSYMBOLS + LZX_LENTABLE_SAFETY]
79 
80 struct LZXstate
81 {
82  UBYTE *window; /* the actual decoding window */
83  ULONG window_size; /* window size (32Kb through 2Mb) */
84  ULONG actual_size; /* window size when it was first allocated */
85  ULONG window_posn; /* current offset within the window */
86  ULONG R0, R1, R2; /* for the LRU offset system */
87  UWORD main_elements; /* number of main tree elements */
88  int header_read; /* have we started decoding at all yet? */
89  UWORD block_type; /* type of this block */
90  ULONG block_length; /* uncompressed length of this block */
91  ULONG block_remaining; /* uncompressed bytes still left to decode */
92  ULONG frames_read; /* the number of CFDATA blocks processed */
93  LONG intel_filesize; /* magic header value used for transform */
94  LONG intel_curpos; /* current offset in transform space */
95  int intel_started; /* have we seen any translatable data yet? */
96 
97  LZX_DECLARE_TABLE(PRETREE);
98  LZX_DECLARE_TABLE(MAINTREE);
101 };
102 
103 /* LZX decruncher */
104 
105 /* Microsoft's LZX document and their implementation of the
106  * com.ms.util.cab Java package do not concur.
107  *
108  * In the LZX document, there is a table showing the correlation between
109  * window size and the number of position slots. It states that the 1MB
110  * window = 40 slots and the 2MB window = 42 slots. In the implementation,
111  * 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the
112  * first slot whose position base is equal to or more than the required
113  * window size'. This would explain why other tables in the document refer
114  * to 50 slots rather than 42.
115  *
116  * The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode
117  * is not defined in the specification.
118  *
119  * The LZX document does not state the uncompressed block has an
120  * uncompressed length field. Where does this length field come from, so
121  * we can know how large the block is? The implementation has it as the 24
122  * bits following after the 3 blocktype bits, before the alignment
123  * padding.
124  *
125  * The LZX document states that aligned offset blocks have their aligned
126  * offset huffman tree AFTER the main and length trees. The implementation
127  * suggests that the aligned offset tree is BEFORE the main and length
128  * trees.
129  *
130  * The LZX document decoding algorithm states that, in an aligned offset
131  * block, if an extra_bits value is 1, 2 or 3, then that number of bits
132  * should be read and the result added to the match offset. This is
133  * correct for 1 and 2, but not 3, where just a huffman symbol (using the
134  * aligned tree) should be read.
135  *
136  * Regarding the E8 preprocessing, the LZX document states 'No translation
137  * may be performed on the last 6 bytes of the input block'. This is
138  * correct. However, the pseudocode provided checks for the *E8 leader*
139  * up to the last 6 bytes. If the leader appears between -10 and -7 bytes
140  * from the end, this would cause the next four bytes to be modified, at
141  * least one of which would be in the last 6 bytes, which is not allowed
142  * according to the spec.
143  *
144  * The specification states that the huffman trees must always contain at
145  * least one element. However, many CAB files contain blocks where the
146  * length tree is completely empty (because there are no matches), and
147  * this is expected to succeed.
148  */
149 
150 
151 /* LZX uses what it calls 'position slots' to represent match offsets.
152  * What this means is that a small 'position slot' number and a small
153  * offset from that slot are encoded instead of one large offset for
154  * every match.
155  * - position_base is an index to the position slot bases
156  * - extra_bits states how many bits of offset-from-base data is needed.
157  */
158 static const UBYTE extra_bits[51] = {
159  0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
160  7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14,
161  15, 15, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
162  17, 17, 17
163 };
164 
165 static const ULONG position_base[51] = {
166  0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192,
167  256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152,
168  65536, 98304, 131072, 196608, 262144, 393216, 524288, 655360, 786432, 917504, 1048576, 1179648, 1310720, 1441792, 1572864, 1703936,
169  1835008, 1966080, 2097152
170 };
171 
172 struct LZXstate *LZXinit(int window)
173 {
174  struct LZXstate *pState=NULL;
175  ULONG wndsize = 1 << window;
176  int i, posn_slots;
177 
178  /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
179  /* if a previously allocated window is big enough, keep it */
180  if (window < 15 || window > 21) return NULL;
181 
182  /* allocate state and associated window */
183  pState = HeapAlloc(GetProcessHeap(), 0, sizeof(struct LZXstate));
184  if (!(pState->window = HeapAlloc(GetProcessHeap(), 0, wndsize)))
185  {
186  HeapFree(GetProcessHeap(), 0, pState);
187  return NULL;
188  }
189  pState->actual_size = wndsize;
190  pState->window_size = wndsize;
191 
192  /* calculate required position slots */
193  if (window == 20) posn_slots = 42;
194  else if (window == 21) posn_slots = 50;
195  else posn_slots = window << 1;
196 
198  /* posn_slots=i=0; while (i < wndsize) i += 1 << extra_bits[posn_slots++]; */
199 
200  /* initialize other state */
201  pState->R0 = pState->R1 = pState->R2 = 1;
202  pState->main_elements = LZX_NUM_CHARS + (posn_slots << 3);
203  pState->header_read = 0;
204  pState->frames_read = 0;
205  pState->block_remaining = 0;
207  pState->intel_curpos = 0;
208  pState->intel_started = 0;
209  pState->window_posn = 0;
210 
211  /* initialise tables to 0 (because deltas will be applied to them) */
212  for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) pState->MAINTREE_len[i] = 0;
213  for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) pState->LENGTH_len[i] = 0;
214 
215  return pState;
216 }
217 
218 void LZXteardown(struct LZXstate *pState)
219 {
220  if (pState)
221  {
222  HeapFree(GetProcessHeap(), 0, pState->window);
223  HeapFree(GetProcessHeap(), 0, pState);
224  }
225 }
226 
227 int LZXreset(struct LZXstate *pState)
228 {
229  int i;
230 
231  pState->R0 = pState->R1 = pState->R2 = 1;
232  pState->header_read = 0;
233  pState->frames_read = 0;
234  pState->block_remaining = 0;
236  pState->intel_curpos = 0;
237  pState->intel_started = 0;
238  pState->window_posn = 0;
239 
240  for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS + LZX_LENTABLE_SAFETY; i++) pState->MAINTREE_len[i] = 0;
241  for (i = 0; i < LZX_LENGTH_MAXSYMBOLS + LZX_LENTABLE_SAFETY; i++) pState->LENGTH_len[i] = 0;
242 
243  return DECR_OK;
244 }
245 
246 
247 /* Bitstream reading macros:
248  *
249  * INIT_BITSTREAM should be used first to set up the system
250  * READ_BITS(var,n) takes N bits from the buffer and puts them in var
251  *
252  * ENSURE_BITS(n) ensures there are at least N bits in the bit buffer
253  * PEEK_BITS(n) extracts (without removing) N bits from the bit buffer
254  * REMOVE_BITS(n) removes N bits from the bit buffer
255  *
256  * These bit access routines work by using the area beyond the MSB and the
257  * LSB as a free source of zeroes. This avoids having to mask any bits.
258  * So we have to know the bit width of the bitbuffer variable. This is
259  * sizeof(ULONG) * 8, also defined as ULONG_BITS
260  */
261 
262 /* number of bits in ULONG. Note: This must be at multiple of 16, and at
263  * least 32 for the bitbuffer code to work (ie, it must be able to ensure
264  * up to 17 bits - that's adding 16 bits when there's one bit left, or
265  * adding 32 bits when there are no bits left. The code should work fine
266  * for machines where ULONG >= 32 bits.
267  */
268 #define ULONG_BITS (sizeof(ULONG)<<3)
269 
270 #define INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0)
271 
272 #define ENSURE_BITS(n) \
273  while (bitsleft < (n)) { \
274  bitbuf |= ((inpos[1]<<8)|inpos[0]) << (ULONG_BITS-16 - bitsleft); \
275  bitsleft += 16; inpos+=2; \
276  }
277 
278 #define PEEK_BITS(n) (bitbuf >> (ULONG_BITS - (n)))
279 #define REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n)))
280 
281 #define READ_BITS(v,n) do { \
282  ENSURE_BITS(n); \
283  (v) = PEEK_BITS(n); \
284  REMOVE_BITS(n); \
285 } while (0)
286 
287 
288 /* Huffman macros */
289 
290 #define TABLEBITS(tbl) (LZX_##tbl##_TABLEBITS)
291 #define MAXSYMBOLS(tbl) (LZX_##tbl##_MAXSYMBOLS)
292 #define SYMTABLE(tbl) (pState->tbl##_table)
293 #define LENTABLE(tbl) (pState->tbl##_len)
294 
295 /* BUILD_TABLE(tablename) builds a huffman lookup table from code lengths.
296  * In reality, it just calls make_decode_table() with the appropriate
297  * values - they're all fixed by some #defines anyway, so there's no point
298  * writing each call out in full by hand.
299  */
300 #define BUILD_TABLE(tbl) \
301  if (make_decode_table( \
302  MAXSYMBOLS(tbl), TABLEBITS(tbl), LENTABLE(tbl), SYMTABLE(tbl) \
303  )) { return DECR_ILLEGALDATA; }
304 
305 
306 /* READ_HUFFSYM(tablename, var) decodes one huffman symbol from the
307  * bitstream using the stated table and puts it in var.
308  */
309 #define READ_HUFFSYM(tbl,var) do { \
310  ENSURE_BITS(16); \
311  hufftbl = SYMTABLE(tbl); \
312  if ((i = hufftbl[PEEK_BITS(TABLEBITS(tbl))]) >= MAXSYMBOLS(tbl)) { \
313  j = 1 << (ULONG_BITS - TABLEBITS(tbl)); \
314  do { \
315  j >>= 1; i <<= 1; i |= (bitbuf & j) ? 1 : 0; \
316  if (!j) { return DECR_ILLEGALDATA; } \
317  } while ((i = hufftbl[i]) >= MAXSYMBOLS(tbl)); \
318  } \
319  j = LENTABLE(tbl)[(var) = i]; \
320  REMOVE_BITS(j); \
321 } while (0)
322 
323 
324 /* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols
325  * first to last in the given table. The code lengths are stored in their
326  * own special LZX way.
327  */
328 #define READ_LENGTHS(tbl,first,last) do { \
329  lb.bb = bitbuf; lb.bl = bitsleft; lb.ip = inpos; \
330  if (lzx_read_lens(pState, LENTABLE(tbl),(first),(last),&lb)) { \
331  return DECR_ILLEGALDATA; \
332  } \
333  bitbuf = lb.bb; bitsleft = lb.bl; inpos = lb.ip; \
334 } while (0)
335 
336 
337 /* make_decode_table(nsyms, nbits, length[], table[])
338  *
339  * This function was coded by David Tritscher. It builds a fast huffman
340  * decoding table out of just a canonical huffman code lengths table.
341  *
342  * nsyms = total number of symbols in this huffman tree.
343  * nbits = any symbols with a code length of nbits or less can be decoded
344  * in one lookup of the table.
345  * length = A table to get code lengths from [0 to syms-1]
346  * table = The table to fill up with decoded symbols and pointers.
347  *
348  * Returns 0 for OK or 1 for error
349  */
350 
351 static int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table) {
352  register UWORD sym;
353  register ULONG leaf;
354  register UBYTE bit_num = 1;
355  ULONG fill;
356  ULONG pos = 0; /* the current position in the decode table */
357  ULONG table_mask = 1 << nbits;
358  ULONG bit_mask = table_mask >> 1; /* don't do 0 length codes */
359  ULONG next_symbol = bit_mask; /* base of allocation for long codes */
360 
361  /* fill entries for codes short enough for a direct mapping */
362  while (bit_num <= nbits) {
363  for (sym = 0; sym < nsyms; sym++) {
364  if (length[sym] == bit_num) {
365  leaf = pos;
366 
367  if((pos += bit_mask) > table_mask) return 1; /* table overrun */
368 
369  /* fill all possible lookups of this symbol with the symbol itself */
370  fill = bit_mask;
371  while (fill-- > 0) table[leaf++] = sym;
372  }
373  }
374  bit_mask >>= 1;
375  bit_num++;
376  }
377 
378  /* if there are any codes longer than nbits */
379  if (pos != table_mask) {
380  /* clear the remainder of the table */
381  for (sym = pos; sym < table_mask; sym++) table[sym] = 0;
382 
383  /* give ourselves room for codes to grow by up to 16 more bits */
384  pos <<= 16;
385  table_mask <<= 16;
386  bit_mask = 1 << 15;
387 
388  while (bit_num <= 16) {
389  for (sym = 0; sym < nsyms; sym++) {
390  if (length[sym] == bit_num) {
391  leaf = pos >> 16;
392  for (fill = 0; fill < bit_num - nbits; fill++) {
393  /* if this path hasn't been taken yet, 'allocate' two entries */
394  if (table[leaf] == 0) {
395  table[(next_symbol << 1)] = 0;
396  table[(next_symbol << 1) + 1] = 0;
397  table[leaf] = next_symbol++;
398  }
399  /* follow the path and select either left or right for next bit */
400  leaf = table[leaf] << 1;
401  if ((pos >> (15-fill)) & 1) leaf++;
402  }
403  table[leaf] = sym;
404 
405  if ((pos += bit_mask) > table_mask) return 1; /* table overflow */
406  }
407  }
408  bit_mask >>= 1;
409  bit_num++;
410  }
411  }
412 
413  /* full table? */
414  if (pos == table_mask) return 0;
415 
416  /* either erroneous table, or all elements are 0 - let's find out. */
417  for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
418  return 0;
419 }
420 
421 struct lzx_bits {
423  int bl;
425 };
426 
427 static int lzx_read_lens(struct LZXstate *pState, UBYTE *lens, ULONG first, ULONG last, struct lzx_bits *lb) {
428  ULONG i,j, x,y;
429  int z;
430 
431  register ULONG bitbuf = lb->bb;
432  register int bitsleft = lb->bl;
433  UBYTE *inpos = lb->ip;
434  UWORD *hufftbl;
435 
436  for (x = 0; x < 20; x++) {
437  READ_BITS(y, 4);
438  LENTABLE(PRETREE)[x] = y;
439  }
440  BUILD_TABLE(PRETREE);
441 
442  for (x = first; x < last; ) {
443  READ_HUFFSYM(PRETREE, z);
444  if (z == 17) {
445  READ_BITS(y, 4); y += 4;
446  while (y--) lens[x++] = 0;
447  }
448  else if (z == 18) {
449  READ_BITS(y, 5); y += 20;
450  while (y--) lens[x++] = 0;
451  }
452  else if (z == 19) {
453  READ_BITS(y, 1); y += 4;
454  READ_HUFFSYM(PRETREE, z);
455  z = lens[x] - z; if (z < 0) z += 17;
456  while (y--) lens[x++] = z;
457  }
458  else {
459  z = lens[x] - z; if (z < 0) z += 17;
460  lens[x++] = z;
461  }
462  }
463 
464  lb->bb = bitbuf;
465  lb->bl = bitsleft;
466  lb->ip = inpos;
467  return 0;
468 }
469 
470 int LZXdecompress(struct LZXstate *pState, unsigned char *inpos, unsigned char *outpos, int inlen, int outlen) {
471  UBYTE *endinp = inpos + inlen;
472  UBYTE *window = pState->window;
473  UBYTE *runsrc, *rundest;
474  UWORD *hufftbl; /* used in READ_HUFFSYM macro as chosen decoding table */
475 
476  ULONG window_posn = pState->window_posn;
477  ULONG window_size = pState->window_size;
478  ULONG R0 = pState->R0;
479  ULONG R1 = pState->R1;
480  ULONG R2 = pState->R2;
481 
482  register ULONG bitbuf;
483  register int bitsleft;
484  ULONG match_offset, i,j,k; /* ijk used in READ_HUFFSYM macro */
485  struct lzx_bits lb; /* used in READ_LENGTHS macro */
486 
487  int togo = outlen, this_run, main_element, aligned_bits;
488  int match_length, length_footer, extra, verbatim_bits;
489  int copy_length;
490 
492 
493  /* read header if necessary */
494  if (!pState->header_read) {
495  i = j = 0;
496  READ_BITS(k, 1); if (k) { READ_BITS(i,16); READ_BITS(j,16); }
497  pState->intel_filesize = (i << 16) | j; /* or 0 if not encoded */
498  pState->header_read = 1;
499  }
500 
501  /* main decoding loop */
502  while (togo > 0) {
503  /* last block finished, new block expected */
504  if (pState->block_remaining == 0) {
505  if (pState->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) {
506  if (pState->block_length & 1) inpos++; /* realign bitstream to word */
508  }
509 
510  READ_BITS(pState->block_type, 3);
511  READ_BITS(i, 16);
512  READ_BITS(j, 8);
513  pState->block_remaining = pState->block_length = (i << 8) | j;
514 
515  switch (pState->block_type) {
517  for (i = 0; i < 8; i++) { READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j; }
519  /* rest of aligned header is same as verbatim */
520 
522  READ_LENGTHS(MAINTREE, 0, 256);
523  READ_LENGTHS(MAINTREE, 256, pState->main_elements);
524  BUILD_TABLE(MAINTREE);
525  if (LENTABLE(MAINTREE)[0xE8] != 0) pState->intel_started = 1;
526 
529  break;
530 
532  pState->intel_started = 1; /* because we can't assume otherwise */
533  ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */
534  if (bitsleft > 16) inpos -= 2; /* and align the bitstream! */
535  R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
536  R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
537  R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
538  break;
539 
540  default:
541  return DECR_ILLEGALDATA;
542  }
543  }
544 
545  /* buffer exhaustion check */
546  if (inpos > endinp) {
547  /* it's possible to have a file where the next run is less than
548  * 16 bits in size. In this case, the READ_HUFFSYM() macro used
549  * in building the tables will exhaust the buffer, so we should
550  * allow for this, but not allow those accidentally read bits to
551  * be used (so we check that there are at least 16 bits
552  * remaining - in this boundary case they aren't really part of
553  * the compressed data)
554  */
555  if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA;
556  }
557 
558  while ((this_run = pState->block_remaining) > 0 && togo > 0) {
559  if (this_run > togo) this_run = togo;
560  togo -= this_run;
561  pState->block_remaining -= this_run;
562 
563  /* apply 2^x-1 mask */
564  window_posn &= window_size - 1;
565  /* runs can't straddle the window wraparound */
566  if ((window_posn + this_run) > window_size)
567  return DECR_DATAFORMAT;
568 
569  switch (pState->block_type) {
570 
572  while (this_run > 0) {
573  READ_HUFFSYM(MAINTREE, main_element);
574 
575  if (main_element < LZX_NUM_CHARS) {
576  /* literal: 0 to LZX_NUM_CHARS-1 */
577  window[window_posn++] = main_element;
578  this_run--;
579  }
580  else {
581  /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
582  main_element -= LZX_NUM_CHARS;
583 
584  match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
585  if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
586  READ_HUFFSYM(LENGTH, length_footer);
587  match_length += length_footer;
588  }
589  match_length += LZX_MIN_MATCH;
590 
591  match_offset = main_element >> 3;
592 
593  if (match_offset > 2) {
594  /* not repeated offset */
595  if (match_offset != 3) {
596  extra = extra_bits[match_offset];
597  READ_BITS(verbatim_bits, extra);
598  match_offset = position_base[match_offset] - 2 + verbatim_bits;
599  }
600  else {
601  match_offset = 1;
602  }
603 
604  /* update repeated offset LRU queue */
605  R2 = R1; R1 = R0; R0 = match_offset;
606  }
607  else if (match_offset == 0) {
608  match_offset = R0;
609  }
610  else if (match_offset == 1) {
611  match_offset = R1;
612  R1 = R0; R0 = match_offset;
613  }
614  else /* match_offset == 2 */ {
615  match_offset = R2;
616  R2 = R0; R0 = match_offset;
617  }
618 
619  rundest = window + window_posn;
620  this_run -= match_length;
621 
622  /* copy any wrapped around source data */
623  if (window_posn >= match_offset) {
624  /* no wrap */
625  runsrc = rundest - match_offset;
626  } else {
627  runsrc = rundest + (window_size - match_offset);
628  copy_length = match_offset - window_posn;
629  if (copy_length < match_length) {
630  match_length -= copy_length;
631  window_posn += copy_length;
632  while (copy_length-- > 0) *rundest++ = *runsrc++;
633  runsrc = window;
634  }
635  }
636  window_posn += match_length;
637 
638  /* copy match data - no worries about destination wraps */
639  while (match_length-- > 0) *rundest++ = *runsrc++;
640 
641  }
642  }
643  break;
644 
646  while (this_run > 0) {
647  READ_HUFFSYM(MAINTREE, main_element);
648 
649  if (main_element < LZX_NUM_CHARS) {
650  /* literal: 0 to LZX_NUM_CHARS-1 */
651  window[window_posn++] = main_element;
652  this_run--;
653  }
654  else {
655  /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
656  main_element -= LZX_NUM_CHARS;
657 
658  match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
659  if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
660  READ_HUFFSYM(LENGTH, length_footer);
661  match_length += length_footer;
662  }
663  match_length += LZX_MIN_MATCH;
664 
665  match_offset = main_element >> 3;
666 
667  if (match_offset > 2) {
668  /* not repeated offset */
669  extra = extra_bits[match_offset];
670  match_offset = position_base[match_offset] - 2;
671  if (extra > 3) {
672  /* verbatim and aligned bits */
673  extra -= 3;
674  READ_BITS(verbatim_bits, extra);
675  match_offset += (verbatim_bits << 3);
676  READ_HUFFSYM(ALIGNED, aligned_bits);
677  match_offset += aligned_bits;
678  }
679  else if (extra == 3) {
680  /* aligned bits only */
681  READ_HUFFSYM(ALIGNED, aligned_bits);
682  match_offset += aligned_bits;
683  }
684  else if (extra > 0) { /* extra==1, extra==2 */
685  /* verbatim bits only */
686  READ_BITS(verbatim_bits, extra);
687  match_offset += verbatim_bits;
688  }
689  else /* extra == 0 */ {
690  /* ??? */
691  match_offset = 1;
692  }
693 
694  /* update repeated offset LRU queue */
695  R2 = R1; R1 = R0; R0 = match_offset;
696  }
697  else if (match_offset == 0) {
698  match_offset = R0;
699  }
700  else if (match_offset == 1) {
701  match_offset = R1;
702  R1 = R0; R0 = match_offset;
703  }
704  else /* match_offset == 2 */ {
705  match_offset = R2;
706  R2 = R0; R0 = match_offset;
707  }
708 
709  rundest = window + window_posn;
710  this_run -= match_length;
711 
712  /* copy any wrapped around source data */
713  if (window_posn >= match_offset) {
714  /* no wrap */
715  runsrc = rundest - match_offset;
716  } else {
717  runsrc = rundest + (window_size - match_offset);
718  copy_length = match_offset - window_posn;
719  if (copy_length < match_length) {
720  match_length -= copy_length;
721  window_posn += copy_length;
722  while (copy_length-- > 0) *rundest++ = *runsrc++;
723  runsrc = window;
724  }
725  }
726  window_posn += match_length;
727 
728  /* copy match data - no worries about destination wraps */
729  while (match_length-- > 0) *rundest++ = *runsrc++;
730 
731  }
732  }
733  break;
734 
736  if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA;
737  memcpy(window + window_posn, inpos, (size_t) this_run);
738  inpos += this_run; window_posn += this_run;
739  break;
740 
741  default:
742  return DECR_ILLEGALDATA; /* might as well */
743  }
744 
745  }
746  }
747 
748  if (togo != 0) return DECR_ILLEGALDATA;
749  memcpy(outpos, window + ((!window_posn) ? window_size : window_posn) - outlen, (size_t) outlen);
750 
751  pState->window_posn = window_posn;
752  pState->R0 = R0;
753  pState->R1 = R1;
754  pState->R2 = R2;
755 
756  /* intel E8 decoding */
757  if ((pState->frames_read++ < 32768) && pState->intel_filesize != 0) {
758  if (outlen <= 6 || !pState->intel_started) {
759  pState->intel_curpos += outlen;
760  }
761  else {
762  UBYTE *data = outpos;
763  UBYTE *dataend = data + outlen - 10;
764  LONG curpos = pState->intel_curpos;
765  LONG filesize = pState->intel_filesize;
766  LONG abs_off, rel_off;
767 
768  pState->intel_curpos = curpos + outlen;
769 
770  while (data < dataend) {
771  if (*data++ != 0xE8) { curpos++; continue; }
772  abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
773  if ((abs_off >= -curpos) && (abs_off < filesize)) {
774  rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
775  data[0] = (UBYTE) rel_off;
776  data[1] = (UBYTE) (rel_off >> 8);
777  data[2] = (UBYTE) (rel_off >> 16);
778  data[3] = (UBYTE) (rel_off >> 24);
779  }
780  data += 4;
781  curpos += 5;
782  }
783  }
784  }
785  return DECR_OK;
786 }
787 
788 #ifdef LZX_CHM_TESTDRIVER
789 int main(int c, char **v)
790 {
791  FILE *fin, *fout;
792  struct LZXstate state;
793  UBYTE ibuf[16384];
794  UBYTE obuf[32768];
795  int ilen, olen;
796  int status;
797  int i;
798  int count=0;
799  int w = atoi(v[1]);
800  LZXinit(&state, w);
801  fout = fopen(v[2], "wb");
802  for (i=3; i<c; i++)
803  {
804  fin = fopen(v[i], "rb");
805  ilen = fread(ibuf, 1, 16384, fin);
806  status = LZXdecompress(&state, ibuf, obuf, ilen, 32768);
807  switch (status)
808  {
809  case DECR_OK:
810  printf("ok\n");
811  fwrite(obuf, 1, 32768, fout);
812  break;
813  case DECR_DATAFORMAT:
814  printf("bad format\n");
815  break;
816  case DECR_ILLEGALDATA:
817  printf("illegal data\n");
818  break;
819  case DECR_NOMEMORY:
820  printf("no memory\n");
821  break;
822  default:
823  break;
824  }
825  fclose(fin);
826  if (++count == 2)
827  {
828  count = 0;
829  LZXreset(&state);
830  }
831  }
832  fclose(fout);
833 }
834 #endif
#define LZX_NUM_SECONDARY_LENGTHS
Definition: lzx.c:62
#define READ_BITS(v, n)
Definition: lzx.c:281
#define LZX_BLOCKTYPE_ALIGNED
Definition: lzx.c:57
#define ALIGNED(a)
Definition: optimize.h:190
ULONG window_size
Definition: lzx.c:83
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
UWORD block_type
Definition: lzx.c:89
#define LZX_BLOCKTYPE_UNCOMPRESSED
Definition: lzx.c:58
UBYTE * ip
Definition: lzx.c:424
POINT last
Definition: font.c:46
LONG intel_filesize
Definition: lzx.c:93
int main(int argc, char *argv[])
Definition: atactl.cpp:1685
#define DECR_ILLEGALDATA
Definition: mszip.h:81
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define BUILD_TABLE(tbl)
Definition: lzx.c:300
const GLint * first
Definition: glext.h:5794
void LZXteardown(struct LZXstate *pState)
Definition: lzx.c:218
#define LZX_LENTABLE_SAFETY
Definition: lzx.c:74
#define R2(v, w, x, y, z, i)
Definition: sha1.c:37
ULONG R2
Definition: lzx.c:86
cab_ULONG R0
Definition: cabinet.h:217
static int lzx_read_lens(struct LZXstate *pState, UBYTE *lens, ULONG first, ULONG last, struct lzx_bits *lb)
Definition: lzx.c:427
_Check_return_opt_ _CRTIMP size_t __cdecl fwrite(_In_reads_bytes_(_Size *_Count) const void *_Str, _In_ size_t _Size, _In_ size_t _Count, _Inout_ FILE *_File)
ULONG bb
Definition: lzx.c:422
ULONG frames_read
Definition: lzx.c:92
cab_UBYTE * window
Definition: cabinet.h:213
INT INT y
Definition: msvc.h:62
#define LZX_MAINTREE_MAXSYMBOLS
Definition: lzx.c:67
UWORD main_elements
Definition: lzx.c:87
#define DECR_OK
Definition: mszip.h:79
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
_Check_return_opt_ _CRTIMP size_t __cdecl fread(_Out_writes_bytes_(_ElementSize *_Count) void *_DstBuf, _In_ size_t _ElementSize, _In_ size_t _Count, _Inout_ FILE *_File)
LONG intel_curpos
Definition: lzx.c:94
long LONG
Definition: pedump.c:60
#define READ_LENGTHS(tbl, first, last)
Definition: lzx.c:328
int header_read
Definition: cabinet.h:219
GLdouble GLdouble z
Definition: glext.h:5874
smooth NULL
Definition: ftsmooth.c:416
Definition: inflate.h:48
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define LENTABLE(tbl)
Definition: lzx.c:293
#define R1(v, w, x, y, z, i)
Definition: sha1.c:36
cab_UBYTE * ip
Definition: cabinet.h:237
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
Definition: id3.c:18
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
ULONG block_length
Definition: lzx.c:90
const GLubyte * c
Definition: glext.h:8905
#define for
Definition: utility.h:88
int LZXreset(struct LZXstate *pState)
Definition: lzx.c:227
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
static int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table)
Definition: lzx.c:351
unsigned char UBYTE
Definition: lzx.c:48
#define LZX_NUM_PRIMARY_LENGTHS
Definition: lzx.c:61
#define LZX_BLOCKTYPE_VERBATIM
Definition: lzx.c:56
#define LZX_MIN_MATCH
Definition: lzx.c:52
static int state
Definition: maze.c:121
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
int intel_started
Definition: cabinet.h:226
_Check_return_opt_ _CRTIMP int __cdecl fclose(_Inout_ FILE *_File)
_Check_return_ _CRTIMP FILE *__cdecl fopen(_In_z_ const char *_Filename, _In_z_ const char *_Mode)
static IHTMLWindow2 * window
Definition: events.c:77
static const UBYTE extra_bits[51]
Definition: lzx.c:158
LZX_DECLARE_TABLE(PRETREE)
static const ULONG position_base[51]
Definition: lzx.c:165
#define INIT_BITSTREAM
Definition: lzx.c:270
#define DECR_NOMEMORY
Definition: mszip.h:82
#define R0(v, w, x, y, z, i)
Definition: sha1.c:35
ULONG window_posn
Definition: lzx.c:85
const GLdouble * v
Definition: gl.h:2040
ULONG actual_size
Definition: lzx.c:84
INT x
Definition: msvc.h:62
static char obuf[100]
Definition: i386-dis.c:1266
struct LZXstate * LZXinit(int window)
Definition: lzx.c:172
#define LZX_NUM_CHARS
Definition: lzx.c:54
_Check_return_ int __cdecl atoi(_In_z_ const char *_Str)
cab_ULONG R1
Definition: cabinet.h:217
#define c
Definition: ke_i.h:80
unsigned int ULONG
Definition: retypes.h:1
#define DECR_DATAFORMAT
Definition: mszip.h:80
int LZXdecompress(struct LZXstate *pState, unsigned char *inpos, unsigned char *outpos, int inlen, int outlen)
Definition: lzx.c:470
unsigned short UWORD
Definition: lzx.c:49
#define READ_HUFFSYM(tbl, var)
Definition: lzx.c:309
#define ENSURE_BITS(n)
Definition: lzx.c:272
#define LZX_LENGTH_MAXSYMBOLS
Definition: lzx.c:69
int bl
Definition: cabinet.h:236
UBYTE * window
Definition: lzx.c:82
static SERVICE_STATUS status
Definition: service.c:31
int k
Definition: mpi.c:3369
#define HeapFree(x, y, z)
Definition: compat.h:394
ULONG block_remaining
Definition: lzx.c:91
#define LZX_BLOCKTYPE_INVALID
Definition: lzx.c:55
#define printf
Definition: config.h:203
Definition: ps.c:97