src/liblzma/lz/lz_encoder_mf.c

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