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