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