src/liblzma/lzma/lzma_encoder_optimum_normal.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_encoder_optimum_normal.c
   4 //
   5 //  Author:     Igor Pavlov
   6 //
   7 //  This file has been put into the public domain.
   8 //  You can do whatever you want with this file.
   9 //
  10 ///////////////////////////////////////////////////////////////////////////////
  11
  12 #include "lzma_encoder_private.h"
  13 #include "fastpos.h"
  14
  15
  16 ////////////
  17 // Prices //
  18 ////////////
  19
  20 static uint32_t
  21 get_literal_price(const lzma_coder *const coder, const uint32_t pos,
  22                 const uint32_t prev_byte, const bool match_mode,
  23                 uint32_t match_byte, uint32_t symbol)
  24 {
  25         const probability *const subcoder = literal_subcoder(coder->literal,
  26                         coder->literal_context_bits, coder->literal_pos_mask,
  27                         pos, prev_byte);
  28
  29         uint32_t price = 0;
  30
  31         if (!match_mode) {
  32                 price = rc_bittree_price(subcoder, 8, symbol);
  33         } else {
  34                 uint32_t offset = 0x100;
  35                 symbol += UINT32_C(1) << 8;
  36
  37                 do {
  38                         match_byte <<= 1;
  39
  40                         const uint32_t match_bit = match_byte & offset;
  41                         const uint32_t subcoder_index
  42                                         = offset + match_bit + (symbol >> 8);
  43                         const uint32_t bit = (symbol >> 7) & 1;
  44                         price += rc_bit_price(subcoder[subcoder_index], bit);
  45
  46                         symbol <<= 1;
  47                         offset &= ~(match_byte ^ symbol);
  48
  49                 } while (symbol < (UINT32_C(1) << 16));
  50         }
  51
  52         return price;
  53 }
  54
  55
  56 static inline uint32_t
  57 get_len_price(const lzma_length_encoder *const lencoder,
  58                 const uint32_t len, const uint32_t pos_state)
  59 {
  60         // NOTE: Unlike the other price tables, length prices are updated
  61         // in lzma_encoder.c
  62         return lencoder->prices[pos_state][len - MATCH_LEN_MIN];
  63 }
  64
  65
  66 static inline uint32_t
  67 get_short_rep_price(const lzma_coder *const coder,
  68                 const lzma_lzma_state state, const uint32_t pos_state)
  69 {
  70         return rc_bit_0_price(coder->is_rep0[state])
  71                 + rc_bit_0_price(coder->is_rep0_long[state][pos_state]);
  72 }
  73
  74
  75 static inline uint32_t
  76 get_pure_rep_price(const lzma_coder *const coder, const uint32_t rep_index,
  77                 const lzma_lzma_state state, uint32_t pos_state)
  78 {
  79         uint32_t price;
  80
  81         if (rep_index == 0) {
  82                 price = rc_bit_0_price(coder->is_rep0[state]);
  83                 price += rc_bit_1_price(coder->is_rep0_long[state][pos_state]);
  84         } else {
  85                 price = rc_bit_1_price(coder->is_rep0[state]);
  86
  87                 if (rep_index == 1) {
  88                         price += rc_bit_0_price(coder->is_rep1[state]);
  89                 } else {
  90                         price += rc_bit_1_price(coder->is_rep1[state]);
  91                         price += rc_bit_price(coder->is_rep2[state],
  92                                         rep_index - 2);
  93                 }
  94         }
  95
  96         return price;
  97 }
  98
  99
 100 static inline uint32_t
 101 get_rep_price(const lzma_coder *const coder, const uint32_t rep_index,
 102                 const uint32_t len, const lzma_lzma_state state,
 103                 const uint32_t pos_state)
 104 {
 105         return get_len_price(&coder->rep_len_encoder, len, pos_state)
 106                 + get_pure_rep_price(coder, rep_index, state, pos_state);
 107 }
 108
 109
 110 static inline uint32_t
 111 get_pos_len_price(const lzma_coder *const coder, const uint32_t pos,
 112                 const uint32_t len, const uint32_t pos_state)
 113 {
 114         const uint32_t len_to_pos_state = get_len_to_pos_state(len);
 115         uint32_t price;
 116
 117         if (pos < FULL_DISTANCES) {
 118                 price = coder->distances_prices[len_to_pos_state][pos];
 119         } else {
 120                 const uint32_t pos_slot = get_pos_slot_2(pos);
 121                 price = coder->pos_slot_prices[len_to_pos_state][pos_slot]
 122                                 + coder->align_prices[pos & ALIGN_MASK];
 123         }
 124
 125         price += get_len_price(&coder->match_len_encoder, len, pos_state);
 126
 127         return price;
 128 }
 129
 130
 131 static void
 132 fill_distances_prices(lzma_coder *coder)
 133 {
 134         for (uint32_t len_to_pos_state = 0;
 135                         len_to_pos_state < LEN_TO_POS_STATES;
 136                         ++len_to_pos_state) {
 137
 138                 uint32_t *const pos_slot_prices
 139                                 = coder->pos_slot_prices[len_to_pos_state];
 140
 141                 // Price to encode the pos_slot.
 142                 for (uint32_t pos_slot = 0;
 143                                 pos_slot < coder->dist_table_size; ++pos_slot)
 144                         pos_slot_prices[pos_slot] = rc_bittree_price(
 145                                         coder->pos_slot[len_to_pos_state],
 146                                         POS_SLOT_BITS, pos_slot);
 147
 148                 // For matches with distance >= FULL_DISTANCES, add the price
 149                 // of the direct bits part of the match distance. (Align bits
 150                 // are handled by fill_align_prices()).
 151                 for (uint32_t pos_slot = END_POS_MODEL_INDEX;
 152                                 pos_slot < coder->dist_table_size; ++pos_slot)
 153                         pos_slot_prices[pos_slot] += rc_direct_price(
 154                                         ((pos_slot >> 1) - 1) - ALIGN_BITS);
 155
 156                 // Distances in the range [0, 3] are fully encoded with
 157                 // pos_slot, so they are used for coder->distances_prices
 158                 // as is.
 159                 for (uint32_t i = 0; i < START_POS_MODEL_INDEX; ++i)
 160                         coder->distances_prices[len_to_pos_state][i]
 161                                         = pos_slot_prices[i];
 162         }
 163
 164         // Distances in the range [4, 127] depend on pos_slot and pos_special.
 165         // We do this in a loop separate from the above loop to avoid
 166         // redundant calls to get_pos_slot().
 167         for (uint32_t i = START_POS_MODEL_INDEX; i < FULL_DISTANCES; ++i) {
 168                 const uint32_t pos_slot = get_pos_slot(i);
 169                 const uint32_t footer_bits = ((pos_slot >> 1) - 1);
 170                 const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
 171                 const uint32_t price = rc_bittree_reverse_price(
 172                                 coder->pos_special + base - pos_slot - 1,
 173                                 footer_bits, i - base);
 174
 175                 for (uint32_t len_to_pos_state = 0;
 176                                 len_to_pos_state < LEN_TO_POS_STATES;
 177                                 ++len_to_pos_state)
 178                         coder->distances_prices[len_to_pos_state][i]
 179                                         = price + coder->pos_slot_prices[
 180                                                 len_to_pos_state][pos_slot];
 181         }
 182
 183         coder->match_price_count = 0;
 184         return;
 185 }
 186
 187
 188 static void
 189 fill_align_prices(lzma_coder *coder)
 190 {
 191         for (uint32_t i = 0; i < ALIGN_TABLE_SIZE; ++i)
 192                 coder->align_prices[i] = rc_bittree_reverse_price(
 193                                 coder->pos_align, ALIGN_BITS, i);
 194
 195         coder->align_price_count = 0;
 196         return;
 197 }
 198
 199
 200 /////////////
 201 // Optimal //
 202 /////////////
 203
 204 static inline void
 205 make_literal(lzma_optimal *optimal)
 206 {
 207         optimal->back_prev = UINT32_MAX;
 208         optimal->prev_1_is_literal = false;
 209 }
 210
 211
 212 static inline void
 213 make_short_rep(lzma_optimal *optimal)
 214 {
 215         optimal->back_prev = 0;
 216         optimal->prev_1_is_literal = false;
 217 }
 218
 219
 220 #define is_short_rep(optimal) \
 221         ((optimal).back_prev == 0)
 222
 223
 224 static void
 225 backward(lzma_coder *restrict coder, uint32_t *restrict len_res,
 226                 uint32_t *restrict back_res, uint32_t cur)
 227 {
 228         coder->opts_end_index = cur;
 229
 230         uint32_t pos_mem = coder->opts[cur].pos_prev;
 231         uint32_t back_mem = coder->opts[cur].back_prev;
 232
 233         do {
 234                 if (coder->opts[cur].prev_1_is_literal) {
 235                         make_literal(&coder->opts[pos_mem]);
 236                         coder->opts[pos_mem].pos_prev = pos_mem - 1;
 237
 238                         if (coder->opts[cur].prev_2) {
 239                                 coder->opts[pos_mem - 1].prev_1_is_literal
 240                                                 = false;
 241                                 coder->opts[pos_mem - 1].pos_prev
 242                                                 = coder->opts[cur].pos_prev_2;
 243                                 coder->opts[pos_mem - 1].back_prev
 244                                                 = coder->opts[cur].back_prev_2;
 245                         }
 246                 }
 247
 248                 const uint32_t pos_prev = pos_mem;
 249                 const uint32_t back_cur = back_mem;
 250
 251                 back_mem = coder->opts[pos_prev].back_prev;
 252                 pos_mem = coder->opts[pos_prev].pos_prev;
 253
 254                 coder->opts[pos_prev].back_prev = back_cur;
 255                 coder->opts[pos_prev].pos_prev = cur;
 256                 cur = pos_prev;
 257
 258         } while (cur != 0);
 259
 260         coder->opts_current_index = coder->opts[0].pos_prev;
 261         *len_res = coder->opts[0].pos_prev;
 262         *back_res = coder->opts[0].back_prev;
 263
 264         return;
 265 }
 266
 267
 268 //////////
 269 // Main //
 270 //////////
 271
 272 static inline uint32_t
 273 helper1(lzma_coder *restrict coder, lzma_mf *restrict mf,
 274                 uint32_t *restrict back_res, uint32_t *restrict len_res,
 275                 uint32_t position)
 276 {
 277         const uint32_t nice_len = mf->nice_len;
 278
 279         uint32_t len_main;
 280         uint32_t matches_count;
 281
 282         if (mf->read_ahead == 0) {
 283                 len_main = mf_find(mf, &matches_count, coder->matches);
 284         } else {
 285                 assert(mf->read_ahead == 1);
 286                 len_main = coder->longest_match_length;
 287                 matches_count = coder->matches_count;
 288         }
 289
 290         const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
 291         if (buf_avail < 2) {
 292                 *back_res = UINT32_MAX;
 293                 *len_res = 1;
 294                 return UINT32_MAX;
 295         }
 296
 297         const uint8_t *const buf = mf_ptr(mf) - 1;
 298
 299         uint32_t rep_lens[REP_DISTANCES];
 300         uint32_t rep_max_index = 0;
 301
 302         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 303                 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
 304
 305                 if (not_equal_16(buf, buf_back)) {
 306                         rep_lens[i] = 0;
 307                         continue;
 308                 }
 309
 310                 uint32_t len_test;
 311                 for (len_test = 2; len_test < buf_avail
 312                                 && buf[len_test] == buf_back[len_test];
 313                                 ++len_test) ;
 314
 315                 rep_lens[i] = len_test;
 316                 if (len_test > rep_lens[rep_max_index])
 317                         rep_max_index = i;
 318         }
 319
 320         if (rep_lens[rep_max_index] >= nice_len) {
 321                 *back_res = rep_max_index;
 322                 *len_res = rep_lens[rep_max_index];
 323                 mf_skip(mf, *len_res - 1);
 324                 return UINT32_MAX;
 325         }
 326
 327
 328         if (len_main >= nice_len) {
 329                 *back_res = coder->matches[matches_count - 1].dist
 330                                 + REP_DISTANCES;
 331                 *len_res = len_main;
 332                 mf_skip(mf, len_main - 1);
 333                 return UINT32_MAX;
 334         }
 335
 336         const uint8_t current_byte = *buf;
 337         const uint8_t match_byte = *(buf - coder->reps[0] - 1);
 338
 339         if (len_main < 2 && current_byte != match_byte
 340                         && rep_lens[rep_max_index] < 2) {
 341                 *back_res = UINT32_MAX;
 342                 *len_res = 1;
 343                 return UINT32_MAX;
 344         }
 345
 346         coder->opts[0].state = coder->state;
 347
 348         const uint32_t pos_state = position & coder->pos_mask;
 349
 350         coder->opts[1].price = rc_bit_0_price(
 351                                 coder->is_match[coder->state][pos_state])
 352                         + get_literal_price(coder, position, buf[-1],
 353                                 !is_literal_state(coder->state),
 354                                 match_byte, current_byte);
 355
 356         make_literal(&coder->opts[1]);
 357
 358         const uint32_t match_price = rc_bit_1_price(
 359                         coder->is_match[coder->state][pos_state]);
 360         const uint32_t rep_match_price = match_price
 361                         + rc_bit_1_price(coder->is_rep[coder->state]);
 362
 363         if (match_byte == current_byte) {
 364                 const uint32_t short_rep_price = rep_match_price
 365                                 + get_short_rep_price(
 366                                         coder, coder->state, pos_state);
 367
 368                 if (short_rep_price < coder->opts[1].price) {
 369                         coder->opts[1].price = short_rep_price;
 370                         make_short_rep(&coder->opts[1]);
 371                 }
 372         }
 373
 374         const uint32_t len_end = my_max(len_main, rep_lens[rep_max_index]);
 375
 376         if (len_end < 2) {
 377                 *back_res = coder->opts[1].back_prev;
 378                 *len_res = 1;
 379                 return UINT32_MAX;
 380         }
 381
 382         coder->opts[1].pos_prev = 0;
 383
 384         for (uint32_t i = 0; i < REP_DISTANCES; ++i)
 385                 coder->opts[0].backs[i] = coder->reps[i];
 386
 387         uint32_t len = len_end;
 388         do {
 389                 coder->opts[len].price = RC_INFINITY_PRICE;
 390         } while (--len >= 2);
 391
 392
 393         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 394                 uint32_t rep_len = rep_lens[i];
 395                 if (rep_len < 2)
 396                         continue;
 397
 398                 const uint32_t price = rep_match_price + get_pure_rep_price(
 399                                 coder, i, coder->state, pos_state);
 400
 401                 do {
 402                         const uint32_t cur_and_len_price = price
 403                                         + get_len_price(
 404                                                 &coder->rep_len_encoder,
 405                                                 rep_len, pos_state);
 406
 407                         if (cur_and_len_price < coder->opts[rep_len].price) {
 408                                 coder->opts[rep_len].price = cur_and_len_price;
 409                                 coder->opts[rep_len].pos_prev = 0;
 410                                 coder->opts[rep_len].back_prev = i;
 411                                 coder->opts[rep_len].prev_1_is_literal = false;
 412                         }
 413                 } while (--rep_len >= 2);
 414         }
 415
 416
 417         const uint32_t normal_match_price = match_price
 418                         + rc_bit_0_price(coder->is_rep[coder->state]);
 419
 420         len = rep_lens[0] >= 2 ? rep_lens[0] + 1 : 2;
 421         if (len <= len_main) {
 422                 uint32_t i = 0;
 423                 while (len > coder->matches[i].len)
 424                         ++i;
 425
 426                 for(; ; ++len) {
 427                         const uint32_t dist = coder->matches[i].dist;
 428                         const uint32_t cur_and_len_price = normal_match_price
 429                                         + get_pos_len_price(coder,
 430                                                 dist, len, pos_state);
 431
 432                         if (cur_and_len_price < coder->opts[len].price) {
 433                                 coder->opts[len].price = cur_and_len_price;
 434                                 coder->opts[len].pos_prev = 0;
 435                                 coder->opts[len].back_prev
 436                                                 = dist + REP_DISTANCES;
 437                                 coder->opts[len].prev_1_is_literal = false;
 438                         }
 439
 440                         if (len == coder->matches[i].len)
 441                                 if (++i == matches_count)
 442                                         break;
 443                 }
 444         }
 445
 446         return len_end;
 447 }
 448
 449
 450 static inline uint32_t
 451 helper2(lzma_coder *coder, uint32_t *reps, const uint8_t *buf,
 452                 uint32_t len_end, uint32_t position, const uint32_t cur,
 453                 const uint32_t nice_len, const uint32_t buf_avail_full)
 454 {
 455         uint32_t matches_count = coder->matches_count;
 456         uint32_t new_len = coder->longest_match_length;
 457         uint32_t pos_prev = coder->opts[cur].pos_prev;
 458         lzma_lzma_state state;
 459
 460         if (coder->opts[cur].prev_1_is_literal) {
 461                 --pos_prev;
 462
 463                 if (coder->opts[cur].prev_2) {
 464                         state = coder->opts[coder->opts[cur].pos_prev_2].state;
 465
 466                         if (coder->opts[cur].back_prev_2 < REP_DISTANCES)
 467                                 update_long_rep(state);
 468                         else
 469                                 update_match(state);
 470
 471                 } else {
 472                         state = coder->opts[pos_prev].state;
 473                 }
 474
 475                 update_literal(state);
 476
 477         } else {
 478                 state = coder->opts[pos_prev].state;
 479         }
 480
 481         if (pos_prev == cur - 1) {
 482                 if (is_short_rep(coder->opts[cur]))
 483                         update_short_rep(state);
 484                 else
 485                         update_literal(state);
 486         } else {
 487                 uint32_t pos;
 488                 if (coder->opts[cur].prev_1_is_literal
 489                                 && coder->opts[cur].prev_2) {
 490                         pos_prev = coder->opts[cur].pos_prev_2;
 491                         pos = coder->opts[cur].back_prev_2;
 492                         update_long_rep(state);
 493                 } else {
 494                         pos = coder->opts[cur].back_prev;
 495                         if (pos < REP_DISTANCES)
 496                                 update_long_rep(state);
 497                         else
 498                                 update_match(state);
 499                 }
 500
 501                 if (pos < REP_DISTANCES) {
 502                         reps[0] = coder->opts[pos_prev].backs[pos];
 503
 504                         uint32_t i;
 505                         for (i = 1; i <= pos; ++i)
 506                                 reps[i] = coder->opts[pos_prev].backs[i - 1];
 507
 508                         for (; i < REP_DISTANCES; ++i)
 509                                 reps[i] = coder->opts[pos_prev].backs[i];
 510
 511                 } else {
 512                         reps[0] = pos - REP_DISTANCES;
 513
 514                         for (uint32_t i = 1; i < REP_DISTANCES; ++i)
 515                                 reps[i] = coder->opts[pos_prev].backs[i - 1];
 516                 }
 517         }
 518
 519         coder->opts[cur].state = state;
 520
 521         for (uint32_t i = 0; i < REP_DISTANCES; ++i)
 522                 coder->opts[cur].backs[i] = reps[i];
 523
 524         const uint32_t cur_price = coder->opts[cur].price;
 525
 526         const uint8_t current_byte = *buf;
 527         const uint8_t match_byte = *(buf - reps[0] - 1);
 528
 529         const uint32_t pos_state = position & coder->pos_mask;
 530
 531         const uint32_t cur_and_1_price = cur_price
 532                         + rc_bit_0_price(coder->is_match[state][pos_state])
 533                         + get_literal_price(coder, position, buf[-1],
 534                         !is_literal_state(state), match_byte, current_byte);
 535
 536         bool next_is_literal = false;
 537
 538         if (cur_and_1_price < coder->opts[cur + 1].price) {
 539                 coder->opts[cur + 1].price = cur_and_1_price;
 540                 coder->opts[cur + 1].pos_prev = cur;
 541                 make_literal(&coder->opts[cur + 1]);
 542                 next_is_literal = true;
 543         }
 544
 545         const uint32_t match_price = cur_price
 546                         + rc_bit_1_price(coder->is_match[state][pos_state]);
 547         const uint32_t rep_match_price = match_price
 548                         + rc_bit_1_price(coder->is_rep[state]);
 549
 550         if (match_byte == current_byte
 551                         && !(coder->opts[cur + 1].pos_prev < cur
 552                                 && coder->opts[cur + 1].back_prev == 0)) {
 553
 554                 const uint32_t short_rep_price = rep_match_price
 555                                 + get_short_rep_price(coder, state, pos_state);
 556
 557                 if (short_rep_price <= coder->opts[cur + 1].price) {
 558                         coder->opts[cur + 1].price = short_rep_price;
 559                         coder->opts[cur + 1].pos_prev = cur;
 560                         make_short_rep(&coder->opts[cur + 1]);
 561                         next_is_literal = true;
 562                 }
 563         }
 564
 565         if (buf_avail_full < 2)
 566                 return len_end;
 567
 568         const uint32_t buf_avail = my_min(buf_avail_full, nice_len);
 569
 570         if (!next_is_literal && match_byte != current_byte) { // speed optimization
 571                 // try literal + rep0
 572                 const uint8_t *const buf_back = buf - reps[0] - 1;
 573                 const uint32_t limit = my_min(buf_avail_full, nice_len + 1);
 574
 575                 uint32_t len_test = 1;
 576                 while (len_test < limit && buf[len_test] == buf_back[len_test])
 577                         ++len_test;
 578
 579                 --len_test;
 580
 581                 if (len_test >= 2) {
 582                         lzma_lzma_state state_2 = state;
 583                         update_literal(state_2);
 584
 585                         const uint32_t pos_state_next = (position + 1) & coder->pos_mask;
 586                         const uint32_t next_rep_match_price = cur_and_1_price
 587                                         + rc_bit_1_price(coder->is_match[state_2][pos_state_next])
 588                                         + rc_bit_1_price(coder->is_rep[state_2]);
 589
 590                         //for (; len_test >= 2; --len_test) {
 591                         const uint32_t offset = cur + 1 + len_test;
 592
 593                         while (len_end < offset)
 594                                 coder->opts[++len_end].price = RC_INFINITY_PRICE;
 595
 596                         const uint32_t cur_and_len_price = next_rep_match_price
 597                                         + get_rep_price(coder, 0, len_test,
 598                                                 state_2, pos_state_next);
 599
 600                         if (cur_and_len_price < coder->opts[offset].price) {
 601                                 coder->opts[offset].price = cur_and_len_price;
 602                                 coder->opts[offset].pos_prev = cur + 1;
 603                                 coder->opts[offset].back_prev = 0;
 604                                 coder->opts[offset].prev_1_is_literal = true;
 605                                 coder->opts[offset].prev_2 = false;
 606                         }
 607                         //}
 608                 }
 609         }
 610
 611
 612         uint32_t start_len = 2; // speed optimization
 613
 614         for (uint32_t rep_index = 0; rep_index < REP_DISTANCES; ++rep_index) {
 615                 const uint8_t *const buf_back = buf - reps[rep_index] - 1;
 616                 if (not_equal_16(buf, buf_back))
 617                         continue;
 618
 619                 uint32_t len_test;
 620                 for (len_test = 2; len_test < buf_avail
 621                                 && buf[len_test] == buf_back[len_test];
 622                                 ++len_test) ;
 623
 624                 while (len_end < cur + len_test)
 625                         coder->opts[++len_end].price = RC_INFINITY_PRICE;
 626
 627                 const uint32_t len_test_temp = len_test;
 628                 const uint32_t price = rep_match_price + get_pure_rep_price(
 629                                 coder, rep_index, state, pos_state);
 630
 631                 do {
 632                         const uint32_t cur_and_len_price = price
 633                                         + get_len_price(&coder->rep_len_encoder,
 634                                                         len_test, pos_state);
 635
 636                         if (cur_and_len_price < coder->opts[cur + len_test].price) {
 637                                 coder->opts[cur + len_test].price = cur_and_len_price;
 638                                 coder->opts[cur + len_test].pos_prev = cur;
 639                                 coder->opts[cur + len_test].back_prev = rep_index;
 640                                 coder->opts[cur + len_test].prev_1_is_literal = false;
 641                         }
 642                 } while (--len_test >= 2);
 643
 644                 len_test = len_test_temp;
 645
 646                 if (rep_index == 0)
 647                         start_len = len_test + 1;
 648
 649
 650                 uint32_t len_test_2 = len_test + 1;
 651                 const uint32_t limit = my_min(buf_avail_full,
 652                                 len_test_2 + nice_len);
 653                 for (; len_test_2 < limit
 654                                 && buf[len_test_2] == buf_back[len_test_2];
 655                                 ++len_test_2) ;
 656
 657                 len_test_2 -= len_test + 1;
 658
 659                 if (len_test_2 >= 2) {
 660                         lzma_lzma_state state_2 = state;
 661                         update_long_rep(state_2);
 662
 663                         uint32_t pos_state_next = (position + len_test) & coder->pos_mask;
 664
 665                         const uint32_t cur_and_len_literal_price = price
 666                                         + get_len_price(&coder->rep_len_encoder,
 667                                                 len_test, pos_state)
 668                                         + rc_bit_0_price(coder->is_match[state_2][pos_state_next])
 669                                         + get_literal_price(coder, position + len_test,
 670                                                 buf[len_test - 1], true,
 671                                                 buf_back[len_test], buf[len_test]);
 672
 673                         update_literal(state_2);
 674
 675                         pos_state_next = (position + len_test + 1) & coder->pos_mask;
 676
 677                         const uint32_t next_rep_match_price = cur_and_len_literal_price
 678                                         + rc_bit_1_price(coder->is_match[state_2][pos_state_next])
 679                                         + rc_bit_1_price(coder->is_rep[state_2]);
 680
 681                         //for(; len_test_2 >= 2; len_test_2--) {
 682                         const uint32_t offset = cur + len_test + 1 + len_test_2;
 683
 684                         while (len_end < offset)
 685                                 coder->opts[++len_end].price = RC_INFINITY_PRICE;
 686
 687                         const uint32_t cur_and_len_price = next_rep_match_price
 688                                         + get_rep_price(coder, 0, len_test_2,
 689                                                 state_2, pos_state_next);
 690
 691                         if (cur_and_len_price < coder->opts[offset].price) {
 692                                 coder->opts[offset].price = cur_and_len_price;
 693                                 coder->opts[offset].pos_prev = cur + len_test + 1;
 694                                 coder->opts[offset].back_prev = 0;
 695                                 coder->opts[offset].prev_1_is_literal = true;
 696                                 coder->opts[offset].prev_2 = true;
 697                                 coder->opts[offset].pos_prev_2 = cur;
 698                                 coder->opts[offset].back_prev_2 = rep_index;
 699                         }
 700                         //}
 701                 }
 702         }
 703
 704
 705         //for (uint32_t len_test = 2; len_test <= new_len; ++len_test)
 706         if (new_len > buf_avail) {
 707                 new_len = buf_avail;
 708
 709                 matches_count = 0;
 710                 while (new_len > coder->matches[matches_count].len)
 711                         ++matches_count;
 712
 713                 coder->matches[matches_count++].len = new_len;
 714         }
 715
 716
 717         if (new_len >= start_len) {
 718                 const uint32_t normal_match_price = match_price
 719                                 + rc_bit_0_price(coder->is_rep[state]);
 720
 721                 while (len_end < cur + new_len)
 722                         coder->opts[++len_end].price = RC_INFINITY_PRICE;
 723
 724                 uint32_t i = 0;
 725                 while (start_len > coder->matches[i].len)
 726                         ++i;
 727
 728                 for (uint32_t len_test = start_len; ; ++len_test) {
 729                         const uint32_t cur_back = coder->matches[i].dist;
 730                         uint32_t cur_and_len_price = normal_match_price
 731                                         + get_pos_len_price(coder,
 732                                                 cur_back, len_test, pos_state);
 733
 734                         if (cur_and_len_price < coder->opts[cur + len_test].price) {
 735                                 coder->opts[cur + len_test].price = cur_and_len_price;
 736                                 coder->opts[cur + len_test].pos_prev = cur;
 737                                 coder->opts[cur + len_test].back_prev
 738                                                 = cur_back + REP_DISTANCES;
 739                                 coder->opts[cur + len_test].prev_1_is_literal = false;
 740                         }
 741
 742                         if (len_test == coder->matches[i].len) {
 743                                 // Try Match + Literal + Rep0
 744                                 const uint8_t *const buf_back = buf - cur_back - 1;
 745                                 uint32_t len_test_2 = len_test + 1;
 746                                 const uint32_t limit = my_min(buf_avail_full,
 747                                                 len_test_2 + nice_len);
 748
 749                                 for (; len_test_2 < limit &&
 750                                                 buf[len_test_2] == buf_back[len_test_2];
 751                                                 ++len_test_2) ;
 752
 753                                 len_test_2 -= len_test + 1;
 754
 755                                 if (len_test_2 >= 2) {
 756                                         lzma_lzma_state state_2 = state;
 757                                         update_match(state_2);
 758                                         uint32_t pos_state_next
 759                                                         = (position + len_test) & coder->pos_mask;
 760
 761                                         const uint32_t cur_and_len_literal_price = cur_and_len_price
 762                                                         + rc_bit_0_price(
 763                                                                 coder->is_match[state_2][pos_state_next])
 764                                                         + get_literal_price(coder,
 765                                                                 position + len_test,
 766                                                                 buf[len_test - 1],
 767                                                                 true,
 768                                                                 buf_back[len_test],
 769                                                                 buf[len_test]);
 770
 771                                         update_literal(state_2);
 772                                         pos_state_next = (pos_state_next + 1) & coder->pos_mask;
 773
 774                                         const uint32_t next_rep_match_price
 775                                                         = cur_and_len_literal_price
 776                                                         + rc_bit_1_price(
 777                                                                 coder->is_match[state_2][pos_state_next])
 778                                                         + rc_bit_1_price(coder->is_rep[state_2]);
 779
 780                                         // for(; len_test_2 >= 2; --len_test_2) {
 781                                         const uint32_t offset = cur + len_test + 1 + len_test_2;
 782
 783                                         while (len_end < offset)
 784                                                 coder->opts[++len_end].price = RC_INFINITY_PRICE;
 785
 786                                         cur_and_len_price = next_rep_match_price
 787                                                         + get_rep_price(coder, 0, len_test_2,
 788                                                                 state_2, pos_state_next);
 789
 790                                         if (cur_and_len_price < coder->opts[offset].price) {
 791                                                 coder->opts[offset].price = cur_and_len_price;
 792                                                 coder->opts[offset].pos_prev = cur + len_test + 1;
 793                                                 coder->opts[offset].back_prev = 0;
 794                                                 coder->opts[offset].prev_1_is_literal = true;
 795                                                 coder->opts[offset].prev_2 = true;
 796                                                 coder->opts[offset].pos_prev_2 = cur;
 797                                                 coder->opts[offset].back_prev_2
 798                                                                 = cur_back + REP_DISTANCES;
 799                                         }
 800                                         //}
 801                                 }
 802
 803                                 if (++i == matches_count)
 804                                         break;
 805                         }
 806                 }
 807         }
 808
 809         return len_end;
 810 }
 811
 812
 813 extern void
 814 lzma_lzma_optimum_normal(lzma_coder *restrict coder, lzma_mf *restrict mf,
 815                 uint32_t *restrict back_res, uint32_t *restrict len_res,
 816                 uint32_t position)
 817 {
 818         // If we have symbols pending, return the next pending symbol.
 819         if (coder->opts_end_index != coder->opts_current_index) {
 820                 assert(mf->read_ahead > 0);
 821                 *len_res = coder->opts[coder->opts_current_index].pos_prev
 822                                 - coder->opts_current_index;
 823                 *back_res = coder->opts[coder->opts_current_index].back_prev;
 824                 coder->opts_current_index = coder->opts[
 825                                 coder->opts_current_index].pos_prev;
 826                 return;
 827         }
 828
 829         // Update the price tables. In LZMA SDK <= 4.60 (and possibly later)
 830         // this was done in both initialization function and in the main loop.
 831         // In liblzma they were moved into this single place.
 832         if (mf->read_ahead == 0) {
 833                 if (coder->match_price_count >= (1 << 7))
 834                         fill_distances_prices(coder);
 835
 836                 if (coder->align_price_count >= ALIGN_TABLE_SIZE)
 837                         fill_align_prices(coder);
 838         }
 839
 840         // TODO: This needs quite a bit of cleaning still. But splitting
 841         // the original function into two pieces makes it at least a little
 842         // more readable, since those two parts don't share many variables.
 843
 844         uint32_t len_end = helper1(coder, mf, back_res, len_res, position);
 845         if (len_end == UINT32_MAX)
 846                 return;
 847
 848         uint32_t reps[REP_DISTANCES];
 849         memcpy(reps, coder->reps, sizeof(reps));
 850
 851         uint32_t cur;
 852         for (cur = 1; cur < len_end; ++cur) {
 853                 assert(cur < OPTS);
 854
 855                 coder->longest_match_length = mf_find(
 856                                 mf, &coder->matches_count, coder->matches);
 857
 858                 if (coder->longest_match_length >= mf->nice_len)
 859                         break;
 860
 861                 len_end = helper2(coder, reps, mf_ptr(mf) - 1, len_end,
 862                                 position + cur, cur, mf->nice_len,
 863                                 my_min(mf_avail(mf) + 1, OPTS - 1 - cur));
 864         }
 865
 866         backward(coder, len_res, back_res, cur);
 867         return;
 868 }