ntfs3/lib/lzx_decompress.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  * lzx_decompress.c - A decompressor for the LZX compression format, which can
0004  * be used in "System Compressed" files.  This is based on the code from wimlib.
0005  * This code only supports a window size (dictionary size) of 32768 bytes, since
0006  * this is the only size used in System Compression.
0007  *
0008  * Copyright (C) 2015 Eric Biggers
0009  */
0010
0011 #include "decompress_common.h"
0012 #include "lib.h"
0013
0014 /* Number of literal byte values  */
0015 #define LZX_NUM_CHARS           256
0016
0017 /* The smallest and largest allowed match lengths  */
0018 #define LZX_MIN_MATCH_LEN       2
0019 #define LZX_MAX_MATCH_LEN       257
0020
0021 /* Number of distinct match lengths that can be represented  */
0022 #define LZX_NUM_LENS            (LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1)
0023
0024 /* Number of match lengths for which no length symbol is required  */
0025 #define LZX_NUM_PRIMARY_LENS        7
0026 #define LZX_NUM_LEN_HEADERS     (LZX_NUM_PRIMARY_LENS + 1)
0027
0028 /* Valid values of the 3-bit block type field  */
0029 #define LZX_BLOCKTYPE_VERBATIM      1
0030 #define LZX_BLOCKTYPE_ALIGNED       2
0031 #define LZX_BLOCKTYPE_UNCOMPRESSED  3
0032
0033 /* Number of offset slots for a window size of 32768  */
0034 #define LZX_NUM_OFFSET_SLOTS        30
0035
0036 /* Number of symbols in the main code for a window size of 32768  */
0037 #define LZX_MAINCODE_NUM_SYMBOLS    \
0038     (LZX_NUM_CHARS + (LZX_NUM_OFFSET_SLOTS * LZX_NUM_LEN_HEADERS))
0039
0040 /* Number of symbols in the length code  */
0041 #define LZX_LENCODE_NUM_SYMBOLS     (LZX_NUM_LENS - LZX_NUM_PRIMARY_LENS)
0042
0043 /* Number of symbols in the precode  */
0044 #define LZX_PRECODE_NUM_SYMBOLS     20
0045
0046 /* Number of bits in which each precode codeword length is represented  */
0047 #define LZX_PRECODE_ELEMENT_SIZE    4
0048
0049 /* Number of low-order bits of each match offset that are entropy-encoded in
0050  * aligned offset blocks
0051  */
0052 #define LZX_NUM_ALIGNED_OFFSET_BITS 3
0053
0054 /* Number of symbols in the aligned offset code  */
0055 #define LZX_ALIGNEDCODE_NUM_SYMBOLS (1 << LZX_NUM_ALIGNED_OFFSET_BITS)
0056
0057 /* Mask for the match offset bits that are entropy-encoded in aligned offset
0058  * blocks
0059  */
0060 #define LZX_ALIGNED_OFFSET_BITMASK  ((1 << LZX_NUM_ALIGNED_OFFSET_BITS) - 1)
0061
0062 /* Number of bits in which each aligned offset codeword length is represented  */
0063 #define LZX_ALIGNEDCODE_ELEMENT_SIZE    3
0064
0065 /* Maximum lengths (in bits) of the codewords in each Huffman code  */
0066 #define LZX_MAX_MAIN_CODEWORD_LEN   16
0067 #define LZX_MAX_LEN_CODEWORD_LEN    16
0068 #define LZX_MAX_PRE_CODEWORD_LEN    ((1 << LZX_PRECODE_ELEMENT_SIZE) - 1)
0069 #define LZX_MAX_ALIGNED_CODEWORD_LEN    ((1 << LZX_ALIGNEDCODE_ELEMENT_SIZE) - 1)
0070
0071 /* The default "filesize" value used in pre/post-processing.  In the LZX format
0072  * used in cabinet files this value must be given to the decompressor, whereas
0073  * in the LZX format used in WIM files and system-compressed files this value is
0074  * fixed at 12000000.
0075  */
0076 #define LZX_DEFAULT_FILESIZE        12000000
0077
0078 /* Assumed block size when the encoded block size begins with a 0 bit.  */
0079 #define LZX_DEFAULT_BLOCK_SIZE      32768
0080
0081 /* Number of offsets in the recent (or "repeat") offsets queue.  */
0082 #define LZX_NUM_RECENT_OFFSETS      3
0083
0084 /* These values are chosen for fast decompression.  */
0085 #define LZX_MAINCODE_TABLEBITS      11
0086 #define LZX_LENCODE_TABLEBITS       10
0087 #define LZX_PRECODE_TABLEBITS       6
0088 #define LZX_ALIGNEDCODE_TABLEBITS   7
0089
0090 #define LZX_READ_LENS_MAX_OVERRUN   50
0091
0092 /* Mapping: offset slot => first match offset that uses that offset slot.
0093  */
0094 static const u32 lzx_offset_slot_base[LZX_NUM_OFFSET_SLOTS + 1] = {
0095     0,  1,  2,  3,  4,  /* 0  --- 4  */
0096     6,  8,  12, 16, 24, /* 5  --- 9  */
0097     32, 48, 64, 96, 128,    /* 10 --- 14 */
0098     192,    256,    384,    512,    768,    /* 15 --- 19 */
0099     1024,   1536,   2048,   3072,   4096,   /* 20 --- 24 */
0100     6144,   8192,   12288,  16384,  24576,  /* 25 --- 29 */
0101     32768,                  /* extra     */
0102 };
0103
0104 /* Mapping: offset slot => how many extra bits must be read and added to the
0105  * corresponding offset slot base to decode the match offset.
0106  */
0107 static const u8 lzx_extra_offset_bits[LZX_NUM_OFFSET_SLOTS] = {
0108     0,  0,  0,  0,  1,
0109     1,  2,  2,  3,  3,
0110     4,  4,  5,  5,  6,
0111     6,  7,  7,  8,  8,
0112     9,  9,  10, 10, 11,
0113     11, 12, 12, 13, 13,
0114 };
0115
0116 /* Reusable heap-allocated memory for LZX decompression  */
0117 struct lzx_decompressor {
0118
0119     /* Huffman decoding tables, and arrays that map symbols to codeword
0120      * lengths
0121      */
0122
0123     u16 maincode_decode_table[(1 << LZX_MAINCODE_TABLEBITS) +
0124                     (LZX_MAINCODE_NUM_SYMBOLS * 2)];
0125     u8 maincode_lens[LZX_MAINCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
0126
0127
0128     u16 lencode_decode_table[(1 << LZX_LENCODE_TABLEBITS) +
0129                     (LZX_LENCODE_NUM_SYMBOLS * 2)];
0130     u8 lencode_lens[LZX_LENCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
0131
0132
0133     u16 alignedcode_decode_table[(1 << LZX_ALIGNEDCODE_TABLEBITS) +
0134                     (LZX_ALIGNEDCODE_NUM_SYMBOLS * 2)];
0135     u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS];
0136
0137     u16 precode_decode_table[(1 << LZX_PRECODE_TABLEBITS) +
0138                  (LZX_PRECODE_NUM_SYMBOLS * 2)];
0139     u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
0140
0141     /* Temporary space for make_huffman_decode_table()  */
0142     u16 working_space[2 * (1 + LZX_MAX_MAIN_CODEWORD_LEN) +
0143               LZX_MAINCODE_NUM_SYMBOLS];
0144 };
0145
0146 static void undo_e8_translation(void *target, s32 input_pos)
0147 {
0148     s32 abs_offset, rel_offset;
0149
0150     abs_offset = get_unaligned_le32(target);
0151     if (abs_offset >= 0) {
0152         if (abs_offset < LZX_DEFAULT_FILESIZE) {
0153             /* "good translation" */
0154             rel_offset = abs_offset - input_pos;
0155             put_unaligned_le32(rel_offset, target);
0156         }
0157     } else {
0158         if (abs_offset >= -input_pos) {
0159             /* "compensating translation" */
0160             rel_offset = abs_offset + LZX_DEFAULT_FILESIZE;
0161             put_unaligned_le32(rel_offset, target);
0162         }
0163     }
0164 }
0165
0166 /*
0167  * Undo the 'E8' preprocessing used in LZX.  Before compression, the
0168  * uncompressed data was preprocessed by changing the targets of suspected x86
0169  * CALL instructions from relative offsets to absolute offsets.  After
0170  * match/literal decoding, the decompressor must undo the translation.
0171  */
0172 static void lzx_postprocess(u8 *data, u32 size)
0173 {
0174     /*
0175      * A worthwhile optimization is to push the end-of-buffer check into the
0176      * relatively rare E8 case.  This is possible if we replace the last six
0177      * bytes of data with E8 bytes; then we are guaranteed to hit an E8 byte
0178      * before reaching end-of-buffer.  In addition, this scheme guarantees
0179      * that no translation can begin following an E8 byte in the last 10
0180      * bytes because a 4-byte offset containing E8 as its high byte is a
0181      * large negative number that is not valid for translation.  That is
0182      * exactly what we need.
0183      */
0184     u8 *tail;
0185     u8 saved_bytes[6];
0186     u8 *p;
0187
0188     if (size <= 10)
0189         return;
0190
0191     tail = &data[size - 6];
0192     memcpy(saved_bytes, tail, 6);
0193     memset(tail, 0xE8, 6);
0194     p = data;
0195     for (;;) {
0196         while (*p != 0xE8)
0197             p++;
0198         if (p >= tail)
0199             break;
0200         undo_e8_translation(p + 1, p - data);
0201         p += 5;
0202     }
0203     memcpy(tail, saved_bytes, 6);
0204 }
0205
0206 /* Read a Huffman-encoded symbol using the precode.  */
0207 static forceinline u32 read_presym(const struct lzx_decompressor *d,
0208                     struct input_bitstream *is)
0209 {
0210     return read_huffsym(is, d->precode_decode_table,
0211                 LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN);
0212 }
0213
0214 /* Read a Huffman-encoded symbol using the main code.  */
0215 static forceinline u32 read_mainsym(const struct lzx_decompressor *d,
0216                      struct input_bitstream *is)
0217 {
0218     return read_huffsym(is, d->maincode_decode_table,
0219                 LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN);
0220 }
0221
0222 /* Read a Huffman-encoded symbol using the length code.  */
0223 static forceinline u32 read_lensym(const struct lzx_decompressor *d,
0224                     struct input_bitstream *is)
0225 {
0226     return read_huffsym(is, d->lencode_decode_table,
0227                 LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN);
0228 }
0229
0230 /* Read a Huffman-encoded symbol using the aligned offset code.  */
0231 static forceinline u32 read_alignedsym(const struct lzx_decompressor *d,
0232                         struct input_bitstream *is)
0233 {
0234     return read_huffsym(is, d->alignedcode_decode_table,
0235                 LZX_ALIGNEDCODE_TABLEBITS,
0236                 LZX_MAX_ALIGNED_CODEWORD_LEN);
0237 }
0238
0239 /*
0240  * Read the precode from the compressed input bitstream, then use it to decode
0241  * @num_lens codeword length values.
0242  *
0243  * @is:     The input bitstream.
0244  *
0245  * @lens:   An array that contains the length values from the previous time
0246  *      the codeword lengths for this Huffman code were read, or all 0's
0247  *      if this is the first time.  This array must have at least
0248  *      (@num_lens + LZX_READ_LENS_MAX_OVERRUN) entries.
0249  *
0250  * @num_lens:   Number of length values to decode.
0251  *
0252  * Returns 0 on success, or -1 if the data was invalid.
0253  */
0254 static int lzx_read_codeword_lens(struct lzx_decompressor *d,
0255                   struct input_bitstream *is,
0256                   u8 *lens, u32 num_lens)
0257 {
0258     u8 *len_ptr = lens;
0259     u8 *lens_end = lens + num_lens;
0260     int i;
0261
0262     /* Read the lengths of the precode codewords.  These are given
0263      * explicitly.
0264      */
0265     for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++) {
0266         d->precode_lens[i] =
0267             bitstream_read_bits(is, LZX_PRECODE_ELEMENT_SIZE);
0268     }
0269
0270     /* Make the decoding table for the precode.  */
0271     if (make_huffman_decode_table(d->precode_decode_table,
0272                       LZX_PRECODE_NUM_SYMBOLS,
0273                       LZX_PRECODE_TABLEBITS,
0274                       d->precode_lens,
0275                       LZX_MAX_PRE_CODEWORD_LEN,
0276                       d->working_space))
0277         return -1;
0278
0279     /* Decode the codeword lengths.  */
0280     do {
0281         u32 presym;
0282         u8 len;
0283
0284         /* Read the next precode symbol.  */
0285         presym = read_presym(d, is);
0286         if (presym < 17) {
0287             /* Difference from old length  */
0288             len = *len_ptr - presym;
0289             if ((s8)len < 0)
0290                 len += 17;
0291             *len_ptr++ = len;
0292         } else {
0293             /* Special RLE values  */
0294
0295             u32 run_len;
0296
0297             if (presym == 17) {
0298                 /* Run of 0's  */
0299                 run_len = 4 + bitstream_read_bits(is, 4);
0300                 len = 0;
0301             } else if (presym == 18) {
0302                 /* Longer run of 0's  */
0303                 run_len = 20 + bitstream_read_bits(is, 5);
0304                 len = 0;
0305             } else {
0306                 /* Run of identical lengths  */
0307                 run_len = 4 + bitstream_read_bits(is, 1);
0308                 presym = read_presym(d, is);
0309                 if (presym > 17)
0310                     return -1;
0311                 len = *len_ptr - presym;
0312                 if ((s8)len < 0)
0313                     len += 17;
0314             }
0315
0316             do {
0317                 *len_ptr++ = len;
0318             } while (--run_len);
0319             /* Worst case overrun is when presym == 18,
0320              * run_len == 20 + 31, and only 1 length was remaining.
0321              * So LZX_READ_LENS_MAX_OVERRUN == 50.
0322              *
0323              * Overrun while reading the first half of maincode_lens
0324              * can corrupt the previous values in the second half.
0325              * This doesn't really matter because the resulting
0326              * lengths will still be in range, and data that
0327              * generates overruns is invalid anyway.
0328              */
0329         }
0330     } while (len_ptr < lens_end);
0331
0332     return 0;
0333 }
0334
0335 /*
0336  * Read the header of an LZX block and save the block type and (uncompressed)
0337  * size in *block_type_ret and *block_size_ret, respectively.
0338  *
0339  * If the block is compressed, also update the Huffman decode @tables with the
0340  * new Huffman codes.  If the block is uncompressed, also update the match
0341  * offset @queue with the new match offsets.
0342  *
0343  * Return 0 on success, or -1 if the data was invalid.
0344  */
0345 static int lzx_read_block_header(struct lzx_decompressor *d,
0346                  struct input_bitstream *is,
0347                  int *block_type_ret,
0348                  u32 *block_size_ret,
0349                  u32 recent_offsets[])
0350 {
0351     int block_type;
0352     u32 block_size;
0353     int i;
0354
0355     bitstream_ensure_bits(is, 4);
0356
0357     /* The first three bits tell us what kind of block it is, and should be
0358      * one of the LZX_BLOCKTYPE_* values.
0359      */
0360     block_type = bitstream_pop_bits(is, 3);
0361
0362     /* Read the block size.  */
0363     if (bitstream_pop_bits(is, 1)) {
0364         block_size = LZX_DEFAULT_BLOCK_SIZE;
0365     } else {
0366         block_size = 0;
0367         block_size |= bitstream_read_bits(is, 8);
0368         block_size <<= 8;
0369         block_size |= bitstream_read_bits(is, 8);
0370     }
0371
0372     switch (block_type) {
0373
0374     case LZX_BLOCKTYPE_ALIGNED:
0375
0376         /* Read the aligned offset code and prepare its decode table.
0377          */
0378
0379         for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
0380             d->alignedcode_lens[i] =
0381                 bitstream_read_bits(is,
0382                             LZX_ALIGNEDCODE_ELEMENT_SIZE);
0383         }
0384
0385         if (make_huffman_decode_table(d->alignedcode_decode_table,
0386                           LZX_ALIGNEDCODE_NUM_SYMBOLS,
0387                           LZX_ALIGNEDCODE_TABLEBITS,
0388                           d->alignedcode_lens,
0389                           LZX_MAX_ALIGNED_CODEWORD_LEN,
0390                           d->working_space))
0391             return -1;
0392
0393         /* Fall though, since the rest of the header for aligned offset
0394          * blocks is the same as that for verbatim blocks.
0395          */
0396         fallthrough;
0397
0398     case LZX_BLOCKTYPE_VERBATIM:
0399
0400         /* Read the main code and prepare its decode table.
0401          *
0402          * Note that the codeword lengths in the main code are encoded
0403          * in two parts: one part for literal symbols, and one part for
0404          * match symbols.
0405          */
0406
0407         if (lzx_read_codeword_lens(d, is, d->maincode_lens,
0408                        LZX_NUM_CHARS))
0409             return -1;
0410
0411         if (lzx_read_codeword_lens(d, is,
0412                        d->maincode_lens + LZX_NUM_CHARS,
0413                        LZX_MAINCODE_NUM_SYMBOLS - LZX_NUM_CHARS))
0414             return -1;
0415
0416         if (make_huffman_decode_table(d->maincode_decode_table,
0417                           LZX_MAINCODE_NUM_SYMBOLS,
0418                           LZX_MAINCODE_TABLEBITS,
0419                           d->maincode_lens,
0420                           LZX_MAX_MAIN_CODEWORD_LEN,
0421                           d->working_space))
0422             return -1;
0423
0424         /* Read the length code and prepare its decode table.  */
0425
0426         if (lzx_read_codeword_lens(d, is, d->lencode_lens,
0427                        LZX_LENCODE_NUM_SYMBOLS))
0428             return -1;
0429
0430         if (make_huffman_decode_table(d->lencode_decode_table,
0431                           LZX_LENCODE_NUM_SYMBOLS,
0432                           LZX_LENCODE_TABLEBITS,
0433                           d->lencode_lens,
0434                           LZX_MAX_LEN_CODEWORD_LEN,
0435                           d->working_space))
0436             return -1;
0437
0438         break;
0439
0440     case LZX_BLOCKTYPE_UNCOMPRESSED:
0441
0442         /* Before reading the three recent offsets from the uncompressed
0443          * block header, the stream must be aligned on a 16-bit
0444          * boundary.  But if the stream is *already* aligned, then the
0445          * next 16 bits must be discarded.
0446          */
0447         bitstream_ensure_bits(is, 1);
0448         bitstream_align(is);
0449
0450         recent_offsets[0] = bitstream_read_u32(is);
0451         recent_offsets[1] = bitstream_read_u32(is);
0452         recent_offsets[2] = bitstream_read_u32(is);
0453
0454         /* Offsets of 0 are invalid.  */
0455         if (recent_offsets[0] == 0 || recent_offsets[1] == 0 ||
0456             recent_offsets[2] == 0)
0457             return -1;
0458         break;
0459
0460     default:
0461         /* Unrecognized block type.  */
0462         return -1;
0463     }
0464
0465     *block_type_ret = block_type;
0466     *block_size_ret = block_size;
0467     return 0;
0468 }
0469
0470 /* Decompress a block of LZX-compressed data.  */
0471 static int lzx_decompress_block(const struct lzx_decompressor *d,
0472                 struct input_bitstream *is,
0473                 int block_type, u32 block_size,
0474                 u8 * const out_begin, u8 *out_next,
0475                 u32 recent_offsets[])
0476 {
0477     u8 * const block_end = out_next + block_size;
0478     u32 ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED);
0479
0480     do {
0481         u32 mainsym;
0482         u32 match_len;
0483         u32 match_offset;
0484         u32 offset_slot;
0485         u32 num_extra_bits;
0486
0487         mainsym = read_mainsym(d, is);
0488         if (mainsym < LZX_NUM_CHARS) {
0489             /* Literal  */
0490             *out_next++ = mainsym;
0491             continue;
0492         }
0493
0494         /* Match  */
0495
0496         /* Decode the length header and offset slot.  */
0497         mainsym -= LZX_NUM_CHARS;
0498         match_len = mainsym % LZX_NUM_LEN_HEADERS;
0499         offset_slot = mainsym / LZX_NUM_LEN_HEADERS;
0500
0501         /* If needed, read a length symbol to decode the full length. */
0502         if (match_len == LZX_NUM_PRIMARY_LENS)
0503             match_len += read_lensym(d, is);
0504         match_len += LZX_MIN_MATCH_LEN;
0505
0506         if (offset_slot < LZX_NUM_RECENT_OFFSETS) {
0507             /* Repeat offset  */
0508
0509             /* Note: This isn't a real LRU queue, since using the R2
0510              * offset doesn't bump the R1 offset down to R2.  This
0511              * quirk allows all 3 recent offsets to be handled by
0512              * the same code.  (For R0, the swap is a no-op.)
0513              */
0514             match_offset = recent_offsets[offset_slot];
0515             recent_offsets[offset_slot] = recent_offsets[0];
0516             recent_offsets[0] = match_offset;
0517         } else {
0518             /* Explicit offset  */
0519
0520             /* Look up the number of extra bits that need to be read
0521              * to decode offsets with this offset slot.
0522              */
0523             num_extra_bits = lzx_extra_offset_bits[offset_slot];
0524
0525             /* Start with the offset slot base value.  */
0526             match_offset = lzx_offset_slot_base[offset_slot];
0527
0528             /* In aligned offset blocks, the low-order 3 bits of
0529              * each offset are encoded using the aligned offset
0530              * code.  Otherwise, all the extra bits are literal.
0531              */
0532
0533             if ((num_extra_bits & ones_if_aligned) >= LZX_NUM_ALIGNED_OFFSET_BITS) {
0534                 match_offset +=
0535                     bitstream_read_bits(is, num_extra_bits -
0536                                 LZX_NUM_ALIGNED_OFFSET_BITS)
0537                             << LZX_NUM_ALIGNED_OFFSET_BITS;
0538                 match_offset += read_alignedsym(d, is);
0539             } else {
0540                 match_offset += bitstream_read_bits(is, num_extra_bits);
0541             }
0542
0543             /* Adjust the offset.  */
0544             match_offset -= (LZX_NUM_RECENT_OFFSETS - 1);
0545
0546             /* Update the recent offsets.  */
0547             recent_offsets[2] = recent_offsets[1];
0548             recent_offsets[1] = recent_offsets[0];
0549             recent_offsets[0] = match_offset;
0550         }
0551
0552         /* Validate the match, then copy it to the current position.  */
0553
0554         if (match_len > (size_t)(block_end - out_next))
0555             return -1;
0556
0557         if (match_offset > (size_t)(out_next - out_begin))
0558             return -1;
0559
0560         out_next = lz_copy(out_next, match_len, match_offset,
0561                    block_end, LZX_MIN_MATCH_LEN);
0562
0563     } while (out_next != block_end);
0564
0565     return 0;
0566 }
0567
0568 /*
0569  * lzx_allocate_decompressor - Allocate an LZX decompressor
0570  *
0571  * Return the pointer to the decompressor on success, or return NULL and set
0572  * errno on failure.
0573  */
0574 struct lzx_decompressor *lzx_allocate_decompressor(void)
0575 {
0576     return kmalloc(sizeof(struct lzx_decompressor), GFP_NOFS);
0577 }
0578
0579 /*
0580  * lzx_decompress - Decompress a buffer of LZX-compressed data
0581  *
0582  * @decompressor:      A decompressor allocated with lzx_allocate_decompressor()
0583  * @compressed_data:    The buffer of data to decompress
0584  * @compressed_size:    Number of bytes of compressed data
0585  * @uncompressed_data:  The buffer in which to store the decompressed data
0586  * @uncompressed_size:  The number of bytes the data decompresses into
0587  *
0588  * Return 0 on success, or return -1 and set errno on failure.
0589  */
0590 int lzx_decompress(struct lzx_decompressor *decompressor,
0591            const void *compressed_data, size_t compressed_size,
0592            void *uncompressed_data, size_t uncompressed_size)
0593 {
0594     struct lzx_decompressor *d = decompressor;
0595     u8 * const out_begin = uncompressed_data;
0596     u8 *out_next = out_begin;
0597     u8 * const out_end = out_begin + uncompressed_size;
0598     struct input_bitstream is;
0599     u32 recent_offsets[LZX_NUM_RECENT_OFFSETS] = {1, 1, 1};
0600     int e8_status = 0;
0601
0602     init_input_bitstream(&is, compressed_data, compressed_size);
0603
0604     /* Codeword lengths begin as all 0's for delta encoding purposes.  */
0605     memset(d->maincode_lens, 0, LZX_MAINCODE_NUM_SYMBOLS);
0606     memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS);
0607
0608     /* Decompress blocks until we have all the uncompressed data.  */
0609
0610     while (out_next != out_end) {
0611         int block_type;
0612         u32 block_size;
0613
0614         if (lzx_read_block_header(d, &is, &block_type, &block_size,
0615                       recent_offsets))
0616             goto invalid;
0617
0618         if (block_size < 1 || block_size > (size_t)(out_end - out_next))
0619             goto invalid;
0620
0621         if (block_type != LZX_BLOCKTYPE_UNCOMPRESSED) {
0622
0623             /* Compressed block  */
0624
0625             if (lzx_decompress_block(d,
0626                          &is,
0627                          block_type,
0628                          block_size,
0629                          out_begin,
0630                          out_next,
0631                          recent_offsets))
0632                 goto invalid;
0633
0634             e8_status |= d->maincode_lens[0xe8];
0635             out_next += block_size;
0636         } else {
0637             /* Uncompressed block  */
0638
0639             out_next = bitstream_read_bytes(&is, out_next,
0640                             block_size);
0641             if (!out_next)
0642                 goto invalid;
0643
0644             if (block_size & 1)
0645                 bitstream_read_byte(&is);
0646
0647             e8_status = 1;
0648         }
0649     }
0650
0651     /* Postprocess the data unless it cannot possibly contain 0xe8 bytes. */
0652     if (e8_status)
0653         lzx_postprocess(uncompressed_data, uncompressed_size);
0654
0655     return 0;
0656
0657 invalid:
0658     return -1;
0659 }
0660
0661 /*
0662  * lzx_free_decompressor - Free an LZX decompressor
0663  *
0664  * @decompressor:       A decompressor that was allocated with
0665  *          lzx_allocate_decompressor(), or NULL.
0666  */
0667 void lzx_free_decompressor(struct lzx_decompressor *decompressor)
0668 {
0669     kfree(decompressor);
0670 }