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