1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lzma_decoder.c
4 /// \brief LZMA decoder
6 // Copyright (C) 1999-2006 Igor Pavlov
7 // Copyright (C) 2007 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 // NOTE: If you want to keep the line length in 80 characters, set
22 // tab width to 4 or less in your editor when editing this file.
24 #include "lzma_common.h"
25 #include "lzma_decoder.h"
26 #include "lz_decoder.h"
27 #include "range_decoder.h"
30 /// REQUIRED_IN_BUFFER_SIZE is the number of required input bytes
31 /// for the worst case: longest match with longest distance.
32 /// LZMA_IN_BUFFER_SIZE must be larger than REQUIRED_IN_BUFFER_SIZE.
33 /// 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4 (align)
34 /// + 1 (rc_normalize)
36 /// \todo Is this correct for sure?
38 #define REQUIRED_IN_BUFFER_SIZE \
39 ((23 * (BIT_MODEL_TOTAL_BITS - MOVE_BITS + 1) + 26 + 9) / 8)
42 // Length decoders are easiest to have as macros, because they use range
43 // decoder macros, which use local variables rc_range and rc_code.
45 #define length_decode(target, len_decoder, pos_state) \
47 if_bit_0(len_decoder.choice) { \
48 update_bit_0(len_decoder.choice); \
49 target = MATCH_MIN_LEN; \
50 bittree_decode(target, len_decoder.low[pos_state], LEN_LOW_BITS); \
52 update_bit_1(len_decoder.choice); \
53 if_bit_0(len_decoder.choice2) { \
54 update_bit_0(len_decoder.choice2); \
55 target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
56 bittree_decode(target, len_decoder.mid[pos_state], LEN_MID_BITS); \
58 update_bit_1(len_decoder.choice2); \
59 target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \
60 bittree_decode(target, len_decoder.high, LEN_HIGH_BITS); \
66 #define length_decode_dummy(target, len_decoder, pos_state) \
68 if_bit_0(len_decoder.choice) { \
69 update_bit_0_dummy(); \
70 target = MATCH_MIN_LEN; \
71 bittree_decode_dummy(target, \
72 len_decoder.low[pos_state], LEN_LOW_BITS); \
74 update_bit_1_dummy(); \
75 if_bit_0(len_decoder.choice2) { \
76 update_bit_0_dummy(); \
77 target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
78 bittree_decode_dummy(target, len_decoder.mid[pos_state], \
81 update_bit_1_dummy(); \
82 target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \
83 bittree_decode_dummy(target, len_decoder.high, LEN_HIGH_BITS); \
92 probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
93 probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
94 probability high[LEN_HIGH_SYMBOLS];
95 } lzma_length_decoder;
99 /// Data of the next coder, if any.
100 lzma_next_coder next;
102 /// Sliding output window a.k.a. dictionary a.k.a. history buffer.
106 lzma_range_decoder rc;
109 lzma_lzma_state state;
110 uint32_t rep0; ///< Distance of the latest match
111 uint32_t rep1; ///< Distance of second latest match
112 uint32_t rep2; ///< Distance of third latest match
113 uint32_t rep3; ///< Distance of fourth latest match
116 uint32_t now_pos; // Lowest 32-bits are enough here.
118 lzma_literal_coder literal_coder;
120 /// If 1, it's a match. Otherwise it's a single 8-bit literal.
121 probability is_match[STATES][POS_STATES_MAX];
123 /// If 1, it's a repeated match. The distance is one of rep0 .. rep3.
124 probability is_rep[STATES];
126 /// If 0, distance of a repeated match is rep0.
127 /// Otherwise check is_rep1.
128 probability is_rep0[STATES];
130 /// If 0, distance of a repeated match is rep1.
131 /// Otherwise check is_rep2.
132 probability is_rep1[STATES];
134 /// If 0, distance of a repeated match is rep2. Otherwise it is rep3.
135 probability is_rep2[STATES];
137 /// If 1, the repeated match has length of one byte. Otherwise
138 /// the length is decoded from rep_len_decoder.
139 probability is_rep0_long[STATES][POS_STATES_MAX];
141 probability pos_slot_decoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
142 probability pos_decoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
143 probability pos_align_decoder[1 << ALIGN_BITS];
145 /// Length of a match
146 lzma_length_decoder match_len_decoder;
148 /// Length of a repeated match.
149 lzma_length_decoder rep_len_decoder;
151 /// True when we have produced at least one byte of output since the
152 /// beginning of the stream or the latest flush marker.
153 bool has_produced_output;
157 /// \brief Check if the next iteration of the decoder loop can be run.
159 /// \note There must always be REQUIRED_IN_BUFFER_SIZE bytes
162 static bool lzma_attribute((pure))
163 decode_dummy(const lzma_coder *restrict coder,
164 const uint8_t *restrict in, size_t in_pos_local,
165 const size_t in_size, lzma_range_decoder rc,
166 uint32_t state, uint32_t rep0, const uint32_t now_pos)
171 const uint32_t pos_state = now_pos & coder->pos_mask;
173 if_bit_0(coder->is_match[state][pos_state]) {
174 // It's a literal i.e. a single 8-bit byte.
176 update_bit_0_dummy();
178 const probability *subcoder = literal_get_subcoder(
179 coder->literal_coder, now_pos, lz_get_byte(coder->lz, 0));
182 if (is_literal_state(state)) {
183 // Decode literal without match byte.
185 if_bit_0(subcoder[symbol]) {
186 update_bit_0_dummy();
189 update_bit_1_dummy();
190 symbol = (symbol << 1) | 1;
192 } while (symbol < 0x100);
195 // Decode literal with match byte.
196 uint32_t match_byte = lz_get_byte(coder->lz, rep0);
197 uint32_t subcoder_offset = 0x100;
201 const uint32_t match_bit = match_byte & subcoder_offset;
202 const uint32_t subcoder_index
203 = subcoder_offset + match_bit + symbol;
205 if_bit_0(subcoder[subcoder_index]) {
206 update_bit_0_dummy();
208 subcoder_offset &= ~match_bit;
210 update_bit_1_dummy();
211 symbol = (symbol << 1) | 1;
212 subcoder_offset &= match_bit;
214 } while (symbol < 0x100);
220 update_bit_1_dummy();
223 if_bit_0(coder->is_rep[state]) {
224 update_bit_0_dummy();
225 length_decode_dummy(len, coder->match_len_decoder, pos_state);
227 const uint32_t len_to_pos_state = get_len_to_pos_state(len);
228 uint32_t pos_slot = 0;
229 bittree_decode_dummy(pos_slot,
230 coder->pos_slot_decoder[len_to_pos_state], POS_SLOT_BITS);
231 assert(pos_slot <= 63);
233 if (pos_slot >= START_POS_MODEL_INDEX) {
234 uint32_t direct_bits = (pos_slot >> 1) - 1;
235 assert(direct_bits >= 1 && direct_bits <= 31);
236 rep0 = 2 | (pos_slot & 1);
238 if (pos_slot < END_POS_MODEL_INDEX) {
239 assert(direct_bits <= 5);
240 rep0 <<= direct_bits;
242 // -1 is fine, because bittree_reverse_decode()
243 // starts from table index [1] (not [0]).
244 assert((int32_t)(rep0 - pos_slot - 1) >= -1);
245 assert((int32_t)(rep0 - pos_slot - 1) <= 82);
246 // We add the result to rep0, so rep0
247 // must not be part of second argument
249 const int32_t offset = rep0 - pos_slot - 1;
250 bittree_reverse_decode_dummy(coder->pos_decoders + offset,
253 assert(pos_slot >= 14);
254 assert(direct_bits >= 6);
255 direct_bits -= ALIGN_BITS;
256 assert(direct_bits >= 2);
257 rc_decode_direct_dummy(direct_bits);
259 bittree_reverse_decode_dummy(coder->pos_align_decoder,
265 update_bit_1_dummy();
267 if_bit_0(coder->is_rep0[state]) {
268 update_bit_0_dummy();
270 if_bit_0(coder->is_rep0_long[state][pos_state]) {
271 update_bit_0_dummy();
274 update_bit_1_dummy();
278 update_bit_1_dummy();
280 if_bit_0(coder->is_rep1[state]) {
281 update_bit_0_dummy();
283 update_bit_1_dummy();
285 if_bit_0(coder->is_rep2[state]) {
286 update_bit_0_dummy();
288 update_bit_1_dummy();
293 length_decode_dummy(len, coder->rep_len_decoder, pos_state);
299 return in_pos_local <= in_size;
304 decode_real(lzma_coder *restrict coder, const uint8_t *restrict in,
305 size_t *restrict in_pos, size_t in_size, bool has_safe_buffer)
311 if (!rc_read_init(&coder->rc, in, in_pos, in_size))
318 // Making local copies of often-used variables improves both
319 // speed and readability.
322 rc_to_local(coder->rc);
325 uint32_t state = coder->state;
326 uint32_t rep0 = coder->rep0;
327 uint32_t rep1 = coder->rep1;
328 uint32_t rep2 = coder->rep2;
329 uint32_t rep3 = coder->rep3;
332 uint32_t now_pos = coder->now_pos;
333 bool has_produced_output = coder->has_produced_output;
335 // Variables derived from decoder settings
336 const uint32_t pos_mask = coder->pos_mask;
338 size_t in_pos_local = *in_pos; // Local copy
340 if (in_size <= REQUIRED_IN_BUFFER_SIZE)
343 in_limit = in_size - REQUIRED_IN_BUFFER_SIZE;
346 while (coder->lz.pos < coder->lz.limit
347 && (in_pos_local < in_limit || (has_safe_buffer
348 && decode_dummy(coder, in, in_pos_local, in_size,
349 rc, state, rep0, now_pos)))) {
351 /////////////////////
352 // Actual decoding //
353 /////////////////////
355 const uint32_t pos_state = now_pos & pos_mask;
357 if_bit_0(coder->is_match[state][pos_state]) {
358 update_bit_0(coder->is_match[state][pos_state]);
360 // It's a literal i.e. a single 8-bit byte.
362 probability *subcoder = literal_get_subcoder(coder->literal_coder,
363 now_pos, lz_get_byte(coder->lz, 0));
366 if (is_literal_state(state)) {
367 // Decode literal without match byte.
369 if_bit_0(subcoder[symbol]) {
370 update_bit_0(subcoder[symbol]);
373 update_bit_1(subcoder[symbol]);
374 symbol = (symbol << 1) | 1;
376 } while (symbol < 0x100);
379 // Decode literal with match byte.
381 // The usage of subcoder_offset allows omitting some
382 // branches, which should give tiny speed improvement on
383 // some CPUs. subcoder_offset gets set to zero if match_bit
385 uint32_t match_byte = lz_get_byte(coder->lz, rep0);
386 uint32_t subcoder_offset = 0x100;
390 const uint32_t match_bit = match_byte & subcoder_offset;
391 const uint32_t subcoder_index
392 = subcoder_offset + match_bit + symbol;
394 if_bit_0(subcoder[subcoder_index]) {
395 update_bit_0(subcoder[subcoder_index]);
397 subcoder_offset &= ~match_bit;
399 update_bit_1(subcoder[subcoder_index]);
400 symbol = (symbol << 1) | 1;
401 subcoder_offset &= match_bit;
403 } while (symbol < 0x100);
406 // Put the decoded byte to the dictionary, update the
407 // decoder state, and start a new decoding loop.
408 coder->lz.dict[coder->lz.pos++] = (uint8_t)(symbol);
410 update_literal(state);
411 has_produced_output = true;
415 // Instead of a new byte we are going to get a byte range
416 // (distance and length) which will be repeated from our
419 update_bit_1(coder->is_match[state][pos_state]);
422 if_bit_0(coder->is_rep[state]) {
423 update_bit_0(coder->is_rep[state]);
425 // Not a repeated match
427 // We will decode a new distance and store
428 // the value to distance.
430 // Decode the length of the match.
431 length_decode(len, coder->match_len_decoder, pos_state);
435 const uint32_t len_to_pos_state = get_len_to_pos_state(len);
436 uint32_t pos_slot = 0;
437 bittree_decode(pos_slot,
438 coder->pos_slot_decoder[len_to_pos_state], POS_SLOT_BITS);
439 assert(pos_slot <= 63);
441 if (pos_slot >= START_POS_MODEL_INDEX) {
442 uint32_t direct_bits = (pos_slot >> 1) - 1;
443 assert(direct_bits >= 1 && direct_bits <= 30);
444 uint32_t distance = 2 | (pos_slot & 1);
446 if (pos_slot < END_POS_MODEL_INDEX) {
447 assert(direct_bits <= 5);
448 distance <<= direct_bits;
449 assert(distance <= 96);
450 // -1 is fine, because
451 // bittree_reverse_decode()
452 // starts from table index [1]
454 assert((int32_t)(distance - pos_slot - 1) >= -1);
455 assert((int32_t)(distance - pos_slot - 1) <= 82);
456 // We add the result to distance, so distance
457 // must not be part of second argument
459 const int32_t offset = distance - pos_slot - 1;
460 bittree_reverse_decode(distance, coder->pos_decoders + offset,
463 assert(pos_slot >= 14);
464 assert(direct_bits >= 6);
465 direct_bits -= ALIGN_BITS;
466 assert(direct_bits >= 2);
467 rc_decode_direct(distance, direct_bits);
468 distance <<= ALIGN_BITS;
470 bittree_reverse_decode(distance, coder->pos_align_decoder,
473 if (distance == UINT32_MAX) {
474 if (len == LEN_SPECIAL_EOPM) {
475 // End of Payload Marker found.
476 coder->lz.eopm_detected = true;
479 } else if (len == LEN_SPECIAL_FLUSH) {
480 // Flush marker detected. We must have produced
481 // at least one byte of output since the previous
482 // flush marker or the beginning of the stream.
483 // This is to prevent hanging the decoder with
484 // malicious input files.
485 if (!has_produced_output)
488 has_produced_output = false;
490 // We know that we have enough input to call
491 // this macro, because it is tested at the
492 // end of decode_dummy().
497 // If we don't have enough input here, we jump
498 // out of the loop. Note that while there is a
499 // useless call to rc_normalize(), it does nothing
500 // since we have just reset the range decoder.
501 if (!rc_read_init(&rc, in, &in_pos_local, in_size))
512 // The latest three match distances are kept in
513 // memory in case there are repeated matches.
527 update_bit_1(coder->is_rep[state]);
531 // The match distance is a value that we have had
532 // earlier. The latest four match distances are
533 // available as rep0, rep1, rep2 and rep3. We will
534 // now decode which of them is the new distance.
536 if_bit_0(coder->is_rep0[state]) {
537 update_bit_0(coder->is_rep0[state]);
539 // The distance is rep0.
541 if_bit_0(coder->is_rep0_long[state][pos_state]) {
542 update_bit_0(coder->is_rep0_long[state][pos_state]);
544 update_short_rep(state);
546 // Repeat exactly one byte and start a new decoding loop.
547 // Note that rep0 is known to have a safe value, thus we
548 // don't need to check if we are wrapping the dictionary
549 // when it isn't full yet.
550 if (unlikely(lz_is_empty(coder->lz)))
553 coder->lz.dict[coder->lz.pos]
554 = lz_get_byte(coder->lz, rep0);
557 has_produced_output = true;
561 update_bit_1(coder->is_rep0_long[state][pos_state]);
563 // Repeating more than one byte at
568 update_bit_1(coder->is_rep0[state]);
570 // The distance is rep1, rep2 or rep3. Once
571 // we find out which one of these three, it
572 // is stored to rep0 and rep1, rep2 and rep3
573 // are updated accordingly.
577 if_bit_0(coder->is_rep1[state]) {
578 update_bit_0(coder->is_rep1[state]);
581 update_bit_1(coder->is_rep1[state]);
583 if_bit_0(coder->is_rep2[state]) {
584 update_bit_0(coder->is_rep2[state]);
587 update_bit_1(coder->is_rep2[state]);
599 update_long_rep(state);
601 // Decode the length of the repeated match.
602 length_decode(len, coder->rep_len_decoder, pos_state);
606 /////////////////////////////////
607 // Repeat from history buffer. //
608 /////////////////////////////////
610 // The length is always between these limits. There is no way
611 // to trigger the algorithm to set len outside this range.
612 assert(len >= MATCH_MIN_LEN);
613 assert(len <= MATCH_MAX_LEN);
616 has_produced_output = true;
618 // Repeat len bytes from distance of rep0.
619 if (!lzma_lz_out_repeat(&coder->lz, rep0, len))
626 /////////////////////////////////
627 // Update the *data structure. //
628 /////////////////////////////////
631 rc_from_local(coder->rc);
634 coder->state = state;
641 coder->now_pos = now_pos;
642 coder->has_produced_output = has_produced_output;
643 *in_pos = in_pos_local;
650 lzma_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
652 lzma_next_coder_end(&coder->next, allocator);
653 lzma_lz_decoder_end(&coder->lz, allocator);
654 lzma_free(coder, allocator);
660 lzma_lzma_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
661 const lzma_filter_info *filters)
663 // LZMA can only be the last filter in the chain.
664 assert(filters[1].init == NULL);
666 // Validate pos_bits. Other options are validated by the
667 // respective initialization functions.
668 const lzma_options_lzma *options = filters[0].options;
669 if (options->pos_bits > LZMA_POS_BITS_MAX)
670 return LZMA_HEADER_ERROR;
672 // Allocate memory for the decoder if needed.
673 if (next->coder == NULL) {
674 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
675 if (next->coder == NULL)
676 return LZMA_MEM_ERROR;
678 next->code = &lzma_lz_decode;
679 next->end = &lzma_decoder_end;
680 next->coder->next = LZMA_NEXT_CODER_INIT;
681 next->coder->lz = LZMA_LZ_DECODER_INIT;
684 // Store the pos_bits and calculate pos_mask.
685 next->coder->pos_bits = options->pos_bits;
686 next->coder->pos_mask = (1U << next->coder->pos_bits) - 1;
688 // Initialize the literal decoder.
689 return_if_error(lzma_literal_init(&next->coder->literal_coder,
690 options->literal_context_bits,
691 options->literal_pos_bits));
693 // Allocate and initialize the LZ decoder.
694 return_if_error(lzma_lz_decoder_reset(&next->coder->lz, allocator,
695 &decode_real, options->dictionary_size,
699 next->coder->state = 0;
700 next->coder->rep0 = 0;
701 next->coder->rep1 = 0;
702 next->coder->rep2 = 0;
703 next->coder->rep3 = 0;
704 next->coder->pos_bits = options->pos_bits;
705 next->coder->pos_mask = (1 << next->coder->pos_bits) - 1;
706 next->coder->now_pos = 0;
709 rc_reset(next->coder->rc);
711 // Bit and bittree decoders
712 for (uint32_t i = 0; i < STATES; ++i) {
713 for (uint32_t j = 0; j <= next->coder->pos_mask; ++j) {
714 bit_reset(next->coder->is_match[i][j]);
715 bit_reset(next->coder->is_rep0_long[i][j]);
718 bit_reset(next->coder->is_rep[i]);
719 bit_reset(next->coder->is_rep0[i]);
720 bit_reset(next->coder->is_rep1[i]);
721 bit_reset(next->coder->is_rep2[i]);
724 for (uint32_t i = 0; i < LEN_TO_POS_STATES; ++i)
725 bittree_reset(next->coder->pos_slot_decoder[i], POS_SLOT_BITS);
727 for (uint32_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
728 bit_reset(next->coder->pos_decoders[i]);
730 bittree_reset(next->coder->pos_align_decoder, ALIGN_BITS);
732 // Len decoders (also bit/bittree)
733 const uint32_t num_pos_states = 1 << next->coder->pos_bits;
734 bit_reset(next->coder->match_len_decoder.choice);
735 bit_reset(next->coder->match_len_decoder.choice2);
736 bit_reset(next->coder->rep_len_decoder.choice);
737 bit_reset(next->coder->rep_len_decoder.choice2);
739 for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
740 bittree_reset(next->coder->match_len_decoder.low[pos_state],
742 bittree_reset(next->coder->match_len_decoder.mid[pos_state],
745 bittree_reset(next->coder->rep_len_decoder.low[pos_state],
747 bittree_reset(next->coder->rep_len_decoder.mid[pos_state],
751 bittree_reset(next->coder->match_len_decoder.high, LEN_HIGH_BITS);
752 bittree_reset(next->coder->rep_len_decoder.high, LEN_HIGH_BITS);
754 next->coder->has_produced_output = false;
761 lzma_lzma_decoder_uncompressed_size(
762 lzma_next_coder *next, lzma_vli uncompressed_size)
764 next->coder->lz.uncompressed_size = uncompressed_size;
770 lzma_lzma_decode_properties(lzma_options_lzma *options, uint8_t byte)
772 if (byte > (4 * 5 + 4) * 9 + 8)
775 // See the file format specification to understand this.
776 options->pos_bits = byte / (9 * 5);
777 byte -= options->pos_bits * 9 * 5;
778 options->literal_pos_bits = byte / 9;
779 options->literal_context_bits = byte - options->literal_pos_bits * 9;
781 return options->literal_context_bits + options->literal_pos_bits
782 > LZMA_LITERAL_BITS_MAX;