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_LEN_HEADERS (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_extra_offset_bits[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
undo_e8_translation(void * target,s32 input_pos)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(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(rel_offset, 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(rel_offset, 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 */
lzx_postprocess(u8 * data,u32 size)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(p + 1, p - data);
201 p += 5;
202 }
203 memcpy(tail, saved_bytes, 6);
204 }
205
206 /* Read a Huffman-encoded symbol using the precode. */
read_presym(const struct lzx_decompressor * d,struct input_bitstream * is)207 static forceinline u32 read_presym(const struct lzx_decompressor *d,
208 struct input_bitstream *is)
209 {
210 return read_huffsym(is, 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. */
read_mainsym(const struct lzx_decompressor * d,struct input_bitstream * is)215 static forceinline u32 read_mainsym(const struct lzx_decompressor *d,
216 struct input_bitstream *is)
217 {
218 return read_huffsym(is, 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. */
read_lensym(const struct lzx_decompressor * d,struct input_bitstream * is)223 static forceinline u32 read_lensym(const struct lzx_decompressor *d,
224 struct input_bitstream *is)
225 {
226 return read_huffsym(is, 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. */
read_alignedsym(const struct lzx_decompressor * d,struct input_bitstream * is)231 static forceinline u32 read_alignedsym(const struct lzx_decompressor *d,
232 struct input_bitstream *is)
233 {
234 return read_huffsym(is, 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 */
lzx_read_codeword_lens(struct lzx_decompressor * d,struct input_bitstream * is,u8 * lens,u32 num_lens)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(d->precode_decode_table,
272 LZX_PRECODE_NUM_SYMBOLS,
273 LZX_PRECODE_TABLEBITS,
274 d->precode_lens,
275 LZX_MAX_PRE_CODEWORD_LEN,
276 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, 4);
300 len = 0;
301 } else if (presym == 18) {
302 /* Longer run of 0's */
303 run_len = 20 + bitstream_read_bits(is, 5);
304 len = 0;
305 } else {
306 /* Run of identical lengths */
307 run_len = 4 + bitstream_read_bits(is, 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 */
lzx_read_block_header(struct lzx_decompressor * d,struct input_bitstream * is,int * block_type_ret,u32 * block_size_ret,u32 recent_offsets[])345 static int lzx_read_block_header(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, 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, 3);
361
362 /* Read the block size. */
363 if (bitstream_pop_bits(is, 1)) {
364 block_size = LZX_DEFAULT_BLOCK_SIZE;
365 } else {
366 block_size = 0;
367 block_size |= bitstream_read_bits(is, 8);
368 block_size <<= 8;
369 block_size |= bitstream_read_bits(is, 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(d->alignedcode_decode_table,
386 LZX_ALIGNEDCODE_NUM_SYMBOLS,
387 LZX_ALIGNEDCODE_TABLEBITS,
388 d->alignedcode_lens,
389 LZX_MAX_ALIGNED_CODEWORD_LEN,
390 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, d->maincode_lens,
408 LZX_NUM_CHARS))
409 return -1;
410
411 if (lzx_read_codeword_lens(d, is,
412 d->maincode_lens + LZX_NUM_CHARS,
413 LZX_MAINCODE_NUM_SYMBOLS - LZX_NUM_CHARS))
414 return -1;
415
416 if (make_huffman_decode_table(d->maincode_decode_table,
417 LZX_MAINCODE_NUM_SYMBOLS,
418 LZX_MAINCODE_TABLEBITS,
419 d->maincode_lens,
420 LZX_MAX_MAIN_CODEWORD_LEN,
421 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, d->lencode_lens,
427 LZX_LENCODE_NUM_SYMBOLS))
428 return -1;
429
430 if (make_huffman_decode_table(d->lencode_decode_table,
431 LZX_LENCODE_NUM_SYMBOLS,
432 LZX_LENCODE_TABLEBITS,
433 d->lencode_lens,
434 LZX_MAX_LEN_CODEWORD_LEN,
435 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, 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. */
lzx_decompress_block(const struct lzx_decompressor * d,struct input_bitstream * is,int block_type,u32 block_size,u8 * const out_begin,u8 * out_next,u32 recent_offsets[])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 num_extra_bits;
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_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_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(out_next, match_len, match_offset,
561 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 */
lzx_allocate_decompressor(void)574 struct lzx_decompressor *lzx_allocate_decompressor(void)
575 {
576 return kmalloc(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 */
lzx_decompress(struct lzx_decompressor * decompressor,const void * compressed_data,size_t compressed_size,void * uncompressed_data,size_t uncompressed_size)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, compressed_data, 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, &block_type, &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,
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, out_next,
640 block_size);
641 if (!out_next)
642 goto invalid;
643
644 if (block_size & 1)
645 bitstream_read_byte(&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(uncompressed_data, 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 */
lzx_free_decompressor(struct lzx_decompressor * decompressor)667 void lzx_free_decompressor(struct lzx_decompressor *decompressor)
668 {
669 kfree(decompressor);
670 }
671