lzma_decoder.c revision 292588
1/////////////////////////////////////////////////////////////////////////////// 2// 3/// \file lzma_decoder.c 4/// \brief LZMA decoder 5/// 6// Authors: Igor Pavlov 7// Lasse Collin 8// 9// This file has been put into the public domain. 10// You can do whatever you want with this file. 11// 12/////////////////////////////////////////////////////////////////////////////// 13 14#include "lz_decoder.h" 15#include "lzma_common.h" 16#include "lzma_decoder.h" 17#include "range_decoder.h" 18 19 20#ifdef HAVE_SMALL 21 22// Macros for (somewhat) size-optimized code. 23#define seq_4(seq) seq 24 25#define seq_6(seq) seq 26 27#define seq_8(seq) seq 28 29#define seq_len(seq) \ 30 seq ## _CHOICE, \ 31 seq ## _CHOICE2, \ 32 seq ## _BITTREE 33 34#define len_decode(target, ld, pos_state, seq) \ 35do { \ 36case seq ## _CHOICE: \ 37 rc_if_0(ld.choice, seq ## _CHOICE) { \ 38 rc_update_0(ld.choice); \ 39 probs = ld.low[pos_state];\ 40 limit = LEN_LOW_SYMBOLS; \ 41 target = MATCH_LEN_MIN; \ 42 } else { \ 43 rc_update_1(ld.choice); \ 44case seq ## _CHOICE2: \ 45 rc_if_0(ld.choice2, seq ## _CHOICE2) { \ 46 rc_update_0(ld.choice2); \ 47 probs = ld.mid[pos_state]; \ 48 limit = LEN_MID_SYMBOLS; \ 49 target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \ 50 } else { \ 51 rc_update_1(ld.choice2); \ 52 probs = ld.high; \ 53 limit = LEN_HIGH_SYMBOLS; \ 54 target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS \ 55 + LEN_MID_SYMBOLS; \ 56 } \ 57 } \ 58 symbol = 1; \ 59case seq ## _BITTREE: \ 60 do { \ 61 rc_bit(probs[symbol], , , seq ## _BITTREE); \ 62 } while (symbol < limit); \ 63 target += symbol - limit; \ 64} while (0) 65 66#else // HAVE_SMALL 67 68// Unrolled versions 69#define seq_4(seq) \ 70 seq ## 0, \ 71 seq ## 1, \ 72 seq ## 2, \ 73 seq ## 3 74 75#define seq_6(seq) \ 76 seq ## 0, \ 77 seq ## 1, \ 78 seq ## 2, \ 79 seq ## 3, \ 80 seq ## 4, \ 81 seq ## 5 82 83#define seq_8(seq) \ 84 seq ## 0, \ 85 seq ## 1, \ 86 seq ## 2, \ 87 seq ## 3, \ 88 seq ## 4, \ 89 seq ## 5, \ 90 seq ## 6, \ 91 seq ## 7 92 93#define seq_len(seq) \ 94 seq ## _CHOICE, \ 95 seq ## _LOW0, \ 96 seq ## _LOW1, \ 97 seq ## _LOW2, \ 98 seq ## _CHOICE2, \ 99 seq ## _MID0, \ 100 seq ## _MID1, \ 101 seq ## _MID2, \ 102 seq ## _HIGH0, \ 103 seq ## _HIGH1, \ 104 seq ## _HIGH2, \ 105 seq ## _HIGH3, \ 106 seq ## _HIGH4, \ 107 seq ## _HIGH5, \ 108 seq ## _HIGH6, \ 109 seq ## _HIGH7 110 111#define len_decode(target, ld, pos_state, seq) \ 112do { \ 113 symbol = 1; \ 114case seq ## _CHOICE: \ 115 rc_if_0(ld.choice, seq ## _CHOICE) { \ 116 rc_update_0(ld.choice); \ 117 rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW0); \ 118 rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW1); \ 119 rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW2); \ 120 target = symbol - LEN_LOW_SYMBOLS + MATCH_LEN_MIN; \ 121 } else { \ 122 rc_update_1(ld.choice); \ 123case seq ## _CHOICE2: \ 124 rc_if_0(ld.choice2, seq ## _CHOICE2) { \ 125 rc_update_0(ld.choice2); \ 126 rc_bit_case(ld.mid[pos_state][symbol], , , \ 127 seq ## _MID0); \ 128 rc_bit_case(ld.mid[pos_state][symbol], , , \ 129 seq ## _MID1); \ 130 rc_bit_case(ld.mid[pos_state][symbol], , , \ 131 seq ## _MID2); \ 132 target = symbol - LEN_MID_SYMBOLS \ 133 + MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \ 134 } else { \ 135 rc_update_1(ld.choice2); \ 136 rc_bit_case(ld.high[symbol], , , seq ## _HIGH0); \ 137 rc_bit_case(ld.high[symbol], , , seq ## _HIGH1); \ 138 rc_bit_case(ld.high[symbol], , , seq ## _HIGH2); \ 139 rc_bit_case(ld.high[symbol], , , seq ## _HIGH3); \ 140 rc_bit_case(ld.high[symbol], , , seq ## _HIGH4); \ 141 rc_bit_case(ld.high[symbol], , , seq ## _HIGH5); \ 142 rc_bit_case(ld.high[symbol], , , seq ## _HIGH6); \ 143 rc_bit_case(ld.high[symbol], , , seq ## _HIGH7); \ 144 target = symbol - LEN_HIGH_SYMBOLS \ 145 + MATCH_LEN_MIN \ 146 + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \ 147 } \ 148 } \ 149} while (0) 150 151#endif // HAVE_SMALL 152 153 154/// Length decoder probabilities; see comments in lzma_common.h. 155typedef struct { 156 probability choice; 157 probability choice2; 158 probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS]; 159 probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS]; 160 probability high[LEN_HIGH_SYMBOLS]; 161} lzma_length_decoder; 162 163 164struct lzma_coder_s { 165 /////////////////// 166 // Probabilities // 167 /////////////////// 168 169 /// Literals; see comments in lzma_common.h. 170 probability literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE]; 171 172 /// If 1, it's a match. Otherwise it's a single 8-bit literal. 173 probability is_match[STATES][POS_STATES_MAX]; 174 175 /// If 1, it's a repeated match. The distance is one of rep0 .. rep3. 176 probability is_rep[STATES]; 177 178 /// If 0, distance of a repeated match is rep0. 179 /// Otherwise check is_rep1. 180 probability is_rep0[STATES]; 181 182 /// If 0, distance of a repeated match is rep1. 183 /// Otherwise check is_rep2. 184 probability is_rep1[STATES]; 185 186 /// If 0, distance of a repeated match is rep2. Otherwise it is rep3. 187 probability is_rep2[STATES]; 188 189 /// If 1, the repeated match has length of one byte. Otherwise 190 /// the length is decoded from rep_len_decoder. 191 probability is_rep0_long[STATES][POS_STATES_MAX]; 192 193 /// Probability tree for the highest two bits of the match distance. 194 /// There is a separate probability tree for match lengths of 195 /// 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273]. 196 probability dist_slot[DIST_STATES][DIST_SLOTS]; 197 198 /// Probability trees for additional bits for match distance when the 199 /// distance is in the range [4, 127]. 200 probability pos_special[FULL_DISTANCES - DIST_MODEL_END]; 201 202 /// Probability tree for the lowest four bits of a match distance 203 /// that is equal to or greater than 128. 204 probability pos_align[ALIGN_SIZE]; 205 206 /// Length of a normal match 207 lzma_length_decoder match_len_decoder; 208 209 /// Length of a repeated match 210 lzma_length_decoder rep_len_decoder; 211 212 /////////////////// 213 // Decoder state // 214 /////////////////// 215 216 // Range coder 217 lzma_range_decoder rc; 218 219 // Types of the most recently seen LZMA symbols 220 lzma_lzma_state state; 221 222 uint32_t rep0; ///< Distance of the latest match 223 uint32_t rep1; ///< Distance of second latest match 224 uint32_t rep2; ///< Distance of third latest match 225 uint32_t rep3; ///< Distance of fourth latest match 226 227 uint32_t pos_mask; // (1U << pb) - 1 228 uint32_t literal_context_bits; 229 uint32_t literal_pos_mask; 230 231 /// Uncompressed size as bytes, or LZMA_VLI_UNKNOWN if end of 232 /// payload marker is expected. 233 lzma_vli uncompressed_size; 234 235 //////////////////////////////// 236 // State of incomplete symbol // 237 //////////////////////////////// 238 239 /// Position where to continue the decoder loop 240 enum { 241 SEQ_NORMALIZE, 242 SEQ_IS_MATCH, 243 seq_8(SEQ_LITERAL), 244 seq_8(SEQ_LITERAL_MATCHED), 245 SEQ_LITERAL_WRITE, 246 SEQ_IS_REP, 247 seq_len(SEQ_MATCH_LEN), 248 seq_6(SEQ_DIST_SLOT), 249 SEQ_DIST_MODEL, 250 SEQ_DIRECT, 251 seq_4(SEQ_ALIGN), 252 SEQ_EOPM, 253 SEQ_IS_REP0, 254 SEQ_SHORTREP, 255 SEQ_IS_REP0_LONG, 256 SEQ_IS_REP1, 257 SEQ_IS_REP2, 258 seq_len(SEQ_REP_LEN), 259 SEQ_COPY, 260 } sequence; 261 262 /// Base of the current probability tree 263 probability *probs; 264 265 /// Symbol being decoded. This is also used as an index variable in 266 /// bittree decoders: probs[symbol] 267 uint32_t symbol; 268 269 /// Used as a loop termination condition on bittree decoders and 270 /// direct bits decoder. 271 uint32_t limit; 272 273 /// Matched literal decoder: 0x100 or 0 to help avoiding branches. 274 /// Bittree reverse decoders: Offset of the next bit: 1 << offset 275 uint32_t offset; 276 277 /// If decoding a literal: match byte. 278 /// If decoding a match: length of the match. 279 uint32_t len; 280}; 281 282 283static lzma_ret 284lzma_decode(lzma_coder *restrict coder, lzma_dict *restrict dictptr, 285 const uint8_t *restrict in, 286 size_t *restrict in_pos, size_t in_size) 287{ 288 //////////////////// 289 // Initialization // 290 //////////////////// 291 292 { 293 const lzma_ret ret = rc_read_init( 294 &coder->rc, in, in_pos, in_size); 295 if (ret != LZMA_STREAM_END) 296 return ret; 297 } 298 299 /////////////// 300 // Variables // 301 /////////////// 302 303 // Making local copies of often-used variables improves both 304 // speed and readability. 305 306 lzma_dict dict = *dictptr; 307 308 const size_t dict_start = dict.pos; 309 310 // Range decoder 311 rc_to_local(coder->rc, *in_pos); 312 313 // State 314 uint32_t state = coder->state; 315 uint32_t rep0 = coder->rep0; 316 uint32_t rep1 = coder->rep1; 317 uint32_t rep2 = coder->rep2; 318 uint32_t rep3 = coder->rep3; 319 320 const uint32_t pos_mask = coder->pos_mask; 321 322 // These variables are actually needed only if we last time ran 323 // out of input in the middle of the decoder loop. 324 probability *probs = coder->probs; 325 uint32_t symbol = coder->symbol; 326 uint32_t limit = coder->limit; 327 uint32_t offset = coder->offset; 328 uint32_t len = coder->len; 329 330 const uint32_t literal_pos_mask = coder->literal_pos_mask; 331 const uint32_t literal_context_bits = coder->literal_context_bits; 332 333 // Temporary variables 334 uint32_t pos_state = dict.pos & pos_mask; 335 336 lzma_ret ret = LZMA_OK; 337 338 // If uncompressed size is known, there must be no end of payload 339 // marker. 340 const bool no_eopm = coder->uncompressed_size 341 != LZMA_VLI_UNKNOWN; 342 if (no_eopm && coder->uncompressed_size < dict.limit - dict.pos) 343 dict.limit = dict.pos + (size_t)(coder->uncompressed_size); 344 345 // The main decoder loop. The "switch" is used to restart the decoder at 346 // correct location. Once restarted, the "switch" is no longer used. 347 switch (coder->sequence) 348 while (true) { 349 // Calculate new pos_state. This is skipped on the first loop 350 // since we already calculated it when setting up the local 351 // variables. 352 pos_state = dict.pos & pos_mask; 353 354 case SEQ_NORMALIZE: 355 case SEQ_IS_MATCH: 356 if (unlikely(no_eopm && dict.pos == dict.limit)) 357 break; 358 359 rc_if_0(coder->is_match[state][pos_state], SEQ_IS_MATCH) { 360 rc_update_0(coder->is_match[state][pos_state]); 361 362 // It's a literal i.e. a single 8-bit byte. 363 364 probs = literal_subcoder(coder->literal, 365 literal_context_bits, literal_pos_mask, 366 dict.pos, dict_get(&dict, 0)); 367 symbol = 1; 368 369 if (is_literal_state(state)) { 370 // Decode literal without match byte. 371#ifdef HAVE_SMALL 372 case SEQ_LITERAL: 373 do { 374 rc_bit(probs[symbol], , , SEQ_LITERAL); 375 } while (symbol < (1 << 8)); 376#else 377 rc_bit_case(probs[symbol], , , SEQ_LITERAL0); 378 rc_bit_case(probs[symbol], , , SEQ_LITERAL1); 379 rc_bit_case(probs[symbol], , , SEQ_LITERAL2); 380 rc_bit_case(probs[symbol], , , SEQ_LITERAL3); 381 rc_bit_case(probs[symbol], , , SEQ_LITERAL4); 382 rc_bit_case(probs[symbol], , , SEQ_LITERAL5); 383 rc_bit_case(probs[symbol], , , SEQ_LITERAL6); 384 rc_bit_case(probs[symbol], , , SEQ_LITERAL7); 385#endif 386 } else { 387 // Decode literal with match byte. 388 // 389 // We store the byte we compare against 390 // ("match byte") to "len" to minimize the 391 // number of variables we need to store 392 // between decoder calls. 393 len = dict_get(&dict, rep0) << 1; 394 395 // The usage of "offset" allows omitting some 396 // branches, which should give tiny speed 397 // improvement on some CPUs. "offset" gets 398 // set to zero if match_bit didn't match. 399 offset = 0x100; 400 401#ifdef HAVE_SMALL 402 case SEQ_LITERAL_MATCHED: 403 do { 404 const uint32_t match_bit 405 = len & offset; 406 const uint32_t subcoder_index 407 = offset + match_bit 408 + symbol; 409 410 rc_bit(probs[subcoder_index], 411 offset &= ~match_bit, 412 offset &= match_bit, 413 SEQ_LITERAL_MATCHED); 414 415 // It seems to be faster to do this 416 // here instead of putting it to the 417 // beginning of the loop and then 418 // putting the "case" in the middle 419 // of the loop. 420 len <<= 1; 421 422 } while (symbol < (1 << 8)); 423#else 424 // Unroll the loop. 425 uint32_t match_bit; 426 uint32_t subcoder_index; 427 428# define d(seq) \ 429 case seq: \ 430 match_bit = len & offset; \ 431 subcoder_index = offset + match_bit + symbol; \ 432 rc_bit(probs[subcoder_index], \ 433 offset &= ~match_bit, \ 434 offset &= match_bit, \ 435 seq) 436 437 d(SEQ_LITERAL_MATCHED0); 438 len <<= 1; 439 d(SEQ_LITERAL_MATCHED1); 440 len <<= 1; 441 d(SEQ_LITERAL_MATCHED2); 442 len <<= 1; 443 d(SEQ_LITERAL_MATCHED3); 444 len <<= 1; 445 d(SEQ_LITERAL_MATCHED4); 446 len <<= 1; 447 d(SEQ_LITERAL_MATCHED5); 448 len <<= 1; 449 d(SEQ_LITERAL_MATCHED6); 450 len <<= 1; 451 d(SEQ_LITERAL_MATCHED7); 452# undef d 453#endif 454 } 455 456 //update_literal(state); 457 // Use a lookup table to update to literal state, 458 // since compared to other state updates, this would 459 // need two branches. 460 static const lzma_lzma_state next_state[] = { 461 STATE_LIT_LIT, 462 STATE_LIT_LIT, 463 STATE_LIT_LIT, 464 STATE_LIT_LIT, 465 STATE_MATCH_LIT_LIT, 466 STATE_REP_LIT_LIT, 467 STATE_SHORTREP_LIT_LIT, 468 STATE_MATCH_LIT, 469 STATE_REP_LIT, 470 STATE_SHORTREP_LIT, 471 STATE_MATCH_LIT, 472 STATE_REP_LIT 473 }; 474 state = next_state[state]; 475 476 case SEQ_LITERAL_WRITE: 477 if (unlikely(dict_put(&dict, symbol))) { 478 coder->sequence = SEQ_LITERAL_WRITE; 479 goto out; 480 } 481 482 continue; 483 } 484 485 // Instead of a new byte we are going to get a byte range 486 // (distance and length) which will be repeated from our 487 // output history. 488 489 rc_update_1(coder->is_match[state][pos_state]); 490 491 case SEQ_IS_REP: 492 rc_if_0(coder->is_rep[state], SEQ_IS_REP) { 493 // Not a repeated match 494 rc_update_0(coder->is_rep[state]); 495 update_match(state); 496 497 // The latest three match distances are kept in 498 // memory in case there are repeated matches. 499 rep3 = rep2; 500 rep2 = rep1; 501 rep1 = rep0; 502 503 // Decode the length of the match. 504 len_decode(len, coder->match_len_decoder, 505 pos_state, SEQ_MATCH_LEN); 506 507 // Prepare to decode the highest two bits of the 508 // match distance. 509 probs = coder->dist_slot[get_dist_state(len)]; 510 symbol = 1; 511 512#ifdef HAVE_SMALL 513 case SEQ_DIST_SLOT: 514 do { 515 rc_bit(probs[symbol], , , SEQ_DIST_SLOT); 516 } while (symbol < DIST_SLOTS); 517#else 518 rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT0); 519 rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT1); 520 rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT2); 521 rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT3); 522 rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT4); 523 rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT5); 524#endif 525 // Get rid of the highest bit that was needed for 526 // indexing of the probability array. 527 symbol -= DIST_SLOTS; 528 assert(symbol <= 63); 529 530 if (symbol < DIST_MODEL_START) { 531 // Match distances [0, 3] have only two bits. 532 rep0 = symbol; 533 } else { 534 // Decode the lowest [1, 29] bits of 535 // the match distance. 536 limit = (symbol >> 1) - 1; 537 assert(limit >= 1 && limit <= 30); 538 rep0 = 2 + (symbol & 1); 539 540 if (symbol < DIST_MODEL_END) { 541 // Prepare to decode the low bits for 542 // a distance of [4, 127]. 543 assert(limit <= 5); 544 rep0 <<= limit; 545 assert(rep0 <= 96); 546 // -1 is fine, because we start 547 // decoding at probs[1], not probs[0]. 548 // NOTE: This violates the C standard, 549 // since we are doing pointer 550 // arithmetic past the beginning of 551 // the array. 552 assert((int32_t)(rep0 - symbol - 1) 553 >= -1); 554 assert((int32_t)(rep0 - symbol - 1) 555 <= 82); 556 probs = coder->pos_special + rep0 557 - symbol - 1; 558 symbol = 1; 559 offset = 0; 560 case SEQ_DIST_MODEL: 561#ifdef HAVE_SMALL 562 do { 563 rc_bit(probs[symbol], , 564 rep0 += 1 << offset, 565 SEQ_DIST_MODEL); 566 } while (++offset < limit); 567#else 568 switch (limit) { 569 case 5: 570 assert(offset == 0); 571 rc_bit(probs[symbol], , 572 rep0 += 1, 573 SEQ_DIST_MODEL); 574 ++offset; 575 --limit; 576 case 4: 577 rc_bit(probs[symbol], , 578 rep0 += 1 << offset, 579 SEQ_DIST_MODEL); 580 ++offset; 581 --limit; 582 case 3: 583 rc_bit(probs[symbol], , 584 rep0 += 1 << offset, 585 SEQ_DIST_MODEL); 586 ++offset; 587 --limit; 588 case 2: 589 rc_bit(probs[symbol], , 590 rep0 += 1 << offset, 591 SEQ_DIST_MODEL); 592 ++offset; 593 --limit; 594 case 1: 595 // We need "symbol" only for 596 // indexing the probability 597 // array, thus we can use 598 // rc_bit_last() here to omit 599 // the unneeded updating of 600 // "symbol". 601 rc_bit_last(probs[symbol], , 602 rep0 += 1 << offset, 603 SEQ_DIST_MODEL); 604 } 605#endif 606 } else { 607 // The distance is >= 128. Decode the 608 // lower bits without probabilities 609 // except the lowest four bits. 610 assert(symbol >= 14); 611 assert(limit >= 6); 612 limit -= ALIGN_BITS; 613 assert(limit >= 2); 614 case SEQ_DIRECT: 615 // Not worth manual unrolling 616 do { 617 rc_direct(rep0, SEQ_DIRECT); 618 } while (--limit > 0); 619 620 // Decode the lowest four bits using 621 // probabilities. 622 rep0 <<= ALIGN_BITS; 623 symbol = 1; 624#ifdef HAVE_SMALL 625 offset = 0; 626 case SEQ_ALIGN: 627 do { 628 rc_bit(coder->pos_align[ 629 symbol], , 630 rep0 += 1 << offset, 631 SEQ_ALIGN); 632 } while (++offset < ALIGN_BITS); 633#else 634 case SEQ_ALIGN0: 635 rc_bit(coder->pos_align[symbol], , 636 rep0 += 1, SEQ_ALIGN0); 637 case SEQ_ALIGN1: 638 rc_bit(coder->pos_align[symbol], , 639 rep0 += 2, SEQ_ALIGN1); 640 case SEQ_ALIGN2: 641 rc_bit(coder->pos_align[symbol], , 642 rep0 += 4, SEQ_ALIGN2); 643 case SEQ_ALIGN3: 644 // Like in SEQ_DIST_MODEL, we don't 645 // need "symbol" for anything else 646 // than indexing the probability array. 647 rc_bit_last(coder->pos_align[symbol], , 648 rep0 += 8, SEQ_ALIGN3); 649#endif 650 651 if (rep0 == UINT32_MAX) { 652 // End of payload marker was 653 // found. It must not be 654 // present if uncompressed 655 // size is known. 656 if (coder->uncompressed_size 657 != LZMA_VLI_UNKNOWN) { 658 ret = LZMA_DATA_ERROR; 659 goto out; 660 } 661 662 case SEQ_EOPM: 663 // LZMA1 stream with 664 // end-of-payload marker. 665 rc_normalize(SEQ_EOPM); 666 ret = LZMA_STREAM_END; 667 goto out; 668 } 669 } 670 } 671 672 // Validate the distance we just decoded. 673 if (unlikely(!dict_is_distance_valid(&dict, rep0))) { 674 ret = LZMA_DATA_ERROR; 675 goto out; 676 } 677 678 } else { 679 rc_update_1(coder->is_rep[state]); 680 681 // Repeated match 682 // 683 // The match distance is a value that we have had 684 // earlier. The latest four match distances are 685 // available as rep0, rep1, rep2 and rep3. We will 686 // now decode which of them is the new distance. 687 // 688 // There cannot be a match if we haven't produced 689 // any output, so check that first. 690 if (unlikely(!dict_is_distance_valid(&dict, 0))) { 691 ret = LZMA_DATA_ERROR; 692 goto out; 693 } 694 695 case SEQ_IS_REP0: 696 rc_if_0(coder->is_rep0[state], SEQ_IS_REP0) { 697 rc_update_0(coder->is_rep0[state]); 698 // The distance is rep0. 699 700 case SEQ_IS_REP0_LONG: 701 rc_if_0(coder->is_rep0_long[state][pos_state], 702 SEQ_IS_REP0_LONG) { 703 rc_update_0(coder->is_rep0_long[ 704 state][pos_state]); 705 706 update_short_rep(state); 707 708 case SEQ_SHORTREP: 709 if (unlikely(dict_put(&dict, dict_get( 710 &dict, rep0)))) { 711 coder->sequence = SEQ_SHORTREP; 712 goto out; 713 } 714 715 continue; 716 } 717 718 // Repeating more than one byte at 719 // distance of rep0. 720 rc_update_1(coder->is_rep0_long[ 721 state][pos_state]); 722 723 } else { 724 rc_update_1(coder->is_rep0[state]); 725 726 case SEQ_IS_REP1: 727 // The distance is rep1, rep2 or rep3. Once 728 // we find out which one of these three, it 729 // is stored to rep0 and rep1, rep2 and rep3 730 // are updated accordingly. 731 rc_if_0(coder->is_rep1[state], SEQ_IS_REP1) { 732 rc_update_0(coder->is_rep1[state]); 733 734 const uint32_t distance = rep1; 735 rep1 = rep0; 736 rep0 = distance; 737 738 } else { 739 rc_update_1(coder->is_rep1[state]); 740 case SEQ_IS_REP2: 741 rc_if_0(coder->is_rep2[state], 742 SEQ_IS_REP2) { 743 rc_update_0(coder->is_rep2[ 744 state]); 745 746 const uint32_t distance = rep2; 747 rep2 = rep1; 748 rep1 = rep0; 749 rep0 = distance; 750 751 } else { 752 rc_update_1(coder->is_rep2[ 753 state]); 754 755 const uint32_t distance = rep3; 756 rep3 = rep2; 757 rep2 = rep1; 758 rep1 = rep0; 759 rep0 = distance; 760 } 761 } 762 } 763 764 update_long_rep(state); 765 766 // Decode the length of the repeated match. 767 len_decode(len, coder->rep_len_decoder, 768 pos_state, SEQ_REP_LEN); 769 } 770 771 ///////////////////////////////// 772 // Repeat from history buffer. // 773 ///////////////////////////////// 774 775 // The length is always between these limits. There is no way 776 // to trigger the algorithm to set len outside this range. 777 assert(len >= MATCH_LEN_MIN); 778 assert(len <= MATCH_LEN_MAX); 779 780 case SEQ_COPY: 781 // Repeat len bytes from distance of rep0. 782 if (unlikely(dict_repeat(&dict, rep0, &len))) { 783 coder->sequence = SEQ_COPY; 784 goto out; 785 } 786 } 787 788 rc_normalize(SEQ_NORMALIZE); 789 coder->sequence = SEQ_IS_MATCH; 790 791out: 792 // Save state 793 794 // NOTE: Must not copy dict.limit. 795 dictptr->pos = dict.pos; 796 dictptr->full = dict.full; 797 798 rc_from_local(coder->rc, *in_pos); 799 800 coder->state = state; 801 coder->rep0 = rep0; 802 coder->rep1 = rep1; 803 coder->rep2 = rep2; 804 coder->rep3 = rep3; 805 806 coder->probs = probs; 807 coder->symbol = symbol; 808 coder->limit = limit; 809 coder->offset = offset; 810 coder->len = len; 811 812 // Update the remaining amount of uncompressed data if uncompressed 813 // size was known. 814 if (coder->uncompressed_size != LZMA_VLI_UNKNOWN) { 815 coder->uncompressed_size -= dict.pos - dict_start; 816 817 // Since there cannot be end of payload marker if the 818 // uncompressed size was known, we check here if we 819 // finished decoding. 820 if (coder->uncompressed_size == 0 && ret == LZMA_OK 821 && coder->sequence != SEQ_NORMALIZE) 822 ret = coder->sequence == SEQ_IS_MATCH 823 ? LZMA_STREAM_END : LZMA_DATA_ERROR; 824 } 825 826 // We can do an additional check in the range decoder to catch some 827 // corrupted files. 828 if (ret == LZMA_STREAM_END) { 829 if (!rc_is_finished(coder->rc)) 830 ret = LZMA_DATA_ERROR; 831 832 // Reset the range decoder so that it is ready to reinitialize 833 // for a new LZMA2 chunk. 834 rc_reset(coder->rc); 835 } 836 837 return ret; 838} 839 840 841 842static void 843lzma_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size) 844{ 845 coder->uncompressed_size = uncompressed_size; 846} 847 848/* 849extern void 850lzma_lzma_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size) 851{ 852 // This is hack. 853 (*(lzma_coder **)(coder))->uncompressed_size = uncompressed_size; 854} 855*/ 856 857static void 858lzma_decoder_reset(lzma_coder *coder, const void *opt) 859{ 860 const lzma_options_lzma *options = opt; 861 862 // NOTE: We assume that lc/lp/pb are valid since they were 863 // successfully decoded with lzma_lzma_decode_properties(). 864 865 // Calculate pos_mask. We don't need pos_bits as is for anything. 866 coder->pos_mask = (1U << options->pb) - 1; 867 868 // Initialize the literal decoder. 869 literal_init(coder->literal, options->lc, options->lp); 870 871 coder->literal_context_bits = options->lc; 872 coder->literal_pos_mask = (1U << options->lp) - 1; 873 874 // State 875 coder->state = STATE_LIT_LIT; 876 coder->rep0 = 0; 877 coder->rep1 = 0; 878 coder->rep2 = 0; 879 coder->rep3 = 0; 880 coder->pos_mask = (1U << options->pb) - 1; 881 882 // Range decoder 883 rc_reset(coder->rc); 884 885 // Bit and bittree decoders 886 for (uint32_t i = 0; i < STATES; ++i) { 887 for (uint32_t j = 0; j <= coder->pos_mask; ++j) { 888 bit_reset(coder->is_match[i][j]); 889 bit_reset(coder->is_rep0_long[i][j]); 890 } 891 892 bit_reset(coder->is_rep[i]); 893 bit_reset(coder->is_rep0[i]); 894 bit_reset(coder->is_rep1[i]); 895 bit_reset(coder->is_rep2[i]); 896 } 897 898 for (uint32_t i = 0; i < DIST_STATES; ++i) 899 bittree_reset(coder->dist_slot[i], DIST_SLOT_BITS); 900 901 for (uint32_t i = 0; i < FULL_DISTANCES - DIST_MODEL_END; ++i) 902 bit_reset(coder->pos_special[i]); 903 904 bittree_reset(coder->pos_align, ALIGN_BITS); 905 906 // Len decoders (also bit/bittree) 907 const uint32_t num_pos_states = 1U << options->pb; 908 bit_reset(coder->match_len_decoder.choice); 909 bit_reset(coder->match_len_decoder.choice2); 910 bit_reset(coder->rep_len_decoder.choice); 911 bit_reset(coder->rep_len_decoder.choice2); 912 913 for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) { 914 bittree_reset(coder->match_len_decoder.low[pos_state], 915 LEN_LOW_BITS); 916 bittree_reset(coder->match_len_decoder.mid[pos_state], 917 LEN_MID_BITS); 918 919 bittree_reset(coder->rep_len_decoder.low[pos_state], 920 LEN_LOW_BITS); 921 bittree_reset(coder->rep_len_decoder.mid[pos_state], 922 LEN_MID_BITS); 923 } 924 925 bittree_reset(coder->match_len_decoder.high, LEN_HIGH_BITS); 926 bittree_reset(coder->rep_len_decoder.high, LEN_HIGH_BITS); 927 928 coder->sequence = SEQ_IS_MATCH; 929 coder->probs = NULL; 930 coder->symbol = 0; 931 coder->limit = 0; 932 coder->offset = 0; 933 coder->len = 0; 934 935 return; 936} 937 938 939extern lzma_ret 940lzma_lzma_decoder_create(lzma_lz_decoder *lz, const lzma_allocator *allocator, 941 const void *opt, lzma_lz_options *lz_options) 942{ 943 if (lz->coder == NULL) { 944 lz->coder = lzma_alloc(sizeof(lzma_coder), allocator); 945 if (lz->coder == NULL) 946 return LZMA_MEM_ERROR; 947 948 lz->code = &lzma_decode; 949 lz->reset = &lzma_decoder_reset; 950 lz->set_uncompressed = &lzma_decoder_uncompressed; 951 } 952 953 // All dictionary sizes are OK here. LZ decoder will take care of 954 // the special cases. 955 const lzma_options_lzma *options = opt; 956 lz_options->dict_size = options->dict_size; 957 lz_options->preset_dict = options->preset_dict; 958 lz_options->preset_dict_size = options->preset_dict_size; 959 960 return LZMA_OK; 961} 962 963 964/// Allocate and initialize LZMA decoder. This is used only via LZ 965/// initialization (lzma_lzma_decoder_init() passes function pointer to 966/// the LZ initialization). 967static lzma_ret 968lzma_decoder_init(lzma_lz_decoder *lz, const lzma_allocator *allocator, 969 const void *options, lzma_lz_options *lz_options) 970{ 971 if (!is_lclppb_valid(options)) 972 return LZMA_PROG_ERROR; 973 974 return_if_error(lzma_lzma_decoder_create( 975 lz, allocator, options, lz_options)); 976 977 lzma_decoder_reset(lz->coder, options); 978 lzma_decoder_uncompressed(lz->coder, LZMA_VLI_UNKNOWN); 979 980 return LZMA_OK; 981} 982 983 984extern lzma_ret 985lzma_lzma_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator, 986 const lzma_filter_info *filters) 987{ 988 // LZMA can only be the last filter in the chain. This is enforced 989 // by the raw_decoder initialization. 990 assert(filters[1].init == NULL); 991 992 return lzma_lz_decoder_init(next, allocator, filters, 993 &lzma_decoder_init); 994} 995 996 997extern bool 998lzma_lzma_lclppb_decode(lzma_options_lzma *options, uint8_t byte) 999{ 1000 if (byte > (4 * 5 + 4) * 9 + 8) 1001 return true; 1002 1003 // See the file format specification to understand this. 1004 options->pb = byte / (9 * 5); 1005 byte -= options->pb * 9 * 5; 1006 options->lp = byte / 9; 1007 options->lc = byte - options->lp * 9; 1008 1009 return options->lc + options->lp > LZMA_LCLP_MAX; 1010} 1011 1012 1013extern uint64_t 1014lzma_lzma_decoder_memusage_nocheck(const void *options) 1015{ 1016 const lzma_options_lzma *const opt = options; 1017 return sizeof(lzma_coder) + lzma_lz_decoder_memusage(opt->dict_size); 1018} 1019 1020 1021extern uint64_t 1022lzma_lzma_decoder_memusage(const void *options) 1023{ 1024 if (!is_lclppb_valid(options)) 1025 return UINT64_MAX; 1026 1027 return lzma_lzma_decoder_memusage_nocheck(options); 1028} 1029 1030 1031extern lzma_ret 1032lzma_lzma_props_decode(void **options, const lzma_allocator *allocator, 1033 const uint8_t *props, size_t props_size) 1034{ 1035 if (props_size != 5) 1036 return LZMA_OPTIONS_ERROR; 1037 1038 lzma_options_lzma *opt 1039 = lzma_alloc(sizeof(lzma_options_lzma), allocator); 1040 if (opt == NULL) 1041 return LZMA_MEM_ERROR; 1042 1043 if (lzma_lzma_lclppb_decode(opt, props[0])) 1044 goto error; 1045 1046 // All dictionary sizes are accepted, including zero. LZ decoder 1047 // will automatically use a dictionary at least a few KiB even if 1048 // a smaller dictionary is requested. 1049 opt->dict_size = unaligned_read32le(props + 1); 1050 1051 opt->preset_dict = NULL; 1052 opt->preset_dict_size = 0; 1053 1054 *options = opt; 1055 1056 return LZMA_OK; 1057 1058error: 1059 lzma_free(opt, allocator); 1060 return LZMA_OPTIONS_ERROR; 1061} 1062