6 * Copyright (C) 2013 Eric Biggers
8 * This file is part of wimlib, a library for working with WIM files.
10 * wimlib is free software; you can redistribute it and/or modify it under the
11 * terms of the GNU General Public License as published by the Free
12 * Software Foundation; either version 3 of the License, or (at your option)
15 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
16 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
17 * A PARTICULAR PURPOSE. See the GNU General Public License for more
20 * You should have received a copy of the GNU General Public License
21 * along with wimlib; if not, see http://www.gnu.org/licenses/.
25 * This is a decompressor for the LZMS compression format used by Microsoft.
26 * This format is not documented, but it is one of the formats supported by the
27 * compression API available in Windows 8, and as of Windows 8 it is one of the
28 * formats that can be used in WIM files.
30 * This decompressor only implements "raw" decompression, which decompresses a
31 * single LZMS-compressed block. This behavior is the same as that of
32 * Decompress() in the Windows 8 compression API when using a compression handle
33 * created with CreateDecompressor() with the Algorithm parameter specified as
34 * COMPRESS_ALGORITHM_LZMS | COMPRESS_RAW. Presumably, non-raw LZMS data
35 * is a container format from which the locations and sizes (both compressed and
36 * uncompressed) of the constituent blocks can be determined.
38 * A LZMS-compressed block must be read in 16-bit little endian units from both
39 * directions. One logical bitstream starts at the front of the block and
40 * proceeds forwards. Another logical bitstream starts at the end of the block
41 * and proceeds backwards. Bits read from the forwards bitstream constitute
42 * range-encoded data, whereas bits read from the backwards bitstream constitute
43 * Huffman-encoded symbols or verbatim bits. For both bitstreams, the ordering
44 * of the bits within the 16-bit coding units is such that the first bit is the
45 * high-order bit and the last bit is the low-order bit.
47 * From these two logical bitstreams, an LZMS decompressor can reconstitute the
48 * series of items that make up the LZMS data representation. Each such item
49 * may be a literal byte or a match. Matches may be either traditional LZ77
50 * matches or "delta" matches, either of which can have its offset encoded
51 * explicitly or encoded via a reference to a recently used (repeat) offset.
53 * A traditional LZ match consists of a length and offset; it asserts that the
54 * sequence of bytes beginning at the current position and extending for the
55 * length is exactly equal to the equal-length sequence of bytes at the offset
56 * back in the window. On the other hand, a delta match consists of a length,
57 * raw offset, and power. It asserts that the sequence of bytes beginning at
58 * the current position and extending for the length is equal to the bytewise
59 * sum of the two equal-length sequences of bytes (2**power) and (raw_offset *
60 * 2**power) bytes before the current position, minus bytewise the sequence of
61 * bytes beginning at (2**power + raw_offset * 2**power) bytes before the
62 * current position. Although not generally as useful as traditional LZ
63 * matches, delta matches can be helpful on some types of data. Both LZ and
64 * delta matches may overlap with the current position; in fact, the minimum
65 * offset is 1, regardless of match length.
67 * For LZ matches, up to 3 repeat offsets are allowed, similar to some other
68 * LZ-based formats such as LZX and LZMA. They must updated in a LRU fashion,
69 * except for a quirk: updates to the queue must be delayed by one LZMS item,
70 * except for the removal of a repeat match. As a result, 4 entries are
71 * actually needed in the queue, even though it is only possible to decode
72 * references to the first 3 at any given time. The queue must be initialized
73 * to the offsets {1, 2, 3, 4}.
75 * Repeat delta matches are handled similarly, but for them there are two queues
76 * updated in lock-step: one for powers and one for raw offsets. The power
77 * queue must be initialized to {0, 0, 0, 0}, and the raw offset queue must be
78 * initialized to {1, 2, 3, 4}.
80 * Bits from the range decoder must be used to disambiguate item types. The
81 * range decoder must hold two state variables: the range, which must initially
82 * be set to 0xffffffff, and the current code, which must initially be set to
83 * the first 32 bits read from the forwards bitstream. The range must be
84 * maintained above 0xffff; when it falls below 0xffff, both the range and code
85 * must be left-shifted by 16 bits and the low 16 bits of the code must be
86 * filled in with the next 16 bits from the forwards bitstream.
88 * To decode each bit, the range decoder requires a probability that is
89 * logically a real number between 0 and 1. Multiplying this probability by the
90 * current range and taking the floor gives the bound between the 0-bit region
91 * of the range and the 1-bit region of the range. However, in LZMS,
92 * probabilities are restricted to values of n/64 where n is an integer is
93 * between 1 and 63 inclusively, so the implementation may use integer
94 * operations instead. Following calculation of the bound, if the current code
95 * is in the 0-bit region, the new range becomes the current code and the
96 * decoded bit is 0; otherwise, the bound must be subtracted from both the range
97 * and the code, and the decoded bit is 1. More information about range coding
98 * can be found at https://en.wikipedia.org/wiki/Range_encoding. Furthermore,
99 * note that the LZMA format also uses range coding and has public domain code
102 * The probability used to range-decode each bit must be taken from a table, of
103 * which one instance must exist for each distinct context in which a
104 * range-decoded bit is needed. At each call of the range decoder, the
105 * appropriate probability must be obtained by indexing the appropriate
106 * probability table with the last 4 (in the context disambiguating literals
107 * from matches), 5 (in the context disambiguating LZ matches from delta
108 * matches), or 6 (in all other contexts) bits recently range-decoded in that
109 * context, ordered such that the most recently decoded bit is the low-order bit
112 * Furthermore, each probability entry itself is variable, as its value must be
113 * maintained as n/64 where n is the number of 0 bits in the most recently
114 * decoded 64 bits with that same entry. This allows the compressed
115 * representation to adapt to the input and use fewer bits to represent the most
116 * likely data; note that LZMA uses a similar scheme. Initially, the most
117 * recently 64 decoded bits for each probability entry are assumed to be
118 * 0x0000000055555555 (high order to low order); therefore, all probabilities
119 * are initially 48/64. During the course of decoding, each probability may be
120 * updated to as low as 0/64 (as a result of reading many consecutive 1 bits
121 * with that entry) or as high as 64/64 (as a result of reading many consecutive
122 * 0 bits with that entry); however, probabilities of 0/64 and 64/64 cannot be
123 * used as-is but rather must be adjusted to 1/64 and 63/64, respectively,
124 * before being used for range decoding.
126 * Representations of the LZMS items themselves must be read from the backwards
127 * bitstream. For this, there are 5 different Huffman codes used:
129 * - The literal code, used for decoding literal bytes. Each of the 256
130 * symbols represents a literal byte. This code must be rebuilt whenever
131 * 1024 symbols have been decoded with it.
133 * - The LZ offset code, used for decoding the offsets of standard LZ77
134 * matches. Each symbol represents a position slot, which corresponds to a
135 * base value and some number of extra bits which must be read and added to
136 * the base value to reconstitute the full offset. The number of symbols in
137 * this code is the number of position slots needed to represent all possible
138 * offsets in the uncompressed block. This code must be rebuilt whenever
139 * 1024 symbols have been decoded with it.
141 * - The length code, used for decoding length symbols. Each of the 54 symbols
142 * represents a length slot, which corresponds to a base value and some
143 * number of extra bits which must be read and added to the base value to
144 * reconstitute the full length. This code must be rebuilt whenever 512
145 * symbols have been decoded with it.
147 * - The delta offset code, used for decoding the offsets of delta matches.
148 * Each symbol corresponds to a position slot, which corresponds to a base
149 * value and some number of extra bits which must be read and added to the
150 * base value to reconstitute the full offset. The number of symbols in this
151 * code is equal to the number of symbols in the LZ offset code. This code
152 * must be rebuilt whenever 1024 symbols have been decoded with it.
154 * - The delta power code, used for decoding the powers of delta matches. Each
155 * of the 8 symbols corresponds to a power. This code must be rebuilt
156 * whenever 512 symbols have been decoded with it.
158 * All the LZMS Huffman codes must be built adaptively based on symbol
159 * frequencies. Initially, each code must be built assuming that all symbols
160 * have equal frequency. Following that, each code must be rebuilt whenever a
161 * certain number of symbols has been decoded with it.
163 * In general, multiple valid Huffman codes can be constructed from a set of
164 * symbol frequencies. Like other compression formats such as XPRESS, LZX, and
165 * DEFLATE, the LZMS format solves this ambiguity by requiring that all Huffman
166 * codes be constructed in canonical form. This form requires that same-length
167 * codewords be lexicographically ordered the same way as the corresponding
168 * symbols and that all shorter codewords lexicographically precede longer
171 * Codewords in all the LZMS Huffman codes are limited to 15 bits. If the
172 * canonical code for a given set of symbol frequencies has any codewords longer
173 * than 15 bits, then all frequencies must be divided by 2, rounding up, and the
174 * code construction must be attempted again.
176 * A LZMS-compressed block seemingly cannot have a compressed size greater than
177 * or equal to the uncompressed size. In such cases the block must be stored
180 * After all LZMS items have been decoded, the data must be postprocessed to
181 * translate absolute address encoded in x86 instructions into their original
182 * relative addresses.
184 * Details omitted above can be found in the code. Note that in the absence of
185 * an official specification there is no guarantee that this decompressor
186 * handles all possible cases.
194 #include "wimlib/compress_common.h"
195 #include "wimlib/decompressor_ops.h"
196 #include "wimlib/decompress_common.h"
197 #include "wimlib/error.h"
198 #include "wimlib/lzms.h"
199 #include "wimlib/util.h"
203 #define LZMS_DECODE_TABLE_BITS 10
205 /* Structure used for range decoding, reading bits forwards. This is the first
206 * logical bitstream mentioned above. */
207 struct lzms_range_decoder_raw {
208 /* The relevant part of the current range. Although the logical range
209 * for range decoding is a very large integer, only a small portion
210 * matters at any given time, and it can be normalized (shifted left)
211 * whenever it gets too small. */
214 /* The current position in the range encoded by the portion of the input
218 /* Pointer to the next little-endian 16-bit integer in the compressed
219 * input data (reading forwards). */
222 /* Number of 16-bit integers remaining in the compressed input data
223 * (reading forwards). */
224 size_t num_le16_remaining;
227 /* Structure used for reading raw bits backwards. This is the second logical
228 * bitstream mentioned above. */
229 struct lzms_input_bitstream {
230 /* Holding variable for bits that have been read from the compressed
231 * data. The bits are ordered from high-order to low-order. */
232 /* XXX: Without special-case code to handle reading more than 17 bits
233 * at a time, this needs to be 64 bits rather than 32 bits. */
236 /* Number of bits in @bitbuf that are are used. */
237 unsigned num_filled_bits;
239 /* Pointer to the one past the next little-endian 16-bit integer in the
240 * compressed input data (reading backwards). */
243 /* Number of 16-bit integers remaining in the compressed input data
244 * (reading backwards). */
245 size_t num_le16_remaining;
248 /* Structure used for range decoding. This wraps around `struct
249 * lzms_range_decoder_raw' to use and maintain probability entries. */
250 struct lzms_range_decoder {
251 /* Pointer to the raw range decoder, which has no persistent knowledge
252 * of probabilities. Multiple lzms_range_decoder's share the same
253 * lzms_range_decoder_raw. */
254 struct lzms_range_decoder_raw *rd;
256 /* Bits recently decoded by this range decoder. This are used as in
257 * index into @prob_entries. */
260 /* Bitmask for @state to prevent its value from exceeding the number of
261 * probability entries. */
264 /* Probability entries being used for this range decoder. */
265 struct lzms_probability_entry prob_entries[LZMS_MAX_NUM_STATES];
268 /* Structure used for Huffman decoding, optionally using the decoded symbols as
269 * slots into a base table to determine how many extra bits need to be read to
270 * reconstitute the full value. */
271 struct lzms_huffman_decoder {
273 /* Bitstream to read Huffman-encoded symbols and verbatim bits from.
274 * Multiple lzms_huffman_decoder's share the same lzms_input_bitstream.
276 struct lzms_input_bitstream *is;
278 /* Pointer to the slot base table to use. It is indexed by the decoded
279 * Huffman symbol that specifies the slot. The entry specifies the base
280 * value to use, and the position of its high bit is the number of
281 * additional bits that must be read to reconstitute the full value.
283 * This member need not be set if only raw Huffman symbols are being
284 * read using this decoder. */
285 const u32 *slot_base_tab;
287 /* Number of symbols that have been read using this code far. Reset to
288 * 0 whenever the code is rebuilt. */
291 /* When @num_syms_read reaches this number, the Huffman code must be
295 /* Number of symbols in the represented Huffman code. */
298 /* Running totals of symbol frequencies. These are diluted slightly
299 * whenever the code is rebuilt. */
300 u32 sym_freqs[LZMS_MAX_NUM_SYMS];
302 /* The length, in bits, of each symbol in the Huffman code. */
303 u8 lens[LZMS_MAX_NUM_SYMS];
305 /* The codeword of each symbol in the Huffman code. */
306 u16 codewords[LZMS_MAX_NUM_SYMS];
308 /* A table for quickly decoding symbols encoded using the Huffman code.
310 u16 decode_table[(1U << LZMS_DECODE_TABLE_BITS) + 2 * LZMS_MAX_NUM_SYMS]
311 _aligned_attribute(DECODE_TABLE_ALIGNMENT);
314 /* State of the LZMS decompressor. */
315 struct lzms_decompressor {
317 /* Pointer to the beginning of the uncompressed data buffer. */
320 /* Pointer to the next position in the uncompressed data buffer. */
323 /* Pointer to one past the end of the uncompressed data buffer. */
326 /* Range decoder, which reads bits from the beginning of the compressed
327 * block, going forwards. */
328 struct lzms_range_decoder_raw rd;
330 /* Input bitstream, which reads from the end of the compressed block,
331 * going backwards. */
332 struct lzms_input_bitstream is;
334 /* Range decoders. */
335 struct lzms_range_decoder main_range_decoder;
336 struct lzms_range_decoder match_range_decoder;
337 struct lzms_range_decoder lz_match_range_decoder;
338 struct lzms_range_decoder lz_repeat_match_range_decoders[LZMS_NUM_RECENT_OFFSETS - 1];
339 struct lzms_range_decoder delta_match_range_decoder;
340 struct lzms_range_decoder delta_repeat_match_range_decoders[LZMS_NUM_RECENT_OFFSETS - 1];
342 /* Huffman decoders. */
343 struct lzms_huffman_decoder literal_decoder;
344 struct lzms_huffman_decoder lz_offset_decoder;
345 struct lzms_huffman_decoder length_decoder;
346 struct lzms_huffman_decoder delta_power_decoder;
347 struct lzms_huffman_decoder delta_offset_decoder;
349 /* LRU (least-recently-used) queue of LZ match offsets. */
350 u64 recent_lz_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
352 /* LRU (least-recently-used) queue of delta match powers. */
353 u32 recent_delta_powers[LZMS_NUM_RECENT_OFFSETS + 1];
355 /* LRU (least-recently-used) queue of delta match offsets. */
356 u32 recent_delta_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
358 /* These variables are used to delay updates to the LRU queues by one
361 u32 prev_delta_power;
362 u32 prev_delta_offset;
363 u32 upcoming_lz_offset;
364 u32 upcoming_delta_power;
365 u32 upcoming_delta_offset;
367 /* Used for postprocessing. */
368 s32 last_target_usages[65536];
371 /* Initialize the input bitstream @is to read forwards from the specified
372 * compressed data buffer @in that is @in_limit 16-bit integers long. */
374 lzms_input_bitstream_init(struct lzms_input_bitstream *is,
375 const le16 *in, size_t in_limit)
378 is->num_filled_bits = 0;
379 is->in = in + in_limit;
380 is->num_le16_remaining = in_limit;
383 /* Ensures that @num_bits bits are buffered in the input bitstream. */
385 lzms_input_bitstream_ensure_bits(struct lzms_input_bitstream *is,
388 while (is->num_filled_bits < num_bits) {
391 LZMS_ASSERT(is->num_filled_bits + 16 <= sizeof(is->bitbuf) * 8);
393 if (unlikely(is->num_le16_remaining == 0))
396 next = le16_to_cpu(*--is->in);
397 is->num_le16_remaining--;
399 is->bitbuf |= next << (sizeof(is->bitbuf) * 8 - is->num_filled_bits - 16);
400 is->num_filled_bits += 16;
406 /* Returns the next @num_bits bits that are buffered in the input bitstream. */
408 lzms_input_bitstream_peek_bits(struct lzms_input_bitstream *is,
411 LZMS_ASSERT(is->num_filled_bits >= num_bits);
412 return is->bitbuf >> (sizeof(is->bitbuf) * 8 - num_bits);
415 /* Removes the next @num_bits bits that are buffered in the input bitstream. */
417 lzms_input_bitstream_remove_bits(struct lzms_input_bitstream *is,
420 LZMS_ASSERT(is->num_filled_bits >= num_bits);
421 is->bitbuf <<= num_bits;
422 is->num_filled_bits -= num_bits;
425 /* Removes and returns the next @num_bits bits that are buffered in the input
428 lzms_input_bitstream_pop_bits(struct lzms_input_bitstream *is,
431 u32 bits = lzms_input_bitstream_peek_bits(is, num_bits);
432 lzms_input_bitstream_remove_bits(is, num_bits);
436 /* Reads the next @num_bits from the input bitstream. */
438 lzms_input_bitstream_read_bits(struct lzms_input_bitstream *is,
441 if (unlikely(lzms_input_bitstream_ensure_bits(is, num_bits)))
443 return lzms_input_bitstream_pop_bits(is, num_bits);
446 /* Initialize the range decoder @rd to read forwards from the specified
447 * compressed data buffer @in that is @in_limit 16-bit integers long. */
449 lzms_range_decoder_raw_init(struct lzms_range_decoder_raw *rd,
450 const le16 *in, size_t in_limit)
452 rd->range = 0xffffffff;
453 rd->code = ((u32)le16_to_cpu(in[0]) << 16) |
454 ((u32)le16_to_cpu(in[1]) << 0);
456 rd->num_le16_remaining = in_limit - 2;
459 /* Ensures the current range of the range decoder has at least 16 bits of
462 lzms_range_decoder_raw_normalize(struct lzms_range_decoder_raw *rd)
464 if (rd->range <= 0xffff) {
466 if (unlikely(rd->num_le16_remaining == 0))
468 rd->code = (rd->code << 16) | le16_to_cpu(*rd->in++);
469 rd->num_le16_remaining--;
474 /* Decode and return the next bit from the range decoder (raw version).
476 * @prob is the chance out of LZMS_PROBABILITY_MAX that the next bit is 0.
479 lzms_range_decoder_raw_decode_bit(struct lzms_range_decoder_raw *rd, u32 prob)
483 /* Ensure the range has at least 16 bits of precision. */
484 lzms_range_decoder_raw_normalize(rd);
486 /* Based on the probability, calculate the bound between the 0-bit
487 * region and the 1-bit region of the range. */
488 bound = (rd->range >> LZMS_PROBABILITY_BITS) * prob;
490 if (rd->code < bound) {
491 /* Current code is in the 0-bit region of the range. */
495 /* Current code is in the 1-bit region of the range. */
502 /* Decode and return the next bit from the range decoder. This wraps around
503 * lzms_range_decoder_raw_decode_bit() to handle using and updating the
504 * appropriate probability table. */
506 lzms_range_decode_bit(struct lzms_range_decoder *dec)
508 struct lzms_probability_entry *prob_entry;
512 /* Load the probability entry corresponding to the current state. */
513 prob_entry = &dec->prob_entries[dec->state];
515 /* Treat the number of zero bits in the most recently decoded
516 * LZMS_PROBABILITY_MAX bits with this probability entry as the chance,
517 * out of LZMS_PROBABILITY_MAX, that the next bit will be a 0. However,
518 * don't allow 0% or 100% probabilities. */
519 prob = prob_entry->num_recent_zero_bits;
520 if (prob == LZMS_PROBABILITY_MAX)
521 prob = LZMS_PROBABILITY_MAX - 1;
525 /* Decode the next bit. */
526 bit = lzms_range_decoder_raw_decode_bit(dec->rd, prob);
528 /* Update the state based on the newly decoded bit. */
529 dec->state = (((dec->state << 1) | bit) & dec->mask);
531 /* Update the recent bits, including the cached count of 0's. */
532 BUILD_BUG_ON(LZMS_PROBABILITY_MAX > sizeof(prob_entry->recent_bits) * 8);
534 if (prob_entry->recent_bits & (1ULL << (LZMS_PROBABILITY_MAX - 1))) {
535 /* Replacing 1 bit with 0 bit; increment the zero count.
537 prob_entry->num_recent_zero_bits++;
540 if (!(prob_entry->recent_bits & (1ULL << (LZMS_PROBABILITY_MAX - 1)))) {
541 /* Replacing 0 bit with 1 bit; decrement the zero count.
543 prob_entry->num_recent_zero_bits--;
546 prob_entry->recent_bits = (prob_entry->recent_bits << 1) | bit;
548 /* Return the decoded bit. */
553 /* Build the decoding table for a new adaptive Huffman code using the alphabet
554 * used in the specified Huffman decoder, with the symbol frequencies
557 lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec)
560 /* XXX: This implementation makes use of code already implemented for
561 * the XPRESS and LZX compression formats. However, since for the
562 * adaptive codes used in LZMS we don't actually need the explicit codes
563 * themselves, only the decode tables, it may be possible to optimize
564 * this by somehow directly building or updating the Huffman decode
565 * table. This may be a worthwhile optimization because the adaptive
566 * codes change many times throughout a decompression run. */
567 LZMS_DEBUG("Rebuilding adaptive Huffman code (num_syms=%u)",
569 make_canonical_huffman_code(dec->num_syms, LZMS_MAX_CODEWORD_LEN,
570 dec->sym_freqs, dec->lens, dec->codewords);
571 #if defined(ENABLE_LZMS_DEBUG)
574 make_huffman_decode_table(dec->decode_table, dec->num_syms,
575 LZMS_DECODE_TABLE_BITS, dec->lens,
576 LZMS_MAX_CODEWORD_LEN);
577 LZMS_ASSERT(ret == 0);
580 /* Decode and return the next Huffman-encoded symbol from the LZMS-compressed
581 * block using the specified Huffman decoder. */
583 lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec)
585 const u8 *lens = dec->lens;
586 const u16 *decode_table = dec->decode_table;
587 struct lzms_input_bitstream *is = dec->is;
589 /* The Huffman codes used in LZMS are adaptive and must be rebuilt
590 * whenever a certain number of symbols have been read. Each such
591 * rebuild uses the current symbol frequencies, but the format also
592 * requires that the symbol frequencies be halved after each code
593 * rebuild. This diminishes the effect of old symbols on the current
594 * Huffman codes, thereby causing the Huffman codes to be more locally
596 if (dec->num_syms_read == dec->rebuild_freq) {
597 lzms_rebuild_adaptive_huffman_code(dec);
598 for (unsigned i = 0; i < dec->num_syms; i++) {
599 dec->sym_freqs[i] >>= 1;
600 dec->sym_freqs[i] += 1;
602 dec->num_syms_read = 0;
605 /* In the following Huffman decoding implementation, the first
606 * LZMS_DECODE_TABLE_BITS of the input are used as an offset into a
607 * decode table. The entry will either provide the decoded symbol
608 * directly, or else a "real" Huffman binary tree will be searched to
609 * decode the symbol. */
611 lzms_input_bitstream_ensure_bits(is, LZMS_MAX_CODEWORD_LEN);
613 u16 key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_TABLE_BITS);
614 u16 sym = decode_table[key_bits];
616 if (sym < dec->num_syms) {
617 /* Fast case: The decode table directly provided the symbol. */
618 lzms_input_bitstream_remove_bits(is, lens[sym]);
620 /* Slow case: The symbol took too many bits to include directly
621 * in the decode table, so search for it in a binary tree at the
622 * end of the decode table. */
623 lzms_input_bitstream_remove_bits(is, LZMS_DECODE_TABLE_BITS);
625 key_bits = sym + lzms_input_bitstream_pop_bits(is, 1);
626 } while ((sym = decode_table[key_bits]) >= dec->num_syms);
629 /* Tally and return the decoded symbol. */
630 ++dec->sym_freqs[sym];
631 ++dec->num_syms_read;
635 /* Decode a number from the LZMS bitstream, encoded as a Huffman-encoded symbol
636 * specifying a "slot" (whose corresponding value is looked up in a static
637 * table) plus the number specified by a number of extra bits depending on the
640 lzms_decode_value(struct lzms_huffman_decoder *dec)
643 unsigned num_extra_bits;
646 /* Read the slot (position slot, length slot, etc.), which is encoded as
647 * a Huffman symbol. */
648 slot = lzms_huffman_decode_symbol(dec);
650 LZMS_ASSERT(dec->slot_base_tab != NULL);
652 /* Get the number of extra bits needed to represent the range of values
653 * that share the slot. */
654 num_extra_bits = bsr32(dec->slot_base_tab[slot + 1] -
655 dec->slot_base_tab[slot]);
657 /* Read the number of extra bits and add them to the slot to form the
658 * final decoded value. */
659 extra_bits = lzms_input_bitstream_read_bits(dec->is, num_extra_bits);
660 return dec->slot_base_tab[slot] + extra_bits;
663 /* Copy a literal to the output buffer. */
665 lzms_copy_literal(struct lzms_decompressor *ctx, u8 literal)
667 *ctx->out_next++ = literal;
671 /* Validate an LZ match and copy it to the output buffer. */
673 lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset)
678 if (length > ctx->out_end - ctx->out_next) {
679 LZMS_DEBUG("Match overrun!");
682 if (offset > ctx->out_next - ctx->out_begin) {
683 LZMS_DEBUG("Match underrun!");
687 out_next = ctx->out_next;
688 matchptr = out_next - offset;
690 *out_next++ = *matchptr++;
692 ctx->out_next = out_next;
696 /* Validate a delta match and copy it to the output buffer. */
698 lzms_copy_delta_match(struct lzms_decompressor *ctx, u32 length,
699 u32 power, u32 raw_offset)
701 u32 offset1 = 1U << power;
702 u32 offset2 = raw_offset << power;
703 u32 offset = offset1 + offset2;
709 if (length > ctx->out_end - ctx->out_next) {
710 LZMS_DEBUG("Match overrun!");
713 if (offset > ctx->out_next - ctx->out_begin) {
714 LZMS_DEBUG("Match underrun!");
718 out_next = ctx->out_next;
719 matchptr1 = out_next - offset1;
720 matchptr2 = out_next - offset2;
721 matchptr = out_next - offset;
724 *out_next++ = *matchptr1++ + *matchptr2++ - *matchptr++;
726 ctx->out_next = out_next;
730 /* Decode a (length, offset) pair from the input. */
732 lzms_decode_lz_match(struct lzms_decompressor *ctx)
737 /* Decode the match offset. The next range-encoded bit indicates
738 * whether it's a repeat offset or an explicit offset. */
740 bit = lzms_range_decode_bit(&ctx->lz_match_range_decoder);
742 /* Explicit offset. */
743 offset = lzms_decode_value(&ctx->lz_offset_decoder);
748 for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
749 if (!lzms_range_decode_bit(&ctx->lz_repeat_match_range_decoders[i]))
752 offset = ctx->recent_lz_offsets[i];
754 for (; i < LZMS_NUM_RECENT_OFFSETS; i++)
755 ctx->recent_lz_offsets[i] = ctx->recent_lz_offsets[i + 1];
758 /* Decode match length, which is always given explicitly (there is no
759 * LRU queue for repeat lengths). */
760 length = lzms_decode_value(&ctx->length_decoder);
762 ctx->upcoming_lz_offset = offset;
764 LZMS_DEBUG("Decoded %s LZ match: length=%u, offset=%u",
765 (bit ? "repeat" : "explicit"), length, offset);
767 /* Validate the match and copy it to the output. */
768 return lzms_copy_lz_match(ctx, length, offset);
771 /* Decodes a "delta" match from the input. */
773 lzms_decode_delta_match(struct lzms_decompressor *ctx)
776 u32 length, power, raw_offset;
778 /* Decode the match power and raw offset. The next range-encoded bit
779 * indicates whether these data are a repeat, or given explicitly. */
781 bit = lzms_range_decode_bit(&ctx->delta_match_range_decoder);
783 power = lzms_huffman_decode_symbol(&ctx->delta_power_decoder);
784 raw_offset = lzms_decode_value(&ctx->delta_offset_decoder);
788 for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
789 if (!lzms_range_decode_bit(&ctx->delta_repeat_match_range_decoders[i]))
792 power = ctx->recent_delta_powers[i];
793 raw_offset = ctx->recent_delta_offsets[i];
795 for (; i < LZMS_NUM_RECENT_OFFSETS; i++) {
796 ctx->recent_delta_powers[i] = ctx->recent_delta_powers[i + 1];
797 ctx->recent_delta_offsets[i] = ctx->recent_delta_offsets[i + 1];
801 length = lzms_decode_value(&ctx->length_decoder);
803 ctx->upcoming_delta_power = power;
804 ctx->upcoming_delta_offset = raw_offset;
806 LZMS_DEBUG("Decoded %s delta match: length=%u, power=%u, raw_offset=%u",
807 (bit ? "repeat" : "explicit"), length, power, raw_offset);
809 /* Validate the match and copy it to the output. */
810 return lzms_copy_delta_match(ctx, length, power, raw_offset);
814 lzms_decode_match(struct lzms_decompressor *ctx)
816 if (!lzms_range_decode_bit(&ctx->match_range_decoder))
817 return lzms_decode_lz_match(ctx);
819 return lzms_decode_delta_match(ctx);
822 /* Decode a literal byte encoded using the literal Huffman code. */
824 lzms_decode_literal(struct lzms_decompressor *ctx)
826 u8 literal = lzms_huffman_decode_symbol(&ctx->literal_decoder);
827 LZMS_DEBUG("Decoded literal: 0x%02x", literal);
828 return lzms_copy_literal(ctx, literal);
831 /* Decode the next LZMS match or literal. */
833 lzms_decode_item(struct lzms_decompressor *ctx)
837 ctx->upcoming_delta_offset = 0;
838 ctx->upcoming_lz_offset = 0;
839 ctx->upcoming_delta_power = 0;
841 if (lzms_range_decode_bit(&ctx->main_range_decoder))
842 ret = lzms_decode_match(ctx);
844 ret = lzms_decode_literal(ctx);
849 /* Update LRU queues */
850 if (ctx->prev_lz_offset != 0) {
851 for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--)
852 ctx->recent_lz_offsets[i + 1] = ctx->recent_lz_offsets[i];
853 ctx->recent_lz_offsets[0] = ctx->prev_lz_offset;
856 if (ctx->prev_delta_offset != 0) {
857 for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--) {
858 ctx->recent_delta_powers[i + 1] = ctx->recent_delta_powers[i];
859 ctx->recent_delta_offsets[i + 1] = ctx->recent_delta_offsets[i];
861 ctx->recent_delta_powers[0] = ctx->prev_delta_power;
862 ctx->recent_delta_offsets[0] = ctx->prev_delta_offset;
865 ctx->prev_lz_offset = ctx->upcoming_lz_offset;
866 ctx->prev_delta_offset = ctx->upcoming_delta_offset;
867 ctx->prev_delta_power = ctx->upcoming_delta_power;
872 lzms_init_range_decoder(struct lzms_range_decoder *dec,
873 struct lzms_range_decoder_raw *rd, u32 num_states)
877 dec->mask = num_states - 1;
878 for (u32 i = 0; i < num_states; i++) {
879 dec->prob_entries[i].num_recent_zero_bits = LZMS_INITIAL_PROBABILITY;
880 dec->prob_entries[i].recent_bits = LZMS_INITIAL_RECENT_BITS;
885 lzms_init_huffman_decoder(struct lzms_huffman_decoder *dec,
886 struct lzms_input_bitstream *is,
887 const u32 *slot_base_tab, unsigned num_syms,
888 unsigned rebuild_freq)
891 dec->slot_base_tab = slot_base_tab;
892 dec->num_syms = num_syms;
893 dec->num_syms_read = rebuild_freq;
894 dec->rebuild_freq = rebuild_freq;
895 for (unsigned i = 0; i < num_syms; i++)
896 dec->sym_freqs[i] = 1;
899 /* Prepare to decode items from an LZMS-compressed block. */
901 lzms_init_decompressor(struct lzms_decompressor *ctx,
902 const void *cdata, unsigned clen,
903 void *ubuf, unsigned ulen)
905 unsigned num_position_slots;
907 LZMS_DEBUG("Initializing decompressor (clen=%u, ulen=%u)", clen, ulen);
909 /* Initialize output pointers. */
910 ctx->out_begin = ubuf;
911 ctx->out_next = ubuf;
912 ctx->out_end = (u8*)ubuf + ulen;
914 /* Initialize the raw range decoder (reading forwards). */
915 lzms_range_decoder_raw_init(&ctx->rd, cdata, clen / 2);
917 /* Initialize the input bitstream for Huffman symbols (reading
919 lzms_input_bitstream_init(&ctx->is, cdata, clen / 2);
921 /* Initialize position and length slot bases if not done already. */
922 lzms_init_slot_bases();
924 /* Calculate the number of position slots needed for this compressed
926 num_position_slots = lzms_get_position_slot(ulen - 1) + 1;
928 LZMS_DEBUG("Using %u position slots", num_position_slots);
930 /* Initialize Huffman decoders for each alphabet used in the compressed
932 lzms_init_huffman_decoder(&ctx->literal_decoder, &ctx->is,
933 NULL, LZMS_NUM_LITERAL_SYMS,
934 LZMS_LITERAL_CODE_REBUILD_FREQ);
936 lzms_init_huffman_decoder(&ctx->lz_offset_decoder, &ctx->is,
937 lzms_position_slot_base, num_position_slots,
938 LZMS_LZ_OFFSET_CODE_REBUILD_FREQ);
940 lzms_init_huffman_decoder(&ctx->length_decoder, &ctx->is,
941 lzms_length_slot_base, LZMS_NUM_LEN_SYMS,
942 LZMS_LENGTH_CODE_REBUILD_FREQ);
944 lzms_init_huffman_decoder(&ctx->delta_offset_decoder, &ctx->is,
945 lzms_position_slot_base, num_position_slots,
946 LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ);
948 lzms_init_huffman_decoder(&ctx->delta_power_decoder, &ctx->is,
949 NULL, LZMS_NUM_DELTA_POWER_SYMS,
950 LZMS_DELTA_POWER_CODE_REBUILD_FREQ);
953 /* Initialize range decoders, all of which wrap around the same
954 * lzms_range_decoder_raw. */
955 lzms_init_range_decoder(&ctx->main_range_decoder,
956 &ctx->rd, LZMS_NUM_MAIN_STATES);
958 lzms_init_range_decoder(&ctx->match_range_decoder,
959 &ctx->rd, LZMS_NUM_MATCH_STATES);
961 lzms_init_range_decoder(&ctx->lz_match_range_decoder,
962 &ctx->rd, LZMS_NUM_LZ_MATCH_STATES);
964 for (size_t i = 0; i < ARRAY_LEN(ctx->lz_repeat_match_range_decoders); i++)
965 lzms_init_range_decoder(&ctx->lz_repeat_match_range_decoders[i],
966 &ctx->rd, LZMS_NUM_LZ_REPEAT_MATCH_STATES);
968 lzms_init_range_decoder(&ctx->delta_match_range_decoder,
969 &ctx->rd, LZMS_NUM_DELTA_MATCH_STATES);
971 for (size_t i = 0; i < ARRAY_LEN(ctx->delta_repeat_match_range_decoders); i++)
972 lzms_init_range_decoder(&ctx->delta_repeat_match_range_decoders[i],
973 &ctx->rd, LZMS_NUM_DELTA_REPEAT_MATCH_STATES);
975 /* Initialize the LRU queue for recent match offsets. */
976 for (size_t i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++)
977 ctx->recent_lz_offsets[i] = i + 1;
979 for (size_t i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) {
980 ctx->recent_delta_powers[i] = 0;
981 ctx->recent_delta_offsets[i] = i + 1;
983 ctx->prev_lz_offset = 0;
984 ctx->prev_delta_offset = 0;
985 ctx->prev_delta_power = 0;
986 ctx->upcoming_lz_offset = 0;
987 ctx->upcoming_delta_offset = 0;
988 ctx->upcoming_delta_power = 0;
990 LZMS_DEBUG("Decompressor successfully initialized");
993 /* Decode the series of literals and matches from the LZMS-compressed data.
994 * Returns 0 on success; nonzero if the compressed data is invalid. */
996 lzms_decode_items(const u8 *cdata, size_t clen, u8 *ubuf, size_t ulen,
997 struct lzms_decompressor *ctx)
999 /* Initialize the LZMS decompressor. */
1000 lzms_init_decompressor(ctx, cdata, clen, ubuf, ulen);
1002 /* Decode the sequence of items. */
1003 while (ctx->out_next != ctx->out_end) {
1004 LZMS_DEBUG("Position %u", ctx->out_next - ctx->out_begin);
1005 if (lzms_decode_item(ctx))
1012 lzms_decompress(const void *compressed_data, size_t compressed_size,
1013 void *uncompressed_data, size_t uncompressed_size, void *_ctx)
1015 struct lzms_decompressor *ctx = _ctx;
1017 /* The range decoder requires that a minimum of 4 bytes of compressed
1018 * data be initially available. */
1019 if (compressed_size < 4) {
1020 LZMS_DEBUG("Compressed size too small (got %zu, expected >= 4)",
1025 /* A LZMS-compressed data block should be evenly divisible into 16-bit
1027 if (compressed_size % 2 != 0) {
1028 LZMS_DEBUG("Compressed size not divisible by 2 (got %zu)",
1033 /* Handle the trivial case where nothing needs to be decompressed.
1034 * (Necessary because a window of size 0 does not have a valid position
1036 if (uncompressed_size == 0)
1039 /* The x86 post-processor requires that the uncompressed length fit into
1040 * a signed 32-bit integer. Also, the position slot table cannot be
1041 * searched for a position of INT32_MAX or greater. */
1042 if (uncompressed_size >= INT32_MAX) {
1043 LZMS_DEBUG("Uncompressed length too large "
1044 "(got %zu, expected < INT32_MAX)",
1049 /* Decode the literals and matches. */
1050 if (lzms_decode_items(compressed_data, compressed_size,
1051 uncompressed_data, uncompressed_size, ctx))
1054 /* Postprocess the data. */
1055 lzms_x86_filter(uncompressed_data, uncompressed_size,
1056 ctx->last_target_usages, true);
1058 LZMS_DEBUG("Decompression successful.");
1063 lzms_free_decompressor(void *_ctx)
1065 struct lzms_decompressor *ctx = _ctx;
1071 lzms_create_decompressor(size_t max_block_size,
1072 const struct wimlib_decompressor_params_header *params,
1075 struct lzms_decompressor *ctx;
1077 ctx = MALLOC(sizeof(struct lzms_decompressor));
1079 return WIMLIB_ERR_NOMEM;
1085 const struct decompressor_ops lzms_decompressor_ops = {
1086 .create_decompressor = lzms_create_decompressor,
1087 .decompress = lzms_decompress,
1088 .free_decompressor = lzms_free_decompressor,