ReactOS  0.4.14-dev-554-g2f8d847
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 wndsize)
173 {
174  struct LZXstate *pState=NULL;
175  int i, posn_slots;
176 
177  /* allocate state and associated window */
178  pState = HeapAlloc(GetProcessHeap(), 0, sizeof(struct LZXstate));
179  if (!(pState->window = HeapAlloc(GetProcessHeap(), 0, wndsize)))
180  {
181  HeapFree(GetProcessHeap(), 0, pState);
182  return NULL;
183  }
184  pState->actual_size = wndsize;
185  pState->window_size = wndsize;
186 
187  /* calculate required position slots */
188  posn_slots = i = 0;
189  while (i < wndsize) i += 1 << extra_bits[posn_slots++];
190 
191  /* initialize other state */
192  pState->R0 = pState->R1 = pState->R2 = 1;
193  pState->main_elements = LZX_NUM_CHARS + (posn_slots << 3);
194  pState->header_read = 0;
195  pState->frames_read = 0;
196  pState->block_remaining = 0;
198  pState->intel_curpos = 0;
199  pState->intel_started = 0;
200  pState->window_posn = 0;
201 
202  /* initialise tables to 0 (because deltas will be applied to them) */
203  for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) pState->MAINTREE_len[i] = 0;
204  for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) pState->LENGTH_len[i] = 0;
205 
206  return pState;
207 }
208 
209 void LZXteardown(struct LZXstate *pState)
210 {
211  if (pState)
212  {
213  HeapFree(GetProcessHeap(), 0, pState->window);
214  HeapFree(GetProcessHeap(), 0, pState);
215  }
216 }
217 
218 int LZXreset(struct LZXstate *pState)
219 {
220  int i;
221 
222  pState->R0 = pState->R1 = pState->R2 = 1;
223  pState->header_read = 0;
224  pState->frames_read = 0;
225  pState->block_remaining = 0;
227  pState->intel_curpos = 0;
228  pState->intel_started = 0;
229  pState->window_posn = 0;
230 
231  for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS + LZX_LENTABLE_SAFETY; i++) pState->MAINTREE_len[i] = 0;
232  for (i = 0; i < LZX_LENGTH_MAXSYMBOLS + LZX_LENTABLE_SAFETY; i++) pState->LENGTH_len[i] = 0;
233 
234  return DECR_OK;
235 }
236 
237 
238 /* Bitstream reading macros:
239  *
240  * INIT_BITSTREAM should be used first to set up the system
241  * READ_BITS(var,n) takes N bits from the buffer and puts them in var
242  *
243  * ENSURE_BITS(n) ensures there are at least N bits in the bit buffer
244  * PEEK_BITS(n) extracts (without removing) N bits from the bit buffer
245  * REMOVE_BITS(n) removes N bits from the bit buffer
246  *
247  * These bit access routines work by using the area beyond the MSB and the
248  * LSB as a free source of zeroes. This avoids having to mask any bits.
249  * So we have to know the bit width of the bitbuffer variable. This is
250  * sizeof(ULONG) * 8, also defined as ULONG_BITS
251  */
252 
253 /* number of bits in ULONG. Note: This must be at multiple of 16, and at
254  * least 32 for the bitbuffer code to work (ie, it must be able to ensure
255  * up to 17 bits - that's adding 16 bits when there's one bit left, or
256  * adding 32 bits when there are no bits left. The code should work fine
257  * for machines where ULONG >= 32 bits.
258  */
259 #define ULONG_BITS (sizeof(ULONG)<<3)
260 
261 #define INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0)
262 
263 #define ENSURE_BITS(n) \
264  while (bitsleft < (n)) { \
265  bitbuf |= ((inpos[1]<<8)|inpos[0]) << (ULONG_BITS-16 - bitsleft); \
266  bitsleft += 16; inpos+=2; \
267  }
268 
269 #define PEEK_BITS(n) (bitbuf >> (ULONG_BITS - (n)))
270 #define REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n)))
271 
272 #define READ_BITS(v,n) do { \
273  ENSURE_BITS(n); \
274  (v) = PEEK_BITS(n); \
275  REMOVE_BITS(n); \
276 } while (0)
277 
278 
279 /* Huffman macros */
280 
281 #define TABLEBITS(tbl) (LZX_##tbl##_TABLEBITS)
282 #define MAXSYMBOLS(tbl) (LZX_##tbl##_MAXSYMBOLS)
283 #define SYMTABLE(tbl) (pState->tbl##_table)
284 #define LENTABLE(tbl) (pState->tbl##_len)
285 
286 /* BUILD_TABLE(tablename) builds a huffman lookup table from code lengths.
287  * In reality, it just calls make_decode_table() with the appropriate
288  * values - they're all fixed by some #defines anyway, so there's no point
289  * writing each call out in full by hand.
290  */
291 #define BUILD_TABLE(tbl) \
292  if (make_decode_table( \
293  MAXSYMBOLS(tbl), TABLEBITS(tbl), LENTABLE(tbl), SYMTABLE(tbl) \
294  )) { return DECR_ILLEGALDATA; }
295 
296 
297 /* READ_HUFFSYM(tablename, var) decodes one huffman symbol from the
298  * bitstream using the stated table and puts it in var.
299  */
300 #define READ_HUFFSYM(tbl,var) do { \
301  ENSURE_BITS(16); \
302  hufftbl = SYMTABLE(tbl); \
303  if ((i = hufftbl[PEEK_BITS(TABLEBITS(tbl))]) >= MAXSYMBOLS(tbl)) { \
304  j = 1 << (ULONG_BITS - TABLEBITS(tbl)); \
305  do { \
306  j >>= 1; i <<= 1; i |= (bitbuf & j) ? 1 : 0; \
307  if (!j) { return DECR_ILLEGALDATA; } \
308  } while ((i = hufftbl[i]) >= MAXSYMBOLS(tbl)); \
309  } \
310  j = LENTABLE(tbl)[(var) = i]; \
311  REMOVE_BITS(j); \
312 } while (0)
313 
314 
315 /* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols
316  * first to last in the given table. The code lengths are stored in their
317  * own special LZX way.
318  */
319 #define READ_LENGTHS(tbl,first,last) do { \
320  lb.bb = bitbuf; lb.bl = bitsleft; lb.ip = inpos; \
321  if (lzx_read_lens(pState, LENTABLE(tbl),(first),(last),&lb)) { \
322  return DECR_ILLEGALDATA; \
323  } \
324  bitbuf = lb.bb; bitsleft = lb.bl; inpos = lb.ip; \
325 } while (0)
326 
327 
328 /* make_decode_table(nsyms, nbits, length[], table[])
329  *
330  * This function was coded by David Tritscher. It builds a fast huffman
331  * decoding table out of just a canonical huffman code lengths table.
332  *
333  * nsyms = total number of symbols in this huffman tree.
334  * nbits = any symbols with a code length of nbits or less can be decoded
335  * in one lookup of the table.
336  * length = A table to get code lengths from [0 to syms-1]
337  * table = The table to fill up with decoded symbols and pointers.
338  *
339  * Returns 0 for OK or 1 for error
340  */
341 
342 static int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table) {
343  register UWORD sym;
344  register ULONG leaf;
345  register UBYTE bit_num = 1;
346  ULONG fill;
347  ULONG pos = 0; /* the current position in the decode table */
348  ULONG table_mask = 1 << nbits;
349  ULONG bit_mask = table_mask >> 1; /* don't do 0 length codes */
350  ULONG next_symbol = bit_mask; /* base of allocation for long codes */
351 
352  /* fill entries for codes short enough for a direct mapping */
353  while (bit_num <= nbits) {
354  for (sym = 0; sym < nsyms; sym++) {
355  if (length[sym] == bit_num) {
356  leaf = pos;
357 
358  if((pos += bit_mask) > table_mask) return 1; /* table overrun */
359 
360  /* fill all possible lookups of this symbol with the symbol itself */
361  fill = bit_mask;
362  while (fill-- > 0) table[leaf++] = sym;
363  }
364  }
365  bit_mask >>= 1;
366  bit_num++;
367  }
368 
369  /* if there are any codes longer than nbits */
370  if (pos != table_mask) {
371  /* clear the remainder of the table */
372  for (sym = pos; sym < table_mask; sym++) table[sym] = 0;
373 
374  /* give ourselves room for codes to grow by up to 16 more bits */
375  pos <<= 16;
376  table_mask <<= 16;
377  bit_mask = 1 << 15;
378 
379  while (bit_num <= 16) {
380  for (sym = 0; sym < nsyms; sym++) {
381  if (length[sym] == bit_num) {
382  leaf = pos >> 16;
383  for (fill = 0; fill < bit_num - nbits; fill++) {
384  /* if this path hasn't been taken yet, 'allocate' two entries */
385  if (table[leaf] == 0) {
386  table[(next_symbol << 1)] = 0;
387  table[(next_symbol << 1) + 1] = 0;
388  table[leaf] = next_symbol++;
389  }
390  /* follow the path and select either left or right for next bit */
391  leaf = table[leaf] << 1;
392  if ((pos >> (15-fill)) & 1) leaf++;
393  }
394  table[leaf] = sym;
395 
396  if ((pos += bit_mask) > table_mask) return 1; /* table overflow */
397  }
398  }
399  bit_mask >>= 1;
400  bit_num++;
401  }
402  }
403 
404  /* full table? */
405  if (pos == table_mask) return 0;
406 
407  /* either erroneous table, or all elements are 0 - let's find out. */
408  for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
409  return 0;
410 }
411 
412 struct lzx_bits {
414  int bl;
416 };
417 
418 static int lzx_read_lens(struct LZXstate *pState, UBYTE *lens, ULONG first, ULONG last, struct lzx_bits *lb) {
419  ULONG i,j, x,y;
420  int z;
421 
422  register ULONG bitbuf = lb->bb;
423  register int bitsleft = lb->bl;
424  UBYTE *inpos = lb->ip;
425  UWORD *hufftbl;
426 
427  for (x = 0; x < 20; x++) {
428  READ_BITS(y, 4);
429  LENTABLE(PRETREE)[x] = y;
430  }
431  BUILD_TABLE(PRETREE);
432 
433  for (x = first; x < last; ) {
434  READ_HUFFSYM(PRETREE, z);
435  if (z == 17) {
436  READ_BITS(y, 4); y += 4;
437  while (y--) lens[x++] = 0;
438  }
439  else if (z == 18) {
440  READ_BITS(y, 5); y += 20;
441  while (y--) lens[x++] = 0;
442  }
443  else if (z == 19) {
444  READ_BITS(y, 1); y += 4;
445  READ_HUFFSYM(PRETREE, z);
446  z = lens[x] - z; if (z < 0) z += 17;
447  while (y--) lens[x++] = z;
448  }
449  else {
450  z = lens[x] - z; if (z < 0) z += 17;
451  lens[x++] = z;
452  }
453  }
454 
455  lb->bb = bitbuf;
456  lb->bl = bitsleft;
457  lb->ip = inpos;
458  return 0;
459 }
460 
461 int LZXdecompress(struct LZXstate *pState, unsigned char *inpos, unsigned char *outpos, int inlen, int outlen) {
462  UBYTE *endinp = inpos + inlen;
463  UBYTE *window = pState->window;
464  UBYTE *runsrc, *rundest;
465  UWORD *hufftbl; /* used in READ_HUFFSYM macro as chosen decoding table */
466 
467  ULONG window_posn = pState->window_posn;
468  ULONG window_size = pState->window_size;
469  ULONG R0 = pState->R0;
470  ULONG R1 = pState->R1;
471  ULONG R2 = pState->R2;
472 
473  register ULONG bitbuf;
474  register int bitsleft;
475  ULONG match_offset, i,j,k; /* ijk used in READ_HUFFSYM macro */
476  struct lzx_bits lb; /* used in READ_LENGTHS macro */
477 
478  int togo = outlen, this_run, main_element, aligned_bits;
479  int match_length, length_footer, extra, verbatim_bits;
480  int copy_length;
481 
483 
484  /* read header if necessary */
485  if (!pState->header_read) {
486  i = j = 0;
487  READ_BITS(k, 1); if (k) { READ_BITS(i,16); READ_BITS(j,16); }
488  pState->intel_filesize = (i << 16) | j; /* or 0 if not encoded */
489  pState->header_read = 1;
490  }
491 
492  /* main decoding loop */
493  while (togo > 0) {
494  /* last block finished, new block expected */
495  if (pState->block_remaining == 0) {
496  if (pState->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) {
497  if (pState->block_length & 1) inpos++; /* realign bitstream to word */
499  }
500 
501  READ_BITS(pState->block_type, 3);
502  READ_BITS(i, 16);
503  READ_BITS(j, 8);
504  pState->block_remaining = pState->block_length = (i << 8) | j;
505 
506  switch (pState->block_type) {
508  for (i = 0; i < 8; i++) { READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j; }
510  /* rest of aligned header is same as verbatim */
511 
513  READ_LENGTHS(MAINTREE, 0, 256);
514  READ_LENGTHS(MAINTREE, 256, pState->main_elements);
515  BUILD_TABLE(MAINTREE);
516  if (LENTABLE(MAINTREE)[0xE8] != 0) pState->intel_started = 1;
517 
520  break;
521 
523  pState->intel_started = 1; /* because we can't assume otherwise */
524  ENSURE_BITS(16); /* get up to 16 pad bits into the buffer */
525  if (bitsleft > 16) inpos -= 2; /* and align the bitstream! */
526  R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
527  R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
528  R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
529  break;
530 
531  default:
532  return DECR_ILLEGALDATA;
533  }
534  }
535 
536  /* buffer exhaustion check */
537  if (inpos > endinp) {
538  /* it's possible to have a file where the next run is less than
539  * 16 bits in size. In this case, the READ_HUFFSYM() macro used
540  * in building the tables will exhaust the buffer, so we should
541  * allow for this, but not allow those accidentally read bits to
542  * be used (so we check that there are at least 16 bits
543  * remaining - in this boundary case they aren't really part of
544  * the compressed data)
545  */
546  if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA;
547  }
548 
549  while ((this_run = pState->block_remaining) > 0 && togo > 0) {
550  if (this_run > togo) this_run = togo;
551  togo -= this_run;
552  pState->block_remaining -= this_run;
553 
554  /* apply 2^x-1 mask */
555  window_posn &= window_size - 1;
556  /* runs can't straddle the window wraparound */
557  if ((window_posn + this_run) > window_size)
558  return DECR_DATAFORMAT;
559 
560  switch (pState->block_type) {
561 
563  while (this_run > 0) {
564  READ_HUFFSYM(MAINTREE, main_element);
565 
566  if (main_element < LZX_NUM_CHARS) {
567  /* literal: 0 to LZX_NUM_CHARS-1 */
568  window[window_posn++] = main_element;
569  this_run--;
570  }
571  else {
572  /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
573  main_element -= LZX_NUM_CHARS;
574 
575  match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
576  if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
577  READ_HUFFSYM(LENGTH, length_footer);
578  match_length += length_footer;
579  }
580  match_length += LZX_MIN_MATCH;
581 
582  match_offset = main_element >> 3;
583 
584  if (match_offset > 2) {
585  /* not repeated offset */
586  if (match_offset != 3) {
587  extra = extra_bits[match_offset];
588  READ_BITS(verbatim_bits, extra);
589  match_offset = position_base[match_offset] - 2 + verbatim_bits;
590  }
591  else {
592  match_offset = 1;
593  }
594 
595  /* update repeated offset LRU queue */
596  R2 = R1; R1 = R0; R0 = match_offset;
597  }
598  else if (match_offset == 0) {
599  match_offset = R0;
600  }
601  else if (match_offset == 1) {
602  match_offset = R1;
603  R1 = R0; R0 = match_offset;
604  }
605  else /* match_offset == 2 */ {
606  match_offset = R2;
607  R2 = R0; R0 = match_offset;
608  }
609 
610  rundest = window + window_posn;
611  this_run -= match_length;
612 
613  /* copy any wrapped around source data */
614  if (window_posn >= match_offset) {
615  /* no wrap */
616  runsrc = rundest - match_offset;
617  } else {
618  runsrc = rundest + (window_size - match_offset);
619  copy_length = match_offset - window_posn;
620  if (copy_length < match_length) {
621  match_length -= copy_length;
622  window_posn += copy_length;
623  while (copy_length-- > 0) *rundest++ = *runsrc++;
624  runsrc = window;
625  }
626  }
627  window_posn += match_length;
628 
629  /* copy match data - no worries about destination wraps */
630  while (match_length-- > 0) *rundest++ = *runsrc++;
631 
632  }
633  }
634  break;
635 
637  while (this_run > 0) {
638  READ_HUFFSYM(MAINTREE, main_element);
639 
640  if (main_element < LZX_NUM_CHARS) {
641  /* literal: 0 to LZX_NUM_CHARS-1 */
642  window[window_posn++] = main_element;
643  this_run--;
644  }
645  else {
646  /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
647  main_element -= LZX_NUM_CHARS;
648 
649  match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
650  if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
651  READ_HUFFSYM(LENGTH, length_footer);
652  match_length += length_footer;
653  }
654  match_length += LZX_MIN_MATCH;
655 
656  match_offset = main_element >> 3;
657 
658  if (match_offset > 2) {
659  /* not repeated offset */
660  extra = extra_bits[match_offset];
661  match_offset = position_base[match_offset] - 2;
662  if (extra > 3) {
663  /* verbatim and aligned bits */
664  extra -= 3;
665  READ_BITS(verbatim_bits, extra);
666  match_offset += (verbatim_bits << 3);
667  READ_HUFFSYM(ALIGNED, aligned_bits);
668  match_offset += aligned_bits;
669  }
670  else if (extra == 3) {
671  /* aligned bits only */
672  READ_HUFFSYM(ALIGNED, aligned_bits);
673  match_offset += aligned_bits;
674  }
675  else if (extra > 0) { /* extra==1, extra==2 */
676  /* verbatim bits only */
677  READ_BITS(verbatim_bits, extra);
678  match_offset += verbatim_bits;
679  }
680  else /* extra == 0 */ {
681  /* ??? */
682  match_offset = 1;
683  }
684 
685  /* update repeated offset LRU queue */
686  R2 = R1; R1 = R0; R0 = match_offset;
687  }
688  else if (match_offset == 0) {
689  match_offset = R0;
690  }
691  else if (match_offset == 1) {
692  match_offset = R1;
693  R1 = R0; R0 = match_offset;
694  }
695  else /* match_offset == 2 */ {
696  match_offset = R2;
697  R2 = R0; R0 = match_offset;
698  }
699 
700  rundest = window + window_posn;
701  this_run -= match_length;
702 
703  /* copy any wrapped around source data */
704  if (window_posn >= match_offset) {
705  /* no wrap */
706  runsrc = rundest - match_offset;
707  } else {
708  runsrc = rundest + (window_size - match_offset);
709  copy_length = match_offset - window_posn;
710  if (copy_length < match_length) {
711  match_length -= copy_length;
712  window_posn += copy_length;
713  while (copy_length-- > 0) *rundest++ = *runsrc++;
714  runsrc = window;
715  }
716  }
717  window_posn += match_length;
718 
719  /* copy match data - no worries about destination wraps */
720  while (match_length-- > 0) *rundest++ = *runsrc++;
721 
722  }
723  }
724  break;
725 
727  if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA;
728  memcpy(window + window_posn, inpos, (size_t) this_run);
729  inpos += this_run; window_posn += this_run;
730  break;
731 
732  default:
733  return DECR_ILLEGALDATA; /* might as well */
734  }
735 
736  }
737  }
738 
739  if (togo != 0) return DECR_ILLEGALDATA;
740  memcpy(outpos, window + ((!window_posn) ? window_size : window_posn) - outlen, (size_t) outlen);
741 
742  pState->window_posn = window_posn;
743  pState->R0 = R0;
744  pState->R1 = R1;
745  pState->R2 = R2;
746 
747  /* intel E8 decoding */
748  if ((pState->frames_read++ < 32768) && pState->intel_filesize != 0) {
749  if (outlen <= 6 || !pState->intel_started) {
750  pState->intel_curpos += outlen;
751  }
752  else {
753  UBYTE *data = outpos;
754  UBYTE *dataend = data + outlen - 10;
755  LONG curpos = pState->intel_curpos;
756  LONG filesize = pState->intel_filesize;
757  LONG abs_off, rel_off;
758 
759  pState->intel_curpos = curpos + outlen;
760 
761  while (data < dataend) {
762  if (*data++ != 0xE8) { curpos++; continue; }
763  abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
764  if ((abs_off >= -curpos) && (abs_off < filesize)) {
765  rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
766  data[0] = (UBYTE) rel_off;
767  data[1] = (UBYTE) (rel_off >> 8);
768  data[2] = (UBYTE) (rel_off >> 16);
769  data[3] = (UBYTE) (rel_off >> 24);
770  }
771  data += 4;
772  curpos += 5;
773  }
774  }
775  }
776  return DECR_OK;
777 }
778 
779 #ifdef LZX_CHM_TESTDRIVER
780 int main(int c, char **v)
781 {
782  FILE *fin, *fout;
783  struct LZXstate state;
784  UBYTE ibuf[16384];
785  UBYTE obuf[32768];
786  int ilen, olen;
787  int status;
788  int i;
789  int count=0;
790  int w = atoi(v[1]);
791  LZXinit(&state, 1 << w);
792  fout = fopen(v[2], "wb");
793  for (i=3; i<c; i++)
794  {
795  fin = fopen(v[i], "rb");
796  ilen = fread(ibuf, 1, 16384, fin);
797  status = LZXdecompress(&state, ibuf, obuf, ilen, 32768);
798  switch (status)
799  {
800  case DECR_OK:
801  printf("ok\n");
802  fwrite(obuf, 1, 32768, fout);
803  break;
804  case DECR_DATAFORMAT:
805  printf("bad format\n");
806  break;
807  case DECR_ILLEGALDATA:
808  printf("illegal data\n");
809  break;
810  case DECR_NOMEMORY:
811  printf("no memory\n");
812  break;
813  default:
814  break;
815  }
816  fclose(fin);
817  if (++count == 2)
818  {
819  count = 0;
820  LZXreset(&state);
821  }
822  }
823  fclose(fout);
824 }
825 #endif
#define LZX_NUM_SECONDARY_LENGTHS
Definition: lzx.c:62
#define READ_BITS(v, n)
Definition: lzx.c:272
#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
struct LZXstate * LZXinit(int wndsize)
Definition: lzx.c:172
UWORD block_type
Definition: lzx.c:89
#define LZX_BLOCKTYPE_UNCOMPRESSED
Definition: lzx.c:58
UBYTE * ip
Definition: lzx.c:415
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:291
const GLint * first
Definition: glext.h:5794
void LZXteardown(struct LZXstate *pState)
Definition: lzx.c:209
#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
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
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:418
_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:413
ULONG frames_read
Definition: lzx.c:92
cab_UBYTE * window
Definition: cabinet.h:213
#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:319
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:284
#define R1(v, w, x, y, z, i)
Definition: sha1.c:36
cab_UBYTE * ip
Definition: cabinet.h:237
#define GetProcessHeap()
Definition: compat.h:403
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:218
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:342
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:261
#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
static char obuf[100]
Definition: i386-dis.c:1266
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
#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:461
unsigned short UWORD
Definition: lzx.c:49
#define READ_HUFFSYM(tbl, var)
Definition: lzx.c:300
#define ENSURE_BITS(n)
Definition: lzx.c:263
#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:402
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