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