text: ///////////////////////////////////////////////////////////////////////////////
  //
  /// \file       lz_encoder_mf.c
  /// \brief      Match finders
  ///
  //  Authors:    Igor Pavlov
  //              Lasse Collin
  //
  //  This file has been put into the public domain.
  //  You can do whatever you want with this file.
  //
  ///////////////////////////////////////////////////////////////////////////////
  
  #include "lz_encoder.h"
  #include "lz_encoder_hash.h"
  #include "memcmplen.h"
  
  /// \brief      Find matches starting from the current byte
  ///
  /// \return     The length of the longest match found
  extern uint32_t lzma_mf_find(lzma_mf* mf, uint32_t* count_ptr,
                               lzma_match* matches)
  {
      // Call the match finder. It returns the number of length-distance
      // pairs found.
      // FIXME: Minimum count is zero, what _exactly_ is the maximum?
      const uint32_t count = mf->find(mf, matches);
  
      // Length of the longest match; assume that no matches were found
      // and thus the maximum length is zero.
      uint32_t len_best = 0;
  
      if (count > 0)
      {
  #ifndef NDEBUG
          // Validate the matches.
          for (uint32_t i = 0; i < count; ++i)
          {
              assert(matches[i].len <= mf->nice_len);
              assert(matches[i].dist < mf->read_pos);
              assert(memcmp(mf_ptr(mf) - 1, mf_ptr(mf) - matches[i].dist - 2,
                            matches[i].len) == 0);
          }
  #endif
  
          // The last used element in the array contains
          // the longest match.
          len_best = matches[count - 1].len;
  
          // If a match of maximum search length was found, try to
          // extend the match to maximum possible length.
          if (len_best == mf->nice_len)
          {
              // The limit for the match length is either the
              // maximum match length supported by the LZ-based
              // encoder or the number of bytes left in the
              // dictionary, whichever is smaller.
              uint32_t limit = mf_avail(mf) + 1;
              if (limit > mf->match_len_max)
                  limit = mf->match_len_max;
  
              // Pointer to the byte we just ran through
              // the match finder.
              const uint8_t* p1 = mf_ptr(mf) - 1;
  
              // Pointer to the beginning of the match. We need -1
              // here because the match distances are zero based.
              const uint8_t* p2 = p1 - matches[count - 1].dist - 1;
  
              len_best = lzma_memcmplen(p1, p2, len_best, limit);
          }
      }
  
      *count_ptr = count;
  
      // Finally update the read position to indicate that match finder was
      // run for this dictionary offset.
      ++mf->read_ahead;
  
      return len_best;
  }
  
  /// Hash value to indicate unused element in the hash. Since we start the
  /// positions from dict_size + 1, zero is always too far to qualify
  /// as usable match position.
  #define EMPTY_HASH_VALUE 0
  
  /// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos
  /// reaches MUST_NORMALIZE_POS.
  #define MUST_NORMALIZE_POS UINT32_MAX
  
  /// \brief      Normalizes hash values
  ///
  /// The hash arrays store positions of match candidates. The positions are
  /// relative to an arbitrary offset that is not the same as the absolute
  /// offset in the input stream. The relative position of the current byte
  /// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are
  /// the differences of the current read position and the position found from
  /// the hash.
  ///
  /// To prevent integer overflows of the offsets stored in the hash arrays,
  /// we need to "normalize" the stored values now and then. During the
  /// normalization, we drop values that indicate distance greater than the
  /// dictionary size, thus making space for new values.
  static void normalize(lzma_mf* mf)
  {
      assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS);
  
      // In future we may not want to touch the lowest bits, because there
      // may be match finders that use larger resolution than one byte.
      const uint32_t subvalue = (MUST_NORMALIZE_POS - mf->cyclic_size);
      // & (~(UINT32_C(1) << 10) - 1);
  
      for (uint32_t i = 0; i < mf->hash_count; ++i)
      {
          // If the distance is greater than the dictionary size,
          // we can simply mark the hash element as empty.
          if (mf->hash[i] <= subvalue)
              mf->hash[i] = EMPTY_HASH_VALUE;
          else
              mf->hash[i] -= subvalue;
      }
  
      for (uint32_t i = 0; i < mf->sons_count; ++i)
      {
          // Do the same for mf->son.
          //
          // NOTE: There may be uninitialized elements in mf->son.
          // Valgrind may complain that the "if" below depends on
          // an uninitialized value. In this case it is safe to ignore
          // the warning. See also the comments in lz_encoder_init()
          // in lz_encoder.c.
          if (mf->son[i] <= subvalue)
              mf->son[i] = EMPTY_HASH_VALUE;
          else
              mf->son[i] -= subvalue;
      }
  
      // Update offset to match the new locations.
      mf->offset -= subvalue;
  
      return;
  }
  
  /// Mark the current byte as processed from point of view of the match finder.
  static void move_pos(lzma_mf* mf)
  {
      if (++mf->cyclic_pos == mf->cyclic_size)
          mf->cyclic_pos = 0;
  
      ++mf->read_pos;
      assert(mf->read_pos <= mf->write_pos);
  
      if (unlikely(mf->read_pos + mf->offset == UINT32_MAX))
          normalize(mf);
  }
  
  /// When flushing, we cannot run the match finder unless there is nice_len
  /// bytes available in the dictionary. Instead, we skip running the match
  /// finder (indicating that no match was found), and count how many bytes we
  /// have ignored this way.
  ///
  /// When new data is given after the flushing was completed, the match finder
  /// is restarted by rewinding mf->read_pos backwards by mf->pending. Then
  /// the missed bytes are added to the hash using the match finder's skip
  /// function (with small amount of input, it may start using mf->pending
  /// again if flushing).
  ///
  /// Due to this rewinding, we don't touch cyclic_pos or test for
  /// normalization. It will be done when the match finder's skip function
  /// catches up after a flush.
  static void move_pending(lzma_mf* mf)
  {
      ++mf->read_pos;
      assert(mf->read_pos <= mf->write_pos);
      ++mf->pending;
  }
  
  /// Calculate len_limit and determine if there is enough input to run
  /// the actual match finder code. Sets up "cur" and "pos". This macro
  /// is used by all find functions and binary tree skip functions. Hash
  /// chain skip function doesn't need len_limit so a simpler code is used
  /// in them.
  #define header(is_bt, len_min, ret_op)                                         \
      uint32_t len_limit = mf_avail(mf);                                         \
      if (mf->nice_len <= len_limit)                                             \
      {                                                                          \
          len_limit = mf->nice_len;                                              \
      }                                                                          \
      else if (len_limit < (len_min) ||                                          \
               (is_bt && mf->action == LZMA_SYNC_FLUSH))                         \
      {                                                                          \
          assert(mf->action != LZMA_RUN);                                        \
          move_pending(mf);                                                      \
          ret_op;                                                                \
      }                                                                          \
      const uint8_t* cur = mf_ptr(mf);                                           \
      const uint32_t pos = mf->read_pos + mf->offset
  
  /// Header for find functions. "return 0" indicates that zero matches
  /// were found.
  #define header_find(is_bt, len_min)                                            \
      header(is_bt, len_min, return 0);                                          \
      uint32_t matches_count = 0
  
  /// Header for a loop in a skip function. "continue" tells to skip the rest
  /// of the code in the loop.
  #define header_skip(is_bt, len_min) header(is_bt, len_min, continue)
  
  /// Calls hc_find_func() or bt_find_func() and calculates the total number
  /// of matches found. Updates the dictionary position and returns the number
  /// of matches found.
  #define call_find(func, len_best)                                              \
      do                                                                         \
      {                                                                          \
          matches_count = func(len_limit, pos, cur, cur_match, mf->depth,        \
                               mf->son, mf->cyclic_pos, mf->cyclic_size,         \
                               matches + matches_count, len_best) -              \
                          matches;                                               \
          move_pos(mf);                                                          \
          return matches_count;                                                  \
      } while (0)
  
  ////////////////
  // Hash Chain //
  ////////////////
  
  #if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
  ///
  ///
  /// \param      len_limit       Don't look for matches longer than len_limit.
  /// \param      pos             lzma_mf.read_pos + lzma_mf.offset
  /// \param      cur             Pointer to current byte (mf_ptr(mf))
  /// \param      cur_match       Start position of the current match candidate
  /// \param      depth           Maximum length of the hash chain
  /// \param      son             lzma_mf.son (contains the hash chain)
  /// \param      cyclic_pos
  /// \param      cyclic_size
  /// \param      matches         Array to hold the matches.
  /// \param      len_best        The length of the longest match found so far.
  static lzma_match* hc_find_func(const uint32_t len_limit, const uint32_t pos,
                                  const uint8_t* const cur, uint32_t cur_match,
                                  uint32_t depth, uint32_t* const son,
                                  const uint32_t cyclic_pos,
                                  const uint32_t cyclic_size, lzma_match* matches,
                                  uint32_t len_best)
  {
      son[cyclic_pos] = cur_match;
  
      while (true)
      {
          const uint32_t delta = pos - cur_match;
          if (depth-- == 0 || delta >= cyclic_size)
              return matches;
  
          const uint8_t* const pb = cur - delta;
          cur_match =
              son[cyclic_pos - delta + (delta > cyclic_pos ? cyclic_size : 0)];
  
          if (pb[len_best] == cur[len_best] && pb[0] == cur[0])
          {
              uint32_t len = lzma_memcmplen(pb, cur, 1, len_limit);
  
              if (len_best < len)
              {
                  len_best = len;
                  matches->len = len;
                  matches->dist = delta - 1;
                  ++matches;
  
                  if (len == len_limit)
                      return matches;
              }
          }
      }
  }
  
  #define hc_find(len_best) call_find(hc_find_func, len_best)
  
  #define hc_skip()                                                              \
      do                                                                         \
      {                                                                          \
          mf->son[mf->cyclic_pos] = cur_match;                                   \
          move_pos(mf);                                                          \
      } while (0)
  
  #endif
  
  #ifdef HAVE_MF_HC3
  extern uint32_t lzma_mf_hc3_find(lzma_mf* mf, lzma_match* matches)
  {
      header_find(false, 3);
  
      hash_3_calc();
  
      const uint32_t delta2 = pos - mf->hash[hash_2_value];
      const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
  
      mf->hash[hash_2_value] = pos;
      mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
  
      uint32_t len_best = 2;
  
      if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur)
      {
          len_best = lzma_memcmplen(cur - delta2, cur, len_best, len_limit);
  
          matches[0].len = len_best;
          matches[0].dist = delta2 - 1;
          matches_count = 1;
  
          if (len_best == len_limit)
          {
              hc_skip();
              return 1; // matches_count
          }
      }
  
      hc_find(len_best);
  }
  
  extern void lzma_mf_hc3_skip(lzma_mf* mf, uint32_t amount)
  {
      do
      {
          if (mf_avail(mf) < 3)
          {
              move_pending(mf);
              continue;
          }
  
          const uint8_t* cur = mf_ptr(mf);
          const uint32_t pos = mf->read_pos + mf->offset;
  
          hash_3_calc();
  
          const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
  
          mf->hash[hash_2_value] = pos;
          mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
  
          hc_skip();
  
      } while (--amount != 0);
  }
  #endif
  
  #ifdef HAVE_MF_HC4
  extern uint32_t lzma_mf_hc4_find(lzma_mf* mf, lzma_match* matches)
  {
      header_find(false, 4);
  
      hash_4_calc();
  
      uint32_t delta2 = pos - mf->hash[hash_2_value];
      const uint32_t delta3 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
      const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
  
      mf->hash[hash_2_value] = pos;
      mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
      mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
  
      uint32_t len_best = 1;
  
      if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur)
      {
          len_best = 2;
          matches[0].len = 2;
          matches[0].dist = delta2 - 1;
          matches_count = 1;
      }
  
      if (delta2 != delta3 && delta3 < mf->cyclic_size && *(cur - delta3) == *cur)
      {
          len_best = 3;
          matches[matches_count++].dist = delta3 - 1;
          delta2 = delta3;
      }
  
      if (matches_count != 0)
      {
          len_best = lzma_memcmplen(cur - delta2, cur, len_best, len_limit);
  
          matches[matches_count - 1].len = len_best;
  
          if (len_best == len_limit)
          {
              hc_skip();
              return matches_count;
          }
      }
  
      if (len_best < 3)
          len_best = 3;
  
      hc_find(len_best);
  }
  
  extern void lzma_mf_hc4_skip(lzma_mf* mf, uint32_t amount)
  {
      do
      {
          if (mf_avail(mf) < 4)
          {
              move_pending(mf);
              continue;
          }
  
          const uint8_t* cur = mf_ptr(mf);
          const uint32_t pos = mf->read_pos + mf->offset;
  
          hash_4_calc();
  
          const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
  
          mf->hash[hash_2_value] = pos;
          mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
          mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
  
          hc_skip();
  
      } while (--amount != 0);
  }
  #endif
  
  /////////////////
  // Binary Tree //
  /////////////////
  
  #if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
  static lzma_match* bt_find_func(const uint32_t len_limit, const uint32_t pos,
                                  const uint8_t* const cur, uint32_t cur_match,
                                  uint32_t depth, uint32_t* const son,
                                  const uint32_t cyclic_pos,
                                  const uint32_t cyclic_size, lzma_match* matches,
                                  uint32_t len_best)
  {
      uint32_t* ptr0 = son + (cyclic_pos << 1) + 1;
      uint32_t* ptr1 = son + (cyclic_pos << 1);
  
      uint32_t len0 = 0;
      uint32_t len1 = 0;
  
      while (true)
      {
          const uint32_t delta = pos - cur_match;
          if (depth-- == 0 || delta >= cyclic_size)
          {
              *ptr0 = EMPTY_HASH_VALUE;
              *ptr1 = EMPTY_HASH_VALUE;
              return matches;
          }
  
          uint32_t* const pair =
              son + ((cyclic_pos - delta + (delta > cyclic_pos ? cyclic_size : 0))
                     << 1);
  
          const uint8_t* const pb = cur - delta;
          uint32_t len = my_min(len0, len1);
  
          if (pb[len] == cur[len])
          {
              len = lzma_memcmplen(pb, cur, len + 1, len_limit);
  
              if (len_best < len)
              {
                  len_best = len;
                  matches->len = len;
                  matches->dist = delta - 1;
                  ++matches;
  
                  if (len == len_limit)
                  {
                      *ptr1 = pair[0];
                      *ptr0 = pair[1];
                      return matches;
                  }
              }
          }
  
          if (pb[len] < cur[len])
          {
              *ptr1 = cur_match;
              ptr1 = pair + 1;
              cur_match = *ptr1;
              len1 = len;
          }
          else
          {
              *ptr0 = cur_match;
              ptr0 = pair;
              cur_match = *ptr0;
              len0 = len;
          }
      }
  }
  
  static void bt_skip_func(const uint32_t len_limit, const uint32_t pos,
                           const uint8_t* const cur, uint32_t cur_match,
                           uint32_t depth, uint32_t* const son,
                           const uint32_t cyclic_pos, const uint32_t cyclic_size)
  {
      uint32_t* ptr0 = son + (cyclic_pos << 1) + 1;
      uint32_t* ptr1 = son + (cyclic_pos << 1);
  
      uint32_t len0 = 0;
      uint32_t len1 = 0;
  
      while (true)
      {
          const uint32_t delta = pos - cur_match;
          if (depth-- == 0 || delta >= cyclic_size)
          {
              *ptr0 = EMPTY_HASH_VALUE;
              *ptr1 = EMPTY_HASH_VALUE;
              return;
          }
  
          uint32_t* pair =
              son + ((cyclic_pos - delta + (delta > cyclic_pos ? cyclic_size : 0))
                     << 1);
          const uint8_t* pb = cur - delta;
          uint32_t len = my_min(len0, len1);
  
          if (pb[len] == cur[len])
          {
              len = lzma_memcmplen(pb, cur, len + 1, len_limit);
  
              if (len == len_limit)
              {
                  *ptr1 = pair[0];
                  *ptr0 = pair[1];
                  return;
              }
          }
  
          if (pb[len] < cur[len])
          {
              *ptr1 = cur_match;
              ptr1 = pair + 1;
              cur_match = *ptr1;
              len1 = len;
          }
          else
          {
              *ptr0 = cur_match;
              ptr0 = pair;
              cur_match = *ptr0;
              len0 = len;
          }
      }
  }
  
  #define bt_find(len_best) call_find(bt_find_func, len_best)
  
  #define bt_skip()                                                              \
      do                                                                         \
      {                                                                          \
          bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, mf->son,       \
                       mf->cyclic_pos, mf->cyclic_size);                         \
          move_pos(mf);                                                          \
      } while (0)
  
  #endif
  
  #ifdef HAVE_MF_BT2
  extern uint32_t lzma_mf_bt2_find(lzma_mf* mf, lzma_match* matches)
  {
      header_find(true, 2);
  
      hash_2_calc();
  
      const uint32_t cur_match = mf->hash[hash_value];
      mf->hash[hash_value] = pos;
  
      bt_find(1);
  }
  
  extern void lzma_mf_bt2_skip(lzma_mf* mf, uint32_t amount)
  {
      do
      {
          header_skip(true, 2);
  
          hash_2_calc();
  
          const uint32_t cur_match = mf->hash[hash_value];
          mf->hash[hash_value] = pos;
  
          bt_skip();
  
      } while (--amount != 0);
  }
  #endif
  
  #ifdef HAVE_MF_BT3
  extern uint32_t lzma_mf_bt3_find(lzma_mf* mf, lzma_match* matches)
  {
      header_find(true, 3);
  
      hash_3_calc();
  
      const uint32_t delta2 = pos - mf->hash[hash_2_value];
      const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
  
      mf->hash[hash_2_value] = pos;
      mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
  
      uint32_t len_best = 2;
  
      if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur)
      {
          len_best = lzma_memcmplen(cur, cur - delta2, len_best, len_limit);
  
          matches[0].len = len_best;
          matches[0].dist = delta2 - 1;
          matches_count = 1;
  
          if (len_best == len_limit)
          {
              bt_skip();
              return 1; // matches_count
          }
      }
  
      bt_find(len_best);
  }
  
  extern void lzma_mf_bt3_skip(lzma_mf* mf, uint32_t amount)
  {
      do
      {
          header_skip(true, 3);
  
          hash_3_calc();
  
          const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
  
          mf->hash[hash_2_value] = pos;
          mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
  
          bt_skip();
  
      } while (--amount != 0);
  }
  #endif
  
  #ifdef HAVE_MF_BT4
  extern uint32_t lzma_mf_bt4_find(lzma_mf* mf, lzma_match* matches)
  {
      header_find(true, 4);
  
      hash_4_calc();
  
      uint32_t delta2 = pos - mf->hash[hash_2_value];
      const uint32_t delta3 = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
      const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
  
      mf->hash[hash_2_value] = pos;
      mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
      mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
  
      uint32_t len_best = 1;
  
      if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur)
      {
          len_best = 2;
          matches[0].len = 2;
          matches[0].dist = delta2 - 1;
          matches_count = 1;
      }
  
      if (delta2 != delta3 && delta3 < mf->cyclic_size && *(cur - delta3) == *cur)
      {
          len_best = 3;
          matches[matches_count++].dist = delta3 - 1;
          delta2 = delta3;
      }
  
      if (matches_count != 0)
      {
          len_best = lzma_memcmplen(cur, cur - delta2, len_best, len_limit);
  
          matches[matches_count - 1].len = len_best;
  
          if (len_best == len_limit)
          {
              bt_skip();
              return matches_count;
          }
      }
  
      if (len_best < 3)
          len_best = 3;
  
      bt_find(len_best);
  }
  
  extern void lzma_mf_bt4_skip(lzma_mf* mf, uint32_t amount)
  {
      do
      {
          header_skip(true, 4);
  
          hash_4_calc();
  
          const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
  
          mf->hash[hash_2_value] = pos;
          mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
          mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
  
          bt_skip();
  
      } while (--amount != 0);
  }
  #endif
  