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 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 // NOTE: If you want to keep the line length in 80 characters, set
  22 //       tab width to 4 or less in your editor when editing this file.
  23
  24 #include "lzma_common.h"
  25 #include "lzma_decoder.h"
  26 #include "lz_decoder.h"
  27 #include "range_decoder.h"
  28
  29
  30 /// REQUIRED_IN_BUFFER_SIZE is the number of required input bytes
  31 /// for the worst case: longest match with longest distance.
  32 /// LZMA_IN_BUFFER_SIZE must be larger than REQUIRED_IN_BUFFER_SIZE.
  33 /// 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4 (align)
  34 ///         + 1 (rc_normalize)
  35 ///
  36 /// \todo       Is this correct for sure?
  37 ///
  38 #define REQUIRED_IN_BUFFER_SIZE \
  39         ((23 * (BIT_MODEL_TOTAL_BITS - MOVE_BITS + 1) + 26 + 9) / 8)
  40
  41
  42 // Length decoders are easiest to have as macros, because they use range
  43 // decoder macros, which use local variables rc_range and rc_code.
  44
  45 #define length_decode(target, len_decoder, pos_state) \
  46 do { \
  47         if_bit_0(len_decoder.choice) { \
  48                 update_bit_0(len_decoder.choice); \
  49                 target = MATCH_MIN_LEN; \
  50                 bittree_decode(target, len_decoder.low[pos_state], LEN_LOW_BITS); \
  51         } else { \
  52                 update_bit_1(len_decoder.choice); \
  53                 if_bit_0(len_decoder.choice2) { \
  54                         update_bit_0(len_decoder.choice2); \
  55                         target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
  56                         bittree_decode(target, len_decoder.mid[pos_state], LEN_MID_BITS); \
  57                 } else { \
  58                         update_bit_1(len_decoder.choice2); \
  59                         target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \
  60                         bittree_decode(target, len_decoder.high, LEN_HIGH_BITS); \
  61                 } \
  62         } \
  63 } while (0)
  64
  65
  66 #define length_decode_dummy(target, len_decoder, pos_state) \
  67 do { \
  68         if_bit_0(len_decoder.choice) { \
  69                 update_bit_0_dummy(); \
  70                 target = MATCH_MIN_LEN; \
  71                 bittree_decode_dummy(target, \
  72                                 len_decoder.low[pos_state], LEN_LOW_BITS); \
  73         } else { \
  74                 update_bit_1_dummy(); \
  75                 if_bit_0(len_decoder.choice2) { \
  76                         update_bit_0_dummy(); \
  77                         target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
  78                         bittree_decode_dummy(target, len_decoder.mid[pos_state], \
  79                                         LEN_MID_BITS); \
  80                 } else { \
  81                         update_bit_1_dummy(); \
  82                         target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \
  83                         bittree_decode_dummy(target, len_decoder.high, LEN_HIGH_BITS); \
  84                 } \
  85         } \
  86 } while (0)
  87
  88
  89 typedef struct {
  90         probability choice;
  91         probability choice2;
  92         probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
  93         probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
  94         probability high[LEN_HIGH_SYMBOLS];
  95 } lzma_length_decoder;
  96
  97
  98 struct lzma_coder_s {
  99         /// Data of the next coder, if any.
 100         lzma_next_coder next;
 101
 102         /// Sliding output window a.k.a. dictionary a.k.a. history buffer.
 103         lzma_lz_decoder lz;
 104
 105         // Range coder
 106         lzma_range_decoder rc;
 107
 108         // State
 109         lzma_lzma_state state;
 110         uint32_t rep0;      ///< Distance of the latest match
 111         uint32_t rep1;      ///< Distance of second latest match
 112         uint32_t rep2;      ///< Distance of third latest match
 113         uint32_t rep3;      ///< Distance of fourth latest match
 114         uint32_t pos_bits;
 115         uint32_t pos_mask;
 116         uint32_t now_pos; // Lowest 32-bits are enough here.
 117
 118         lzma_literal_coder *literal_coder;
 119
 120         /// If 1, it's a match. Otherwise it's a single 8-bit literal.
 121         probability is_match[STATES][POS_STATES_MAX];
 122
 123         /// If 1, it's a repeated match. The distance is one of rep0 .. rep3.
 124         probability is_rep[STATES];
 125
 126         /// If 0, distance of a repeated match is rep0.
 127         /// Otherwise check is_rep1.
 128         probability is_rep0[STATES];
 129
 130         /// If 0, distance of a repeated match is rep1.
 131         /// Otherwise check is_rep2.
 132         probability is_rep1[STATES];
 133
 134         /// If 0, distance of a repeated match is rep2. Otherwise it is rep3.
 135         probability is_rep2[STATES];
 136
 137         /// If 1, the repeated match has length of one byte. Otherwise
 138         /// the length is decoded from rep_len_decoder.
 139         probability is_rep0_long[STATES][POS_STATES_MAX];
 140
 141         probability pos_slot_decoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
 142         probability pos_decoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
 143         probability pos_align_decoder[1 << ALIGN_BITS];
 144
 145         /// Length of a match
 146         lzma_length_decoder match_len_decoder;
 147
 148         /// Length of a repeated match.
 149         lzma_length_decoder rep_len_decoder;
 150
 151         /// True when we have produced at least one byte of output since the
 152         /// beginning of the stream or the latest flush marker.
 153         bool has_produced_output;
 154 };
 155
 156
 157 /// \brief      Check if the next iteration of the decoder loop can be run.
 158 ///
 159 /// \note       There must always be REQUIRED_IN_BUFFER_SIZE bytes
 160 ///             readable space!
 161 ///
 162 static bool lzma_attribute((pure))
 163 decode_dummy(const lzma_coder *restrict coder,
 164                 const uint8_t *restrict in, size_t in_pos_local,
 165                 const size_t in_size, lzma_range_decoder rc,
 166                 uint32_t state, uint32_t rep0, const uint32_t now_pos)
 167 {
 168         uint32_t rc_bound;
 169
 170         do {
 171                 const uint32_t pos_state = now_pos & coder->pos_mask;
 172
 173                 if_bit_0(coder->is_match[state][pos_state]) {
 174                         // It's a literal i.e. a single 8-bit byte.
 175
 176                         update_bit_0_dummy();
 177
 178                         const probability *subcoder = literal_get_subcoder(
 179                                         coder->literal_coder, now_pos, lz_get_byte(coder->lz, 0));
 180                         uint32_t symbol = 1;
 181
 182                         if (is_literal_state(state)) {
 183                                 // Decode literal without match byte.
 184                                 do {
 185                                         if_bit_0(subcoder[symbol]) {
 186                                                 update_bit_0_dummy();
 187                                                 symbol <<= 1;
 188                                         } else {
 189                                                 update_bit_1_dummy();
 190                                                 symbol = (symbol << 1) | 1;
 191                                         }
 192                                 } while (symbol < 0x100);
 193
 194                         } else {
 195                                 // Decode literal with match byte.
 196                                 uint32_t match_byte = lz_get_byte(coder->lz, rep0);
 197                                 uint32_t subcoder_offset = 0x100;
 198
 199                                 do {
 200                                         match_byte <<= 1;
 201                                         const uint32_t match_bit = match_byte & subcoder_offset;
 202                                         const uint32_t subcoder_index
 203                                                         = subcoder_offset + match_bit + symbol;
 204
 205                                         if_bit_0(subcoder[subcoder_index]) {
 206                                                 update_bit_0_dummy();
 207                                                 symbol <<= 1;
 208                                                 subcoder_offset &= ~match_bit;
 209                                         } else {
 210                                                 update_bit_1_dummy();
 211                                                 symbol = (symbol << 1) | 1;
 212                                                 subcoder_offset &= match_bit;
 213                                         }
 214                                 } while (symbol < 0x100);
 215                         }
 216
 217                         break;
 218                 }
 219
 220                 update_bit_1_dummy();
 221                 uint32_t len;
 222
 223                 if_bit_0(coder->is_rep[state]) {
 224                         update_bit_0_dummy();
 225                         length_decode_dummy(len, coder->match_len_decoder, pos_state);
 226
 227                         const uint32_t len_to_pos_state = get_len_to_pos_state(len);
 228                         uint32_t pos_slot = 0;
 229                         bittree_decode_dummy(pos_slot,
 230                                         coder->pos_slot_decoder[len_to_pos_state], POS_SLOT_BITS);
 231                         assert(pos_slot <= 63);
 232
 233                         if (pos_slot >= START_POS_MODEL_INDEX) {
 234                                 uint32_t direct_bits = (pos_slot >> 1) - 1;
 235                                 assert(direct_bits >= 1 && direct_bits <= 31);
 236                                 rep0 = 2 | (pos_slot & 1);
 237
 238                                 if (pos_slot < END_POS_MODEL_INDEX) {
 239                                         assert(direct_bits <= 5);
 240                                         rep0 <<= direct_bits;
 241                                         assert(rep0 <= 96);
 242                                         // -1 is fine, because bittree_reverse_decode()
 243                                         // starts from table index [1] (not [0]).
 244                                         assert((int32_t)(rep0 - pos_slot - 1) >= -1);
 245                                         assert((int32_t)(rep0 - pos_slot - 1) <= 82);
 246                                         // We add the result to rep0, so rep0
 247                                         // must not be part of second argument
 248                                         // of the macro.
 249                                         const int32_t offset = rep0 - pos_slot - 1;
 250                                         bittree_reverse_decode_dummy(coder->pos_decoders + offset,
 251                                                         direct_bits);
 252                                 } else {
 253                                         assert(pos_slot >= 14);
 254                                         assert(direct_bits >= 6);
 255                                         direct_bits -= ALIGN_BITS;
 256                                         assert(direct_bits >= 2);
 257                                         rc_decode_direct_dummy(direct_bits);
 258
 259                                         bittree_reverse_decode_dummy(coder->pos_align_decoder,
 260                                                         ALIGN_BITS);
 261                                 }
 262                         }
 263
 264                 } else {
 265                         update_bit_1_dummy();
 266
 267                         if_bit_0(coder->is_rep0[state]) {
 268                                 update_bit_0_dummy();
 269
 270                                 if_bit_0(coder->is_rep0_long[state][pos_state]) {
 271                                         update_bit_0_dummy();
 272                                         break;
 273                                 } else {
 274                                         update_bit_1_dummy();
 275                                 }
 276
 277                         } else {
 278                                 update_bit_1_dummy();
 279
 280                                 if_bit_0(coder->is_rep1[state]) {
 281                                         update_bit_0_dummy();
 282                                 } else {
 283                                         update_bit_1_dummy();
 284
 285                                         if_bit_0(coder->is_rep2[state]) {
 286                                                 update_bit_0_dummy();
 287                                         } else {
 288                                                 update_bit_1_dummy();
 289                                         }
 290                                 }
 291                         }
 292
 293                         length_decode_dummy(len, coder->rep_len_decoder, pos_state);
 294                 }
 295         } while (0);
 296
 297         rc_normalize();
 298
 299         return in_pos_local <= in_size;
 300 }
 301
 302
 303 static bool
 304 decode_real(lzma_coder *restrict coder, const uint8_t *restrict in,
 305                 size_t *restrict in_pos, size_t in_size, bool has_safe_buffer)
 306 {
 307         ////////////////////
 308         // Initialization //
 309         ////////////////////
 310
 311         if (!rc_read_init(&coder->rc, in, in_pos, in_size))
 312                 return false;
 313
 314         ///////////////
 315         // Variables //
 316         ///////////////
 317
 318         // Making local copies of often-used variables improves both
 319         // speed and readability.
 320
 321         // Range decoder
 322         rc_to_local(coder->rc);
 323
 324         // State
 325         uint32_t state = coder->state;
 326         uint32_t rep0 = coder->rep0;
 327         uint32_t rep1 = coder->rep1;
 328         uint32_t rep2 = coder->rep2;
 329         uint32_t rep3 = coder->rep3;
 330
 331         // Misc
 332         uint32_t now_pos = coder->now_pos;
 333         bool has_produced_output = coder->has_produced_output;
 334
 335         // Variables derived from decoder settings
 336         const uint32_t pos_mask = coder->pos_mask;
 337
 338         size_t in_pos_local = *in_pos; // Local copy
 339         size_t in_limit;
 340         if (in_size <= REQUIRED_IN_BUFFER_SIZE)
 341                 in_limit = 0;
 342         else
 343                 in_limit = in_size - REQUIRED_IN_BUFFER_SIZE;
 344
 345
 346         while (coder->lz.pos < coder->lz.limit
 347                         && (in_pos_local < in_limit || (has_safe_buffer
 348                                 && decode_dummy(coder, in, in_pos_local, in_size,
 349                                         rc, state, rep0, now_pos)))) {
 350
 351                 /////////////////////
 352                 // Actual decoding //
 353                 /////////////////////
 354
 355                 const uint32_t pos_state = now_pos & pos_mask;
 356
 357                 if_bit_0(coder->is_match[state][pos_state]) {
 358                         update_bit_0(coder->is_match[state][pos_state]);
 359
 360                         // It's a literal i.e. a single 8-bit byte.
 361
 362                         probability *subcoder = literal_get_subcoder(coder->literal_coder,
 363                                         now_pos, lz_get_byte(coder->lz, 0));
 364                         uint32_t symbol = 1;
 365
 366                         if (is_literal_state(state)) {
 367                                 // Decode literal without match byte.
 368                                 do {
 369                                         if_bit_0(subcoder[symbol]) {
 370                                                 update_bit_0(subcoder[symbol]);
 371                                                 symbol <<= 1;
 372                                         } else {
 373                                                 update_bit_1(subcoder[symbol]);
 374                                                 symbol = (symbol << 1) | 1;
 375                                         }
 376                                 } while (symbol < 0x100);
 377
 378                         } else {
 379                                 // Decode literal with match byte.
 380                                 //
 381                                 // The usage of subcoder_offset allows omitting some
 382                                 // branches, which should give tiny speed improvement on
 383                                 // some CPUs. subcoder_offset gets set to zero if match_bit
 384                                 // didn't match.
 385                                 uint32_t match_byte = lz_get_byte(coder->lz, rep0);
 386                                 uint32_t subcoder_offset = 0x100;
 387
 388                                 do {
 389                                         match_byte <<= 1;
 390                                         const uint32_t match_bit = match_byte & subcoder_offset;
 391                                         const uint32_t subcoder_index
 392                                                         = subcoder_offset + match_bit + symbol;
 393
 394                                         if_bit_0(subcoder[subcoder_index]) {
 395                                                 update_bit_0(subcoder[subcoder_index]);
 396                                                 symbol <<= 1;
 397                                                 subcoder_offset &= ~match_bit;
 398                                         } else {
 399                                                 update_bit_1(subcoder[subcoder_index]);
 400                                                 symbol = (symbol << 1) | 1;
 401                                                 subcoder_offset &= match_bit;
 402                                         }
 403                                 } while (symbol < 0x100);
 404                         }
 405
 406                         // Put the decoded byte to the dictionary, update the
 407                         // decoder state, and start a new decoding loop.
 408                         coder->lz.dict[coder->lz.pos++] = (uint8_t)(symbol);
 409                         ++now_pos;
 410                         update_literal(state);
 411                         has_produced_output = true;
 412                         continue;
 413                 }
 414
 415                 // Instead of a new byte we are going to get a byte range
 416                 // (distance and length) which will be repeated from our
 417                 // output history.
 418
 419                 update_bit_1(coder->is_match[state][pos_state]);
 420                 uint32_t len;
 421
 422                 if_bit_0(coder->is_rep[state]) {
 423                         update_bit_0(coder->is_rep[state]);
 424
 425                         // Not a repeated match
 426                         //
 427                         // We will decode a new distance and store
 428                         // the value to distance.
 429
 430                         // Decode the length of the match.
 431                         length_decode(len, coder->match_len_decoder, pos_state);
 432
 433                         update_match(state);
 434
 435                         const uint32_t len_to_pos_state = get_len_to_pos_state(len);
 436                         uint32_t pos_slot = 0;
 437                         bittree_decode(pos_slot,
 438                                         coder->pos_slot_decoder[len_to_pos_state], POS_SLOT_BITS);
 439                         assert(pos_slot <= 63);
 440
 441                         if (pos_slot >= START_POS_MODEL_INDEX) {
 442                                 uint32_t direct_bits = (pos_slot >> 1) - 1;
 443                                 assert(direct_bits >= 1 && direct_bits <= 30);
 444                                 uint32_t distance = 2 | (pos_slot & 1);
 445
 446                                 if (pos_slot < END_POS_MODEL_INDEX) {
 447                                         assert(direct_bits <= 5);
 448                                         distance <<= direct_bits;
 449                                         assert(distance <= 96);
 450                                         // -1 is fine, because
 451                                         // bittree_reverse_decode()
 452                                         // starts from table index [1]
 453                                         // (not [0]).
 454                                         assert((int32_t)(distance - pos_slot - 1) >= -1);
 455                                         assert((int32_t)(distance - pos_slot - 1) <= 82);
 456                                         // We add the result to distance, so distance
 457                                         // must not be part of second argument
 458                                         // of the macro.
 459                                         const int32_t offset = distance - pos_slot - 1;
 460                                         bittree_reverse_decode(distance, coder->pos_decoders + offset,
 461                                                         direct_bits);
 462                                 } else {
 463                                         assert(pos_slot >= 14);
 464                                         assert(direct_bits >= 6);
 465                                         direct_bits -= ALIGN_BITS;
 466                                         assert(direct_bits >= 2);
 467                                         rc_decode_direct(distance, direct_bits);
 468                                         distance <<= ALIGN_BITS;
 469
 470                                         bittree_reverse_decode(distance, coder->pos_align_decoder,
 471                                                         ALIGN_BITS);
 472
 473                                         if (distance == UINT32_MAX) {
 474                                                 if (len == LEN_SPECIAL_EOPM) {
 475                                                         // End of Payload Marker found.
 476                                                         coder->lz.eopm_detected = true;
 477                                                         break;
 478
 479                                                 } else if (len == LEN_SPECIAL_FLUSH) {
 480                                                         // Flush marker detected. We must have produced
 481                                                         // at least one byte of output since the previous
 482                                                         // flush marker or the beginning of the stream.
 483                                                         // This is to prevent hanging the decoder with
 484                                                         // malicious input files.
 485                                                         if (!has_produced_output)
 486                                                                 return true;
 487
 488                                                         has_produced_output = false;
 489
 490                                                         // We know that we have enough input to call
 491                                                         // this macro, because it is tested at the
 492                                                         // end of decode_dummy().
 493                                                         rc_normalize();
 494
 495                                                         rc_reset(rc);
 496
 497                                                         // If we don't have enough input here, we jump
 498                                                         // out of the loop. Note that while there is a
 499                                                         // useless call to rc_normalize(), it does nothing
 500                                                         // since we have just reset the range decoder.
 501                                                         if (!rc_read_init(&rc, in, &in_pos_local, in_size))
 502                                                                 break;
 503
 504                                                         continue;
 505
 506                                                 } else {
 507                                                         return true;
 508                                                 }
 509                                         }
 510                                 }
 511
 512                                 // The latest three match distances are kept in
 513                                 // memory in case there are repeated matches.
 514                                 rep3 = rep2;
 515                                 rep2 = rep1;
 516                                 rep1 = rep0;
 517                                 rep0 = distance;
 518
 519                         } else {
 520                                 rep3 = rep2;
 521                                 rep2 = rep1;
 522                                 rep1 = rep0;
 523                                 rep0 = pos_slot;
 524                         }
 525
 526                 } else {
 527                         update_bit_1(coder->is_rep[state]);
 528
 529                         // Repeated match
 530                         //
 531                         // The match distance is a value that we have had
 532                         // earlier. The latest four match distances are
 533                         // available as rep0, rep1, rep2 and rep3. We will
 534                         // now decode which of them is the new distance.
 535
 536                         if_bit_0(coder->is_rep0[state]) {
 537                                 update_bit_0(coder->is_rep0[state]);
 538
 539                                 // The distance is rep0.
 540
 541                                 if_bit_0(coder->is_rep0_long[state][pos_state]) {
 542                                         update_bit_0(coder->is_rep0_long[state][pos_state]);
 543
 544                                         update_short_rep(state);
 545
 546                                         // Repeat exactly one byte and start a new decoding loop.
 547                                         // Note that rep0 is known to have a safe value, thus we
 548                                         // don't need to check if we are wrapping the dictionary
 549                                         // when it isn't full yet.
 550                                         if (unlikely(lz_is_empty(coder->lz)))
 551                                                 return true;
 552
 553                                         coder->lz.dict[coder->lz.pos]
 554                                                         = lz_get_byte(coder->lz, rep0);
 555                                         ++coder->lz.pos;
 556                                         ++now_pos;
 557                                         has_produced_output = true;
 558                                         continue;
 559
 560                                 } else {
 561                                         update_bit_1(coder->is_rep0_long[state][pos_state]);
 562
 563                                         // Repeating more than one byte at
 564                                         // distance of rep0.
 565                                 }
 566
 567                         } else {
 568                                 update_bit_1(coder->is_rep0[state]);
 569
 570                                 // The distance is rep1, rep2 or rep3. Once
 571                                 // we find out which one of these three, it
 572                                 // is stored to rep0 and rep1, rep2 and rep3
 573                                 // are updated accordingly.
 574
 575                                 uint32_t distance;
 576
 577                                 if_bit_0(coder->is_rep1[state]) {
 578                                         update_bit_0(coder->is_rep1[state]);
 579                                         distance = rep1;
 580                                 } else {
 581                                         update_bit_1(coder->is_rep1[state]);
 582
 583                                         if_bit_0(coder->is_rep2[state]) {
 584                                                 update_bit_0(coder->is_rep2[state]);
 585                                                 distance = rep2;
 586                                         } else {
 587                                                 update_bit_1(coder->is_rep2[state]);
 588                                                 distance = rep3;
 589                                                 rep3 = rep2;
 590                                         }
 591
 592                                         rep2 = rep1;
 593                                 }
 594
 595                                 rep1 = rep0;
 596                                 rep0 = distance;
 597                         }
 598
 599                         update_long_rep(state);
 600
 601                         // Decode the length of the repeated match.
 602                         length_decode(len, coder->rep_len_decoder, pos_state);
 603                 }
 604
 605
 606                 /////////////////////////////////
 607                 // Repeat from history buffer. //
 608                 /////////////////////////////////
 609
 610                 // The length is always between these limits. There is no way
 611                 // to trigger the algorithm to set len outside this range.
 612                 assert(len >= MATCH_MIN_LEN);
 613                 assert(len <= MATCH_MAX_LEN);
 614
 615                 now_pos += len;
 616                 has_produced_output = true;
 617
 618                 // Repeat len bytes from distance of rep0.
 619                 if (!lzma_lz_out_repeat(&coder->lz, rep0, len))
 620                         return true;
 621         }
 622
 623         rc_normalize();
 624
 625
 626         /////////////////////////////////
 627         // Update the *data structure. //
 628         /////////////////////////////////
 629
 630         // Range decoder
 631         rc_from_local(coder->rc);
 632
 633         // State
 634         coder->state = state;
 635         coder->rep0 = rep0;
 636         coder->rep1 = rep1;
 637         coder->rep2 = rep2;
 638         coder->rep3 = rep3;
 639
 640         // Misc
 641         coder->now_pos = now_pos;
 642         coder->has_produced_output = has_produced_output;
 643         *in_pos = in_pos_local;
 644
 645         return false;
 646 }
 647
 648
 649 static void
 650 lzma_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
 651 {
 652         lzma_next_coder_end(&coder->next, allocator);
 653         lzma_lz_decoder_end(&coder->lz, allocator);
 654         lzma_literal_end(&coder->literal_coder, allocator);
 655         lzma_free(coder, allocator);
 656         return;
 657 }
 658
 659
 660 extern lzma_ret
 661 lzma_lzma_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 662                 const lzma_filter_info *filters)
 663 {
 664         // Validate pos_bits. Other options are validated by the
 665         // respective initialization functions.
 666         const lzma_options_lzma *options = filters[0].options;
 667         if (options->pos_bits > LZMA_POS_BITS_MAX)
 668                 return LZMA_HEADER_ERROR;
 669
 670         // Allocate memory for the decoder if needed.
 671         if (next->coder == NULL) {
 672                 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 673                 if (next->coder == NULL)
 674                         return LZMA_MEM_ERROR;
 675
 676                 // Initialize variables so that we know later that we don't
 677                 // have an existing decoder initialized.
 678                 next->coder->next = LZMA_NEXT_CODER_INIT;
 679                 next->coder->lz = LZMA_LZ_DECODER_INIT;
 680                 next->coder->literal_coder = NULL;
 681         }
 682
 683         // Store the pos_bits and calculate pos_mask.
 684         next->coder->pos_bits = options->pos_bits;
 685         next->coder->pos_mask = (1U << next->coder->pos_bits) - 1;
 686
 687         // Allocate (if needed) and initialize the literal decoder.
 688         {
 689                 const lzma_ret ret = lzma_literal_init(
 690                                 &next->coder->literal_coder, allocator,
 691                                 options->literal_context_bits,
 692                                 options->literal_pos_bits);
 693                 if (ret != LZMA_OK) {
 694                         lzma_free(next->coder, allocator);
 695                         next->coder = NULL;
 696                         return ret;
 697                 }
 698         }
 699
 700         // Allocate and initialize the LZ decoder.
 701         {
 702                 const lzma_ret ret = lzma_lz_decoder_reset(
 703                                 &next->coder->lz, allocator, &decode_real,
 704                                 options->dictionary_size, MATCH_MAX_LEN);
 705                 if (ret != LZMA_OK) {
 706                         lzma_literal_end(&next->coder->literal_coder,
 707                                         allocator);
 708                         lzma_free(next->coder, allocator);
 709                         next->coder = NULL;
 710                         return ret;
 711                 }
 712         }
 713
 714         // State
 715         next->coder->state = 0;
 716         next->coder->rep0 = 0;
 717         next->coder->rep1 = 0;
 718         next->coder->rep2 = 0;
 719         next->coder->rep3 = 0;
 720         next->coder->pos_bits = options->pos_bits;
 721         next->coder->pos_mask = (1 << next->coder->pos_bits) - 1;
 722         next->coder->now_pos = 0;
 723
 724         // Range decoder
 725         rc_reset(next->coder->rc);
 726
 727         // Bit and bittree decoders
 728         for (uint32_t i = 0; i < STATES; ++i) {
 729                 for (uint32_t j = 0; j <= next->coder->pos_mask; ++j) {
 730                         bit_reset(next->coder->is_match[i][j]);
 731                         bit_reset(next->coder->is_rep0_long[i][j]);
 732                 }
 733
 734                 bit_reset(next->coder->is_rep[i]);
 735                 bit_reset(next->coder->is_rep0[i]);
 736                 bit_reset(next->coder->is_rep1[i]);
 737                 bit_reset(next->coder->is_rep2[i]);
 738         }
 739
 740         for (uint32_t i = 0; i < LEN_TO_POS_STATES; ++i)
 741                 bittree_reset(next->coder->pos_slot_decoder[i], POS_SLOT_BITS);
 742
 743         for (uint32_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
 744                 bit_reset(next->coder->pos_decoders[i]);
 745
 746         bittree_reset(next->coder->pos_align_decoder, ALIGN_BITS);
 747
 748         // Len decoders (also bit/bittree)
 749         const uint32_t num_pos_states = 1 << next->coder->pos_bits;
 750         bit_reset(next->coder->match_len_decoder.choice);
 751         bit_reset(next->coder->match_len_decoder.choice2);
 752         bit_reset(next->coder->rep_len_decoder.choice);
 753         bit_reset(next->coder->rep_len_decoder.choice2);
 754
 755         for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
 756                 bittree_reset(next->coder->match_len_decoder.low[pos_state],
 757                                 LEN_LOW_BITS);
 758                 bittree_reset(next->coder->match_len_decoder.mid[pos_state],
 759                                 LEN_MID_BITS);
 760
 761                 bittree_reset(next->coder->rep_len_decoder.low[pos_state],
 762                                 LEN_LOW_BITS);
 763                 bittree_reset(next->coder->rep_len_decoder.mid[pos_state],
 764                                 LEN_MID_BITS);
 765         }
 766
 767         bittree_reset(next->coder->match_len_decoder.high, LEN_HIGH_BITS);
 768         bittree_reset(next->coder->rep_len_decoder.high, LEN_HIGH_BITS);
 769
 770         next->coder->has_produced_output = false;
 771
 772         // Initialize the next decoder in the chain, if any.
 773         {
 774                 const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
 775                                 allocator, filters + 1);
 776                 if (ret != LZMA_OK) {
 777                         lzma_decoder_end(next->coder, allocator);
 778                         return ret;
 779                 }
 780         }
 781
 782         // Initialization successful. Set the function pointers.
 783         next->code = &lzma_lz_decode;
 784         next->end = &lzma_decoder_end;
 785
 786         return LZMA_OK;
 787 }
 788
 789
 790 extern void
 791 lzma_lzma_decoder_uncompressed_size(
 792                 lzma_next_coder *next, lzma_vli uncompressed_size)
 793 {
 794         next->coder->lz.uncompressed_size = uncompressed_size;
 795         return;
 796 }
 797
 798
 799 extern bool
 800 lzma_lzma_decode_properties(lzma_options_lzma *options, uint8_t byte)
 801 {
 802         if (byte > (4 * 5 + 4) * 9 + 8)
 803                 return true;
 804
 805         // See the file format specification to understand this.
 806         options->pos_bits = byte / (9 * 5);
 807         byte -= options->pos_bits * 9 * 5;
 808         options->literal_pos_bits = byte / 9;
 809         options->literal_context_bits = byte - options->literal_pos_bits * 9;
 810
 811         return false;
 812 }