OLD | NEW |
(Empty) | |
| 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 optimizat
ion |
| 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].pric
e) { |
| 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_inde
x; |
| 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 + le
n_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_litera
l_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].pric
e) { |
| 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(code
r, |
| 765 position + len_t
est, |
| 766 buf[len_test - 1
], |
| 767 true, |
| 768 buf_back[len_tes
t], |
| 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_pr
ice |
| 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 = R
C_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_sta
te_next); |
| 789 |
| 790 if (cur_and_len_price < coder->opts[offs
et].price) { |
| 791 coder->opts[offset].price = cur_
and_len_price; |
| 792 coder->opts[offset].pos_prev = c
ur + len_test + 1; |
| 793 coder->opts[offset].back_prev =
0; |
| 794 coder->opts[offset].prev_1_is_li
teral = true; |
| 795 coder->opts[offset].prev_2 = tru
e; |
| 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 } |
OLD | NEW |