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         uint32_t i;
 122
 123         for (i = 0; i < count; ++i) {
 124                 // If the distance is greater than the dictionary size,
 125                 // we can simply mark the hash element as empty.
 126                 //
 127                 // NOTE: Only the first mf->hash_size_sum elements are
 128                 // initialized for sure. There may be uninitialized elements
 129                 // in mf->son. Since we go through both mf->hash and
 130                 // mf->son here in normalization, Valgrind may complain
 131                 // that the "if" below depends on uninitialized value. In
 132                 // this case it is safe to ignore the warning. See also the
 133                 // comments in lz_encoder_init() in lz_encoder.c.
 134                 if (hash[i] <= subvalue)
 135                         hash[i] = EMPTY_HASH_VALUE;
 136                 else
 137                         hash[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 = func(len_limit, pos, cur, cur_match, mf->depth, \
 223                                 mf->son, mf->cyclic_pos, mf->cyclic_size, \
 224                                 matches + matches_count, len_best) \
 225                         - matches; \
 226         move_pos(mf); \
 227         return matches_count; \
 228 } while (0)
 229
 230
 231 ////////////////
 232 // Hash Chain //
 233 ////////////////
 234
 235 #if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
 236 ///
 237 ///
 238 /// \param      len_limit       Don't look for matches longer than len_limit.
 239 /// \param      pos             lzma_mf.read_pos + lzma_mf.offset
 240 /// \param      cur             Pointer to current byte (mf_ptr(mf))
 241 /// \param      cur_match       Start position of the current match candidate
 242 /// \param      depth           Maximum length of the hash chain
 243 /// \param      son             lzma_mf.son (contains the hash chain)
 244 /// \param      cyclic_pos
 245 /// \param      cyclic_size
 246 /// \param      matches         Array to hold the matches.
 247 /// \param      len_best        The length of the longest match found so far.
 248 static lzma_match *
 249 hc_find_func(
 250                 const uint32_t len_limit,
 251                 const uint32_t pos,
 252                 const uint8_t *const cur,
 253                 uint32_t cur_match,
 254                 uint32_t depth,
 255                 uint32_t *const son,
 256                 const uint32_t cyclic_pos,
 257                 const uint32_t cyclic_size,
 258                 lzma_match *matches,
 259                 uint32_t len_best)
 260 {
 261         son[cyclic_pos] = cur_match;
 262
 263         while (true) {
 264                 const uint32_t delta = pos - cur_match;
 265                 if (depth-- == 0 || delta >= cyclic_size)
 266                         return matches;
 267
 268                 const uint8_t *const pb = cur - delta;
 269                 cur_match = son[cyclic_pos - delta
 270                                 + (delta > cyclic_pos ? cyclic_size : 0)];
 271
 272                 if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) {
 273                         uint32_t len = 0;
 274                         while (++len != len_limit)
 275                                 if (pb[len] != cur[len])
 276                                         break;
 277
 278                         if (len_best < len) {
 279                                 len_best = len;
 280                                 matches->len = len;
 281                                 matches->dist = delta - 1;
 282                                 ++matches;
 283
 284                                 if (len == len_limit)
 285                                         return matches;
 286                         }
 287                 }
 288         }
 289 }
 290
 291
 292 #define hc_find(len_best) \
 293         call_find(hc_find_func, len_best)
 294
 295
 296 #define hc_skip() \
 297 do { \
 298         mf->son[mf->cyclic_pos] = cur_match; \
 299         move_pos(mf); \
 300 } while (0)
 301
 302 #endif
 303
 304
 305 #ifdef HAVE_MF_HC3
 306 extern uint32_t
 307 lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches)
 308 {
 309         header_find(false, 3);
 310
 311         hash_3_calc();
 312
 313         const uint32_t delta2 = pos - mf->hash[hash_2_value];
 314         const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
 315
 316         mf->hash[hash_2_value] = pos;
 317         mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
 318
 319         uint32_t len_best = 2;
 320
 321         if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
 322                 for ( ; len_best != len_limit; ++len_best)
 323                         if (*(cur + len_best - delta2) != cur[len_best])
 324                                 break;
 325
 326                 matches[0].len = len_best;
 327                 matches[0].dist = delta2 - 1;
 328                 matches_count = 1;
 329
 330                 if (len_best == len_limit) {
 331                         hc_skip();
 332                         return 1; // matches_count
 333                 }
 334         }
 335
 336         hc_find(len_best);
 337 }
 338
 339
 340 extern void
 341 lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount)
 342 {
 343         do {
 344                 if (mf_avail(mf) < 3) {
 345                         move_pending(mf);
 346                         continue;
 347                 }
 348
 349                 const uint8_t *cur = mf_ptr(mf);
 350                 const uint32_t pos = mf->read_pos + mf->offset;
 351
 352                 hash_3_calc();
 353
 354                 const uint32_t cur_match
 355                                 = mf->hash[FIX_3_HASH_SIZE + hash_value];
 356
 357                 mf->hash[hash_2_value] = pos;
 358                 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
 359
 360                 hc_skip();
 361
 362         } while (--amount != 0);
 363 }
 364 #endif
 365
 366
 367 #ifdef HAVE_MF_HC4
 368 extern uint32_t
 369 lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches)
 370 {
 371         header_find(false, 4);
 372
 373         hash_4_calc();
 374
 375         uint32_t delta2 = pos - mf->hash[hash_2_value];
 376         const uint32_t delta3
 377                         = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
 378         const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
 379
 380         mf->hash[hash_2_value ] = pos;
 381         mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
 382         mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
 383
 384         uint32_t len_best = 1;
 385
 386         if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
 387                 len_best = 2;
 388                 matches[0].len = 2;
 389                 matches[0].dist = delta2 - 1;
 390                 matches_count = 1;
 391         }
 392
 393         if (delta2 != delta3 && delta3 < mf->cyclic_size
 394                         && *(cur - delta3) == *cur) {
 395                 len_best = 3;
 396                 matches[matches_count++].dist = delta3 - 1;
 397                 delta2 = delta3;
 398         }
 399
 400         if (matches_count != 0) {
 401                 for ( ; len_best != len_limit; ++len_best)
 402                         if (*(cur + len_best - delta2) != cur[len_best])
 403                                 break;
 404
 405                 matches[matches_count - 1].len = len_best;
 406
 407                 if (len_best == len_limit) {
 408                         hc_skip();
 409                         return matches_count;
 410                 }
 411         }
 412
 413         if (len_best < 3)
 414                 len_best = 3;
 415
 416         hc_find(len_best);
 417 }
 418
 419
 420 extern void
 421 lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount)
 422 {
 423         do {
 424                 if (mf_avail(mf) < 4) {
 425                         move_pending(mf);
 426                         continue;
 427                 }
 428
 429                 const uint8_t *cur = mf_ptr(mf);
 430                 const uint32_t pos = mf->read_pos + mf->offset;
 431
 432                 hash_4_calc();
 433
 434                 const uint32_t cur_match
 435                                 = mf->hash[FIX_4_HASH_SIZE + hash_value];
 436
 437                 mf->hash[hash_2_value] = pos;
 438                 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
 439                 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
 440
 441                 hc_skip();
 442
 443         } while (--amount != 0);
 444 }
 445 #endif
 446
 447
 448 /////////////////
 449 // Binary Tree //
 450 /////////////////
 451
 452 #if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
 453 static lzma_match *
 454 bt_find_func(
 455                 const uint32_t len_limit,
 456                 const uint32_t pos,
 457                 const uint8_t *const cur,
 458                 uint32_t cur_match,
 459                 uint32_t depth,
 460                 uint32_t *const son,
 461                 const uint32_t cyclic_pos,
 462                 const uint32_t cyclic_size,
 463                 lzma_match *matches,
 464                 uint32_t len_best)
 465 {
 466         uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
 467         uint32_t *ptr1 = son + (cyclic_pos << 1);
 468
 469         uint32_t len0 = 0;
 470         uint32_t len1 = 0;
 471
 472         while (true) {
 473                 const uint32_t delta = pos - cur_match;
 474                 if (depth-- == 0 || delta >= cyclic_size) {
 475                         *ptr0 = EMPTY_HASH_VALUE;
 476                         *ptr1 = EMPTY_HASH_VALUE;
 477                         return matches;
 478                 }
 479
 480                 uint32_t *const pair = son + ((cyclic_pos - delta
 481                                 + (delta > cyclic_pos ? cyclic_size : 0))
 482                                 << 1);
 483
 484                 const uint8_t *const pb = cur - delta;
 485                 uint32_t len = my_min(len0, len1);
 486
 487                 if (pb[len] == cur[len]) {
 488                         while (++len != len_limit)
 489                                 if (pb[len] != cur[len])
 490                                         break;
 491
 492                         if (len_best < len) {
 493                                 len_best = len;
 494                                 matches->len = len;
 495                                 matches->dist = delta - 1;
 496                                 ++matches;
 497
 498                                 if (len == len_limit) {
 499                                         *ptr1 = pair[0];
 500                                         *ptr0 = pair[1];
 501                                         return matches;
 502                                 }
 503                         }
 504                 }
 505
 506                 if (pb[len] < cur[len]) {
 507                         *ptr1 = cur_match;
 508                         ptr1 = pair + 1;
 509                         cur_match = *ptr1;
 510                         len1 = len;
 511                 } else {
 512                         *ptr0 = cur_match;
 513                         ptr0 = pair;
 514                         cur_match = *ptr0;
 515                         len0 = len;
 516                 }
 517         }
 518 }
 519
 520
 521 static void
 522 bt_skip_func(
 523                 const uint32_t len_limit,
 524                 const uint32_t pos,
 525                 const uint8_t *const cur,
 526                 uint32_t cur_match,
 527                 uint32_t depth,
 528                 uint32_t *const son,
 529                 const uint32_t cyclic_pos,
 530                 const uint32_t cyclic_size)
 531 {
 532         uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
 533         uint32_t *ptr1 = son + (cyclic_pos << 1);
 534
 535         uint32_t len0 = 0;
 536         uint32_t len1 = 0;
 537
 538         while (true) {
 539                 const uint32_t delta = pos - cur_match;
 540                 if (depth-- == 0 || delta >= cyclic_size) {
 541                         *ptr0 = EMPTY_HASH_VALUE;
 542                         *ptr1 = EMPTY_HASH_VALUE;
 543                         return;
 544                 }
 545
 546                 uint32_t *pair = son + ((cyclic_pos - delta
 547                                 + (delta > cyclic_pos ? cyclic_size : 0))
 548                                 << 1);
 549                 const uint8_t *pb = cur - delta;
 550                 uint32_t len = my_min(len0, len1);
 551
 552                 if (pb[len] == cur[len]) {
 553                         while (++len != len_limit)
 554                                 if (pb[len] != cur[len])
 555                                         break;
 556
 557                         if (len == len_limit) {
 558                                 *ptr1 = pair[0];
 559                                 *ptr0 = pair[1];
 560                                 return;
 561                         }
 562                 }
 563
 564                 if (pb[len] < cur[len]) {
 565                         *ptr1 = cur_match;
 566                         ptr1 = pair + 1;
 567                         cur_match = *ptr1;
 568                         len1 = len;
 569                 } else {
 570                         *ptr0 = cur_match;
 571                         ptr0 = pair;
 572                         cur_match = *ptr0;
 573                         len0 = len;
 574                 }
 575         }
 576 }
 577
 578
 579 #define bt_find(len_best) \
 580         call_find(bt_find_func, len_best)
 581
 582 #define bt_skip() \
 583 do { \
 584         bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \
 585                         mf->son, mf->cyclic_pos, \
 586                         mf->cyclic_size); \
 587         move_pos(mf); \
 588 } while (0)
 589
 590 #endif
 591
 592
 593 #ifdef HAVE_MF_BT2
 594 extern uint32_t
 595 lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches)
 596 {
 597         header_find(true, 2);
 598
 599         hash_2_calc();
 600
 601         const uint32_t cur_match = mf->hash[hash_value];
 602         mf->hash[hash_value] = pos;
 603
 604         bt_find(1);
 605 }
 606
 607
 608 extern void
 609 lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount)
 610 {
 611         do {
 612                 header_skip(true, 2);
 613
 614                 hash_2_calc();
 615
 616                 const uint32_t cur_match = mf->hash[hash_value];
 617                 mf->hash[hash_value] = pos;
 618
 619                 bt_skip();
 620
 621         } while (--amount != 0);
 622 }
 623 #endif
 624
 625
 626 #ifdef HAVE_MF_BT3
 627 extern uint32_t
 628 lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches)
 629 {
 630         header_find(true, 3);
 631
 632         hash_3_calc();
 633
 634         const uint32_t delta2 = pos - mf->hash[hash_2_value];
 635         const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
 636
 637         mf->hash[hash_2_value] = pos;
 638         mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
 639
 640         uint32_t len_best = 2;
 641
 642         if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
 643                 for ( ; len_best != len_limit; ++len_best)
 644                         if (*(cur + len_best - delta2) != cur[len_best])
 645                                 break;
 646
 647                 matches[0].len = len_best;
 648                 matches[0].dist = delta2 - 1;
 649                 matches_count = 1;
 650
 651                 if (len_best == len_limit) {
 652                         bt_skip();
 653                         return 1; // matches_count
 654                 }
 655         }
 656
 657         bt_find(len_best);
 658 }
 659
 660
 661 extern void
 662 lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount)
 663 {
 664         do {
 665                 header_skip(true, 3);
 666
 667                 hash_3_calc();
 668
 669                 const uint32_t cur_match
 670                                 = mf->hash[FIX_3_HASH_SIZE + hash_value];
 671
 672                 mf->hash[hash_2_value] = pos;
 673                 mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
 674
 675                 bt_skip();
 676
 677         } while (--amount != 0);
 678 }
 679 #endif
 680
 681
 682 #ifdef HAVE_MF_BT4
 683 extern uint32_t
 684 lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches)
 685 {
 686         header_find(true, 4);
 687
 688         hash_4_calc();
 689
 690         uint32_t delta2 = pos - mf->hash[hash_2_value];
 691         const uint32_t delta3
 692                         = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
 693         const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
 694
 695         mf->hash[hash_2_value] = pos;
 696         mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
 697         mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
 698
 699         uint32_t len_best = 1;
 700
 701         if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
 702                 len_best = 2;
 703                 matches[0].len = 2;
 704                 matches[0].dist = delta2 - 1;
 705                 matches_count = 1;
 706         }
 707
 708         if (delta2 != delta3 && delta3 < mf->cyclic_size
 709                         && *(cur - delta3) == *cur) {
 710                 len_best = 3;
 711                 matches[matches_count++].dist = delta3 - 1;
 712                 delta2 = delta3;
 713         }
 714
 715         if (matches_count != 0) {
 716                 for ( ; len_best != len_limit; ++len_best)
 717                         if (*(cur + len_best - delta2) != cur[len_best])
 718                                 break;
 719
 720                 matches[matches_count - 1].len = len_best;
 721
 722                 if (len_best == len_limit) {
 723                         bt_skip();
 724                         return matches_count;
 725                 }
 726         }
 727
 728         if (len_best < 3)
 729                 len_best = 3;
 730
 731         bt_find(len_best);
 732 }
 733
 734
 735 extern void
 736 lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount)
 737 {
 738         do {
 739                 header_skip(true, 4);
 740
 741                 hash_4_calc();
 742
 743                 const uint32_t cur_match
 744                                 = mf->hash[FIX_4_HASH_SIZE + hash_value];
 745
 746                 mf->hash[hash_2_value] = pos;
 747                 mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
 748                 mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
 749
 750                 bt_skip();
 751
 752         } while (--amount != 0);
 753 }
 754 #endif