| // SPDX-License-Identifier: 0BSD |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // |
| /// \file lzma_decoder.c |
| /// \brief LZMA decoder |
| /// |
| // Authors: Igor Pavlov |
| // Lasse Collin |
| // Jia Tan |
| // |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| #include "lz_decoder.h" |
| #include "lzma_common.h" |
| #include "lzma_decoder.h" |
| #include "range_decoder.h" |
| |
| // The macros unroll loops with switch statements. |
| // Silence warnings about missing fall-through comments. |
| #if TUKLIB_GNUC_REQ(7, 0) |
| # 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. |
| #define LZMA_IN_REQUIRED 20 |
| |
| |
| // Macros for (somewhat) size-optimized code. |
| // This is used to decode the match length (how many bytes must be repeated |
| // from the dictionary). This version is used in the Resumable mode and |
| // does not unroll any loops. |
| #define len_decode(target, ld, pos_state, seq) \ |
| do { \ |
| case seq ## _CHOICE: \ |
| rc_if_0_safe(ld.choice, seq ## _CHOICE) { \ |
| rc_update_0(ld.choice); \ |
| probs = ld.low[pos_state];\ |
| limit = LEN_LOW_SYMBOLS; \ |
| target = MATCH_LEN_MIN; \ |
| } else { \ |
| rc_update_1(ld.choice); \ |
| case seq ## _CHOICE2: \ |
| rc_if_0_safe(ld.choice2, seq ## _CHOICE2) { \ |
| rc_update_0(ld.choice2); \ |
| probs = ld.mid[pos_state]; \ |
| limit = LEN_MID_SYMBOLS; \ |
| target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \ |
| } else { \ |
| rc_update_1(ld.choice2); \ |
| probs = ld.high; \ |
| limit = LEN_HIGH_SYMBOLS; \ |
| target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS \ |
| + LEN_MID_SYMBOLS; \ |
| } \ |
| } \ |
| symbol = 1; \ |
| case seq ## _BITTREE: \ |
| do { \ |
| rc_bit_safe(probs[symbol], , , seq ## _BITTREE); \ |
| } while (symbol < limit); \ |
| target += symbol - limit; \ |
| } while (0) |
| |
| |
| // This is the faster version of the match length decoder that does not |
| // worry about being resumable. It unrolls the bittree decoding loop. |
| #define len_decode_fast(target, ld, pos_state) \ |
| do { \ |
| symbol = 1; \ |
| rc_if_0(ld.choice) { \ |
| rc_update_0(ld.choice); \ |
| rc_bittree3(ld.low[pos_state], \ |
| -LEN_LOW_SYMBOLS + MATCH_LEN_MIN); \ |
| target = symbol; \ |
| } else { \ |
| rc_update_1(ld.choice); \ |
| rc_if_0(ld.choice2) { \ |
| rc_update_0(ld.choice2); \ |
| rc_bittree3(ld.mid[pos_state], -LEN_MID_SYMBOLS \ |
| + MATCH_LEN_MIN + LEN_LOW_SYMBOLS); \ |
| target = symbol; \ |
| } else { \ |
| rc_update_1(ld.choice2); \ |
| rc_bittree8(ld.high, -LEN_HIGH_SYMBOLS \ |
| + MATCH_LEN_MIN \ |
| + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS); \ |
| target = symbol; \ |
| } \ |
| } \ |
| } while (0) |
| |
| |
| /// Length decoder probabilities; see comments in lzma_common.h. |
| typedef struct { |
| probability choice; |
| probability choice2; |
| probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS]; |
| probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS]; |
| probability high[LEN_HIGH_SYMBOLS]; |
| } lzma_length_decoder; |
| |
| |
| typedef struct { |
| /////////////////// |
| // Probabilities // |
| /////////////////// |
| |
| /// Literals; see comments in lzma_common.h. |
| probability literal[LITERAL_CODERS_MAX * LITERAL_CODER_SIZE]; |
| |
| /// If 1, it's a match. Otherwise it's a single 8-bit literal. |
| probability is_match[STATES][POS_STATES_MAX]; |
| |
| /// If 1, it's a repeated match. The distance is one of rep0 .. rep3. |
| probability is_rep[STATES]; |
| |
| /// If 0, distance of a repeated match is rep0. |
| /// Otherwise check is_rep1. |
| probability is_rep0[STATES]; |
| |
| /// If 0, distance of a repeated match is rep1. |
| /// Otherwise check is_rep2. |
| probability is_rep1[STATES]; |
| |
| /// If 0, distance of a repeated match is rep2. Otherwise it is rep3. |
| probability is_rep2[STATES]; |
| |
| /// If 1, the repeated match has length of one byte. Otherwise |
| /// the length is decoded from rep_len_decoder. |
| probability is_rep0_long[STATES][POS_STATES_MAX]; |
| |
| /// Probability tree for the highest two bits of the match distance. |
| /// There is a separate probability tree for match lengths of |
| /// 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273]. |
| probability dist_slot[DIST_STATES][DIST_SLOTS]; |
| |
| /// Probability trees for additional bits for match distance when the |
| /// distance is in the range [4, 127]. |
| probability pos_special[FULL_DISTANCES - DIST_MODEL_END]; |
| |
| /// Probability tree for the lowest four bits of a match distance |
| /// that is equal to or greater than 128. |
| probability pos_align[ALIGN_SIZE]; |
| |
| /// Length of a normal match |
| lzma_length_decoder match_len_decoder; |
| |
| /// Length of a repeated match |
| lzma_length_decoder rep_len_decoder; |
| |
| /////////////////// |
| // Decoder state // |
| /////////////////// |
| |
| // Range coder |
| lzma_range_decoder rc; |
| |
| // Types of the most recently seen LZMA symbols |
| lzma_lzma_state state; |
| |
| uint32_t rep0; ///< Distance of the latest match |
| uint32_t rep1; ///< Distance of second latest match |
| uint32_t rep2; ///< Distance of third latest match |
| uint32_t rep3; ///< Distance of fourth latest match |
| |
| uint32_t pos_mask; // (1U << pb) - 1 |
| uint32_t literal_context_bits; |
| uint32_t literal_mask; |
| |
| /// Uncompressed size as bytes, or LZMA_VLI_UNKNOWN if end of |
| /// payload marker is expected. |
| lzma_vli uncompressed_size; |
| |
| /// True if end of payload marker (EOPM) is allowed even when |
| /// uncompressed_size is known; false if EOPM must not be present. |
| /// This is ignored if uncompressed_size == LZMA_VLI_UNKNOWN. |
| bool allow_eopm; |
| |
| //////////////////////////////// |
| // State of incomplete symbol // |
| //////////////////////////////// |
| |
| /// Position where to continue the decoder loop |
| enum { |
| SEQ_NORMALIZE, |
| SEQ_IS_MATCH, |
| SEQ_LITERAL, |
| SEQ_LITERAL_MATCHED, |
| SEQ_LITERAL_WRITE, |
| SEQ_IS_REP, |
| SEQ_MATCH_LEN_CHOICE, |
| SEQ_MATCH_LEN_CHOICE2, |
| SEQ_MATCH_LEN_BITTREE, |
| SEQ_DIST_SLOT, |
| SEQ_DIST_MODEL, |
| SEQ_DIRECT, |
| SEQ_ALIGN, |
| SEQ_EOPM, |
| SEQ_IS_REP0, |
| SEQ_SHORTREP, |
| SEQ_IS_REP0_LONG, |
| SEQ_IS_REP1, |
| SEQ_IS_REP2, |
| SEQ_REP_LEN_CHOICE, |
| SEQ_REP_LEN_CHOICE2, |
| SEQ_REP_LEN_BITTREE, |
| SEQ_COPY, |
| } sequence; |
| |
| /// Base of the current probability tree |
| probability *probs; |
| |
| /// Symbol being decoded. This is also used as an index variable in |
| /// bittree decoders: probs[symbol] |
| uint32_t symbol; |
| |
| /// Used as a loop termination condition on bittree decoders and |
| /// direct bits decoder. |
| uint32_t limit; |
| |
| /// Matched literal decoder: 0x100 or 0 to help avoiding branches. |
| /// Bittree reverse decoders: Offset of the next bit: 1 << offset |
| uint32_t offset; |
| |
| /// If decoding a literal: match byte. |
| /// If decoding a match: length of the match. |
| uint32_t len; |
| } lzma_lzma1_decoder; |
| |
| |
| static lzma_ret |
| lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr, |
| const uint8_t *restrict in, |
| size_t *restrict in_pos, size_t in_size) |
| { |
| lzma_lzma1_decoder *restrict coder = coder_ptr; |
| |
| //////////////////// |
| // Initialization // |
| //////////////////// |
| |
| { |
| const lzma_ret ret = rc_read_init( |
| &coder->rc, in, in_pos, in_size); |
| if (ret != LZMA_STREAM_END) |
| return ret; |
| } |
| |
| /////////////// |
| // Variables // |
| /////////////// |
| |
| // Making local copies of often-used variables improves both |
| // speed and readability. |
| |
| lzma_dict dict = *dictptr; |
| |
| const size_t dict_start = dict.pos; |
| |
| // Range decoder |
| rc_to_local(coder->rc, *in_pos, LZMA_IN_REQUIRED); |
| |
| // State |
| uint32_t state = coder->state; |
| uint32_t rep0 = coder->rep0; |
| uint32_t rep1 = coder->rep1; |
| uint32_t rep2 = coder->rep2; |
| uint32_t rep3 = coder->rep3; |
| |
| const uint32_t pos_mask = coder->pos_mask; |
| |
| // These variables are actually needed only if we last time ran |
| // out of input in the middle of the decoder loop. |
| probability *probs = coder->probs; |
| uint32_t symbol = coder->symbol; |
| uint32_t limit = coder->limit; |
| uint32_t offset = coder->offset; |
| uint32_t len = coder->len; |
| |
| const uint32_t literal_mask = coder->literal_mask; |
| const uint32_t literal_context_bits = coder->literal_context_bits; |
| |
| // Temporary variables |
| uint32_t pos_state = dict.pos & pos_mask; |
| |
| lzma_ret ret = LZMA_OK; |
| |
| // This is true when the next LZMA symbol is allowed to be EOPM. |
| // That is, if this is false, then EOPM is considered |
| // an invalid symbol and we will return LZMA_DATA_ERROR. |
| // |
| // EOPM is always required (not just allowed) when |
| // the uncompressed size isn't known. When uncompressed size |
| // is known, eopm_is_valid may be set to true later. |
| bool eopm_is_valid = coder->uncompressed_size == LZMA_VLI_UNKNOWN; |
| |
| // If uncompressed size is known and there is enough output space |
| // to decode all the data, limit the available buffer space so that |
| // the main loop won't try to decode past the end of the stream. |
| bool might_finish_without_eopm = false; |
| if (coder->uncompressed_size != LZMA_VLI_UNKNOWN |
| && coder->uncompressed_size <= dict.limit - dict.pos) { |
| dict.limit = dict.pos + (size_t)(coder->uncompressed_size); |
| might_finish_without_eopm = true; |
| } |
| |
| // 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 |
| // since we already calculated it when setting up the local |
| // variables. |
| pos_state = dict.pos & pos_mask; |
| |
| #ifndef HAVE_SMALL |
| |
| /////////////////////////////// |
| // Non-resumable Mode (fast) // |
| /////////////////////////////// |
| |
| // Go to Resumable mode (1) if there is not enough input to |
| // safely decode any possible LZMA symbol or (2) if the |
| // dictionary is full, which may need special checks that |
| // are only done in the Resumable mode. |
| if (unlikely(!rc_is_fast_allowed() |
| || dict.pos == dict.limit)) |
| goto slow; |
| |
| // 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. // |
| ///////////////////// |
| |
| // Update the RC that we have decoded a 0. |
| rc_update_0(coder->is_match[state][pos_state]); |
| |
| // Get the correct probability array from lp and |
| // lc params. |
| probs = literal_subcoder(coder->literal, |
| literal_context_bits, literal_mask, |
| dict.pos, dict_get0(&dict)); |
| |
| if (is_literal_state(state)) { |
| update_literal_normal(state); |
| |
| // Decode literal without match byte. |
| rc_bittree8(probs, 0); |
| } else { |
| update_literal_matched(state); |
| |
| // Decode literal with match byte. |
| rc_matched_literal(probs, |
| dict_get(&dict, rep0)); |
| } |
| |
| // Write decoded literal to dictionary |
| dict_put(&dict, symbol); |
| continue; |
| } |
| |
| /////////////////// |
| // 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]); |
| |
| 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); |
| |
| // The latest three match distances are kept in |
| // memory in case there are repeated matches. |
| rep3 = rep2; |
| rep2 = rep1; |
| rep1 = rep0; |
| |
| // Decode the length of the match. |
| len_decode_fast(len, coder->match_len_decoder, |
| pos_state); |
| |
| // Next, decode the distance into rep0. |
| |
| // The next 6 bits determine how to decode the |
| // rest of the distance. |
| probs = coder->dist_slot[get_dist_state(len)]; |
| |
| rc_bittree6(probs, -DIST_SLOTS); |
| assert(symbol <= 63); |
| |
| if (symbol < DIST_MODEL_START) { |
| // 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 { |
| // 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) { |
| // 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); |
| |
| // -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 = 1; |
| |
| // Variable number (1-5) of bits |
| // from a reverse bittree. This |
| // isn't worth manual unrolling. |
| // |
| // NOTE: Making one or many of the |
| // variables (probs, symbol, offset, |
| // or limit) local here (instead of |
| // using those declared outside the |
| // main loop) can affect code size |
| // and performance which isn't a |
| // surprise but it's not so clear |
| // what is the best. |
| do { |
| rc_bit_add_if_1(probs, |
| rep0, offset); |
| offset <<= 1; |
| } while (--limit > 0); |
| } else { |
| // The distance is >= 128. Decode the |
| // lower bits without probabilities |
| // except the lowest four bits. |
| assert(symbol >= 14); |
| assert(limit >= 6); |
| |
| limit -= ALIGN_BITS; |
| assert(limit >= 2); |
| |
| rc_direct(rep0, limit); |
| |
| // Decode the lowest four bits using |
| // probabilities. |
| rep0 <<= ALIGN_BITS; |
| rc_bittree_rev4(coder->pos_align); |
| rep0 += symbol; |
| |
| // If the end of payload marker (EOPM) |
| // is detected, jump to the safe code. |
| // The EOPM handling isn't speed |
| // critical at all. |
| // |
| // A final normalization is needed |
| // after the EOPM (there can be a |
| // dummy byte to read in some cases). |
| // If the normalization was done here |
| // in the fast code, it would need to |
| // be taken into account in the value |
| // of LZMA_IN_REQUIRED. Using the |
| // safe code allows keeping |
| // LZMA_IN_REQUIRED as 20 instead of |
| // 21. |
| if (rep0 == UINT32_MAX) |
| goto eopm; |
| } |
| } |
| |
| // Validate the distance we just decoded. |
| if (unlikely(!dict_is_distance_valid(&dict, rep0))) { |
| ret = LZMA_DATA_ERROR; |
| goto out; |
| } |
| |
| } else { |
| rc_update_1(coder->is_rep[state]); |
| |
| ///////////////////// |
| // 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. |
| // |
| // There cannot be a match if we haven't produced |
| // any output, so check that first. |
| if (unlikely(!dict_is_distance_valid(&dict, 0))) { |
| ret = LZMA_DATA_ERROR; |
| goto out; |
| } |
| |
| 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_mask, |
| dict.pos, dict_get0(&dict)); |
| symbol = 1; |
| |
| if (is_literal_state(state)) { |
| update_literal_normal(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 { |
| update_literal_matched(state); |
| |
| // 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)); |
| } |
| |
| 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: |
| rc_direct_safe(rep0, limit, |
| SEQ_DIRECT); |
| |
| rep0 <<= ALIGN_BITS; |
| symbol = 0; |
| offset = 1; |
| case SEQ_ALIGN: |
| do { |
| rc_bit_last_safe( |
| coder->pos_align[ |
| offset |
| + symbol], |
| , |
| symbol += offset, |
| SEQ_ALIGN); |
| offset <<= 1; |
| } while (offset < ALIGN_SIZE); |
| |
| rep0 += symbol; |
| |
| if (rep0 == UINT32_MAX) { |
| // End of payload marker was |
| // found. It may only be |
| // present if |
| // - uncompressed size is |
| // unknown or |
| // - after known uncompressed |
| // size amount of bytes has |
| // been decompressed and |
| // caller has indicated |
| // that EOPM might be used |
| // (it's not allowed in |
| // LZMA2). |
| #ifndef HAVE_SMALL |
| eopm: |
| #endif |
| if (!eopm_is_valid) { |
| ret = LZMA_DATA_ERROR; |
| goto out; |
| } |
| |
| case SEQ_EOPM: |
| // LZMA1 stream with |
| // end-of-payload marker. |
| 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_safe(coder->is_rep0_long |
| [state][pos_state], |
| SEQ_IS_REP0_LONG) { |
| rc_update_0(coder->is_rep0_long[ |
| state][pos_state]); |
| |
| update_short_rep(state); |
| |
| case SEQ_SHORTREP: |
| if (dict_put_safe(&dict, |
| dict_get(&dict, |
| rep0))) { |
| coder->sequence = SEQ_SHORTREP; |
| goto out; |
| } |
| |
| continue; |
| } |
| |
| rc_update_1(coder->is_rep0_long[ |
| state][pos_state]); |
| |
| } else { |
| rc_update_1(coder->is_rep0[state]); |
| |
| case 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; |
| rep1 = rep0; |
| rep0 = distance; |
| |
| } else { |
| rc_update_1(coder->is_rep1[state]); |
| case SEQ_IS_REP2: |
| rc_if_0_safe(coder->is_rep2[state], |
| SEQ_IS_REP2) { |
| rc_update_0(coder->is_rep2[ |
| state]); |
| |
| const uint32_t distance = rep2; |
| rep2 = rep1; |
| rep1 = rep0; |
| rep0 = distance; |
| |
| } else { |
| rc_update_1(coder->is_rep2[ |
| state]); |
| |
| const uint32_t distance = rep3; |
| rep3 = rep2; |
| rep2 = rep1; |
| rep1 = rep0; |
| rep0 = distance; |
| } |
| } |
| } |
| |
| update_long_rep(state); |
| |
| len_decode(len, coder->rep_len_decoder, |
| pos_state, SEQ_REP_LEN); |
| } |
| |
| ///////////////////////////////// |
| // Repeat from history buffer. // |
| ///////////////////////////////// |
| |
| assert(len >= MATCH_LEN_MIN); |
| assert(len <= MATCH_LEN_MAX); |
| |
| case SEQ_COPY: |
| if (unlikely(dict_repeat(&dict, rep0, &len))) { |
| coder->sequence = SEQ_COPY; |
| goto out; |
| } |
| } |
| |
| out: |
| // Save state |
| |
| // NOTE: Must not copy dict.limit. |
| dictptr->pos = dict.pos; |
| dictptr->full = dict.full; |
| |
| rc_from_local(coder->rc, *in_pos); |
| |
| coder->state = state; |
| coder->rep0 = rep0; |
| coder->rep1 = rep1; |
| coder->rep2 = rep2; |
| coder->rep3 = rep3; |
| |
| coder->probs = probs; |
| coder->symbol = symbol; |
| coder->limit = limit; |
| coder->offset = offset; |
| coder->len = len; |
| |
| // Update the remaining amount of uncompressed data if uncompressed |
| // size was known. |
| if (coder->uncompressed_size != LZMA_VLI_UNKNOWN) { |
| coder->uncompressed_size -= dict.pos - dict_start; |
| |
| // If we have gotten all the output but the decoder wants |
| // to write more output, the file is corrupt. There are |
| // three SEQ values where output is produced. |
| if (coder->uncompressed_size == 0 && ret == LZMA_OK |
| && (coder->sequence == SEQ_LITERAL_WRITE |
| || coder->sequence == SEQ_SHORTREP |
| || coder->sequence == SEQ_COPY)) |
| ret = LZMA_DATA_ERROR; |
| } |
| |
| if (ret == LZMA_STREAM_END) { |
| // Reset the range decoder so that it is ready to reinitialize |
| // for a new LZMA2 chunk. |
| rc_reset(coder->rc); |
| coder->sequence = SEQ_IS_MATCH; |
| } |
| |
| return ret; |
| } |
| |
| |
| static void |
| lzma_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size, |
| bool allow_eopm) |
| { |
| lzma_lzma1_decoder *coder = coder_ptr; |
| coder->uncompressed_size = uncompressed_size; |
| coder->allow_eopm = allow_eopm; |
| } |
| |
| |
| static void |
| lzma_decoder_reset(void *coder_ptr, const void *opt) |
| { |
| lzma_lzma1_decoder *coder = coder_ptr; |
| const lzma_options_lzma *options = opt; |
| |
| // NOTE: We assume that lc/lp/pb are valid since they were |
| // successfully decoded with lzma_lzma_decode_properties(). |
| |
| // Calculate pos_mask. We don't need pos_bits as is for anything. |
| coder->pos_mask = (1U << options->pb) - 1; |
| |
| // Initialize the literal decoder. |
| literal_init(coder->literal, options->lc, options->lp); |
| |
| coder->literal_context_bits = options->lc; |
| coder->literal_mask = literal_mask_calc(options->lc, options->lp); |
| |
| // State |
| coder->state = STATE_LIT_LIT; |
| coder->rep0 = 0; |
| coder->rep1 = 0; |
| coder->rep2 = 0; |
| coder->rep3 = 0; |
| coder->pos_mask = (1U << options->pb) - 1; |
| |
| // Range decoder |
| rc_reset(coder->rc); |
| |
| // Bit and bittree decoders |
| for (uint32_t i = 0; i < STATES; ++i) { |
| for (uint32_t j = 0; j <= coder->pos_mask; ++j) { |
| bit_reset(coder->is_match[i][j]); |
| bit_reset(coder->is_rep0_long[i][j]); |
| } |
| |
| bit_reset(coder->is_rep[i]); |
| bit_reset(coder->is_rep0[i]); |
| bit_reset(coder->is_rep1[i]); |
| bit_reset(coder->is_rep2[i]); |
| } |
| |
| for (uint32_t i = 0; i < DIST_STATES; ++i) |
| bittree_reset(coder->dist_slot[i], DIST_SLOT_BITS); |
| |
| for (uint32_t i = 0; i < FULL_DISTANCES - DIST_MODEL_END; ++i) |
| bit_reset(coder->pos_special[i]); |
| |
| bittree_reset(coder->pos_align, ALIGN_BITS); |
| |
| // Len decoders (also bit/bittree) |
| const uint32_t num_pos_states = 1U << options->pb; |
| bit_reset(coder->match_len_decoder.choice); |
| bit_reset(coder->match_len_decoder.choice2); |
| bit_reset(coder->rep_len_decoder.choice); |
| bit_reset(coder->rep_len_decoder.choice2); |
| |
| for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) { |
| bittree_reset(coder->match_len_decoder.low[pos_state], |
| LEN_LOW_BITS); |
| bittree_reset(coder->match_len_decoder.mid[pos_state], |
| LEN_MID_BITS); |
| |
| bittree_reset(coder->rep_len_decoder.low[pos_state], |
| LEN_LOW_BITS); |
| bittree_reset(coder->rep_len_decoder.mid[pos_state], |
| LEN_MID_BITS); |
| } |
| |
| bittree_reset(coder->match_len_decoder.high, LEN_HIGH_BITS); |
| bittree_reset(coder->rep_len_decoder.high, LEN_HIGH_BITS); |
| |
| coder->sequence = SEQ_IS_MATCH; |
| coder->probs = NULL; |
| coder->symbol = 0; |
| coder->limit = 0; |
| coder->offset = 0; |
| coder->len = 0; |
| |
| return; |
| } |
| |
| |
| extern lzma_ret |
| lzma_lzma_decoder_create(lzma_lz_decoder *lz, const lzma_allocator *allocator, |
| const lzma_options_lzma *options, lzma_lz_options *lz_options) |
| { |
| if (lz->coder == NULL) { |
| lz->coder = lzma_alloc(sizeof(lzma_lzma1_decoder), allocator); |
| if (lz->coder == NULL) |
| return LZMA_MEM_ERROR; |
| |
| lz->code = &lzma_decode; |
| lz->reset = &lzma_decoder_reset; |
| lz->set_uncompressed = &lzma_decoder_uncompressed; |
| } |
| |
| // All dictionary sizes are OK here. LZ decoder will take care of |
| // the special cases. |
| lz_options->dict_size = options->dict_size; |
| lz_options->preset_dict = options->preset_dict; |
| lz_options->preset_dict_size = options->preset_dict_size; |
| |
| return LZMA_OK; |
| } |
| |
| |
| /// Allocate and initialize LZMA decoder. This is used only via LZ |
| /// initialization (lzma_lzma_decoder_init() passes function pointer to |
| /// the LZ initialization). |
| static lzma_ret |
| lzma_decoder_init(lzma_lz_decoder *lz, const lzma_allocator *allocator, |
| lzma_vli id, const void *options, lzma_lz_options *lz_options) |
| { |
| if (!is_lclppb_valid(options)) |
| return LZMA_PROG_ERROR; |
| |
| lzma_vli uncomp_size = LZMA_VLI_UNKNOWN; |
| bool allow_eopm = true; |
| |
| if (id == LZMA_FILTER_LZMA1EXT) { |
| const lzma_options_lzma *opt = options; |
| |
| // Only one flag is supported. |
| if (opt->ext_flags & ~LZMA_LZMA1EXT_ALLOW_EOPM) |
| return LZMA_OPTIONS_ERROR; |
| |
| // FIXME? Using lzma_vli instead of uint64_t is weird because |
| // this has nothing to do with .xz headers and variable-length |
| // integer encoding. On the other hand, using LZMA_VLI_UNKNOWN |
| // instead of UINT64_MAX is clearer when unknown size is |
| // meant. A problem with using lzma_vli is that now we |
| // allow > LZMA_VLI_MAX which is fine in this file but |
| // it's still confusing. Note that alone_decoder.c also |
| // allows > LZMA_VLI_MAX when setting uncompressed size. |
| uncomp_size = opt->ext_size_low |
| + ((uint64_t)(opt->ext_size_high) << 32); |
| allow_eopm = (opt->ext_flags & LZMA_LZMA1EXT_ALLOW_EOPM) != 0 |
| || uncomp_size == LZMA_VLI_UNKNOWN; |
| } |
| |
| return_if_error(lzma_lzma_decoder_create( |
| lz, allocator, options, lz_options)); |
| |
| lzma_decoder_reset(lz->coder, options); |
| lzma_decoder_uncompressed(lz->coder, uncomp_size, allow_eopm); |
| |
| return LZMA_OK; |
| } |
| |
| |
| extern lzma_ret |
| lzma_lzma_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator, |
| const lzma_filter_info *filters) |
| { |
| // LZMA can only be the last filter in the chain. This is enforced |
| // by the raw_decoder initialization. |
| assert(filters[1].init == NULL); |
| |
| return lzma_lz_decoder_init(next, allocator, filters, |
| &lzma_decoder_init); |
| } |
| |
| |
| extern bool |
| lzma_lzma_lclppb_decode(lzma_options_lzma *options, uint8_t byte) |
| { |
| if (byte > (4 * 5 + 4) * 9 + 8) |
| return true; |
| |
| // See the file format specification to understand this. |
| options->pb = byte / (9 * 5); |
| byte -= options->pb * 9 * 5; |
| options->lp = byte / 9; |
| options->lc = byte - options->lp * 9; |
| |
| return options->lc + options->lp > LZMA_LCLP_MAX; |
| } |
| |
| |
| extern uint64_t |
| lzma_lzma_decoder_memusage_nocheck(const void *options) |
| { |
| const lzma_options_lzma *const opt = options; |
| return sizeof(lzma_lzma1_decoder) |
| + lzma_lz_decoder_memusage(opt->dict_size); |
| } |
| |
| |
| extern uint64_t |
| lzma_lzma_decoder_memusage(const void *options) |
| { |
| if (!is_lclppb_valid(options)) |
| return UINT64_MAX; |
| |
| return lzma_lzma_decoder_memusage_nocheck(options); |
| } |
| |
| |
| extern lzma_ret |
| lzma_lzma_props_decode(void **options, const lzma_allocator *allocator, |
| const uint8_t *props, size_t props_size) |
| { |
| if (props_size != 5) |
| return LZMA_OPTIONS_ERROR; |
| |
| lzma_options_lzma *opt |
| = lzma_alloc(sizeof(lzma_options_lzma), allocator); |
| if (opt == NULL) |
| return LZMA_MEM_ERROR; |
| |
| if (lzma_lzma_lclppb_decode(opt, props[0])) |
| goto error; |
| |
| // All dictionary sizes are accepted, including zero. LZ decoder |
| // will automatically use a dictionary at least a few KiB even if |
| // a smaller dictionary is requested. |
| opt->dict_size = read32le(props + 1); |
| |
| opt->preset_dict = NULL; |
| opt->preset_dict_size = 0; |
| |
| *options = opt; |
| |
| return LZMA_OK; |
| |
| error: |
| lzma_free(opt, allocator); |
| return LZMA_OPTIONS_ERROR; |
| } |