| 1 |
/* This file is part of libmspack. |
| 2 |
* (C) 2003-2013 Stuart Caie. |
| 3 |
* |
| 4 |
* The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted |
| 5 |
* by Microsoft Corporation. |
| 6 |
* |
| 7 |
* libmspack is free software; you can redistribute it and/or modify it under |
| 8 |
* the terms of the GNU Lesser General Public License (LGPL) version 2.1 |
| 9 |
* |
| 10 |
* For further details, see the file COPYING.LIB distributed with libmspack |
| 11 |
*/ |
| 12 |
|
| 13 |
/* LZX decompression implementation */ |
| 14 |
|
| 15 |
#include "lzx.h" |
| 16 |
#include <glib.h> |
| 17 |
|
| 18 |
/* Microsoft's LZX document (in cab-sdk.exe) and their implementation |
| 19 |
* of the com.ms.util.cab Java package do not concur. |
| 20 |
* |
| 21 |
* In the LZX document, there is a table showing the correlation between |
| 22 |
* window size and the number of position slots. It states that the 1MB |
| 23 |
* window = 40 slots and the 2MB window = 42 slots. In the implementation, |
| 24 |
* 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the |
| 25 |
* first slot whose position base is equal to or more than the required |
| 26 |
* window size'. This would explain why other tables in the document refer |
| 27 |
* to 50 slots rather than 42. |
| 28 |
* |
| 29 |
* The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode |
| 30 |
* is not defined in the specification. |
| 31 |
* |
| 32 |
* The LZX document does not state the uncompressed block has an |
| 33 |
* uncompressed length field. Where does this length field come from, so |
| 34 |
* we can know how large the block is? The implementation has it as the 24 |
| 35 |
* bits following after the 3 blocktype bits, before the alignment |
| 36 |
* padding. |
| 37 |
* |
| 38 |
* The LZX document states that aligned offset blocks have their aligned |
| 39 |
* offset huffman tree AFTER the main and length trees. The implementation |
| 40 |
* suggests that the aligned offset tree is BEFORE the main and length |
| 41 |
* trees. |
| 42 |
* |
| 43 |
* The LZX document decoding algorithm states that, in an aligned offset |
| 44 |
* block, if an extra_bits value is 1, 2 or 3, then that number of bits |
| 45 |
* should be read and the result added to the match offset. This is |
| 46 |
* correct for 1 and 2, but not 3, where just a huffman symbol (using the |
| 47 |
* aligned tree) should be read. |
| 48 |
* |
| 49 |
* Regarding the E8 preprocessing, the LZX document states 'No translation |
| 50 |
* may be performed on the last 6 bytes of the input block'. This is |
| 51 |
* correct. However, the pseudocode provided checks for the *E8 leader* |
| 52 |
* up to the last 6 bytes. If the leader appears between -10 and -7 bytes |
| 53 |
* from the end, this would cause the next four bytes to be modified, at |
| 54 |
* least one of which would be in the last 6 bytes, which is not allowed |
| 55 |
* according to the spec. |
| 56 |
* |
| 57 |
* The specification states that the huffman trees must always contain at |
| 58 |
* least one element. However, many CAB files contain blocks where the |
| 59 |
* length tree is completely empty (because there are no matches), and |
| 60 |
* this is expected to succeed. |
| 61 |
* |
| 62 |
* The errors in LZX documentation appear have been corrected in the |
| 63 |
* new documentation for the LZX DELTA format. |
| 64 |
* |
| 65 |
* http://msdn.microsoft.com/en-us/library/cc483133.aspx |
| 66 |
* |
| 67 |
* However, this is a different format, an extension of regular LZX. |
| 68 |
* I have noticed the following differences, there may be more: |
| 69 |
* |
| 70 |
* The maximum window size has increased from 2MB to 32MB. This also |
| 71 |
* increases the maximum number of position slots, etc. |
| 72 |
* |
| 73 |
* If the match length is 257 (the maximum possible), this signals |
| 74 |
* a further length decoding step, that allows for matches up to |
| 75 |
* 33024 bytes long. |
| 76 |
* |
| 77 |
* The format now allows for "reference data", supplied by the caller. |
| 78 |
* If match offsets go further back than the number of bytes |
| 79 |
* decompressed so far, that is them accessing the reference data. |
| 80 |
*/ |
| 81 |
|
| 82 |
/* import bit-reading macros and code */ |
| 83 |
#define BITS_TYPE struct lzxd_stream |
| 84 |
#define BITS_VAR lzx |
| 85 |
#define BITS_ORDER_MSB |
| 86 |
#define READ_BYTES do { \ |
| 87 |
unsigned char b0, b1; \ |
| 88 |
READ_IF_NEEDED; b0 = *i_ptr++; \ |
| 89 |
READ_IF_NEEDED; b1 = *i_ptr++; \ |
| 90 |
INJECT_BITS((b1 << 8) | b0, 16); \ |
| 91 |
} while (0) |
| 92 |
#include "readbits.h" |
| 93 |
|
| 94 |
/* import huffman-reading macros and code */ |
| 95 |
#define TABLEBITS(tbl) LZX_##tbl##_TABLEBITS |
| 96 |
#define MAXSYMBOLS(tbl) LZX_##tbl##_MAXSYMBOLS |
| 97 |
#define HUFF_TABLE(tbl,idx) lzx->tbl##_table[idx] |
| 98 |
#define HUFF_LEN(tbl,idx) lzx->tbl##_len[idx] |
| 99 |
#define HUFF_ERROR return lzx->error = LZX_ERR_DECRUNCH |
| 100 |
#include "readhuff.h" |
| 101 |
|
| 102 |
/* BUILD_TABLE(tbl) builds a huffman lookup table from code lengths */ |
| 103 |
#define BUILD_TABLE(tbl) \ |
| 104 |
if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \ |
| 105 |
&HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \ |
| 106 |
{ \ |
| 107 |
D(("failed to build %s table", #tbl)) \ |
| 108 |
return lzx->error = LZX_ERR_DECRUNCH; \ |
| 109 |
} |
| 110 |
|
| 111 |
#define BUILD_TABLE_MAYBE_EMPTY(tbl) do { \ |
| 112 |
lzx->tbl##_empty = 0; \ |
| 113 |
if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \ |
| 114 |
&HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \ |
| 115 |
{ \ |
| 116 |
for (i = 0; i < MAXSYMBOLS(tbl); i++) { \ |
| 117 |
if (HUFF_LEN(tbl, i) > 0) { \ |
| 118 |
D(("failed to build %s table", #tbl)) \ |
| 119 |
return lzx->error = LZX_ERR_DECRUNCH; \ |
| 120 |
} \ |
| 121 |
} \ |
| 122 |
/* empty tree - allow it, but don't decode symbols with it */ \ |
| 123 |
lzx->tbl##_empty = 1; \ |
| 124 |
} \ |
| 125 |
} while (0) |
| 126 |
|
| 127 |
/* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols |
| 128 |
* first to last in the given table. The code lengths are stored in their |
| 129 |
* own special LZX way. |
| 130 |
*/ |
| 131 |
#define READ_LENGTHS(tbl, first, last) do { \ |
| 132 |
STORE_BITS; \ |
| 133 |
if (lzxd_read_lens(lzx, &HUFF_LEN(tbl, 0), (first), \ |
| 134 |
(unsigned int)(last))) return lzx->error; \ |
| 135 |
RESTORE_BITS; \ |
| 136 |
} while (0) |
| 137 |
|
| 138 |
static int lzxd_read_lens(struct lzxd_stream *lzx, unsigned char *lens, |
| 139 |
unsigned int first, unsigned int last) |
| 140 |
{ |
| 141 |
/* bit buffer and huffman symbol decode variables */ |
| 142 |
register unsigned int bit_buffer; |
| 143 |
register int bits_left, i; |
| 144 |
register unsigned short sym; |
| 145 |
unsigned char *i_ptr, *i_end; |
| 146 |
|
| 147 |
unsigned int x, y; |
| 148 |
int z; |
| 149 |
|
| 150 |
RESTORE_BITS; |
| 151 |
|
| 152 |
/* read lengths for pretree (20 symbols, lengths stored in fixed 4 bits) */ |
| 153 |
for (x = 0; x < 20; x++) { |
| 154 |
READ_BITS(y, 4); |
| 155 |
lzx->PRETREE_len[x] = y; |
| 156 |
} |
| 157 |
BUILD_TABLE(PRETREE); |
| 158 |
|
| 159 |
for (x = first; x < last; ) { |
| 160 |
READ_HUFFSYM(PRETREE, z); |
| 161 |
if (z == 17) { |
| 162 |
/* code = 17, run of ([read 4 bits]+4) zeros */ |
| 163 |
READ_BITS(y, 4); y += 4; |
| 164 |
while (y--) lens[x++] = 0; |
| 165 |
} |
| 166 |
else if (z == 18) { |
| 167 |
/* code = 18, run of ([read 5 bits]+20) zeros */ |
| 168 |
READ_BITS(y, 5); y += 20; |
| 169 |
while (y--) lens[x++] = 0; |
| 170 |
} |
| 171 |
else if (z == 19) { |
| 172 |
/* code = 19, run of ([read 1 bit]+4) [read huffman symbol] */ |
| 173 |
READ_BITS(y, 1); y += 4; |
| 174 |
READ_HUFFSYM(PRETREE, z); |
| 175 |
z = lens[x] - z; if (z < 0) z += 17; |
| 176 |
while (y--) lens[x++] = z; |
| 177 |
} |
| 178 |
else { |
| 179 |
/* code = 0 to 16, delta current length entry */ |
| 180 |
z = lens[x] - z; if (z < 0) z += 17; |
| 181 |
lens[x++] = z; |
| 182 |
} |
| 183 |
} |
| 184 |
|
| 185 |
STORE_BITS; |
| 186 |
|
| 187 |
return LZX_ERR_OK; |
| 188 |
} |
| 189 |
|
| 190 |
/* LZX static data tables: |
| 191 |
* |
| 192 |
* LZX uses 'position slots' to represent match offsets. For every match, |
| 193 |
* a small 'position slot' number and a small offset from that slot are |
| 194 |
* encoded instead of one large offset. |
| 195 |
* |
| 196 |
* The number of slots is decided by how many are needed to encode the |
| 197 |
* largest offset for a given window size. This is easy when the gap between |
| 198 |
* slots is less than 128Kb, it's a linear relationship. But when extra_bits |
| 199 |
* reaches its limit of 17 (because LZX can only ensure reading 17 bits of |
| 200 |
* data at a time), we can only jump 128Kb at a time and have to start |
| 201 |
* using more and more position slots as each window size doubles. |
| 202 |
* |
| 203 |
* position_base[] is an index to the position slot bases |
| 204 |
* |
| 205 |
* extra_bits[] states how many bits of offset-from-base data is needed. |
| 206 |
* |
| 207 |
* They are calculated as follows: |
| 208 |
* extra_bits[i] = 0 where i < 4 |
| 209 |
* extra_bits[i] = floor(i/2)-1 where i >= 4 && i < 36 |
| 210 |
* extra_bits[i] = 17 where i >= 36 |
| 211 |
* position_base[0] = 0 |
| 212 |
* position_base[i] = position_base[i-1] + (1 << extra_bits[i-1]) |
| 213 |
*/ |
| 214 |
static const unsigned int position_slots[11] = { |
| 215 |
30, 32, 34, 36, 38, 42, 50, 66, 98, 162, 290 |
| 216 |
}; |
| 217 |
static const unsigned char extra_bits[36] = { |
| 218 |
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, |
| 219 |
9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16 |
| 220 |
}; |
| 221 |
static const unsigned int position_base[290] = { |
| 222 |
0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, |
| 223 |
768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, |
| 224 |
49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 655360, |
| 225 |
786432, 917504, 1048576, 1179648, 1310720, 1441792, 1572864, 1703936, |
| 226 |
1835008, 1966080, 2097152, 2228224, 2359296, 2490368, 2621440, 2752512, |
| 227 |
2883584, 3014656, 3145728, 3276800, 3407872, 3538944, 3670016, 3801088, |
| 228 |
3932160, 4063232, 4194304, 4325376, 4456448, 4587520, 4718592, 4849664, |
| 229 |
4980736, 5111808, 5242880, 5373952, 5505024, 5636096, 5767168, 5898240, |
| 230 |
6029312, 6160384, 6291456, 6422528, 6553600, 6684672, 6815744, 6946816, |
| 231 |
7077888, 7208960, 7340032, 7471104, 7602176, 7733248, 7864320, 7995392, |
| 232 |
8126464, 8257536, 8388608, 8519680, 8650752, 8781824, 8912896, 9043968, |
| 233 |
9175040, 9306112, 9437184, 9568256, 9699328, 9830400, 9961472, 10092544, |
| 234 |
10223616, 10354688, 10485760, 10616832, 10747904, 10878976, 11010048, |
| 235 |
11141120, 11272192, 11403264, 11534336, 11665408, 11796480, 11927552, |
| 236 |
12058624, 12189696, 12320768, 12451840, 12582912, 12713984, 12845056, |
| 237 |
12976128, 13107200, 13238272, 13369344, 13500416, 13631488, 13762560, |
| 238 |
13893632, 14024704, 14155776, 14286848, 14417920, 14548992, 14680064, |
| 239 |
14811136, 14942208, 15073280, 15204352, 15335424, 15466496, 15597568, |
| 240 |
15728640, 15859712, 15990784, 16121856, 16252928, 16384000, 16515072, |
| 241 |
16646144, 16777216, 16908288, 17039360, 17170432, 17301504, 17432576, |
| 242 |
17563648, 17694720, 17825792, 17956864, 18087936, 18219008, 18350080, |
| 243 |
18481152, 18612224, 18743296, 18874368, 19005440, 19136512, 19267584, |
| 244 |
19398656, 19529728, 19660800, 19791872, 19922944, 20054016, 20185088, |
| 245 |
20316160, 20447232, 20578304, 20709376, 20840448, 20971520, 21102592, |
| 246 |
21233664, 21364736, 21495808, 21626880, 21757952, 21889024, 22020096, |
| 247 |
22151168, 22282240, 22413312, 22544384, 22675456, 22806528, 22937600, |
| 248 |
23068672, 23199744, 23330816, 23461888, 23592960, 23724032, 23855104, |
| 249 |
23986176, 24117248, 24248320, 24379392, 24510464, 24641536, 24772608, |
| 250 |
24903680, 25034752, 25165824, 25296896, 25427968, 25559040, 25690112, |
| 251 |
25821184, 25952256, 26083328, 26214400, 26345472, 26476544, 26607616, |
| 252 |
26738688, 26869760, 27000832, 27131904, 27262976, 27394048, 27525120, |
| 253 |
27656192, 27787264, 27918336, 28049408, 28180480, 28311552, 28442624, |
| 254 |
28573696, 28704768, 28835840, 28966912, 29097984, 29229056, 29360128, |
| 255 |
29491200, 29622272, 29753344, 29884416, 30015488, 30146560, 30277632, |
| 256 |
30408704, 30539776, 30670848, 30801920, 30932992, 31064064, 31195136, |
| 257 |
31326208, 31457280, 31588352, 31719424, 31850496, 31981568, 32112640, |
| 258 |
32243712, 32374784, 32505856, 32636928, 32768000, 32899072, 33030144, |
| 259 |
33161216, 33292288, 33423360 |
| 260 |
}; |
| 261 |
|
| 262 |
static void lzxd_reset_state(struct lzxd_stream *lzx) { |
| 263 |
int i; |
| 264 |
|
| 265 |
lzx->R0 = 1; |
| 266 |
lzx->R1 = 1; |
| 267 |
lzx->R2 = 1; |
| 268 |
lzx->header_read = 0; |
| 269 |
lzx->block_remaining = 0; |
| 270 |
lzx->block_type = LZX_BLOCKTYPE_INVALID; |
| 271 |
|
| 272 |
/* initialise tables to 0 (because deltas will be applied to them) */ |
| 273 |
for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) lzx->MAINTREE_len[i] = 0; |
| 274 |
for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) lzx->LENGTH_len[i] = 0; |
| 275 |
} |
| 276 |
|
| 277 |
/*-------- main LZX code --------*/ |
| 278 |
|
| 279 |
struct lzxd_stream *ews_lzxd_init(FILE *input, |
| 280 |
FILE *output, |
| 281 |
int window_bits, |
| 282 |
int reset_interval, |
| 283 |
int input_buffer_size, |
| 284 |
off_t output_length, |
| 285 |
char is_delta) |
| 286 |
{ |
| 287 |
unsigned int window_size = 1 << window_bits; |
| 288 |
struct lzxd_stream *lzx; |
| 289 |
|
| 290 |
/* LZX DELTA window sizes are between 2^17 (128KiB) and 2^25 (32MiB), |
| 291 |
* regular LZX windows are between 2^15 (32KiB) and 2^21 (2MiB) |
| 292 |
*/ |
| 293 |
if (is_delta) { |
| 294 |
if (window_bits < 17 || window_bits > 25) return NULL; |
| 295 |
} |
| 296 |
else { |
| 297 |
if (window_bits < 15 || window_bits > 21) return NULL; |
| 298 |
} |
| 299 |
|
| 300 |
input_buffer_size = (input_buffer_size + 1) & -2; |
| 301 |
if (!input_buffer_size) return NULL; |
| 302 |
|
| 303 |
/* allocate decompression state */ |
| 304 |
if (!(lzx = (struct lzxd_stream *) malloc(sizeof(struct lzxd_stream)))) { |
| 305 |
return NULL; |
| 306 |
} |
| 307 |
|
| 308 |
/* allocate decompression window and input buffer */ |
| 309 |
lzx->window = (unsigned char *) malloc((size_t) window_size); |
| 310 |
lzx->inbuf = (unsigned char *) malloc((size_t) input_buffer_size); |
| 311 |
if (!lzx->window || !lzx->inbuf) { |
| 312 |
free(lzx->window); |
| 313 |
free(lzx->inbuf); |
| 314 |
free(lzx); |
| 315 |
return NULL; |
| 316 |
} |
| 317 |
|
| 318 |
/* initialise decompression state */ |
| 319 |
lzx->input = input; |
| 320 |
lzx->output = output; |
| 321 |
lzx->offset = 0; |
| 322 |
lzx->length = output_length; |
| 323 |
|
| 324 |
lzx->inbuf_size = input_buffer_size; |
| 325 |
lzx->window_size = 1 << window_bits; |
| 326 |
lzx->ref_data_size = 0; |
| 327 |
lzx->window_posn = 0; |
| 328 |
lzx->frame_posn = 0; |
| 329 |
lzx->frame = 0; |
| 330 |
lzx->reset_interval = reset_interval; |
| 331 |
lzx->intel_filesize = 0; |
| 332 |
lzx->intel_curpos = 0; |
| 333 |
lzx->intel_started = 0; |
| 334 |
lzx->error = LZX_ERR_OK; |
| 335 |
lzx->num_offsets = position_slots[window_bits - 15] << 3; |
| 336 |
lzx->is_delta = is_delta; |
| 337 |
|
| 338 |
lzx->o_ptr = lzx->o_end = &lzx->e8_buf[0]; |
| 339 |
lzxd_reset_state(lzx); |
| 340 |
INIT_BITS; |
| 341 |
return lzx; |
| 342 |
} |
| 343 |
|
| 344 |
int ews_lzxd_set_reference_data(struct lzxd_stream *lzx, |
| 345 |
FILE *input, |
| 346 |
unsigned int length) |
| 347 |
{ |
| 348 |
if (!lzx) return LZX_ERR_ARGS; |
| 349 |
|
| 350 |
if (!lzx->is_delta) { |
| 351 |
D(("only LZX DELTA streams support reference data")) |
| 352 |
return LZX_ERR_ARGS; |
| 353 |
} |
| 354 |
if (lzx->offset) { |
| 355 |
D(("too late to set reference data after decoding starts")) |
| 356 |
return LZX_ERR_ARGS; |
| 357 |
} |
| 358 |
if (length > lzx->window_size) { |
| 359 |
D(("reference length (%u) is longer than the window", length)) |
| 360 |
return LZX_ERR_ARGS; |
| 361 |
} |
| 362 |
if (length > 0 && (!input)) { |
| 363 |
D(("length > 0 but no input")) |
| 364 |
return LZX_ERR_ARGS; |
| 365 |
} |
| 366 |
|
| 367 |
lzx->ref_data_size = length; |
| 368 |
if (length > 0) { |
| 369 |
/* copy reference data */ |
| 370 |
unsigned char *pos = &lzx->window[lzx->window_size - length]; |
| 371 |
int bytes = fread(pos, 1, length, input); |
| 372 |
if (bytes < length) return LZX_ERR_READ; |
| 373 |
} |
| 374 |
lzx->ref_data_size = length; |
| 375 |
return LZX_ERR_OK; |
| 376 |
} |
| 377 |
|
| 378 |
void ews_lzxd_set_output_length(struct lzxd_stream *lzx, off_t out_bytes) { |
| 379 |
if (lzx) lzx->length = out_bytes; |
| 380 |
} |
| 381 |
|
| 382 |
int ews_lzxd_decompress(struct lzxd_stream *lzx, off_t out_bytes) { |
| 383 |
/* bitstream and huffman reading variables */ |
| 384 |
register unsigned int bit_buffer; |
| 385 |
register int bits_left, i=0; |
| 386 |
unsigned char *i_ptr, *i_end; |
| 387 |
register unsigned short sym; |
| 388 |
|
| 389 |
int match_length, length_footer, extra, verbatim_bits, bytes_todo; |
| 390 |
int this_run, main_element, aligned_bits, j; |
| 391 |
unsigned char *window, *runsrc, *rundest, buf[12]; |
| 392 |
unsigned int frame_size=0, end_frame, match_offset, window_posn; |
| 393 |
unsigned int R0, R1, R2; |
| 394 |
|
| 395 |
/* easy answers */ |
| 396 |
if (!lzx || (out_bytes < 0)) return LZX_ERR_ARGS; |
| 397 |
if (lzx->error) return lzx->error; |
| 398 |
|
| 399 |
/* flush out any stored-up bytes before we begin */ |
| 400 |
i = lzx->o_end - lzx->o_ptr; |
| 401 |
if ((off_t) i > out_bytes) i = (int) out_bytes; |
| 402 |
if (i) { |
| 403 |
if (fwrite(lzx->o_ptr, 1, i, lzx->output) != i) { |
| 404 |
return lzx->error = LZX_ERR_WRITE; |
| 405 |
} |
| 406 |
lzx->o_ptr += i; |
| 407 |
lzx->offset += i; |
| 408 |
out_bytes -= i; |
| 409 |
} |
| 410 |
if (out_bytes == 0) return LZX_ERR_OK; |
| 411 |
|
| 412 |
/* restore local state */ |
| 413 |
RESTORE_BITS; |
| 414 |
window = lzx->window; |
| 415 |
window_posn = lzx->window_posn; |
| 416 |
R0 = lzx->R0; |
| 417 |
R1 = lzx->R1; |
| 418 |
R2 = lzx->R2; |
| 419 |
|
| 420 |
end_frame = (unsigned int)((lzx->offset + out_bytes) / LZX_FRAME_SIZE) + 1; |
| 421 |
|
| 422 |
while (lzx->frame < end_frame) { |
| 423 |
/* have we reached the reset interval? (if there is one?) */ |
| 424 |
if (lzx->reset_interval && ((lzx->frame % lzx->reset_interval) == 0)) { |
| 425 |
if (lzx->block_remaining) { |
| 426 |
D(("%d bytes remaining at reset interval", lzx->block_remaining)) |
| 427 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 428 |
} |
| 429 |
|
| 430 |
/* re-read the intel header and reset the huffman lengths */ |
| 431 |
lzxd_reset_state(lzx); |
| 432 |
R0 = lzx->R0; |
| 433 |
R1 = lzx->R1; |
| 434 |
R2 = lzx->R2; |
| 435 |
} |
| 436 |
|
| 437 |
/* LZX DELTA format has chunk_size, not present in LZX format */ |
| 438 |
if (lzx->is_delta) { |
| 439 |
ENSURE_BITS(16); |
| 440 |
REMOVE_BITS(16); |
| 441 |
} |
| 442 |
|
| 443 |
/* read header if necessary */ |
| 444 |
if (!lzx->header_read) { |
| 445 |
/* read 1 bit. if bit=0, intel filesize = 0. |
| 446 |
* if bit=1, read intel filesize (32 bits) */ |
| 447 |
j = 0; READ_BITS(i, 1); if (i) { READ_BITS(i, 16); READ_BITS(j, 16); } |
| 448 |
lzx->intel_filesize = (i << 16) | j; |
| 449 |
lzx->header_read = 1; |
| 450 |
} |
| 451 |
|
| 452 |
/* calculate size of frame: all frames are 32k except the final frame |
| 453 |
* which is 32kb or less. this can only be calculated when lzx->length |
| 454 |
* has been filled in. */ |
| 455 |
frame_size = LZX_FRAME_SIZE; |
| 456 |
if (lzx->length && (lzx->length - lzx->offset) < (off_t)frame_size) { |
| 457 |
frame_size = lzx->length - lzx->offset; |
| 458 |
} |
| 459 |
|
| 460 |
/* decode until one more frame is available */ |
| 461 |
bytes_todo = lzx->frame_posn + frame_size - window_posn; |
| 462 |
while (bytes_todo > 0) { |
| 463 |
/* initialise new block, if one is needed */ |
| 464 |
if (lzx->block_remaining == 0) { |
| 465 |
/* realign if previous block was an odd-sized UNCOMPRESSED block */ |
| 466 |
if ((lzx->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) && |
| 467 |
(lzx->block_length & 1)) |
| 468 |
{ |
| 469 |
READ_IF_NEEDED; |
| 470 |
i_ptr++; |
| 471 |
} |
| 472 |
|
| 473 |
/* read block type (3 bits) and block length (24 bits) */ |
| 474 |
READ_BITS(lzx->block_type, 3); |
| 475 |
READ_BITS(i, 16); READ_BITS(j, 8); |
| 476 |
lzx->block_remaining = lzx->block_length = (i << 8) | j; |
| 477 |
/*D(("new block t%d len %u", lzx->block_type, lzx->block_length))*/ |
| 478 |
|
| 479 |
/* read individual block headers */ |
| 480 |
switch (lzx->block_type) { |
| 481 |
case LZX_BLOCKTYPE_ALIGNED: |
| 482 |
/* read lengths of and build aligned huffman decoding tree */ |
| 483 |
for (i = 0; i < 8; i++) { READ_BITS(j, 3); lzx->ALIGNED_len[i] = j; } |
| 484 |
BUILD_TABLE(ALIGNED); |
| 485 |
/* no break -- rest of aligned header is same as verbatim */ |
| 486 |
case LZX_BLOCKTYPE_VERBATIM: |
| 487 |
/* read lengths of and build main huffman decoding tree */ |
| 488 |
READ_LENGTHS(MAINTREE, 0, 256); |
| 489 |
READ_LENGTHS(MAINTREE, 256, LZX_NUM_CHARS + lzx->num_offsets); |
| 490 |
BUILD_TABLE(MAINTREE); |
| 491 |
/* if the literal 0xE8 is anywhere in the block... */ |
| 492 |
if (lzx->MAINTREE_len[0xE8] != 0) lzx->intel_started = 1; |
| 493 |
/* read lengths of and build lengths huffman decoding tree */ |
| 494 |
READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS); |
| 495 |
BUILD_TABLE_MAYBE_EMPTY(LENGTH); |
| 496 |
break; |
| 497 |
|
| 498 |
case LZX_BLOCKTYPE_UNCOMPRESSED: |
| 499 |
/* because we can't assume otherwise */ |
| 500 |
lzx->intel_started = 1; |
| 501 |
|
| 502 |
/* read 1-16 (not 0-15) bits to align to bytes */ |
| 503 |
ENSURE_BITS(16); |
| 504 |
if (bits_left > 16) i_ptr -= 2; |
| 505 |
bits_left = 0; bit_buffer = 0; |
| 506 |
|
| 507 |
/* read 12 bytes of stored R0 / R1 / R2 values */ |
| 508 |
for (rundest = &buf[0], i = 0; i < 12; i++) { |
| 509 |
READ_IF_NEEDED; |
| 510 |
*rundest++ = *i_ptr++; |
| 511 |
} |
| 512 |
R0 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24); |
| 513 |
R1 = buf[4] | (buf[5] << 8) | (buf[6] << 16) | (buf[7] << 24); |
| 514 |
R2 = buf[8] | (buf[9] << 8) | (buf[10] << 16) | (buf[11] << 24); |
| 515 |
break; |
| 516 |
|
| 517 |
default: |
| 518 |
D(("bad block type")) |
| 519 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 520 |
} |
| 521 |
} |
| 522 |
|
| 523 |
/* decode more of the block: |
| 524 |
* run = min(what's available, what's needed) */ |
| 525 |
this_run = lzx->block_remaining; |
| 526 |
if (this_run > bytes_todo) this_run = bytes_todo; |
| 527 |
|
| 528 |
/* assume we decode exactly this_run bytes, for now */ |
| 529 |
bytes_todo -= this_run; |
| 530 |
lzx->block_remaining -= this_run; |
| 531 |
|
| 532 |
/* decode at least this_run bytes */ |
| 533 |
switch (lzx->block_type) { |
| 534 |
case LZX_BLOCKTYPE_VERBATIM: |
| 535 |
while (this_run > 0) { |
| 536 |
READ_HUFFSYM(MAINTREE, main_element); |
| 537 |
if (main_element < LZX_NUM_CHARS) { |
| 538 |
/* literal: 0 to LZX_NUM_CHARS-1 */ |
| 539 |
window[window_posn++] = main_element; |
| 540 |
this_run--; |
| 541 |
} |
| 542 |
else { |
| 543 |
/* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */ |
| 544 |
main_element -= LZX_NUM_CHARS; |
| 545 |
|
| 546 |
/* get match length */ |
| 547 |
match_length = main_element & LZX_NUM_PRIMARY_LENGTHS; |
| 548 |
if (match_length == LZX_NUM_PRIMARY_LENGTHS) { |
| 549 |
if (lzx->LENGTH_empty) { |
| 550 |
D(("LENGTH symbol needed but tree is empty")) |
| 551 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 552 |
} |
| 553 |
READ_HUFFSYM(LENGTH, length_footer); |
| 554 |
match_length += length_footer; |
| 555 |
} |
| 556 |
match_length += LZX_MIN_MATCH; |
| 557 |
|
| 558 |
/* get match offset */ |
| 559 |
switch ((match_offset = (main_element >> 3))) { |
| 560 |
case 0: match_offset = R0; break; |
| 561 |
case 1: match_offset = R1; R1=R0; R0 = match_offset; break; |
| 562 |
case 2: match_offset = R2; R2=R0; R0 = match_offset; break; |
| 563 |
case 3: match_offset = 1; R2=R1; R1=R0; R0 = match_offset; break; |
| 564 |
default: |
| 565 |
extra = (match_offset >= 36) ? 17 : extra_bits[match_offset]; |
| 566 |
READ_BITS(verbatim_bits, extra); |
| 567 |
match_offset = position_base[match_offset] - 2 + verbatim_bits; |
| 568 |
R2 = R1; R1 = R0; R0 = match_offset; |
| 569 |
} |
| 570 |
|
| 571 |
/* LZX DELTA uses max match length to signal even longer match */ |
| 572 |
if (match_length == LZX_MAX_MATCH && lzx->is_delta) { |
| 573 |
int extra_len = 0; |
| 574 |
ENSURE_BITS(3); /* 4 entry huffman tree */ |
| 575 |
if (PEEK_BITS(1) == 0) { |
| 576 |
REMOVE_BITS(1); /* '0' -> 8 extra length bits */ |
| 577 |
READ_BITS(extra_len, 8); |
| 578 |
} |
| 579 |
else if (PEEK_BITS(2) == 2) { |
| 580 |
REMOVE_BITS(2); /* '10' -> 10 extra length bits + 0x100 */ |
| 581 |
READ_BITS(extra_len, 10); |
| 582 |
extra_len += 0x100; |
| 583 |
} |
| 584 |
else if (PEEK_BITS(3) == 6) { |
| 585 |
REMOVE_BITS(3); /* '110' -> 12 extra length bits + 0x500 */ |
| 586 |
READ_BITS(extra_len, 12); |
| 587 |
extra_len += 0x500; |
| 588 |
} |
| 589 |
else { |
| 590 |
REMOVE_BITS(3); /* '111' -> 15 extra length bits */ |
| 591 |
READ_BITS(extra_len, 15); |
| 592 |
} |
| 593 |
match_length += extra_len; |
| 594 |
} |
| 595 |
|
| 596 |
if ((window_posn + match_length) > lzx->window_size) { |
| 597 |
D(("match ran over window wrap")) |
| 598 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 599 |
} |
| 600 |
|
| 601 |
/* copy match */ |
| 602 |
rundest = &window[window_posn]; |
| 603 |
i = match_length; |
| 604 |
/* does match offset wrap the window? */ |
| 605 |
if (match_offset > window_posn) { |
| 606 |
if (match_offset > lzx->offset && |
| 607 |
(match_offset - window_posn) > lzx->ref_data_size) |
| 608 |
{ |
| 609 |
D(("match offset beyond LZX stream")) |
| 610 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 611 |
} |
| 612 |
/* j = length from match offset to end of window */ |
| 613 |
j = match_offset - window_posn; |
| 614 |
if (j > (int) lzx->window_size) { |
| 615 |
D(("match offset beyond window boundaries")) |
| 616 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 617 |
} |
| 618 |
runsrc = &window[lzx->window_size - j]; |
| 619 |
if (j < i) { |
| 620 |
/* if match goes over the window edge, do two copy runs */ |
| 621 |
i -= j; while (j-- > 0) *rundest++ = *runsrc++; |
| 622 |
runsrc = window; |
| 623 |
} |
| 624 |
while (i-- > 0) *rundest++ = *runsrc++; |
| 625 |
} |
| 626 |
else { |
| 627 |
runsrc = rundest - match_offset; |
| 628 |
while (i-- > 0) *rundest++ = *runsrc++; |
| 629 |
} |
| 630 |
|
| 631 |
this_run -= match_length; |
| 632 |
window_posn += match_length; |
| 633 |
} |
| 634 |
} /* while (this_run > 0) */ |
| 635 |
break; |
| 636 |
|
| 637 |
case LZX_BLOCKTYPE_ALIGNED: |
| 638 |
while (this_run > 0) { |
| 639 |
READ_HUFFSYM(MAINTREE, main_element); |
| 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 |
/* get match length */ |
| 650 |
match_length = main_element & LZX_NUM_PRIMARY_LENGTHS; |
| 651 |
if (match_length == LZX_NUM_PRIMARY_LENGTHS) { |
| 652 |
if (lzx->LENGTH_empty) { |
| 653 |
D(("LENGTH symbol needed but tree is empty")) |
| 654 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 655 |
} |
| 656 |
READ_HUFFSYM(LENGTH, length_footer); |
| 657 |
match_length += length_footer; |
| 658 |
} |
| 659 |
match_length += LZX_MIN_MATCH; |
| 660 |
|
| 661 |
/* get match offset */ |
| 662 |
switch ((match_offset = (main_element >> 3))) { |
| 663 |
case 0: match_offset = R0; break; |
| 664 |
case 1: match_offset = R1; R1 = R0; R0 = match_offset; break; |
| 665 |
case 2: match_offset = R2; R2 = R0; R0 = match_offset; break; |
| 666 |
default: |
| 667 |
extra = (match_offset >= 36) ? 17 : extra_bits[match_offset]; |
| 668 |
match_offset = position_base[match_offset] - 2; |
| 669 |
if (extra > 3) { |
| 670 |
/* verbatim and aligned bits */ |
| 671 |
extra -= 3; |
| 672 |
READ_BITS(verbatim_bits, extra); |
| 673 |
match_offset += (verbatim_bits << 3); |
| 674 |
READ_HUFFSYM(ALIGNED, aligned_bits); |
| 675 |
match_offset += aligned_bits; |
| 676 |
} |
| 677 |
else if (extra == 3) { |
| 678 |
/* aligned bits only */ |
| 679 |
READ_HUFFSYM(ALIGNED, aligned_bits); |
| 680 |
match_offset += aligned_bits; |
| 681 |
} |
| 682 |
else if (extra > 0) { /* extra==1, extra==2 */ |
| 683 |
/* verbatim bits only */ |
| 684 |
READ_BITS(verbatim_bits, extra); |
| 685 |
match_offset += verbatim_bits; |
| 686 |
} |
| 687 |
else /* extra == 0 */ { |
| 688 |
/* ??? not defined in LZX specification! */ |
| 689 |
match_offset = 1; |
| 690 |
} |
| 691 |
/* update repeated offset LRU queue */ |
| 692 |
R2 = R1; R1 = R0; R0 = match_offset; |
| 693 |
} |
| 694 |
|
| 695 |
/* LZX DELTA uses max match length to signal even longer match */ |
| 696 |
if (match_length == LZX_MAX_MATCH && lzx->is_delta) { |
| 697 |
int extra_len = 0; |
| 698 |
ENSURE_BITS(3); /* 4 entry huffman tree */ |
| 699 |
if (PEEK_BITS(1) == 0) { |
| 700 |
REMOVE_BITS(1); /* '0' -> 8 extra length bits */ |
| 701 |
READ_BITS(extra_len, 8); |
| 702 |
} |
| 703 |
else if (PEEK_BITS(2) == 2) { |
| 704 |
REMOVE_BITS(2); /* '10' -> 10 extra length bits + 0x100 */ |
| 705 |
READ_BITS(extra_len, 10); |
| 706 |
extra_len += 0x100; |
| 707 |
} |
| 708 |
else if (PEEK_BITS(3) == 6) { |
| 709 |
REMOVE_BITS(3); /* '110' -> 12 extra length bits + 0x500 */ |
| 710 |
READ_BITS(extra_len, 12); |
| 711 |
extra_len += 0x500; |
| 712 |
} |
| 713 |
else { |
| 714 |
REMOVE_BITS(3); /* '111' -> 15 extra length bits */ |
| 715 |
READ_BITS(extra_len, 15); |
| 716 |
} |
| 717 |
match_length += extra_len; |
| 718 |
} |
| 719 |
|
| 720 |
if ((window_posn + match_length) > lzx->window_size) { |
| 721 |
D(("match ran over window wrap")) |
| 722 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 723 |
} |
| 724 |
|
| 725 |
/* copy match */ |
| 726 |
rundest = &window[window_posn]; |
| 727 |
i = match_length; |
| 728 |
/* does match offset wrap the window? */ |
| 729 |
if (match_offset > window_posn) { |
| 730 |
if (match_offset > lzx->offset && |
| 731 |
(match_offset - window_posn) > lzx->ref_data_size) |
| 732 |
{ |
| 733 |
D(("match offset beyond LZX stream")) |
| 734 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 735 |
} |
| 736 |
/* j = length from match offset to end of window */ |
| 737 |
j = match_offset - window_posn; |
| 738 |
if (j > (int) lzx->window_size) { |
| 739 |
D(("match offset beyond window boundaries")) |
| 740 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 741 |
} |
| 742 |
runsrc = &window[lzx->window_size - j]; |
| 743 |
if (j < i) { |
| 744 |
/* if match goes over the window edge, do two copy runs */ |
| 745 |
i -= j; while (j-- > 0) *rundest++ = *runsrc++; |
| 746 |
runsrc = window; |
| 747 |
} |
| 748 |
while (i-- > 0) *rundest++ = *runsrc++; |
| 749 |
} |
| 750 |
else { |
| 751 |
runsrc = rundest - match_offset; |
| 752 |
while (i-- > 0) *rundest++ = *runsrc++; |
| 753 |
} |
| 754 |
|
| 755 |
this_run -= match_length; |
| 756 |
window_posn += match_length; |
| 757 |
} |
| 758 |
} /* while (this_run > 0) */ |
| 759 |
break; |
| 760 |
|
| 761 |
case LZX_BLOCKTYPE_UNCOMPRESSED: |
| 762 |
/* as this_run is limited not to wrap a frame, this also means it |
| 763 |
* won't wrap the window (as the window is a multiple of 32k) */ |
| 764 |
rundest = &window[window_posn]; |
| 765 |
window_posn += this_run; |
| 766 |
while (this_run > 0) { |
| 767 |
if ((i = i_end - i_ptr) == 0) { |
| 768 |
READ_IF_NEEDED; |
| 769 |
} |
| 770 |
else { |
| 771 |
if (i > this_run) i = this_run; |
| 772 |
memcpy(rundest, i_ptr, (size_t) i); |
| 773 |
rundest += i; |
| 774 |
i_ptr += i; |
| 775 |
this_run -= i; |
| 776 |
} |
| 777 |
} |
| 778 |
break; |
| 779 |
|
| 780 |
default: |
| 781 |
return lzx->error = LZX_ERR_DECRUNCH; /* might as well */ |
| 782 |
} |
| 783 |
|
| 784 |
/* did the final match overrun our desired this_run length? */ |
| 785 |
if (this_run < 0) { |
| 786 |
if ((unsigned int)(-this_run) > lzx->block_remaining) { |
| 787 |
D(("overrun went past end of block by %d (%d remaining)", |
| 788 |
-this_run, lzx->block_remaining )) |
| 789 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 790 |
} |
| 791 |
lzx->block_remaining -= -this_run; |
| 792 |
} |
| 793 |
} /* while (bytes_todo > 0) */ |
| 794 |
|
| 795 |
/* streams don't extend over frame boundaries */ |
| 796 |
if ((window_posn - lzx->frame_posn) != frame_size) { |
| 797 |
D(("decode beyond output frame limits! %d != %d", |
| 798 |
window_posn - lzx->frame_posn, frame_size)) |
| 799 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 800 |
} |
| 801 |
|
| 802 |
/* re-align input bitstream */ |
| 803 |
if (bits_left > 0) ENSURE_BITS(16); |
| 804 |
if (bits_left & 15) REMOVE_BITS(bits_left & 15); |
| 805 |
|
| 806 |
/* check that we've used all of the previous frame first */ |
| 807 |
if (lzx->o_ptr != lzx->o_end) { |
| 808 |
D(("%" G_GINT64_FORMAT " avail bytes, new %d frame", (gint64) (lzx->o_end - lzx->o_ptr), frame_size)) |
| 809 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 810 |
} |
| 811 |
|
| 812 |
/* does this intel block _really_ need decoding? */ |
| 813 |
if (lzx->intel_started && lzx->intel_filesize && |
| 814 |
(lzx->frame <= 32768) && (frame_size > 10)) |
| 815 |
{ |
| 816 |
unsigned char *data = &lzx->e8_buf[0]; |
| 817 |
unsigned char *dataend = &lzx->e8_buf[frame_size - 10]; |
| 818 |
signed int curpos = lzx->intel_curpos; |
| 819 |
signed int filesize = lzx->intel_filesize; |
| 820 |
signed int abs_off, rel_off; |
| 821 |
|
| 822 |
/* copy e8 block to the e8 buffer and tweak if needed */ |
| 823 |
lzx->o_ptr = data; |
| 824 |
memcpy(data, &lzx->window[lzx->frame_posn], frame_size); |
| 825 |
|
| 826 |
while (data < dataend) { |
| 827 |
if (*data++ != 0xE8) { curpos++; continue; } |
| 828 |
abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24); |
| 829 |
if ((abs_off >= -curpos) && (abs_off < filesize)) { |
| 830 |
rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize; |
| 831 |
data[0] = (unsigned char) rel_off; |
| 832 |
data[1] = (unsigned char) (rel_off >> 8); |
| 833 |
data[2] = (unsigned char) (rel_off >> 16); |
| 834 |
data[3] = (unsigned char) (rel_off >> 24); |
| 835 |
} |
| 836 |
data += 4; |
| 837 |
curpos += 5; |
| 838 |
} |
| 839 |
lzx->intel_curpos += frame_size; |
| 840 |
} |
| 841 |
else { |
| 842 |
lzx->o_ptr = &lzx->window[lzx->frame_posn]; |
| 843 |
if (lzx->intel_filesize) lzx->intel_curpos += frame_size; |
| 844 |
} |
| 845 |
lzx->o_end = &lzx->o_ptr[frame_size]; |
| 846 |
|
| 847 |
/* write a frame */ |
| 848 |
i = (out_bytes < (off_t)frame_size) ? (unsigned int)out_bytes : frame_size; |
| 849 |
if (fwrite(lzx->o_ptr, 1, i, lzx->output) != i) { |
| 850 |
return lzx->error = LZX_ERR_WRITE; |
| 851 |
} |
| 852 |
lzx->o_ptr += i; |
| 853 |
lzx->offset += i; |
| 854 |
out_bytes -= i; |
| 855 |
|
| 856 |
/* advance frame start position */ |
| 857 |
lzx->frame_posn += frame_size; |
| 858 |
lzx->frame++; |
| 859 |
|
| 860 |
/* wrap window / frame position pointers */ |
| 861 |
if (window_posn == lzx->window_size) window_posn = 0; |
| 862 |
if (lzx->frame_posn == lzx->window_size) lzx->frame_posn = 0; |
| 863 |
|
| 864 |
} /* while (lzx->frame < end_frame) */ |
| 865 |
|
| 866 |
if (out_bytes) { |
| 867 |
D(("bytes left to output")) |
| 868 |
return lzx->error = LZX_ERR_DECRUNCH; |
| 869 |
} |
| 870 |
|
| 871 |
/* store local state */ |
| 872 |
STORE_BITS; |
| 873 |
lzx->window_posn = window_posn; |
| 874 |
lzx->R0 = R0; |
| 875 |
lzx->R1 = R1; |
| 876 |
lzx->R2 = R2; |
| 877 |
|
| 878 |
return LZX_ERR_OK; |
| 879 |
} |
| 880 |
|
| 881 |
void ews_lzxd_free(struct lzxd_stream *lzx) { |
| 882 |
if (lzx) { |
| 883 |
free(lzx->inbuf); |
| 884 |
free(lzx->window); |
| 885 |
free(lzx); |
| 886 |
} |
| 887 |
} |