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