1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* |
3 | * lzx_decompress.c - A decompressor for the LZX compression format, which can |
4 | * be used in "System Compressed" files. This is based on the code from wimlib. |
5 | * This code only supports a window size (dictionary size) of 32768 bytes, since |
6 | * this is the only size used in System Compression. |
7 | * |
8 | * Copyright (C) 2015 Eric Biggers |
9 | */ |
10 | |
11 | #include "decompress_common.h" |
12 | #include "lib.h" |
13 | |
14 | /* Number of literal byte values */ |
15 | #define LZX_NUM_CHARS 256 |
16 | |
17 | /* The smallest and largest allowed match lengths */ |
18 | #define LZX_MIN_MATCH_LEN 2 |
19 | #define LZX_MAX_MATCH_LEN 257 |
20 | |
21 | /* Number of distinct match lengths that can be represented */ |
22 | #define LZX_NUM_LENS (LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1) |
23 | |
24 | /* Number of match lengths for which no length symbol is required */ |
25 | #define LZX_NUM_PRIMARY_LENS 7 |
26 | #define (LZX_NUM_PRIMARY_LENS + 1) |
27 | |
28 | /* Valid values of the 3-bit block type field */ |
29 | #define LZX_BLOCKTYPE_VERBATIM 1 |
30 | #define LZX_BLOCKTYPE_ALIGNED 2 |
31 | #define LZX_BLOCKTYPE_UNCOMPRESSED 3 |
32 | |
33 | /* Number of offset slots for a window size of 32768 */ |
34 | #define LZX_NUM_OFFSET_SLOTS 30 |
35 | |
36 | /* Number of symbols in the main code for a window size of 32768 */ |
37 | #define LZX_MAINCODE_NUM_SYMBOLS \ |
38 | (LZX_NUM_CHARS + (LZX_NUM_OFFSET_SLOTS * LZX_NUM_LEN_HEADERS)) |
39 | |
40 | /* Number of symbols in the length code */ |
41 | #define LZX_LENCODE_NUM_SYMBOLS (LZX_NUM_LENS - LZX_NUM_PRIMARY_LENS) |
42 | |
43 | /* Number of symbols in the precode */ |
44 | #define LZX_PRECODE_NUM_SYMBOLS 20 |
45 | |
46 | /* Number of bits in which each precode codeword length is represented */ |
47 | #define LZX_PRECODE_ELEMENT_SIZE 4 |
48 | |
49 | /* Number of low-order bits of each match offset that are entropy-encoded in |
50 | * aligned offset blocks |
51 | */ |
52 | #define LZX_NUM_ALIGNED_OFFSET_BITS 3 |
53 | |
54 | /* Number of symbols in the aligned offset code */ |
55 | #define LZX_ALIGNEDCODE_NUM_SYMBOLS (1 << LZX_NUM_ALIGNED_OFFSET_BITS) |
56 | |
57 | /* Mask for the match offset bits that are entropy-encoded in aligned offset |
58 | * blocks |
59 | */ |
60 | #define LZX_ALIGNED_OFFSET_BITMASK ((1 << LZX_NUM_ALIGNED_OFFSET_BITS) - 1) |
61 | |
62 | /* Number of bits in which each aligned offset codeword length is represented */ |
63 | #define LZX_ALIGNEDCODE_ELEMENT_SIZE 3 |
64 | |
65 | /* Maximum lengths (in bits) of the codewords in each Huffman code */ |
66 | #define LZX_MAX_MAIN_CODEWORD_LEN 16 |
67 | #define LZX_MAX_LEN_CODEWORD_LEN 16 |
68 | #define LZX_MAX_PRE_CODEWORD_LEN ((1 << LZX_PRECODE_ELEMENT_SIZE) - 1) |
69 | #define LZX_MAX_ALIGNED_CODEWORD_LEN ((1 << LZX_ALIGNEDCODE_ELEMENT_SIZE) - 1) |
70 | |
71 | /* The default "filesize" value used in pre/post-processing. In the LZX format |
72 | * used in cabinet files this value must be given to the decompressor, whereas |
73 | * in the LZX format used in WIM files and system-compressed files this value is |
74 | * fixed at 12000000. |
75 | */ |
76 | #define LZX_DEFAULT_FILESIZE 12000000 |
77 | |
78 | /* Assumed block size when the encoded block size begins with a 0 bit. */ |
79 | #define LZX_DEFAULT_BLOCK_SIZE 32768 |
80 | |
81 | /* Number of offsets in the recent (or "repeat") offsets queue. */ |
82 | #define LZX_NUM_RECENT_OFFSETS 3 |
83 | |
84 | /* These values are chosen for fast decompression. */ |
85 | #define LZX_MAINCODE_TABLEBITS 11 |
86 | #define LZX_LENCODE_TABLEBITS 10 |
87 | #define LZX_PRECODE_TABLEBITS 6 |
88 | #define LZX_ALIGNEDCODE_TABLEBITS 7 |
89 | |
90 | #define LZX_READ_LENS_MAX_OVERRUN 50 |
91 | |
92 | /* Mapping: offset slot => first match offset that uses that offset slot. |
93 | */ |
94 | static const u32 lzx_offset_slot_base[LZX_NUM_OFFSET_SLOTS + 1] = { |
95 | 0, 1, 2, 3, 4, /* 0 --- 4 */ |
96 | 6, 8, 12, 16, 24, /* 5 --- 9 */ |
97 | 32, 48, 64, 96, 128, /* 10 --- 14 */ |
98 | 192, 256, 384, 512, 768, /* 15 --- 19 */ |
99 | 1024, 1536, 2048, 3072, 4096, /* 20 --- 24 */ |
100 | 6144, 8192, 12288, 16384, 24576, /* 25 --- 29 */ |
101 | 32768, /* extra */ |
102 | }; |
103 | |
104 | /* Mapping: offset slot => how many extra bits must be read and added to the |
105 | * corresponding offset slot base to decode the match offset. |
106 | */ |
107 | static const u8 [LZX_NUM_OFFSET_SLOTS] = { |
108 | 0, 0, 0, 0, 1, |
109 | 1, 2, 2, 3, 3, |
110 | 4, 4, 5, 5, 6, |
111 | 6, 7, 7, 8, 8, |
112 | 9, 9, 10, 10, 11, |
113 | 11, 12, 12, 13, 13, |
114 | }; |
115 | |
116 | /* Reusable heap-allocated memory for LZX decompression */ |
117 | struct lzx_decompressor { |
118 | |
119 | /* Huffman decoding tables, and arrays that map symbols to codeword |
120 | * lengths |
121 | */ |
122 | |
123 | u16 maincode_decode_table[(1 << LZX_MAINCODE_TABLEBITS) + |
124 | (LZX_MAINCODE_NUM_SYMBOLS * 2)]; |
125 | u8 maincode_lens[LZX_MAINCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN]; |
126 | |
127 | |
128 | u16 lencode_decode_table[(1 << LZX_LENCODE_TABLEBITS) + |
129 | (LZX_LENCODE_NUM_SYMBOLS * 2)]; |
130 | u8 lencode_lens[LZX_LENCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN]; |
131 | |
132 | |
133 | u16 alignedcode_decode_table[(1 << LZX_ALIGNEDCODE_TABLEBITS) + |
134 | (LZX_ALIGNEDCODE_NUM_SYMBOLS * 2)]; |
135 | u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS]; |
136 | |
137 | u16 precode_decode_table[(1 << LZX_PRECODE_TABLEBITS) + |
138 | (LZX_PRECODE_NUM_SYMBOLS * 2)]; |
139 | u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS]; |
140 | |
141 | /* Temporary space for make_huffman_decode_table() */ |
142 | u16 working_space[2 * (1 + LZX_MAX_MAIN_CODEWORD_LEN) + |
143 | LZX_MAINCODE_NUM_SYMBOLS]; |
144 | }; |
145 | |
146 | static void undo_e8_translation(void *target, s32 input_pos) |
147 | { |
148 | s32 abs_offset, rel_offset; |
149 | |
150 | abs_offset = get_unaligned_le32(p: target); |
151 | if (abs_offset >= 0) { |
152 | if (abs_offset < LZX_DEFAULT_FILESIZE) { |
153 | /* "good translation" */ |
154 | rel_offset = abs_offset - input_pos; |
155 | put_unaligned_le32(val: rel_offset, p: target); |
156 | } |
157 | } else { |
158 | if (abs_offset >= -input_pos) { |
159 | /* "compensating translation" */ |
160 | rel_offset = abs_offset + LZX_DEFAULT_FILESIZE; |
161 | put_unaligned_le32(val: rel_offset, p: target); |
162 | } |
163 | } |
164 | } |
165 | |
166 | /* |
167 | * Undo the 'E8' preprocessing used in LZX. Before compression, the |
168 | * uncompressed data was preprocessed by changing the targets of suspected x86 |
169 | * CALL instructions from relative offsets to absolute offsets. After |
170 | * match/literal decoding, the decompressor must undo the translation. |
171 | */ |
172 | static void lzx_postprocess(u8 *data, u32 size) |
173 | { |
174 | /* |
175 | * A worthwhile optimization is to push the end-of-buffer check into the |
176 | * relatively rare E8 case. This is possible if we replace the last six |
177 | * bytes of data with E8 bytes; then we are guaranteed to hit an E8 byte |
178 | * before reaching end-of-buffer. In addition, this scheme guarantees |
179 | * that no translation can begin following an E8 byte in the last 10 |
180 | * bytes because a 4-byte offset containing E8 as its high byte is a |
181 | * large negative number that is not valid for translation. That is |
182 | * exactly what we need. |
183 | */ |
184 | u8 *tail; |
185 | u8 saved_bytes[6]; |
186 | u8 *p; |
187 | |
188 | if (size <= 10) |
189 | return; |
190 | |
191 | tail = &data[size - 6]; |
192 | memcpy(saved_bytes, tail, 6); |
193 | memset(tail, 0xE8, 6); |
194 | p = data; |
195 | for (;;) { |
196 | while (*p != 0xE8) |
197 | p++; |
198 | if (p >= tail) |
199 | break; |
200 | undo_e8_translation(target: p + 1, input_pos: p - data); |
201 | p += 5; |
202 | } |
203 | memcpy(tail, saved_bytes, 6); |
204 | } |
205 | |
206 | /* Read a Huffman-encoded symbol using the precode. */ |
207 | static forceinline u32 read_presym(const struct lzx_decompressor *d, |
208 | struct input_bitstream *is) |
209 | { |
210 | return read_huffsym(istream: is, decode_table: d->precode_decode_table, |
211 | LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN); |
212 | } |
213 | |
214 | /* Read a Huffman-encoded symbol using the main code. */ |
215 | static forceinline u32 read_mainsym(const struct lzx_decompressor *d, |
216 | struct input_bitstream *is) |
217 | { |
218 | return read_huffsym(istream: is, decode_table: d->maincode_decode_table, |
219 | LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN); |
220 | } |
221 | |
222 | /* Read a Huffman-encoded symbol using the length code. */ |
223 | static forceinline u32 read_lensym(const struct lzx_decompressor *d, |
224 | struct input_bitstream *is) |
225 | { |
226 | return read_huffsym(istream: is, decode_table: d->lencode_decode_table, |
227 | LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN); |
228 | } |
229 | |
230 | /* Read a Huffman-encoded symbol using the aligned offset code. */ |
231 | static forceinline u32 read_alignedsym(const struct lzx_decompressor *d, |
232 | struct input_bitstream *is) |
233 | { |
234 | return read_huffsym(istream: is, decode_table: d->alignedcode_decode_table, |
235 | LZX_ALIGNEDCODE_TABLEBITS, |
236 | LZX_MAX_ALIGNED_CODEWORD_LEN); |
237 | } |
238 | |
239 | /* |
240 | * Read the precode from the compressed input bitstream, then use it to decode |
241 | * @num_lens codeword length values. |
242 | * |
243 | * @is: The input bitstream. |
244 | * |
245 | * @lens: An array that contains the length values from the previous time |
246 | * the codeword lengths for this Huffman code were read, or all 0's |
247 | * if this is the first time. This array must have at least |
248 | * (@num_lens + LZX_READ_LENS_MAX_OVERRUN) entries. |
249 | * |
250 | * @num_lens: Number of length values to decode. |
251 | * |
252 | * Returns 0 on success, or -1 if the data was invalid. |
253 | */ |
254 | static int lzx_read_codeword_lens(struct lzx_decompressor *d, |
255 | struct input_bitstream *is, |
256 | u8 *lens, u32 num_lens) |
257 | { |
258 | u8 *len_ptr = lens; |
259 | u8 *lens_end = lens + num_lens; |
260 | int i; |
261 | |
262 | /* Read the lengths of the precode codewords. These are given |
263 | * explicitly. |
264 | */ |
265 | for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++) { |
266 | d->precode_lens[i] = |
267 | bitstream_read_bits(is, LZX_PRECODE_ELEMENT_SIZE); |
268 | } |
269 | |
270 | /* Make the decoding table for the precode. */ |
271 | if (make_huffman_decode_table(decode_table: d->precode_decode_table, |
272 | LZX_PRECODE_NUM_SYMBOLS, |
273 | LZX_PRECODE_TABLEBITS, |
274 | lens: d->precode_lens, |
275 | LZX_MAX_PRE_CODEWORD_LEN, |
276 | working_space: d->working_space)) |
277 | return -1; |
278 | |
279 | /* Decode the codeword lengths. */ |
280 | do { |
281 | u32 presym; |
282 | u8 len; |
283 | |
284 | /* Read the next precode symbol. */ |
285 | presym = read_presym(d, is); |
286 | if (presym < 17) { |
287 | /* Difference from old length */ |
288 | len = *len_ptr - presym; |
289 | if ((s8)len < 0) |
290 | len += 17; |
291 | *len_ptr++ = len; |
292 | } else { |
293 | /* Special RLE values */ |
294 | |
295 | u32 run_len; |
296 | |
297 | if (presym == 17) { |
298 | /* Run of 0's */ |
299 | run_len = 4 + bitstream_read_bits(is, num_bits: 4); |
300 | len = 0; |
301 | } else if (presym == 18) { |
302 | /* Longer run of 0's */ |
303 | run_len = 20 + bitstream_read_bits(is, num_bits: 5); |
304 | len = 0; |
305 | } else { |
306 | /* Run of identical lengths */ |
307 | run_len = 4 + bitstream_read_bits(is, num_bits: 1); |
308 | presym = read_presym(d, is); |
309 | if (presym > 17) |
310 | return -1; |
311 | len = *len_ptr - presym; |
312 | if ((s8)len < 0) |
313 | len += 17; |
314 | } |
315 | |
316 | do { |
317 | *len_ptr++ = len; |
318 | } while (--run_len); |
319 | /* Worst case overrun is when presym == 18, |
320 | * run_len == 20 + 31, and only 1 length was remaining. |
321 | * So LZX_READ_LENS_MAX_OVERRUN == 50. |
322 | * |
323 | * Overrun while reading the first half of maincode_lens |
324 | * can corrupt the previous values in the second half. |
325 | * This doesn't really matter because the resulting |
326 | * lengths will still be in range, and data that |
327 | * generates overruns is invalid anyway. |
328 | */ |
329 | } |
330 | } while (len_ptr < lens_end); |
331 | |
332 | return 0; |
333 | } |
334 | |
335 | /* |
336 | * Read the header of an LZX block and save the block type and (uncompressed) |
337 | * size in *block_type_ret and *block_size_ret, respectively. |
338 | * |
339 | * If the block is compressed, also update the Huffman decode @tables with the |
340 | * new Huffman codes. If the block is uncompressed, also update the match |
341 | * offset @queue with the new match offsets. |
342 | * |
343 | * Return 0 on success, or -1 if the data was invalid. |
344 | */ |
345 | static int (struct lzx_decompressor *d, |
346 | struct input_bitstream *is, |
347 | int *block_type_ret, |
348 | u32 *block_size_ret, |
349 | u32 recent_offsets[]) |
350 | { |
351 | int block_type; |
352 | u32 block_size; |
353 | int i; |
354 | |
355 | bitstream_ensure_bits(is, num_bits: 4); |
356 | |
357 | /* The first three bits tell us what kind of block it is, and should be |
358 | * one of the LZX_BLOCKTYPE_* values. |
359 | */ |
360 | block_type = bitstream_pop_bits(is, num_bits: 3); |
361 | |
362 | /* Read the block size. */ |
363 | if (bitstream_pop_bits(is, num_bits: 1)) { |
364 | block_size = LZX_DEFAULT_BLOCK_SIZE; |
365 | } else { |
366 | block_size = 0; |
367 | block_size |= bitstream_read_bits(is, num_bits: 8); |
368 | block_size <<= 8; |
369 | block_size |= bitstream_read_bits(is, num_bits: 8); |
370 | } |
371 | |
372 | switch (block_type) { |
373 | |
374 | case LZX_BLOCKTYPE_ALIGNED: |
375 | |
376 | /* Read the aligned offset code and prepare its decode table. |
377 | */ |
378 | |
379 | for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) { |
380 | d->alignedcode_lens[i] = |
381 | bitstream_read_bits(is, |
382 | LZX_ALIGNEDCODE_ELEMENT_SIZE); |
383 | } |
384 | |
385 | if (make_huffman_decode_table(decode_table: d->alignedcode_decode_table, |
386 | LZX_ALIGNEDCODE_NUM_SYMBOLS, |
387 | LZX_ALIGNEDCODE_TABLEBITS, |
388 | lens: d->alignedcode_lens, |
389 | LZX_MAX_ALIGNED_CODEWORD_LEN, |
390 | working_space: d->working_space)) |
391 | return -1; |
392 | |
393 | /* Fall though, since the rest of the header for aligned offset |
394 | * blocks is the same as that for verbatim blocks. |
395 | */ |
396 | fallthrough; |
397 | |
398 | case LZX_BLOCKTYPE_VERBATIM: |
399 | |
400 | /* Read the main code and prepare its decode table. |
401 | * |
402 | * Note that the codeword lengths in the main code are encoded |
403 | * in two parts: one part for literal symbols, and one part for |
404 | * match symbols. |
405 | */ |
406 | |
407 | if (lzx_read_codeword_lens(d, is, lens: d->maincode_lens, |
408 | LZX_NUM_CHARS)) |
409 | return -1; |
410 | |
411 | if (lzx_read_codeword_lens(d, is, |
412 | lens: d->maincode_lens + LZX_NUM_CHARS, |
413 | LZX_MAINCODE_NUM_SYMBOLS - LZX_NUM_CHARS)) |
414 | return -1; |
415 | |
416 | if (make_huffman_decode_table(decode_table: d->maincode_decode_table, |
417 | LZX_MAINCODE_NUM_SYMBOLS, |
418 | LZX_MAINCODE_TABLEBITS, |
419 | lens: d->maincode_lens, |
420 | LZX_MAX_MAIN_CODEWORD_LEN, |
421 | working_space: d->working_space)) |
422 | return -1; |
423 | |
424 | /* Read the length code and prepare its decode table. */ |
425 | |
426 | if (lzx_read_codeword_lens(d, is, lens: d->lencode_lens, |
427 | LZX_LENCODE_NUM_SYMBOLS)) |
428 | return -1; |
429 | |
430 | if (make_huffman_decode_table(decode_table: d->lencode_decode_table, |
431 | LZX_LENCODE_NUM_SYMBOLS, |
432 | LZX_LENCODE_TABLEBITS, |
433 | lens: d->lencode_lens, |
434 | LZX_MAX_LEN_CODEWORD_LEN, |
435 | working_space: d->working_space)) |
436 | return -1; |
437 | |
438 | break; |
439 | |
440 | case LZX_BLOCKTYPE_UNCOMPRESSED: |
441 | |
442 | /* Before reading the three recent offsets from the uncompressed |
443 | * block header, the stream must be aligned on a 16-bit |
444 | * boundary. But if the stream is *already* aligned, then the |
445 | * next 16 bits must be discarded. |
446 | */ |
447 | bitstream_ensure_bits(is, num_bits: 1); |
448 | bitstream_align(is); |
449 | |
450 | recent_offsets[0] = bitstream_read_u32(is); |
451 | recent_offsets[1] = bitstream_read_u32(is); |
452 | recent_offsets[2] = bitstream_read_u32(is); |
453 | |
454 | /* Offsets of 0 are invalid. */ |
455 | if (recent_offsets[0] == 0 || recent_offsets[1] == 0 || |
456 | recent_offsets[2] == 0) |
457 | return -1; |
458 | break; |
459 | |
460 | default: |
461 | /* Unrecognized block type. */ |
462 | return -1; |
463 | } |
464 | |
465 | *block_type_ret = block_type; |
466 | *block_size_ret = block_size; |
467 | return 0; |
468 | } |
469 | |
470 | /* Decompress a block of LZX-compressed data. */ |
471 | static int lzx_decompress_block(const struct lzx_decompressor *d, |
472 | struct input_bitstream *is, |
473 | int block_type, u32 block_size, |
474 | u8 * const out_begin, u8 *out_next, |
475 | u32 recent_offsets[]) |
476 | { |
477 | u8 * const block_end = out_next + block_size; |
478 | u32 ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED); |
479 | |
480 | do { |
481 | u32 mainsym; |
482 | u32 match_len; |
483 | u32 match_offset; |
484 | u32 offset_slot; |
485 | u32 ; |
486 | |
487 | mainsym = read_mainsym(d, is); |
488 | if (mainsym < LZX_NUM_CHARS) { |
489 | /* Literal */ |
490 | *out_next++ = mainsym; |
491 | continue; |
492 | } |
493 | |
494 | /* Match */ |
495 | |
496 | /* Decode the length header and offset slot. */ |
497 | mainsym -= LZX_NUM_CHARS; |
498 | match_len = mainsym % LZX_NUM_LEN_HEADERS; |
499 | offset_slot = mainsym / LZX_NUM_LEN_HEADERS; |
500 | |
501 | /* If needed, read a length symbol to decode the full length. */ |
502 | if (match_len == LZX_NUM_PRIMARY_LENS) |
503 | match_len += read_lensym(d, is); |
504 | match_len += LZX_MIN_MATCH_LEN; |
505 | |
506 | if (offset_slot < LZX_NUM_RECENT_OFFSETS) { |
507 | /* Repeat offset */ |
508 | |
509 | /* Note: This isn't a real LRU queue, since using the R2 |
510 | * offset doesn't bump the R1 offset down to R2. This |
511 | * quirk allows all 3 recent offsets to be handled by |
512 | * the same code. (For R0, the swap is a no-op.) |
513 | */ |
514 | match_offset = recent_offsets[offset_slot]; |
515 | recent_offsets[offset_slot] = recent_offsets[0]; |
516 | recent_offsets[0] = match_offset; |
517 | } else { |
518 | /* Explicit offset */ |
519 | |
520 | /* Look up the number of extra bits that need to be read |
521 | * to decode offsets with this offset slot. |
522 | */ |
523 | num_extra_bits = lzx_extra_offset_bits[offset_slot]; |
524 | |
525 | /* Start with the offset slot base value. */ |
526 | match_offset = lzx_offset_slot_base[offset_slot]; |
527 | |
528 | /* In aligned offset blocks, the low-order 3 bits of |
529 | * each offset are encoded using the aligned offset |
530 | * code. Otherwise, all the extra bits are literal. |
531 | */ |
532 | |
533 | if ((num_extra_bits & ones_if_aligned) >= LZX_NUM_ALIGNED_OFFSET_BITS) { |
534 | match_offset += |
535 | bitstream_read_bits(is, num_bits: num_extra_bits - |
536 | LZX_NUM_ALIGNED_OFFSET_BITS) |
537 | << LZX_NUM_ALIGNED_OFFSET_BITS; |
538 | match_offset += read_alignedsym(d, is); |
539 | } else { |
540 | match_offset += bitstream_read_bits(is, num_bits: num_extra_bits); |
541 | } |
542 | |
543 | /* Adjust the offset. */ |
544 | match_offset -= (LZX_NUM_RECENT_OFFSETS - 1); |
545 | |
546 | /* Update the recent offsets. */ |
547 | recent_offsets[2] = recent_offsets[1]; |
548 | recent_offsets[1] = recent_offsets[0]; |
549 | recent_offsets[0] = match_offset; |
550 | } |
551 | |
552 | /* Validate the match, then copy it to the current position. */ |
553 | |
554 | if (match_len > (size_t)(block_end - out_next)) |
555 | return -1; |
556 | |
557 | if (match_offset > (size_t)(out_next - out_begin)) |
558 | return -1; |
559 | |
560 | out_next = lz_copy(dst: out_next, length: match_len, offset: match_offset, |
561 | bufend: block_end, LZX_MIN_MATCH_LEN); |
562 | |
563 | } while (out_next != block_end); |
564 | |
565 | return 0; |
566 | } |
567 | |
568 | /* |
569 | * lzx_allocate_decompressor - Allocate an LZX decompressor |
570 | * |
571 | * Return the pointer to the decompressor on success, or return NULL and set |
572 | * errno on failure. |
573 | */ |
574 | struct lzx_decompressor *lzx_allocate_decompressor(void) |
575 | { |
576 | return kmalloc(size: sizeof(struct lzx_decompressor), GFP_NOFS); |
577 | } |
578 | |
579 | /* |
580 | * lzx_decompress - Decompress a buffer of LZX-compressed data |
581 | * |
582 | * @decompressor: A decompressor allocated with lzx_allocate_decompressor() |
583 | * @compressed_data: The buffer of data to decompress |
584 | * @compressed_size: Number of bytes of compressed data |
585 | * @uncompressed_data: The buffer in which to store the decompressed data |
586 | * @uncompressed_size: The number of bytes the data decompresses into |
587 | * |
588 | * Return 0 on success, or return -1 and set errno on failure. |
589 | */ |
590 | int lzx_decompress(struct lzx_decompressor *decompressor, |
591 | const void *compressed_data, size_t compressed_size, |
592 | void *uncompressed_data, size_t uncompressed_size) |
593 | { |
594 | struct lzx_decompressor *d = decompressor; |
595 | u8 * const out_begin = uncompressed_data; |
596 | u8 *out_next = out_begin; |
597 | u8 * const out_end = out_begin + uncompressed_size; |
598 | struct input_bitstream is; |
599 | u32 recent_offsets[LZX_NUM_RECENT_OFFSETS] = {1, 1, 1}; |
600 | int e8_status = 0; |
601 | |
602 | init_input_bitstream(is: &is, buffer: compressed_data, size: compressed_size); |
603 | |
604 | /* Codeword lengths begin as all 0's for delta encoding purposes. */ |
605 | memset(d->maincode_lens, 0, LZX_MAINCODE_NUM_SYMBOLS); |
606 | memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS); |
607 | |
608 | /* Decompress blocks until we have all the uncompressed data. */ |
609 | |
610 | while (out_next != out_end) { |
611 | int block_type; |
612 | u32 block_size; |
613 | |
614 | if (lzx_read_block_header(d, is: &is, block_type_ret: &block_type, block_size_ret: &block_size, |
615 | recent_offsets)) |
616 | goto invalid; |
617 | |
618 | if (block_size < 1 || block_size > (size_t)(out_end - out_next)) |
619 | goto invalid; |
620 | |
621 | if (block_type != LZX_BLOCKTYPE_UNCOMPRESSED) { |
622 | |
623 | /* Compressed block */ |
624 | |
625 | if (lzx_decompress_block(d, |
626 | is: &is, |
627 | block_type, |
628 | block_size, |
629 | out_begin, |
630 | out_next, |
631 | recent_offsets)) |
632 | goto invalid; |
633 | |
634 | e8_status |= d->maincode_lens[0xe8]; |
635 | out_next += block_size; |
636 | } else { |
637 | /* Uncompressed block */ |
638 | |
639 | out_next = bitstream_read_bytes(is: &is, dst_buffer: out_next, |
640 | count: block_size); |
641 | if (!out_next) |
642 | goto invalid; |
643 | |
644 | if (block_size & 1) |
645 | bitstream_read_byte(is: &is); |
646 | |
647 | e8_status = 1; |
648 | } |
649 | } |
650 | |
651 | /* Postprocess the data unless it cannot possibly contain 0xe8 bytes. */ |
652 | if (e8_status) |
653 | lzx_postprocess(data: uncompressed_data, size: uncompressed_size); |
654 | |
655 | return 0; |
656 | |
657 | invalid: |
658 | return -1; |
659 | } |
660 | |
661 | /* |
662 | * lzx_free_decompressor - Free an LZX decompressor |
663 | * |
664 | * @decompressor: A decompressor that was allocated with |
665 | * lzx_allocate_decompressor(), or NULL. |
666 | */ |
667 | void lzx_free_decompressor(struct lzx_decompressor *decompressor) |
668 | { |
669 | kfree(objp: decompressor); |
670 | } |
671 | |