[ Index ]

PHP Cross Reference of Unnamed Project

title

Body

[close]

/wimlib/wimlib-0.2/ -> lzx.c (source)

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


Generated: Tue Mar 17 22:47:18 2015 Cross-referenced by PHPXref 0.7.1