From 3b8919b3c4121090183b40cd3fbcdeb81bf47645 Mon Sep 17 00:00:00 2001
From: Yedidya Feldblum <yfeldblum@fb.com>
Date: Tue, 26 Dec 2017 10:59:25 -0800
Subject: [PATCH] constexpr_log2_ceil

Summary: [Folly] `constexpr_log2_ceil`, like `constexpr_log2` but rounding up.

Reviewed By: Orvid

Differential Revision: D6636433

fbshipit-source-id: a10f031cc9c91cfeba7b74bbf143895a311ca772
---
 folly/ConstexprMath.h            | 10 +++++++++
 folly/test/ConstexprMathTest.cpp | 35 ++++++++++++++++++++++++++++++++
 2 files changed, 45 insertions(+)

diff --git a/folly/ConstexprMath.h b/folly/ConstexprMath.h
index 5b0bc51d..34f7664e 100644
--- a/folly/ConstexprMath.h
+++ b/folly/ConstexprMath.h
@@ -108,6 +108,11 @@ template <typename T>
 constexpr T constexpr_log2(T a, T e) {
   return e == T(1) ? a : constexpr_log2(a + T(1), e / T(2));
 }
+
+template <typename T>
+constexpr T constexpr_log2_ceil(T l2, T t) {
+  return l2 + T(T(1) << l2 < t ? 1 : 0);
+}
 } // namespace detail
 
 template <typename T>
@@ -115,6 +120,11 @@ constexpr T constexpr_log2(T t) {
   return detail::constexpr_log2(T(0), t);
 }
 
+template <typename T>
+constexpr T constexpr_log2_ceil(T t) {
+  return detail::constexpr_log2_ceil(constexpr_log2(t), t);
+}
+
 template <typename T>
 constexpr T constexpr_ceil(T t, T round) {
   return round == T(0)
diff --git a/folly/test/ConstexprMathTest.cpp b/folly/test/ConstexprMathTest.cpp
index 7b60e8f0..a0f9b102 100644
--- a/folly/test/ConstexprMathTest.cpp
+++ b/folly/test/ConstexprMathTest.cpp
@@ -123,6 +123,41 @@ TEST_F(ConstexprMathTest, constexpr_log2_64) {
   EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
 }
 
+TEST_F(ConstexprMathTest, constexpr_log2_ceil_1) {
+  constexpr auto v = 1ull;
+  constexpr auto a = folly::constexpr_log2_ceil(v);
+  EXPECT_EQ(0ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
+TEST_F(ConstexprMathTest, constexpr_log2_ceil_2) {
+  constexpr auto v = 2ull;
+  constexpr auto a = folly::constexpr_log2_ceil(v);
+  EXPECT_EQ(1ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
+TEST_F(ConstexprMathTest, constexpr_log2_ceil_3) {
+  constexpr auto v = 3ull;
+  constexpr auto a = folly::constexpr_log2_ceil(v);
+  EXPECT_EQ(2ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
+TEST_F(ConstexprMathTest, constexpr_log2_ceil_63) {
+  constexpr auto v = 63ull;
+  constexpr auto a = folly::constexpr_log2_ceil(v);
+  EXPECT_EQ(6ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
+TEST_F(ConstexprMathTest, constexpr_log2_ceil_64) {
+  constexpr auto v = 64ull;
+  constexpr auto a = folly::constexpr_log2_ceil(v);
+  EXPECT_EQ(6ull, a);
+  EXPECT_TRUE((std::is_same<decltype(v), decltype(a)>::value));
+}
+
 TEST_F(ConstexprMathTest, constexpr_ceil) {
   {
     constexpr auto roundable = 20ull;
-- 
2.34.1