commit 002b6d97257d12340cefe8041a5b300ea2be2282
author Paul Wankadia <junyer@google.com> Fri May 22 04:36:43 2020 -0700
committer Paul Wankadia <junyer@google.com> Fri May 22 11:38:37 2020 +0000
tree 5fe33d6f99090eeba439a64028cf184923145960
parent 25238e4a33af97b16156f56b4fe7bd7a4e46b182

Make "front and back" prefix accel work with MSVC.

Change-Id: Idbae09ca9a97c1f8ce08ddefd0bb2863d4deb325
Reviewed-on: https://code-review.googlesource.com/c/re2/+/56774
Reviewed-by: Paul Wankadia <junyer@google.com>

re2/prog.cc

diff --git a/re2/prog.cc b/re2/prog.cc
index fdc8022..ac9c085 100644
--- a/re2/prog.cc
+++ b/re2/prog.cc
@@ -7,8 +7,11 @@
 
 #include "re2/prog.h"
 
-#if defined(__GNUC__) && defined(__AVX2__)
+#if defined(__AVX2__)
 #include <immintrin.h>
+#ifdef _MSC_VER
+#include <intrin.h>
+#endif
 #endif
 #include <stdint.h>
 #include <string.h>
@@ -913,6 +916,30 @@
   }
 }
 
+#if defined(__AVX2__)
+// Finds the least significant non-zero bit in n.
+static int FindLSBSet(uint32_t n) {
+  DCHECK_NE(n, 0);
+#if defined(__GNUC__)
+  return __builtin_ctz(n);
+#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86))
+  unsigned long c;
+  _BitScanForward(&c, n);
+  return static_cast<int>(c);
+#else
+  int c = 31;
+  for (int shift = 1 << 4; shift != 0; shift >>= 1) {
+    uint32_t word = n << shift;
+    if (word != 0) {
+      n = word;
+      c -= shift;
+    }
+  }
+  return c;
+#endif
+}
+#endif
+
 const void* Prog::PrefixAccel_FrontAndBack(const void* data, size_t size) {
   DCHECK_GE(prefix_size_, 2);
   if (size < prefix_size_)
@@ -921,7 +948,7 @@
   // This also means that probing for prefix_back_ doesn't go out of bounds.
   size -= prefix_size_-1;
 
-#if defined(__GNUC__) && defined(__AVX2__)
+#if defined(__AVX2__)
   // Use AVX2 to look for prefix_front_ and prefix_back_ 32 bytes at a time.
   if (size >= sizeof(__m256i)) {
     const __m256i* fp = reinterpret_cast<const __m256i*>(
@@ -940,7 +967,7 @@
       if (fb_testz == 0) {  // ZF: 1 means zero, 0 means non-zero.
         const __m256i fb_and = _mm256_and_si256(f_cmpeq, b_cmpeq);
         const int fb_movemask = _mm256_movemask_epi8(fb_and);
-        const int fb_ctz = __builtin_ctz(fb_movemask);
+        const int fb_ctz = FindLSBSet(fb_movemask);
         return reinterpret_cast<const char*>(fp-1) + fb_ctz;
       }
     }