ART: Clean up arm64 kNumberOfXRegisters usage.

Avoid undefined behavior for arm64 stemming from 1u << 32 in
loops with upper bound kNumberOfXRegisters.

Create iterators for enumerating bits in an integer either
from high to low or from low to high and use them for
<arch>Context::FillCalleeSaves() on all architectures.

Refactor runtime/utils.{h,cc} by moving all bit-fiddling
functions to runtime/base/bit_utils.{h,cc} (together with
the new bit iterators) and all time-related functions to
runtime/base/time_utils.{h,cc}. Improve test coverage and
fix some corner cases for the bit-fiddling functions.

Bug: 13925192

(cherry picked from commit 80afd02024d20e60b197d3adfbb43cc303cf29e0)

Change-Id: I905257a21de90b5860ebe1e39563758f721eab82

15 files changed, 1157 insertions, 16 deletions

diff --git a/runtime/base/arena_allocator.h b/runtime/base/arena_allocator.h
index ab5968c..2e617b5 100644
--- a/runtime/base/arena_allocator.h
+++ b/runtime/base/arena_allocator.h
@@ -20,10 +20,10 @@
 #include <stdint.h>
 #include <stddef.h>
 
+#include "base/bit_utils.h"
 #include "debug_stack.h"
 #include "macros.h"
 #include "mutex.h"
