Add some bit math helpers

Change-Id: I59ed76d52aa6346f46595faa9c7220b66a6a6964
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/100447
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: Lily Chen <chlily@google.com>

crypto/crypto_test.cc

diff --git a/crypto/crypto_test.cc b/crypto/crypto_test.cc
index 8658a3c..bbcabd4 100644
--- a/crypto/crypto_test.cc
+++ b/crypto/crypto_test.cc
@@ -56,6 +56,74 @@
             CRYPTO_bswap8(UINT64_C(0x0102030405060708)));
 }
 
+TEST(CryptoTest, BitWidth) {
+  EXPECT_EQ(CRYPTO_bit_width(0), 0);
+  EXPECT_EQ(CRYPTO_bit_width(1), 1);
+  EXPECT_EQ(CRYPTO_bit_width(2), 2);
+  EXPECT_EQ(CRYPTO_bit_width(3), 2);
+  EXPECT_EQ(CRYPTO_bit_width(4), 3);
+  EXPECT_EQ(CRYPTO_bit_width(5), 3);
+  EXPECT_EQ(CRYPTO_bit_width(6), 3);
+  EXPECT_EQ(CRYPTO_bit_width(7), 3);
+  EXPECT_EQ(CRYPTO_bit_width(8), 4);
+  EXPECT_EQ(CRYPTO_bit_width(~uint64_t{0}), 64);
+  EXPECT_EQ(CRYPTO_bit_width(~uint64_t{0} - 1), 64);
+}
+
+TEST(CryptoTest, Popcount) {
+  EXPECT_EQ(CRYPTO_popcount(0), 0);
+  EXPECT_EQ(CRYPTO_popcount(1), 1);
+  EXPECT_EQ(CRYPTO_popcount(2), 1);
+  EXPECT_EQ(CRYPTO_popcount(3), 2);
+  EXPECT_EQ(CRYPTO_popcount(4), 1);
+  EXPECT_EQ(CRYPTO_popcount(5), 2);
+  EXPECT_EQ(CRYPTO_popcount(6), 2);
+  EXPECT_EQ(CRYPTO_popcount(7), 3);
+  EXPECT_EQ(CRYPTO_popcount(8), 1);
+  EXPECT_EQ(CRYPTO_popcount(~uint64_t{0}), 64);
+  EXPECT_EQ(CRYPTO_popcount(~uint64_t{0} - 1), 63);
+}
+
+TEST(CryptoTest, BitCeil) {
+  EXPECT_EQ(CRYPTO_bit_ceil(0), 1u);
+  EXPECT_EQ(CRYPTO_bit_ceil(1), 1u);
+  EXPECT_EQ(CRYPTO_bit_ceil(2), 2u);
+  EXPECT_EQ(CRYPTO_bit_ceil(3), 4u);
+  EXPECT_EQ(CRYPTO_bit_ceil(4), 4u);
+  EXPECT_EQ(CRYPTO_bit_ceil(5), 8u);
+  EXPECT_EQ(CRYPTO_bit_ceil(6), 8u);
+  EXPECT_EQ(CRYPTO_bit_ceil(7), 8u);
+  EXPECT_EQ(CRYPTO_bit_ceil(8), 8u);
+  EXPECT_EQ(CRYPTO_bit_ceil(9), 16u);
+}
+
+TEST(CryptoTest, BitFloor) {
+  EXPECT_EQ(CRYPTO_bit_floor(0), 0u);
+  EXPECT_EQ(CRYPTO_bit_floor(1), 1u);
+  EXPECT_EQ(CRYPTO_bit_floor(2), 2u);
+  EXPECT_EQ(CRYPTO_bit_floor(3), 2u);
+  EXPECT_EQ(CRYPTO_bit_floor(4), 4u);
+  EXPECT_EQ(CRYPTO_bit_floor(5), 4u);
+  EXPECT_EQ(CRYPTO_bit_floor(6), 4u);
+  EXPECT_EQ(CRYPTO_bit_floor(7), 4u);
+  EXPECT_EQ(CRYPTO_bit_floor(8), 8u);
+  EXPECT_EQ(CRYPTO_bit_floor(9), 8u);
+}
+
+TEST(CryptoTest, HasSingleBit) {
+  EXPECT_FALSE(CRYPTO_has_single_bit(0));
+  EXPECT_TRUE(CRYPTO_has_single_bit(1));
+  EXPECT_TRUE(CRYPTO_has_single_bit(2));
+  EXPECT_FALSE(CRYPTO_has_single_bit(3));
+  EXPECT_TRUE(CRYPTO_has_single_bit(4));
+  EXPECT_FALSE(CRYPTO_has_single_bit(5));
+  EXPECT_FALSE(CRYPTO_has_single_bit(6));
+  EXPECT_FALSE(CRYPTO_has_single_bit(7));
+  EXPECT_TRUE(CRYPTO_has_single_bit(8));
+  EXPECT_FALSE(CRYPTO_has_single_bit(~uint64_t{0}));
+  EXPECT_TRUE(CRYPTO_has_single_bit(uint64_t{1} << 63));
+}
+
 #if defined(BORINGSSL_FIPS_COUNTERS)
 using CounterArray = size_t[fips_counter_max + 1];
 

crypto/internal.h

diff --git a/crypto/internal.h b/crypto/internal.h
index dda1933..e318a24 100644
--- a/crypto/internal.h
+++ b/crypto/internal.h
@@ -1025,6 +1025,60 @@
 }
 
 
+// Bit math functions.
+//
+// Polyfills for C++20.
+
+// CRYPTO_bit_width returns the smallest number of bits needed to represent `n`.
+// It returns zero if `n` is zero.
+inline int CRYPTO_bit_width(uint64_t n) {
+#if OPENSSL_HAS_BUILTIN(__builtin_clzll)
+  static_assert(sizeof(unsigned long long) >= sizeof(uint64_t));
+  return n ? (sizeof(unsigned long long) * 8 - __builtin_clzll(n)) : 0;
+#else
+  int width = 0;
+  while (n > 0) {
+    ++width;
+    n >>= 1;
+  }
+  return width;
+#endif
+}
+
+// CRYPTO_popcount returns the number of set bits in `n`'s binary
+// representation.
+inline int CRYPTO_popcount(uint64_t n) {
+#if OPENSSL_HAS_BUILTIN(__builtin_popcountll)
+  static_assert(sizeof(unsigned long long) >= sizeof(uint64_t));
+  return __builtin_popcountll(n);
+#else
+  int count = 0;
+  while (n > 0) {
+    n &= (n - 1);  // Clears the least significant bit that is set.
+    ++count;
+  }
+  return count;
+#endif
+}
+
+// CRYPTO_bit_ceil returns the smallest power of 2 that is greater than or equal
+// to `n`.
+inline uint64_t CRYPTO_bit_ceil(uint64_t n) {
+  return n ? uint64_t{1} << CRYPTO_bit_width(n - 1) : uint64_t{1};
+}
+
+// CRYPTO_bit_floor returns the largest power of 2 that is less than or equal to
+// `n`. It returns zero if `n` is zero.
+inline uint64_t CRYPTO_bit_floor(uint64_t n) {
+  return n ? (uint64_t{1} << (CRYPTO_bit_width(n) - 1)) : uint64_t{0};
+}
+
+// CRYPTO_has_single_bit returns whether `n` is an integral power of 2.
+inline bool CRYPTO_has_single_bit(uint64_t n) {
+  return CRYPTO_popcount(n) == 1;
+}
+
+
 // FIPS functions.
 
 #if defined(BORINGSSL_FIPS)