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