1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file lzma_decoder.c 4207753Smm/// \brief LZMA decoder 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#include "lz_decoder.h" 15207753Smm#include "lzma_common.h" 16207753Smm#include "lzma_decoder.h" 17207753Smm#include "range_decoder.h" 18207753Smm 19207753Smm 20207753Smm#ifdef HAVE_SMALL 21207753Smm 22207753Smm// Macros for (somewhat) size-optimized code. 23207753Smm#define seq_4(seq) seq 24207753Smm 25207753Smm#define seq_6(seq) seq 26207753Smm 27207753Smm#define seq_8(seq) seq 28207753Smm 29207753Smm#define seq_len(seq) \ 30207753Smm seq ## _CHOICE, \ 31207753Smm seq ## _CHOICE2, \ 32207753Smm seq ## _BITTREE 33207753Smm 34207753Smm#define len_decode(target, ld, pos_state, seq) \ 35207753Smmdo { \ 36207753Smmcase seq ## _CHOICE: \ 37207753Smm rc_if_0(ld.choice, seq ## _CHOICE) { \ 38207753Smm rc_update_0(ld.choice); \ 39207753Smm probs = ld.low[pos_state];\ 40207753Smm limit = LEN_LOW_SYMBOLS; \ 41207753Smm target = MATCH_LEN_MIN; \ 42207753Smm } else { \ 43207753Smm rc_update_1(ld.choice); \ 44207753Smmcase seq ## _CHOICE2: \ 45207753Smm rc_if_0(ld.choice2, seq ## _CHOICE2) { \ 46207753Smm rc_update_0(ld.choice2); \ 47207753Smm probs = ld.mid[pos_state]; \ 48207753Smm limit = LEN_MID_SYMBOLS; \ 49207753Smm target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \ 50207753Smm } else { \ 51207753Smm rc_update_1(ld.choice2); \ 52207753Smm probs = ld.high; \ 53207753Smm limit = LEN_HIGH_SYMBOLS; \ 54207753Smm target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS \ 55207753Smm + LEN_MID_SYMBOLS; \ 56207753Smm } \ 57207753Smm } \ 58207753Smm symbol = 1; \ 59207753Smmcase seq ## _BITTREE: \ 60207753Smm do { \ 61207753Smm rc_bit(probs[symbol], , , seq ## _BITTREE); \ 62207753Smm } while (symbol < limit); \ 63207753Smm target += symbol - limit; \ 64207753Smm} while (0) 65207753Smm 66207753Smm#else // HAVE_SMALL 67207753Smm 68207753Smm// Unrolled versions 69207753Smm#define seq_4(seq) \ 70207753Smm seq ## 0, \ 71207753Smm seq ## 1, \ 72207753Smm seq ## 2, \ 73207753Smm seq ## 3 74207753Smm 75207753Smm#define seq_6(seq) \ 76207753Smm seq ## 0, \ 77207753Smm seq ## 1, \ 78207753Smm seq ## 2, \ 79207753Smm seq ## 3, \ 80207753Smm seq ## 4, \ 81207753Smm seq ## 5 82207753Smm 83207753Smm#define seq_8(seq) \ 84207753Smm seq ## 0, \ 85207753Smm seq ## 1, \ 86207753Smm seq ## 2, \ 87207753Smm seq ## 3, \ 88207753Smm seq ## 4, \ 89207753Smm seq ## 5, \ 90207753Smm seq ## 6, \ 91207753Smm seq ## 7 92207753Smm 93207753Smm#define seq_len(seq) \ 94207753Smm seq ## _CHOICE, \ 95207753Smm seq ## _LOW0, \ 96207753Smm seq ## _LOW1, \ 97207753Smm seq ## _LOW2, \ 98207753Smm seq ## _CHOICE2, \ 99207753Smm seq ## _MID0, \ 100207753Smm seq ## _MID1, \ 101207753Smm seq ## _MID2, \ 102207753Smm seq ## _HIGH0, \ 103207753Smm seq ## _HIGH1, \ 104207753Smm seq ## _HIGH2, \ 105207753Smm seq ## _HIGH3, \ 106207753Smm seq ## _HIGH4, \ 107207753Smm seq ## _HIGH5, \ 108207753Smm seq ## _HIGH6, \ 109207753Smm seq ## _HIGH7 110207753Smm 111207753Smm#define len_decode(target, ld, pos_state, seq) \ 112207753Smmdo { \ 113207753Smm symbol = 1; \ 114207753Smmcase seq ## _CHOICE: \ 115207753Smm rc_if_0(ld.choice, seq ## _CHOICE) { \ 116207753Smm rc_update_0(ld.choice); \ 117207753Smm rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW0); \ 118207753Smm rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW1); \ 119207753Smm rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW2); \ 120207753Smm target = symbol - LEN_LOW_SYMBOLS + MATCH_LEN_MIN; \ 121207753Smm } else { \ 122207753Smm rc_update_1(ld.choice); \ 123207753Smmcase seq ## _CHOICE2: \ 124207753Smm rc_if_0(ld.choice2, seq ## _CHOICE2) { \ 125207753Smm rc_update_0(ld.choice2); \ 126207753Smm rc_bit_case(ld.mid[pos_state][symbol], , , \ 127207753Smm seq ## _MID0); \ 128207753Smm rc_bit_case(ld.mid[pos_state][symbol], , , \ 129207753Smm seq ## _MID1); \ 130207753Smm rc_bit_case(ld.mid[pos_state][symbol], , , \ 131207753Smm seq ## _MID2); \ 132207753Smm target = symbol - LEN_MID_SYMBOLS \ 133207753Smm + MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \ 134207753Smm } else { \ 135207753Smm rc_update_1(ld.choice2); \ 136207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH0); \ 137207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH1); \ 138207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH2); \ 139207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH3); \ 140207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH4); \ 141207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH5); \ 142207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH6); \ 143207753Smm rc_bit_case(ld.high[symbol], , , seq ## _HIGH7); \ 144207753Smm target = symbol - LEN_HIGH_SYMBOLS \ 145207753Smm + MATCH_LEN_MIN \ 146207753Smm + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \ 147207753Smm } \ 148207753Smm } \ 149207753Smm} while (0) 150207753Smm 151207753Smm#endif // HAVE_SMALL 152207753Smm 153207753Smm 154207753Smm/// Length decoder probabilities; see comments in lzma_common.h. 155207753Smmtypedef struct { 156207753Smm probability choice; 157207753Smm probability choice2; 158207753Smm probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS]; 159207753Smm probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS]; 160207753Smm probability high[LEN_HIGH_SYMBOLS]; 161207753Smm} lzma_length_decoder; 162207753Smm 163207753Smm 164312518Sdelphijtypedef struct { 165207753Smm /////////////////// 166207753Smm // Probabilities // 167207753Smm /////////////////// 168207753Smm 169207753Smm /// Literals; see comments in lzma_common.h. 170207753Smm probability literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE]; 171207753Smm 172207753Smm /// If 1, it's a match. Otherwise it's a single 8-bit literal. 173207753Smm probability is_match[STATES][POS_STATES_MAX]; 174207753Smm 175207753Smm /// If 1, it's a repeated match. The distance is one of rep0 .. rep3. 176207753Smm probability is_rep[STATES]; 177207753Smm 178207753Smm /// If 0, distance of a repeated match is rep0. 179207753Smm /// Otherwise check is_rep1. 180207753Smm probability is_rep0[STATES]; 181207753Smm 182207753Smm /// If 0, distance of a repeated match is rep1. 183207753Smm /// Otherwise check is_rep2. 184207753Smm probability is_rep1[STATES]; 185207753Smm 186207753Smm /// If 0, distance of a repeated match is rep2. Otherwise it is rep3. 187207753Smm probability is_rep2[STATES]; 188207753Smm 189207753Smm /// If 1, the repeated match has length of one byte. Otherwise 190207753Smm /// the length is decoded from rep_len_decoder. 191207753Smm probability is_rep0_long[STATES][POS_STATES_MAX]; 192207753Smm 193207753Smm /// Probability tree for the highest two bits of the match distance. 194207753Smm /// There is a separate probability tree for match lengths of 195207753Smm /// 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273]. 196292588Sdelphij probability dist_slot[DIST_STATES][DIST_SLOTS]; 197207753Smm 198207753Smm /// Probability trees for additional bits for match distance when the 199207753Smm /// distance is in the range [4, 127]. 200292588Sdelphij probability pos_special[FULL_DISTANCES - DIST_MODEL_END]; 201207753Smm 202207753Smm /// Probability tree for the lowest four bits of a match distance 203207753Smm /// that is equal to or greater than 128. 204292588Sdelphij probability pos_align[ALIGN_SIZE]; 205207753Smm 206207753Smm /// Length of a normal match 207207753Smm lzma_length_decoder match_len_decoder; 208207753Smm 209207753Smm /// Length of a repeated match 210207753Smm lzma_length_decoder rep_len_decoder; 211207753Smm 212207753Smm /////////////////// 213207753Smm // Decoder state // 214207753Smm /////////////////// 215207753Smm 216207753Smm // Range coder 217207753Smm lzma_range_decoder rc; 218207753Smm 219207753Smm // Types of the most recently seen LZMA symbols 220207753Smm lzma_lzma_state state; 221207753Smm 222207753Smm uint32_t rep0; ///< Distance of the latest match 223207753Smm uint32_t rep1; ///< Distance of second latest match 224207753Smm uint32_t rep2; ///< Distance of third latest match 225207753Smm uint32_t rep3; ///< Distance of fourth latest match 226207753Smm 227207753Smm uint32_t pos_mask; // (1U << pb) - 1 228207753Smm uint32_t literal_context_bits; 229207753Smm uint32_t literal_pos_mask; 230207753Smm 231207753Smm /// Uncompressed size as bytes, or LZMA_VLI_UNKNOWN if end of 232207753Smm /// payload marker is expected. 233207753Smm lzma_vli uncompressed_size; 234207753Smm 235207753Smm //////////////////////////////// 236207753Smm // State of incomplete symbol // 237207753Smm //////////////////////////////// 238207753Smm 239207753Smm /// Position where to continue the decoder loop 240207753Smm enum { 241207753Smm SEQ_NORMALIZE, 242207753Smm SEQ_IS_MATCH, 243207753Smm seq_8(SEQ_LITERAL), 244207753Smm seq_8(SEQ_LITERAL_MATCHED), 245207753Smm SEQ_LITERAL_WRITE, 246207753Smm SEQ_IS_REP, 247207753Smm seq_len(SEQ_MATCH_LEN), 248292588Sdelphij seq_6(SEQ_DIST_SLOT), 249292588Sdelphij SEQ_DIST_MODEL, 250207753Smm SEQ_DIRECT, 251207753Smm seq_4(SEQ_ALIGN), 252207753Smm SEQ_EOPM, 253207753Smm SEQ_IS_REP0, 254207753Smm SEQ_SHORTREP, 255207753Smm SEQ_IS_REP0_LONG, 256207753Smm SEQ_IS_REP1, 257207753Smm SEQ_IS_REP2, 258207753Smm seq_len(SEQ_REP_LEN), 259207753Smm SEQ_COPY, 260207753Smm } sequence; 261207753Smm 262207753Smm /// Base of the current probability tree 263207753Smm probability *probs; 264207753Smm 265207753Smm /// Symbol being decoded. This is also used as an index variable in 266207753Smm /// bittree decoders: probs[symbol] 267207753Smm uint32_t symbol; 268207753Smm 269207753Smm /// Used as a loop termination condition on bittree decoders and 270207753Smm /// direct bits decoder. 271207753Smm uint32_t limit; 272207753Smm 273207753Smm /// Matched literal decoder: 0x100 or 0 to help avoiding branches. 274207753Smm /// Bittree reverse decoders: Offset of the next bit: 1 << offset 275207753Smm uint32_t offset; 276207753Smm 277207753Smm /// If decoding a literal: match byte. 278207753Smm /// If decoding a match: length of the match. 279207753Smm uint32_t len; 280312518Sdelphij} lzma_lzma1_decoder; 281207753Smm 282207753Smm 283207753Smmstatic lzma_ret 284312518Sdelphijlzma_decode(void *coder_ptr, lzma_dict *restrict dictptr, 285207753Smm const uint8_t *restrict in, 286207753Smm size_t *restrict in_pos, size_t in_size) 287207753Smm{ 288312518Sdelphij lzma_lzma1_decoder *restrict coder = coder_ptr; 289312518Sdelphij 290207753Smm //////////////////// 291207753Smm // Initialization // 292207753Smm //////////////////// 293207753Smm 294292588Sdelphij { 295292588Sdelphij const lzma_ret ret = rc_read_init( 296292588Sdelphij &coder->rc, in, in_pos, in_size); 297292588Sdelphij if (ret != LZMA_STREAM_END) 298292588Sdelphij return ret; 299292588Sdelphij } 300207753Smm 301207753Smm /////////////// 302207753Smm // Variables // 303207753Smm /////////////// 304207753Smm 305207753Smm // Making local copies of often-used variables improves both 306207753Smm // speed and readability. 307207753Smm 308207753Smm lzma_dict dict = *dictptr; 309207753Smm 310207753Smm const size_t dict_start = dict.pos; 311207753Smm 312207753Smm // Range decoder 313207753Smm rc_to_local(coder->rc, *in_pos); 314207753Smm 315207753Smm // State 316207753Smm uint32_t state = coder->state; 317207753Smm uint32_t rep0 = coder->rep0; 318207753Smm uint32_t rep1 = coder->rep1; 319207753Smm uint32_t rep2 = coder->rep2; 320207753Smm uint32_t rep3 = coder->rep3; 321207753Smm 322207753Smm const uint32_t pos_mask = coder->pos_mask; 323207753Smm 324207753Smm // These variables are actually needed only if we last time ran 325207753Smm // out of input in the middle of the decoder loop. 326207753Smm probability *probs = coder->probs; 327207753Smm uint32_t symbol = coder->symbol; 328207753Smm uint32_t limit = coder->limit; 329207753Smm uint32_t offset = coder->offset; 330207753Smm uint32_t len = coder->len; 331207753Smm 332207753Smm const uint32_t literal_pos_mask = coder->literal_pos_mask; 333207753Smm const uint32_t literal_context_bits = coder->literal_context_bits; 334207753Smm 335207753Smm // Temporary variables 336207753Smm uint32_t pos_state = dict.pos & pos_mask; 337207753Smm 338207753Smm lzma_ret ret = LZMA_OK; 339207753Smm 340207753Smm // If uncompressed size is known, there must be no end of payload 341207753Smm // marker. 342207753Smm const bool no_eopm = coder->uncompressed_size 343207753Smm != LZMA_VLI_UNKNOWN; 344207753Smm if (no_eopm && coder->uncompressed_size < dict.limit - dict.pos) 345207753Smm dict.limit = dict.pos + (size_t)(coder->uncompressed_size); 346207753Smm 347207753Smm // The main decoder loop. The "switch" is used to restart the decoder at 348207753Smm // correct location. Once restarted, the "switch" is no longer used. 349207753Smm switch (coder->sequence) 350207753Smm while (true) { 351207753Smm // Calculate new pos_state. This is skipped on the first loop 352207753Smm // since we already calculated it when setting up the local 353207753Smm // variables. 354207753Smm pos_state = dict.pos & pos_mask; 355207753Smm 356207753Smm case SEQ_NORMALIZE: 357207753Smm case SEQ_IS_MATCH: 358207753Smm if (unlikely(no_eopm && dict.pos == dict.limit)) 359207753Smm break; 360207753Smm 361207753Smm rc_if_0(coder->is_match[state][pos_state], SEQ_IS_MATCH) { 362207753Smm rc_update_0(coder->is_match[state][pos_state]); 363207753Smm 364207753Smm // It's a literal i.e. a single 8-bit byte. 365207753Smm 366207753Smm probs = literal_subcoder(coder->literal, 367207753Smm literal_context_bits, literal_pos_mask, 368207753Smm dict.pos, dict_get(&dict, 0)); 369207753Smm symbol = 1; 370207753Smm 371207753Smm if (is_literal_state(state)) { 372207753Smm // Decode literal without match byte. 373207753Smm#ifdef HAVE_SMALL 374207753Smm case SEQ_LITERAL: 375207753Smm do { 376207753Smm rc_bit(probs[symbol], , , SEQ_LITERAL); 377207753Smm } while (symbol < (1 << 8)); 378207753Smm#else 379207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL0); 380207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL1); 381207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL2); 382207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL3); 383207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL4); 384207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL5); 385207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL6); 386207753Smm rc_bit_case(probs[symbol], , , SEQ_LITERAL7); 387207753Smm#endif 388207753Smm } else { 389207753Smm // Decode literal with match byte. 390207753Smm // 391207753Smm // We store the byte we compare against 392207753Smm // ("match byte") to "len" to minimize the 393207753Smm // number of variables we need to store 394207753Smm // between decoder calls. 395207753Smm len = dict_get(&dict, rep0) << 1; 396207753Smm 397207753Smm // The usage of "offset" allows omitting some 398207753Smm // branches, which should give tiny speed 399207753Smm // improvement on some CPUs. "offset" gets 400207753Smm // set to zero if match_bit didn't match. 401207753Smm offset = 0x100; 402207753Smm 403207753Smm#ifdef HAVE_SMALL 404207753Smm case SEQ_LITERAL_MATCHED: 405207753Smm do { 406207753Smm const uint32_t match_bit 407207753Smm = len & offset; 408207753Smm const uint32_t subcoder_index 409207753Smm = offset + match_bit 410207753Smm + symbol; 411207753Smm 412207753Smm rc_bit(probs[subcoder_index], 413207753Smm offset &= ~match_bit, 414207753Smm offset &= match_bit, 415207753Smm SEQ_LITERAL_MATCHED); 416207753Smm 417207753Smm // It seems to be faster to do this 418207753Smm // here instead of putting it to the 419207753Smm // beginning of the loop and then 420207753Smm // putting the "case" in the middle 421207753Smm // of the loop. 422207753Smm len <<= 1; 423207753Smm 424207753Smm } while (symbol < (1 << 8)); 425207753Smm#else 426207753Smm // Unroll the loop. 427207753Smm uint32_t match_bit; 428207753Smm uint32_t subcoder_index; 429207753Smm 430207753Smm# define d(seq) \ 431207753Smm case seq: \ 432207753Smm match_bit = len & offset; \ 433207753Smm subcoder_index = offset + match_bit + symbol; \ 434207753Smm rc_bit(probs[subcoder_index], \ 435207753Smm offset &= ~match_bit, \ 436207753Smm offset &= match_bit, \ 437207753Smm seq) 438207753Smm 439207753Smm d(SEQ_LITERAL_MATCHED0); 440207753Smm len <<= 1; 441207753Smm d(SEQ_LITERAL_MATCHED1); 442207753Smm len <<= 1; 443207753Smm d(SEQ_LITERAL_MATCHED2); 444207753Smm len <<= 1; 445207753Smm d(SEQ_LITERAL_MATCHED3); 446207753Smm len <<= 1; 447207753Smm d(SEQ_LITERAL_MATCHED4); 448207753Smm len <<= 1; 449207753Smm d(SEQ_LITERAL_MATCHED5); 450207753Smm len <<= 1; 451207753Smm d(SEQ_LITERAL_MATCHED6); 452207753Smm len <<= 1; 453207753Smm d(SEQ_LITERAL_MATCHED7); 454207753Smm# undef d 455207753Smm#endif 456207753Smm } 457207753Smm 458207753Smm //update_literal(state); 459207753Smm // Use a lookup table to update to literal state, 460207753Smm // since compared to other state updates, this would 461207753Smm // need two branches. 462207753Smm static const lzma_lzma_state next_state[] = { 463207753Smm STATE_LIT_LIT, 464207753Smm STATE_LIT_LIT, 465207753Smm STATE_LIT_LIT, 466207753Smm STATE_LIT_LIT, 467207753Smm STATE_MATCH_LIT_LIT, 468207753Smm STATE_REP_LIT_LIT, 469207753Smm STATE_SHORTREP_LIT_LIT, 470207753Smm STATE_MATCH_LIT, 471207753Smm STATE_REP_LIT, 472207753Smm STATE_SHORTREP_LIT, 473207753Smm STATE_MATCH_LIT, 474207753Smm STATE_REP_LIT 475207753Smm }; 476207753Smm state = next_state[state]; 477207753Smm 478207753Smm case SEQ_LITERAL_WRITE: 479207753Smm if (unlikely(dict_put(&dict, symbol))) { 480207753Smm coder->sequence = SEQ_LITERAL_WRITE; 481207753Smm goto out; 482207753Smm } 483207753Smm 484207753Smm continue; 485207753Smm } 486207753Smm 487207753Smm // Instead of a new byte we are going to get a byte range 488207753Smm // (distance and length) which will be repeated from our 489207753Smm // output history. 490207753Smm 491207753Smm rc_update_1(coder->is_match[state][pos_state]); 492207753Smm 493207753Smm case SEQ_IS_REP: 494207753Smm rc_if_0(coder->is_rep[state], SEQ_IS_REP) { 495207753Smm // Not a repeated match 496207753Smm rc_update_0(coder->is_rep[state]); 497207753Smm update_match(state); 498207753Smm 499207753Smm // The latest three match distances are kept in 500207753Smm // memory in case there are repeated matches. 501207753Smm rep3 = rep2; 502207753Smm rep2 = rep1; 503207753Smm rep1 = rep0; 504207753Smm 505207753Smm // Decode the length of the match. 506207753Smm len_decode(len, coder->match_len_decoder, 507207753Smm pos_state, SEQ_MATCH_LEN); 508207753Smm 509207753Smm // Prepare to decode the highest two bits of the 510207753Smm // match distance. 511292588Sdelphij probs = coder->dist_slot[get_dist_state(len)]; 512207753Smm symbol = 1; 513207753Smm 514207753Smm#ifdef HAVE_SMALL 515292588Sdelphij case SEQ_DIST_SLOT: 516207753Smm do { 517292588Sdelphij rc_bit(probs[symbol], , , SEQ_DIST_SLOT); 518292588Sdelphij } while (symbol < DIST_SLOTS); 519207753Smm#else 520292588Sdelphij rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT0); 521292588Sdelphij rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT1); 522292588Sdelphij rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT2); 523292588Sdelphij rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT3); 524292588Sdelphij rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT4); 525292588Sdelphij rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT5); 526207753Smm#endif 527207753Smm // Get rid of the highest bit that was needed for 528207753Smm // indexing of the probability array. 529292588Sdelphij symbol -= DIST_SLOTS; 530207753Smm assert(symbol <= 63); 531207753Smm 532292588Sdelphij if (symbol < DIST_MODEL_START) { 533207753Smm // Match distances [0, 3] have only two bits. 534207753Smm rep0 = symbol; 535207753Smm } else { 536207753Smm // Decode the lowest [1, 29] bits of 537207753Smm // the match distance. 538207753Smm limit = (symbol >> 1) - 1; 539207753Smm assert(limit >= 1 && limit <= 30); 540207753Smm rep0 = 2 + (symbol & 1); 541207753Smm 542292588Sdelphij if (symbol < DIST_MODEL_END) { 543207753Smm // Prepare to decode the low bits for 544207753Smm // a distance of [4, 127]. 545207753Smm assert(limit <= 5); 546207753Smm rep0 <<= limit; 547207753Smm assert(rep0 <= 96); 548207753Smm // -1 is fine, because we start 549207753Smm // decoding at probs[1], not probs[0]. 550207753Smm // NOTE: This violates the C standard, 551207753Smm // since we are doing pointer 552207753Smm // arithmetic past the beginning of 553207753Smm // the array. 554207753Smm assert((int32_t)(rep0 - symbol - 1) 555207753Smm >= -1); 556207753Smm assert((int32_t)(rep0 - symbol - 1) 557207753Smm <= 82); 558207753Smm probs = coder->pos_special + rep0 559207753Smm - symbol - 1; 560207753Smm symbol = 1; 561207753Smm offset = 0; 562292588Sdelphij case SEQ_DIST_MODEL: 563207753Smm#ifdef HAVE_SMALL 564207753Smm do { 565207753Smm rc_bit(probs[symbol], , 566207753Smm rep0 += 1 << offset, 567292588Sdelphij SEQ_DIST_MODEL); 568207753Smm } while (++offset < limit); 569207753Smm#else 570207753Smm switch (limit) { 571207753Smm case 5: 572207753Smm assert(offset == 0); 573207753Smm rc_bit(probs[symbol], , 574207753Smm rep0 += 1, 575292588Sdelphij SEQ_DIST_MODEL); 576207753Smm ++offset; 577207753Smm --limit; 578207753Smm case 4: 579207753Smm rc_bit(probs[symbol], , 580207753Smm rep0 += 1 << offset, 581292588Sdelphij SEQ_DIST_MODEL); 582207753Smm ++offset; 583207753Smm --limit; 584207753Smm case 3: 585207753Smm rc_bit(probs[symbol], , 586207753Smm rep0 += 1 << offset, 587292588Sdelphij SEQ_DIST_MODEL); 588207753Smm ++offset; 589207753Smm --limit; 590207753Smm case 2: 591207753Smm rc_bit(probs[symbol], , 592207753Smm rep0 += 1 << offset, 593292588Sdelphij SEQ_DIST_MODEL); 594207753Smm ++offset; 595207753Smm --limit; 596207753Smm case 1: 597207753Smm // We need "symbol" only for 598207753Smm // indexing the probability 599207753Smm // array, thus we can use 600207753Smm // rc_bit_last() here to omit 601207753Smm // the unneeded updating of 602207753Smm // "symbol". 603207753Smm rc_bit_last(probs[symbol], , 604207753Smm rep0 += 1 << offset, 605292588Sdelphij SEQ_DIST_MODEL); 606207753Smm } 607207753Smm#endif 608207753Smm } else { 609207753Smm // The distance is >= 128. Decode the 610207753Smm // lower bits without probabilities 611207753Smm // except the lowest four bits. 612207753Smm assert(symbol >= 14); 613207753Smm assert(limit >= 6); 614207753Smm limit -= ALIGN_BITS; 615207753Smm assert(limit >= 2); 616207753Smm case SEQ_DIRECT: 617207753Smm // Not worth manual unrolling 618207753Smm do { 619207753Smm rc_direct(rep0, SEQ_DIRECT); 620207753Smm } while (--limit > 0); 621207753Smm 622207753Smm // Decode the lowest four bits using 623207753Smm // probabilities. 624207753Smm rep0 <<= ALIGN_BITS; 625207753Smm symbol = 1; 626207753Smm#ifdef HAVE_SMALL 627207753Smm offset = 0; 628207753Smm case SEQ_ALIGN: 629207753Smm do { 630207753Smm rc_bit(coder->pos_align[ 631207753Smm symbol], , 632207753Smm rep0 += 1 << offset, 633207753Smm SEQ_ALIGN); 634207753Smm } while (++offset < ALIGN_BITS); 635207753Smm#else 636207753Smm case SEQ_ALIGN0: 637207753Smm rc_bit(coder->pos_align[symbol], , 638207753Smm rep0 += 1, SEQ_ALIGN0); 639207753Smm case SEQ_ALIGN1: 640207753Smm rc_bit(coder->pos_align[symbol], , 641207753Smm rep0 += 2, SEQ_ALIGN1); 642207753Smm case SEQ_ALIGN2: 643207753Smm rc_bit(coder->pos_align[symbol], , 644207753Smm rep0 += 4, SEQ_ALIGN2); 645207753Smm case SEQ_ALIGN3: 646292588Sdelphij // Like in SEQ_DIST_MODEL, we don't 647207753Smm // need "symbol" for anything else 648207753Smm // than indexing the probability array. 649207753Smm rc_bit_last(coder->pos_align[symbol], , 650207753Smm rep0 += 8, SEQ_ALIGN3); 651207753Smm#endif 652207753Smm 653207753Smm if (rep0 == UINT32_MAX) { 654207753Smm // End of payload marker was 655207753Smm // found. It must not be 656207753Smm // present if uncompressed 657207753Smm // size is known. 658207753Smm if (coder->uncompressed_size 659207753Smm != LZMA_VLI_UNKNOWN) { 660207753Smm ret = LZMA_DATA_ERROR; 661207753Smm goto out; 662207753Smm } 663207753Smm 664207753Smm case SEQ_EOPM: 665215187Smm // LZMA1 stream with 666215187Smm // end-of-payload marker. 667207753Smm rc_normalize(SEQ_EOPM); 668207753Smm ret = LZMA_STREAM_END; 669207753Smm goto out; 670207753Smm } 671207753Smm } 672207753Smm } 673207753Smm 674207753Smm // Validate the distance we just decoded. 675207753Smm if (unlikely(!dict_is_distance_valid(&dict, rep0))) { 676207753Smm ret = LZMA_DATA_ERROR; 677207753Smm goto out; 678207753Smm } 679207753Smm 680207753Smm } else { 681207753Smm rc_update_1(coder->is_rep[state]); 682207753Smm 683207753Smm // Repeated match 684207753Smm // 685207753Smm // The match distance is a value that we have had 686207753Smm // earlier. The latest four match distances are 687207753Smm // available as rep0, rep1, rep2 and rep3. We will 688207753Smm // now decode which of them is the new distance. 689207753Smm // 690207753Smm // There cannot be a match if we haven't produced 691207753Smm // any output, so check that first. 692207753Smm if (unlikely(!dict_is_distance_valid(&dict, 0))) { 693207753Smm ret = LZMA_DATA_ERROR; 694207753Smm goto out; 695207753Smm } 696207753Smm 697207753Smm case SEQ_IS_REP0: 698207753Smm rc_if_0(coder->is_rep0[state], SEQ_IS_REP0) { 699207753Smm rc_update_0(coder->is_rep0[state]); 700207753Smm // The distance is rep0. 701207753Smm 702207753Smm case SEQ_IS_REP0_LONG: 703207753Smm rc_if_0(coder->is_rep0_long[state][pos_state], 704207753Smm SEQ_IS_REP0_LONG) { 705207753Smm rc_update_0(coder->is_rep0_long[ 706207753Smm state][pos_state]); 707207753Smm 708207753Smm update_short_rep(state); 709207753Smm 710207753Smm case SEQ_SHORTREP: 711207753Smm if (unlikely(dict_put(&dict, dict_get( 712207753Smm &dict, rep0)))) { 713207753Smm coder->sequence = SEQ_SHORTREP; 714207753Smm goto out; 715207753Smm } 716207753Smm 717207753Smm continue; 718207753Smm } 719207753Smm 720207753Smm // Repeating more than one byte at 721207753Smm // distance of rep0. 722207753Smm rc_update_1(coder->is_rep0_long[ 723207753Smm state][pos_state]); 724207753Smm 725207753Smm } else { 726207753Smm rc_update_1(coder->is_rep0[state]); 727207753Smm 728207753Smm case SEQ_IS_REP1: 729207753Smm // The distance is rep1, rep2 or rep3. Once 730207753Smm // we find out which one of these three, it 731207753Smm // is stored to rep0 and rep1, rep2 and rep3 732207753Smm // are updated accordingly. 733207753Smm rc_if_0(coder->is_rep1[state], SEQ_IS_REP1) { 734207753Smm rc_update_0(coder->is_rep1[state]); 735207753Smm 736207753Smm const uint32_t distance = rep1; 737207753Smm rep1 = rep0; 738207753Smm rep0 = distance; 739207753Smm 740207753Smm } else { 741207753Smm rc_update_1(coder->is_rep1[state]); 742207753Smm case SEQ_IS_REP2: 743207753Smm rc_if_0(coder->is_rep2[state], 744207753Smm SEQ_IS_REP2) { 745207753Smm rc_update_0(coder->is_rep2[ 746207753Smm state]); 747207753Smm 748207753Smm const uint32_t distance = rep2; 749207753Smm rep2 = rep1; 750207753Smm rep1 = rep0; 751207753Smm rep0 = distance; 752207753Smm 753207753Smm } else { 754207753Smm rc_update_1(coder->is_rep2[ 755207753Smm state]); 756207753Smm 757207753Smm const uint32_t distance = rep3; 758207753Smm rep3 = rep2; 759207753Smm rep2 = rep1; 760207753Smm rep1 = rep0; 761207753Smm rep0 = distance; 762207753Smm } 763207753Smm } 764207753Smm } 765207753Smm 766207753Smm update_long_rep(state); 767207753Smm 768207753Smm // Decode the length of the repeated match. 769207753Smm len_decode(len, coder->rep_len_decoder, 770207753Smm pos_state, SEQ_REP_LEN); 771207753Smm } 772207753Smm 773207753Smm ///////////////////////////////// 774207753Smm // Repeat from history buffer. // 775207753Smm ///////////////////////////////// 776207753Smm 777207753Smm // The length is always between these limits. There is no way 778207753Smm // to trigger the algorithm to set len outside this range. 779207753Smm assert(len >= MATCH_LEN_MIN); 780207753Smm assert(len <= MATCH_LEN_MAX); 781207753Smm 782207753Smm case SEQ_COPY: 783207753Smm // Repeat len bytes from distance of rep0. 784207753Smm if (unlikely(dict_repeat(&dict, rep0, &len))) { 785207753Smm coder->sequence = SEQ_COPY; 786207753Smm goto out; 787207753Smm } 788207753Smm } 789207753Smm 790207753Smm rc_normalize(SEQ_NORMALIZE); 791207753Smm coder->sequence = SEQ_IS_MATCH; 792207753Smm 793207753Smmout: 794207753Smm // Save state 795207753Smm 796207753Smm // NOTE: Must not copy dict.limit. 797207753Smm dictptr->pos = dict.pos; 798207753Smm dictptr->full = dict.full; 799207753Smm 800207753Smm rc_from_local(coder->rc, *in_pos); 801207753Smm 802207753Smm coder->state = state; 803207753Smm coder->rep0 = rep0; 804207753Smm coder->rep1 = rep1; 805207753Smm coder->rep2 = rep2; 806207753Smm coder->rep3 = rep3; 807207753Smm 808207753Smm coder->probs = probs; 809207753Smm coder->symbol = symbol; 810207753Smm coder->limit = limit; 811207753Smm coder->offset = offset; 812207753Smm coder->len = len; 813207753Smm 814207753Smm // Update the remaining amount of uncompressed data if uncompressed 815207753Smm // size was known. 816207753Smm if (coder->uncompressed_size != LZMA_VLI_UNKNOWN) { 817207753Smm coder->uncompressed_size -= dict.pos - dict_start; 818207753Smm 819207753Smm // Since there cannot be end of payload marker if the 820207753Smm // uncompressed size was known, we check here if we 821207753Smm // finished decoding. 822207753Smm if (coder->uncompressed_size == 0 && ret == LZMA_OK 823207753Smm && coder->sequence != SEQ_NORMALIZE) 824207753Smm ret = coder->sequence == SEQ_IS_MATCH 825207753Smm ? LZMA_STREAM_END : LZMA_DATA_ERROR; 826207753Smm } 827207753Smm 828207753Smm // We can do an additional check in the range decoder to catch some 829207753Smm // corrupted files. 830207753Smm if (ret == LZMA_STREAM_END) { 831207753Smm if (!rc_is_finished(coder->rc)) 832207753Smm ret = LZMA_DATA_ERROR; 833207753Smm 834207753Smm // Reset the range decoder so that it is ready to reinitialize 835207753Smm // for a new LZMA2 chunk. 836207753Smm rc_reset(coder->rc); 837207753Smm } 838207753Smm 839207753Smm return ret; 840207753Smm} 841207753Smm 842207753Smm 843207753Smm 844207753Smmstatic void 845312518Sdelphijlzma_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size) 846207753Smm{ 847312518Sdelphij lzma_lzma1_decoder *coder = coder_ptr; 848207753Smm coder->uncompressed_size = uncompressed_size; 849207753Smm} 850207753Smm 851207753Smm 852207753Smmstatic void 853312518Sdelphijlzma_decoder_reset(void *coder_ptr, const void *opt) 854207753Smm{ 855312518Sdelphij lzma_lzma1_decoder *coder = coder_ptr; 856207753Smm const lzma_options_lzma *options = opt; 857207753Smm 858207753Smm // NOTE: We assume that lc/lp/pb are valid since they were 859207753Smm // successfully decoded with lzma_lzma_decode_properties(). 860207753Smm 861207753Smm // Calculate pos_mask. We don't need pos_bits as is for anything. 862207753Smm coder->pos_mask = (1U << options->pb) - 1; 863207753Smm 864207753Smm // Initialize the literal decoder. 865207753Smm literal_init(coder->literal, options->lc, options->lp); 866207753Smm 867207753Smm coder->literal_context_bits = options->lc; 868207753Smm coder->literal_pos_mask = (1U << options->lp) - 1; 869207753Smm 870207753Smm // State 871207753Smm coder->state = STATE_LIT_LIT; 872207753Smm coder->rep0 = 0; 873207753Smm coder->rep1 = 0; 874207753Smm coder->rep2 = 0; 875207753Smm coder->rep3 = 0; 876207753Smm coder->pos_mask = (1U << options->pb) - 1; 877207753Smm 878207753Smm // Range decoder 879207753Smm rc_reset(coder->rc); 880207753Smm 881207753Smm // Bit and bittree decoders 882207753Smm for (uint32_t i = 0; i < STATES; ++i) { 883207753Smm for (uint32_t j = 0; j <= coder->pos_mask; ++j) { 884207753Smm bit_reset(coder->is_match[i][j]); 885207753Smm bit_reset(coder->is_rep0_long[i][j]); 886207753Smm } 887207753Smm 888207753Smm bit_reset(coder->is_rep[i]); 889207753Smm bit_reset(coder->is_rep0[i]); 890207753Smm bit_reset(coder->is_rep1[i]); 891207753Smm bit_reset(coder->is_rep2[i]); 892207753Smm } 893207753Smm 894292588Sdelphij for (uint32_t i = 0; i < DIST_STATES; ++i) 895292588Sdelphij bittree_reset(coder->dist_slot[i], DIST_SLOT_BITS); 896207753Smm 897292588Sdelphij for (uint32_t i = 0; i < FULL_DISTANCES - DIST_MODEL_END; ++i) 898207753Smm bit_reset(coder->pos_special[i]); 899207753Smm 900207753Smm bittree_reset(coder->pos_align, ALIGN_BITS); 901207753Smm 902207753Smm // Len decoders (also bit/bittree) 903207753Smm const uint32_t num_pos_states = 1U << options->pb; 904207753Smm bit_reset(coder->match_len_decoder.choice); 905207753Smm bit_reset(coder->match_len_decoder.choice2); 906207753Smm bit_reset(coder->rep_len_decoder.choice); 907207753Smm bit_reset(coder->rep_len_decoder.choice2); 908207753Smm 909207753Smm for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) { 910207753Smm bittree_reset(coder->match_len_decoder.low[pos_state], 911207753Smm LEN_LOW_BITS); 912207753Smm bittree_reset(coder->match_len_decoder.mid[pos_state], 913207753Smm LEN_MID_BITS); 914207753Smm 915207753Smm bittree_reset(coder->rep_len_decoder.low[pos_state], 916207753Smm LEN_LOW_BITS); 917207753Smm bittree_reset(coder->rep_len_decoder.mid[pos_state], 918207753Smm LEN_MID_BITS); 919207753Smm } 920207753Smm 921207753Smm bittree_reset(coder->match_len_decoder.high, LEN_HIGH_BITS); 922207753Smm bittree_reset(coder->rep_len_decoder.high, LEN_HIGH_BITS); 923207753Smm 924207753Smm coder->sequence = SEQ_IS_MATCH; 925207753Smm coder->probs = NULL; 926207753Smm coder->symbol = 0; 927207753Smm coder->limit = 0; 928207753Smm coder->offset = 0; 929207753Smm coder->len = 0; 930207753Smm 931207753Smm return; 932207753Smm} 933207753Smm 934207753Smm 935207753Smmextern lzma_ret 936292588Sdelphijlzma_lzma_decoder_create(lzma_lz_decoder *lz, const lzma_allocator *allocator, 937207753Smm const void *opt, lzma_lz_options *lz_options) 938207753Smm{ 939207753Smm if (lz->coder == NULL) { 940312518Sdelphij lz->coder = lzma_alloc(sizeof(lzma_lzma1_decoder), allocator); 941207753Smm if (lz->coder == NULL) 942207753Smm return LZMA_MEM_ERROR; 943207753Smm 944207753Smm lz->code = &lzma_decode; 945207753Smm lz->reset = &lzma_decoder_reset; 946207753Smm lz->set_uncompressed = &lzma_decoder_uncompressed; 947207753Smm } 948207753Smm 949207753Smm // All dictionary sizes are OK here. LZ decoder will take care of 950207753Smm // the special cases. 951207753Smm const lzma_options_lzma *options = opt; 952207753Smm lz_options->dict_size = options->dict_size; 953207753Smm lz_options->preset_dict = options->preset_dict; 954207753Smm lz_options->preset_dict_size = options->preset_dict_size; 955207753Smm 956207753Smm return LZMA_OK; 957207753Smm} 958207753Smm 959207753Smm 960207753Smm/// Allocate and initialize LZMA decoder. This is used only via LZ 961207753Smm/// initialization (lzma_lzma_decoder_init() passes function pointer to 962207753Smm/// the LZ initialization). 963207753Smmstatic lzma_ret 964292588Sdelphijlzma_decoder_init(lzma_lz_decoder *lz, const lzma_allocator *allocator, 965207753Smm const void *options, lzma_lz_options *lz_options) 966207753Smm{ 967207753Smm if (!is_lclppb_valid(options)) 968207753Smm return LZMA_PROG_ERROR; 969207753Smm 970207753Smm return_if_error(lzma_lzma_decoder_create( 971207753Smm lz, allocator, options, lz_options)); 972207753Smm 973207753Smm lzma_decoder_reset(lz->coder, options); 974207753Smm lzma_decoder_uncompressed(lz->coder, LZMA_VLI_UNKNOWN); 975207753Smm 976207753Smm return LZMA_OK; 977207753Smm} 978207753Smm 979207753Smm 980207753Smmextern lzma_ret 981292588Sdelphijlzma_lzma_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator, 982207753Smm const lzma_filter_info *filters) 983207753Smm{ 984207753Smm // LZMA can only be the last filter in the chain. This is enforced 985207753Smm // by the raw_decoder initialization. 986207753Smm assert(filters[1].init == NULL); 987207753Smm 988207753Smm return lzma_lz_decoder_init(next, allocator, filters, 989207753Smm &lzma_decoder_init); 990207753Smm} 991207753Smm 992207753Smm 993207753Smmextern bool 994207753Smmlzma_lzma_lclppb_decode(lzma_options_lzma *options, uint8_t byte) 995207753Smm{ 996207753Smm if (byte > (4 * 5 + 4) * 9 + 8) 997207753Smm return true; 998207753Smm 999207753Smm // See the file format specification to understand this. 1000207753Smm options->pb = byte / (9 * 5); 1001207753Smm byte -= options->pb * 9 * 5; 1002207753Smm options->lp = byte / 9; 1003207753Smm options->lc = byte - options->lp * 9; 1004207753Smm 1005207753Smm return options->lc + options->lp > LZMA_LCLP_MAX; 1006207753Smm} 1007207753Smm 1008207753Smm 1009207753Smmextern uint64_t 1010207753Smmlzma_lzma_decoder_memusage_nocheck(const void *options) 1011207753Smm{ 1012207753Smm const lzma_options_lzma *const opt = options; 1013312518Sdelphij return sizeof(lzma_lzma1_decoder) 1014312518Sdelphij + lzma_lz_decoder_memusage(opt->dict_size); 1015207753Smm} 1016207753Smm 1017207753Smm 1018207753Smmextern uint64_t 1019207753Smmlzma_lzma_decoder_memusage(const void *options) 1020207753Smm{ 1021207753Smm if (!is_lclppb_valid(options)) 1022207753Smm return UINT64_MAX; 1023207753Smm 1024207753Smm return lzma_lzma_decoder_memusage_nocheck(options); 1025207753Smm} 1026207753Smm 1027207753Smm 1028207753Smmextern lzma_ret 1029292588Sdelphijlzma_lzma_props_decode(void **options, const lzma_allocator *allocator, 1030207753Smm const uint8_t *props, size_t props_size) 1031207753Smm{ 1032207753Smm if (props_size != 5) 1033207753Smm return LZMA_OPTIONS_ERROR; 1034207753Smm 1035207753Smm lzma_options_lzma *opt 1036207753Smm = lzma_alloc(sizeof(lzma_options_lzma), allocator); 1037207753Smm if (opt == NULL) 1038207753Smm return LZMA_MEM_ERROR; 1039207753Smm 1040207753Smm if (lzma_lzma_lclppb_decode(opt, props[0])) 1041207753Smm goto error; 1042207753Smm 1043207753Smm // All dictionary sizes are accepted, including zero. LZ decoder 1044207753Smm // will automatically use a dictionary at least a few KiB even if 1045207753Smm // a smaller dictionary is requested. 1046207753Smm opt->dict_size = unaligned_read32le(props + 1); 1047207753Smm 1048207753Smm opt->preset_dict = NULL; 1049207753Smm opt->preset_dict_size = 0; 1050207753Smm 1051207753Smm *options = opt; 1052207753Smm 1053207753Smm return LZMA_OK; 1054207753Smm 1055207753Smmerror: 1056207753Smm lzma_free(opt, allocator); 1057207753Smm return LZMA_OPTIONS_ERROR; 1058207753Smm} 1059