From 02548aa013320689d38b906fa893a028f4cdfb6b Mon Sep 17 00:00:00 2001
From: Ben Maurer <bmaurer@fb.com>
Date: Mon, 24 Oct 2016 20:14:08 -0700
Subject: [PATCH] prevPowTwo / faster bit operations

Summary:
Add a prevPowTwo method to bits.h and optimize the current code for
GCCs output.

Reviewed By: ot

Differential Revision: D4072341

fbshipit-source-id: 6e949d0bfcf88ff8500022939d08a2b5aa9e00c9
---
 folly/Bits.h            | 23 ++++++++++++++++-------
 folly/test/BitsTest.cpp | 23 +++++++++++++++++++++++
 2 files changed, 39 insertions(+), 7 deletions(-)

diff --git a/folly/Bits.h b/folly/Bits.h
index 43ceb40a..9742a066 100644
--- a/folly/Bits.h
+++ b/folly/Bits.h
@@ -143,7 +143,9 @@ typename std::enable_if<
    sizeof(T) <= sizeof(unsigned int)),
   unsigned int>::type
   findLastSet(T x) {
-  return x ? 8 * sizeof(unsigned int) - __builtin_clz(x) : 0;
+  // If X is a power of two X - Y = ((X - 1) ^ Y) + 1. Doing this transformation
+  // allows GCC to remove its own xor that it adds to implement clz using bsr
+  return x ? ((8 * sizeof(unsigned int) - 1) ^ __builtin_clz(x)) + 1 : 0;
 }
 
 template <class T>
@@ -155,7 +157,7 @@ typename std::enable_if<
    sizeof(T) <= sizeof(unsigned long)),
   unsigned int>::type
   findLastSet(T x) {
-  return x ? 8 * sizeof(unsigned long) - __builtin_clzl(x) : 0;
+  return x ? ((8 * sizeof(unsigned long) - 1) ^ __builtin_clzl(x)) + 1 : 0;
 }
 
 template <class T>
@@ -167,7 +169,8 @@ typename std::enable_if<
    sizeof(T) <= sizeof(unsigned long long)),
   unsigned int>::type
   findLastSet(T x) {
-  return x ? 8 * sizeof(unsigned long long) - __builtin_clzll(x) : 0;
+  return x ? ((8 * sizeof(unsigned long long) - 1) ^ __builtin_clzll(x)) + 1
+           : 0;
 }
 
 template <class T>
@@ -190,10 +193,16 @@ nextPowTwo(T v) {
 }
 
 template <class T>
-inline constexpr
-typename std::enable_if<
-  std::is_integral<T>::value && std::is_unsigned<T>::value,
-  bool>::type
+inline FOLLY_INTRINSIC_CONSTEXPR typename std::
+    enable_if<std::is_integral<T>::value && std::is_unsigned<T>::value, T>::type
+    prevPowTwo(T v) {
+  return v ? (T(1) << (findLastSet(v) - 1)) : 0;
+}
+
+template <class T>
+inline constexpr typename std::enable_if<
+    std::is_integral<T>::value && std::is_unsigned<T>::value,
+    bool>::type
 isPowTwo(T v) {
   return (v != 0) && !(v & (v - 1));
 }
diff --git a/folly/test/BitsTest.cpp b/folly/test/BitsTest.cpp
index 4f6ed676..96abd60c 100644
--- a/folly/test/BitsTest.cpp
+++ b/folly/test/BitsTest.cpp
@@ -114,6 +114,29 @@ TEST(Bits, nextPowTwoClz) {
   EXPECT_EQ(1ull << 63, nextPowTwo((1ull << 62) + 1));
 }
 
+TEST(Bits, prevPowTwoClz) {
+  EXPECT_EQ(0, prevPowTwo(0u));
+  EXPECT_EQ(1, prevPowTwo(1u));
+  EXPECT_EQ(2, prevPowTwo(2u));
+  EXPECT_EQ(2, prevPowTwo(3u));
+  EXPECT_EQ(4, prevPowTwo(4u));
+  EXPECT_EQ(4, prevPowTwo(5u));
+  EXPECT_EQ(4, prevPowTwo(6u));
+  EXPECT_EQ(4, prevPowTwo(7u));
+  EXPECT_EQ(8, prevPowTwo(8u));
+  EXPECT_EQ(8, prevPowTwo(9u));
+  EXPECT_EQ(8, prevPowTwo(13u));
+  EXPECT_EQ(16, prevPowTwo(16u));
+  EXPECT_EQ(256, prevPowTwo(510u));
+  EXPECT_EQ(256, prevPowTwo(511u));
+  EXPECT_EQ(512, prevPowTwo(512u));
+  EXPECT_EQ(512, prevPowTwo(513u));
+  EXPECT_EQ(512, prevPowTwo(777u));
+  EXPECT_EQ(1ul << 30, prevPowTwo((1ul << 31) - 1));
+  EXPECT_EQ(1ull << 31, prevPowTwo((1ull << 32) - 1));
+  EXPECT_EQ(1ull << 62, prevPowTwo((1ull << 62) + 1));
+}
+
 TEST(Bits, isPowTwo) {
   EXPECT_FALSE(isPowTwo(0u));
   EXPECT_TRUE(isPowTwo(1ul));
-- 
2.34.1