src/liblzma/lz/lz_encoder_mf.c

   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