/////////////////////////////////////////////////////////////////////////////// // /// \file lzma_decoder.c /// \brief LZMA decoder /// // Authors: Igor Pavlov // Lasse Collin // // This file has been put into the public domain. // You can do whatever you want with this file. // /////////////////////////////////////////////////////////////////////////////// #include "lz_decoder.h" #include "lzma_common.h" #include "lzma_decoder.h" #include "range_decoder.h" #ifdef HAVE_SMALL // Macros for (somewhat) size-optimized code. #define seq_4(seq) seq #define seq_6(seq) seq #define seq_8(seq) seq #define seq_len(seq) \ seq ## _CHOICE, \ seq ## _CHOICE2, \ seq ## _BITTREE #define len_decode(target, ld, pos_state, seq) \ do { \ case seq ## _CHOICE: \ rc_if_0(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(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(probs[symbol], , , seq ## _BITTREE); \ } while (symbol < limit); \ target += symbol - limit; \ } while (0) #else // HAVE_SMALL // Unrolled versions #define seq_4(seq) \ seq ## 0, \ seq ## 1, \ seq ## 2, \ seq ## 3 #define seq_6(seq) \ seq ## 0, \ seq ## 1, \ seq ## 2, \ seq ## 3, \ seq ## 4, \ seq ## 5 #define seq_8(seq) \ seq ## 0, \ seq ## 1, \ seq ## 2, \ seq ## 3, \ seq ## 4, \ seq ## 5, \ seq ## 6, \ seq ## 7 #define seq_len(seq) \ seq ## _CHOICE, \ seq ## _LOW0, \ seq ## _LOW1, \ seq ## _LOW2, \ seq ## _CHOICE2, \ seq ## _MID0, \ seq ## _MID1, \ seq ## _MID2, \ seq ## _HIGH0, \ seq ## _HIGH1, \ seq ## _HIGH2, \ seq ## _HIGH3, \ seq ## _HIGH4, \ seq ## _HIGH5, \ seq ## _HIGH6, \ seq ## _HIGH7 #define len_decode(target, ld, pos_state, seq) \ do { \ symbol = 1; \ case seq ## _CHOICE: \ rc_if_0(ld.choice, seq ## _CHOICE) { \ rc_update_0(ld.choice); \ rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW0); \ rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW1); \ rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW2); \ target = symbol - LEN_LOW_SYMBOLS + MATCH_LEN_MIN; \ } else { \ rc_update_1(ld.choice); \ case seq ## _CHOICE2: \ rc_if_0(ld.choice2, seq ## _CHOICE2) { \ rc_update_0(ld.choice2); \ rc_bit_case(ld.mid[pos_state][symbol], , , \ seq ## _MID0); \ rc_bit_case(ld.mid[pos_state][symbol], , , \ seq ## _MID1); \ rc_bit_case(ld.mid[pos_state][symbol], , , \ seq ## _MID2); \ target = symbol - LEN_MID_SYMBOLS \ + MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \ } else { \ rc_update_1(ld.choice2); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH0); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH1); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH2); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH3); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH4); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH5); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH6); \ rc_bit_case(ld.high[symbol], , , seq ## _HIGH7); \ target = symbol - LEN_HIGH_SYMBOLS \ + MATCH_LEN_MIN \ + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \ } \ } \ } while (0) #endif // HAVE_SMALL /// 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; struct lzma_coder_s { /////////////////// // 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_pos_mask; /// Uncompressed size as bytes, or LZMA_VLI_UNKNOWN if end of /// payload marker is expected. lzma_vli uncompressed_size; //////////////////////////////// // State of incomplete symbol // //////////////////////////////// /// Position where to continue the decoder loop enum { SEQ_NORMALIZE, SEQ_IS_MATCH, seq_8(SEQ_LITERAL), seq_8(SEQ_LITERAL_MATCHED), SEQ_LITERAL_WRITE, SEQ_IS_REP, seq_len(SEQ_MATCH_LEN), seq_6(SEQ_DIST_SLOT), SEQ_DIST_MODEL, SEQ_DIRECT, seq_4(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_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; }; static lzma_ret lzma_decode(lzma_coder *restrict coder, lzma_dict *restrict dictptr, const uint8_t *restrict in, size_t *restrict in_pos, size_t in_size) { //////////////////// // 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); // 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_pos_mask = coder->literal_pos_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; // If uncompressed size is known, there must be no end of payload // marker. const bool no_eopm = coder->uncompressed_size != LZMA_VLI_UNKNOWN; if (no_eopm && coder->uncompressed_size < dict.limit - dict.pos) dict.limit = dict.pos + (size_t)(coder->uncompressed_size); // The main decoder loop. The "switch" is used to restart the decoder at // correct location. Once restarted, the "switch" is no longer used. 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; case SEQ_NORMALIZE: case SEQ_IS_MATCH: if (unlikely(no_eopm && dict.pos == dict.limit)) break; rc_if_0(coder->is_match[state][pos_state], SEQ_IS_MATCH) { rc_update_0(coder->is_match[state][pos_state]); // It's a literal i.e. a single 8-bit byte. 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. #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 } else { // Decode literal with match byte. // // We store the byte we compare against // ("match byte") to "len" to minimize the // number of variables we need to store // between decoder calls. len = dict_get(&dict, rep0) << 1; // The usage of "offset" allows omitting some // branches, which should give tiny speed // improvement on some CPUs. "offset" gets // 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: \ match_bit = len & offset; \ subcoder_index = offset + match_bit + symbol; \ rc_bit(probs[subcoder_index], \ offset &= ~match_bit, \ offset &= match_bit, \ seq) d(SEQ_LITERAL_MATCHED0); len <<= 1; d(SEQ_LITERAL_MATCHED1); len <<= 1; d(SEQ_LITERAL_MATCHED2); len <<= 1; d(SEQ_LITERAL_MATCHED3); len <<= 1; d(SEQ_LITERAL_MATCHED4); len <<= 1; d(SEQ_LITERAL_MATCHED5); len <<= 1; d(SEQ_LITERAL_MATCHED6); len <<= 1; d(SEQ_LITERAL_MATCHED7); # undef d #endif } //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; } 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. 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_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(len, coder->match_len_decoder, pos_state, SEQ_MATCH_LEN); // Prepare to decode the highest two bits of the // match 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 // 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. rep0 = symbol; } else { // Decode the lowest [1, 29] bits of // the match distance. 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]. 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: #ifdef HAVE_SMALL do { rc_bit(probs[symbol], , rep0 += 1 << offset, SEQ_DIST_MODEL); } while (++offset < limit); #else switch (limit) { case 5: assert(offset == 0); rc_bit(probs[symbol], , rep0 += 1, SEQ_DIST_MODEL); ++offset; --limit; case 4: rc_bit(probs[symbol], , rep0 += 1 << offset, SEQ_DIST_MODEL); ++offset; --limit; case 3: rc_bit(probs[symbol], , rep0 += 1 << offset, SEQ_DIST_MODEL); ++offset; --limit; case 2: rc_bit(probs[symbol], , rep0 += 1 << offset, SEQ_DIST_MODEL); ++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(probs[symbol], , rep0 += 1 << offset, SEQ_DIST_MODEL); } #endif } 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); case SEQ_DIRECT: // Not worth manual unrolling do { rc_direct(rep0, SEQ_DIRECT); } 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 += 1 << offset, SEQ_ALIGN); } while (++offset < ALIGN_BITS); #else case SEQ_ALIGN0: rc_bit(coder->pos_align[symbol], , rep0 += 1, SEQ_ALIGN0); case SEQ_ALIGN1: rc_bit(coder->pos_align[symbol], , rep0 += 2, SEQ_ALIGN1); case SEQ_ALIGN2: 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 if (rep0 == UINT32_MAX) { // End of payload marker was // found. It must not be // present if uncompressed // size is known. if (coder->uncompressed_size != LZMA_VLI_UNKNOWN) { ret = LZMA_DATA_ERROR; goto out; } case SEQ_EOPM: // LZMA1 stream with // end-of-payload marker. rc_normalize(SEQ_EOPM); ret = LZMA_STREAM_END; goto out; } } } // 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 had // earlier. 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; } case SEQ_IS_REP0: rc_if_0(coder->is_rep0[state], SEQ_IS_REP0) { rc_update_0(coder->is_rep0[state]); // The distance is rep0. case SEQ_IS_REP0_LONG: rc_if_0(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 (unlikely(dict_put(&dict, dict_get( &dict, rep0)))) { coder->sequence = SEQ_SHORTREP; goto out; } 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]); 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_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(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); // Decode the length of the repeated match. len_decode(len, coder->rep_len_decoder, pos_state, SEQ_REP_LEN); } ///////////////////////////////// // 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; } } rc_normalize(SEQ_NORMALIZE); coder->sequence = SEQ_IS_MATCH; 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; // Since there cannot be end of payload marker if the // uncompressed size was known, we check here if we // finished decoding. if (coder->uncompressed_size == 0 && ret == LZMA_OK && coder->sequence != SEQ_NORMALIZE) ret = coder->sequence == SEQ_IS_MATCH ? LZMA_STREAM_END : LZMA_DATA_ERROR; } // We can do an additional check in the range decoder to catch some // corrupted files. if (ret == LZMA_STREAM_END) { if (!rc_is_finished(coder->rc)) ret = LZMA_DATA_ERROR; // Reset the range decoder so that it is ready to reinitialize // for a new LZMA2 chunk. rc_reset(coder->rc); } return ret; } static void lzma_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size) { coder->uncompressed_size = uncompressed_size; } /* extern void lzma_lzma_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size) { // This is hack. (*(lzma_coder **)(coder))->uncompressed_size = uncompressed_size; } */ static void lzma_decoder_reset(lzma_coder *coder, const void *opt) { 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_pos_mask = (1U << options->lp) - 1; // 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 void *opt, lzma_lz_options *lz_options) { if (lz->coder == NULL) { lz->coder = lzma_alloc(sizeof(lzma_coder), 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. const lzma_options_lzma *options = opt; 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, const void *options, lzma_lz_options *lz_options) { if (!is_lclppb_valid(options)) return LZMA_PROG_ERROR; return_if_error(lzma_lzma_decoder_create( lz, allocator, options, lz_options)); lzma_decoder_reset(lz->coder, options); lzma_decoder_uncompressed(lz->coder, LZMA_VLI_UNKNOWN); 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_coder) + 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 = unaligned_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; }