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