From 3b75d2b05a1ed02525b86152168151300a827613 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Wed, 8 Feb 2023 12:05:58 +0700
Subject: [PATCH v4 2/4] Add MSVC support for bitscan reverse/forward

---
 src/include/port/pg_bitutils.h | 75 ++++++++++++++++++++++++++++++----
 1 file changed, 67 insertions(+), 8 deletions(-)

diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index a5df4f1a35..9150789aaf 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -13,6 +13,21 @@
 #ifndef PG_BITUTILS_H
 #define PG_BITUTILS_H
 
+#ifdef _MSC_VER
+#include <intrin.h>
+#define HAVE_BITSCAN_FORWARD
+#define HAVE_BITSCAN_REVERSE
+
+#else
+#if defined(HAVE__BUILTIN_CTZ)
+#define HAVE_BITSCAN_FORWARD
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ)
+#define HAVE_BITSCAN_REVERSE
+#endif
+#endif							/* _MSC_VER */
+
 extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
 extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
 extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
@@ -27,9 +42,12 @@ pg_leftmost_one_pos32(uint32 word)
 {
 #ifdef HAVE__BUILTIN_CLZ
 	int			bitscan_result;
+#elif defined(_MSC_VER)
+	unsigned long bitscan_result;
+	bool		non_zero;
 #endif
 
-#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_REVERSE) || defined(USE_ASSERT_CHECKING)
 	int			result;
 	int			shift = 32 - 8;
 
@@ -41,13 +59,20 @@ pg_leftmost_one_pos32(uint32 word)
 	result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
 #endif
 
+#ifdef HAVE_BITSCAN_REVERSE
+
 #if defined(HAVE__BUILTIN_CLZ)
 	bitscan_result = 31 - __builtin_clz(word);
+#elif defined(_MSC_VER)
+	non_zero = _BitScanReverse(&bitscan_result, word);
+	Assert(non_zero);
+#endif
 	Assert(bitscan_result == result);
 	return bitscan_result;
+
 #else
 	return result;
-#endif							/* HAVE__BUILTIN_CLZ */
+#endif							/* HAVE_BITSCAN_REVERSE */
 }
 
 /*
@@ -59,9 +84,12 @@ pg_leftmost_one_pos64(uint64 word)
 {
 #ifdef HAVE__BUILTIN_CLZ
 	int			bitscan_result;
+#elif defined(_MSC_VER)
+	unsigned long bitscan_result;
+	bool		non_zero;
 #endif
 
-#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_REVERSE) || defined(USE_ASSERT_CHECKING)
 	int			result;
 	int			shift = 64 - 8;
 
@@ -73,6 +101,8 @@ pg_leftmost_one_pos64(uint64 word)
 	result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
 #endif
 
+#ifdef HAVE_BITSCAN_REVERSE
+
 #if defined(HAVE__BUILTIN_CLZ)
 #if defined(HAVE_LONG_INT_64)
 	bitscan_result = 63 - __builtin_clzl(word);
@@ -81,11 +111,17 @@ pg_leftmost_one_pos64(uint64 word)
 #else
 #error must have a working 64-bit integer datatype
 #endif							/* HAVE_LONG_INT_64 */
+
+#elif defined(_MSC_VER)
+	non_zero = _BitScanReverse64(&bitscan_result, word);
+	Assert(non_zero);
+#endif							/* HAVE__BUILTIN_CLZ */
 	Assert(bitscan_result == result);
 	return bitscan_result;
+
 #else
 	return result;
-#endif							/* HAVE__BUILTIN_CLZ */
+#endif							/* HAVE_BITSCAN_REVERSE */
 }
 
 /*
@@ -99,9 +135,13 @@ pg_rightmost_one_pos32(uint32 word)
 #ifdef HAVE__BUILTIN_CTZ
 	const uint32 orig_word = word;
 	int			bitscan_result;
+#elif defined(_MSC_VER)
+	const unsigned long orig_word = word;
+	unsigned long bitscan_result;
+	bool		non_zero;
 #endif
 
-#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_FORWARD) || defined(USE_ASSERT_CHECKING)
 	int			result = 0;
 
 	Assert(word != 0);
@@ -114,13 +154,20 @@ pg_rightmost_one_pos32(uint32 word)
 	result += pg_rightmost_one_pos[word & 255];
 #endif
 
+#ifdef HAVE_BITSCAN_FORWARD
+
 #if defined(HAVE__BUILTIN_CTZ)
 	bitscan_result = __builtin_ctz(orig_word);
+#elif defined(_MSC_VER)
+	non_zero = _BitScanForward(&bitscan_result, orig_word);
+	Assert(non_zero);
+#endif
 	Assert(bitscan_result == result);
 	return bitscan_result;
+
 #else
 	return result;
-#endif							/* HAVE__BUILTIN_CTZ */
+#endif							/* HAVE_BITSCAN_FORWARD */
 }
 
 /*
@@ -133,9 +180,13 @@ pg_rightmost_one_pos64(uint64 word)
 #ifdef HAVE__BUILTIN_CTZ
 	const uint64 orig_word = word;
 	int			bitscan_result;
+#elif defined(_MSC_VER)
+	const unsigned __int64 orig_word = word;
+	unsigned long bitscan_result;
+	bool		non_zero;
 #endif
 
-#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_FORWARD) || defined(USE_ASSERT_CHECKING)
 	int			result = 0;
 
 	Assert(word != 0);
@@ -148,6 +199,8 @@ pg_rightmost_one_pos64(uint64 word)
 	result += pg_rightmost_one_pos[word & 255];
 #endif
 
+#ifdef HAVE_BITSCAN_FORWARD
+
 #if defined(HAVE__BUILTIN_CTZ)
 #if defined(HAVE_LONG_INT_64)
 	bitscan_result = __builtin_ctzl(orig_word);
@@ -156,11 +209,17 @@ pg_rightmost_one_pos64(uint64 word)
 #else
 #error must have a working 64-bit integer datatype
 #endif							/* HAVE_LONG_INT_64 */
+
+#elif defined(_MSC_VER)
+	non_zero = _BitScanForward64(&bitscan_result, orig_word);
+	Assert(non_zero);
+#endif							/* HAVE__BUILTIN_CTZ */
 	Assert(bitscan_result == result);
 	return bitscan_result;
+
 #else
 	return result;
-#endif							/* HAVE__BUILTIN_CTZ */
+#endif							/* HAVE_BITSCAN_FORWARD */
 }
 
 /*
-- 
2.39.1