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

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