00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdio.h>
00022 #include <stdlib.h>
00023 #include <string.h>
00024 #include "decompress.h"
00025
00026 int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table);
00027 int lzx_read_lens(UBYTE *lens, ULONG first, ULONG last, lzx_bits *lb);
00028
00029
00030
00031
00032
00033
00034
00035
00036 #define LZX_MIN_MATCH (2)
00037 #define LZX_MAX_MATCH (257)
00038 #define LZX_NUM_CHARS (256)
00039 #define LZX_BLOCKTYPE_INVALID (0)
00040 #define LZX_BLOCKTYPE_VERBATIM (1)
00041 #define LZX_BLOCKTYPE_ALIGNED (2)
00042 #define LZX_BLOCKTYPE_UNCOMPRESSED (3)
00043 #define LZX_PRETREE_NUM_ELEMENTS (20)
00044 #define LZX_ALIGNED_NUM_ELEMENTS (8)
00045 #define LZX_NUM_PRIMARY_LENGTHS (7)
00046 #define LZX_NUM_SECONDARY_LENGTHS (249)
00047
00048
00049 #define LZX_PRETREE_MAXSYMBOLS (LZX_PRETREE_NUM_ELEMENTS)
00050 #define LZX_PRETREE_TABLEBITS (6)
00051 #define LZX_MAINTREE_MAXSYMBOLS (LZX_NUM_CHARS + 50*8)
00052 #define LZX_MAINTREE_TABLEBITS (12)
00053 #define LZX_LENGTH_MAXSYMBOLS (LZX_NUM_SECONDARY_LENGTHS+1)
00054 #define LZX_LENGTH_TABLEBITS (12)
00055 #define LZX_ALIGNED_MAXSYMBOLS (LZX_ALIGNED_NUM_ELEMENTS)
00056 #define LZX_ALIGNED_TABLEBITS (7)
00057
00058 #define LZX_LENTABLE_SAFETY (64)
00059
00060 #define LZX_DECLARE_TABLE(tbl) \
00061 UWORD tbl##_table[(1<<LZX_##tbl##_TABLEBITS) + (LZX_##tbl##_MAXSYMBOLS<<1)];\
00062 UBYTE tbl##_len [LZX_##tbl##_MAXSYMBOLS + LZX_LENTABLE_SAFETY]
00063
00064 struct LZXstate
00065 {
00066 UBYTE *window;
00067 ULONG window_size;
00068 ULONG actual_size;
00069 ULONG window_posn;
00070 ULONG R0, R1, R2;
00071 UWORD main_elements;
00072 int header_read;
00073 UWORD block_type;
00074 ULONG block_length;
00075 ULONG block_remaining;
00076 ULONG frames_read;
00077 LONG intel_filesize;
00078 LONG intel_curpos;
00079 int intel_started;
00080
00081 LZX_DECLARE_TABLE(PRETREE);
00082 LZX_DECLARE_TABLE(MAINTREE);
00083 LZX_DECLARE_TABLE(LENGTH);
00084 LZX_DECLARE_TABLE(ALIGNED);
00085 };
00086
00087
00088
00089 #define CAB(x) (decomp_state.x)
00090 #define LZX(x) (decomp_state.lzx.x)
00091 #define DECR_OK (0)
00092 #define DECR_DATAFORMAT (1)
00093 #define DECR_ILLEGALDATA (2)
00094 #define DECR_NOMEMORY (3)
00095 #define DECR_CHECKSUM (4)
00096 #define DECR_INPUT (5)
00097 #define DECR_OUTPUT (6)
00098
00099 struct
00100 {
00101 struct LZXstate lzx;
00102 } decomp_state;
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160 static ULONG position_base[51];
00161 static UBYTE extra_bits[51];
00162
00163
00164 int LZXinit(int window) {
00165 ULONG wndsize = 1 << window;
00166 int i, j, posn_slots;
00167
00168
00169
00170 if (window < 15 || window > 21) return DECR_DATAFORMAT;
00171 if (LZX(actual_size) < wndsize)
00172 {
00173 if (LZX(window)) free(LZX(window));
00174 LZX(window) = NULL;
00175 }
00176 if (!LZX(window))
00177 {
00178 if (!(LZX(window) = (UBYTE*)malloc(wndsize))) return DECR_NOMEMORY;
00179 LZX(actual_size) = wndsize;
00180 }
00181 LZX(window_size) = wndsize;
00182
00183
00184 for (i=0, j=0; i <= 50; i += 2)
00185 {
00186 extra_bits[i] = extra_bits[i+1] = j;
00187 if ((i != 0) && (j < 17)) j++;
00188 }
00189 for (i=0, j=0; i <= 50; i++)
00190 {
00191 position_base[i] = j;
00192 j += 1 << extra_bits[i];
00193 }
00194
00195
00196 if (window == 20) posn_slots = 42;
00197 else if (window == 21) posn_slots = 50;
00198 else posn_slots = window << 1;
00199
00200
00201
00202
00203 LZX(R0) = LZX(R1) = LZX(R2) = 1;
00204 LZX(main_elements) = LZX_NUM_CHARS + (posn_slots << 3);
00205 LZX(header_read) = 0;
00206 LZX(frames_read) = 0;
00207 LZX(block_remaining) = 0;
00208 LZX(block_type) = LZX_BLOCKTYPE_INVALID;
00209 LZX(intel_curpos) = 0;
00210 LZX(intel_started) = 0;
00211 LZX(window_posn) = 0;
00212
00213
00214 for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) LZX(MAINTREE_len)[i] = 0;
00215 for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) LZX(LENGTH_len)[i] = 0;
00216
00217 return DECR_OK;
00218 }
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242 #define ULONG_BITS (sizeof(ULONG)<<3)
00243
00244 #define INIT_BITSTREAM do { bitsleft = 0; bitbuf = 0; } while (0)
00245
00246 #define ENSURE_BITS(n) \
00247 while (bitsleft < (n)) { \
00248 bitbuf |= ((inpos[1]<<8)|inpos[0]) << (ULONG_BITS-16 - bitsleft); \
00249 bitsleft += 16; inpos+=2; \
00250 }
00251
00252 #define PEEK_BITS(n) (bitbuf >> (ULONG_BITS - (n)))
00253 #define REMOVE_BITS(n) ((bitbuf <<= (n)), (bitsleft -= (n)))
00254
00255 #define READ_BITS(v,n) do { \
00256 ENSURE_BITS(n); \
00257 (v) = PEEK_BITS(n); \
00258 REMOVE_BITS(n); \
00259 } while (0)
00260
00261
00262
00263
00264 #define TABLEBITS(tbl) (LZX_##tbl##_TABLEBITS)
00265 #define MAXSYMBOLS(tbl) (LZX_##tbl##_MAXSYMBOLS)
00266 #define SYMTABLE(tbl) (LZX(tbl##_table))
00267 #define LENTABLE(tbl) (LZX(tbl##_len))
00268
00269
00270
00271
00272
00273
00274 #define BUILD_TABLE(tbl) \
00275 if (make_decode_table( \
00276 MAXSYMBOLS(tbl), TABLEBITS(tbl), LENTABLE(tbl), SYMTABLE(tbl) \
00277 )) { return DECR_ILLEGALDATA; }
00278
00279
00280
00281
00282
00283 #define READ_HUFFSYM(tbl,var) do { \
00284 ENSURE_BITS(16); \
00285 hufftbl = SYMTABLE(tbl); \
00286 if ((i = hufftbl[PEEK_BITS(TABLEBITS(tbl))]) >= MAXSYMBOLS(tbl)) { \
00287 j = 1 << (ULONG_BITS - TABLEBITS(tbl)); \
00288 do { \
00289 j >>= 1; i <<= 1; i |= (bitbuf & j) ? 1 : 0; \
00290 if (!j) { return DECR_ILLEGALDATA; } \
00291 } while ((i = hufftbl[i]) >= MAXSYMBOLS(tbl)); \
00292 } \
00293 j = LENTABLE(tbl)[(var) = i]; \
00294 REMOVE_BITS(j); \
00295 } while (0)
00296
00297
00298
00299
00300
00301
00302 #define READ_LENGTHS(tbl,first,last) do { \
00303 lb.bb = bitbuf; lb.bl = bitsleft; lb.ip = inpos; \
00304 if (lzx_read_lens(LENTABLE(tbl),(first),(last),&lb)) { \
00305 return DECR_ILLEGALDATA; \
00306 } \
00307 bitbuf = lb.bb; bitsleft = lb.bl; inpos = lb.ip; \
00308 } while (0)
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325 int make_decode_table(ULONG nsyms, ULONG nbits, UBYTE *length, UWORD *table) {
00326 register UWORD sym;
00327 register ULONG leaf;
00328 register UBYTE bit_num = 1;
00329 ULONG fill;
00330 ULONG pos = 0;
00331 ULONG table_mask = 1 << nbits;
00332 ULONG bit_mask = table_mask >> 1;
00333 ULONG next_symbol = bit_mask;
00334
00335
00336 while (bit_num <= nbits)
00337 {
00338 for (sym = 0; sym < nsyms; sym++)
00339 {
00340 if (length[sym] == bit_num)
00341 {
00342 leaf = pos;
00343
00344 if ((pos += bit_mask) > table_mask) return 1;
00345
00346
00347 fill = bit_mask;
00348 while (fill-- > 0) table[leaf++] = sym;
00349 }
00350 }
00351 bit_mask >>= 1;
00352 bit_num++;
00353 }
00354
00355
00356 if (pos != table_mask)
00357 {
00358
00359 for (sym = pos; sym < table_mask; sym++) table[sym] = 0;
00360
00361
00362 pos <<= 16;
00363 table_mask <<= 16;
00364 bit_mask = 1 << 15;
00365
00366 while (bit_num <= 16)
00367 {
00368 for (sym = 0; sym < nsyms; sym++)
00369 {
00370 if (length[sym] == bit_num)
00371 {
00372 leaf = pos >> 16;
00373 for (fill = 0; fill < bit_num - nbits; fill++)
00374 {
00375
00376 if (table[leaf] == 0)
00377 {
00378 table[(next_symbol << 1)] = 0;
00379 table[(next_symbol << 1) + 1] = 0;
00380 table[leaf] = next_symbol++;
00381 }
00382
00383 leaf = table[leaf] << 1;
00384 if ((pos >> (15-fill)) & 1) leaf++;
00385 }
00386 table[leaf] = sym;
00387
00388 if ((pos += bit_mask) > table_mask) return 1;
00389 }
00390 }
00391 bit_mask >>= 1;
00392 bit_num++;
00393 }
00394 }
00395
00396
00397 if (pos == table_mask) return 0;
00398
00399
00400 for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
00401 return 0;
00402 }
00403
00404 int lzx_read_lens(UBYTE *lens, ULONG first, ULONG last, lzx_bits *lb) {
00405 ULONG i,j, x,y;
00406 int z;
00407
00408 register ULONG bitbuf = lb->bb;
00409 register int bitsleft = lb->bl;
00410 UBYTE *inpos = lb->ip;
00411 UWORD *hufftbl;
00412
00413 for (x = 0; x < 20; x++)
00414 {
00415 READ_BITS(y, 4);
00416 LENTABLE(PRETREE)[x] = y;
00417 }
00418 BUILD_TABLE(PRETREE);
00419
00420 for (x = first; x < last;)
00421 {
00422 READ_HUFFSYM(PRETREE, z);
00423 if (z == 17)
00424 {
00425 READ_BITS(y, 4); y += 4;
00426 while (y--) lens[x++] = 0;
00427 }
00428 else if (z == 18)
00429 {
00430 READ_BITS(y, 5); y += 20;
00431 while (y--) lens[x++] = 0;
00432 }
00433 else if (z == 19)
00434 {
00435 READ_BITS(y, 1); y += 4;
00436 READ_HUFFSYM(PRETREE, z);
00437 z = lens[x] - z; if (z < 0) z += 17;
00438 while (y--) lens[x++] = z;
00439 }
00440 else
00441 {
00442 z = lens[x] - z; if (z < 0) z += 17;
00443 lens[x++] = z;
00444 }
00445 }
00446
00447 lb->bb = bitbuf;
00448 lb->bl = bitsleft;
00449 lb->ip = inpos;
00450 return 0;
00451 }
00452
00453 int LZXdecompress(UBYTE* inpos, int inlen, UBYTE* outpos, int outlen) {
00454 UBYTE *endinp = inpos + inlen;
00455 UBYTE *window = LZX(window);
00456 UBYTE *runsrc, *rundest;
00457 UWORD *hufftbl;
00458
00459 ULONG window_posn = LZX(window_posn);
00460 ULONG window_size = LZX(window_size);
00461 ULONG R0 = LZX(R0);
00462 ULONG R1 = LZX(R1);
00463 ULONG R2 = LZX(R2);
00464
00465 register ULONG bitbuf;
00466 register int bitsleft;
00467 ULONG match_offset, i,j,k;
00468 lzx_bits lb;
00469
00470 int togo = outlen, this_run, main_element, aligned_bits;
00471 int match_length, length_footer, extra, verbatim_bits;
00472
00473 INIT_BITSTREAM;
00474
00475
00476 if (!LZX(header_read))
00477 {
00478 i = j = 0;
00479 READ_BITS(k, 1); if (k)
00480 {
00481 READ_BITS(i,16); READ_BITS(j,16);
00482 }
00483 LZX(intel_filesize) = (i << 16) | j;
00484 LZX(header_read) = 1;
00485 }
00486
00487
00488 while (togo > 0)
00489 {
00490
00491 if (LZX(block_remaining) == 0)
00492 {
00493 if (LZX(block_type) == LZX_BLOCKTYPE_UNCOMPRESSED)
00494 {
00495 if (LZX(block_length) & 1) inpos++;
00496 INIT_BITSTREAM;
00497 }
00498
00499 READ_BITS(LZX(block_type), 3);
00500 READ_BITS(i, 16);
00501 READ_BITS(j, 8);
00502 LZX(block_remaining) = LZX(block_length) = (i << 8) | j;
00503
00504 switch (LZX(block_type))
00505 {
00506 case LZX_BLOCKTYPE_ALIGNED:
00507 for (i = 0; i < 8; i++)
00508 {
00509 READ_BITS(j, 3); LENTABLE(ALIGNED)[i] = j;
00510 }
00511 BUILD_TABLE(ALIGNED);
00512
00513
00514 case LZX_BLOCKTYPE_VERBATIM:
00515 READ_LENGTHS(MAINTREE, 0, 256);
00516 READ_LENGTHS(MAINTREE, 256, LZX(main_elements));
00517 BUILD_TABLE(MAINTREE);
00518 if (LENTABLE(MAINTREE)[0xE8] != 0) LZX(intel_started) = 1;
00519
00520 READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS);
00521 BUILD_TABLE(LENGTH);
00522 break;
00523
00524 case LZX_BLOCKTYPE_UNCOMPRESSED:
00525 LZX(intel_started) = 1;
00526 ENSURE_BITS(16);
00527 if (bitsleft > 16) inpos -= 2;
00528 R0 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
00529 R1 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
00530 R2 = inpos[0]|(inpos[1]<<8)|(inpos[2]<<16)|(inpos[3]<<24);inpos+=4;
00531 break;
00532
00533 default:
00534 return DECR_ILLEGALDATA;
00535 }
00536 }
00537
00538
00539 if (inpos > endinp)
00540 {
00541
00542
00543
00544
00545
00546
00547
00548
00549 if (inpos > (endinp+2) || bitsleft < 16) return DECR_ILLEGALDATA;
00550 }
00551
00552 while ((this_run = LZX(block_remaining)) > 0 && togo > 0)
00553 {
00554 if (this_run > togo) this_run = togo;
00555 togo -= this_run;
00556 LZX(block_remaining) -= this_run;
00557
00558
00559 window_posn &= window_size - 1;
00560
00561 if ((window_posn + this_run) > window_size)
00562 return DECR_DATAFORMAT;
00563
00564 switch (LZX(block_type))
00565 {
00566
00567 case LZX_BLOCKTYPE_VERBATIM:
00568 while (this_run > 0)
00569 {
00570 READ_HUFFSYM(MAINTREE, main_element);
00571
00572 if (main_element < LZX_NUM_CHARS)
00573 {
00574
00575 window[window_posn++] = main_element;
00576 this_run--;
00577 }
00578 else
00579 {
00580
00581 main_element -= LZX_NUM_CHARS;
00582
00583 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
00584 if (match_length == LZX_NUM_PRIMARY_LENGTHS)
00585 {
00586 READ_HUFFSYM(LENGTH, length_footer);
00587 match_length += length_footer;
00588 }
00589 match_length += LZX_MIN_MATCH;
00590
00591 match_offset = main_element >> 3;
00592
00593 if (match_offset > 2)
00594 {
00595
00596 if (match_offset != 3)
00597 {
00598 extra = extra_bits[match_offset];
00599 READ_BITS(verbatim_bits, extra);
00600 match_offset = position_base[match_offset] - 2 + verbatim_bits;
00601 }
00602 else
00603 {
00604 match_offset = 1;
00605 }
00606
00607
00608 R2 = R1; R1 = R0; R0 = match_offset;
00609 }
00610 else if (match_offset == 0)
00611 {
00612 match_offset = R0;
00613 }
00614 else if (match_offset == 1)
00615 {
00616 match_offset = R1;
00617 R1 = R0; R0 = match_offset;
00618 }
00619 else
00620 {
00621 match_offset = R2;
00622 R2 = R0; R0 = match_offset;
00623 }
00624
00625 rundest = window + window_posn;
00626 runsrc = rundest - match_offset;
00627 window_posn += match_length;
00628 this_run -= match_length;
00629
00630
00631 while ((runsrc < window) && (match_length-- > 0))
00632 {
00633 *rundest++ = *(runsrc + window_size); runsrc++;
00634 }
00635
00636 while (match_length-- > 0) *rundest++ = *runsrc++;
00637
00638 }
00639 }
00640 break;
00641
00642 case LZX_BLOCKTYPE_ALIGNED:
00643 while (this_run > 0)
00644 {
00645 READ_HUFFSYM(MAINTREE, main_element);
00646
00647 if (main_element < LZX_NUM_CHARS)
00648 {
00649
00650 window[window_posn++] = main_element;
00651 this_run--;
00652 }
00653 else
00654 {
00655
00656 main_element -= LZX_NUM_CHARS;
00657
00658 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
00659 if (match_length == LZX_NUM_PRIMARY_LENGTHS)
00660 {
00661 READ_HUFFSYM(LENGTH, length_footer);
00662 match_length += length_footer;
00663 }
00664 match_length += LZX_MIN_MATCH;
00665
00666 match_offset = main_element >> 3;
00667
00668 if (match_offset > 2)
00669 {
00670
00671 extra = extra_bits[match_offset];
00672 match_offset = position_base[match_offset] - 2;
00673 if (extra > 3)
00674 {
00675
00676 extra -= 3;
00677 READ_BITS(verbatim_bits, extra);
00678 match_offset += (verbatim_bits << 3);
00679 READ_HUFFSYM(ALIGNED, aligned_bits);
00680 match_offset += aligned_bits;
00681 }
00682 else if (extra == 3)
00683 {
00684
00685 READ_HUFFSYM(ALIGNED, aligned_bits);
00686 match_offset += aligned_bits;
00687 }
00688 else if (extra > 0)
00689 {
00690
00691 READ_BITS(verbatim_bits, extra);
00692 match_offset += verbatim_bits;
00693 }
00694 else
00695 {
00696
00697 match_offset = 1;
00698 }
00699
00700
00701 R2 = R1; R1 = R0; R0 = match_offset;
00702 }
00703 else if (match_offset == 0)
00704 {
00705 match_offset = R0;
00706 }
00707 else if (match_offset == 1)
00708 {
00709 match_offset = R1;
00710 R1 = R0; R0 = match_offset;
00711 }
00712 else
00713 {
00714 match_offset = R2;
00715 R2 = R0; R0 = match_offset;
00716 }
00717
00718 rundest = window + window_posn;
00719 runsrc = rundest - match_offset;
00720 window_posn += match_length;
00721 this_run -= match_length;
00722
00723
00724 while ((runsrc < window) && (match_length-- > 0))
00725 {
00726 *rundest++ = *(runsrc + window_size); runsrc++;
00727 }
00728
00729 while (match_length-- > 0) *rundest++ = *runsrc++;
00730
00731 }
00732 }
00733 break;
00734
00735 case LZX_BLOCKTYPE_UNCOMPRESSED:
00736 if ((inpos + this_run) > endinp) return DECR_ILLEGALDATA;
00737 memcpy(window + window_posn, inpos, (size_t) this_run);
00738 inpos += this_run; window_posn += this_run;
00739 break;
00740
00741 default:
00742 return DECR_ILLEGALDATA;
00743 }
00744
00745 }
00746 }
00747
00748 if (togo != 0) return DECR_ILLEGALDATA;
00749 memcpy(outpos, window + ((!window_posn) ? window_size : window_posn) -
00750 outlen, (size_t) outlen);
00751
00752 LZX(window_posn) = window_posn;
00753 LZX(R0) = R0;
00754 LZX(R1) = R1;
00755 LZX(R2) = R2;
00756
00757
00758 if ((LZX(frames_read)++ < 32768) && LZX(intel_filesize) != 0)
00759 {
00760 if (outlen <= 6 || !LZX(intel_started))
00761 {
00762 LZX(intel_curpos) += outlen;
00763 }
00764 else
00765 {
00766 UBYTE *data = outpos;
00767 UBYTE *dataend = data + outlen - 10;
00768 LONG curpos = LZX(intel_curpos);
00769 LONG filesize = LZX(intel_filesize);
00770 LONG abs_off, rel_off;
00771
00772 LZX(intel_curpos) = curpos + outlen;
00773
00774 while (data < dataend)
00775 {
00776 if (*data++ != 0xE8)
00777 {
00778 curpos++; continue;
00779 }
00780 abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
00781 if ((abs_off >= -curpos) && (abs_off < filesize))
00782 {
00783 rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
00784 data[0] = (UBYTE) rel_off;
00785 data[1] = (UBYTE) (rel_off >> 8);
00786 data[2] = (UBYTE) (rel_off >> 16);
00787 data[3] = (UBYTE) (rel_off >> 24);
00788 }
00789 data += 4;
00790 curpos += 5;
00791 }
00792 }
00793 }
00794 return DECR_OK;
00795 }
00796