String
| 2494 | |
| 2495 | /// String |
| 2496 | bool Matcher::advance_string(size_t loc) |
| 2497 | { |
| 2498 | const char *chr = pat_->chr_; |
| 2499 | const uint16_t len = pat_->len_; |
| 2500 | uint16_t lcp = pat_->lcp_; |
| 2501 | uint16_t lcs = pat_->lcs_; |
| 2502 | while (true) |
| 2503 | { |
| 2504 | const char *s = buf_ + loc + lcp; |
| 2505 | const char *e = buf_ + end_ + lcp - len + 1; |
| 2506 | #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2) |
| 2507 | // implements SSE2 string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html |
| 2508 | __m128i vlcp = _mm_set1_epi8(chr[lcp]); |
| 2509 | __m128i vlcs = _mm_set1_epi8(chr[lcs]); |
| 2510 | while (s <= e - 16) |
| 2511 | { |
| 2512 | __m128i vlcpm = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s)); |
| 2513 | __m128i vlcsm = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + lcs - lcp)); |
| 2514 | __m128i vlcpeq = _mm_cmpeq_epi8(vlcp, vlcpm); |
| 2515 | __m128i vlcseq = _mm_cmpeq_epi8(vlcs, vlcsm); |
| 2516 | uint32_t mask = _mm_movemask_epi8(_mm_and_si128(vlcpeq, vlcseq)); |
| 2517 | while (REFLEX_UNLIKELY(mask != 0)) |
| 2518 | { |
| 2519 | uint32_t offset = ctz(mask); |
| 2520 | if (std::memcmp(s - lcp + offset, chr, len) == 0) |
| 2521 | { |
| 2522 | size_t k = s - lcp + offset - buf_; |
| 2523 | set_current(k); |
| 2524 | return true; |
| 2525 | } |
| 2526 | mask &= mask - 1; |
| 2527 | } |
| 2528 | s += 16; |
| 2529 | } |
| 2530 | #elif defined(HAVE_NEON) |
| 2531 | // slightly faster when abstracted into a routine |
| 2532 | if (simd_advance_string_neon(s, e)) |
| 2533 | return true; |
| 2534 | #endif |
| 2535 | while (s < e) |
| 2536 | { |
| 2537 | do |
| 2538 | s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s)); |
| 2539 | while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e); |
| 2540 | if (s == NULL || s >= e) |
| 2541 | { |
| 2542 | s = e; |
| 2543 | break; |
| 2544 | } |
| 2545 | if (std::memcmp(s - lcp, chr, len) == 0) |
| 2546 | { |
| 2547 | size_t k = s - lcp - buf_; |
| 2548 | set_current(k); |
| 2549 | return true; |
| 2550 | } |
| 2551 | ++s; |
| 2552 | } |
| 2553 | loc = s - lcp - buf_; |