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 }