From 51db2c217052fd6881b81f3ac5162fe88c36dbf0 Mon Sep 17 00:00:00 2001
From: Andreas Gampe <agampe@google.com>
Date: Thu, 13 Aug 2015 20:55:31 -0700
Subject: [PATCH] ART: DCHECK zero case for CLZ/CTZ

Add a DCHECK_CONSTEXPR. All current callers have an explicit
zero check before hand and so we should not trip this at the
moment. Remove the TODO.

Add the check for T being unsigned for CLZ (trivial fix for
leb128.h). We use CTZ with signed types.

Change-Id: I7bbf0b1699eed21715c6cc20dbfe22b7da403b1a
---
 runtime/base/bit_utils.h | 23 +++++++++++++++--------
 runtime/leb128.h         |  4 ++--
 2 files changed, 17 insertions(+), 10 deletions(-)

diff --git a/runtime/base/bit_utils.h b/runtime/base/bit_utils.h
index 6f45dc820..332012bda 100644
--- a/runtime/base/bit_utils.h
+++ b/runtime/base/bit_utils.h
@@ -29,21 +29,28 @@ namespace art {
 template<typename T>
 static constexpr int CLZ(T x) {
   static_assert(std::is_integral<T>::value, "T must be integral");
-  // TODO: assert unsigned. There is currently many uses with signed values.
+  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
   static_assert(sizeof(T) <= sizeof(long long),  // NOLINT [runtime/int] [4]
                 "T too large, must be smaller than long long");
-  return (sizeof(T) == sizeof(uint32_t))
-      ? __builtin_clz(x)  // TODO: __builtin_clz[ll] has undefined behavior for x=0
-      : __builtin_clzll(x);
+  return
+      DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0))
+      (sizeof(T) == sizeof(uint32_t))
+          ? __builtin_clz(x)
+          : __builtin_clzll(x);
 }
 
 template<typename T>
 static constexpr int CTZ(T x) {
   static_assert(std::is_integral<T>::value, "T must be integral");
-  // TODO: assert unsigned. There is currently many uses with signed values.
-  return (sizeof(T) == sizeof(uint32_t))
-      ? __builtin_ctz(x)
-      : __builtin_ctzll(x);
+  // A similar check to the above does not make sense. It isn't as non-intuitive to ask for
+  // trailing zeros in a negative number, and the quick backends do this for immediate encodings.
+  static_assert(sizeof(T) <= sizeof(long long),  // NOLINT [runtime/int] [4]
+                "T too large, must be smaller than long long");
+  return
+      DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0))
+      (sizeof(T) == sizeof(uint32_t))
+          ? __builtin_ctz(x)
+          : __builtin_ctzll(x);
 }
 
 template<typename T>
diff --git a/runtime/leb128.h b/runtime/leb128.h
index 14683d406..976936d63 100644
--- a/runtime/leb128.h
+++ b/runtime/leb128.h
@@ -101,7 +101,7 @@ static inline int32_t DecodeSignedLeb128(const uint8_t** data) {
 static inline uint32_t UnsignedLeb128Size(uint32_t data) {
   // bits_to_encode = (data != 0) ? 32 - CLZ(x) : 1  // 32 - CLZ(data | 1)
   // bytes = ceil(bits_to_encode / 7.0);             // (6 + bits_to_encode) / 7
-  uint32_t x = 6 + 32 - CLZ(data | 1);
+  uint32_t x = 6 + 32 - CLZ(data | 1U);
   // Division by 7 is done by (x * 37) >> 8 where 37 = ceil(256 / 7).
   // This works for 0 <= x < 256 / (7 * 37 - 256), i.e. 0 <= x <= 85.
   return (x * 37) >> 8;
@@ -111,7 +111,7 @@ static inline uint32_t UnsignedLeb128Size(uint32_t data) {
 static inline uint32_t SignedLeb128Size(int32_t data) {
   // Like UnsignedLeb128Size(), but we need one bit beyond the highest bit that differs from sign.
   data = data ^ (data >> 31);
-  uint32_t x = 1 /* we need to encode the sign bit */ + 6 + 32 - CLZ(data | 1);
+  uint32_t x = 1 /* we need to encode the sign bit */ + 6 + 32 - CLZ(data | 1U);
   return (x * 37) >> 8;
 }
 
-- 
2.11.0