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