From c35c11a7aa7fd7c585268d05204cdb00efbb1852 Mon Sep 17 00:00:00 2001
From: Nikita Lapkov <nikita.lapkov@mongodb.com>
Date: Mon, 26 Apr 2021 16:03:55 +0000
Subject: SERVER-55601 Improve performance of Queries.CoveredBlockingSort
 benchmark in SBE

---
 src/mongo/platform/bits.h | 69 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)

(limited to 'src/mongo/platform')

diff --git a/src/mongo/platform/bits.h b/src/mongo/platform/bits.h
index b12bda75b3e..606ad9d830e 100644
--- a/src/mongo/platform/bits.h
+++ b/src/mongo/platform/bits.h
@@ -40,11 +40,25 @@ namespace mongo {
  */
 inline int countLeadingZeros64(unsigned long long num);
 
+/**
+ * Returns the number of leading 0-bits in num. The result is undefined if num is 0.
+ */
+inline int countLeadingZerosNonZero64(unsigned long long num);
+
 /**
  * Returns the number of trailing 0-bits in num. Returns 64 if num is 0.
  */
 inline int countTrailingZeros64(unsigned long long num);
 
+/**
+ * Returns the number of trailing 0-bits in num. The result is undefined if num is 0.
+ */
+inline int countTrailingZerosNonZero64(unsigned long long num);
+
+/**
+ * Same as above, but for int.
+ */
+inline int countTrailingZerosNonZero32(unsigned int num);
 
 #if defined(__GNUC__)
 int countLeadingZeros64(unsigned long long num) {
@@ -53,11 +67,24 @@ int countLeadingZeros64(unsigned long long num) {
     return __builtin_clzll(num);
 }
 
+int countLeadingZerosNonZero64(unsigned long long num) {
+    return __builtin_clzll(num);
+}
+
 int countTrailingZeros64(unsigned long long num) {
     if (num == 0)
         return 64;
     return __builtin_ctzll(num);
 }
+
+int countTrailingZerosNonZero64(unsigned long long num) {
+    return __builtin_ctzll(num);
+}
+
+int countTrailingZerosNonZero32(unsigned int num) {
+    return __builtin_ctz(num);
+}
+
 #elif defined(_MSC_VER) && defined(_WIN64)
 int countLeadingZeros64(unsigned long long num) {
     unsigned long out;
@@ -66,12 +93,31 @@ int countLeadingZeros64(unsigned long long num) {
     return 64;
 }
 
+int countLeadingZerosNonZero64(unsigned long long num) {
+    unsigned long out;
+    _BitScanReverse64(&out, num);
+    return 63 ^ out;
+}
+
 int countTrailingZeros64(unsigned long long num) {
     unsigned long out;
     if (_BitScanForward64(&out, num))
         return out;
     return 64;
 }
+
+int countTrailingZerosNonZero64(unsigned long long num) {
+    unsigned long out;
+    _BitScanForward64(&out, num);
+    return out;
+}
+
+int countTrailingZerosNonZero32(unsigned int num) {
+    unsigned long out;
+    _BitScanForward(&out, static_cast<unsigned long>(num));
+    return out;
+}
+
 #elif defined(_MSC_VER) && defined(_WIN32)
 int countLeadingZeros64(unsigned long long num) {
     unsigned long out;
@@ -82,6 +128,14 @@ int countLeadingZeros64(unsigned long long num) {
     return 64;
 }
 
+int countLeadingZerosNonZero64(unsigned long long num) {
+    unsigned long out;
+    if (_BitScanReverse(&out, static_cast<unsigned long>(num >> 32)))
+        return 31 ^ out;
+    _BitScanReverse(&out, static_cast<unsigned long>(num));
+    return 63 ^ out;
+}
+
 int countTrailingZeros64(unsigned long long num) {
     unsigned long out;
     if (_BitScanForward(&out, static_cast<unsigned long>(num)))
@@ -90,6 +144,21 @@ int countTrailingZeros64(unsigned long long num) {
         return out + 32;
     return 64;
 }
+
+int countTrailingZerosNonZero64(unsigned long long num) {
+    unsigned long out;
+    if (_BitScanForward(&out, static_cast<unsigned long>(num)))
+        return out;
+
+    _BitScanForward(&out, static_cast<unsigned long>(num >> 32));
+    return out + 32;
+}
+
+int countTrailingZerosNonZero32(unsigned int num) {
+    unsigned long out;
+    _BitScanForward(&out, static_cast<unsigned long>(num));
+    return out;
+}
 #else
 #error "No bit-ops definitions for your platform"
 #endif
-- 
cgit v1.2.1