| [ Index ] |
PHP Cross Reference of Unnamed Project |
[Summary view] [Print] [Text view]
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 }
title
Description
Body
title
Description
Body
title
Description
Body
title
Body
| Generated: Tue Mar 17 22:47:18 2015 | Cross-referenced by PHPXref 0.7.1 |