src/liblzma/lzma/lzma_encoder_getoptimum.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_encoder_getoptimum.c
   4 //
   5 //  Copyright (C) 1999-2006 Igor Pavlov
   6 //  Copyright (C) 2007 Lasse Collin
   7 //
   8 //  This library is free software; you can redistribute it and/or
   9 //  modify it under the terms of the GNU Lesser General Public
  10 //  License as published by the Free Software Foundation; either
  11 //  version 2.1 of the License, or (at your option) any later version.
  12 //
  13 //  This library is distributed in the hope that it will be useful,
  14 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 //  Lesser General Public License for more details.
  17 //
  18 ///////////////////////////////////////////////////////////////////////////////
  19
  20 // NOTE: If you want to keep the line length in 80 characters, set
  21 //       tab width to 4 or less in your editor when editing this file.
  22
  23
  24 // "Would you love the monster code?
  25 //  Could you understand beauty of the beast?"
  26 //      --Adapted from Lordi's "Would you love a monster man".
  27
  28
  29 #include "lzma_encoder_private.h"
  30
  31
  32 #define length_get_price(length_encoder, symbol, pos_state) \
  33         (length_encoder).prices[pos_state][symbol]
  34
  35
  36 #define get_rep_len_1_price(state, pos_state) \
  37         bit_get_price_0(coder->is_rep0[state]) \
  38                         + bit_get_price_0(coder->is_rep0_long[state][pos_state])
  39
  40
  41 // Adds to price_target.
  42 #define get_pure_rep_price(price_target, rep_index, state, pos_state) \
  43 do { \
  44         if ((rep_index) == 0) { \
  45                 price_target += bit_get_price_0(coder->is_rep0[state]); \
  46                 price_target += bit_get_price_1( \
  47                                 coder->is_rep0_long[state][pos_state]); \
  48         } else { \
  49                 price_target += bit_get_price_1(coder->is_rep0[state]); \
  50                 if ((rep_index) == 1) { \
  51                         price_target += bit_get_price_0(coder->is_rep1[state]); \
  52                 } else { \
  53                         price_target += bit_get_price_1(coder->is_rep1[state]); \
  54                         price_target += bit_get_price( \
  55                                         coder->is_rep2[state], (rep_index) - 2); \
  56                 } \
  57         } \
  58 } while (0)
  59
  60
  61 // Adds to price_target.
  62 #define get_rep_price(price_target, rep_index, len, state, pos_state) \
  63 do { \
  64         get_pure_rep_price(price_target, rep_index, state, pos_state); \
  65         price_target += length_get_price(coder->rep_match_len_encoder, \
  66                         (len) - MATCH_MIN_LEN, pos_state); \
  67 } while (0)
  68
  69
  70 // Adds to price_target.
  71 #define get_pos_len_price(price_target, pos, len, pos_state) \
  72 do { \
  73         const uint32_t len_to_pos_state_tmp = get_len_to_pos_state(len); \
  74         if ((pos) < FULL_DISTANCES) { \
  75                 price_target += distances_prices[len_to_pos_state_tmp][pos]; \
  76         } else { \
  77                 price_target \
  78                                 += pos_slot_prices[len_to_pos_state_tmp][get_pos_slot_2(pos)] \
  79                                 + align_prices[(pos) & ALIGN_MASK]; \
  80         } \
  81         price_target += length_get_price( \
  82                         coder->len_encoder, (len) - MATCH_MIN_LEN, pos_state); \
  83 } while (0)
  84
  85
  86 // Three macros to manipulate lzma_optimal structures:
  87 #define make_as_char(opt) \
  88 do { \
  89         (opt).back_prev = UINT32_MAX; \
  90         (opt).prev_1_is_char = false; \
  91 } while (0)
  92
  93
  94 #define make_as_short_rep(opt) \
  95 do { \
  96         (opt).back_prev = 0; \
  97         (opt).prev_1_is_char = false; \
  98 } while (0)
  99
 100
 101 #define is_short_rep(opt) \
 102         ((opt).back_prev == 0)
 103
 104
 105 static void
 106 fill_distances_prices(lzma_coder *coder)
 107 {
 108         uint32_t temp_prices[FULL_DISTANCES];
 109
 110         for (uint32_t i = START_POS_MODEL_INDEX; i < FULL_DISTANCES; ++i) {
 111                 const uint32_t pos_slot = get_pos_slot(i);
 112                 const uint32_t footer_bits = ((pos_slot >> 1) - 1);
 113                 const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
 114                 temp_prices[i] = 0;
 115                 bittree_reverse_get_price(temp_prices[i],
 116                                 coder->pos_encoders + base - pos_slot - 1,
 117                                 footer_bits, i - base);
 118         }
 119
 120         const uint32_t dist_table_size = coder->dist_table_size;
 121
 122         for (uint32_t len_to_pos_state = 0;
 123                         len_to_pos_state < LEN_TO_POS_STATES;
 124                         ++len_to_pos_state) {
 125
 126                 const probability *encoder = coder->pos_slot_encoder[len_to_pos_state];
 127                 uint32_t *pos_slot_prices = coder->pos_slot_prices[len_to_pos_state];
 128
 129                 for (uint32_t pos_slot = 0;
 130                                 pos_slot < dist_table_size;
 131                                 ++pos_slot) {
 132                         pos_slot_prices[pos_slot] = 0;
 133                         bittree_get_price(pos_slot_prices[pos_slot], encoder,
 134                                         POS_SLOT_BITS, pos_slot);
 135                 }
 136
 137                 for (uint32_t pos_slot = END_POS_MODEL_INDEX;
 138                                 pos_slot < dist_table_size;
 139                                 ++pos_slot)
 140                         pos_slot_prices[pos_slot] += (((pos_slot >> 1) - 1)
 141                                         - ALIGN_BITS) << BIT_PRICE_SHIFT_BITS;
 142
 143
 144                 uint32_t *distances_prices
 145                                 = coder->distances_prices[len_to_pos_state];
 146
 147                 uint32_t i;
 148                 for (i = 0; i < START_POS_MODEL_INDEX; ++i)
 149                         distances_prices[i] = pos_slot_prices[i];
 150
 151                 for (; i < FULL_DISTANCES; ++i)
 152                         distances_prices[i] = pos_slot_prices[get_pos_slot(i)]
 153                                         + temp_prices[i];
 154         }
 155
 156         coder->match_price_count = 0;
 157
 158         return;
 159 }
 160
 161
 162 static void
 163 fill_align_prices(lzma_coder *coder)
 164 {
 165         for (uint32_t i = 0; i < ALIGN_TABLE_SIZE; ++i) {
 166                 uint32_t tmp = 0;
 167                 bittree_reverse_get_price(tmp, coder->pos_align_encoder,
 168                                 ALIGN_BITS, i);
 169                 coder->align_prices[i] = tmp;
 170         }
 171
 172         coder->align_price_count = 0;
 173 }
 174
 175
 176 // The first argument is a pointer returned by literal_get_subcoder().
 177 static uint32_t
 178 literal_get_price(const probability *encoders, const bool match_mode,
 179                 const uint8_t match_byte, const uint8_t symbol)
 180 {
 181         uint32_t price = 0;
 182         uint32_t context = 1;
 183         int i = 8;
 184
 185         if (match_mode) {
 186                 do {
 187                         --i;
 188                         const uint32_t match_bit = (match_byte >> i) & 1;
 189                         const uint32_t bit = (symbol >> i) & 1;
 190                         const uint32_t subcoder_index
 191                                         = 0x100 + (match_bit << 8) + context;
 192
 193                         price += bit_get_price(encoders[subcoder_index], bit);
 194                         context = (context << 1) | bit;
 195
 196                         if (match_bit != bit)
 197                                 break;
 198
 199                 } while (i != 0);
 200         }
 201
 202         while (i != 0) {
 203                 --i;
 204                 const uint32_t bit = (symbol >> i) & 1;
 205                 price += bit_get_price(encoders[context], bit);
 206                 context = (context << 1) | bit;
 207         }
 208
 209         return price;
 210 }
 211
 212
 213 static void
 214 backward(lzma_coder *restrict coder, uint32_t *restrict len_res,
 215                 uint32_t *restrict back_res, uint32_t cur)
 216 {
 217         coder->optimum_end_index = cur;
 218
 219         uint32_t pos_mem = coder->optimum[cur].pos_prev;
 220         uint32_t back_mem = coder->optimum[cur].back_prev;
 221
 222         do {
 223                 if (coder->optimum[cur].prev_1_is_char) {
 224                         make_as_char(coder->optimum[pos_mem]);
 225                         coder->optimum[pos_mem].pos_prev = pos_mem - 1;
 226
 227                         if (coder->optimum[cur].prev_2) {
 228                                 coder->optimum[pos_mem - 1].prev_1_is_char = false;
 229                                 coder->optimum[pos_mem - 1].pos_prev
 230                                                 = coder->optimum[cur].pos_prev_2;
 231                                 coder->optimum[pos_mem - 1].back_prev
 232                                                 = coder->optimum[cur].back_prev_2;
 233                         }
 234                 }
 235
 236                 uint32_t pos_prev = pos_mem;
 237                 uint32_t back_cur = back_mem;
 238
 239                 back_mem = coder->optimum[pos_prev].back_prev;
 240                 pos_mem = coder->optimum[pos_prev].pos_prev;
 241
 242                 coder->optimum[pos_prev].back_prev = back_cur;
 243                 coder->optimum[pos_prev].pos_prev = cur;
 244                 cur = pos_prev;
 245
 246         } while (cur != 0);
 247
 248         coder->optimum_current_index = coder->optimum[0].pos_prev;
 249         *len_res = coder->optimum[0].pos_prev;
 250         *back_res = coder->optimum[0].back_prev;
 251
 252         return;
 253 }
 254
 255
 256 extern void
 257 lzma_get_optimum(lzma_coder *restrict coder,
 258                 uint32_t *restrict back_res, uint32_t *restrict len_res)
 259 {
 260         // Update the price tables. In the C++ LZMA SDK 4.42 this was done in both
 261         // initialization function and in the main loop. In liblzma they were
 262         // moved into this single place.
 263         if (coder->additional_offset == 0) {
 264                 if (coder->match_price_count >= (1 << 7))
 265                         fill_distances_prices(coder);
 266
 267                 if (coder->align_price_count >= ALIGN_TABLE_SIZE)
 268                         fill_align_prices(coder);
 269         }
 270
 271
 272         if (coder->optimum_end_index != coder->optimum_current_index) {
 273                 *len_res = coder->optimum[coder->optimum_current_index].pos_prev
 274                                 - coder->optimum_current_index;
 275                 *back_res = coder->optimum[coder->optimum_current_index].back_prev;
 276                 coder->optimum_current_index = coder->optimum[
 277                                 coder->optimum_current_index].pos_prev;
 278                 return;
 279         }
 280
 281         coder->optimum_current_index = 0;
 282         coder->optimum_end_index = 0;
 283
 284
 285         const uint32_t fast_bytes = coder->fast_bytes;
 286         uint32_t *match_distances = coder->match_distances;
 287
 288         uint32_t len_main;
 289         uint32_t num_distance_pairs;
 290
 291         if (!coder->longest_match_was_found) {
 292                 lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
 293         } else {
 294                 len_main = coder->longest_match_length;
 295                 num_distance_pairs = coder->num_distance_pairs;
 296                 coder->longest_match_was_found = false;
 297         }
 298
 299
 300         const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
 301         uint32_t num_available_bytes
 302                         = coder->lz.write_pos - coder->lz.read_pos + 1;
 303         if (num_available_bytes < 2) {
 304                 *back_res = UINT32_MAX;
 305                 *len_res = 1;
 306                 return;
 307         }
 308
 309         if (num_available_bytes > MATCH_MAX_LEN)
 310                 num_available_bytes = MATCH_MAX_LEN;
 311
 312
 313         uint32_t reps[REP_DISTANCES];
 314         uint32_t rep_lens[REP_DISTANCES];
 315         uint32_t rep_max_index = 0;
 316
 317         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 318                 reps[i] = coder->rep_distances[i];
 319                 const uint32_t back_offset = reps[i] + 1;
 320
 321                 if (buf[0] != *(buf - back_offset)
 322                                 || buf[1] != *(buf + 1 - back_offset)) {
 323                         rep_lens[i] = 0;
 324                         continue;
 325                 }
 326
 327                 uint32_t len_test;
 328                 for (len_test = 2; len_test < num_available_bytes
 329                                 && buf[len_test] == *(buf + len_test - back_offset);
 330                                 ++len_test) ;
 331
 332                 rep_lens[i] = len_test;
 333                 if (len_test > rep_lens[rep_max_index])
 334                         rep_max_index = i;
 335         }
 336
 337         if (rep_lens[rep_max_index] >= fast_bytes) {
 338                 *back_res = rep_max_index;
 339                 *len_res = rep_lens[rep_max_index];
 340                 move_pos(*len_res - 1);
 341                 return;
 342         }
 343
 344
 345         if (len_main >= fast_bytes) {
 346                 *back_res = match_distances[num_distance_pairs] + REP_DISTANCES;
 347                 *len_res = len_main;
 348                 move_pos(len_main - 1);
 349                 return;
 350         }
 351
 352         uint8_t current_byte = *buf;
 353         uint8_t match_byte = *(buf - reps[0] - 1);
 354
 355         if (len_main < 2 && current_byte != match_byte
 356                         && rep_lens[rep_max_index] < 2) {
 357                 *back_res = UINT32_MAX;
 358                 *len_res = 1;
 359                 return;
 360         }
 361
 362         const uint32_t pos_mask = coder->pos_mask;
 363
 364         coder->optimum[0].state = coder->state;
 365
 366         uint32_t position = coder->now_pos;
 367         uint32_t pos_state = (position & pos_mask);
 368
 369         coder->optimum[1].price = bit_get_price_0(
 370                                 coder->is_match[coder->state][pos_state])
 371                         + literal_get_price(
 372                                 literal_get_subcoder(coder->literal_coder,
 373                                         position, coder->previous_byte),
 374                                 !is_char_state(coder->state), match_byte, current_byte);
 375
 376         make_as_char(coder->optimum[1]);
 377
 378         uint32_t match_price
 379                         = bit_get_price_1(coder->is_match[coder->state][pos_state]);
 380         uint32_t rep_match_price
 381                         = match_price + bit_get_price_1(coder->is_rep[coder->state]);
 382
 383
 384         if (match_byte == current_byte) {
 385                 const uint32_t short_rep_price = rep_match_price
 386                                 + get_rep_len_1_price(coder->state, pos_state);
 387
 388                 if (short_rep_price < coder->optimum[1].price) {
 389                         coder->optimum[1].price = short_rep_price;
 390                         make_as_short_rep(coder->optimum[1]);
 391                 }
 392         }
 393
 394         uint32_t len_end = (len_main >= rep_lens[rep_max_index])
 395                         ? len_main
 396                         : rep_lens[rep_max_index];
 397
 398         if (len_end < 2) {
 399                 *back_res = coder->optimum[1].back_prev;
 400                 *len_res = 1;
 401                 return;
 402         }
 403
 404         coder->optimum[1].pos_prev = 0;
 405
 406         for (uint32_t i = 0; i < REP_DISTANCES; ++i)
 407                 coder->optimum[0].backs[i] = reps[i];
 408
 409         uint32_t len = len_end;
 410         do {
 411                 coder->optimum[len].price = INFINITY_PRICE;
 412         } while (--len >= 2);
 413
 414
 415         uint32_t (*distances_prices)[FULL_DISTANCES] = coder->distances_prices;
 416         uint32_t (*pos_slot_prices)[DIST_TABLE_SIZE_MAX] = coder->pos_slot_prices;
 417         uint32_t *align_prices = coder->align_prices;
 418
 419         for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
 420                 uint32_t rep_len = rep_lens[i];
 421                 if (rep_len < 2)
 422                         continue;
 423
 424                 uint32_t price = rep_match_price;
 425                 get_pure_rep_price(price, i, coder->state, pos_state);
 426
 427                 do {
 428                         const uint32_t cur_and_len_price = price
 429                                         + length_get_price(
 430                                         coder->rep_match_len_encoder,
 431                                         rep_len - 2, pos_state);
 432
 433                         if (cur_and_len_price < coder->optimum[rep_len].price) {
 434                                 coder->optimum[rep_len].price = cur_and_len_price;
 435                                 coder->optimum[rep_len].pos_prev = 0;
 436                                 coder->optimum[rep_len].back_prev = i;
 437                                 coder->optimum[rep_len].prev_1_is_char = false;
 438                         }
 439                 } while (--rep_len >= 2);
 440         }
 441
 442
 443         uint32_t normal_match_price = match_price
 444                         + bit_get_price_0(coder->is_rep[coder->state]);
 445
 446         len = (rep_lens[0] >= 2) ? rep_lens[0] + 1 : 2;
 447
 448         if (len <= len_main) {
 449                 uint32_t offs = 0;
 450
 451                 while (len > match_distances[offs + 1])
 452                         offs += 2;
 453
 454                 for(; ; ++len) {
 455                         const uint32_t distance = match_distances[offs + 2];
 456                         uint32_t cur_and_len_price = normal_match_price;
 457                         get_pos_len_price(cur_and_len_price, distance, len, pos_state);
 458
 459                         if (cur_and_len_price < coder->optimum[len].price) {
 460                                 coder->optimum[len].price = cur_and_len_price;
 461                                 coder->optimum[len].pos_prev = 0;
 462                                 coder->optimum[len].back_prev = distance + REP_DISTANCES;
 463                                 coder->optimum[len].prev_1_is_char = false;
 464                         }
 465
 466                         if (len == match_distances[offs + 1]) {
 467                                 offs += 2;
 468                                 if (offs == num_distance_pairs)
 469                                         break;
 470                         }
 471                 }
 472         }
 473
 474
 475         //////////////////
 476         // Big loop ;-) //
 477         //////////////////
 478
 479         uint32_t cur = 0;
 480
 481         // The rest of this function is a huge while-loop. To avoid extreme
 482         // indentation, the indentation level is not increased here.
 483         while (true) {
 484
 485         ++cur;
 486
 487         assert(cur < OPTS);
 488
 489         if (cur == len_end) {
 490                 backward(coder, len_res, back_res, cur);
 491                 return;
 492         }
 493
 494         uint32_t new_len;
 495
 496         lzma_read_match_distances(coder, &new_len, &num_distance_pairs);
 497
 498         if (new_len >= fast_bytes) {
 499                 coder->num_distance_pairs = num_distance_pairs;
 500                 coder->longest_match_length = new_len;
 501                 coder->longest_match_was_found = true;
 502                 backward(coder, len_res, back_res, cur);
 503                 return;
 504         }
 505
 506
 507         ++position;
 508
 509         uint32_t pos_prev = coder->optimum[cur].pos_prev;
 510         uint32_t state;
 511
 512         if (coder->optimum[cur].prev_1_is_char) {
 513                 --pos_prev;
 514
 515                 if (coder->optimum[cur].prev_2) {
 516                         state = coder->optimum[coder->optimum[cur].pos_prev_2].state;
 517
 518                         if (coder->optimum[cur].back_prev_2 < REP_DISTANCES)
 519                                 update_rep(state);
 520                         else
 521                                 update_match(state);
 522
 523                 } else {
 524                         state = coder->optimum[pos_prev].state;
 525                 }
 526
 527                 update_char(state);
 528
 529         } else {
 530                 state = coder->optimum[pos_prev].state;
 531         }
 532
 533         if (pos_prev == cur - 1) {
 534                 if (is_short_rep(coder->optimum[cur]))
 535                         update_short_rep(state);
 536                 else
 537                         update_char(state);
 538         } else {
 539                 uint32_t pos;
 540                 if (coder->optimum[cur].prev_1_is_char && coder->optimum[cur].prev_2) {
 541                         pos_prev = coder->optimum[cur].pos_prev_2;
 542                         pos = coder->optimum[cur].back_prev_2;
 543                         update_rep(state);
 544                 } else {
 545                         pos = coder->optimum[cur].back_prev;
 546                         if (pos < REP_DISTANCES)
 547                                 update_rep(state);
 548                         else
 549                                 update_match(state);
 550                 }
 551
 552                 if (pos < REP_DISTANCES) {
 553                         reps[0] = coder->optimum[pos_prev].backs[pos];
 554
 555                         uint32_t i;
 556                         for (i = 1; i <= pos; ++i)
 557                                 reps[i] = coder->optimum[pos_prev].backs[i - 1];
 558
 559                         for (; i < REP_DISTANCES; ++i)
 560                                 reps[i] = coder->optimum[pos_prev].backs[i];
 561
 562                 } else {
 563                         reps[0] = pos - REP_DISTANCES;
 564
 565                         for (uint32_t i = 1; i < REP_DISTANCES; ++i)
 566                                 reps[i] = coder->optimum[pos_prev].backs[i - 1];
 567                 }
 568         }
 569
 570         coder->optimum[cur].state = state;
 571
 572         for (uint32_t i = 0; i < REP_DISTANCES; ++i)
 573                 coder->optimum[cur].backs[i] = reps[i];
 574
 575         const uint32_t cur_price = coder->optimum[cur].price;
 576
 577         buf = coder->lz.buffer + coder->lz.read_pos - 1;
 578         current_byte = *buf;
 579         match_byte = *(buf - reps[0] - 1);
 580
 581         pos_state = position & pos_mask;
 582
 583         const uint32_t cur_and_1_price = cur_price
 584                         + bit_get_price_0(coder->is_match[state][pos_state])
 585                         + literal_get_price(
 586                                 literal_get_subcoder(coder->literal_coder,
 587                                         position, buf[-1]),
 588                         !is_char_state(state), match_byte, current_byte);
 589
 590         bool next_is_char = false;
 591
 592         if (cur_and_1_price < coder->optimum[cur + 1].price) {
 593                 coder->optimum[cur + 1].price = cur_and_1_price;
 594                 coder->optimum[cur + 1].pos_prev = cur;
 595                 make_as_char(coder->optimum[cur + 1]);
 596                 next_is_char = true;
 597         }
 598
 599         match_price = cur_price
 600                         + bit_get_price_1(coder->is_match[state][pos_state]);
 601         rep_match_price = match_price
 602                         + bit_get_price_1(coder->is_rep[state]);
 603
 604         if (match_byte == current_byte
 605                         && !(coder->optimum[cur + 1].pos_prev < cur
 606                         && coder->optimum[cur + 1].back_prev == 0)) {
 607
 608                 const uint32_t short_rep_price = rep_match_price
 609                                 + get_rep_len_1_price(state, pos_state);
 610
 611                 if (short_rep_price <= coder->optimum[cur + 1].price) {
 612                         coder->optimum[cur + 1].price = short_rep_price;
 613                         coder->optimum[cur + 1].pos_prev = cur;
 614                         make_as_short_rep(coder->optimum[cur + 1]);
 615                         next_is_char = true;
 616                 }
 617         }
 618
 619         uint32_t num_available_bytes_full
 620                         = coder->lz.write_pos - coder->lz.read_pos + 1;
 621         num_available_bytes_full = MIN(OPTS - 1 - cur, num_available_bytes_full);
 622         num_available_bytes = num_available_bytes_full;
 623
 624         if (num_available_bytes < 2)
 625                 continue;
 626
 627         if (num_available_bytes > fast_bytes)
 628                 num_available_bytes = fast_bytes;
 629
 630         if (!next_is_char && match_byte != current_byte) { // speed optimization
 631                 // try literal + rep0
 632                 const uint32_t back_offset = reps[0] + 1;
 633                 const uint32_t limit = MIN(num_available_bytes_full, fast_bytes + 1);
 634
 635                 uint32_t temp;
 636                 for (temp = 1; temp < limit
 637                                 && buf[temp] == *(buf + temp - back_offset);
 638                                 ++temp) ;
 639
 640                 const uint32_t len_test_2 = temp - 1;
 641
 642                 if (len_test_2 >= 2) {
 643                         uint32_t state_2 = state;
 644                         update_char(state_2);
 645
 646                         const uint32_t pos_state_next = (position + 1) & pos_mask;
 647                         const uint32_t next_rep_match_price = cur_and_1_price
 648                                         + bit_get_price_1(coder->is_match[state_2][pos_state_next])
 649                                         + bit_get_price_1(coder->is_rep[state_2]);
 650
 651                         // for (; len_test_2 >= 2; --len_test_2) {
 652                         const uint32_t offset = cur + 1 + len_test_2;
 653
 654                         while (len_end < offset)
 655                                 coder->optimum[++len_end].price = INFINITY_PRICE;
 656
 657                         uint32_t cur_and_len_price = next_rep_match_price;
 658                         get_rep_price(cur_and_len_price,
 659                                         0, len_test_2, state_2, pos_state_next);
 660
 661                         if (cur_and_len_price < coder->optimum[offset].price) {
 662                                 coder->optimum[offset].price = cur_and_len_price;
 663                                 coder->optimum[offset].pos_prev = cur + 1;
 664                                 coder->optimum[offset].back_prev = 0;
 665                                 coder->optimum[offset].prev_1_is_char = true;
 666                                 coder->optimum[offset].prev_2 = false;
 667                         }
 668 //                      }
 669                 }
 670         }
 671
 672
 673         uint32_t start_len = 2; // speed optimization
 674
 675         for (uint32_t rep_index = 0; rep_index < REP_DISTANCES; ++rep_index) {
 676                 const uint32_t back_offset = reps[rep_index] + 1;
 677
 678                 if (buf[0] != *(buf - back_offset) || buf[1] != *(buf + 1 - back_offset))
 679                         continue;
 680
 681                 uint32_t len_test;
 682                 for (len_test = 2; len_test < num_available_bytes
 683                                 && buf[len_test] == *(buf + len_test - back_offset);
 684                                 ++len_test) ;
 685
 686                 while (len_end < cur + len_test)
 687                         coder->optimum[++len_end].price = INFINITY_PRICE;
 688
 689                 const uint32_t len_test_temp = len_test;
 690                 uint32_t price = rep_match_price;
 691                 get_pure_rep_price(price, rep_index, state, pos_state);
 692
 693                 do {
 694                         const uint32_t cur_and_len_price = price
 695                                         + length_get_price(coder->rep_match_len_encoder,
 696                                                         len_test - 2, pos_state);
 697
 698                         if (cur_and_len_price < coder->optimum[cur + len_test].price) {
 699                                 coder->optimum[cur + len_test].price = cur_and_len_price;
 700                                 coder->optimum[cur + len_test].pos_prev = cur;
 701                                 coder->optimum[cur + len_test].back_prev = rep_index;
 702                                 coder->optimum[cur + len_test].prev_1_is_char = false;
 703                         }
 704                 } while (--len_test >= 2);
 705
 706                 len_test = len_test_temp;
 707
 708                 if (rep_index == 0)
 709                         start_len = len_test + 1;
 710
 711
 712                 uint32_t len_test_2 = len_test + 1;
 713                 const uint32_t limit = MIN(num_available_bytes_full,
 714                                 len_test_2 + fast_bytes);
 715                 for (; len_test_2 < limit
 716                                 && buf[len_test_2] == *(buf + len_test_2 - back_offset);
 717                                 ++len_test_2) ;
 718
 719                 len_test_2 -= len_test + 1;
 720
 721                 if (len_test_2 >= 2) {
 722                         uint32_t state_2 = state;
 723                         update_rep(state_2);
 724
 725                         uint32_t pos_state_next = (position + len_test) & pos_mask;
 726
 727                         const uint32_t cur_and_len_char_price = price
 728                                         + length_get_price(coder->rep_match_len_encoder,
 729                                                 len_test - 2, pos_state)
 730                                         + bit_get_price_0(coder->is_match[state_2][pos_state_next])
 731                                         + literal_get_price(
 732                                                 literal_get_subcoder(coder->literal_coder,
 733                                                         position + len_test, buf[len_test - 1]),
 734                                                 true, *(buf + len_test - back_offset), buf[len_test]);
 735
 736                         update_char(state_2);
 737
 738                         pos_state_next = (position + len_test + 1) & pos_mask;
 739
 740                         const uint32_t next_rep_match_price = cur_and_len_char_price
 741                                         + bit_get_price_1(coder->is_match[state_2][pos_state_next])
 742                                         + bit_get_price_1(coder->is_rep[state_2]);
 743
 744 //                      for(; len_test_2 >= 2; len_test_2--) {
 745                         const uint32_t offset = cur + len_test + 1 + len_test_2;
 746
 747                         while (len_end < offset)
 748                                 coder->optimum[++len_end].price = INFINITY_PRICE;
 749
 750                         uint32_t cur_and_len_price = next_rep_match_price;
 751                         get_rep_price(cur_and_len_price,
 752                                         0, len_test_2, state_2, pos_state_next);
 753
 754                         if (cur_and_len_price < coder->optimum[offset].price) {
 755                                 coder->optimum[offset].price = cur_and_len_price;
 756                                 coder->optimum[offset].pos_prev = cur + len_test + 1;
 757                                 coder->optimum[offset].back_prev = 0;
 758                                 coder->optimum[offset].prev_1_is_char = true;
 759                                 coder->optimum[offset].prev_2 = true;
 760                                 coder->optimum[offset].pos_prev_2 = cur;
 761                                 coder->optimum[offset].back_prev_2 = rep_index;
 762                         }
 763 //                      }
 764                 }
 765         }
 766
 767
 768 //      for (uint32_t len_test = 2; len_test <= new_len; ++len_test)
 769         if (new_len > num_available_bytes) {
 770                 new_len = num_available_bytes;
 771
 772                 for (num_distance_pairs = 0;
 773                                 new_len > match_distances[num_distance_pairs + 1];
 774                                 num_distance_pairs += 2) ;
 775
 776                 match_distances[num_distance_pairs + 1] = new_len;
 777                 num_distance_pairs += 2;
 778         }
 779
 780
 781         if (new_len >= start_len) {
 782                 normal_match_price = match_price
 783                                 + bit_get_price_0(coder->is_rep[state]);
 784
 785                 while (len_end < cur + new_len)
 786                         coder->optimum[++len_end].price = INFINITY_PRICE;
 787
 788                 uint32_t offs = 0;
 789                 while (start_len > match_distances[offs + 1])
 790                         offs += 2;
 791
 792                 uint32_t cur_back = match_distances[offs + 2];
 793                 uint32_t pos_slot = get_pos_slot_2(cur_back);
 794
 795                 for (uint32_t len_test = start_len; ; ++len_test) {
 796                         uint32_t cur_and_len_price = normal_match_price;
 797                         const uint32_t len_to_pos_state = get_len_to_pos_state(len_test);
 798
 799                         if (cur_back < FULL_DISTANCES)
 800                                 cur_and_len_price += distances_prices[
 801                                                 len_to_pos_state][cur_back];
 802                         else
 803                                 cur_and_len_price += pos_slot_prices[
 804                                                 len_to_pos_state][pos_slot]
 805                                                 + align_prices[cur_back & ALIGN_MASK];
 806
 807                         cur_and_len_price += length_get_price(coder->len_encoder,
 808                                         len_test - MATCH_MIN_LEN, pos_state);
 809
 810                         if (cur_and_len_price < coder->optimum[cur + len_test].price) {
 811                                 coder->optimum[cur + len_test].price = cur_and_len_price;
 812                                 coder->optimum[cur + len_test].pos_prev = cur;
 813                                 coder->optimum[cur + len_test].back_prev
 814                                                 = cur_back + REP_DISTANCES;
 815                                 coder->optimum[cur + len_test].prev_1_is_char = false;
 816                         }
 817
 818                         if (len_test == match_distances[offs + 1]) {
 819                                 // Try Match + Literal + Rep0
 820                                 const uint32_t back_offset = cur_back + 1;
 821                                 uint32_t len_test_2 = len_test + 1;
 822                                 const uint32_t limit = MIN(num_available_bytes_full,
 823                                                 len_test_2 + fast_bytes);
 824
 825                                 for (; len_test_2 < limit &&
 826                                                 buf[len_test_2] == *(buf + len_test_2 - back_offset);
 827                                                 ++len_test_2) ;
 828
 829                                 len_test_2 -= len_test + 1;
 830
 831                                 if (len_test_2 >= 2) {
 832                                         uint32_t state_2 = state;
 833                                         update_match(state_2);
 834                                         uint32_t pos_state_next
 835                                                         = (position + len_test) & pos_mask;
 836
 837                                         const uint32_t cur_and_len_char_price = cur_and_len_price
 838                                                         + bit_get_price_0(
 839                                                                 coder->is_match[state_2][pos_state_next])
 840                                                         + literal_get_price(
 841                                                                 literal_get_subcoder(
 842                                                                         coder->literal_coder,
 843                                                                         position + len_test,
 844                                                                         buf[len_test - 1]),
 845                                                                 true,
 846                                                                 *(buf + len_test - back_offset),
 847                                                                 buf[len_test]);
 848
 849                                         update_char(state_2);
 850                                         pos_state_next = (pos_state_next + 1) & pos_mask;
 851
 852                                         const uint32_t next_rep_match_price
 853                                                         = cur_and_len_char_price
 854                                                         + bit_get_price_1(
 855                                                                 coder->is_match[state_2][pos_state_next])
 856                                                         + bit_get_price_1(coder->is_rep[state_2]);
 857
 858                                         // for(; len_test_2 >= 2; --len_test_2) {
 859                                         const uint32_t offset = cur + len_test + 1 + len_test_2;
 860
 861                                         while (len_end < offset)
 862                                                 coder->optimum[++len_end].price = INFINITY_PRICE;
 863
 864                                         cur_and_len_price = next_rep_match_price;
 865                                         get_rep_price(cur_and_len_price,
 866                                                         0, len_test_2, state_2, pos_state_next);
 867
 868                                         if (cur_and_len_price < coder->optimum[offset].price) {
 869                                                 coder->optimum[offset].price = cur_and_len_price;
 870                                                 coder->optimum[offset].pos_prev = cur + len_test + 1;
 871                                                 coder->optimum[offset].back_prev = 0;
 872                                                 coder->optimum[offset].prev_1_is_char = true;
 873                                                 coder->optimum[offset].prev_2 = true;
 874                                                 coder->optimum[offset].pos_prev_2 = cur;
 875                                                 coder->optimum[offset].back_prev_2
 876                                                                 = cur_back + REP_DISTANCES;
 877                                         }
 878 //                                      }
 879                                 }
 880
 881                                 offs += 2;
 882                                 if (offs == num_distance_pairs)
 883                                         break;
 884
 885                                 cur_back = match_distances[offs + 2];
 886                                 if (cur_back >= FULL_DISTANCES)
 887                                         pos_slot = get_pos_slot_2(cur_back);
 888                         }
 889                 }
 890         }
 891
 892         } // Closes: while (true)
 893 }