decompress_common: move temp space for building decode table to heap
[wimlib] / 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 inline 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 inline 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 inline 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 inline 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         u8 * const block_end = out_next + block_size;
340         unsigned min_aligned_offset_slot;
341
342         /*
343          * Build the Huffman decode tables.  We always need to build the main
344          * and length decode tables.  For aligned blocks we additionally need to
345          * build the aligned offset decode table.
346          */
347
348         if (make_huffman_decode_table(d->maincode_decode_table,
349                                       d->num_main_syms,
350                                       LZX_MAINCODE_TABLEBITS,
351                                       d->maincode_lens,
352                                       LZX_MAX_MAIN_CODEWORD_LEN,
353                                       d->maincode_working_space))
354                 return -1;
355
356         if (make_huffman_decode_table(d->lencode_decode_table,
357                                       LZX_LENCODE_NUM_SYMBOLS,
358                                       LZX_LENCODE_TABLEBITS,
359                                       d->lencode_lens,
360                                       LZX_MAX_LEN_CODEWORD_LEN,
361                                       d->lencode_working_space))
362                 return -1;
363
364         if (block_type == LZX_BLOCKTYPE_ALIGNED) {
365                 if (make_huffman_decode_table(d->alignedcode_decode_table,
366                                               LZX_ALIGNEDCODE_NUM_SYMBOLS,
367                                               LZX_ALIGNEDCODE_TABLEBITS,
368                                               d->alignedcode_lens,
369                                               LZX_MAX_ALIGNED_CODEWORD_LEN,
370                                               d->alignedcode_working_space))
371                         return -1;
372                 min_aligned_offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT;
373                 memcpy(d->extra_offset_bits, d->extra_offset_bits_minus_aligned,
374                        sizeof(lzx_extra_offset_bits));
375         } else {
376                 min_aligned_offset_slot = LZX_MAX_OFFSET_SLOTS;
377                 memcpy(d->extra_offset_bits, lzx_extra_offset_bits,
378                        sizeof(lzx_extra_offset_bits));
379         }
380
381         /* Decode the literals and matches. */
382
383         do {
384                 unsigned mainsym;
385                 unsigned length;
386                 u32 offset;
387                 unsigned offset_slot;
388
389                 mainsym = read_mainsym(d, is);
390                 if (mainsym < LZX_NUM_CHARS) {
391                         /* Literal */
392                         *out_next++ = mainsym;
393                         continue;
394                 }
395
396                 /* Match */
397
398                 /* Decode the length header and offset slot.  */
399                 STATIC_ASSERT(LZX_NUM_CHARS % LZX_NUM_LEN_HEADERS == 0);
400                 length = mainsym % LZX_NUM_LEN_HEADERS;
401                 offset_slot = (mainsym - LZX_NUM_CHARS) / LZX_NUM_LEN_HEADERS;
402
403                 /* If needed, read a length symbol to decode the full length. */
404                 if (length == LZX_NUM_PRIMARY_LENS)
405                         length += read_lensym(d, is);
406                 length += LZX_MIN_MATCH_LEN;
407
408                 if (offset_slot < LZX_NUM_RECENT_OFFSETS) {
409                         /* Repeat offset  */
410
411                         /* Note: This isn't a real LRU queue, since using the R2
412                          * offset doesn't bump the R1 offset down to R2. */
413                         offset = recent_offsets[offset_slot];
414                         recent_offsets[offset_slot] = recent_offsets[0];
415                 } else {
416                         /* Explicit offset  */
417                         offset = bitstream_read_bits(is, d->extra_offset_bits[offset_slot]);
418                         if (offset_slot >= min_aligned_offset_slot) {
419                                 offset = (offset << LZX_NUM_ALIGNED_OFFSET_BITS) |
420                                          read_alignedsym(d, is);
421                         }
422                         offset += lzx_offset_slot_base[offset_slot];
423
424                         /* Update the match offset LRU queue.  */
425                         STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3);
426                         recent_offsets[2] = recent_offsets[1];
427                         recent_offsets[1] = recent_offsets[0];
428                 }
429                 recent_offsets[0] = offset;
430
431                 /* Validate the match and copy it to the current position.  */
432                 if (unlikely(lz_copy(length, offset, out_begin,
433                                      out_next, block_end, LZX_MIN_MATCH_LEN)))
434                         return -1;
435                 out_next += length;
436         } while (out_next != block_end);
437
438         return 0;
439 }
440
441 static int
442 lzx_decompress(const void *restrict compressed_data, size_t compressed_size,
443                void *restrict uncompressed_data, size_t uncompressed_size,
444                void *restrict _d)
445 {
446         struct lzx_decompressor *d = _d;
447         u8 * const out_begin = uncompressed_data;
448         u8 *out_next = out_begin;
449         u8 * const out_end = out_begin + uncompressed_size;
450         struct input_bitstream is;
451         STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3);
452         u32 recent_offsets[LZX_NUM_RECENT_OFFSETS] = {1, 1, 1};
453         unsigned may_have_e8_byte = 0;
454
455         init_input_bitstream(&is, compressed_data, compressed_size);
456
457         /* Codeword lengths begin as all 0's for delta encoding purposes. */
458         memset(d->maincode_lens, 0, d->num_main_syms);
459         memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS);
460
461         /* Decompress blocks until we have all the uncompressed data. */
462
463         while (out_next != out_end) {
464                 int block_type;
465                 u32 block_size;
466
467                 if (lzx_read_block_header(d, &is, recent_offsets,
468                                           &block_type, &block_size))
469                         return -1;
470
471                 if (block_size < 1 || block_size > out_end - out_next)
472                         return -1;
473
474                 if (likely(block_type != LZX_BLOCKTYPE_UNCOMPRESSED)) {
475
476                         /* Compressed block */
477                         if (lzx_decompress_block(d, &is, block_type, block_size,
478                                                  out_begin, out_next,
479                                                  recent_offsets))
480                                 return -1;
481
482                         /* If the first E8 byte was in this block, then it must
483                          * have been encoded as a literal using mainsym E8. */
484                         may_have_e8_byte |= d->maincode_lens[0xE8];
485                 } else {
486
487                         /* Uncompressed block */
488                         if (bitstream_read_bytes(&is, out_next, block_size))
489                                 return -1;
490
491                         /* Re-align the bitstream if needed. */
492                         if (block_size & 1)
493                                 bitstream_read_byte(&is);
494
495                         /* There may have been an E8 byte in the block. */
496                         may_have_e8_byte = 1;
497                 }
498                 out_next += block_size;
499         }
500
501         /* Postprocess the data unless it cannot possibly contain E8 bytes. */
502         if (may_have_e8_byte)
503                 lzx_postprocess(uncompressed_data, uncompressed_size);
504
505         return 0;
506 }
507
508 static int
509 lzx_create_decompressor(size_t max_block_size, void **d_ret)
510 {
511         unsigned window_order;
512         struct lzx_decompressor *d;
513
514         window_order = lzx_get_window_order(max_block_size);
515         if (window_order == 0)
516                 return WIMLIB_ERR_INVALID_PARAM;
517
518         d = ALIGNED_MALLOC(sizeof(*d), DECODE_TABLE_ALIGNMENT);
519         if (!d)
520                 return WIMLIB_ERR_NOMEM;
521
522         d->window_order = window_order;
523         d->num_main_syms = lzx_get_num_main_syms(window_order);
524
525         /* Initialize 'd->extra_offset_bits_minus_aligned'. */
526         STATIC_ASSERT(sizeof(d->extra_offset_bits_minus_aligned) ==
527                       sizeof(lzx_extra_offset_bits));
528         STATIC_ASSERT(sizeof(d->extra_offset_bits) ==
529                       sizeof(lzx_extra_offset_bits));
530         memcpy(d->extra_offset_bits_minus_aligned, lzx_extra_offset_bits,
531                sizeof(lzx_extra_offset_bits));
532         for (unsigned offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT;
533              offset_slot < LZX_MAX_OFFSET_SLOTS; offset_slot++)
534         {
535                 d->extra_offset_bits_minus_aligned[offset_slot] -=
536                                 LZX_NUM_ALIGNED_OFFSET_BITS;
537         }
538
539         *d_ret = d;
540         return 0;
541 }
542
543 static void
544 lzx_free_decompressor(void *_d)
545 {
546         ALIGNED_FREE(_d);
547 }
548
549 const struct decompressor_ops lzx_decompressor_ops = {
550         .create_decompressor = lzx_create_decompressor,
551         .decompress          = lzx_decompress,
552         .free_decompressor   = lzx_free_decompressor,
553 };