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