4 * A decompressor for the LZMS compression format.
8 * Copyright (C) 2013, 2014, 2015 Eric Biggers
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
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
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/.
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 is a
35 * container format from which the locations and sizes (both compressed and
36 * uncompressed) of the constituent blocks can be determined.
38 * An 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 * binary range-encoded data, whereas bits read from the backwards bitstream
43 * constitute Huffman-encoded symbols or verbatim bits. For both bitstreams,
44 * the ordering of the bits within the 16-bit coding units is such that the
45 * first bit is the 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 LZ77 match consists of a length and offset. It asserts that
54 * the sequence of bytes beginning at the current position and extending for the
55 * length is equal to the same-length sequence of bytes at the offset back in
56 * the data buffer. This type of match can be visualized as follows, with the
57 * caveat that the sequences may overlap:
60 * --------------------
62 * B[1...len] A[1...len]
64 * Decoding proceeds as follows:
70 * On the other hand, a delta match consists of a "span" as well as a length and
71 * offset. A delta match can be visualized as follows, with the caveat that the
72 * various sequences may overlap:
75 * -----------------------------
78 * ------------- -------------
80 * D[1...len] C[1...len] B[1...len] A[1...len]
82 * Decoding proceeds as follows:
85 * *A++ = *B++ + *C++ - *D++;
88 * A delta match asserts that the bytewise differences of the A and B sequences
89 * are equal to the bytewise differences of the C and D sequences. The
90 * sequences within each pair are separated by the same number of bytes, the
91 * "span". The inter-pair distance is the "offset". In LZMS, spans are
92 * restricted to powers of 2 between 2**0 and 2**7 inclusively. Offsets are
93 * restricted to multiples of the span. The stored value for the offset is the
94 * "raw offset", which is the real offset divided by the span.
96 * Delta matches can cover data containing a series of power-of-2 sized integers
97 * that is linearly increasing or decreasing. Another way of thinking about it
98 * is that a delta match can match a longer sequence that is interrupted by a
99 * non-matching byte, provided that the non-matching byte is a continuation of a
100 * linearly changing pattern. Examples of files that may contain data like this
101 * are uncompressed bitmap images, uncompressed digital audio, and Unicode data
102 * tables. To some extent, this match type is a replacement for delta filters
103 * or multimedia filters that are sometimes used in other compression software
104 * (e.g. 'xz --delta --lzma2'). However, on most types of files, delta matches
105 * do not seem to be very useful.
107 * Both LZ and delta matches may use overlapping sequences. Therefore, they
108 * must be decoded as if only one byte is copied at a time.
110 * For both LZ and delta matches, any match length in [1, 1073809578] can be
111 * represented. Similarly, any match offset in [1, 1180427428] can be
112 * represented. For delta matches, this range applies to the raw offset, so the
113 * real offset may be larger.
115 * For LZ matches, up to 3 repeat offsets are allowed, similar to some other
116 * LZ-based formats such as LZX and LZMA. They must updated in an LRU fashion,
117 * except for a quirk: inserting anything to the front of the queue must be
118 * delayed by one LZMS item. The reason for this is presumably that there is
119 * almost no reason to code the same match offset twice in a row, since you
120 * might as well have coded a longer match at that offset. For this same
121 * reason, it also is a requirement that when an offset in the queue is used,
122 * that offset is removed from the queue immediately (and made pending for
123 * front-insertion after the following decoded item), and everything to the
124 * right is shifted left one queue slot. This creates a need for an "overflow"
125 * fourth entry in the queue, even though it is only possible to decode
126 * references to the first 3 entries at any given time. The queue must be
127 * initialized to the offsets {1, 2, 3, 4}.
129 * Repeat delta matches are handled similarly, but for them the queue contains
130 * (power, raw offset) pairs. This queue must be initialized to
131 * {(0, 1), (0, 2), (0, 3), (0, 4)}.
133 * Bits from the binary range decoder must be used to disambiguate item types.
134 * The range decoder must hold two state variables: the range, which must
135 * initially be set to 0xffffffff, and the current code, which must initially be
136 * set to the first 32 bits read from the forwards bitstream. The range must be
137 * maintained above 0xffff; when it falls below 0xffff, both the range and code
138 * must be left-shifted by 16 bits and the low 16 bits of the code must be
139 * filled in with the next 16 bits from the forwards bitstream.
141 * To decode each bit, the binary range decoder requires a probability that is
142 * logically a real number between 0 and 1. Multiplying this probability by the
143 * current range and taking the floor gives the bound between the 0-bit region of
144 * the range and the 1-bit region of the range. However, in LZMS, probabilities
145 * are restricted to values of n/64 where n is an integer is between 1 and 63
146 * inclusively, so the implementation may use integer operations instead.
147 * Following calculation of the bound, if the current code is in the 0-bit
148 * region, the new range becomes the current code and the decoded bit is 0;
149 * otherwise, the bound must be subtracted from both the range and the code, and
150 * the decoded bit is 1. More information about range coding can be found at
151 * https://en.wikipedia.org/wiki/Range_encoding. Furthermore, note that the
152 * LZMA format also uses range coding and has public domain code available for
155 * The probability used to range-decode each bit must be taken from a table, of
156 * which one instance must exist for each distinct context, or "binary decision
157 * class", in which a range-decoded bit is needed. At each call of the range
158 * decoder, the appropriate probability must be obtained by indexing the
159 * appropriate probability table with the last 4 (in the context disambiguating
160 * literals from matches), 5 (in the context disambiguating LZ matches from
161 * delta matches), or 6 (in all other contexts) bits recently range-decoded in
162 * that context, ordered such that the most recently decoded bit is the
163 * low-order bit of the index.
165 * Furthermore, each probability entry itself is variable, as its value must be
166 * maintained as n/64 where n is the number of 0 bits in the most recently
167 * decoded 64 bits with that same entry. This allows the compressed
168 * representation to adapt to the input and use fewer bits to represent the most
169 * likely data; note that LZMA uses a similar scheme. Initially, the most
170 * recently 64 decoded bits for each probability entry are assumed to be
171 * 0x0000000055555555 (high order to low order); therefore, all probabilities
172 * are initially 48/64. During the course of decoding, each probability may be
173 * updated to as low as 0/64 (as a result of reading many consecutive 1 bits
174 * with that entry) or as high as 64/64 (as a result of reading many consecutive
175 * 0 bits with that entry); however, probabilities of 0/64 and 64/64 cannot be
176 * used as-is but rather must be adjusted to 1/64 and 63/64, respectively,
177 * before being used for range decoding.
179 * Representations of the LZMS items themselves must be read from the backwards
180 * bitstream. For this, there are 5 different Huffman codes used:
182 * - The literal code, used for decoding literal bytes. Each of the 256
183 * symbols represents a literal byte. This code must be rebuilt whenever
184 * 1024 symbols have been decoded with it.
186 * - The LZ offset code, used for decoding the offsets of standard LZ77
187 * matches. Each symbol represents an offset slot, which corresponds to a
188 * base value and some number of extra bits which must be read and added to
189 * the base value to reconstitute the full offset. The number of symbols in
190 * this code is the number of offset slots needed to represent all possible
191 * offsets in the uncompressed block. This code must be rebuilt whenever
192 * 1024 symbols have been decoded with it.
194 * - The length code, used for decoding length symbols. Each of the 54 symbols
195 * represents a length slot, which corresponds to a base value and some
196 * number of extra bits which must be read and added to the base value to
197 * reconstitute the full length. This code must be rebuilt whenever 512
198 * symbols have been decoded with it.
200 * - The delta offset code, used for decoding the raw offsets of delta matches.
201 * Each symbol corresponds to an offset slot, which corresponds to a base
202 * value and some number of extra bits which must be read and added to the
203 * base value to reconstitute the full raw offset. The number of symbols in
204 * this code is equal to the number of symbols in the LZ offset code. This
205 * code must be rebuilt whenever 1024 symbols have been decoded with it.
207 * - The delta power code, used for decoding the powers of delta matches. Each
208 * of the 8 symbols corresponds to a power. This code must be rebuilt
209 * whenever 512 symbols have been decoded with it.
211 * Initially, each Huffman code must be built assuming that each symbol in that
212 * code has frequency 1. Following that, each code must be rebuilt each time a
213 * certain number of symbols, as noted above, has been decoded with it. The
214 * symbol frequencies for a code must be halved after each rebuild of that code;
215 * this makes the codes adapt to the more recent data.
217 * Like other compression formats such as XPRESS, LZX, and DEFLATE, the LZMS
218 * format requires that all Huffman codes be constructed in canonical form.
219 * This form requires that same-length codewords be lexicographically ordered
220 * the same way as the corresponding symbols and that all shorter codewords
221 * lexicographically precede longer codewords. Such a code can be constructed
222 * directly from codeword lengths.
224 * Even with the canonical code restriction, the same frequencies can be used to
225 * construct multiple valid Huffman codes. Therefore, the decompressor needs to
226 * construct the right one. Specifically, the LZMS format requires that the
227 * Huffman code be constructed as if the well-known priority queue algorithm is
228 * used and frequency ties are always broken in favor of leaf nodes.
230 * Codewords in LZMS are guaranteed to not exceed 15 bits. The format otherwise
231 * places no restrictions on codeword length. Therefore, the Huffman code
232 * construction algorithm that a correct LZMS decompressor uses need not
233 * implement length-limited code construction. But if it does (e.g. by virtue
234 * of being shared among multiple compression algorithms), the details of how it
235 * does so are unimportant, provided that the maximum codeword length parameter
236 * is set to at least 15 bits.
238 * After all LZMS items have been decoded, the data must be postprocessed to
239 * translate absolute address encoded in x86 instructions into their original
240 * relative addresses.
242 * Details omitted above can be found in the code. Note that in the absence of
243 * an official specification there is no guarantee that this decompressor
244 * handles all possible cases.
251 #include "wimlib/compress_common.h"
252 #include "wimlib/decompress_common.h"
253 #include "wimlib/decompressor_ops.h"
254 #include "wimlib/error.h"
255 #include "wimlib/lzms_common.h"
256 #include "wimlib/util.h"
258 /* The TABLEBITS values can be changed; they only affect decoding speed. */
259 #define LZMS_LITERAL_TABLEBITS 10
260 #define LZMS_LENGTH_TABLEBITS 10
261 #define LZMS_LZ_OFFSET_TABLEBITS 10
262 #define LZMS_DELTA_OFFSET_TABLEBITS 10
263 #define LZMS_DELTA_POWER_TABLEBITS 8
265 struct lzms_range_decoder {
267 /* The relevant part of the current range. Although the logical range
268 * for range decoding is a very large integer, only a small portion
269 * matters at any given time, and it can be normalized (shifted left)
270 * whenever it gets too small. */
273 /* The current position in the range encoded by the portion of the input
277 /* Pointer to the next little-endian 16-bit integer in the compressed
278 * input data (reading forwards). */
281 /* Pointer to the end of the compressed input data. */
285 typedef u64 bitbuf_t;
287 struct lzms_input_bitstream {
289 /* Holding variable for bits that have been read from the compressed
290 * data. The bit ordering is high to low. */
293 /* Number of bits currently held in @bitbuf. */
296 /* Pointer to the one past the next little-endian 16-bit integer in the
297 * compressed input data (reading backwards). */
300 /* Pointer to the beginning of the compressed input data. */
304 /* Bookkeeping information for an adaptive Huffman code */
305 struct lzms_huffman_rebuild_info {
306 unsigned num_syms_until_rebuild;
308 unsigned rebuild_freq;
316 struct lzms_decompressor {
318 /* 'last_target_usages' is in union with everything else because it is
319 * only used for postprocessing. */
323 struct lzms_range_decoder rd;
324 struct lzms_input_bitstream is;
326 /* LRU queues for match sources */
327 u32 recent_lz_offsets[LZMS_NUM_LZ_REPS + 1];
328 u64 recent_delta_pairs[LZMS_NUM_DELTA_REPS + 1];
329 u32 pending_lz_offset;
330 u64 pending_delta_pair;
331 const u8 *lz_offset_still_pending;
332 const u8 *delta_pair_still_pending;
334 /* States and probability entries for item type disambiguation */
337 struct lzms_probability_entry main_probs[LZMS_NUM_MAIN_PROBS];
340 struct lzms_probability_entry match_probs[LZMS_NUM_MATCH_PROBS];
343 struct lzms_probability_entry lz_probs[LZMS_NUM_LZ_PROBS];
346 struct lzms_probability_entry delta_probs[LZMS_NUM_DELTA_PROBS];
348 u32 lz_rep_states[LZMS_NUM_LZ_REP_DECISIONS];
349 struct lzms_probability_entry lz_rep_probs[LZMS_NUM_LZ_REP_DECISIONS]
350 [LZMS_NUM_LZ_REP_PROBS];
352 u32 delta_rep_states[LZMS_NUM_DELTA_REP_DECISIONS];
353 struct lzms_probability_entry delta_rep_probs[LZMS_NUM_DELTA_REP_DECISIONS]
354 [LZMS_NUM_DELTA_REP_PROBS];
356 /* Huffman decoding */
358 u16 literal_decode_table[(1 << LZMS_LITERAL_TABLEBITS) +
359 (2 * LZMS_NUM_LITERAL_SYMS)]
360 _aligned_attribute(DECODE_TABLE_ALIGNMENT);
361 u32 literal_freqs[LZMS_NUM_LITERAL_SYMS];
362 struct lzms_huffman_rebuild_info literal_rebuild_info;
364 u16 lz_offset_decode_table[(1 << LZMS_LZ_OFFSET_TABLEBITS) +
365 ( 2 * LZMS_MAX_NUM_OFFSET_SYMS)]
366 _aligned_attribute(DECODE_TABLE_ALIGNMENT);
367 u32 lz_offset_freqs[LZMS_MAX_NUM_OFFSET_SYMS];
368 struct lzms_huffman_rebuild_info lz_offset_rebuild_info;
370 u16 length_decode_table[(1 << LZMS_LENGTH_TABLEBITS) +
371 (2 * LZMS_NUM_LENGTH_SYMS)]
372 _aligned_attribute(DECODE_TABLE_ALIGNMENT);
373 u32 length_freqs[LZMS_NUM_LENGTH_SYMS];
374 struct lzms_huffman_rebuild_info length_rebuild_info;
376 u16 delta_offset_decode_table[(1 << LZMS_DELTA_OFFSET_TABLEBITS) +
377 (2 * LZMS_MAX_NUM_OFFSET_SYMS)]
378 _aligned_attribute(DECODE_TABLE_ALIGNMENT);
379 u32 delta_offset_freqs[LZMS_MAX_NUM_OFFSET_SYMS];
380 struct lzms_huffman_rebuild_info delta_offset_rebuild_info;
382 u16 delta_power_decode_table[(1 << LZMS_DELTA_POWER_TABLEBITS) +
383 (2 * LZMS_NUM_DELTA_POWER_SYMS)]
384 _aligned_attribute(DECODE_TABLE_ALIGNMENT);
385 u32 delta_power_freqs[LZMS_NUM_DELTA_POWER_SYMS];
386 struct lzms_huffman_rebuild_info delta_power_rebuild_info;
388 u32 codewords[LZMS_MAX_NUM_SYMS];
389 u8 lens[LZMS_MAX_NUM_SYMS];
393 s32 last_target_usages[65536];
398 /* Initialize the input bitstream @is to read backwards from the compressed data
399 * buffer @in that is @count 16-bit integers long. */
401 lzms_input_bitstream_init(struct lzms_input_bitstream *is,
402 const le16 *in, size_t count)
406 is->next = in + count;
410 /* Ensure that at least @num_bits bits are in the bitbuffer variable.
411 * @num_bits cannot be more than 32. */
413 lzms_ensure_bits(struct lzms_input_bitstream *is, unsigned num_bits)
415 if (is->bitsleft >= num_bits)
418 if (likely(is->next != is->begin))
419 is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next)
420 << (sizeof(is->bitbuf) * 8 - is->bitsleft - 16);
423 if (likely(is->next != is->begin))
424 is->bitbuf |= (bitbuf_t)le16_to_cpu(*--is->next)
425 << (sizeof(is->bitbuf) * 8 - is->bitsleft - 16);
429 /* Get @num_bits bits from the bitbuffer variable. */
430 static inline bitbuf_t
431 lzms_peek_bits(struct lzms_input_bitstream *is, unsigned num_bits)
433 return (is->bitbuf >> 1) >> (sizeof(is->bitbuf) * 8 - num_bits - 1);
436 /* Remove @num_bits bits from the bitbuffer variable. */
438 lzms_remove_bits(struct lzms_input_bitstream *is, unsigned num_bits)
440 is->bitbuf <<= num_bits;
441 is->bitsleft -= num_bits;
444 /* Remove and return @num_bits bits from the bitbuffer variable. */
445 static inline bitbuf_t
446 lzms_pop_bits(struct lzms_input_bitstream *is, unsigned num_bits)
448 bitbuf_t bits = lzms_peek_bits(is, num_bits);
449 lzms_remove_bits(is, num_bits);
453 /* Read @num_bits bits from the input bitstream. */
454 static inline bitbuf_t
455 lzms_read_bits(struct lzms_input_bitstream *is, unsigned num_bits)
457 lzms_ensure_bits(is, num_bits);
458 return lzms_pop_bits(is, num_bits);
461 /* Initialize the range decoder @rd to read forwards from the compressed data
462 * buffer @in that is @count 16-bit integers long. */
464 lzms_range_decoder_init(struct lzms_range_decoder *rd,
465 const le16 *in, size_t count)
467 rd->range = 0xffffffff;
468 rd->code = ((u32)le16_to_cpu(in[0]) << 16) | le16_to_cpu(in[1]);
470 rd->end = in + count;
474 * Decode and return the next bit from the range decoder.
476 * @prob is the probability out of LZMS_PROBABILITY_DENOMINATOR that the next
477 * bit is 0 rather than 1.
480 lzms_range_decode_bit(struct lzms_range_decoder *rd, u32 prob)
484 /* Normalize if needed. */
485 if (rd->range <= 0xffff) {
488 if (likely(rd->next != rd->end))
489 rd->code |= le16_to_cpu(*rd->next++);
492 /* Based on the probability, calculate the bound between the 0-bit
493 * region and the 1-bit region of the range. */
494 bound = (rd->range >> LZMS_PROBABILITY_BITS) * prob;
496 if (rd->code < bound) {
497 /* Current code is in the 0-bit region of the range. */
501 /* Current code is in the 1-bit region of the range. */
509 * Decode a bit. This wraps around lzms_range_decode_bit() to handle using and
510 * updating the state and its corresponding probability entry.
513 lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
514 struct lzms_probability_entry *probs)
516 struct lzms_probability_entry *prob_entry;
520 /* Load the probability entry corresponding to the current state. */
521 prob_entry = &probs[*state_p];
523 /* Get the probability that the next bit is 0. */
524 prob = lzms_get_probability(prob_entry);
526 /* Decode the next bit. */
527 bit = lzms_range_decode_bit(rd, prob);
529 /* Update the state and probability entry based on the decoded bit. */
530 *state_p = ((*state_p << 1) | bit) & (num_states - 1);
531 lzms_update_probability_entry(prob_entry, bit);
533 /* Return the decoded bit. */
538 lzms_decode_main_bit(struct lzms_decompressor *d)
540 return lzms_decode_bit(&d->rd, &d->main_state,
541 LZMS_NUM_MAIN_PROBS, d->main_probs);
545 lzms_decode_match_bit(struct lzms_decompressor *d)
547 return lzms_decode_bit(&d->rd, &d->match_state,
548 LZMS_NUM_MATCH_PROBS, d->match_probs);
552 lzms_decode_lz_bit(struct lzms_decompressor *d)
554 return lzms_decode_bit(&d->rd, &d->lz_state,
555 LZMS_NUM_LZ_PROBS, d->lz_probs);
559 lzms_decode_delta_bit(struct lzms_decompressor *d)
561 return lzms_decode_bit(&d->rd, &d->delta_state,
562 LZMS_NUM_DELTA_PROBS, d->delta_probs);
566 lzms_decode_lz_rep_bit(struct lzms_decompressor *d, int idx)
568 return lzms_decode_bit(&d->rd, &d->lz_rep_states[idx],
569 LZMS_NUM_LZ_REP_PROBS, d->lz_rep_probs[idx]);
573 lzms_decode_delta_rep_bit(struct lzms_decompressor *d, int idx)
575 return lzms_decode_bit(&d->rd, &d->delta_rep_states[idx],
576 LZMS_NUM_DELTA_REP_PROBS, d->delta_rep_probs[idx]);
580 lzms_build_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info)
582 make_canonical_huffman_code(rebuild_info->num_syms,
583 LZMS_MAX_CODEWORD_LENGTH,
586 rebuild_info->codewords);
588 make_huffman_decode_table(rebuild_info->decode_table,
589 rebuild_info->num_syms,
590 rebuild_info->table_bits,
592 LZMS_MAX_CODEWORD_LENGTH);
594 rebuild_info->num_syms_until_rebuild = rebuild_info->rebuild_freq;
598 lzms_init_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info,
599 unsigned num_syms, unsigned rebuild_freq,
600 u32 *codewords, u8 *lens, u32 *freqs,
601 u16 *decode_table, unsigned table_bits)
603 rebuild_info->num_syms = num_syms;
604 rebuild_info->rebuild_freq = rebuild_freq;
605 rebuild_info->codewords = codewords;
606 rebuild_info->lens = lens;
607 rebuild_info->freqs = freqs;
608 rebuild_info->decode_table = decode_table;
609 rebuild_info->table_bits = table_bits;
610 lzms_init_symbol_frequencies(freqs, num_syms);
611 lzms_build_huffman_code(rebuild_info);
615 lzms_rebuild_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info)
617 lzms_build_huffman_code(rebuild_info);
618 lzms_dilute_symbol_frequencies(rebuild_info->freqs, rebuild_info->num_syms);
621 static inline unsigned
622 lzms_decode_huffman_symbol(struct lzms_input_bitstream *is, u16 decode_table[],
623 unsigned table_bits, u32 freqs[],
624 struct lzms_huffman_rebuild_info *rebuild_info)
630 lzms_ensure_bits(is, LZMS_MAX_CODEWORD_LENGTH);
632 /* Index the decode table by the next table_bits bits of the input. */
633 key_bits = lzms_peek_bits(is, table_bits);
634 entry = decode_table[key_bits];
635 if (likely(entry < 0xC000)) {
636 /* Fast case: The decode table directly provided the symbol and
637 * codeword length. The low 11 bits are the symbol, and the
638 * high 5 bits are the codeword length. */
639 lzms_remove_bits(is, entry >> 11);
642 /* Slow case: The codeword for the symbol is longer than
643 * table_bits, so the symbol does not have an entry directly in
644 * the first (1 << table_bits) entries of the decode table.
645 * Traverse the appropriate binary tree bit-by-bit in order to
646 * decode the symbol. */
647 lzms_remove_bits(is, table_bits);
649 key_bits = (entry & 0x3FFF) + lzms_pop_bits(is, 1);
650 } while ((entry = decode_table[key_bits]) >= 0xC000);
655 if (--rebuild_info->num_syms_until_rebuild == 0)
656 lzms_rebuild_huffman_code(rebuild_info);
661 lzms_decode_literal(struct lzms_decompressor *d)
663 return lzms_decode_huffman_symbol(&d->is,
664 d->literal_decode_table,
665 LZMS_LITERAL_TABLEBITS,
667 &d->literal_rebuild_info);
671 lzms_decode_lz_offset(struct lzms_decompressor *d)
673 unsigned slot = lzms_decode_huffman_symbol(&d->is,
674 d->lz_offset_decode_table,
675 LZMS_LZ_OFFSET_TABLEBITS,
677 &d->lz_offset_rebuild_info);
678 return lzms_offset_slot_base[slot] +
679 lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]);
683 lzms_decode_length(struct lzms_decompressor *d)
685 unsigned slot = lzms_decode_huffman_symbol(&d->is,
686 d->length_decode_table,
687 LZMS_LENGTH_TABLEBITS,
689 &d->length_rebuild_info);
690 u32 length = lzms_length_slot_base[slot];
691 unsigned num_extra_bits = lzms_extra_length_bits[slot];
692 /* Usually most lengths are short and have no extra bits. */
694 length += lzms_read_bits(&d->is, num_extra_bits);
699 lzms_decode_delta_offset(struct lzms_decompressor *d)
701 unsigned slot = lzms_decode_huffman_symbol(&d->is,
702 d->delta_offset_decode_table,
703 LZMS_DELTA_OFFSET_TABLEBITS,
704 d->delta_offset_freqs,
705 &d->delta_offset_rebuild_info);
706 return lzms_offset_slot_base[slot] +
707 lzms_read_bits(&d->is, lzms_extra_offset_bits[slot]);
711 lzms_decode_delta_power(struct lzms_decompressor *d)
713 return lzms_decode_huffman_symbol(&d->is,
714 d->delta_power_decode_table,
715 LZMS_DELTA_POWER_TABLEBITS,
716 d->delta_power_freqs,
717 &d->delta_power_rebuild_info);
720 /* Decode the series of literals and matches from the LZMS-compressed data.
721 * Return 0 if successful or -1 if the compressed data is invalid. */
723 lzms_decode_items(struct lzms_decompressor * const restrict d,
724 u8 * const restrict out, const size_t out_nbytes)
727 u8 * const out_end = out + out_nbytes;
729 while (out_next != out_end) {
731 if (!lzms_decode_main_bit(d)) {
734 *out_next++ = lzms_decode_literal(d);
736 } else if (!lzms_decode_match_bit(d)) {
743 if (d->pending_lz_offset != 0 &&
744 out_next != d->lz_offset_still_pending)
746 BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3);
747 d->recent_lz_offsets[3] = d->recent_lz_offsets[2];
748 d->recent_lz_offsets[2] = d->recent_lz_offsets[1];
749 d->recent_lz_offsets[1] = d->recent_lz_offsets[0];
750 d->recent_lz_offsets[0] = d->pending_lz_offset;
751 d->pending_lz_offset = 0;
754 if (!lzms_decode_lz_bit(d)) {
755 /* Explicit offset */
756 offset = lzms_decode_lz_offset(d);
760 BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3);
761 if (!lzms_decode_lz_rep_bit(d, 0)) {
762 offset = d->recent_lz_offsets[0];
763 d->recent_lz_offsets[0] = d->recent_lz_offsets[1];
764 d->recent_lz_offsets[1] = d->recent_lz_offsets[2];
765 d->recent_lz_offsets[2] = d->recent_lz_offsets[3];
766 } else if (!lzms_decode_lz_rep_bit(d, 1)) {
767 offset = d->recent_lz_offsets[1];
768 d->recent_lz_offsets[1] = d->recent_lz_offsets[2];
769 d->recent_lz_offsets[2] = d->recent_lz_offsets[3];
771 offset = d->recent_lz_offsets[2];
772 d->recent_lz_offsets[2] = d->recent_lz_offsets[3];
776 if (d->pending_lz_offset != 0) {
777 BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3);
778 d->recent_lz_offsets[3] = d->recent_lz_offsets[2];
779 d->recent_lz_offsets[2] = d->recent_lz_offsets[1];
780 d->recent_lz_offsets[1] = d->recent_lz_offsets[0];
781 d->recent_lz_offsets[0] = d->pending_lz_offset;
783 d->pending_lz_offset = offset;
785 length = lzms_decode_length(d);
787 if (unlikely(length > out_end - out_next))
789 if (unlikely(offset > out_next - out))
792 lz_copy(out_next, length, offset, out_end, LZMS_MIN_MATCH_LENGTH);
795 d->lz_offset_still_pending = out_next;
799 /* (See beginning of file for more information.) */
808 if (d->pending_delta_pair != 0 &&
809 out_next != d->delta_pair_still_pending)
811 BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3);
812 d->recent_delta_pairs[3] = d->recent_delta_pairs[2];
813 d->recent_delta_pairs[2] = d->recent_delta_pairs[1];
814 d->recent_delta_pairs[1] = d->recent_delta_pairs[0];
815 d->recent_delta_pairs[0] = d->pending_delta_pair;
816 d->pending_delta_pair = 0;
819 if (!lzms_decode_delta_bit(d)) {
820 /* Explicit offset */
821 power = lzms_decode_delta_power(d);
822 raw_offset = lzms_decode_delta_offset(d);
827 BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3);
828 if (!lzms_decode_delta_rep_bit(d, 0)) {
829 val = d->recent_delta_pairs[0];
830 d->recent_delta_pairs[0] = d->recent_delta_pairs[1];
831 d->recent_delta_pairs[1] = d->recent_delta_pairs[2];
832 d->recent_delta_pairs[2] = d->recent_delta_pairs[3];
833 } else if (!lzms_decode_delta_rep_bit(d, 1)) {
834 val = d->recent_delta_pairs[1];
835 d->recent_delta_pairs[1] = d->recent_delta_pairs[2];
836 d->recent_delta_pairs[2] = d->recent_delta_pairs[3];
838 val = d->recent_delta_pairs[2];
839 d->recent_delta_pairs[2] = d->recent_delta_pairs[3];
842 raw_offset = (u32)val;
845 if (d->pending_delta_pair != 0) {
846 BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3);
847 d->recent_delta_pairs[3] = d->recent_delta_pairs[2];
848 d->recent_delta_pairs[2] = d->recent_delta_pairs[1];
849 d->recent_delta_pairs[1] = d->recent_delta_pairs[0];
850 d->recent_delta_pairs[0] = d->pending_delta_pair;
852 d->pending_delta_pair = raw_offset | ((u64)power << 32);
854 length = lzms_decode_length(d);
856 span = (u32)1 << power;
857 offset = raw_offset << power;
859 /* raw_offset<<power overflows? */
860 if (unlikely(offset >> power != raw_offset))
863 /* offset+span overflows? */
864 if (unlikely(offset + span < offset))
867 /* buffer underrun? */
868 if (unlikely(offset + span > out_next - out))
871 /* buffer overrun? */
872 if (unlikely(length > out_end - out_next))
875 matchptr = out_next - offset;
877 *out_next = *matchptr + *(out_next - span) -
883 d->delta_pair_still_pending = out_next;
890 lzms_init_decompressor(struct lzms_decompressor *d, const void *in,
891 size_t in_nbytes, unsigned num_offset_slots)
893 /* Match offset LRU queues */
894 for (int i = 0; i < LZMS_NUM_LZ_REPS + 1; i++)
895 d->recent_lz_offsets[i] = i + 1;
896 for (int i = 0; i < LZMS_NUM_DELTA_REPS + 1; i++)
897 d->recent_delta_pairs[i] = i + 1;
898 d->pending_lz_offset = 0;
899 d->pending_delta_pair = 0;
903 lzms_range_decoder_init(&d->rd, in, in_nbytes / sizeof(le16));
906 lzms_init_probability_entries(d->main_probs, LZMS_NUM_MAIN_PROBS);
909 lzms_init_probability_entries(d->match_probs, LZMS_NUM_MATCH_PROBS);
912 lzms_init_probability_entries(d->lz_probs, LZMS_NUM_LZ_PROBS);
914 for (int i = 0; i < LZMS_NUM_LZ_REP_DECISIONS; i++) {
915 d->lz_rep_states[i] = 0;
916 lzms_init_probability_entries(d->lz_rep_probs[i],
917 LZMS_NUM_LZ_REP_PROBS);
921 lzms_init_probability_entries(d->delta_probs, LZMS_NUM_DELTA_PROBS);
923 for (int i = 0; i < LZMS_NUM_DELTA_REP_DECISIONS; i++) {
924 d->delta_rep_states[i] = 0;
925 lzms_init_probability_entries(d->delta_rep_probs[i],
926 LZMS_NUM_DELTA_REP_PROBS);
929 /* Huffman decoding */
931 lzms_input_bitstream_init(&d->is, in, in_nbytes / sizeof(le16));
933 lzms_init_huffman_code(&d->literal_rebuild_info,
934 LZMS_NUM_LITERAL_SYMS,
935 LZMS_LITERAL_CODE_REBUILD_FREQ,
939 d->literal_decode_table,
940 LZMS_LITERAL_TABLEBITS);
942 lzms_init_huffman_code(&d->lz_offset_rebuild_info,
944 LZMS_LZ_OFFSET_CODE_REBUILD_FREQ,
948 d->lz_offset_decode_table,
949 LZMS_LZ_OFFSET_TABLEBITS);
951 lzms_init_huffman_code(&d->length_rebuild_info,
952 LZMS_NUM_LENGTH_SYMS,
953 LZMS_LENGTH_CODE_REBUILD_FREQ,
957 d->length_decode_table,
958 LZMS_LENGTH_TABLEBITS);
960 lzms_init_huffman_code(&d->delta_offset_rebuild_info,
962 LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ,
965 d->delta_offset_freqs,
966 d->delta_offset_decode_table,
967 LZMS_DELTA_OFFSET_TABLEBITS);
969 lzms_init_huffman_code(&d->delta_power_rebuild_info,
970 LZMS_NUM_DELTA_POWER_SYMS,
971 LZMS_DELTA_POWER_CODE_REBUILD_FREQ,
974 d->delta_power_freqs,
975 d->delta_power_decode_table,
976 LZMS_DELTA_POWER_TABLEBITS);
980 lzms_create_decompressor(size_t max_bufsize, void **d_ret)
982 struct lzms_decompressor *d;
984 if (max_bufsize > LZMS_MAX_BUFFER_SIZE)
985 return WIMLIB_ERR_INVALID_PARAM;
987 d = ALIGNED_MALLOC(sizeof(struct lzms_decompressor),
988 DECODE_TABLE_ALIGNMENT);
990 return WIMLIB_ERR_NOMEM;
997 * Decompress @in_nbytes bytes of LZMS-compressed data at @in and write the
998 * uncompressed data, which had original size @out_nbytes, to @out. Return 0 if
999 * successful or -1 if the compressed data is invalid.
1002 lzms_decompress(const void *in, size_t in_nbytes, void *out, size_t out_nbytes,
1005 struct lzms_decompressor *d = _d;
1008 * Requirements on the compressed data:
1010 * 1. LZMS-compressed data is a series of 16-bit integers, so the
1011 * compressed data buffer cannot take up an odd number of bytes.
1012 * 2. To prevent poor performance on some architectures, we require that
1013 * the compressed data buffer is 2-byte aligned.
1014 * 3. There must be at least 4 bytes of compressed data, since otherwise
1015 * we cannot even initialize the range decoder.
1017 if ((in_nbytes & 1) || ((uintptr_t)in & 1) || (in_nbytes < 4))
1020 lzms_init_decompressor(d, in, in_nbytes,
1021 lzms_get_num_offset_slots(out_nbytes));
1023 if (lzms_decode_items(d, out, out_nbytes))
1026 lzms_x86_filter(out, out_nbytes, d->last_target_usages, true);
1031 lzms_free_decompressor(void *_d)
1033 struct lzms_decompressor *d = _d;
1038 const struct decompressor_ops lzms_decompressor_ops = {
1039 .create_decompressor = lzms_create_decompressor,
1040 .decompress = lzms_decompress,
1041 .free_decompressor = lzms_free_decompressor,