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