src/liblzma/lzma/lzma_decoder.c

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