Method advance_string_bm

lib/matcher.cpp:2769–2822

My homegrown improved Boyer-Moore string search, a fallback method

/// My homegrown improved Boyer-Moore string search, a fallback method
bool Matcher::advance_string_bm(size_t loc)
{
  const char *chr = pat_->chr_;
  const uint8_t *bms = pat_->bms_;
  const uint16_t len = pat_->len_;
  const uint16_t bmd = pat_->bmd_;
  const uint16_t lcp = pat_->lcp_;
  while (true)
  {
    const char *s = buf_ + loc + len - 1;
    const char *e = buf_ + end_;
    const char *t = chr + len - 1;
    while (s < e)
    {
      size_t k = 0;
      do
        s += k = bms[static_cast<uint8_t>(*s)];
      while (k > 0 ? s < e : s[lcp - len + 1] != chr[lcp] && (s += bmd) < e);
      if (s >= e)
        break;
      const char *p = t - 1;
      const char *q = s - 1;
      while (p >= chr && *p == *q)
      {
        --p;
        --q;
      }
      if (p < chr)
      {
        k = q - buf_ + 1;
        set_current(k);
        return true;
      }
      if (chr + bmd >= p)
      {
        s += bmd;
      }
      else
      {
        k = bms[static_cast<uint8_t>(*q)];
        if (p + k > t + bmd)
          s += k - (t - p);
        else
          s += bmd;
      }
    }
    s -= len - 1;
    loc = s - buf_;
    set_current_and_peek_more(loc);
    loc = cur_;
    if (loc + len > end_ && eof_)
      return false;
  }
}

/// My homegrown improved Boyer-Moore string search followed by minimal 1 byte long patterns, using PM
bool Matcher::advance_string_bm_pma(size_t loc)