aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/lzma
diff options
context:
space:
mode:
Diffstat (limited to 'src/liblzma/lzma')
-rw-r--r--src/liblzma/lzma/lzma_decoder.c720
1 files changed, 509 insertions, 211 deletions
diff --git a/src/liblzma/lzma/lzma_decoder.c b/src/liblzma/lzma/lzma_decoder.c
index 2e8393d6..6203bae9 100644
--- a/src/liblzma/lzma/lzma_decoder.c
+++ b/src/liblzma/lzma/lzma_decoder.c
@@ -7,6 +7,7 @@
///
// Authors: Igor Pavlov
// Lasse Collin
+// Jia Tan
//
///////////////////////////////////////////////////////////////////////////////
@@ -21,8 +22,12 @@
# pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
#endif
+// Minimum number of input bytes to safely decode one LZMA symbol.
+// The worst case is that we decode 22 bits using probabilities and 26
+// direct bits. This may decode at maximum 20 bytes of input plus one
+// extra byte after the final EOPM normalization.
+#define LZMA_IN_REQUIRED 21
-#ifdef HAVE_SMALL
// Macros for (somewhat) size-optimized code.
// This is used to decode the match length (how many bytes must be repeated
@@ -193,22 +198,26 @@ typedef struct {
enum {
SEQ_NORMALIZE,
SEQ_IS_MATCH,
- seq_8(SEQ_LITERAL),
- seq_8(SEQ_LITERAL_MATCHED),
+ SEQ_LITERAL,
+ SEQ_LITERAL_MATCHED,
SEQ_LITERAL_WRITE,
SEQ_IS_REP,
- seq_len(SEQ_MATCH_LEN),
- seq_6(SEQ_DIST_SLOT),
+ SEQ_MATCH_LEN_CHOICE,
+ SEQ_MATCH_LEN_CHOICE2,
+ SEQ_MATCH_LEN_BITTREE,
+ SEQ_DIST_SLOT,
SEQ_DIST_MODEL,
SEQ_DIRECT,
- seq_4(SEQ_ALIGN),
+ SEQ_ALIGN,
SEQ_EOPM,
SEQ_IS_REP0,
SEQ_SHORTREP,
SEQ_IS_REP0_LONG,
SEQ_IS_REP1,
SEQ_IS_REP2,
- seq_len(SEQ_REP_LEN),
+ SEQ_REP_LEN_CHOICE,
+ SEQ_REP_LEN_CHOICE2,
+ SEQ_REP_LEN_BITTREE,
SEQ_COPY,
} sequence;
@@ -309,8 +318,42 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
might_finish_without_eopm = true;
}
- // The main decoder loop. The "switch" is used to restart the decoder at
- // correct location. Once restarted, the "switch" is no longer used.
+ // Lookup table used to update the literal state.
+ // Compared to other state updates, this would need two branches.
+ // The lookup table is used by both Resumable and Non-resumable modes.
+ static const lzma_lzma_state next_state[] = {
+ STATE_LIT_LIT,
+ STATE_LIT_LIT,
+ STATE_LIT_LIT,
+ STATE_LIT_LIT,
+ STATE_MATCH_LIT_LIT,
+ STATE_REP_LIT_LIT,
+ STATE_SHORTREP_LIT_LIT,
+ STATE_MATCH_LIT,
+ STATE_REP_LIT,
+ STATE_SHORTREP_LIT,
+ STATE_MATCH_LIT,
+ STATE_REP_LIT
+ };
+
+ // The main decoder loop. The "switch" is used to resume the decoder at
+ // correct location. Once resumed, the "switch" is no longer used.
+ // The decoder loops is split into two modes:
+ //
+ // 1 - Non-resumable mode (fast). This is used when it is guaranteed
+ // there is enough input to decode the next symbol. If the output
+ // limit is reached, then the decoder loop will save the place
+ // for the resumable mode to continue. This mode is not used if
+ // HAVE_SMALL is defined. This is faster than Resumable mode
+ // because it reduces the number of branches needed and allows
+ // for more compiler optimizations.
+ //
+ // 2 - Resumable mode (slow). This is used when a previous decoder
+ // loop did not have enough space in the input or output buffers
+ // to complete. It uses sequence enum values to set remind
+ // coder->sequence where to resume in the decoder loop. This
+ // is the only mode used when HAVE_SMALL is defined.
+
switch (coder->sequence)
while (true) {
// Calculate new pos_state. This is skipped on the first loop
@@ -318,40 +361,32 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
// variables.
pos_state = dict.pos & pos_mask;
- case SEQ_NORMALIZE:
- case SEQ_IS_MATCH:
- if (unlikely(might_finish_without_eopm
- && dict.pos == dict.limit)) {
- // In rare cases there is a useless byte that needs
- // to be read anyway.
- rc_normalize(SEQ_NORMALIZE);
+#ifndef HAVE_SMALL
- // If the range decoder state is such that we can
- // be at the end of the LZMA stream, then the
- // decoding is finished.
- if (rc_is_finished(rc)) {
- ret = LZMA_STREAM_END;
- goto out;
- }
+ ///////////////////////////////
+ // Non-resumable Mode (fast) //
+ ///////////////////////////////
- // If the caller hasn't allowed EOPM to be present
- // together with known uncompressed size, then the
- // LZMA stream is corrupt.
- if (!coder->allow_eopm) {
- ret = LZMA_DATA_ERROR;
- goto out;
- }
+ // If there is not enough room for another LZMA symbol
+ // go to Resumable mode.
+ if (rc_in_pos + LZMA_IN_REQUIRED > in_size
+ || dict.pos == dict.limit)
+ goto slow;
- // Otherwise continue decoding with the expectation
- // that the next LZMA symbol is EOPM.
- eopm_is_valid = true;
- }
+ // Decode the first bit from the next LZMA symbol.
+ // If the bit is a 0, then we handle it as a literal.
+ // If the bit is a 1, then it is a match of previously
+ // decoded data.
+ rc_if_0(coder->is_match[state][pos_state]) {
+ /////////////////////
+ // Decode literal. //
+ /////////////////////
- rc_if_0(coder->is_match[state][pos_state], SEQ_IS_MATCH) {
+ // Update the RC that we have decoded a 0.
rc_update_0(coder->is_match[state][pos_state]);
- // It's a literal i.e. a single 8-bit byte.
-
+ // Get the correct probability array from lp and
+ // lc params.
probs = literal_subcoder(coder->literal,
literal_context_bits, literal_pos_mask,
dict.pos, dict_get(&dict, 0));
@@ -359,21 +394,17 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
if (is_literal_state(state)) {
// Decode literal without match byte.
-#ifdef HAVE_SMALL
- case SEQ_LITERAL:
- do {
- rc_bit(probs[symbol], , , SEQ_LITERAL);
- } while (symbol < (1 << 8));
-#else
- rc_bit_case(probs[symbol], , , SEQ_LITERAL0);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL1);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL2);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL3);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL4);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL5);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL6);
- rc_bit_case(probs[symbol], , , SEQ_LITERAL7);
-#endif
+ // We need to decode 8 bits, so instead
+ // of looping from 1 - 8, we unroll the
+ // loop for a speed optimization.
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
} else {
// Decode literal with match byte.
//
@@ -381,6 +412,7 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
// ("match byte") to "len" to minimize the
// number of variables we need to store
// between decoder calls.
+
len = (uint32_t)(dict_get(&dict, rep0)) << 1;
// The usage of "offset" allows omitting some
@@ -389,99 +421,68 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
// set to zero if match_bit didn't match.
offset = 0x100;
-#ifdef HAVE_SMALL
- case SEQ_LITERAL_MATCHED:
- do {
- const uint32_t match_bit
- = len & offset;
- const uint32_t subcoder_index
- = offset + match_bit
- + symbol;
-
- rc_bit(probs[subcoder_index],
- offset &= ~match_bit,
- offset &= match_bit,
- SEQ_LITERAL_MATCHED);
-
- // It seems to be faster to do this
- // here instead of putting it to the
- // beginning of the loop and then
- // putting the "case" in the middle
- // of the loop.
- len <<= 1;
-
- } while (symbol < (1 << 8));
-#else
// Unroll the loop.
uint32_t match_bit;
uint32_t subcoder_index;
-# define d(seq) \
- case seq: \
+# define decode_with_match_bit \
match_bit = len & offset; \
subcoder_index = offset + match_bit + symbol; \
rc_bit(probs[subcoder_index], \
offset &= ~match_bit, \
- offset &= match_bit, \
- seq)
+ offset &= match_bit)
- d(SEQ_LITERAL_MATCHED0);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED1);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED2);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED3);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED4);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED5);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED6);
+ decode_with_match_bit;
len <<= 1;
- d(SEQ_LITERAL_MATCHED7);
-# undef d
-#endif
+ decode_with_match_bit;
+# undef decode_match_bit
}
- //update_literal(state);
- // Use a lookup table to update to literal state,
- // since compared to other state updates, this would
- // need two branches.
- static const lzma_lzma_state next_state[] = {
- STATE_LIT_LIT,
- STATE_LIT_LIT,
- STATE_LIT_LIT,
- STATE_LIT_LIT,
- STATE_MATCH_LIT_LIT,
- STATE_REP_LIT_LIT,
- STATE_SHORTREP_LIT_LIT,
- STATE_MATCH_LIT,
- STATE_REP_LIT,
- STATE_SHORTREP_LIT,
- STATE_MATCH_LIT,
- STATE_REP_LIT
- };
state = next_state[state];
- case SEQ_LITERAL_WRITE:
- if (unlikely(dict_put(&dict, symbol))) {
- coder->sequence = SEQ_LITERAL_WRITE;
- goto out;
- }
-
+ // Write decoded literal to dictionary
+ dict_put(&dict, symbol);
continue;
}
- // Instead of a new byte we are going to get a byte range
- // (distance and length) which will be repeated from our
- // output history.
+ ///////////////////
+ // Decode match. //
+ ///////////////////
+
+ // Instead of a new byte we are going to decode a
+ // distance-length pair. The distance represents how far
+ // back in the dictionary to begin copying. The length
+ // represents how many bytes to copy.
rc_update_1(coder->is_match[state][pos_state]);
- case SEQ_IS_REP:
- rc_if_0(coder->is_rep[state], SEQ_IS_REP) {
- // Not a repeated match
+ rc_if_0(coder->is_rep[state]) {
+ ///////////////////
+ // Simple match. //
+ ///////////////////
+
+ // Not a repeated match. In this case,
+ // the length (how many bytes to copy) must be
+ // decoded first. Then, the distance (where to
+ // start copying) is decoded.
+ //
+ // This is also how we know when we are done
+ // decoding. If the distance decodes to UINT32_MAX,
+ // then we know to stop decoding (end of payload
+ // marker).
+
rc_update_0(coder->is_rep[state]);
update_match(state);
@@ -492,45 +493,50 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
rep1 = rep0;
// Decode the length of the match.
- len_decode(len, coder->match_len_decoder,
- pos_state, SEQ_MATCH_LEN);
+ len_decode_fast(len, coder->match_len_decoder,
+ pos_state);
+
+ // Next, decode the distance into rep0.
- // Prepare to decode the highest two bits of the
- // match distance.
+ // The next 6 bits determine how to decode the
+ // rest of the distance.
probs = coder->dist_slot[get_dist_state(len)];
symbol = 1;
-#ifdef HAVE_SMALL
- case SEQ_DIST_SLOT:
- do {
- rc_bit(probs[symbol], , , SEQ_DIST_SLOT);
- } while (symbol < DIST_SLOTS);
-#else
- rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT0);
- rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT1);
- rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT2);
- rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT3);
- rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT4);
- rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT5);
-#endif
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+ rc_bit(probs[symbol], , );
+
// Get rid of the highest bit that was needed for
// indexing of the probability array.
symbol -= DIST_SLOTS;
assert(symbol <= 63);
if (symbol < DIST_MODEL_START) {
- // Match distances [0, 3] have only two bits.
+ // If the decoded symbol is < DIST_MODEL_START
+ // then we use its value directly as the
+ // match distance. No other bits are needed.
+ // The only possible distance values
+ // are [0, 3].
rep0 = symbol;
} else {
- // Decode the lowest [1, 29] bits of
- // the match distance.
+ // Use the first two bits of symbol as the
+ // highest bits of the match distance.
+
+ // "limit" represents the number of low bits
+ // to decode.
limit = (symbol >> 1) - 1;
assert(limit >= 1 && limit <= 30);
rep0 = 2 + (symbol & 1);
if (symbol < DIST_MODEL_END) {
- // Prepare to decode the low bits for
- // a distance of [4, 127].
+ // When symbol is > DIST_MODEL_START,
+ // but symbol < DIST_MODEL_END, then
+ // it can decode distances between
+ // [4, 127].
assert(limit <= 5);
rep0 <<= limit;
assert(rep0 <= 96);
@@ -548,52 +554,39 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
- symbol - 1;
symbol = 1;
offset = 0;
- case SEQ_DIST_MODEL:
-#ifdef HAVE_SMALL
- do {
- rc_bit(probs[symbol], ,
- rep0 += 1U << offset,
- SEQ_DIST_MODEL);
- } while (++offset < limit);
-#else
+
switch (limit) {
case 5:
assert(offset == 0);
rc_bit(probs[symbol], ,
- rep0 += 1U,
- SEQ_DIST_MODEL);
+ rep0 += 1U);
++offset;
--limit;
case 4:
rc_bit(probs[symbol], ,
- rep0 += 1U << offset,
- SEQ_DIST_MODEL);
+ rep0 += 1U << offset);
++offset;
--limit;
case 3:
rc_bit(probs[symbol], ,
- rep0 += 1U << offset,
- SEQ_DIST_MODEL);
+ rep0 += 1U << offset);
++offset;
--limit;
case 2:
rc_bit(probs[symbol], ,
- rep0 += 1U << offset,
- SEQ_DIST_MODEL);
+ rep0 += 1U << offset);
++offset;
--limit;
case 1:
// We need "symbol" only for
// indexing the probability
// array, thus we can use
- // rc_bit_last() here to omit
- // the unneeded updating of
- // "symbol".
+ // rc_bit_last() here to
+ // omit the unneeded updating
+ // of "symbol".
rc_bit_last(probs[symbol], ,
- rep0 += 1U << offset,
- SEQ_DIST_MODEL);
+ rep0 += 1U << offset);
}
-#endif
} else {
// The distance is >= 128. Decode the
// lower bits without probabilities
@@ -602,44 +595,39 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
assert(limit >= 6);
limit -= ALIGN_BITS;
assert(limit >= 2);
- case SEQ_DIRECT:
+
// Not worth manual unrolling
do {
- rc_direct(rep0, SEQ_DIRECT);
+ rc_direct(rep0);
} while (--limit > 0);
// Decode the lowest four bits using
// probabilities.
rep0 <<= ALIGN_BITS;
symbol = 1;
-#ifdef HAVE_SMALL
- offset = 0;
- case SEQ_ALIGN:
- do {
- rc_bit(coder->pos_align[
- symbol], ,
- rep0 += 1U << offset,
- SEQ_ALIGN);
- } while (++offset < ALIGN_BITS);
-#else
- case SEQ_ALIGN0:
+
rc_bit(coder->pos_align[symbol], ,
- rep0 += 1, SEQ_ALIGN0);
- case SEQ_ALIGN1:
+ rep0 += 1);
+
rc_bit(coder->pos_align[symbol], ,
- rep0 += 2, SEQ_ALIGN1);
- case SEQ_ALIGN2:
+ rep0 += 2);
+
rc_bit(coder->pos_align[symbol], ,
- rep0 += 4, SEQ_ALIGN2);
- case SEQ_ALIGN3:
- // Like in SEQ_DIST_MODEL, we don't
- // need "symbol" for anything else
- // than indexing the probability array.
- rc_bit_last(coder->pos_align[symbol], ,
- rep0 += 8, SEQ_ALIGN3);
-#endif
+ rep0 += 4);
+
+ // Like when distance [4, 127], we
+ // don't need "symbol" for anything
+ // other than indexing the probability
+ // array.
+ rc_bit_last(
+ coder->pos_align[symbol], ,
+ rep0 += 8);
if (rep0 == UINT32_MAX) {
+ ///////////////////////////
+ // End of payload marker //
+ ///////////////////////////
+
// End of payload marker was
// found. It may only be
// present if
@@ -657,10 +645,9 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
goto out;
}
- case SEQ_EOPM:
// LZMA1 stream with
// end-of-payload marker.
- rc_normalize(SEQ_EOPM);
+ rc_normalize();
ret = rc_is_finished(rc)
? LZMA_STREAM_END
: LZMA_DATA_ERROR;
@@ -678,10 +665,12 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
} else {
rc_update_1(coder->is_rep[state]);
- // Repeated match
- //
- // The match distance is a value that we have had
- // earlier. The latest four match distances are
+ /////////////////////
+ // Repeated match. //
+ /////////////////////
+
+ // The match distance is a value that we have decoded
+ // recently. The latest four match distances are
// available as rep0, rep1, rep2 and rep3. We will
// now decode which of them is the new distance.
//
@@ -692,13 +681,331 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
goto out;
}
- case SEQ_IS_REP0:
- rc_if_0(coder->is_rep0[state], SEQ_IS_REP0) {
+ rc_if_0(coder->is_rep0[state]) {
rc_update_0(coder->is_rep0[state]);
// The distance is rep0.
+ // Decode the next bit to determine if 1 byte
+ // should be copied from rep0 distance or
+ // if the number of bytes needs to be decoded.
+
+ // If the next bit is 0, then it is a
+ // "Short Rep Match" and only 1 bit is copied.
+ // Otherwise, the length of the match is
+ // decoded after the "else" statement.
+ rc_if_0(coder->is_rep0_long[state][pos_state]) {
+ rc_update_0(coder->is_rep0_long[
+ state][pos_state]);
+
+ update_short_rep(state);
+ dict_put(&dict, dict_get(&dict, rep0));
+ continue;
+ }
+
+ // Repeating more than one byte at
+ // distance of rep0.
+ rc_update_1(coder->is_rep0_long[
+ state][pos_state]);
+
+ } else {
+ rc_update_1(coder->is_rep0[state]);
+
+ // The distance is rep1, rep2 or rep3. Once
+ // we find out which one of these three, it
+ // is stored to rep0 and rep1, rep2 and rep3
+ // are updated accordingly. There is no
+ // "Short Rep Match" option, so the length
+ // of the match must always be decoded next.
+ rc_if_0(coder->is_rep1[state]) {
+ // The distance is rep1.
+ rc_update_0(coder->is_rep1[state]);
+
+ const uint32_t distance = rep1;
+ rep1 = rep0;
+ rep0 = distance;
+
+ } else {
+ rc_update_1(coder->is_rep1[state]);
+
+ rc_if_0(coder->is_rep2[state]) {
+ // The distance is rep2.
+ rc_update_0(coder->is_rep2[
+ state]);
+
+ const uint32_t distance = rep2;
+ rep2 = rep1;
+ rep1 = rep0;
+ rep0 = distance;
+
+ } else {
+ // The distance is rep3.
+ rc_update_1(coder->is_rep2[
+ state]);
+
+ const uint32_t distance = rep3;
+ rep3 = rep2;
+ rep2 = rep1;
+ rep1 = rep0;
+ rep0 = distance;
+ }
+ }
+ }
+
+ update_long_rep(state);
+
+ // Decode the length of the repeated match.
+ len_decode_fast(len, coder->rep_len_decoder,
+ pos_state);
+ }
+
+ /////////////////////////////////
+ // Repeat from history buffer. //
+ /////////////////////////////////
+
+ // The length is always between these limits. There is no way
+ // to trigger the algorithm to set len outside this range.
+ assert(len >= MATCH_LEN_MIN);
+ assert(len <= MATCH_LEN_MAX);
+
+ // Repeat len bytes from distance of rep0.
+ if (unlikely(dict_repeat(&dict, rep0, &len))) {
+ coder->sequence = SEQ_COPY;
+ goto out;
+ }
+
+ continue;
+
+slow:
+#endif
+ ///////////////////////////
+ // Resumable Mode (slow) //
+ ///////////////////////////
+
+ // This is very similar to Non-resumable Mode, so most of the
+ // comments are not repeated. The main differences are:
+ // - case labels are used to resume at the correct location.
+ // - Loops are not unrolled.
+ // - Range coder macros take an extra sequence argument
+ // so they can save to coder->sequence the location to
+ // resume in case there is not enough input.
+ case SEQ_NORMALIZE:
+ case SEQ_IS_MATCH:
+ if (unlikely(might_finish_without_eopm
+ && dict.pos == dict.limit)) {
+ // In rare cases there is a useless byte that needs
+ // to be read anyway.
+ rc_normalize_safe(SEQ_NORMALIZE);
+
+ // If the range decoder state is such that we can
+ // be at the end of the LZMA stream, then the
+ // decoding is finished.
+ if (rc_is_finished(rc)) {
+ ret = LZMA_STREAM_END;
+ goto out;
+ }
+
+ // If the caller hasn't allowed EOPM to be present
+ // together with known uncompressed size, then the
+ // LZMA stream is corrupt.
+ if (!coder->allow_eopm) {
+ ret = LZMA_DATA_ERROR;
+ goto out;
+ }
+
+ // Otherwise continue decoding with the expectation
+ // that the next LZMA symbol is EOPM.
+ eopm_is_valid = true;
+ }
+
+ rc_if_0_safe(coder->is_match[state][pos_state], SEQ_IS_MATCH) {
+ /////////////////////
+ // Decode literal. //
+ /////////////////////
+
+ rc_update_0(coder->is_match[state][pos_state]);
+
+ probs = literal_subcoder(coder->literal,
+ literal_context_bits, literal_pos_mask,
+ dict.pos, dict_get(&dict, 0));
+ symbol = 1;
+
+ if (is_literal_state(state)) {
+ // Decode literal without match byte.
+ // The "slow" version does not unroll
+ // the loop.
+ case SEQ_LITERAL:
+ do {
+ rc_bit_safe(probs[symbol], , ,
+ SEQ_LITERAL);
+ } while (symbol < (1 << 8));
+ } else {
+ // Decode literal with match byte.
+ len = (uint32_t)(dict_get(&dict, rep0)) << 1;
+
+ offset = 0x100;
+
+ case SEQ_LITERAL_MATCHED:
+ do {
+ const uint32_t match_bit
+ = len & offset;
+ const uint32_t subcoder_index
+ = offset + match_bit
+ + symbol;
+
+ rc_bit_safe(probs[subcoder_index],
+ offset &= ~match_bit,
+ offset &= match_bit,
+ SEQ_LITERAL_MATCHED);
+
+ // It seems to be faster to do this
+ // here instead of putting it to the
+ // beginning of the loop and then
+ // putting the "case" in the middle
+ // of the loop.
+ len <<= 1;
+
+ } while (symbol < (1 << 8));
+ }
+
+ state = next_state[state];
+
+ case SEQ_LITERAL_WRITE:
+ if (dict_put_safe(&dict, symbol)) {
+ coder->sequence = SEQ_LITERAL_WRITE;
+ goto out;
+ }
+
+ continue;
+ }
+
+ ///////////////////
+ // Decode match. //
+ ///////////////////
+
+ rc_update_1(coder->is_match[state][pos_state]);
+
+ case SEQ_IS_REP:
+ rc_if_0_safe(coder->is_rep[state], SEQ_IS_REP) {
+ ///////////////////
+ // Simple match. //
+ ///////////////////
+
+ rc_update_0(coder->is_rep[state]);
+ update_match(state);
+
+ rep3 = rep2;
+ rep2 = rep1;
+ rep1 = rep0;
+
+ len_decode(len, coder->match_len_decoder,
+ pos_state, SEQ_MATCH_LEN);
+
+ probs = coder->dist_slot[get_dist_state(len)];
+ symbol = 1;
+
+ case SEQ_DIST_SLOT:
+ do {
+ rc_bit_safe(probs[symbol], , , SEQ_DIST_SLOT);
+ } while (symbol < DIST_SLOTS);
+
+ symbol -= DIST_SLOTS;
+ assert(symbol <= 63);
+
+ if (symbol < DIST_MODEL_START) {
+ rep0 = symbol;
+ } else {
+ limit = (symbol >> 1) - 1;
+ assert(limit >= 1 && limit <= 30);
+ rep0 = 2 + (symbol & 1);
+
+ if (symbol < DIST_MODEL_END) {
+ assert(limit <= 5);
+ rep0 <<= limit;
+ assert(rep0 <= 96);
+ // -1 is fine, because we start
+ // decoding at probs[1], not probs[0].
+ // NOTE: This violates the C standard,
+ // since we are doing pointer
+ // arithmetic past the beginning of
+ // the array.
+ assert((int32_t)(rep0 - symbol - 1)
+ >= -1);
+ assert((int32_t)(rep0 - symbol - 1)
+ <= 82);
+ probs = coder->pos_special + rep0
+ - symbol - 1;
+ symbol = 1;
+ offset = 0;
+ case SEQ_DIST_MODEL:
+ do {
+ rc_bit_safe(probs[symbol], ,
+ rep0 += 1U << offset,
+ SEQ_DIST_MODEL);
+ } while (++offset < limit);
+ } else {
+ assert(symbol >= 14);
+ assert(limit >= 6);
+ limit -= ALIGN_BITS;
+ assert(limit >= 2);
+ case SEQ_DIRECT:
+ do {
+ rc_direct_safe(rep0,
+ SEQ_DIRECT);
+ } while (--limit > 0);
+
+ rep0 <<= ALIGN_BITS;
+ symbol = 1;
+
+ offset = 0;
+ case SEQ_ALIGN:
+ do {
+ rc_bit_safe(coder->pos_align[
+ symbol], ,
+ rep0 += 1U << offset,
+ SEQ_ALIGN);
+ } while (++offset < ALIGN_BITS);
+
+ // End of payload marker
+ if (rep0 == UINT32_MAX) {
+ if (!eopm_is_valid) {
+ ret = LZMA_DATA_ERROR;
+ goto out;
+ }
+
+ case SEQ_EOPM:
+ rc_normalize_safe(SEQ_EOPM);
+ ret = rc_is_finished(rc)
+ ? LZMA_STREAM_END
+ : LZMA_DATA_ERROR;
+ goto out;
+ }
+ }
+ }
+
+ if (unlikely(!dict_is_distance_valid(&dict, rep0))) {
+ ret = LZMA_DATA_ERROR;
+ goto out;
+ }
+
+ } else {
+ /////////////////////
+ // Repeated match. //
+ /////////////////////
+
+ rc_update_1(coder->is_rep[state]);
+
+ if (unlikely(!dict_is_distance_valid(&dict, 0))) {
+ ret = LZMA_DATA_ERROR;
+ goto out;
+ }
+
+ case SEQ_IS_REP0:
+ rc_if_0_safe(coder->is_rep0[state], SEQ_IS_REP0) {
+ rc_update_0(coder->is_rep0[state]);
+
case SEQ_IS_REP0_LONG:
- rc_if_0(coder->is_rep0_long[state][pos_state],
+ rc_if_0_safe(coder->is_rep0_long
+ [state][pos_state],
SEQ_IS_REP0_LONG) {
rc_update_0(coder->is_rep0_long[
state][pos_state]);
@@ -706,8 +1013,9 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
update_short_rep(state);
case SEQ_SHORTREP:
- if (unlikely(dict_put(&dict, dict_get(
- &dict, rep0)))) {
+ if (dict_put_safe(&dict,
+ dict_get(&dict,
+ rep0))) {
coder->sequence = SEQ_SHORTREP;
goto out;
}
@@ -715,8 +1023,6 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
continue;
}
- // Repeating more than one byte at
- // distance of rep0.
rc_update_1(coder->is_rep0_long[
state][pos_state]);
@@ -724,11 +1030,7 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
rc_update_1(coder->is_rep0[state]);
case SEQ_IS_REP1:
- // The distance is rep1, rep2 or rep3. Once
- // we find out which one of these three, it
- // is stored to rep0 and rep1, rep2 and rep3
- // are updated accordingly.
- rc_if_0(coder->is_rep1[state], SEQ_IS_REP1) {
+ rc_if_0_safe(coder->is_rep1[state], SEQ_IS_REP1) {
rc_update_0(coder->is_rep1[state]);
const uint32_t distance = rep1;
@@ -738,7 +1040,7 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
} else {
rc_update_1(coder->is_rep1[state]);
case SEQ_IS_REP2:
- rc_if_0(coder->is_rep2[state],
+ rc_if_0_safe(coder->is_rep2[state],
SEQ_IS_REP2) {
rc_update_0(coder->is_rep2[
state]);
@@ -763,7 +1065,6 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
update_long_rep(state);
- // Decode the length of the repeated match.
len_decode(len, coder->rep_len_decoder,
pos_state, SEQ_REP_LEN);
}
@@ -772,13 +1073,10 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
// Repeat from history buffer. //
/////////////////////////////////
- // The length is always between these limits. There is no way
- // to trigger the algorithm to set len outside this range.
assert(len >= MATCH_LEN_MIN);
assert(len <= MATCH_LEN_MAX);
case SEQ_COPY:
- // Repeat len bytes from distance of rep0.
if (unlikely(dict_repeat(&dict, rep0, &len))) {
coder->sequence = SEQ_COPY;
goto out;
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 05:11:46 +0000