git.oblomov.eu Git - wine/blob - dlls/itss/lzx.c

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