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