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