1 // SPDX-License-Identifier: 0BSD 2 3 /////////////////////////////////////////////////////////////////////////////// 4 // 5 /// \file lz_encoder_mf.c 6 /// \brief Match finders 7 /// 8 // Authors: Igor Pavlov 9 // Lasse Collin 10 // 11 /////////////////////////////////////////////////////////////////////////////// 12 13 #include "lz_encoder.h" 14 #include "lz_encoder_hash.h" 15 #include "memcmplen.h" 16 17 18 /// \brief Find matches starting from the current byte 19 /// 20 /// \return The length of the longest match found 21 extern uint32_t 22 lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches) 23 { 24 // Call the match finder. It returns the number of length-distance 25 // pairs found. 26 // FIXME: Minimum count is zero, what _exactly_ is the maximum? 27 const uint32_t count = mf->find(mf, matches); 28 29 // Length of the longest match; assume that no matches were found 30 // and thus the maximum length is zero. 31 uint32_t len_best = 0; 32 33 if (count > 0) { 34 #ifndef NDEBUG 35 // Validate the matches. 36 for (uint32_t i = 0; i < count; ++i) { 37 assert(matches[i].len <= mf->nice_len); 38 assert(matches[i].dist < mf->read_pos); 39 assert(memcmp(mf_ptr(mf) - 1, 40 mf_ptr(mf) - matches[i].dist - 2, 41 matches[i].len) == 0); 42 } 43 #endif 44 45 // The last used element in the array contains 46 // the longest match. 47 len_best = matches[count - 1].len; 48 49 // If a match of maximum search length was found, try to 50 // extend the match to maximum possible length. 51 if (len_best == mf->nice_len) { 52 // The limit for the match length is either the 53 // maximum match length supported by the LZ-based 54 // encoder or the number of bytes left in the 55 // dictionary, whichever is smaller. 56 uint32_t limit = mf_avail(mf) + 1; 57 if (limit > mf->match_len_max) 58 limit = mf->match_len_max; 59 60 // Pointer to the byte we just ran through 61 // the match finder. 62 const uint8_t *p1 = mf_ptr(mf) - 1; 63 64 // Pointer to the beginning of the match. We need -1 65 // here because the match distances are zero based. 66 const uint8_t *p2 = p1 - matches[count - 1].dist - 1; 67 68 len_best = lzma_memcmplen(p1, p2, len_best, limit); 69 } 70 } 71 72 *count_ptr = count; 73 74 // Finally update the read position to indicate that match finder was 75 // run for this dictionary offset. 76 ++mf->read_ahead; 77 78 return len_best; 79 } 80 81 82 /// Hash value to indicate unused element in the hash. Since we start the 83 /// positions from dict_size + 1, zero is always too far to qualify 84 /// as usable match position. 85 #define EMPTY_HASH_VALUE 0 86 87 88 /// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos 89 /// reaches MUST_NORMALIZE_POS. 90 #define MUST_NORMALIZE_POS UINT32_MAX 91 92 93 /// \brief Normalizes hash values 94 /// 95 /// The hash arrays store positions of match candidates. The positions are 96 /// relative to an arbitrary offset that is not the same as the absolute 97 /// offset in the input stream. The relative position of the current byte 98 /// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are 99 /// the differences of the current read position and the position found from 100 /// the hash. 101 /// 102 /// To prevent integer overflows of the offsets stored in the hash arrays, 103 /// we need to "normalize" the stored values now and then. During the 104 /// normalization, we drop values that indicate distance greater than the 105 /// dictionary size, thus making space for new values. 106 static void 107 normalize(lzma_mf *mf) 108 { 109 assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS); 110 111 // In future we may not want to touch the lowest bits, because there 112 // may be match finders that use larger resolution than one byte. 113 const uint32_t subvalue 114 = (MUST_NORMALIZE_POS - mf->cyclic_size); 115 // & ~((UINT32_C(1) << 10) - 1); 116 117 for (uint32_t i = 0; i < mf->hash_count; ++i) { 118 // If the distance is greater than the dictionary size, 119 // we can simply mark the hash element as empty. 120 if (mf->hash[i] <= subvalue) 121 mf->hash[i] = EMPTY_HASH_VALUE; 122 else 123 mf->hash[i] -= subvalue; 124 } 125 126 for (uint32_t i = 0; i < mf->sons_count; ++i) { 127 // Do the same for mf->son. 128 // 129 // NOTE: There may be uninitialized elements in mf->son. 130 // Valgrind may complain that the "if" below depends on 131 // an uninitialized value. In this case it is safe to ignore 132 // the warning. See also the comments in lz_encoder_init() 133 // in lz_encoder.c. 134 if (mf->son[i] <= subvalue) 135 mf->son[i] = EMPTY_HASH_VALUE; 136 else 137 mf->son[i] -= subvalue; 138 } 139 140 // Update offset to match the new locations. 141 mf->offset -= subvalue; 142 143 return; 144 } 145 146 147 /// Mark the current byte as processed from point of view of the match finder. 148 static void 149 move_pos(lzma_mf *mf) 150 { 151 if (++mf->cyclic_pos == mf->cyclic_size) 152 mf->cyclic_pos = 0; 153 154 ++mf->read_pos; 155 assert(mf->read_pos <= mf->write_pos); 156 157 if (unlikely(mf->read_pos + mf->offset == UINT32_MAX)) 158 normalize(mf); 159 } 160 161 162 /// When flushing, we cannot run the match finder unless there is nice_len 163 /// bytes available in the dictionary. Instead, we skip running the match 164 /// finder (indicating that no match was found), and count how many bytes we 165 /// have ignored this way. 166 /// 167 /// When new data is given after the flushing was completed, the match finder 168 /// is restarted by rewinding mf->read_pos backwards by mf->pending. Then 169 /// the missed bytes are added to the hash using the match finder's skip 170 /// function (with small amount of input, it may start using mf->pending 171 /// again if flushing). 172 /// 173 /// Due to this rewinding, we don't touch cyclic_pos or test for 174 /// normalization. It will be done when the match finder's skip function 175 /// catches up after a flush. 176 static void 177 move_pending(lzma_mf *mf) 178 { 179 ++mf->read_pos; 180 assert(mf->read_pos <= mf->write_pos); 181 ++mf->pending; 182 } 183 184 185 /// Calculate len_limit and determine if there is enough input to run 186 /// the actual match finder code. Sets up "cur" and "pos". This macro 187 /// is used by all find functions and binary tree skip functions. Hash 188 /// chain skip function doesn't need len_limit so a simpler code is used 189 /// in them. 190 #define header(is_bt, len_min, ret_op) \ 191 uint32_t len_limit = mf_avail(mf); \ 192 if (mf->nice_len <= len_limit) { \ 193 len_limit = mf->nice_len; \ 194 } else if (len_limit < (len_min) \ 195 || (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \ 196 assert(mf->action != LZMA_RUN); \ 197 move_pending(mf); \ 198 ret_op; \ 199 } \ 200 const uint8_t *cur = mf_ptr(mf); \ 201 const uint32_t pos = mf->read_pos + mf->offset 202 203 204 /// Header for find functions. "return 0" indicates that zero matches 205 /// were found. 206 #define header_find(is_bt, len_min) \ 207 header(is_bt, len_min, return 0); \ 208 uint32_t matches_count = 0 209 210 211 /// Header for a loop in a skip function. "continue" tells to skip the rest 212 /// of the code in the loop. 213 #define header_skip(is_bt, len_min) \ 214 header(is_bt, len_min, continue) 215 216 217 /// Calls hc_find_func() or bt_find_func() and calculates the total number 218 /// of matches found. Updates the dictionary position and returns the number 219 /// of matches found. 220 #define call_find(func, len_best) \ 221 do { \ 222 matches_count = (uint32_t)(func(len_limit, pos, cur, cur_match, \ 223 mf->depth, mf->son, \ 224 mf->cyclic_pos, mf->cyclic_size, \ 225 matches + matches_count, len_best) \ 226 - matches); \ 227 move_pos(mf); \ 228 return matches_count; \ 229 } while (0) 230 231 232 //////////////// 233 // Hash Chain // 234 //////////////// 235 236 #if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4) 237 /// 238 /// 239 /// \param len_limit Don't look for matches longer than len_limit. 240 /// \param pos lzma_mf.read_pos + lzma_mf.offset 241 /// \param cur Pointer to current byte (mf_ptr(mf)) 242 /// \param cur_match Start position of the current match candidate 243 /// \param depth Maximum length of the hash chain 244 /// \param son lzma_mf.son (contains the hash chain) 245 /// \param cyclic_pos lzma_mf.cyclic_pos 246 /// \param cyclic_size lzma_mf_cyclic_size 247 /// \param matches Array to hold the matches. 248 /// \param len_best The length of the longest match found so far. 249 static lzma_match * 250 hc_find_func( 251 const uint32_t len_limit, 252 const uint32_t pos, 253 const uint8_t *const cur, 254 uint32_t cur_match, 255 uint32_t depth, 256 uint32_t *const son, 257 const uint32_t cyclic_pos, 258 const uint32_t cyclic_size, 259 lzma_match *matches, 260 uint32_t len_best) 261 { 262 son[cyclic_pos] = cur_match; 263 264 while (true) { 265 const uint32_t delta = pos - cur_match; 266 if (depth-- == 0 || delta >= cyclic_size) 267 return matches; 268 269 const uint8_t *const pb = cur - delta; 270 cur_match = son[cyclic_pos - delta 271 + (delta > cyclic_pos ? cyclic_size : 0)]; 272 273 if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) { 274 uint32_t len = lzma_memcmplen(pb, cur, 1, len_limit); 275 276 if (len_best < len) { 277 len_best = len; 278 matches->len = len; 279 matches->dist = delta - 1; 280 ++matches; 281 282 if (len == len_limit) 283 return matches; 284 } 285 } 286 } 287 } 288 289 290 #define hc_find(len_best) \ 291 call_find(hc_find_func, len_best) 292 293 294 #define hc_skip() \ 295 do { \ 296 mf->son[mf->cyclic_pos] = cur_match; \ 297 move_pos(mf); \ 298 } while (0) 299 300 #endif 301 302 303 #ifdef HAVE_MF_HC3 304 extern uint32_t 305 lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches) 306 { 307 header_find(false, 3); 308 309 hash_3_calc(); 310 311 const uint32_t delta2 = pos - mf->hash[hash_2_value]; 312 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value]; 313 314 mf->hash[hash_2_value] = pos; 315 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 316 317 uint32_t len_best = 2; 318 319 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 320 len_best = lzma_memcmplen(cur - delta2, cur, 321 len_best, len_limit); 322 323 matches[0].len = len_best; 324 matches[0].dist = delta2 - 1; 325 matches_count = 1; 326 327 if (len_best == len_limit) { 328 hc_skip(); 329 return 1; // matches_count 330 } 331 } 332 333 hc_find(len_best); 334 } 335 336 337 extern void 338 lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount) 339 { 340 do { 341 if (mf_avail(mf) < 3) { 342 move_pending(mf); 343 continue; 344 } 345 346 const uint8_t *cur = mf_ptr(mf); 347 const uint32_t pos = mf->read_pos + mf->offset; 348 349 hash_3_calc(); 350 351 const uint32_t cur_match 352 = mf->hash[FIX_3_HASH_SIZE + hash_value]; 353 354 mf->hash[hash_2_value] = pos; 355 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 356 357 hc_skip(); 358 359 } while (--amount != 0); 360 } 361 #endif 362 363 364 #ifdef HAVE_MF_HC4 365 extern uint32_t 366 lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches) 367 { 368 header_find(false, 4); 369 370 hash_4_calc(); 371 372 uint32_t delta2 = pos - mf->hash[hash_2_value]; 373 const uint32_t delta3 374 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value]; 375 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value]; 376 377 mf->hash[hash_2_value ] = pos; 378 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 379 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 380 381 uint32_t len_best = 1; 382 383 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 384 len_best = 2; 385 matches[0].len = 2; 386 matches[0].dist = delta2 - 1; 387 matches_count = 1; 388 } 389 390 if (delta2 != delta3 && delta3 < mf->cyclic_size 391 && *(cur - delta3) == *cur) { 392 len_best = 3; 393 matches[matches_count++].dist = delta3 - 1; 394 delta2 = delta3; 395 } 396 397 if (matches_count != 0) { 398 len_best = lzma_memcmplen(cur - delta2, cur, 399 len_best, len_limit); 400 401 matches[matches_count - 1].len = len_best; 402 403 if (len_best == len_limit) { 404 hc_skip(); 405 return matches_count; 406 } 407 } 408 409 if (len_best < 3) 410 len_best = 3; 411 412 hc_find(len_best); 413 } 414 415 416 extern void 417 lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount) 418 { 419 do { 420 if (mf_avail(mf) < 4) { 421 move_pending(mf); 422 continue; 423 } 424 425 const uint8_t *cur = mf_ptr(mf); 426 const uint32_t pos = mf->read_pos + mf->offset; 427 428 hash_4_calc(); 429 430 const uint32_t cur_match 431 = mf->hash[FIX_4_HASH_SIZE + hash_value]; 432 433 mf->hash[hash_2_value] = pos; 434 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 435 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 436 437 hc_skip(); 438 439 } while (--amount != 0); 440 } 441 #endif 442 443 444 ///////////////// 445 // Binary Tree // 446 ///////////////// 447 448 #if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4) 449 static lzma_match * 450 bt_find_func( 451 const uint32_t len_limit, 452 const uint32_t pos, 453 const uint8_t *const cur, 454 uint32_t cur_match, 455 uint32_t depth, 456 uint32_t *const son, 457 const uint32_t cyclic_pos, 458 const uint32_t cyclic_size, 459 lzma_match *matches, 460 uint32_t len_best) 461 { 462 uint32_t *ptr0 = son + (cyclic_pos << 1) + 1; 463 uint32_t *ptr1 = son + (cyclic_pos << 1); 464 465 uint32_t len0 = 0; 466 uint32_t len1 = 0; 467 468 while (true) { 469 const uint32_t delta = pos - cur_match; 470 if (depth-- == 0 || delta >= cyclic_size) { 471 *ptr0 = EMPTY_HASH_VALUE; 472 *ptr1 = EMPTY_HASH_VALUE; 473 return matches; 474 } 475 476 uint32_t *const pair = son + ((cyclic_pos - delta 477 + (delta > cyclic_pos ? cyclic_size : 0)) 478 << 1); 479 480 const uint8_t *const pb = cur - delta; 481 uint32_t len = my_min(len0, len1); 482 483 if (pb[len] == cur[len]) { 484 len = lzma_memcmplen(pb, cur, len + 1, len_limit); 485 486 if (len_best < len) { 487 len_best = len; 488 matches->len = len; 489 matches->dist = delta - 1; 490 ++matches; 491 492 if (len == len_limit) { 493 *ptr1 = pair[0]; 494 *ptr0 = pair[1]; 495 return matches; 496 } 497 } 498 } 499 500 if (pb[len] < cur[len]) { 501 *ptr1 = cur_match; 502 ptr1 = pair + 1; 503 cur_match = *ptr1; 504 len1 = len; 505 } else { 506 *ptr0 = cur_match; 507 ptr0 = pair; 508 cur_match = *ptr0; 509 len0 = len; 510 } 511 } 512 } 513 514 515 static void 516 bt_skip_func( 517 const uint32_t len_limit, 518 const uint32_t pos, 519 const uint8_t *const cur, 520 uint32_t cur_match, 521 uint32_t depth, 522 uint32_t *const son, 523 const uint32_t cyclic_pos, 524 const uint32_t cyclic_size) 525 { 526 uint32_t *ptr0 = son + (cyclic_pos << 1) + 1; 527 uint32_t *ptr1 = son + (cyclic_pos << 1); 528 529 uint32_t len0 = 0; 530 uint32_t len1 = 0; 531 532 while (true) { 533 const uint32_t delta = pos - cur_match; 534 if (depth-- == 0 || delta >= cyclic_size) { 535 *ptr0 = EMPTY_HASH_VALUE; 536 *ptr1 = EMPTY_HASH_VALUE; 537 return; 538 } 539 540 uint32_t *pair = son + ((cyclic_pos - delta 541 + (delta > cyclic_pos ? cyclic_size : 0)) 542 << 1); 543 const uint8_t *pb = cur - delta; 544 uint32_t len = my_min(len0, len1); 545 546 if (pb[len] == cur[len]) { 547 len = lzma_memcmplen(pb, cur, len + 1, len_limit); 548 549 if (len == len_limit) { 550 *ptr1 = pair[0]; 551 *ptr0 = pair[1]; 552 return; 553 } 554 } 555 556 if (pb[len] < cur[len]) { 557 *ptr1 = cur_match; 558 ptr1 = pair + 1; 559 cur_match = *ptr1; 560 len1 = len; 561 } else { 562 *ptr0 = cur_match; 563 ptr0 = pair; 564 cur_match = *ptr0; 565 len0 = len; 566 } 567 } 568 } 569 570 571 #define bt_find(len_best) \ 572 call_find(bt_find_func, len_best) 573 574 #define bt_skip() \ 575 do { \ 576 bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \ 577 mf->son, mf->cyclic_pos, \ 578 mf->cyclic_size); \ 579 move_pos(mf); \ 580 } while (0) 581 582 #endif 583 584 585 #ifdef HAVE_MF_BT2 586 extern uint32_t 587 lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches) 588 { 589 header_find(true, 2); 590 591 hash_2_calc(); 592 593 const uint32_t cur_match = mf->hash[hash_value]; 594 mf->hash[hash_value] = pos; 595 596 bt_find(1); 597 } 598 599 600 extern void 601 lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount) 602 { 603 do { 604 header_skip(true, 2); 605 606 hash_2_calc(); 607 608 const uint32_t cur_match = mf->hash[hash_value]; 609 mf->hash[hash_value] = pos; 610 611 bt_skip(); 612 613 } while (--amount != 0); 614 } 615 #endif 616 617 618 #ifdef HAVE_MF_BT3 619 extern uint32_t 620 lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches) 621 { 622 header_find(true, 3); 623 624 hash_3_calc(); 625 626 const uint32_t delta2 = pos - mf->hash[hash_2_value]; 627 const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value]; 628 629 mf->hash[hash_2_value] = pos; 630 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 631 632 uint32_t len_best = 2; 633 634 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 635 len_best = lzma_memcmplen( 636 cur, cur - delta2, len_best, len_limit); 637 638 matches[0].len = len_best; 639 matches[0].dist = delta2 - 1; 640 matches_count = 1; 641 642 if (len_best == len_limit) { 643 bt_skip(); 644 return 1; // matches_count 645 } 646 } 647 648 bt_find(len_best); 649 } 650 651 652 extern void 653 lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount) 654 { 655 do { 656 header_skip(true, 3); 657 658 hash_3_calc(); 659 660 const uint32_t cur_match 661 = mf->hash[FIX_3_HASH_SIZE + hash_value]; 662 663 mf->hash[hash_2_value] = pos; 664 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 665 666 bt_skip(); 667 668 } while (--amount != 0); 669 } 670 #endif 671 672 673 #ifdef HAVE_MF_BT4 674 extern uint32_t 675 lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches) 676 { 677 header_find(true, 4); 678 679 hash_4_calc(); 680 681 uint32_t delta2 = pos - mf->hash[hash_2_value]; 682 const uint32_t delta3 683 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value]; 684 const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value]; 685 686 mf->hash[hash_2_value] = pos; 687 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 688 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 689 690 uint32_t len_best = 1; 691 692 if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 693 len_best = 2; 694 matches[0].len = 2; 695 matches[0].dist = delta2 - 1; 696 matches_count = 1; 697 } 698 699 if (delta2 != delta3 && delta3 < mf->cyclic_size 700 && *(cur - delta3) == *cur) { 701 len_best = 3; 702 matches[matches_count++].dist = delta3 - 1; 703 delta2 = delta3; 704 } 705 706 if (matches_count != 0) { 707 len_best = lzma_memcmplen( 708 cur, cur - delta2, len_best, len_limit); 709 710 matches[matches_count - 1].len = len_best; 711 712 if (len_best == len_limit) { 713 bt_skip(); 714 return matches_count; 715 } 716 } 717 718 if (len_best < 3) 719 len_best = 3; 720 721 bt_find(len_best); 722 } 723 724 725 extern void 726 lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount) 727 { 728 do { 729 header_skip(true, 4); 730 731 hash_4_calc(); 732 733 const uint32_t cur_match 734 = mf->hash[FIX_4_HASH_SIZE + hash_value]; 735 736 mf->hash[hash_2_value] = pos; 737 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 738 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 739 740 bt_skip(); 741 742 } while (--amount != 0); 743 } 744 #endif 745