GNU Linux-libre 6.1.86-gnu
[releases.git] / fs / ntfs3 / lib / lzx_decompress.c
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
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  */
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.  */
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.  */
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.  */
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.  */
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  */
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  */
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.  */
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  */
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  */
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  */
667 void lzx_free_decompressor(struct lzx_decompressor *decompressor)
668 {
669         kfree(decompressor);
670 }