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         uint32_t 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_match_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 len_decoder;
 147
 148         /// Length of a repeated match.
 149         lzma_length_decoder rep_match_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_char_state(state)) {
 183                                 // Decode literal with match byte.
 184
 185                                 assert(rep0 != UINT32_MAX);
 186                                 uint32_t match_byte = lz_get_byte(coder->lz, rep0);
 187
 188                                 do {
 189                                         match_byte <<= 1;
 190                                         const uint32_t match_bit = match_byte & 0x100;
 191                                         const uint32_t subcoder_index = 0x100 + match_bit + symbol;
 192
 193                                         if_bit_0(subcoder[subcoder_index]) {
 194                                                 update_bit_0_dummy();
 195                                                 symbol <<= 1;
 196                                                 if (match_bit != 0)
 197                                                         break;
 198                                         } else {
 199                                                 update_bit_1_dummy();
 200                                                 symbol = (symbol << 1) | 1;
 201                                                 if (match_bit == 0)
 202                                                         break;
 203                                         }
 204                                 } while (symbol < 0x100);
 205                         }
 206
 207                         // Decode literal without match byte. This is also
 208                         // the tail of the with-match-byte function.
 209                         while (symbol < 0x100) {
 210                                 if_bit_0(subcoder[symbol]) {
 211                                         update_bit_0_dummy();
 212                                         symbol <<= 1;
 213                                 } else {
 214                                         update_bit_1_dummy();
 215                                         symbol = (symbol << 1) | 1;
 216                                 }
 217                         }
 218
 219                         break;
 220                 }
 221
 222                 update_bit_1_dummy();
 223                 uint32_t len;
 224
 225                 if_bit_0(coder->is_rep[state]) {
 226                         update_bit_0_dummy();
 227                         length_decode_dummy(len, coder->len_decoder, pos_state);
 228                         update_match(state);
 229
 230                         const uint32_t len_to_pos_state = get_len_to_pos_state(len);
 231                         uint32_t pos_slot = 0;
 232                         bittree_decode_dummy(pos_slot,
 233                                         coder->pos_slot_decoder[len_to_pos_state], POS_SLOT_BITS);
 234                         assert(pos_slot <= 63);
 235
 236                         if (pos_slot >= START_POS_MODEL_INDEX) {
 237                                 uint32_t direct_bits = (pos_slot >> 1) - 1;
 238                                 assert(direct_bits >= 1 && direct_bits <= 31);
 239                                 rep0 = 2 | (pos_slot & 1);
 240
 241                                 if (pos_slot < END_POS_MODEL_INDEX) {
 242                                         assert(direct_bits <= 5);
 243                                         rep0 <<= direct_bits;
 244                                         assert(rep0 <= 96);
 245                                         // -1 is fine, because bittree_reverse_decode()
 246                                         // starts from table index [1] (not [0]).
 247                                         assert((int32_t)(rep0 - pos_slot - 1) >= -1);
 248                                         assert((int32_t)(rep0 - pos_slot - 1) <= 82);
 249                                         // We add the result to rep0, so rep0
 250                                         // must not be part of second argument
 251                                         // of the macro.
 252                                         const int32_t offset = rep0 - pos_slot - 1;
 253                                         bittree_reverse_decode_dummy(coder->pos_decoders + offset,
 254                                                         direct_bits);
 255                                 } else {
 256                                         assert(pos_slot >= 14);
 257                                         assert(direct_bits >= 6);
 258                                         direct_bits -= ALIGN_BITS;
 259                                         assert(direct_bits >= 2);
 260                                         rc_decode_direct_dummy(direct_bits);
 261
 262                                         bittree_reverse_decode_dummy(coder->pos_align_decoder,
 263                                                         ALIGN_BITS);
 264                                 }
 265                         }
 266
 267                 } else {
 268                         update_bit_1_dummy();
 269
 270                         if_bit_0(coder->is_rep0[state]) {
 271                                 update_bit_0_dummy();
 272
 273                                 if_bit_0(coder->is_rep0_long[state][pos_state]) {
 274                                         update_bit_0_dummy();
 275                                         break;
 276                                 } else {
 277                                         update_bit_1_dummy();
 278                                 }
 279
 280                         } else {
 281                                 update_bit_1_dummy();
 282
 283                                 if_bit_0(coder->is_rep1[state]) {
 284                                         update_bit_0_dummy();
 285                                 } else {
 286                                         update_bit_1_dummy();
 287
 288                                         if_bit_0(coder->is_rep2[state]) {
 289                                                 update_bit_0_dummy();
 290                                         } else {
 291                                                 update_bit_1_dummy();
 292                                         }
 293                                 }
 294                         }
 295
 296                         length_decode_dummy(len, coder->rep_match_len_decoder, pos_state);
 297                 }
 298         } while (0);
 299
 300         rc_normalize();
 301
 302         return in_pos_local <= in_size;
 303 }
 304
 305
 306 static bool
 307 decode_real(lzma_coder *restrict coder, const uint8_t *restrict in,
 308                 size_t *restrict in_pos, size_t in_size, bool has_safe_buffer)
 309 {
 310         ////////////////////
 311         // Initialization //
 312         ////////////////////
 313
 314         if (!rc_read_init(&coder->rc, in, in_pos, in_size))
 315                 return false;
 316
 317         ///////////////
 318         // Variables //
 319         ///////////////
 320
 321         // Making local copies of often-used variables improves both
 322         // speed and readability.
 323
 324         // Range decoder
 325         rc_to_local(coder->rc);
 326
 327         // State
 328         uint32_t state = coder->state;
 329         uint32_t rep0 = coder->rep0;
 330         uint32_t rep1 = coder->rep1;
 331         uint32_t rep2 = coder->rep2;
 332         uint32_t rep3 = coder->rep3;
 333
 334         // Misc
 335         uint32_t now_pos = coder->now_pos;
 336         bool has_produced_output = coder->has_produced_output;
 337
 338         // Variables derived from decoder settings
 339         const uint32_t pos_mask = coder->pos_mask;
 340
 341         size_t in_pos_local = *in_pos; // Local copy
 342         size_t in_limit;
 343         if (in_size <= REQUIRED_IN_BUFFER_SIZE)
 344                 in_limit = 0;
 345         else
 346                 in_limit = in_size - REQUIRED_IN_BUFFER_SIZE;
 347
 348
 349         while (coder->lz.pos < coder->lz.limit
 350                         && (in_pos_local < in_limit || (has_safe_buffer
 351                                 && decode_dummy(coder, in, in_pos_local, in_size,
 352                                         rc, state, rep0, now_pos)))) {
 353
 354                 /////////////////////
 355                 // Actual decoding //
 356                 /////////////////////
 357
 358                 const uint32_t pos_state = now_pos & pos_mask;
 359
 360                 if_bit_0(coder->is_match[state][pos_state]) {
 361                         update_bit_0(coder->is_match[state][pos_state]);
 362
 363                         // It's a literal i.e. a single 8-bit byte.
 364
 365                         probability *subcoder = literal_get_subcoder(coder->literal_coder,
 366                                         now_pos, lz_get_byte(coder->lz, 0));
 367                         uint32_t symbol = 1;
 368
 369                         if (!is_char_state(state)) {
 370                                 // Decode literal with match byte.
 371
 372                                 assert(rep0 != UINT32_MAX);
 373                                 uint32_t match_byte = lz_get_byte(coder->lz, rep0);
 374
 375                                 do {
 376                                         match_byte <<= 1;
 377                                         const uint32_t match_bit = match_byte & 0x100;
 378                                         const uint32_t subcoder_index = 0x100 + match_bit + symbol;
 379
 380                                         if_bit_0(subcoder[subcoder_index]) {
 381                                                 update_bit_0(subcoder[subcoder_index]);
 382                                                 symbol <<= 1;
 383                                                 if (match_bit != 0)
 384                                                         break;
 385                                         } else {
 386                                                 update_bit_1(subcoder[subcoder_index]);
 387                                                 symbol = (symbol << 1) | 1;
 388                                                 if (match_bit == 0)
 389                                                         break;
 390                                         }
 391                                 } while (symbol < 0x100);
 392                         }
 393
 394                         // Decode literal without match byte. This is also
 395                         // the tail of the with-match-byte function.
 396                         while (symbol < 0x100) {
 397                                 if_bit_0(subcoder[symbol]) {
 398                                         update_bit_0(subcoder[symbol]);
 399                                         symbol <<= 1;
 400                                 } else {
 401                                         update_bit_1(subcoder[symbol]);
 402                                         symbol = (symbol << 1) | 1;
 403                                 }
 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_char(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 rep0.
 429
 430                         // The latest three match distances are kept in
 431                         // memory in case there are repeated matches.
 432                         rep3 = rep2;
 433                         rep2 = rep1;
 434                         rep1 = rep0;
 435
 436                         // Decode the length of the match.
 437                         length_decode(len, coder->len_decoder, pos_state);
 438
 439                         update_match(state);
 440
 441                         const uint32_t len_to_pos_state = get_len_to_pos_state(len);
 442                         uint32_t pos_slot = 0;
 443                         bittree_decode(pos_slot,
 444                                         coder->pos_slot_decoder[len_to_pos_state], POS_SLOT_BITS);
 445                         assert(pos_slot <= 63);
 446
 447                         if (pos_slot >= START_POS_MODEL_INDEX) {
 448                                 uint32_t direct_bits = (pos_slot >> 1) - 1;
 449                                 assert(direct_bits >= 1 && direct_bits <= 30);
 450                                 rep0 = 2 | (pos_slot & 1);
 451
 452                                 if (pos_slot < END_POS_MODEL_INDEX) {
 453                                         assert(direct_bits <= 5);
 454                                         rep0 <<= direct_bits;
 455                                         assert(rep0 <= 96);
 456                                         // -1 is fine, because
 457                                         // bittree_reverse_decode()
 458                                         // starts from table index [1]
 459                                         // (not [0]).
 460                                         assert((int32_t)(rep0 - pos_slot - 1) >= -1);
 461                                         assert((int32_t)(rep0 - pos_slot - 1) <= 82);
 462                                         // We add the result to rep0, so rep0
 463                                         // must not be part of second argument
 464                                         // of the macro.
 465                                         const int32_t offset = rep0 - pos_slot - 1;
 466                                         bittree_reverse_decode(rep0, coder->pos_decoders + offset,
 467                                                         direct_bits);
 468                                 } else {
 469                                         assert(pos_slot >= 14);
 470                                         assert(direct_bits >= 6);
 471                                         direct_bits -= ALIGN_BITS;
 472                                         assert(direct_bits >= 2);
 473                                         rc_decode_direct(rep0, direct_bits);
 474                                         rep0 <<= ALIGN_BITS;
 475
 476                                         bittree_reverse_decode(rep0, coder->pos_align_decoder,
 477                                                         ALIGN_BITS);
 478
 479                                         if (rep0 == UINT32_MAX) {
 480                                                 if (len == LEN_SPECIAL_EOPM) {
 481                                                         // End of Payload Marker found.
 482                                                         coder->lz.eopm_detected = true;
 483                                                         break;
 484
 485                                                 } else if (len == LEN_SPECIAL_FLUSH) {
 486                                                         // Flush marker detected. We must have produced
 487                                                         // at least one byte of output since the previous
 488                                                         // flush marker or the beginning of the stream.
 489                                                         // This is to prevent hanging the decoder with
 490                                                         // malicious input files.
 491                                                         if (!coder->has_produced_output)
 492                                                                 return true;
 493
 494                                                         coder->has_produced_output = false;
 495
 496                                                         rc_reset(rc);
 497                                                         if (!rc_read_init(&rc, in, &in_pos_local, in_size))
 498                                                                 break;
 499
 500                                                 } else {
 501                                                         return true;
 502                                                 }
 503                                         }
 504                                 }
 505                         } else {
 506                                 rep0 = pos_slot;
 507                         }
 508
 509                 } else {
 510                         update_bit_1(coder->is_rep[state]);
 511
 512                         // Repeated match
 513                         //
 514                         // The match distance is a value that we have had
 515                         // earlier. The latest four match distances are
 516                         // available as rep0, rep1, rep2 and rep3. We will
 517                         // now decode which of them is the new distance.
 518
 519                         if_bit_0(coder->is_rep0[state]) {
 520                                 update_bit_0(coder->is_rep0[state]);
 521
 522                                 // The distance is rep0.
 523
 524                                 if_bit_0(coder->is_rep0_long[state][pos_state]) {
 525                                         update_bit_0(coder->is_rep0_long[state][pos_state]);
 526
 527                                         // Repeating exactly one byte. For
 528                                         // simplicity, it is done here inline
 529                                         // instead of at the end of the main
 530                                         // loop.
 531
 532                                         update_short_rep(state);
 533
 534                                         // Security/sanity checks. See the end
 535                                         // of the main loop for explanation
 536                                         // of these.
 537                                         if ((rep0 >= coder->lz.pos && !coder->lz.is_full)
 538                                                         || in_pos_local > in_size)
 539                                                 return true;
 540
 541                                         // Repeat one byte and start a new
 542                                         // decoding loop.
 543                                         coder->lz.dict[coder->lz.pos]
 544                                                         = lz_get_byte(coder->lz, rep0);
 545                                         ++coder->lz.pos;
 546                                         ++now_pos;
 547                                         has_produced_output = true;
 548                                         continue;
 549
 550                                 } else {
 551                                         update_bit_1(coder->is_rep0_long[state][pos_state]);
 552
 553                                         // Repeating more than one byte at
 554                                         // distance of rep0.
 555                                 }
 556
 557                         } else {
 558                                 update_bit_1(coder->is_rep0[state]);
 559
 560                                 // The distance is rep1, rep2 or rep3. Once
 561                                 // we find out which one of these three, it
 562                                 // is stored to rep0 and rep1, rep2 and rep3
 563                                 // are updated accordingly.
 564
 565                                 uint32_t distance;
 566
 567                                 if_bit_0(coder->is_rep1[state]) {
 568                                         update_bit_0(coder->is_rep1[state]);
 569                                         distance = rep1;
 570                                 } else {
 571                                         update_bit_1(coder->is_rep1[state]);
 572
 573                                         if_bit_0(coder->is_rep2[state]) {
 574                                                 update_bit_0(coder->is_rep2[state]);
 575                                                 distance = rep2;
 576                                         } else {
 577                                                 update_bit_1(coder->is_rep2[state]);
 578                                                 distance = rep3;
 579                                                 rep3 = rep2;
 580                                         }
 581
 582                                         rep2 = rep1;
 583                                 }
 584
 585                                 rep1 = rep0;
 586                                 rep0 = distance;
 587                         }
 588
 589                         // Decode the length of the repeated match.
 590                         length_decode(len, coder->rep_match_len_decoder, pos_state);
 591
 592                         update_rep(state);
 593                 }
 594
 595
 596                 /////////////////////////////////
 597                 // Repeat from history buffer. //
 598                 /////////////////////////////////
 599
 600                 // The length is always between these limits. There is no way
 601                 // to trigger the algorithm to set len outside this range.
 602                 assert(len >= MATCH_MIN_LEN);
 603                 assert(len <= MATCH_MAX_LEN);
 604
 605                 now_pos += len;
 606                 has_produced_output = true;
 607
 608                 // Validate the buffer position to avoid buffer overflows
 609                 // on corrupted input data.
 610                 if (in_pos_local > in_size)
 611                         return true;
 612
 613                 // Repeat len bytes from distance of rep0.
 614                 if (!lzma_lz_out_repeat(&coder->lz, rep0, len))
 615                         return true;
 616         }
 617
 618         rc_normalize();
 619
 620
 621         /////////////////////////////////
 622         // Update the *data structure. //
 623         /////////////////////////////////
 624
 625         // Range decoder
 626         rc_from_local(coder->rc);
 627
 628         // State
 629         coder->state = state;
 630         coder->rep0 = rep0;
 631         coder->rep1 = rep1;
 632         coder->rep2 = rep2;
 633         coder->rep3 = rep3;
 634
 635         // Misc
 636         coder->now_pos = now_pos;
 637         coder->has_produced_output = has_produced_output;
 638         *in_pos = in_pos_local;
 639
 640         return false;
 641 }
 642
 643
 644 static void
 645 lzma_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
 646 {
 647         lzma_next_coder_end(&coder->next, allocator);
 648         lzma_lz_decoder_end(&coder->lz, allocator);
 649         lzma_literal_end(&coder->literal_coder, allocator);
 650         lzma_free(coder, allocator);
 651         return;
 652 }
 653
 654
 655 extern lzma_ret
 656 lzma_lzma_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 657                 const lzma_filter_info *filters)
 658 {
 659         // Validate pos_bits. Other options are validated by the
 660         // respective initialization functions.
 661         const lzma_options_lzma *options = filters[0].options;
 662         if (options->pos_bits > LZMA_POS_BITS_MAX)
 663                 return LZMA_HEADER_ERROR;
 664
 665         // Allocate memory for the decoder if needed.
 666         if (next->coder == NULL) {
 667                 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 668                 if (next->coder == NULL)
 669                         return LZMA_MEM_ERROR;
 670
 671                 // Initialize variables so that we know later that we don't
 672                 // have an existing decoder initialized.
 673                 next->coder->next = LZMA_NEXT_CODER_INIT;
 674                 next->coder->lz = LZMA_LZ_DECODER_INIT;
 675                 next->coder->literal_coder = NULL;
 676         }
 677
 678         // Store the pos_bits and calculate pos_mask.
 679         next->coder->pos_bits = options->pos_bits;
 680         next->coder->pos_mask = (1U << next->coder->pos_bits) - 1;
 681
 682         // Allocate (if needed) and initialize the literal decoder.
 683         {
 684                 const lzma_ret ret = lzma_literal_init(
 685                                 &next->coder->literal_coder, allocator,
 686                                 options->literal_context_bits,
 687                                 options->literal_pos_bits);
 688                 if (ret != LZMA_OK) {
 689                         lzma_free(next->coder, allocator);
 690                         next->coder = NULL;
 691                         return ret;
 692                 }
 693         }
 694
 695         // Allocate and initialize the LZ decoder.
 696         {
 697                 const lzma_ret ret = lzma_lz_decoder_reset(
 698                                 &next->coder->lz, allocator, &decode_real,
 699                                 filters[0].uncompressed_size,
 700                                 options->dictionary_size, MATCH_MAX_LEN);
 701                 if (ret != LZMA_OK) {
 702                         lzma_literal_end(&next->coder->literal_coder,
 703                                         allocator);
 704                         lzma_free(next->coder, allocator);
 705                         next->coder = NULL;
 706                         return ret;
 707                 }
 708         }
 709
 710         // State
 711         next->coder->state = 0;
 712         next->coder->rep0 = 0;
 713         next->coder->rep1 = 0;
 714         next->coder->rep2 = 0;
 715         next->coder->rep3 = 0;
 716         next->coder->pos_bits = options->pos_bits;
 717         next->coder->pos_mask = (1 << next->coder->pos_bits) - 1;
 718         next->coder->now_pos = 0;
 719
 720         // Range decoder
 721         rc_reset(next->coder->rc);
 722
 723         // Bit and bittree decoders
 724         for (uint32_t i = 0; i < STATES; ++i) {
 725                 for (uint32_t j = 0; j <= next->coder->pos_mask; ++j) {
 726                         bit_reset(next->coder->is_match[i][j]);
 727                         bit_reset(next->coder->is_rep0_long[i][j]);
 728                 }
 729
 730                 bit_reset(next->coder->is_rep[i]);
 731                 bit_reset(next->coder->is_rep0[i]);
 732                 bit_reset(next->coder->is_rep1[i]);
 733                 bit_reset(next->coder->is_rep2[i]);
 734         }
 735
 736         for (uint32_t i = 0; i < LEN_TO_POS_STATES; ++i)
 737                 bittree_reset(next->coder->pos_slot_decoder[i], POS_SLOT_BITS);
 738
 739         for (uint32_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
 740                 bit_reset(next->coder->pos_decoders[i]);
 741
 742         bittree_reset(next->coder->pos_align_decoder, ALIGN_BITS);
 743
 744         // Len decoders (also bit/bittree)
 745         const uint32_t num_pos_states = 1 << next->coder->pos_bits;
 746         bit_reset(next->coder->len_decoder.choice);
 747         bit_reset(next->coder->len_decoder.choice2);
 748         bit_reset(next->coder->rep_match_len_decoder.choice);
 749         bit_reset(next->coder->rep_match_len_decoder.choice2);
 750
 751         for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
 752                 bittree_reset(next->coder->len_decoder.low[pos_state], LEN_LOW_BITS);
 753                 bittree_reset(next->coder->len_decoder.mid[pos_state], LEN_MID_BITS);
 754
 755                 bittree_reset(next->coder->rep_match_len_decoder.low[pos_state],
 756                                 LEN_LOW_BITS);
 757                 bittree_reset(next->coder->rep_match_len_decoder.mid[pos_state],
 758                                 LEN_MID_BITS);
 759         }
 760
 761         bittree_reset(next->coder->len_decoder.high, LEN_HIGH_BITS);
 762         bittree_reset(next->coder->rep_match_len_decoder.high, LEN_HIGH_BITS);
 763
 764         next->coder->has_produced_output = false;
 765
 766         // Initialize the next decoder in the chain, if any.
 767         {
 768                 const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
 769                                 allocator, filters + 1);
 770                 if (ret != LZMA_OK) {
 771                         lzma_decoder_end(next->coder, allocator);
 772                         return ret;
 773                 }
 774         }
 775
 776         // Initialization successful. Set the function pointers.
 777         next->code = &lzma_lz_decode;
 778         next->end = &lzma_decoder_end;
 779
 780         return LZMA_OK;
 781 }
 782
 783
 784 extern bool
 785 lzma_lzma_decode_properties(lzma_options_lzma *options, uint8_t byte)
 786 {
 787         if (byte > (4 * 5 + 4) * 9 + 8)
 788                 return true;
 789
 790         // See the file format specification to understand this.
 791         options->pos_bits = byte / (9 * 5);
 792         byte -= options->pos_bits * 9 * 5;
 793         options->literal_pos_bits = byte / 9;
 794         options->literal_context_bits = byte - options->literal_pos_bits * 9;
 795
 796         return false;
 797 }