Attached is a quick-and-dirty attempt to add MSVC support for the
rightmost/leftmost-one-pos functions.
0001 adds asserts to the existing coding.
0002 adds MSVC support. Tests pass on CI, but it's of course possible that
there is some bug that prevents hitting the fastpath. I've mostly used
the platform specific types, so some further cleanup might be needed.
0003 tries one way to reduce the duplication that arose in 0002. Maybe
there is a better way.
--
John Naylor
EDB: http://www.enterprisedb.com
From 9390a74f1712d58c88ac513afff8d878071c040c Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Tue, 24 Jan 2023 15:57:53 +0700
Subject: [PATCH v3 2/3] Add MSVC support for bitscan reverse/forward
---
src/include/port/pg_bitutils.h | 38 ++++++++++++++++++++++++++++++++++
1 file changed, 38 insertions(+)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 9a53f53d11..ce04f4ffad 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -13,6 +13,10 @@
#ifndef PG_BITUTILS_H
#define PG_BITUTILS_H
+#ifdef _MSC_VER
+#include <intrin.h>
+#endif
+
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,6 +31,9 @@ pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
int bitscan_result;
+#elif defined(_MSC_VER)
+ unsigned long bitscan_result;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
@@ -45,6 +52,11 @@ pg_leftmost_one_pos32(uint32 word)
bitscan_result = 31 - __builtin_clz(word);
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanReverse(&bitscan_result, word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CLZ */
@@ -59,6 +71,9 @@ pg_leftmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
int bitscan_result;
+#elif defined(_MSC_VER)
+ unsigned long bitscan_result;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
@@ -83,6 +98,11 @@ pg_leftmost_one_pos64(uint64 word)
#endif /* HAVE_LONG_... */
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanReverse64(&bitscan_result, word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CLZ */
@@ -99,6 +119,10 @@ 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;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
@@ -118,6 +142,11 @@ pg_rightmost_one_pos32(uint32 word)
bitscan_result = __builtin_ctz(orig_word);
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanForward(&bitscan_result, orig_word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
@@ -133,6 +162,10 @@ 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;
+ unsigned char non_zero; // XXX can this be bool?
#endif
#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
@@ -158,6 +191,11 @@ pg_rightmost_one_pos64(uint64 word)
#endif /* HAVE_LONG_... */
Assert(bitscan_result == result);
return bitscan_result;
+#elif defined(_MSC_VER)
+ non_zero = _BitScanForward64(&bitscan_result, orig_word);
+ Assert(non_zero);
+ Assert(bitscan_result == result);
+ return bitscan_result;
#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
--
2.39.0
From 88b98a3fe8d9b5f9a10a839e65b34c43c03e33b2 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Tue, 24 Jan 2023 14:39:26 +0700
Subject: [PATCH v3 1/3] Add asserts to verify bitscan intrinsics
---
src/include/port/pg_bitutils.h | 86 ++++++++++++++++++++++++----------
1 file changed, 60 insertions(+), 26 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index a49a9c03d9..9a53f53d11 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -26,10 +26,11 @@ static inline int
pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
- Assert(word != 0);
+ int bitscan_result;
+#endif
- return 31 - __builtin_clz(word);
-#else
+#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+ int result;
int shift = 32 - 8;
Assert(word != 0);
@@ -37,7 +38,15 @@ pg_leftmost_one_pos32(uint32 word)
while ((word >> shift) == 0)
shift -= 8;
- return shift + pg_leftmost_one_pos[(word >> shift) & 255];
+ result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ)
+ bitscan_result = 31 - __builtin_clz(word);
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
+ return result;
#endif /* HAVE__BUILTIN_CLZ */
}
@@ -49,16 +58,11 @@ static inline int
pg_leftmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
- Assert(word != 0);
-
-#if defined(HAVE_LONG_INT_64)
- return 63 - __builtin_clzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
- return 63 - __builtin_clzll(word);
-#else
-#error must have a working 64-bit integer datatype
+ int bitscan_result;
#endif
-#else /* !HAVE__BUILTIN_CLZ */
+
+#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+ int result;
int shift = 64 - 8;
Assert(word != 0);
@@ -66,7 +70,21 @@ pg_leftmost_one_pos64(uint64 word)
while ((word >> shift) == 0)
shift -= 8;
- return shift + pg_leftmost_one_pos[(word >> shift) & 255];
+ result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ)
+#if defined(HAVE_LONG_INT_64)
+ bitscan_result = 63 - __builtin_clzl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+ bitscan_result = 63 - __builtin_clzll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif /* HAVE_LONG_... */
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
+ return result;
#endif /* HAVE__BUILTIN_CLZ */
}
@@ -79,10 +97,11 @@ static inline int
pg_rightmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CTZ
- Assert(word != 0);
+ const uint32 orig_word = word;
+ int bitscan_result;
+#endif
- return __builtin_ctz(word);
-#else
+#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -93,6 +112,13 @@ pg_rightmost_one_pos32(uint32 word)
result += 8;
}
result += pg_rightmost_one_pos[word & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CTZ)
+ bitscan_result = __builtin_ctz(orig_word);
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
}
@@ -105,16 +131,11 @@ static inline int
pg_rightmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CTZ
- Assert(word != 0);
-
-#if defined(HAVE_LONG_INT_64)
- return __builtin_ctzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
- return __builtin_ctzll(word);
-#else
-#error must have a working 64-bit integer datatype
+ const uint64 orig_word = word;
+ int bitscan_result;
#endif
-#else /* !HAVE__BUILTIN_CTZ */
+
+#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -125,6 +146,19 @@ pg_rightmost_one_pos64(uint64 word)
result += 8;
}
result += pg_rightmost_one_pos[word & 255];
+#endif
+
+#ifdef HAVE__BUILTIN_CTZ
+#if defined(HAVE_LONG_INT_64)
+ bitscan_result = __builtin_ctzl(orig_word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+ bitscan_result = __builtin_ctzll(orig_word);
+#else
+#error must have a working 64-bit integer datatype
+#endif /* HAVE_LONG_... */
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
}
--
2.39.0
From fb51913a6c76a5d5aa09a8ef843e16cd3c383f37 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Tue, 24 Jan 2023 20:39:55 +0700
Subject: [PATCH v3 3/3] Add new symbols for reducing repetition
---
src/include/port/pg_bitutils.h | 72 +++++++++++++++++++---------------
1 file changed, 40 insertions(+), 32 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index ce04f4ffad..68aba3e090 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -21,6 +21,10 @@ 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];
+#if defined(HAVE__BUILTIN_CLZ) || defined(_MSC_VER)
+#define FAST_BITSCAN_REVERSE
+#endif
+
/*
* pg_leftmost_one_pos32
* Returns the position of the most significant set bit in "word",
@@ -36,7 +40,7 @@ pg_leftmost_one_pos32(uint32 word)
unsigned char non_zero; // XXX can this be bool?
#endif
-#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(FAST_BITSCAN_REVERSE) || defined(USE_ASSERT_CHECKING)
int result;
int shift = 32 - 8;
@@ -48,18 +52,18 @@ pg_leftmost_one_pos32(uint32 word)
result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif
-#if defined(HAVE__BUILTIN_CLZ)
- bitscan_result = 31 - __builtin_clz(word);
- Assert(bitscan_result == result);
- return bitscan_result;
-#elif defined(_MSC_VER)
+#ifdef FAST_BITSCAN_REVERSE
+#if defined(_MSC_VER)
non_zero = _BitScanReverse(&bitscan_result, word);
Assert(non_zero);
+#elif defined(HAVE__BUILTIN_CLZ)
+ bitscan_result = 31 - __builtin_clz(word);
+#endif
Assert(bitscan_result == result);
return bitscan_result;
#else
return result;
-#endif /* HAVE__BUILTIN_CLZ */
+#endif /* FAST_BITSCAN_REVERSE */
}
/*
@@ -76,7 +80,7 @@ pg_leftmost_one_pos64(uint64 word)
unsigned char non_zero; // XXX can this be bool?
#endif
-#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(FAST_BITSCAN_REVERSE) || defined(USE_ASSERT_CHECKING)
int result;
int shift = 64 - 8;
@@ -88,26 +92,30 @@ pg_leftmost_one_pos64(uint64 word)
result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif
-#if defined(HAVE__BUILTIN_CLZ)
+#ifdef FAST_BITSCAN_REVERSE
+#if defined(_MSC_VER)
+ non_zero = _BitScanReverse64(&bitscan_result, word);
+ Assert(non_zero);
+#elif defined(HAVE__BUILTIN_CLZ)
#if defined(HAVE_LONG_INT_64)
bitscan_result = 63 - __builtin_clzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
bitscan_result = 63 - __builtin_clzll(word);
#else
#error must have a working 64-bit integer datatype
-#endif /* HAVE_LONG_... */
- Assert(bitscan_result == result);
- return bitscan_result;
-#elif defined(_MSC_VER)
- non_zero = _BitScanReverse64(&bitscan_result, word);
- Assert(non_zero);
+#endif /* HAVE_LONG_INT_64 */
+#endif /* _MSC_VER */
Assert(bitscan_result == result);
return bitscan_result;
#else
return result;
-#endif /* HAVE__BUILTIN_CLZ */
+#endif /* FAST_BITSCAN_REVERSE */
}
+#if defined(HAVE__BUILTIN_CTZ) || defined(_MSC_VER)
+#define FAST_BITSCAN_FORWARD
+#endif
+
/*
* pg_rightmost_one_pos32
* Returns the position of the least significant set bit in "word",
@@ -125,7 +133,7 @@ pg_rightmost_one_pos32(uint32 word)
unsigned char non_zero; // XXX can this be bool?
#endif
-#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(FAST_BITSCAN_FORWARD) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -138,18 +146,18 @@ pg_rightmost_one_pos32(uint32 word)
result += pg_rightmost_one_pos[word & 255];
#endif
-#if defined(HAVE__BUILTIN_CTZ)
- bitscan_result = __builtin_ctz(orig_word);
- Assert(bitscan_result == result);
- return bitscan_result;
-#elif defined(_MSC_VER)
+#ifdef FAST_BITSCAN_FORWARD
+#if defined(_MSC_VER)
non_zero = _BitScanForward(&bitscan_result, orig_word);
Assert(non_zero);
+#elif defined(HAVE__BUILTIN_CTZ)
+ bitscan_result = __builtin_ctz(orig_word);
+#endif
Assert(bitscan_result == result);
return bitscan_result;
#else
return result;
-#endif /* HAVE__BUILTIN_CTZ */
+#endif /* FAST_BITSCAN_FORWARD */
}
/*
@@ -168,7 +176,7 @@ pg_rightmost_one_pos64(uint64 word)
unsigned char non_zero; // XXX can this be bool?
#endif
-#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(FAST_BITSCAN_FORWARD) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -181,24 +189,24 @@ pg_rightmost_one_pos64(uint64 word)
result += pg_rightmost_one_pos[word & 255];
#endif
-#ifdef HAVE__BUILTIN_CTZ
+#ifdef FAST_BITSCAN_FORWARD
+#if defined(_MSC_VER)
+ non_zero = _BitScanForward64(&bitscan_result, orig_word);
+ Assert(non_zero);
+#elif HAVE__BUILTIN_CTZ
#if defined(HAVE_LONG_INT_64)
bitscan_result = __builtin_ctzl(orig_word);
#elif defined(HAVE_LONG_LONG_INT_64)
bitscan_result = __builtin_ctzll(orig_word);
#else
#error must have a working 64-bit integer datatype
-#endif /* HAVE_LONG_... */
- Assert(bitscan_result == result);
- return bitscan_result;
-#elif defined(_MSC_VER)
- non_zero = _BitScanForward64(&bitscan_result, orig_word);
- Assert(non_zero);
+#endif /* HAVE_LONG_INT_64 */
+#endif /* _MSC_VER */
Assert(bitscan_result == result);
return bitscan_result;
#else
return result;
-#endif /* HAVE__BUILTIN_CTZ */
+#endif /* FAST_BITSCAN_FORWARD */
}
/*
--
2.39.0
