wimlib.net Git - wimlib/blob - src/lzx_decompress.c

   1 /*
   2  * lzx_decompress.c
   3  *
   4  * A decompressor for the LZX compression format, as used in WIM files.
   5  */
   6
   7 /*
   8  * Copyright (C) 2012-2016 Eric Biggers
   9  *
  10  * This file is free software; you can redistribute it and/or modify it under
  11  * the terms of the GNU Lesser General Public License as published by the Free
  12  * Software Foundation; either version 3 of the License, or (at your option) any
  13  * later version.
  14  *
  15  * This file is distributed in the hope that it will be useful, but WITHOUT
  16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  17  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  18  * details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with this file; if not, see http://www.gnu.org/licenses/.
  22  */
  23
  24 /*
  25  * LZX is an LZ77 and Huffman-code based compression format that has many
  26  * similarities to DEFLATE (the format used by zlib/gzip).  The compression
  27  * ratio is as good or better than DEFLATE.  See lzx_compress.c for a format
  28  * overview, and see https://en.wikipedia.org/wiki/LZX_(algorithm) for a
  29  * historical overview.  Here I make some pragmatic notes.
  30  *
  31  * The old specification for LZX is the document "Microsoft LZX Data Compression
  32  * Format" (1997).  It defines the LZX format as used in cabinet files.  Allowed
  33  * window sizes are 2^n where 15 <= n <= 21.  However, this document contains
  34  * several errors, so don't read too much into it...
  35  *
  36  * The new specification for LZX is the document "[MS-PATCH]: LZX DELTA
  37  * Compression and Decompression" (2014).  It defines the LZX format as used by
  38  * Microsoft's binary patcher.  It corrects several errors in the 1997 document
  39  * and extends the format in several ways --- namely, optional reference data,
  40  * up to 2^25 byte windows, and longer match lengths.
  41  *
  42  * WIM files use a more restricted form of LZX.  No LZX DELTA extensions are
  43  * present, the window is not "sliding", E8 preprocessing is done
  44  * unconditionally with a fixed file size, and the maximum window size is always
  45  * 2^15 bytes (equal to the size of each "chunk" in a compressed WIM resource).
  46  * This code is primarily intended to implement this form of LZX.  But although
  47  * not compatible with WIMGAPI, this code also supports maximum window sizes up
  48  * to 2^21 bytes.
  49  *
  50  * TODO: Add support for window sizes up to 2^25 bytes.
  51  */
  52
  53 #ifdef HAVE_CONFIG_H
  54 #  include "config.h"
  55 #endif
  56
  57 #include <string.h>
  58
  59 #include "wimlib/decompressor_ops.h"
  60 #include "wimlib/decompress_common.h"
  61 #include "wimlib/error.h"
  62 #include "wimlib/lzx_common.h"
  63 #include "wimlib/util.h"
  64
  65 /* These values are chosen for fast decompression.  */
  66 #define LZX_MAINCODE_TABLEBITS          11
  67 #define LZX_LENCODE_TABLEBITS           9
  68 #define LZX_PRECODE_TABLEBITS           6
  69 #define LZX_ALIGNEDCODE_TABLEBITS       7
  70
  71 #define LZX_READ_LENS_MAX_OVERRUN 50
  72
  73 struct lzx_decompressor {
  74
  75         DECODE_TABLE(maincode_decode_table, LZX_MAINCODE_MAX_NUM_SYMBOLS,
  76                      LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN);
  77         u8 maincode_lens[LZX_MAINCODE_MAX_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
  78
  79         DECODE_TABLE(lencode_decode_table, LZX_LENCODE_NUM_SYMBOLS,
  80                      LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN);
  81         u8 lencode_lens[LZX_LENCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
  82
  83         union {
  84                 DECODE_TABLE(alignedcode_decode_table, LZX_ALIGNEDCODE_NUM_SYMBOLS,
  85                              LZX_ALIGNEDCODE_TABLEBITS, LZX_MAX_ALIGNED_CODEWORD_LEN);
  86                 u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS];
  87         };
  88
  89         union {
  90                 DECODE_TABLE(precode_decode_table, LZX_PRECODE_NUM_SYMBOLS,
  91                              LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN);
  92                 u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
  93                 u8 extra_offset_bits[LZX_MAX_OFFSET_SLOTS];
  94         };
  95
  96         union {
  97                 DECODE_TABLE_WORKING_SPACE(maincode_working_space,
  98                                            LZX_MAINCODE_MAX_NUM_SYMBOLS,
  99                                            LZX_MAX_MAIN_CODEWORD_LEN);
 100                 DECODE_TABLE_WORKING_SPACE(lencode_working_space,
 101                                            LZX_LENCODE_NUM_SYMBOLS,
 102                                            LZX_MAX_LEN_CODEWORD_LEN);
 103                 DECODE_TABLE_WORKING_SPACE(alignedcode_working_space,
 104                                            LZX_ALIGNEDCODE_NUM_SYMBOLS,
 105                                            LZX_MAX_ALIGNED_CODEWORD_LEN);
 106                 DECODE_TABLE_WORKING_SPACE(precode_working_space,
 107                                            LZX_PRECODE_NUM_SYMBOLS,
 108                                            LZX_MAX_PRE_CODEWORD_LEN);
 109         };
 110
 111         unsigned window_order;
 112         unsigned num_main_syms;
 113
 114         /* Like lzx_extra_offset_bits[], but does not include the entropy-coded
 115          * bits of aligned offset blocks */
 116         u8 extra_offset_bits_minus_aligned[LZX_MAX_OFFSET_SLOTS];
 117
 118 } _aligned_attribute(DECODE_TABLE_ALIGNMENT);
 119
 120 /* Read a Huffman-encoded symbol using the precode. */
 121 static forceinline unsigned
 122 read_presym(const struct lzx_decompressor *d, struct input_bitstream *is)
 123 {
 124         return read_huffsym(is, d->precode_decode_table,
 125                             LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN);
 126 }
 127
 128 /* Read a Huffman-encoded symbol using the main code. */
 129 static forceinline unsigned
 130 read_mainsym(const struct lzx_decompressor *d, struct input_bitstream *is)
 131 {
 132         return read_huffsym(is, d->maincode_decode_table,
 133                             LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN);
 134 }
 135
 136 /* Read a Huffman-encoded symbol using the length code. */
 137 static forceinline unsigned
 138 read_lensym(const struct lzx_decompressor *d, struct input_bitstream *is)
 139 {
 140         return read_huffsym(is, d->lencode_decode_table,
 141                             LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN);
 142 }
 143
 144 /* Read a Huffman-encoded symbol using the aligned offset code. */
 145 static forceinline unsigned
 146 read_alignedsym(const struct lzx_decompressor *d, struct input_bitstream *is)
 147 {
 148         return read_huffsym(is, d->alignedcode_decode_table,
 149                             LZX_ALIGNEDCODE_TABLEBITS, LZX_MAX_ALIGNED_CODEWORD_LEN);
 150 }
 151
 152 /*
 153  * Read a precode from the compressed input bitstream, then use it to decode
 154  * @num_lens codeword length values and write them to @lens.
 155  */
 156 static int
 157 lzx_read_codeword_lens(struct lzx_decompressor *d, struct input_bitstream *is,
 158                        u8 *lens, unsigned num_lens)
 159 {
 160         u8 *len_ptr = lens;
 161         u8 *lens_end = lens + num_lens;
 162
 163         /* Read the lengths of the precode codewords.  These are stored
 164          * explicitly. */
 165         for (int i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++) {
 166                 d->precode_lens[i] =
 167                         bitstream_read_bits(is, LZX_PRECODE_ELEMENT_SIZE);
 168         }
 169
 170         /* Build the decoding table for the precode. */
 171         if (make_huffman_decode_table(d->precode_decode_table,
 172                                       LZX_PRECODE_NUM_SYMBOLS,
 173                                       LZX_PRECODE_TABLEBITS,
 174                                       d->precode_lens,
 175                                       LZX_MAX_PRE_CODEWORD_LEN,
 176                                       d->precode_working_space))
 177                 return -1;
 178
 179         /* Decode the codeword lengths.  */
 180         do {
 181                 unsigned presym;
 182                 u8 len;
 183
 184                 /* Read the next precode symbol.  */
 185                 presym = read_presym(d, is);
 186                 if (presym < 17) {
 187                         /* Difference from old length  */
 188                         len = *len_ptr - presym;
 189                         if ((s8)len < 0)
 190                                 len += 17;
 191                         *len_ptr++ = len;
 192                 } else {
 193                         /* Special RLE values  */
 194
 195                         unsigned run_len;
 196
 197                         if (presym == 17) {
 198                                 /* Run of 0's  */
 199                                 run_len = 4 + bitstream_read_bits(is, 4);
 200                                 len = 0;
 201                         } else if (presym == 18) {
 202                                 /* Longer run of 0's  */
 203                                 run_len = 20 + bitstream_read_bits(is, 5);
 204                                 len = 0;
 205                         } else {
 206                                 /* Run of identical lengths  */
 207                                 run_len = 4 + bitstream_read_bits(is, 1);
 208                                 presym = read_presym(d, is);
 209                                 if (unlikely(presym > 17))
 210                                         return -1;
 211                                 len = *len_ptr - presym;
 212                                 if ((s8)len < 0)
 213                                         len += 17;
 214                         }
 215
 216                         do {
 217                                 *len_ptr++ = len;
 218                         } while (--run_len);
 219                         /*
 220                          * The worst case overrun is when presym == 18,
 221                          * run_len == 20 + 31, and only 1 length was remaining.
 222                          * So LZX_READ_LENS_MAX_OVERRUN == 50.
 223                          *
 224                          * Overrun while reading the first half of maincode_lens
 225                          * can corrupt the previous values in the second half.
 226                          * This doesn't really matter because the resulting
 227                          * lengths will still be in range, and data that
 228                          * generates overruns is invalid anyway.
 229                          */
 230                 }
 231         } while (len_ptr < lens_end);
 232
 233         return 0;
 234 }
 235
 236 /*
 237  * Read the header of an LZX block.  For all block types, the block type and
 238  * size is saved in *block_type_ret and *block_size_ret, respectively.  For
 239  * compressed blocks, the codeword lengths are also saved.  For uncompressed
 240  * blocks, the recent offsets queue is also updated.
 241  */
 242 static int
 243 lzx_read_block_header(struct lzx_decompressor *d, struct input_bitstream *is,
 244                       u32 recent_offsets[], int *block_type_ret,
 245                       u32 *block_size_ret)
 246 {
 247         int block_type;
 248         u32 block_size;
 249
 250         bitstream_ensure_bits(is, 4);
 251
 252         /* Read the block type. */
 253         block_type = bitstream_pop_bits(is, 3);
 254
 255         /* Read the block size. */
 256         if (bitstream_pop_bits(is, 1)) {
 257                 block_size = LZX_DEFAULT_BLOCK_SIZE;
 258         } else {
 259                 block_size = bitstream_read_bits(is, 16);
 260                 if (d->window_order >= 16) {
 261                         block_size <<= 8;
 262                         block_size |= bitstream_read_bits(is, 8);
 263                 }
 264         }
 265
 266         switch (block_type) {
 267
 268         case LZX_BLOCKTYPE_ALIGNED:
 269
 270                 /* Read the aligned offset codeword lengths. */
 271
 272                 for (int i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
 273                         d->alignedcode_lens[i] =
 274                                 bitstream_read_bits(is,
 275                                                     LZX_ALIGNEDCODE_ELEMENT_SIZE);
 276                 }
 277
 278                 /* Fall though, since the rest of the header for aligned offset
 279                  * blocks is the same as that for verbatim blocks.  */
 280
 281         case LZX_BLOCKTYPE_VERBATIM:
 282
 283                 /* Read the main codeword lengths, which are divided into two
 284                  * parts: literal symbols and match headers. */
 285
 286                 if (lzx_read_codeword_lens(d, is, d->maincode_lens,
 287                                            LZX_NUM_CHARS))
 288                         return -1;
 289
 290                 if (lzx_read_codeword_lens(d, is, d->maincode_lens + LZX_NUM_CHARS,
 291                                            d->num_main_syms - LZX_NUM_CHARS))
 292                         return -1;
 293
 294
 295                 /* Read the length codeword lengths. */
 296
 297                 if (lzx_read_codeword_lens(d, is, d->lencode_lens,
 298                                            LZX_LENCODE_NUM_SYMBOLS))
 299                         return -1;
 300
 301                 break;
 302
 303         case LZX_BLOCKTYPE_UNCOMPRESSED:
 304                 /*
 305                  * The header of an uncompressed block contains new values for
 306                  * the recent offsets queue, starting on the next 16-bit
 307                  * boundary in the bitstream.  Careful: if the stream is
 308                  * *already* aligned, the correct thing to do is to throw away
 309                  * the next 16 bits (this is probably a mistake in the format).
 310                  */
 311                 bitstream_ensure_bits(is, 1);
 312                 bitstream_align(is);
 313                 recent_offsets[0] = bitstream_read_u32(is);
 314                 recent_offsets[1] = bitstream_read_u32(is);
 315                 recent_offsets[2] = bitstream_read_u32(is);
 316
 317                 /* Offsets of 0 are invalid.  */
 318                 if (recent_offsets[0] == 0 || recent_offsets[1] == 0 ||
 319                     recent_offsets[2] == 0)
 320                         return -1;
 321                 break;
 322
 323         default:
 324                 /* Unrecognized block type.  */
 325                 return -1;
 326         }
 327
 328         *block_type_ret = block_type;
 329         *block_size_ret = block_size;
 330         return 0;
 331 }
 332
 333 /* Decompress a block of LZX-compressed data. */
 334 static int
 335 lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *_is,
 336                      int block_type, u32 block_size,
 337                      u8 * const out_begin, u8 *out_next, u32 recent_offsets[])
 338 {
 339         /*
 340          * Redeclare the input bitstream on the stack.  This shouldn't be
 341          * needed, but it can improve the main loop's performance significantly
 342          * with both gcc and clang, apparently because the compiler otherwise
 343          * gets confused and doesn't properly allocate registers for
 344          * 'is->bitbuf' et al. and/or thinks 'is->next' may point into 'is'.
 345          */
 346         struct input_bitstream is_onstack = *_is;
 347         struct input_bitstream *is = &is_onstack;
 348         u8 * const block_end = out_next + block_size;
 349         unsigned min_aligned_offset_slot;
 350
 351         /*
 352          * Build the Huffman decode tables.  We always need to build the main
 353          * and length decode tables.  For aligned blocks we additionally need to
 354          * build the aligned offset decode table.
 355          */
 356
 357         if (make_huffman_decode_table(d->maincode_decode_table,
 358                                       d->num_main_syms,
 359                                       LZX_MAINCODE_TABLEBITS,
 360                                       d->maincode_lens,
 361                                       LZX_MAX_MAIN_CODEWORD_LEN,
 362                                       d->maincode_working_space))
 363                 return -1;
 364
 365         if (make_huffman_decode_table(d->lencode_decode_table,
 366                                       LZX_LENCODE_NUM_SYMBOLS,
 367                                       LZX_LENCODE_TABLEBITS,
 368                                       d->lencode_lens,
 369                                       LZX_MAX_LEN_CODEWORD_LEN,
 370                                       d->lencode_working_space))
 371                 return -1;
 372
 373         if (block_type == LZX_BLOCKTYPE_ALIGNED) {
 374                 if (make_huffman_decode_table(d->alignedcode_decode_table,
 375                                               LZX_ALIGNEDCODE_NUM_SYMBOLS,
 376                                               LZX_ALIGNEDCODE_TABLEBITS,
 377                                               d->alignedcode_lens,
 378                                               LZX_MAX_ALIGNED_CODEWORD_LEN,
 379                                               d->alignedcode_working_space))
 380                         return -1;
 381                 min_aligned_offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT;
 382                 memcpy(d->extra_offset_bits, d->extra_offset_bits_minus_aligned,
 383                        sizeof(lzx_extra_offset_bits));
 384         } else {
 385                 min_aligned_offset_slot = LZX_MAX_OFFSET_SLOTS;
 386                 memcpy(d->extra_offset_bits, lzx_extra_offset_bits,
 387                        sizeof(lzx_extra_offset_bits));
 388         }
 389
 390         /* Decode the literals and matches. */
 391
 392         do {
 393                 unsigned mainsym;
 394                 unsigned length;
 395                 u32 offset;
 396                 unsigned offset_slot;
 397
 398                 mainsym = read_mainsym(d, is);
 399                 if (mainsym < LZX_NUM_CHARS) {
 400                         /* Literal */
 401                         *out_next++ = mainsym;
 402                         continue;
 403                 }
 404
 405                 /* Match */
 406
 407                 /* Decode the length header and offset slot.  */
 408                 STATIC_ASSERT(LZX_NUM_CHARS % LZX_NUM_LEN_HEADERS == 0);
 409                 length = mainsym % LZX_NUM_LEN_HEADERS;
 410                 offset_slot = (mainsym - LZX_NUM_CHARS) / LZX_NUM_LEN_HEADERS;
 411
 412                 /* If needed, read a length symbol to decode the full length. */
 413                 if (length == LZX_NUM_PRIMARY_LENS)
 414                         length += read_lensym(d, is);
 415                 length += LZX_MIN_MATCH_LEN;
 416
 417                 if (offset_slot < LZX_NUM_RECENT_OFFSETS) {
 418                         /* Repeat offset  */
 419
 420                         /* Note: This isn't a real LRU queue, since using the R2
 421                          * offset doesn't bump the R1 offset down to R2. */
 422                         offset = recent_offsets[offset_slot];
 423                         recent_offsets[offset_slot] = recent_offsets[0];
 424                 } else {
 425                         /* Explicit offset  */
 426                         offset = bitstream_read_bits(is, d->extra_offset_bits[offset_slot]);
 427                         if (offset_slot >= min_aligned_offset_slot) {
 428                                 offset = (offset << LZX_NUM_ALIGNED_OFFSET_BITS) |
 429                                          read_alignedsym(d, is);
 430                         }
 431                         offset += lzx_offset_slot_base[offset_slot];
 432
 433                         /* Update the match offset LRU queue.  */
 434                         STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3);
 435                         recent_offsets[2] = recent_offsets[1];
 436                         recent_offsets[1] = recent_offsets[0];
 437                 }
 438                 recent_offsets[0] = offset;
 439
 440                 /* Validate the match and copy it to the current position.  */
 441                 if (unlikely(lz_copy(length, offset, out_begin,
 442                                      out_next, block_end, LZX_MIN_MATCH_LEN)))
 443                         return -1;
 444                 out_next += length;
 445         } while (out_next != block_end);
 446
 447         *_is = is_onstack;
 448         return 0;
 449 }
 450
 451 static int
 452 lzx_decompress(const void *restrict compressed_data, size_t compressed_size,
 453                void *restrict uncompressed_data, size_t uncompressed_size,
 454                void *restrict _d)
 455 {
 456         struct lzx_decompressor *d = _d;
 457         u8 * const out_begin = uncompressed_data;
 458         u8 *out_next = out_begin;
 459         u8 * const out_end = out_begin + uncompressed_size;
 460         struct input_bitstream is;
 461         STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3);
 462         u32 recent_offsets[LZX_NUM_RECENT_OFFSETS] = {1, 1, 1};
 463         unsigned may_have_e8_byte = 0;
 464
 465         init_input_bitstream(&is, compressed_data, compressed_size);
 466
 467         /* Codeword lengths begin as all 0's for delta encoding purposes. */
 468         memset(d->maincode_lens, 0, d->num_main_syms);
 469         memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS);
 470
 471         /* Decompress blocks until we have all the uncompressed data. */
 472
 473         while (out_next != out_end) {
 474                 int block_type;
 475                 u32 block_size;
 476
 477                 if (lzx_read_block_header(d, &is, recent_offsets,
 478                                           &block_type, &block_size))
 479                         return -1;
 480
 481                 if (block_size < 1 || block_size > out_end - out_next)
 482                         return -1;
 483
 484                 if (likely(block_type != LZX_BLOCKTYPE_UNCOMPRESSED)) {
 485
 486                         /* Compressed block */
 487                         if (lzx_decompress_block(d, &is, block_type, block_size,
 488                                                  out_begin, out_next,
 489                                                  recent_offsets))
 490                                 return -1;
 491
 492                         /* If the first E8 byte was in this block, then it must
 493                          * have been encoded as a literal using mainsym E8. */
 494                         may_have_e8_byte |= d->maincode_lens[0xE8];
 495                 } else {
 496
 497                         /* Uncompressed block */
 498                         if (bitstream_read_bytes(&is, out_next, block_size))
 499                                 return -1;
 500
 501                         /* Re-align the bitstream if needed. */
 502                         if (block_size & 1)
 503                                 bitstream_read_byte(&is);
 504
 505                         /* There may have been an E8 byte in the block. */
 506                         may_have_e8_byte = 1;
 507                 }
 508                 out_next += block_size;
 509         }
 510
 511         /* Postprocess the data unless it cannot possibly contain E8 bytes. */
 512         if (may_have_e8_byte)
 513                 lzx_postprocess(uncompressed_data, uncompressed_size);
 514
 515         return 0;
 516 }
 517
 518 static int
 519 lzx_create_decompressor(size_t max_block_size, void **d_ret)
 520 {
 521         unsigned window_order;
 522         struct lzx_decompressor *d;
 523
 524         window_order = lzx_get_window_order(max_block_size);
 525         if (window_order == 0)
 526                 return WIMLIB_ERR_INVALID_PARAM;
 527
 528         d = ALIGNED_MALLOC(sizeof(*d), DECODE_TABLE_ALIGNMENT);
 529         if (!d)
 530                 return WIMLIB_ERR_NOMEM;
 531
 532         d->window_order = window_order;
 533         d->num_main_syms = lzx_get_num_main_syms(window_order);
 534
 535         /* Initialize 'd->extra_offset_bits_minus_aligned'. */
 536         STATIC_ASSERT(sizeof(d->extra_offset_bits_minus_aligned) ==
 537                       sizeof(lzx_extra_offset_bits));
 538         STATIC_ASSERT(sizeof(d->extra_offset_bits) ==
 539                       sizeof(lzx_extra_offset_bits));
 540         memcpy(d->extra_offset_bits_minus_aligned, lzx_extra_offset_bits,
 541                sizeof(lzx_extra_offset_bits));
 542         for (unsigned offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT;
 543              offset_slot < LZX_MAX_OFFSET_SLOTS; offset_slot++)
 544         {
 545                 d->extra_offset_bits_minus_aligned[offset_slot] -=
 546                                 LZX_NUM_ALIGNED_OFFSET_BITS;
 547         }
 548
 549         *d_ret = d;
 550         return 0;
 551 }
 552
 553 static void
 554 lzx_free_decompressor(void *_d)
 555 {
 556         ALIGNED_FREE(_d);
 557 }
 558
 559 const struct decompressor_ops lzx_decompressor_ops = {
 560         .create_decompressor = lzx_create_decompressor,
 561         .decompress          = lzx_decompress,
 562         .free_decompressor   = lzx_free_decompressor,
 563 };