f7f6661649cb78fae376ad7c3a4e29c63c11df70
[wimlib] / src / lzx-decompress.c
1 /*
2  * lzx-decompress.c
3  *
4  * LZX decompression routines, originally based on code taken from cabextract
5  * v0.5, which was, itself, a modified version of the lzx decompression code
6  * from unlzx.
7  */
8
9 /*
10  * Copyright (C) 2012, 2013, 2014 Eric Biggers
11  *
12  * This file is part of wimlib, a library for working with WIM files.
13  *
14  * wimlib is free software; you can redistribute it and/or modify it under the
15  * terms of the GNU General Public License as published by the Free
16  * Software Foundation; either version 3 of the License, or (at your option)
17  * any later version.
18  *
19  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
20  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
21  * A PARTICULAR PURPOSE. See the GNU General Public License for more
22  * details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with wimlib; if not, see http://www.gnu.org/licenses/.
26  */
27
28 /*
29  * LZX is an LZ77 and Huffman-code based compression format that has many
30  * similarities to the DEFLATE format used in zlib.  The compression ratio is as
31  * good or better than DEFLATE.
32  *
33  * Some notes on the LZX compression format as used in Windows Imaging (WIM)
34  * files:
35  *
36  * A compressed WIM resource consists of a table of chunk offsets followed by
37  * the compressed chunks themselves.  All compressed chunks except possibly the
38  * last decompress to a fixed number of bytes, by default 32768.  This is quite
39  * similar to the cabinet (.cab) file format, but they are not the same.
40  * According to the cabinet format documentation, the LZX block size is
41  * independent from the CFDATA blocks, and an LZX block may span several CFDATA
42  * blocks.  However, in WIMs, LZX blocks do not appear to ever span multiple WIM
43  * chunks.  Note that this means any WIM chunk may be decompressed or compressed
44  * independently from any other chunk, which allows random access.
45  *
46  * An LZX compressed WIM chunk contains one or more LZX blocks of the aligned,
47  * verbatim, or uncompressed block types.  For aligned and verbatim blocks, the
48  * size of the block in uncompressed bytes is specified by a bit following the 3
49  * bits that specify the block type, possibly followed by an additional 16 bits.
50  * '1' means to use the default block size (equal to 32768, the default size of
51  * a WIM chunk), while '0' means that the block size is provided by the next 16
52  * bits.
53  *
54  * The cabinet format, as documented, allows for the possibility that a
55  * compressed CFDATA chunk is up to 6144 bytes larger than the data it
56  * uncompresses to.  However, in the WIM format it appears that every chunk that
57  * would be 32768 bytes or more when compressed is actually stored fully
58  * uncompressed.
59  *
60  * The 'e8' preprocessing step that changes x86 call instructions to use
61  * absolute offsets instead of relative offsets relies on a filesize parameter.
62  * There is no such parameter for this in the WIM files (even though the size of
63  * the file resource could be used for this purpose), and instead a magic file
64  * size of 12000000 is used.  The 'e8' preprocessing is always done, and there
65  * is no bit to indicate whether it is done or not.
66  */
67
68 /*
69  * Some more notes about errors in Microsoft's LZX documentation:
70  *
71  * Microsoft's LZX document and their implementation of the com.ms.util.cab Java
72  * package do not concur.
73  *
74  * In the LZX document, there is a table showing the correlation between window
75  * size and the number of position slots. It states that the 1MB window = 40
76  * slots and the 2MB window = 42 slots. In the implementation, 1MB = 42 slots,
77  * 2MB = 50 slots. The actual calculation is 'find the first slot whose position
78  * base is equal to or more than the required window size'. This would explain
79  * why other tables in the document refer to 50 slots rather than 42.
80  *
81  * The constant NUM_PRIMARY_LENS used in the decompression pseudocode is not
82  * defined in the specification.
83  *
84  * The LZX document states that aligned offset blocks have their aligned offset
85  * Huffman tree AFTER the main and length trees. The implementation suggests
86  * that the aligned offset tree is BEFORE the main and length trees.
87  *
88  * The LZX document decoding algorithm states that, in an aligned offset block,
89  * if an extra_bits value is 1, 2 or 3, then that number of bits should be read
90  * and the result added to the match offset. This is correct for 1 and 2, but
91  * not 3, where just a Huffman symbol (using the aligned tree) should be read.
92  *
93  * Regarding the E8 preprocessing, the LZX document states 'No translation may
94  * be performed on the last 6 bytes of the input block'. This is correct.
95  * However, the pseudocode provided checks for the *E8 leader* up to the last 6
96  * bytes. If the leader appears between -10 and -7 bytes from the end, this
97  * would cause the next four bytes to be modified, at least one of which would
98  * be in the last 6 bytes, which is not allowed according to the spec.
99  *
100  * The specification states that the Huffman trees must always contain at least
101  * one element. However, many CAB files contain blocks where the length tree is
102  * completely empty (because there are no matches), and this is expected to
103  * succeed.
104  */
105
106 #ifdef HAVE_CONFIG_H
107 #  include "config.h"
108 #endif
109
110 #include "wimlib.h"
111 #include "wimlib/decompressor_ops.h"
112 #include "wimlib/decompress_common.h"
113 #include "wimlib/lzx.h"
114 #include "wimlib/util.h"
115
116 #include <string.h>
117
118 #ifdef __SSE2__
119 #  include <emmintrin.h>
120 #endif
121
122 /* Huffman decoding tables and maps from symbols to code lengths. */
123 struct lzx_tables {
124
125         u16 maintree_decode_table[(1 << LZX_MAINCODE_TABLEBITS) +
126                                         (LZX_MAINCODE_MAX_NUM_SYMBOLS * 2)]
127                                         _aligned_attribute(DECODE_TABLE_ALIGNMENT);
128         u8 maintree_lens[LZX_MAINCODE_MAX_NUM_SYMBOLS];
129
130
131         u16 lentree_decode_table[(1 << LZX_LENCODE_TABLEBITS) +
132                                         (LZX_LENCODE_NUM_SYMBOLS * 2)]
133                                         _aligned_attribute(DECODE_TABLE_ALIGNMENT);
134         u8 lentree_lens[LZX_LENCODE_NUM_SYMBOLS];
135
136
137         u16 alignedtree_decode_table[(1 << LZX_ALIGNEDCODE_TABLEBITS) +
138                                         (LZX_ALIGNEDCODE_NUM_SYMBOLS * 2)]
139                                         _aligned_attribute(DECODE_TABLE_ALIGNMENT);
140         u8 alignedtree_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS];
141 } _aligned_attribute(DECODE_TABLE_ALIGNMENT);
142
143 struct lzx_decompressor {
144         u32 max_window_size;
145         unsigned num_main_syms;
146         struct lzx_tables tables;
147 };
148
149 /*
150  * Reads a Huffman-encoded symbol using the pre-tree.
151  */
152 static inline u16
153 read_huffsym_using_pretree(struct input_bitstream *istream,
154                            const u16 pretree_decode_table[],
155                            const u8 pretree_lens[])
156 {
157         return read_huffsym(istream, pretree_decode_table, pretree_lens,
158                             LZX_PRECODE_NUM_SYMBOLS, LZX_PRECODE_TABLEBITS,
159                             LZX_MAX_PRE_CODEWORD_LEN);
160 }
161
162 /* Reads a Huffman-encoded symbol using the main tree. */
163 static inline u16
164 read_huffsym_using_maintree(struct input_bitstream *istream,
165                             const struct lzx_tables *tables,
166                             unsigned num_main_syms)
167 {
168         return read_huffsym(istream, tables->maintree_decode_table,
169                             tables->maintree_lens, num_main_syms,
170                             LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN);
171 }
172
173 /* Reads a Huffman-encoded symbol using the length tree. */
174 static inline u16
175 read_huffsym_using_lentree(struct input_bitstream *istream,
176                            const struct lzx_tables *tables)
177 {
178         return read_huffsym(istream, tables->lentree_decode_table,
179                             tables->lentree_lens, LZX_LENCODE_NUM_SYMBOLS,
180                             LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN);
181 }
182
183 /* Reads a Huffman-encoded symbol using the aligned offset tree. */
184 static inline u16
185 read_huffsym_using_alignedtree(struct input_bitstream *istream,
186                                const struct lzx_tables *tables)
187 {
188         return read_huffsym(istream, tables->alignedtree_decode_table,
189                             tables->alignedtree_lens,
190                             LZX_ALIGNEDCODE_NUM_SYMBOLS,
191                             LZX_ALIGNEDCODE_TABLEBITS,
192                             LZX_MAX_ALIGNED_CODEWORD_LEN);
193 }
194
195 /*
196  * Reads the pretree from the input, then uses the pretree to decode @num_lens
197  * code length values from the input.
198  *
199  * @istream:    The bit stream for the input.  It is positioned on the beginning
200  *                      of the pretree for the code length values.
201  * @lens:       An array that contains the length values from the previous time
202  *                      the code lengths for this Huffman tree were read, or all
203  *                      0's if this is the first time.
204  * @num_lens:   Number of length values to decode and return.
205  *
206  */
207 static int
208 lzx_read_code_lens(struct input_bitstream *istream, u8 lens[],
209                    unsigned num_lens)
210 {
211         /* Declare the decoding table and length table for the pretree. */
212         u16 pretree_decode_table[(1 << LZX_PRECODE_TABLEBITS) +
213                                         (LZX_PRECODE_NUM_SYMBOLS * 2)]
214                                         _aligned_attribute(DECODE_TABLE_ALIGNMENT);
215         u8 pretree_lens[LZX_PRECODE_NUM_SYMBOLS];
216         unsigned i;
217         int ret;
218
219         /* Read the code lengths of the pretree codes.  There are 20 lengths of
220          * 4 bits each. */
221         for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++) {
222                 pretree_lens[i] = bitstream_read_bits(istream,
223                                                       LZX_PRECODE_ELEMENT_SIZE);
224         }
225
226         /* Make the decoding table for the pretree. */
227         ret = make_huffman_decode_table(pretree_decode_table,
228                                         LZX_PRECODE_NUM_SYMBOLS,
229                                         LZX_PRECODE_TABLEBITS,
230                                         pretree_lens,
231                                         LZX_MAX_PRE_CODEWORD_LEN);
232         if (ret)
233                 return ret;
234
235         /* Pointer past the last length value that needs to be filled in. */
236         u8 *lens_end = lens + num_lens;
237
238         while (1) {
239
240                 /* Decode a symbol from the input.  If the symbol is between 0
241                  * and 16, it is the difference from the old length.  If it is
242                  * between 17 and 19, it is a special code that indicates that
243                  * some number of the next lengths are all 0, or some number of
244                  * the next lengths are all equal to the next symbol in the
245                  * input. */
246                 unsigned tree_code;
247                 u32 num_zeroes;
248                 unsigned code;
249                 u32 num_same;
250                 signed char value;
251
252                 tree_code = read_huffsym_using_pretree(istream,
253                                                        pretree_decode_table,
254                                                        pretree_lens);
255                 switch (tree_code) {
256                 case 17: /* Run of 0's */
257                         num_zeroes = bitstream_read_bits(istream, 4);
258                         num_zeroes += 4;
259                         while (num_zeroes--) {
260                                 *lens = 0;
261                                 if (++lens == lens_end)
262                                         return 0;
263                         }
264                         break;
265                 case 18: /* Longer run of 0's */
266                         num_zeroes = bitstream_read_bits(istream, 5);
267                         num_zeroes += 20;
268                         while (num_zeroes--) {
269                                 *lens = 0;
270                                 if (++lens == lens_end)
271                                         return 0;
272                         }
273                         break;
274                 case 19: /* Run of identical lengths */
275                         num_same = bitstream_read_bits(istream, 1);
276                         num_same += 4;
277                         code = read_huffsym_using_pretree(istream,
278                                                           pretree_decode_table,
279                                                           pretree_lens);
280                         value = (signed char)*lens - (signed char)code;
281                         if (value < 0)
282                                 value += 17;
283                         while (num_same--) {
284                                 *lens = value;
285                                 if (++lens == lens_end)
286                                         return 0;
287                         }
288                         break;
289                 default: /* Difference from old length. */
290                         value = (signed char)*lens - (signed char)tree_code;
291                         if (value < 0)
292                                 value += 17;
293                         *lens = value;
294                         if (++lens == lens_end)
295                                 return 0;
296                         break;
297                 }
298         }
299 }
300
301 /*
302  * Reads the header for an LZX-compressed block.
303  *
304  * @istream:            The input bitstream.
305  * @block_size_ret:     A pointer to an int into which the size of the block,
306  *                              in bytes, will be returned.
307  * @block_type_ret:     A pointer to an int into which the type of the block
308  *                              (LZX_BLOCKTYPE_*) will be returned.
309  * @tables:             A pointer to an lzx_tables structure in which the
310  *                              main tree, the length tree, and possibly the
311  *                              aligned offset tree will be constructed.
312  * @queue:      A pointer to the least-recently-used queue into which
313  *                      R0, R1, and R2 will be written (only for uncompressed
314  *                      blocks, which contain this information in the header)
315  */
316 static int
317 lzx_read_block_header(struct input_bitstream *istream,
318                       unsigned num_main_syms,
319                       unsigned max_window_size,
320                       unsigned *block_size_ret,
321                       unsigned *block_type_ret,
322                       struct lzx_tables *tables,
323                       struct lzx_lru_queue *queue)
324 {
325         int ret;
326         unsigned block_type;
327         unsigned block_size;
328
329         bitstream_ensure_bits(istream, 4);
330
331         /* The first three bits tell us what kind of block it is, and are one
332          * of the LZX_BLOCKTYPE_* values.  */
333         block_type = bitstream_pop_bits(istream, 3);
334
335         /* Read the block size.  This mirrors the behavior
336          * lzx_write_compressed_block() in lzx-compress.c; see that for more
337          * details.  */
338         if (bitstream_pop_bits(istream, 1)) {
339                 block_size = LZX_DEFAULT_BLOCK_SIZE;
340         } else {
341                 u32 tmp;
342                 block_size = 0;
343
344                 tmp = bitstream_read_bits(istream, 8);
345                 block_size |= tmp;
346                 tmp = bitstream_read_bits(istream, 8);
347                 block_size <<= 8;
348                 block_size |= tmp;
349
350                 if (max_window_size >= 65536) {
351                         tmp = bitstream_read_bits(istream, 8);
352                         block_size <<= 8;
353                         block_size |= tmp;
354                 }
355         }
356
357         switch (block_type) {
358         case LZX_BLOCKTYPE_ALIGNED:
359                 /* Read the path lengths for the elements of the aligned tree,
360                  * then build it. */
361
362                 for (unsigned i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
363                         tables->alignedtree_lens[i] =
364                                 bitstream_read_bits(istream,
365                                                     LZX_ALIGNEDCODE_ELEMENT_SIZE);
366                 }
367
368                 LZX_DEBUG("Building the aligned tree.");
369                 ret = make_huffman_decode_table(tables->alignedtree_decode_table,
370                                                 LZX_ALIGNEDCODE_NUM_SYMBOLS,
371                                                 LZX_ALIGNEDCODE_TABLEBITS,
372                                                 tables->alignedtree_lens,
373                                                 LZX_MAX_ALIGNED_CODEWORD_LEN);
374                 if (ret) {
375                         LZX_DEBUG("Failed to make the decode table for the "
376                                   "aligned offset tree");
377                         return ret;
378                 }
379
380                 /* Fall though, since the rest of the header for aligned offset
381                  * blocks is the same as that for verbatim blocks */
382
383         case LZX_BLOCKTYPE_VERBATIM:
384                 if (block_type == LZX_BLOCKTYPE_VERBATIM)
385                         LZX_DEBUG("Found verbatim block.");
386
387                 LZX_DEBUG("Reading path lengths for main tree.");
388                 /* Read the path lengths for the first 256 elements of the main
389                  * tree. */
390                 ret = lzx_read_code_lens(istream, tables->maintree_lens,
391                                          LZX_NUM_CHARS);
392                 if (ret) {
393                         LZX_DEBUG("Failed to read the code lengths for the "
394                                   "first 256 elements of the main tree");
395                         return ret;
396                 }
397
398                 /* Read the path lengths for the remaining elements of the main
399                  * tree. */
400                 LZX_DEBUG("Reading path lengths for remaining elements of "
401                           "main tree (%d elements).",
402                           num_main_syms - LZX_NUM_CHARS);
403                 ret = lzx_read_code_lens(istream,
404                                          tables->maintree_lens + LZX_NUM_CHARS,
405                                          num_main_syms - LZX_NUM_CHARS);
406                 if (ret) {
407                         LZX_DEBUG("Failed to read the path lengths for the "
408                                   "remaining elements of the main tree");
409                         return ret;
410                 }
411
412                 LZX_DEBUG("Building the Huffman decoding "
413                           "table for the main tree.");
414
415                 ret = make_huffman_decode_table(tables->maintree_decode_table,
416                                                 num_main_syms,
417                                                 LZX_MAINCODE_TABLEBITS,
418                                                 tables->maintree_lens,
419                                                 LZX_MAX_MAIN_CODEWORD_LEN);
420                 if (ret) {
421                         LZX_DEBUG("Failed to make the decode "
422                                   "table for the main tree");
423                         return ret;
424                 }
425
426                 LZX_DEBUG("Reading path lengths for the length tree.");
427                 ret = lzx_read_code_lens(istream, tables->lentree_lens,
428                                          LZX_LENCODE_NUM_SYMBOLS);
429                 if (ret) {
430                         LZX_DEBUG("Failed to read the path "
431                                   "lengths for the length tree");
432                         return ret;
433                 }
434
435                 LZX_DEBUG("Building the length tree.");
436                 ret = make_huffman_decode_table(tables->lentree_decode_table,
437                                                 LZX_LENCODE_NUM_SYMBOLS,
438                                                 LZX_LENCODE_TABLEBITS,
439                                                 tables->lentree_lens,
440                                                 LZX_MAX_LEN_CODEWORD_LEN);
441                 if (ret) {
442                         LZX_DEBUG("Failed to build the length Huffman tree");
443                         return ret;
444                 }
445                 /* The bitstream of compressed literals and matches for this
446                  * block directly follows and will be read in
447                  * lzx_decompress_block(). */
448                 break;
449         case LZX_BLOCKTYPE_UNCOMPRESSED:
450                 LZX_DEBUG("Found uncompressed block.");
451                 /* Before reading the three LRU match offsets from the
452                  * uncompressed block header, the stream needs to be aligned on
453                  * a 16-bit boundary.  But, unexpectedly, if the stream is
454                  * *already* aligned, the correct thing to do is to throw away
455                  * the next 16 bits. */
456                 if (istream->bitsleft == 0) {
457                         if (istream->data_bytes_left < 14) {
458                                 LZX_DEBUG("Insufficient length in "
459                                           "uncompressed block");
460                                 return -1;
461                         }
462                         istream->data += 2;
463                         istream->data_bytes_left -= 2;
464                 } else {
465                         if (istream->data_bytes_left < 12) {
466                                 LZX_DEBUG("Insufficient length in "
467                                           "uncompressed block");
468                                 return -1;
469                         }
470                         istream->bitsleft = 0;
471                         istream->bitbuf = 0;
472                 }
473                 queue->R[0] = le32_to_cpu(*(le32*)(istream->data + 0));
474                 queue->R[1] = le32_to_cpu(*(le32*)(istream->data + 4));
475                 queue->R[2] = le32_to_cpu(*(le32*)(istream->data + 8));
476                 istream->data += 12;
477                 istream->data_bytes_left -= 12;
478                 /* The uncompressed data of this block directly follows and will
479                  * be read in lzx_decompress(). */
480                 break;
481         default:
482                 LZX_DEBUG("Found invalid block");
483                 return -1;
484         }
485         *block_type_ret = block_type;
486         *block_size_ret = block_size;
487         return 0;
488 }
489
490 /*
491  * Decodes a compressed match from a block of LZX-compressed data.  A match
492  * refers to some match_offset to a point earlier in the window as well as some
493  * match_len, for which the data is to be copied to the current position in the
494  * window.
495  *
496  * @main_element:       The start of the match data, as decoded using the main
497  *                      tree.
498  *
499  * @block_type:         The type of the block (LZX_BLOCKTYPE_ALIGNED or
500  *                      LZX_BLOCKTYPE_VERBATIM)
501  *
502  * @bytes_remaining:    The amount of uncompressed data remaining to be
503  *                      uncompressed in this block.  It is an error if the match
504  *                      is longer than this number.
505  *
506  * @window:             A pointer to the window into which the uncompressed
507  *                      data is being written.
508  *
509  * @window_pos:         The current byte offset in the window.
510  *
511  * @tables:             The Huffman decoding tables for this LZX block (main
512  *                      code, length code, and for LZX_BLOCKTYPE_ALIGNED blocks,
513  *                      also the aligned offset code).
514  *
515  * @queue:              The least-recently used queue for match offsets.
516  *
517  * @istream:            The input bitstream.
518  *
519  * Returns the length of the match, or a negative number on error.  The possible
520  * error cases are:
521  *      - Match would exceed the amount of data remaining to be uncompressed.
522  *      - Match refers to data before the window.
523  *      - The input bitstream ended unexpectedly.
524  */
525 static int
526 lzx_decode_match(unsigned main_element, int block_type,
527                  unsigned bytes_remaining, u8 *window,
528                  unsigned window_pos,
529                  const struct lzx_tables *tables,
530                  struct lzx_lru_queue *queue,
531                  struct input_bitstream *istream)
532 {
533         unsigned length_header;
534         unsigned position_slot;
535         unsigned match_len;
536         unsigned match_offset;
537         unsigned num_extra_bits;
538         u32 verbatim_bits;
539         u32 aligned_bits;
540         unsigned i;
541         u8 *match_dest;
542         u8 *match_src;
543
544         /* The main element is offset by 256 because values under 256 indicate a
545          * literal value. */
546         main_element -= LZX_NUM_CHARS;
547
548         /* The length header consists of the lower 3 bits of the main element.
549          * The position slot is the rest of it. */
550         length_header = main_element & LZX_NUM_PRIMARY_LENS;
551         position_slot = main_element >> 3;
552
553         /* If the length_header is less than LZX_NUM_PRIMARY_LENS (= 7), it
554          * gives the match length as the offset from LZX_MIN_MATCH_LEN.
555          * Otherwise, the length is given by an additional symbol encoded using
556          * the length tree, offset by 9 (LZX_MIN_MATCH_LEN +
557          * LZX_NUM_PRIMARY_LENS) */
558         match_len = LZX_MIN_MATCH_LEN + length_header;
559         if (length_header == LZX_NUM_PRIMARY_LENS)
560                 match_len += read_huffsym_using_lentree(istream, tables);
561
562         /* If the position_slot is 0, 1, or 2, the match offset is retrieved
563          * from the LRU queue.  Otherwise, the match offset is not in the LRU
564          * queue. */
565         switch (position_slot) {
566         case 0:
567                 match_offset = queue->R[0];
568                 break;
569         case 1:
570                 match_offset = queue->R[1];
571                 swap(queue->R[0], queue->R[1]);
572                 break;
573         case 2:
574                 /* The queue doesn't work quite the same as a real LRU queue,
575                  * since using the R2 offset doesn't bump the R1 offset down to
576                  * R2. */
577                 match_offset = queue->R[2];
578                 swap(queue->R[0], queue->R[2]);
579                 break;
580         default:
581                 /* Otherwise, the offset was not encoded as one the offsets in
582                  * the queue.  Depending on the position slot, there is a
583                  * certain number of extra bits that need to be read to fully
584                  * decode the match offset. */
585
586                 /* Look up the number of extra bits that need to be read. */
587                 num_extra_bits = lzx_get_num_extra_bits(position_slot);
588
589                 /* For aligned blocks, if there are at least 3 extra bits, the
590                  * actual number of extra bits is 3 less, and they encode a
591                  * number of 8-byte words that are added to the offset; there
592                  * is then an additional symbol read using the aligned tree that
593                  * specifies the actual byte alignment. */
594                 if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3) {
595
596                         /* There is an error in the LZX "specification" at this
597                          * point; it indicates that a Huffman symbol is to be
598                          * read only if num_extra_bits is greater than 3, but
599                          * actually it is if num_extra_bits is greater than or
600                          * equal to 3.  (Note that in the case with
601                          * num_extra_bits == 3, the assignment to verbatim_bits
602                          * will just set it to 0. ) */
603                         verbatim_bits = bitstream_read_bits(istream,
604                                                             num_extra_bits - 3);
605                         verbatim_bits <<= 3;
606                         aligned_bits = read_huffsym_using_alignedtree(istream,
607                                                                       tables);
608                 } else {
609                         /* For non-aligned blocks, or for aligned blocks with
610                          * less than 3 extra bits, the extra bits are added
611                          * directly to the match offset, and the correction for
612                          * the alignment is taken to be 0. */
613                         verbatim_bits = bitstream_read_bits(istream, num_extra_bits);
614                         aligned_bits = 0;
615                 }
616
617                 /* Calculate the match offset. */
618                 match_offset = lzx_position_base[position_slot] +
619                                verbatim_bits + aligned_bits - LZX_OFFSET_OFFSET;
620
621                 /* Update the LRU queue. */
622                 queue->R[2] = queue->R[1];
623                 queue->R[1] = queue->R[0];
624                 queue->R[0] = match_offset;
625                 break;
626         }
627
628         /* Verify that the match is in the bounds of the part of the window
629          * currently in use, then copy the source of the match to the current
630          * position. */
631
632         if (unlikely(match_len > bytes_remaining)) {
633                 LZX_DEBUG("Match of length %u bytes overflows "
634                           "uncompressed block size", match_len);
635                 return -1;
636         }
637
638         if (unlikely(match_offset > window_pos)) {
639                 LZX_DEBUG("Match of length %u bytes references "
640                           "data before window (match_offset = %u, "
641                           "window_pos = %u)",
642                           match_len, match_offset, window_pos);
643                 return -1;
644         }
645
646         match_dest = window + window_pos;
647         match_src = match_dest - match_offset;
648
649 #if 0
650         printf("Match: src %u, dst %u, len %u\n", match_src - window,
651                                                 match_dest - window,
652                                                 match_len);
653         putchar('|');
654         for (i = 0; i < match_len; i++) {
655                 match_dest[i] = match_src[i];
656                 putchar(match_src[i]);
657         }
658         putchar('|');
659         putchar('\n');
660 #else
661         for (i = 0; i < match_len; i++)
662                 match_dest[i] = match_src[i];
663 #endif
664
665         return match_len;
666 }
667
668 static void
669 undo_call_insn_translation(u32 *call_insn_target, s32 input_pos)
670 {
671         s32 abs_offset;
672         s32 rel_offset;
673
674         abs_offset = le32_to_cpu(*call_insn_target);
675         if (abs_offset >= -input_pos && abs_offset < LZX_WIM_MAGIC_FILESIZE) {
676                 if (abs_offset >= 0) {
677                         /* "good translation" */
678                         rel_offset = abs_offset - input_pos;
679                 } else {
680                         /* "compensating translation" */
681                         rel_offset = abs_offset + LZX_WIM_MAGIC_FILESIZE;
682                 }
683                 *call_insn_target = cpu_to_le32(rel_offset);
684         }
685 }
686
687 /* Undo the 'E8' preprocessing, where the targets of x86 CALL instructions were
688  * changed from relative offsets to absolute offsets.
689  *
690  * Note that this call instruction preprocessing can and will be used on any
691  * data even if it is not actually x86 machine code.  In fact, this type of
692  * preprocessing appears to always be used in LZX-compressed resources in WIM
693  * files; there is no bit to indicate whether it is used or not, unlike in the
694  * LZX compressed format as used in cabinet files, where a bit is reserved for
695  * that purpose.
696  *
697  * Call instruction preprocessing is disabled in the last 6 bytes of the
698  * uncompressed data, which really means the 5-byte call instruction cannot
699  * start in the last 10 bytes of the uncompressed data.  This is one of the
700  * errors in the LZX documentation.
701  *
702  * Call instruction preprocessing does not appear to be disabled after the
703  * 32768th chunk of a WIM stream, which is apparently is yet another difference
704  * from the LZX compression used in cabinet files.
705  *
706  * Call instruction processing is supposed to take the file size as a parameter,
707  * as it is used in calculating the translated jump targets.  But in WIM files,
708  * this file size is always the same (LZX_WIM_MAGIC_FILESIZE == 12000000).*/
709 static void
710 undo_call_insn_preprocessing(u8 *uncompressed_data, size_t uncompressed_size)
711 {
712 #ifdef __SSE2__
713
714         /* SSE2 vectorized implementation for x86_64.  This speeds up LZX
715          * decompression by about 5-8% overall.  (Usually --- the performance
716          * actually regresses slightly in the degenerate case that the data
717          * consists entirely of 0xe8 bytes.)  */
718         __m128i *p128 = (__m128i *)uncompressed_data;
719         u32 valid_mask = 0xFFFFFFFF;
720
721         if (uncompressed_size >= 32 &&
722             ((uintptr_t)uncompressed_data % 16 == 0))
723         {
724                 __m128i * const end128 = p128 + uncompressed_size / 16 - 1;
725
726                 /* Create a vector of all 0xe8 bytes  */
727                 const __m128i e8_bytes = _mm_set1_epi8(0xe8);
728
729                 /* Iterate through the 16-byte vectors in the input.  */
730                 do {
731                         /* Compare the current 16-byte vector with the vector of
732                          * all 0xe8 bytes.  This produces 0xff where the byte is
733                          * 0xe8 and 0x00 where it is not.  */
734                         __m128i cmpresult = _mm_cmpeq_epi8(*p128, e8_bytes);
735
736                         /* Map the comparison results into a single 16-bit
737                          * number.  It will contain a 1 bit when the
738                          * corresponding byte in the current 16-byte vector is
739                          * an e8 byte.  Note: the low-order bit corresponds to
740                          * the first (lowest address) byte.  */
741                         u32 e8_mask = _mm_movemask_epi8(cmpresult);
742
743                         if (!e8_mask) {
744                                 /* If e8_mask is 0, then none of these 16 bytes
745                                  * have value 0xe8.  No e8 translation is
746                                  * needed, and there is no restriction that
747                                  * carries over to the next 16 bytes.  */
748                                 valid_mask = 0xFFFFFFFF;
749                         } else {
750                                 /* At least one byte has value 0xe8.
751                                  *
752                                  * The AND with valid_mask accounts for the fact
753                                  * that we can't start an e8 translation that
754                                  * overlaps the previous one.  */
755                                 while ((e8_mask &= valid_mask)) {
756
757                                         /* Count the number of trailing zeroes
758                                          * in e8_mask.  This will produce the
759                                          * index of the byte, within the 16, at
760                                          * which the next e8 translation should
761                                          * be done.  */
762                                         u32 bit = __builtin_ctz(e8_mask);
763
764                                         /* Do the e8 translation.  */
765                                         u8 *p8 = (u8 *)p128 + bit;
766                                         undo_call_insn_translation((s32 *)(p8 + 1),
767                                                                    p8 - uncompressed_data);
768
769                                         /* Don't start an e8 translation in the
770                                          * next 4 bytes.  */
771                                         valid_mask &= ~((u32)0x1F << bit);
772                                 }
773                                 /* Moving on to the next vector.  Shift and set
774                                  * valid_mask accordingly.  */
775                                 valid_mask >>= 16;
776                                 valid_mask |= 0xFFFF0000;
777                         }
778                 } while (++p128 < end128);
779         }
780
781         u8 *p8 = (u8 *)p128;
782         while (!(valid_mask & 1)) {
783                 p8++;
784                 valid_mask >>= 1;
785         }
786 #else /* __SSE2__  */
787         u8 *p8 = uncompressed_data;
788 #endif /* !__SSE2__  */
789
790         if (uncompressed_size > 10) {
791                 /* Finish any bytes that weren't processed by the vectorized
792                  * implementation.  */
793                 u8 *p8_end = uncompressed_data + uncompressed_size - 10;
794                 do {
795                         if (*p8 == 0xe8) {
796                                 undo_call_insn_translation((s32 *)(p8 + 1),
797                                                            p8 - uncompressed_data);
798                                 p8 += 5;
799                         } else {
800                                 p8++;
801                         }
802                 } while (p8 < p8_end);
803         }
804 }
805
806 /*
807  * Decompresses an LZX-compressed block of data from which the header has already
808  * been read.
809  *
810  * @block_type: The type of the block (LZX_BLOCKTYPE_VERBATIM or
811  *              LZX_BLOCKTYPE_ALIGNED)
812  * @block_size: The size of the block, in bytes.
813  * @num_main_syms:      Number of symbols in the main alphabet.
814  * @window:     Pointer to the decompression window.
815  * @window_pos: The current position in the window.  Will be 0 for the first
816  *                      block.
817  * @tables:     The Huffman decoding tables for the block (main, length, and
818  *                      aligned offset, the latter only for LZX_BLOCKTYPE_ALIGNED)
819  * @queue:      The least-recently-used queue for match offsets.
820  * @istream:    The input bitstream for the compressed literals.
821  */
822 static int
823 lzx_decompress_block(int block_type, unsigned block_size,
824                      unsigned num_main_syms,
825                      u8 *window,
826                      unsigned window_pos,
827                      const struct lzx_tables *tables,
828                      struct lzx_lru_queue *queue,
829                      struct input_bitstream *istream)
830 {
831         unsigned main_element;
832         unsigned end;
833         int match_len;
834
835         end = window_pos + block_size;
836         while (window_pos < end) {
837                 main_element = read_huffsym_using_maintree(istream, tables,
838                                                            num_main_syms);
839                 if (main_element < LZX_NUM_CHARS) {
840                         /* literal: 0 to LZX_NUM_CHARS - 1 */
841                         window[window_pos++] = main_element;
842                 } else {
843                         /* match: LZX_NUM_CHARS to num_main_syms - 1 */
844                         match_len = lzx_decode_match(main_element,
845                                                      block_type,
846                                                      end - window_pos,
847                                                      window,
848                                                      window_pos,
849                                                      tables,
850                                                      queue,
851                                                      istream);
852                         if (unlikely(match_len < 0))
853                                 return match_len;
854                         window_pos += match_len;
855                 }
856         }
857         return 0;
858 }
859
860 static int
861 lzx_decompress(const void *compressed_data, size_t compressed_size,
862                void *uncompressed_data, size_t uncompressed_size,
863                void *_ctx)
864 {
865         struct lzx_decompressor *ctx = _ctx;
866         struct input_bitstream istream;
867         struct lzx_lru_queue queue;
868         unsigned window_pos;
869         unsigned block_size;
870         unsigned block_type;
871         int ret;
872         bool e8_preprocessing_done;
873
874         LZX_DEBUG("compressed_data = %p, compressed_size = %zu, "
875                   "uncompressed_data = %p, uncompressed_size = %zu, "
876                   "max_window_size=%u).",
877                   compressed_data, compressed_size,
878                   uncompressed_data, uncompressed_size,
879                   ctx->max_window_size);
880
881         if (uncompressed_size > ctx->max_window_size) {
882                 LZX_DEBUG("Uncompressed size of %zu exceeds "
883                           "window size of %u!",
884                           uncompressed_size, ctx->max_window_size);
885                 return -1;
886         }
887
888         memset(ctx->tables.maintree_lens, 0, sizeof(ctx->tables.maintree_lens));
889         memset(ctx->tables.lentree_lens, 0, sizeof(ctx->tables.lentree_lens));
890         lzx_lru_queue_init(&queue);
891         init_input_bitstream(&istream, compressed_data, compressed_size);
892
893         e8_preprocessing_done = false; /* Set to true if there may be 0xe8 bytes
894                                           in the uncompressed data. */
895
896         /* The compressed data will consist of one or more blocks.  The
897          * following loop decompresses one block, and it runs until there all
898          * the compressed data has been decompressed, so there are no more
899          * blocks.  */
900
901         for (window_pos = 0;
902              window_pos < uncompressed_size;
903              window_pos += block_size)
904         {
905                 LZX_DEBUG("Reading block header.");
906                 ret = lzx_read_block_header(&istream, ctx->num_main_syms,
907                                             ctx->max_window_size, &block_size,
908                                             &block_type, &ctx->tables, &queue);
909                 if (ret)
910                         return ret;
911
912                 LZX_DEBUG("block_size = %u, window_pos = %u",
913                           block_size, window_pos);
914
915                 if (block_size > uncompressed_size - window_pos) {
916                         LZX_DEBUG("Expected a block size of at "
917                                   "most %zu bytes (found %u bytes)",
918                                   uncompressed_size - window_pos, block_size);
919                         return -1;
920                 }
921
922                 switch (block_type) {
923                 case LZX_BLOCKTYPE_VERBATIM:
924                 case LZX_BLOCKTYPE_ALIGNED:
925                         if (block_type == LZX_BLOCKTYPE_VERBATIM)
926                                 LZX_DEBUG("LZX_BLOCKTYPE_VERBATIM");
927                         else
928                                 LZX_DEBUG("LZX_BLOCKTYPE_ALIGNED");
929                         ret = lzx_decompress_block(block_type,
930                                                    block_size,
931                                                    ctx->num_main_syms,
932                                                    uncompressed_data,
933                                                    window_pos,
934                                                    &ctx->tables,
935                                                    &queue,
936                                                    &istream);
937                         if (ret)
938                                 return ret;
939
940                         if (ctx->tables.maintree_lens[0xe8] != 0)
941                                 e8_preprocessing_done = true;
942                         break;
943                 case LZX_BLOCKTYPE_UNCOMPRESSED:
944                         LZX_DEBUG("LZX_BLOCKTYPE_UNCOMPRESSED");
945                         if (istream.data_bytes_left < block_size) {
946                                 LZX_DEBUG("Unexpected end of input when "
947                                           "reading %u bytes from LZX bitstream "
948                                           "(only have %u bytes left)",
949                                           block_size, istream.data_bytes_left);
950                                 return -1;
951                         }
952                         memcpy(&((u8*)uncompressed_data)[window_pos], istream.data,
953                                block_size);
954                         istream.data += block_size;
955                         istream.data_bytes_left -= block_size;
956                         /* Re-align bitstream if an odd number of bytes were
957                          * read.  */
958                         if (istream.data_bytes_left && (block_size & 1)) {
959                                 istream.data_bytes_left--;
960                                 istream.data++;
961                         }
962                         e8_preprocessing_done = true;
963                         break;
964                 }
965         }
966         if (e8_preprocessing_done)
967                 undo_call_insn_preprocessing(uncompressed_data, uncompressed_size);
968         return 0;
969 }
970
971 static void
972 lzx_free_decompressor(void *_ctx)
973 {
974         struct lzx_decompressor *ctx = _ctx;
975
976         FREE(ctx);
977 }
978
979 static int
980 lzx_create_decompressor(size_t max_window_size,
981                         const struct wimlib_decompressor_params_header *params,
982                         void **ctx_ret)
983 {
984         struct lzx_decompressor *ctx;
985
986         if (!lzx_window_size_valid(max_window_size))
987                 return WIMLIB_ERR_INVALID_PARAM;
988
989         ctx = MALLOC(sizeof(struct lzx_decompressor));
990         if (ctx == NULL)
991                 return WIMLIB_ERR_NOMEM;
992
993         ctx->max_window_size = max_window_size;
994         ctx->num_main_syms = lzx_get_num_main_syms(max_window_size);
995
996         *ctx_ret = ctx;
997         return 0;
998 }
999
1000 const struct decompressor_ops lzx_decompressor_ops = {
1001         .create_decompressor = lzx_create_decompressor,
1002         .decompress          = lzx_decompress,
1003         .free_decompressor   = lzx_free_decompressor,
1004 };