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