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 wndsize) 173 { 174 struct LZXstate *pState=NULL; 175 int i, posn_slots; 176 177 /* allocate state and associated window */ 178 pState = HeapAlloc(GetProcessHeap(), 0, sizeof(struct LZXstate)); 179 if (!(pState->window = HeapAlloc(GetProcessHeap(), 0, wndsize))) 180 { 181 HeapFree(GetProcessHeap(), 0, pState); 182 return NULL; 183 } 184 pState->actual_size = wndsize; 185 pState->window_size = wndsize; 186 187 /* calculate required position slots */ 188 posn_slots = i = 0; 189 while (i < wndsize) i += 1 << extra_bits[posn_slots++]; 190 191 /* initialize other state */ 192 pState->R0 = pState->R1 = pState->R2 = 1; 193 pState->main_elements = LZX_NUM_CHARS + (posn_slots << 3); 194 pState->header_read = 0; 195 pState->frames_read = 0; 196 pState->block_remaining = 0; 197 pState->block_type = LZX_BLOCKTYPE_INVALID; 198 pState->intel_curpos = 0; 199 pState->intel_started = 0; 200 pState->window_posn = 0; 201 202 /* initialise tables to 0 (because deltas will be applied to them) */ 203 for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) pState->MAINTREE_len[i] = 0; 204 for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) pState->LENGTH_len[i] = 0; 205 206 return pState; 207 } 208 209 void LZXteardown(struct LZXstate *pState) 210 { 211 if (pState) 212 { 213 HeapFree(GetProcessHeap(), 0, pState->window); 214 HeapFree(GetProcessHeap(), 0, 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, 1 << 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 826