-#include "utils.h"
 
 namespace art {
 
diff --git a/runtime/base/bit_utils.h b/runtime/base/bit_utils.h
new file mode 100644
index 0000000..7972158
--- /dev/null
+++ b/runtime/base/bit_utils.h
@@ -0,0 +1,337 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_BIT_UTILS_H_
+#define ART_RUNTIME_BASE_BIT_UTILS_H_
+
+#include <iterator>
+#include <limits>
+#include <type_traits>
+
+#include "base/logging.h"
+#include "base/iteration_range.h"
+
+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(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);
+}
+
+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);
+}
+
+template<typename T>
+static constexpr int POPCOUNT(T x) {
+  return (sizeof(T) == sizeof(uint32_t))
+      ? __builtin_popcount(x)
+      : __builtin_popcountll(x);
+}
+
+// Find the bit position of the most significant bit (0-based), or -1 if there were no bits set.
+template <typename T>
+static constexpr ssize_t MostSignificantBit(T value) {
+  static_assert(std::is_integral<T>::value, "T must be integral");
+  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+  static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
+  return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value);
+}
+
+// Find the bit position of the least significant bit (0-based), or -1 if there were no bits set.
+template <typename T>
+static constexpr ssize_t LeastSignificantBit(T value) {
+  static_assert(std::is_integral<T>::value, "T must be integral");
+  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+  return (value == 0) ? -1 : CTZ(value);
+}
+
+// How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc.
+template <typename T>
+static constexpr size_t MinimumBitsToStore(T value) {
+  return static_cast<size_t>(MostSignificantBit(value) + 1);
+}
+
+template <typename T>
+static constexpr inline T RoundUpToPowerOfTwo(T x) {
+  static_assert(std::is_integral<T>::value, "T must be integral");
+  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+  // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)).
+  return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u));
+}
+
+template<typename T>
+static constexpr bool IsPowerOfTwo(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 (x & (x - 1)) == 0;
+}
+
+template<typename T>
+static inline int WhichPowerOf2(T x) {
+  static_assert(std::is_integral<T>::value, "T must be integral");
+  // TODO: assert unsigned. There is currently many uses with signed values.
+  DCHECK((x != 0) && IsPowerOfTwo(x));
+  return CTZ(x);
+}
+
+// For rounding integers.
+// NOTE: In the absence of std::omit_from_type_deduction<T> or std::identity<T>, use std::decay<T>.
+template<typename T>
+static constexpr T RoundDown(T x, typename std::decay<T>::type n) WARN_UNUSED;
+
+template<typename T>
+static constexpr T RoundDown(T x, typename std::decay<T>::type n) {
+  return
+      DCHECK_CONSTEXPR(IsPowerOfTwo(n), , T(0))
+      (x & -n);
+}
+
+template<typename T>
+static constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED;
+
+template<typename T>
+static constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) {
+  return RoundDown(x + n - 1, n);
+}
+
+// For aligning pointers.
+template<typename T>
+static inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED;
+
+template<typename T>
+static inline T* AlignDown(T* x, uintptr_t n) {
+  return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n));
+}
+
+template<typename T>
+static inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED;
+
+template<typename T>
+static inline T* AlignUp(T* x, uintptr_t n) {
+  return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n));
+}
+
+template<int n, typename T>
+static inline bool IsAligned(T x) {
+  static_assert((n & (n - 1)) == 0, "n is not a power of two");
+  return (x & (n - 1)) == 0;
+}
+
+template<int n, typename T>
+static inline bool IsAligned(T* x) {
+  return IsAligned<n>(reinterpret_cast<const uintptr_t>(x));
+}
+
+template<typename T>
+static inline bool IsAlignedParam(T x, int n) {
+  return (x & (n - 1)) == 0;
+}
+
+#define CHECK_ALIGNED(value, alignment) \
+  CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
+
+#define DCHECK_ALIGNED(value, alignment) \
+  DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
+
+#define DCHECK_ALIGNED_PARAM(value, alignment) \
+  DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value)
+
+// Like sizeof, but count how many bits a type takes. Pass type explicitly.
+template <typename T>
+static constexpr size_t BitSizeOf() {
+  static_assert(std::is_integral<T>::value, "T must be integral");
+  typedef typename std::make_unsigned<T>::type unsigned_type;
+  static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!");
+  static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!");
+  return std::numeric_limits<unsigned_type>::digits;
+}
+
+// Like sizeof, but count how many bits a type takes. Infers type from parameter.
+template <typename T>
+static constexpr size_t BitSizeOf(T /*x*/) {
+  return BitSizeOf<T>();
+}
+
+static inline uint16_t Low16Bits(uint32_t value) {
+  return static_cast<uint16_t>(value);
+}
+
+static inline uint16_t High16Bits(uint32_t value) {
+  return static_cast<uint16_t>(value >> 16);
+}
+
+static inline uint32_t Low32Bits(uint64_t value) {
+  return static_cast<uint32_t>(value);
+}
+
+static inline uint32_t High32Bits(uint64_t value) {
+  return static_cast<uint32_t>(value >> 32);
+}
+
+// Check whether an N-bit two's-complement representation can hold value.
+template <typename T>
+static inline bool IsInt(size_t N, T value) {
+  if (N == BitSizeOf<T>()) {
+    return true;
+  } else {
+    CHECK_LT(0u, N);
+    CHECK_LT(N, BitSizeOf<T>());
+    T limit = static_cast<T>(1) << (N - 1u);
+    return (-limit <= value) && (value < limit);
+  }
+}
+
+template <typename T>
+static constexpr T GetIntLimit(size_t bits) {
+  return
+      DCHECK_CONSTEXPR(bits > 0, "bits cannot be zero", 0)
+      DCHECK_CONSTEXPR(bits < BitSizeOf<T>(), "kBits must be < max.", 0)
+      static_cast<T>(1) << (bits - 1);
+}
+
+template <size_t kBits, typename T>
+static constexpr bool IsInt(T value) {
+  static_assert(kBits > 0, "kBits cannot be zero.");
+  static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
+  static_assert(std::is_signed<T>::value, "Needs a signed type.");
+  // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
+  // trivially true.
+  return (kBits == BitSizeOf<T>()) ?
+      true :
+      (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits));
+}
+
+template <size_t kBits, typename T>
+static constexpr bool IsUint(T value) {
+  static_assert(kBits > 0, "kBits cannot be zero.");
+  static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
+  static_assert(std::is_integral<T>::value, "Needs an integral type.");
+  // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
+  // trivially true.
+  // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(),
+  // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows.
+  return (0 <= value) &&
+      (kBits == BitSizeOf<T>() ||
+          (static_cast<typename std::make_unsigned<T>::type>(value) <=
+               GetIntLimit<typename std::make_unsigned<T>::type>(kBits) * 2u - 1u));
+}
+
+template <size_t kBits, typename T>
+static constexpr bool IsAbsoluteUint(T value) {
+  static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
+  static_assert(std::is_integral<T>::value, "Needs an integral type.");
+  typedef typename std::make_unsigned<T>::type unsigned_type;
+  return (kBits == BitSizeOf<T>())
+      ? true
+      : IsUint<kBits>(value < 0
+                      ? static_cast<unsigned_type>(-1 - value) + 1u  // Avoid overflow.
+                      : static_cast<unsigned_type>(value));
+}
+
+// Using the Curiously Recurring Template Pattern to implement everything shared
+// by LowToHighBitIterator and HighToLowBitIterator, i.e. everything but operator*().
+template <typename T, typename Iter>
+class BitIteratorBase
+    : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, void> {
+  static_assert(std::is_integral<T>::value, "T must be integral");
+  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+
+  static_assert(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t), "Unsupported size");
+
+ public:
+  BitIteratorBase() : bits_(0u) { }
+  explicit BitIteratorBase(T bits) : bits_(bits) { }
+
+  Iter& operator++() {
+    DCHECK_NE(bits_, 0u);
+    uint32_t bit = *static_cast<Iter&>(*this);
+    bits_ &= ~(static_cast<T>(1u) << bit);
+    return static_cast<Iter&>(*this);
+  }
+
+  Iter& operator++(int) {
+    Iter tmp(static_cast<Iter&>(*this));
+    ++*this;
+    return tmp;
+  }
+
+ protected:
+  T bits_;
+
+  template <typename U, typename I>
+  friend bool operator==(const BitIteratorBase<U, I>& lhs, const BitIteratorBase<U, I>& rhs);
+};
+
+template <typename T, typename Iter>
+bool operator==(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) {
+  return lhs.bits_ == rhs.bits_;
+}
+
+template <typename T, typename Iter>
+bool operator!=(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) {
+  return !(lhs == rhs);
+}
+
+template <typename T>
+class LowToHighBitIterator : public BitIteratorBase<T, LowToHighBitIterator<T>> {
+ public:
+  using BitIteratorBase<T, LowToHighBitIterator<T>>::BitIteratorBase;
+
+  uint32_t operator*() const {
+    DCHECK_NE(this->bits_, 0u);
+    return CTZ(this->bits_);
+  }
+};
+
+template <typename T>
+class HighToLowBitIterator : public BitIteratorBase<T, HighToLowBitIterator<T>> {
+ public:
+  using BitIteratorBase<T, HighToLowBitIterator<T>>::BitIteratorBase;
+
+  uint32_t operator*() const {
+    DCHECK_NE(this->bits_, 0u);
+    static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
+    return std::numeric_limits<T>::digits - 1u - CLZ(this->bits_);
+  }
+};
+
+template <typename T>
+IterationRange<LowToHighBitIterator<T>> LowToHighBits(T bits) {
+  return IterationRange<LowToHighBitIterator<T>>(
+      LowToHighBitIterator<T>(bits), LowToHighBitIterator<T>());
+}
+
+template <typename T>
+IterationRange<HighToLowBitIterator<T>> HighToLowBits(T bits) {
+  return IterationRange<HighToLowBitIterator<T>>(
+      HighToLowBitIterator<T>(bits), HighToLowBitIterator<T>());
+}
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_BIT_UTILS_H_
diff --git a/runtime/base/bit_utils_test.cc b/runtime/base/bit_utils_test.cc
new file mode 100644
index 0000000..77bd0b8
--- /dev/null
+++ b/runtime/base/bit_utils_test.cc
@@ -0,0 +1,400 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vector>
+
+#include "bit_utils.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+// NOTE: CLZ(0u) is undefined.
+static_assert(31 == CLZ<uint32_t>(1u), "TestCLZ32#1");
+static_assert(30 == CLZ<uint32_t>(2u), "TestCLZ32#2");
+static_assert(16 == CLZ<uint32_t>(0x00008765u), "TestCLZ32#3");
+static_assert(15 == CLZ<uint32_t>(0x00012345u), "TestCLZ32#4");
+static_assert(1 == CLZ<uint32_t>(0x43214321u), "TestCLZ32#5");
+static_assert(0 == CLZ<uint32_t>(0x87654321u), "TestCLZ32#6");
+
+// NOTE: CLZ(0ull) is undefined.
+static_assert(63 == CLZ<uint64_t>(UINT64_C(1)), "TestCLZ64#1");
+static_assert(62 == CLZ<uint64_t>(UINT64_C(3)), "TestCLZ64#2");
+static_assert(48 == CLZ<uint64_t>(UINT64_C(0x00008765)), "TestCLZ64#3");
+static_assert(32 == CLZ<uint64_t>(UINT64_C(0x87654321)), "TestCLZ64#4");
+static_assert(31 == CLZ<uint64_t>(UINT64_C(0x123456789)), "TestCLZ64#5");
+static_assert(16 == CLZ<uint64_t>(UINT64_C(0x876543211234)), "TestCLZ64#6");
+static_assert(1 == CLZ<uint64_t>(UINT64_C(0x4321432187654321)), "TestCLZ64#7");
+static_assert(0 == CLZ<uint64_t>(UINT64_C(0x8765432187654321)), "TestCLZ64#8");
+
+// NOTE: CTZ(0u) is undefined.
+static_assert(0 == CTZ<uint32_t>(1u), "TestCTZ32#1");
+static_assert(1 == CTZ<uint32_t>(2u), "TestCTZ32#2");
+static_assert(15 == CTZ<uint32_t>(0x45678000u), "TestCTZ32#3");
+static_assert(16 == CTZ<uint32_t>(0x43210000u), "TestCTZ32#4");
+static_assert(30 == CTZ<uint32_t>(0xc0000000u), "TestCTZ32#5");
+static_assert(31 == CTZ<uint32_t>(0x80000000u), "TestCTZ32#6");
+
+// NOTE: CTZ(0ull) is undefined.
+static_assert(0 == CTZ<uint64_t>(UINT64_C(1)), "TestCTZ64#1");
+static_assert(1 == CTZ<uint64_t>(UINT64_C(2)), "TestCTZ64#2");
+static_assert(16 == CTZ<uint64_t>(UINT64_C(0x43210000)), "TestCTZ64#3");
+static_assert(31 == CTZ<uint64_t>(UINT64_C(0x80000000)), "TestCTZ64#4");
+static_assert(32 == CTZ<uint64_t>(UINT64_C(0x8765432100000000)), "TestCTZ64#5");
+static_assert(48 == CTZ<uint64_t>(UINT64_C(0x4321000000000000)), "TestCTZ64#6");
+static_assert(62 == CTZ<uint64_t>(UINT64_C(0x4000000000000000)), "TestCTZ64#7");
+static_assert(63 == CTZ<uint64_t>(UINT64_C(0x8000000000000000)), "TestCTZ64#8");
+
+static_assert(0 == POPCOUNT<uint32_t>(0u), "TestPOPCOUNT32#1");
+static_assert(1 == POPCOUNT<uint32_t>(8u), "TestPOPCOUNT32#2");
+static_assert(15 == POPCOUNT<uint32_t>(0x55555554u), "TestPOPCOUNT32#3");
+static_assert(16 == POPCOUNT<uint32_t>(0xaaaaaaaau), "TestPOPCOUNT32#4");
+static_assert(31 == POPCOUNT<uint32_t>(0xfffffffeu), "TestPOPCOUNT32#5");
+static_assert(32 == POPCOUNT<uint32_t>(0xffffffffu), "TestPOPCOUNT32#6");
+
+static_assert(0 == POPCOUNT<uint64_t>(UINT64_C(0)), "TestPOPCOUNT64#1");
+static_assert(1 == POPCOUNT<uint64_t>(UINT64_C(0x40000)), "TestPOPCOUNT64#2");
+static_assert(16 == POPCOUNT<uint64_t>(UINT64_C(0x1414141482828282)), "TestPOPCOUNT64#3");
+static_assert(31 == POPCOUNT<uint64_t>(UINT64_C(0x0000ffff00007fff)), "TestPOPCOUNT64#4");
+static_assert(32 == POPCOUNT<uint64_t>(UINT64_C(0x5555555555555555)), "TestPOPCOUNT64#5");
+static_assert(48 == POPCOUNT<uint64_t>(UINT64_C(0x7777bbbbddddeeee)), "TestPOPCOUNT64#6");
+static_assert(63 == POPCOUNT<uint64_t>(UINT64_C(0x7fffffffffffffff)), "TestPOPCOUNT64#7");
+static_assert(64 == POPCOUNT<uint64_t>(UINT64_C(0xffffffffffffffff)), "TestPOPCOUNT64#8");
+
+static_assert(-1 == MostSignificantBit<uint32_t>(0u), "TestMSB32#1");
+static_assert(0 == MostSignificantBit<uint32_t>(1u), "TestMSB32#2");
+static_assert(31 == MostSignificantBit<uint32_t>(~static_cast<uint32_t>(0u)), "TestMSB32#3");
+static_assert(2 == MostSignificantBit<uint32_t>(0b110), "TestMSB32#4");
+static_assert(2 == MostSignificantBit<uint32_t>(0b100), "TestMSB32#5");
+
+static_assert(-1 == MostSignificantBit<uint64_t>(UINT64_C(0)), "TestMSB64#1");
+static_assert(0 == MostSignificantBit<uint64_t>(UINT64_C(1)), "TestMSB64#2");
+static_assert(63 == MostSignificantBit<uint64_t>(~UINT64_C(0)), "TestMSB64#3");
+static_assert(34 == MostSignificantBit<uint64_t>(UINT64_C(0x700000000)), "TestMSB64#4");
+static_assert(34 == MostSignificantBit<uint64_t>(UINT64_C(0x777777777)), "TestMSB64#5");
+
+static_assert(-1 == LeastSignificantBit<uint32_t>(0u), "TestLSB32#1");
+static_assert(0 == LeastSignificantBit<uint32_t>(1u), "TestLSB32#1");
+static_assert(0 == LeastSignificantBit<uint32_t>(~static_cast<uint32_t>(0u)), "TestLSB32#1");
+static_assert(1 == LeastSignificantBit<uint32_t>(0b110), "TestLSB32#1");
+static_assert(2 == LeastSignificantBit<uint32_t>(0b100), "TestLSB32#1");
+
+static_assert(-1 == LeastSignificantBit<uint64_t>(UINT64_C(0)), "TestLSB64#1");
+static_assert(0 == LeastSignificantBit<uint64_t>(UINT64_C(1)), "TestLSB64#2");
+static_assert(0 == LeastSignificantBit<uint64_t>(~UINT64_C(0)), "TestLSB64#3");
+static_assert(12 == LeastSignificantBit<uint64_t>(UINT64_C(0x5000)), "TestLSB64#4");
+static_assert(48 == LeastSignificantBit<uint64_t>(UINT64_C(0x5555000000000000)), "TestLSB64#5");
+
+static_assert(0u == MinimumBitsToStore<uint32_t>(0u), "TestMinBits2Store32#1");
+static_assert(1u == MinimumBitsToStore<uint32_t>(1u), "TestMinBits2Store32#2");
+static_assert(2u == MinimumBitsToStore<uint32_t>(0b10u), "TestMinBits2Store32#3");
+static_assert(2u == MinimumBitsToStore<uint32_t>(0b11u), "TestMinBits2Store32#4");
+static_assert(3u == MinimumBitsToStore<uint32_t>(0b100u), "TestMinBits2Store32#5");
+static_assert(3u == MinimumBitsToStore<uint32_t>(0b110u), "TestMinBits2Store32#6");
+static_assert(3u == MinimumBitsToStore<uint32_t>(0b101u), "TestMinBits2Store32#7");
+static_assert(8u == MinimumBitsToStore<uint32_t>(0xFFu), "TestMinBits2Store32#8");
+static_assert(32u == MinimumBitsToStore<uint32_t>(~static_cast<uint32_t>(0u)),
+              "TestMinBits2Store32#9");
+
+static_assert(0u == MinimumBitsToStore<uint64_t>(UINT64_C(0)), "TestMinBits2Store64#1");
+static_assert(1u == MinimumBitsToStore<uint64_t>(UINT64_C(1)), "TestMinBits2Store64#2");
+static_assert(2u == MinimumBitsToStore<uint64_t>(UINT64_C(0b10)), "TestMinBits2Store64#3");
+static_assert(2u == MinimumBitsToStore<uint64_t>(UINT64_C(0b11)), "TestMinBits2Store64#4");
+static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b100)), "TestMinBits2Store64#5");
+static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b110)), "TestMinBits2Store64#6");
+static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b101)), "TestMinBits2Store64#7");
+static_assert(8u == MinimumBitsToStore<uint64_t>(UINT64_C(0xFF)), "TestMinBits2Store64#8");
+static_assert(32u == MinimumBitsToStore<uint64_t>(UINT64_C(0xFFFFFFFF)), "TestMinBits2Store64#9");
+static_assert(33u == MinimumBitsToStore<uint64_t>(UINT64_C(0x1FFFFFFFF)), "TestMinBits2Store64#10");
+static_assert(64u == MinimumBitsToStore<uint64_t>(~UINT64_C(0)), "TestMinBits2Store64#11");
+
+static_assert(0 == RoundUpToPowerOfTwo<uint32_t>(0u), "TestRoundUpPowerOfTwo32#1");
+static_assert(1 == RoundUpToPowerOfTwo<uint32_t>(1u), "TestRoundUpPowerOfTwo32#2");
+static_assert(2 == RoundUpToPowerOfTwo<uint32_t>(2u), "TestRoundUpPowerOfTwo32#3");
+static_assert(4 == RoundUpToPowerOfTwo<uint32_t>(3u), "TestRoundUpPowerOfTwo32#4");
+static_assert(8 == RoundUpToPowerOfTwo<uint32_t>(7u), "TestRoundUpPowerOfTwo32#5");
+static_assert(0x40000u == RoundUpToPowerOfTwo<uint32_t>(0x2aaaau),
+              "TestRoundUpPowerOfTwo32#6");
+static_assert(0x80000000u == RoundUpToPowerOfTwo<uint32_t>(0x40000001u),
+              "TestRoundUpPowerOfTwo32#7");
+static_assert(0x80000000u == RoundUpToPowerOfTwo<uint32_t>(0x80000000u),
+              "TestRoundUpPowerOfTwo32#8");
+
+static_assert(0 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0)), "TestRoundUpPowerOfTwo64#1");
+static_assert(1 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(1)), "TestRoundUpPowerOfTwo64#2");
+static_assert(2 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(2)), "TestRoundUpPowerOfTwo64#3");
+static_assert(4 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(3)), "TestRoundUpPowerOfTwo64#4");
+static_assert(8 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(7)), "TestRoundUpPowerOfTwo64#5");
+static_assert(UINT64_C(0x40000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x2aaaa)),
+              "TestRoundUpPowerOfTwo64#6");
+static_assert(
+    UINT64_C(0x8000000000000000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x4000000000000001)),
+    "TestRoundUpPowerOfTwo64#7");
+static_assert(
+    UINT64_C(0x8000000000000000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x8000000000000000)),
+    "TestRoundUpPowerOfTwo64#8");
+
+static constexpr int64_t kInt32MinMinus1 =
+    static_cast<int64_t>(std::numeric_limits<int32_t>::min()) - 1;
+static constexpr int64_t kInt32MaxPlus1 =
+    static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + 1;
+static constexpr int64_t kUint32MaxPlus1 =
+    static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 1;
+
+TEST(BitUtilsTest, TestIsInt32) {
+  EXPECT_FALSE(IsInt<int32_t>(1, -2));
+  EXPECT_TRUE(IsInt<int32_t>(1, -1));
+  EXPECT_TRUE(IsInt<int32_t>(1, 0));
+  EXPECT_FALSE(IsInt<int32_t>(1, 1));
+  EXPECT_FALSE(IsInt<int32_t>(4, -9));
+  EXPECT_TRUE(IsInt<int32_t>(4, -8));
+  EXPECT_TRUE(IsInt<int32_t>(4, 7));
+  EXPECT_FALSE(IsInt<int32_t>(4, 8));
+  EXPECT_FALSE(IsInt<int32_t>(31, std::numeric_limits<int32_t>::min()));
+  EXPECT_FALSE(IsInt<int32_t>(31, std::numeric_limits<int32_t>::max()));
+  EXPECT_TRUE(IsInt<int32_t>(32, std::numeric_limits<int32_t>::min()));
+  EXPECT_TRUE(IsInt<int32_t>(32, std::numeric_limits<int32_t>::max()));
+}
+
+TEST(BitUtilsTest, TestIsInt64) {
+  EXPECT_FALSE(IsInt<int64_t>(1, -2));
+  EXPECT_TRUE(IsInt<int64_t>(1, -1));
+  EXPECT_TRUE(IsInt<int64_t>(1, 0));
+  EXPECT_FALSE(IsInt<int64_t>(1, 1));
+  EXPECT_FALSE(IsInt<int64_t>(4, -9));
+  EXPECT_TRUE(IsInt<int64_t>(4, -8));
+  EXPECT_TRUE(IsInt<int64_t>(4, 7));
+  EXPECT_FALSE(IsInt<int64_t>(4, 8));
+  EXPECT_FALSE(IsInt<int64_t>(31, std::numeric_limits<int32_t>::min()));
+  EXPECT_FALSE(IsInt<int64_t>(31, std::numeric_limits<int32_t>::max()));
+  EXPECT_TRUE(IsInt<int64_t>(32, std::numeric_limits<int32_t>::min()));
+  EXPECT_TRUE(IsInt<int64_t>(32, std::numeric_limits<int32_t>::max()));
+  EXPECT_FALSE(IsInt<int64_t>(32, kInt32MinMinus1));
+  EXPECT_FALSE(IsInt<int64_t>(32, kInt32MaxPlus1));
+  EXPECT_FALSE(IsInt<int64_t>(63, std::numeric_limits<int64_t>::min()));
+  EXPECT_FALSE(IsInt<int64_t>(63, std::numeric_limits<int64_t>::max()));
+  EXPECT_TRUE(IsInt<int64_t>(64, std::numeric_limits<int64_t>::min()));
+  EXPECT_TRUE(IsInt<int64_t>(64, std::numeric_limits<int64_t>::max()));
+}
+
+static_assert(!IsInt<1, int32_t>(-2), "TestIsInt32#1");
+static_assert(IsInt<1, int32_t>(-1), "TestIsInt32#2");
+static_assert(IsInt<1, int32_t>(0), "TestIsInt32#3");
+static_assert(!IsInt<1, int32_t>(1), "TestIsInt32#4");
+static_assert(!IsInt<4, int32_t>(-9), "TestIsInt32#5");
+static_assert(IsInt<4, int32_t>(-8), "TestIsInt32#6");
+static_assert(IsInt<4, int32_t>(7), "TestIsInt32#7");
+static_assert(!IsInt<4, int32_t>(8), "TestIsInt32#8");
+static_assert(!IsInt<31, int32_t>(std::numeric_limits<int32_t>::min()), "TestIsInt32#9");
+static_assert(!IsInt<31, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsInt32#10");
+static_assert(IsInt<32, int32_t>(std::numeric_limits<int32_t>::min()), "TestIsInt32#11");
+static_assert(IsInt<32, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsInt32#12");
+
+static_assert(!IsInt<1, int64_t>(-2), "TestIsInt64#1");
+static_assert(IsInt<1, int64_t>(-1), "TestIsInt64#2");
+static_assert(IsInt<1, int64_t>(0), "TestIsInt64#3");
+static_assert(!IsInt<1, int64_t>(1), "TestIsInt64#4");
+static_assert(!IsInt<4, int64_t>(-9), "TestIsInt64#5");
+static_assert(IsInt<4, int64_t>(-8), "TestIsInt64#6");
+static_assert(IsInt<4, int64_t>(7), "TestIsInt64#7");
+static_assert(!IsInt<4, int64_t>(8), "TestIsInt64#8");
+static_assert(!IsInt<31, int64_t>(std::numeric_limits<int32_t>::min()), "TestIsInt64#9");
+static_assert(!IsInt<31, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsInt64#10");
+static_assert(IsInt<32, int64_t>(std::numeric_limits<int32_t>::min()), "TestIsInt64#11");
+static_assert(IsInt<32, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsInt64#12");
+static_assert(!IsInt<32, int64_t>(kInt32MinMinus1), "TestIsInt64#13");
+static_assert(!IsInt<32, int64_t>(kInt32MaxPlus1), "TestIsInt64#14");
+static_assert(!IsInt<63, int64_t>(std::numeric_limits<int64_t>::min()), "TestIsInt64#15");
+static_assert(!IsInt<63, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsInt64#16");
+static_assert(IsInt<64, int64_t>(std::numeric_limits<int64_t>::min()), "TestIsInt64#17");
+static_assert(IsInt<64, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsInt64#18");
+
+static_assert(!IsUint<1, int32_t>(-1), "TestIsUint32#1");
+static_assert(IsUint<1, int32_t>(0), "TestIsUint32#2");
+static_assert(IsUint<1, int32_t>(1), "TestIsUint32#3");
+static_assert(!IsUint<1, int32_t>(2), "TestIsUint32#4");
+static_assert(!IsUint<4, int32_t>(-1), "TestIsUint32#5");
+static_assert(IsUint<4, int32_t>(0), "TestIsUint32#6");
+static_assert(IsUint<4, int32_t>(15), "TestIsUint32#7");
+static_assert(!IsUint<4, int32_t>(16), "TestIsUint32#8");
+static_assert(!IsUint<30, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsUint32#9");
+static_assert(IsUint<31, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsUint32#10");
+static_assert(!IsUint<32, int32_t>(-1), "TestIsUint32#11");
+static_assert(IsUint<32, int32_t>(0), "TestIsUint32#11");
+static_assert(IsUint<32, uint32_t>(static_cast<uint32_t>(-1)), "TestIsUint32#12");
+
+static_assert(!IsUint<1, int64_t>(-1), "TestIsUint64#1");
+static_assert(IsUint<1, int64_t>(0), "TestIsUint64#2");
+static_assert(IsUint<1, int64_t>(1), "TestIsUint64#3");
+static_assert(!IsUint<1, int64_t>(2), "TestIsUint64#4");
+static_assert(!IsUint<4, int64_t>(-1), "TestIsUint64#5");
+static_assert(IsUint<4, int64_t>(0), "TestIsUint64#6");
+static_assert(IsUint<4, int64_t>(15), "TestIsUint64#7");
+static_assert(!IsUint<4, int64_t>(16), "TestIsUint64#8");
+static_assert(!IsUint<30, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsUint64#9");
+static_assert(IsUint<31, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsUint64#10");
+static_assert(!IsUint<62, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsUint64#11");
+static_assert(IsUint<63, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsUint64#12");
+static_assert(!IsUint<64, int64_t>(-1), "TestIsUint64#13");
+static_assert(IsUint<64, int64_t>(0), "TestIsUint64#14");
+static_assert(IsUint<64, uint64_t>(static_cast<uint32_t>(-1)), "TestIsUint64#15");
+
+static_assert(!IsAbsoluteUint<1, int32_t>(-2), "TestIsAbsoluteUint32#1");
+static_assert(IsAbsoluteUint<1, int32_t>(-1), "TestIsAbsoluteUint32#2");
+static_assert(IsAbsoluteUint<1, int32_t>(0), "TestIsAbsoluteUint32#3");
+static_assert(IsAbsoluteUint<1, int32_t>(1), "TestIsAbsoluteUint32#4");
+static_assert(!IsAbsoluteUint<1, int32_t>(2), "TestIsAbsoluteUint32#5");
+static_assert(!IsAbsoluteUint<4, int32_t>(-16), "TestIsAbsoluteUint32#6");
+static_assert(IsAbsoluteUint<4, int32_t>(-15), "TestIsAbsoluteUint32#7");
+static_assert(IsAbsoluteUint<4, int32_t>(0), "TestIsAbsoluteUint32#8");
+static_assert(IsAbsoluteUint<4, int32_t>(15), "TestIsAbsoluteUint32#9");
+static_assert(!IsAbsoluteUint<4, int32_t>(16), "TestIsAbsoluteUint32#10");
+static_assert(!IsAbsoluteUint<30, int32_t>(std::numeric_limits<int32_t>::max()),
+              "TestIsAbsoluteUint32#11");
+static_assert(IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::max()),
+              "TestIsAbsoluteUint32#12");
+static_assert(!IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::min()),
+              "TestIsAbsoluteUint32#13");
+static_assert(IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::min() + 1),
+              "TestIsAbsoluteUint32#14");
+static_assert(IsAbsoluteUint<32, int32_t>(std::numeric_limits<int32_t>::max()),
+              "TestIsAbsoluteUint32#15");
+static_assert(IsAbsoluteUint<32, int32_t>(std::numeric_limits<int32_t>::min()),
+              "TestIsAbsoluteUint32#16");
+static_assert(IsAbsoluteUint<32, int32_t>(0), "TestIsAbsoluteUint32#17");
+
+static_assert(!IsAbsoluteUint<1, int64_t>(-2), "TestIsAbsoluteUint64#1");
+static_assert(IsAbsoluteUint<1, int64_t>(-1), "TestIsAbsoluteUint64#2");
+static_assert(IsAbsoluteUint<1, int64_t>(0), "TestIsAbsoluteUint64#3");
+static_assert(IsAbsoluteUint<1, int64_t>(1), "TestIsAbsoluteUint64#4");
+static_assert(!IsAbsoluteUint<1, int64_t>(2), "TestIsAbsoluteUint64#5");
+static_assert(!IsAbsoluteUint<4, int64_t>(-16), "TestIsAbsoluteUint64#6");
+static_assert(IsAbsoluteUint<4, int64_t>(-15), "TestIsAbsoluteUint64#7");
+static_assert(IsAbsoluteUint<4, int64_t>(0), "TestIsAbsoluteUint64#8");
+static_assert(IsAbsoluteUint<4, int64_t>(15), "TestIsAbsoluteUint64#9");
+static_assert(!IsAbsoluteUint<4, int64_t>(16), "TestIsAbsoluteUint64#10");
+static_assert(!IsAbsoluteUint<30, int64_t>(std::numeric_limits<int32_t>::max()),
+              "TestIsAbsoluteUint64#11");
+static_assert(IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::max()),
+              "TestIsAbsoluteUint64#12");
+static_assert(!IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::min()),
+              "TestIsAbsoluteUint64#13");
+static_assert(IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::min() + 1),
+              "TestIsAbsoluteUint64#14");
+static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<int32_t>::max()),
+              "TestIsAbsoluteUint64#15");
+static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<int32_t>::min()),
+              "TestIsAbsoluteUint64#16");
+static_assert(!IsAbsoluteUint<62, int64_t>(std::numeric_limits<int64_t>::max()),
+              "TestIsAbsoluteUint64#17");
+static_assert(IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::max()),
+              "TestIsAbsoluteUint64#18");
+static_assert(!IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::min()),
+              "TestIsAbsoluteUint64#19");
+static_assert(IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::min() + 1),
+              "TestIsAbsoluteUint64#20");
+static_assert(IsAbsoluteUint<64, int64_t>(std::numeric_limits<int64_t>::max()),
+              "TestIsAbsoluteUint64#21");
+static_assert(IsAbsoluteUint<64, int64_t>(std::numeric_limits<int64_t>::min()),
+              "TestIsAbsoluteUint64#22");
+static_assert(!IsAbsoluteUint<32, int64_t>(-kUint32MaxPlus1), "TestIsAbsoluteUint64#23");
+static_assert(IsAbsoluteUint<32, int64_t>(-kUint32MaxPlus1 + 1), "TestIsAbsoluteUint64#24");
+static_assert(IsAbsoluteUint<32, int64_t>(0), "TestIsAbsoluteUint64#25");
+static_assert(IsAbsoluteUint<64, int64_t>(0), "TestIsAbsoluteUint64#26");
+static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<uint32_t>::max()),
+              "TestIsAbsoluteUint64#27");
+static_assert(!IsAbsoluteUint<32, int64_t>(kUint32MaxPlus1), "TestIsAbsoluteUint64#28");
+
+template <typename Container>
+void CheckElements(const std::initializer_list<uint32_t>& expected, const Container& elements) {
+  auto expected_it = expected.begin();
+  auto element_it = elements.begin();
+  size_t idx = 0u;
+  while (expected_it != expected.end() && element_it != elements.end()) {
+    EXPECT_EQ(*expected_it, *element_it) << idx;
+    ++idx;
+    ++expected_it;
+    ++element_it;
+  }
+  ASSERT_TRUE(expected_it == expected.end() && element_it == elements.end())
+      << std::boolalpha << (expected_it == expected.end()) << " " << (element_it == elements.end());
+}
+
+TEST(BitUtilsTest, TestLowToHighBits32) {
+  CheckElements({}, LowToHighBits<uint32_t>(0u));
+  CheckElements({0}, LowToHighBits<uint32_t>(1u));
+  CheckElements({15}, LowToHighBits<uint32_t>(0x8000u));
+  CheckElements({31}, LowToHighBits<uint32_t>(0x80000000u));
+  CheckElements({0, 31}, LowToHighBits<uint32_t>(0x80000001u));
+  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 31}, LowToHighBits<uint32_t>(0x800000ffu));
+  CheckElements({0, 8, 16, 24, 31}, LowToHighBits<uint32_t>(0x81010101u));
+  CheckElements({16, 17, 30, 31}, LowToHighBits<uint32_t>(0xc0030000u));
+  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
+                 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31},
+                LowToHighBits<uint32_t>(0xffffffffu));
+}
+
+TEST(BitUtilsTest, TestLowToHighBits64) {
+  CheckElements({}, LowToHighBits<uint64_t>(UINT64_C(0)));
+  CheckElements({0}, LowToHighBits<uint64_t>(UINT64_C(1)));
+  CheckElements({32}, LowToHighBits<uint64_t>(UINT64_C(0x100000000)));
+  CheckElements({63}, LowToHighBits<uint64_t>(UINT64_C(0x8000000000000000)));
+  CheckElements({0, 63}, LowToHighBits<uint64_t>(UINT64_C(0x8000000000000001)));
+  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 63},
+                LowToHighBits<uint64_t>(UINT64_C(0x80000000000000ff)));
+  CheckElements({0, 8, 16, 24, 32, 40, 48, 56, 63},
+                LowToHighBits<uint64_t>(UINT64_C(0x8101010101010101)));
+  CheckElements({16, 17, 62, 63}, LowToHighBits<uint64_t>(UINT64_C(0xc000000000030000)));
+  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
+                 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
+                 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
+                 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63},
+                LowToHighBits<uint64_t>(UINT64_C(0xffffffffffffffff)));
+}
+
+TEST(BitUtilsTest, TestHighToLowBits32) {
+  CheckElements({}, HighToLowBits<uint32_t>(0u));
+  CheckElements({0}, HighToLowBits<uint32_t>(1u));
+  CheckElements({15}, HighToLowBits<uint32_t>(0x8000u));
+  CheckElements({31}, HighToLowBits<uint32_t>(0x80000000u));
+  CheckElements({31, 0}, HighToLowBits<uint32_t>(0x80000001u));
+  CheckElements({31, 7, 6, 5, 4, 3, 2, 1, 0}, HighToLowBits<uint32_t>(0x800000ffu));
+  CheckElements({31, 24, 16, 8, 0}, HighToLowBits<uint32_t>(0x81010101u));
+  CheckElements({31, 30, 17, 16}, HighToLowBits<uint32_t>(0xc0030000u));
+  CheckElements({31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
+                 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+                HighToLowBits<uint32_t>(0xffffffffu));
+}
+
+TEST(BitUtilsTest, TestHighToLowBits64) {
+  CheckElements({}, HighToLowBits<uint64_t>(UINT64_C(0)));
+  CheckElements({0}, HighToLowBits<uint64_t>(UINT64_C(1)));
+  CheckElements({32}, HighToLowBits<uint64_t>(UINT64_C(0x100000000)));
+  CheckElements({63}, HighToLowBits<uint64_t>(UINT64_C(0x8000000000000000)));
+  CheckElements({63, 0}, HighToLowBits<uint64_t>(UINT64_C(0x8000000000000001)));
+  CheckElements({63, 7, 6, 5, 4, 3, 2, 1, 0},
+                HighToLowBits<uint64_t>(UINT64_C(0x80000000000000ff)));
+  CheckElements({63, 56, 48, 40, 32, 24, 16, 8, 0},
+                HighToLowBits<uint64_t>(UINT64_C(0x8101010101010101)));
+  CheckElements({63, 62, 17, 16}, HighToLowBits<uint64_t>(UINT64_C(0xc000000000030000)));
+  CheckElements({63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48,
+                 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32,
+                 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
+                 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+                HighToLowBits<uint64_t>(UINT64_C(0xffffffffffffffff)));
+}
+
+}  // namespace art
diff --git a/runtime/base/bit_vector-inl.h b/runtime/base/bit_vector-inl.h
index 39b19e5..0887798 100644
--- a/runtime/base/bit_vector-inl.h
+++ b/runtime/base/bit_vector-inl.h
@@ -17,9 +17,9 @@
 #ifndef ART_RUNTIME_BASE_BIT_VECTOR_INL_H_
 #define ART_RUNTIME_BASE_BIT_VECTOR_INL_H_
 
+#include "base/bit_utils.h"
 #include "bit_vector.h"
 #include "logging.h"
-#include "utils.h"
 
 namespace art {
 
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 6e4367a..17835f5 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -20,7 +20,7 @@
 #include <stdint.h>
 #include <iterator>
 
-#include "utils.h"
+#include "base/bit_utils.h"
 
 namespace art {
 
diff --git a/runtime/base/bounded_fifo.h b/runtime/base/bounded_fifo.h
index d04840a..7bcd382 100644
--- a/runtime/base/bounded_fifo.h
+++ b/runtime/base/bounded_fifo.h
@@ -17,16 +17,19 @@
 #ifndef ART_RUNTIME_BASE_BOUNDED_FIFO_H_
 #define ART_RUNTIME_BASE_BOUNDED_FIFO_H_
 
+#include "base/bit_utils.h"
+#include "base/logging.h"
+
 namespace art {
 
 // A bounded fifo is a fifo which has a bounded size. The power of two version uses a bit mask to
 // avoid needing to deal with wrapping integers around or using a modulo operation.
-template <typename T, const size_t MaxSize>
+template <typename T, const size_t kMaxSize>
 class BoundedFifoPowerOfTwo {
+  static_assert(IsPowerOfTwo(kMaxSize), "kMaxSize must be a power of 2.");
+
  public:
   BoundedFifoPowerOfTwo() {
-    // TODO: Do this with a compile time check.
-    CHECK(IsPowerOfTwo(MaxSize));
     clear();
   }
 
@@ -45,7 +48,7 @@ class BoundedFifoPowerOfTwo {
 
   void push_back(const T& value) {
     ++size_;
-    DCHECK_LE(size_, MaxSize);
+    DCHECK_LE(size_, kMaxSize);
     // Relies on integer overflow behavior.
     data_[back_index_++ & mask_] = value;
   }
@@ -61,9 +64,9 @@ class BoundedFifoPowerOfTwo {
   }
 
  private:
-  static const size_t mask_ = MaxSize - 1;
+  static const size_t mask_ = kMaxSize - 1;
   size_t back_index_, size_;
-  T data_[MaxSize];
+  T data_[kMaxSize];
 };
 
 }  // namespace art
diff --git a/runtime/base/histogram-inl.h b/runtime/base/histogram-inl.h
index 0f969b9..aba3762 100644
--- a/runtime/base/histogram-inl.h
+++ b/runtime/base/histogram-inl.h
@@ -17,15 +17,16 @@
 #ifndef ART_RUNTIME_BASE_HISTOGRAM_INL_H_
 #define ART_RUNTIME_BASE_HISTOGRAM_INL_H_
 
-#include "histogram.h"
-
-#include "utils.h"
-
 #include <algorithm>
 #include <cmath>
 #include <limits>
 #include <ostream>
 
+#include "histogram.h"
+
+#include "base/bit_utils.h"
+#include "base/time_utils.h"
+
 namespace art {
 
 template <class Value> inline void Histogram<Value>::AddValue(Value value) {
diff --git a/runtime/base/histogram.h b/runtime/base/histogram.h
index c312fb2..ef3a5d7 100644
--- a/runtime/base/histogram.h
+++ b/runtime/base/histogram.h
@@ -20,7 +20,6 @@
 #include <string>
 
 #include "base/logging.h"
-#include "utils.h"
 
 namespace art {
 
diff --git a/runtime/base/iteration_range.h b/runtime/base/iteration_range.h
new file mode 100644
index 0000000..5a46376
--- /dev/null
+++ b/runtime/base/iteration_range.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_ITERATION_RANGE_H_
+#define ART_RUNTIME_BASE_ITERATION_RANGE_H_
+
+namespace art {
+
+// Helper class that acts as a container for range-based loops, given an iteration
+// range [first, last) defined by two iterators.
+template <typename Iter>
+class IterationRange {
+ public:
+  typedef Iter iterator;
+  typedef typename std::iterator_traits<Iter>::difference_type difference_type;
+  typedef typename std::iterator_traits<Iter>::value_type value_type;
+  typedef typename std::iterator_traits<Iter>::pointer pointer;
+  typedef typename std::iterator_traits<Iter>::reference reference;
+
+  IterationRange(iterator first, iterator last) : first_(first), last_(last) { }
+
+  iterator begin() const { return first_; }
+  iterator end() const { return last_; }
+  iterator cbegin() const { return first_; }
+  iterator cend() const { return last_; }
+
+ private:
+  iterator first_;
+  iterator last_;
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_ITERATION_RANGE_H_
diff --git a/runtime/base/mutex-inl.h b/runtime/base/mutex-inl.h
index a727992..87840e7 100644
--- a/runtime/base/mutex-inl.h
+++ b/runtime/base/mutex-inl.h
@@ -25,6 +25,7 @@
 #include "base/value_object.h"
 #include "runtime.h"
 #include "thread.h"
+#include "utils.h"
 
 #if ART_USE_FUTEXES
 #include "linux/futex.h"
diff --git a/runtime/base/mutex.cc b/runtime/base/mutex.cc
index 99c7246..5c6065d 100644
--- a/runtime/base/mutex.cc
+++ b/runtime/base/mutex.cc
@@ -24,12 +24,12 @@
 
 #include "atomic.h"
 #include "base/logging.h"
+#include "base/time_utils.h"
 #include "base/value_object.h"
 #include "mutex-inl.h"
 #include "runtime.h"
 #include "scoped_thread_state_change.h"
 #include "thread-inl.h"
-#include "utils.h"
 
 namespace art {
 
diff --git a/runtime/base/time_utils.cc b/runtime/base/time_utils.cc
new file mode 100644
index 0000000..29b849e
--- /dev/null
+++ b/runtime/base/time_utils.cc
@@ -0,0 +1,205 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <inttypes.h>
+#include <sstream>
+
+#include "time_utils.h"
+
+#include "base/logging.h"
+#include "base/stringprintf.h"
+
+namespace art {
+
+std::string PrettyDuration(uint64_t nano_duration, size_t max_fraction_digits) {
+  if (nano_duration == 0) {
+    return "0";
+  } else {
+    return FormatDuration(nano_duration, GetAppropriateTimeUnit(nano_duration),
+                          max_fraction_digits);
+  }
+}
+
+TimeUnit GetAppropriateTimeUnit(uint64_t nano_duration) {
+  const uint64_t one_sec = 1000 * 1000 * 1000;
+  const uint64_t one_ms  = 1000 * 1000;
+  const uint64_t one_us  = 1000;
+  if (nano_duration >= one_sec) {
+    return kTimeUnitSecond;
+  } else if (nano_duration >= one_ms) {
+    return kTimeUnitMillisecond;
+  } else if (nano_duration >= one_us) {
+    return kTimeUnitMicrosecond;
+  } else {
+    return kTimeUnitNanosecond;
+  }
+}
+
+uint64_t GetNsToTimeUnitDivisor(TimeUnit time_unit) {
+  const uint64_t one_sec = 1000 * 1000 * 1000;
+  const uint64_t one_ms  = 1000 * 1000;
+  const uint64_t one_us  = 1000;
+
+  switch (time_unit) {
+    case kTimeUnitSecond:
+      return one_sec;
+    case kTimeUnitMillisecond:
+      return one_ms;
+    case kTimeUnitMicrosecond:
+      return one_us;
+    case kTimeUnitNanosecond:
+      return 1;
+  }
+  return 0;
+}
+
+std::string FormatDuration(uint64_t nano_duration, TimeUnit time_unit,
+                           size_t max_fraction_digits) {
+  const char* unit = nullptr;
+  uint64_t divisor = GetNsToTimeUnitDivisor(time_unit);
+  switch (time_unit) {
+    case kTimeUnitSecond:
+      unit = "s";
+      break;
+    case kTimeUnitMillisecond:
+      unit = "ms";
+      break;
+    case kTimeUnitMicrosecond:
+      unit = "us";
+      break;
+    case kTimeUnitNanosecond:
+      unit = "ns";
+      break;
+  }
+  const uint64_t whole_part = nano_duration / divisor;
+  uint64_t fractional_part = nano_duration % divisor;
+  if (fractional_part == 0) {
+    return StringPrintf("%" PRIu64 "%s", whole_part, unit);
+  } else {
+    static constexpr size_t kMaxDigits = 30;
+    size_t avail_digits = kMaxDigits;
+    char fraction_buffer[kMaxDigits];
+    char* ptr = fraction_buffer;
+    uint64_t multiplier = 10;
+    // This infinite loops if fractional part is 0.
+    while (avail_digits > 1 && fractional_part * multiplier < divisor) {
+      multiplier *= 10;
+      *ptr++ = '0';
+      avail_digits--;
+    }
+    snprintf(ptr, avail_digits, "%" PRIu64, fractional_part);
+    fraction_buffer[std::min(kMaxDigits - 1, max_fraction_digits)] = '\0';
+    return StringPrintf("%" PRIu64 ".%s%s", whole_part, fraction_buffer, unit);
+  }
+}
+
+std::string GetIsoDate() {
+  time_t now = time(nullptr);
+  tm tmbuf;
+  tm* ptm = localtime_r(&now, &tmbuf);
+  return StringPrintf("%04d-%02d-%02d %02d:%02d:%02d",
+      ptm->tm_year + 1900, ptm->tm_mon+1, ptm->tm_mday,
+      ptm->tm_hour, ptm->tm_min, ptm->tm_sec);
+}
+
+uint64_t MilliTime() {
+#if defined(__linux__)
+  timespec now;
+  clock_gettime(CLOCK_MONOTONIC, &now);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000) + now.tv_nsec / UINT64_C(1000000);
+#else  // __APPLE__
+  timeval now;
+  gettimeofday(&now, nullptr);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000) + now.tv_usec / UINT64_C(1000);
+#endif
+}
+
+uint64_t MicroTime() {
+#if defined(__linux__)
+  timespec now;
+  clock_gettime(CLOCK_MONOTONIC, &now);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000000) + now.tv_nsec / UINT64_C(1000);
+#else  // __APPLE__
+  timeval now;
+  gettimeofday(&now, nullptr);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000000) + now.tv_usec;
+#endif
+}
+
+uint64_t NanoTime() {
+#if defined(__linux__)
+  timespec now;
+  clock_gettime(CLOCK_MONOTONIC, &now);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000000000) + now.tv_nsec;
+#else  // __APPLE__
+  timeval now;
+  gettimeofday(&now, nullptr);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000000000) + now.tv_usec * UINT64_C(1000);
+#endif
+}
+
+uint64_t ThreadCpuNanoTime() {
+#if defined(__linux__)
+  timespec now;
+  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &now);
+  return static_cast<uint64_t>(now.tv_sec) * UINT64_C(1000000000) + now.tv_nsec;
+#else  // __APPLE__
+  UNIMPLEMENTED(WARNING);
+  return -1;
+#endif
+}
+
+void NanoSleep(uint64_t ns) {
+  timespec tm;
+  tm.tv_sec = ns / MsToNs(1000);
+  tm.tv_nsec = ns - static_cast<uint64_t>(tm.tv_sec) * MsToNs(1000);
+  nanosleep(&tm, nullptr);
+}
+
+void InitTimeSpec(bool absolute, int clock, int64_t ms, int32_t ns, timespec* ts) {
+  int64_t endSec;
+
+  if (absolute) {
+#if !defined(__APPLE__)
+    clock_gettime(clock, ts);
+#else
+    UNUSED(clock);
+    timeval tv;
+    gettimeofday(&tv, nullptr);
+    ts->tv_sec = tv.tv_sec;
+    ts->tv_nsec = tv.tv_usec * 1000;
+#endif
+  } else {
+    ts->tv_sec = 0;
+    ts->tv_nsec = 0;
+  }
+  endSec = ts->tv_sec + ms / 1000;
+  if (UNLIKELY(endSec >= 0x7fffffff)) {
+    std::ostringstream ss;
+    LOG(INFO) << "Note: end time exceeds epoch: " << ss.str();
+    endSec = 0x7ffffffe;
+  }
+  ts->tv_sec = endSec;
+  ts->tv_nsec = (ts->tv_nsec + (ms % 1000) * 1000000) + ns;
+
+  // Catch rollover.
+  if (ts->tv_nsec >= 1000000000L) {
+    ts->tv_sec++;
+    ts->tv_nsec -= 1000000000L;
+  }
+}
+
+}  // namespace art
diff --git a/runtime/base/time_utils.h b/runtime/base/time_utils.h
new file mode 100644
index 0000000..f58c22a
--- /dev/null
+++ b/runtime/base/time_utils.h
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_TIME_UTILS_H_
+#define ART_RUNTIME_BASE_TIME_UTILS_H_
+
+#include <stdint.h>
+#include <string>
+#include <time.h>
+
+#include "base/macros.h"
+
+namespace art {
+
+enum TimeUnit {
+  kTimeUnitNanosecond,
+  kTimeUnitMicrosecond,
+  kTimeUnitMillisecond,
+  kTimeUnitSecond,
+};
+
+// Returns a human-readable time string which prints every nanosecond while trying to limit the
+// number of trailing zeros. Prints using the largest human readable unit up to a second.
+// e.g. "1ms", "1.000000001s", "1.001us"
+std::string PrettyDuration(uint64_t nano_duration, size_t max_fraction_digits = 3);
+
+// Format a nanosecond time to specified units.
+std::string FormatDuration(uint64_t nano_duration, TimeUnit time_unit,
+                           size_t max_fraction_digits);
+
+// Get the appropriate unit for a nanosecond duration.
+TimeUnit GetAppropriateTimeUnit(uint64_t nano_duration);
+
+// Get the divisor to convert from a nanoseconds to a time unit.
+uint64_t GetNsToTimeUnitDivisor(TimeUnit time_unit);
+
+// Returns the current date in ISO yyyy-mm-dd hh:mm:ss format.
+std::string GetIsoDate();
+
+// Returns the monotonic time since some unspecified starting point in milliseconds.
+uint64_t MilliTime();
+
+// Returns the monotonic time since some unspecified starting point in microseconds.
+uint64_t MicroTime();
+
+// Returns the monotonic time since some unspecified starting point in nanoseconds.
+uint64_t NanoTime();
+
+// Returns the thread-specific CPU-time clock in nanoseconds or -1 if unavailable.
+uint64_t ThreadCpuNanoTime();
+
+// Converts the given number of nanoseconds to milliseconds.
+static constexpr inline uint64_t NsToMs(uint64_t ns) {
+  return ns / 1000 / 1000;
+}
+
+// Converts the given number of milliseconds to nanoseconds
+static constexpr inline uint64_t MsToNs(uint64_t ns) {
+  return ns * 1000 * 1000;
+}
+
+#if defined(__APPLE__)
+// No clocks to specify on OS/X, fake value to pass to routines that require a clock.
+#define CLOCK_REALTIME 0xebadf00d
+#endif
+
+// Sleep for the given number of nanoseconds, a bad way to handle contention.
+void NanoSleep(uint64_t ns);
+
+// Initialize a timespec to either a relative time (ms,ns), or to the absolute
+// time corresponding to the indicated clock value plus the supplied offset.
+void InitTimeSpec(bool absolute, int clock, int64_t ms, int32_t ns, timespec* ts);
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_TIME_UTILS_H_
diff --git a/runtime/base/time_utils_test.cc b/runtime/base/time_utils_test.cc
new file mode 100644
index 0000000..c553f4e
--- /dev/null
+++ b/runtime/base/time_utils_test.cc
@@ -0,0 +1,58 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "time_utils.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+TEST(TimeUtilsTest, PrettyDuration) {
+  const uint64_t one_sec = 1000000000;
+  const uint64_t one_ms  = 1000000;
+  const uint64_t one_us  = 1000;
+
+  EXPECT_EQ("1s", PrettyDuration(1 * one_sec));
+  EXPECT_EQ("10s", PrettyDuration(10 * one_sec));
+  EXPECT_EQ("100s", PrettyDuration(100 * one_sec));
+  EXPECT_EQ("1.001s", PrettyDuration(1 * one_sec + one_ms));
+  EXPECT_EQ("1.000001s", PrettyDuration(1 * one_sec + one_us, 6));
+  EXPECT_EQ("1.000000001s", PrettyDuration(1 * one_sec + 1, 9));
+  EXPECT_EQ("1.000s", PrettyDuration(1 * one_sec + one_us, 3));
+
+  EXPECT_EQ("1ms", PrettyDuration(1 * one_ms));
+  EXPECT_EQ("10ms", PrettyDuration(10 * one_ms));
+  EXPECT_EQ("100ms", PrettyDuration(100 * one_ms));
+  EXPECT_EQ("1.001ms", PrettyDuration(1 * one_ms + one_us));
+  EXPECT_EQ("1.000001ms", PrettyDuration(1 * one_ms + 1, 6));
+
+  EXPECT_EQ("1us", PrettyDuration(1 * one_us));
+  EXPECT_EQ("10us", PrettyDuration(10 * one_us));
+  EXPECT_EQ("100us", PrettyDuration(100 * one_us));
+  EXPECT_EQ("1.001us", PrettyDuration(1 * one_us + 1));
+
+  EXPECT_EQ("1ns", PrettyDuration(1));
+  EXPECT_EQ("10ns", PrettyDuration(10));
+  EXPECT_EQ("100ns", PrettyDuration(100));
+}
+
+TEST(TimeUtilsTest, TestSleep) {
+  auto start = NanoTime();
+  NanoSleep(MsToNs(1500));
+  EXPECT_GT(NanoTime() - start, MsToNs(1000));
+}
+
+}  // namespace art
diff --git a/runtime/base/timing_logger.cc b/runtime/base/timing_logger.cc
index b6a2aaf..f1f6f9b 100644
--- a/runtime/base/timing_logger.cc
+++ b/runtime/base/timing_logger.cc
@@ -22,9 +22,10 @@
 #include "timing_logger.h"
 
 #include "base/logging.h"
-#include "thread-inl.h"
 #include "base/stl_util.h"
 #include "base/histogram-inl.h"
+#include "base/time_utils.h"
+#include "thread-inl.h"
 
 #include <cmath>
 #include <iomanip>