base/bits.h

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // This file defines some bit utilities.
   6
   7 #ifndef BASE_BITS_H_
   8 #define BASE_BITS_H_
   9
  10 #include <limits.h>
  11 #include <stddef.h>
  12 #include <stdint.h>
  13
  14 #include <type_traits>
  15
  16 #include "base/check.h"
  17 #include "base/compiler_specific.h"
  18 #include "build/build_config.h"
  19
  20 #if defined(COMPILER_MSVC)
  21 #include <intrin.h>
  22 #endif
  23
  24 namespace base {
  25 namespace bits {
  26
  27 // Returns true iff |value| is a power of 2.
  28 template <typename T,
  29           typename = typename std::enable_if<std::is_integral<T>::value>>
  30 constexpr inline bool IsPowerOfTwo(T value) {
  31   // From "Hacker's Delight": Section 2.1 Manipulating Rightmost Bits.
  32   //
  33   // Only positive integers with a single bit set are powers of two. If only one
  34   // bit is set in x (e.g. 0b00000100000000) then |x-1| will have that bit set
  35   // to zero and all bits to its right set to 1 (e.g. 0b00000011111111). Hence
  36   // |x & (x-1)| is 0 iff x is a power of two.
  37   return value > 0 && (value & (value - 1)) == 0;
  38 }
  39
  40 // Round up |size| to a multiple of alignment, which must be a power of two.
  41 inline size_t Align(size_t size, size_t alignment) {
  42   DCHECK(IsPowerOfTwo(alignment));
  43   return (size + alignment - 1) & ~(alignment - 1);
  44 }
  45
  46 // Round down |size| to a multiple of alignment, which must be a power of two.
  47 inline size_t AlignDown(size_t size, size_t alignment) {
  48   DCHECK(IsPowerOfTwo(alignment));
  49   return size & ~(alignment - 1);
  50 }
  51
  52 // CountLeadingZeroBits(value) returns the number of zero bits following the
  53 // most significant 1 bit in |value| if |value| is non-zero, otherwise it
  54 // returns {sizeof(T) * 8}.
  55 // Example: 00100010 -> 2
  56 //
  57 // CountTrailingZeroBits(value) returns the number of zero bits preceding the
  58 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
  59 // returns {sizeof(T) * 8}.
  60 // Example: 00100010 -> 1
  61 //
  62 // C does not have an operator to do this, but fortunately the various
  63 // compilers have built-ins that map to fast underlying processor instructions.
  64 #if defined(COMPILER_MSVC)
  65
  66 template <typename T, unsigned bits = sizeof(T) * 8>
  67 ALWAYS_INLINE
  68     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4,
  69                             unsigned>::type
  70     CountLeadingZeroBits(T x) {
  71   static_assert(bits > 0, "invalid instantiation");
  72   unsigned long index;
  73   return LIKELY(_BitScanReverse(&index, static_cast<uint32_t>(x)))
  74              ? (31 - index - (32 - bits))
  75              : bits;
  76 }
  77
  78 template <typename T, unsigned bits = sizeof(T) * 8>
  79 ALWAYS_INLINE
  80     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8,
  81                             unsigned>::type
  82     CountLeadingZeroBits(T x) {
  83   static_assert(bits > 0, "invalid instantiation");
  84   unsigned long index;
  85 // MSVC only supplies _BitScanReverse64 when building for a 64-bit target.
  86 #if defined(ARCH_CPU_64_BITS)
  87   return LIKELY(_BitScanReverse64(&index, static_cast<uint64_t>(x)))
  88              ? (63 - index)
  89              : 64;
  90 #else
  91   uint32_t left = static_cast<uint32_t>(x >> 32);
  92   if (LIKELY(_BitScanReverse(&index, left)))
  93     return 31 - index;
  94
  95   uint32_t right = static_cast<uint32_t>(x);
  96   if (LIKELY(_BitScanReverse(&index, right)))
  97     return 63 - index;
  98
  99   return 64;
 100 #endif
 101 }
 102
 103 template <typename T, unsigned bits = sizeof(T) * 8>
 104 ALWAYS_INLINE
 105     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4,
 106                             unsigned>::type
 107     CountTrailingZeroBits(T x) {
 108   static_assert(bits > 0, "invalid instantiation");
 109   unsigned long index;
 110   return LIKELY(_BitScanForward(&index, static_cast<uint32_t>(x))) ? index
 111                                                                    : bits;
 112 }
 113
 114 template <typename T, unsigned bits = sizeof(T) * 8>
 115 ALWAYS_INLINE
 116     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8,
 117                             unsigned>::type
 118     CountTrailingZeroBits(T x) {
 119   static_assert(bits > 0, "invalid instantiation");
 120   unsigned long index;
 121 // MSVC only supplies _BitScanForward64 when building for a 64-bit target.
 122 #if defined(ARCH_CPU_64_BITS)
 123   return LIKELY(_BitScanForward64(&index, static_cast<uint64_t>(x))) ? index
 124                                                                      : 64;
 125 #else
 126   uint32_t right = static_cast<uint32_t>(x);
 127   if (LIKELY(_BitScanForward(&index, right)))
 128     return index;
 129
 130   uint32_t left = static_cast<uint32_t>(x >> 32);
 131   if (LIKELY(_BitScanForward(&index, left)))
 132     return 32 + index;
 133
 134   return 64;
 135 #endif
 136 }
 137
 138 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
 139   return CountLeadingZeroBits(x);
 140 }
 141
 142 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
 143   return CountLeadingZeroBits(x);
 144 }
 145
 146 #elif defined(COMPILER_GCC)
 147
 148 // __builtin_clz has undefined behaviour for an input of 0, even though there's
 149 // clearly a return value that makes sense, and even though some processor clz
 150 // instructions have defined behaviour for 0. We could drop to raw __asm__ to
 151 // do better, but we'll avoid doing that unless we see proof that we need to.
 152 template <typename T, unsigned bits = sizeof(T) * 8>
 153 ALWAYS_INLINE
 154     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
 155                             unsigned>::type
 156     CountLeadingZeroBits(T value) {
 157   static_assert(bits > 0, "invalid instantiation");
 158   return LIKELY(value)
 159              ? bits == 64
 160                    ? __builtin_clzll(static_cast<uint64_t>(value))
 161                    : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits)
 162              : bits;
 163 }
 164
 165 template <typename T, unsigned bits = sizeof(T) * 8>
 166 ALWAYS_INLINE
 167     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
 168                             unsigned>::type
 169     CountTrailingZeroBits(T value) {
 170   return LIKELY(value) ? bits == 64
 171                              ? __builtin_ctzll(static_cast<uint64_t>(value))
 172                              : __builtin_ctz(static_cast<uint32_t>(value))
 173                        : bits;
 174 }
 175
 176 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
 177   return CountLeadingZeroBits(x);
 178 }
 179
 180 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
 181   return CountLeadingZeroBits(x);
 182 }
 183
 184 #endif
 185
 186 ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) {
 187   return CountLeadingZeroBits(x);
 188 }
 189
 190 ALWAYS_INLINE size_t CountTrailingZeroBitsSizeT(size_t x) {
 191   return CountTrailingZeroBits(x);
 192 }
 193
 194 // Returns the integer i such as 2^i <= n < 2^(i+1)
 195 inline int Log2Floor(uint32_t n) {
 196   return 31 - CountLeadingZeroBits(n);
 197 }
 198
 199 // Returns the integer i such as 2^(i-1) < n <= 2^i
 200 inline int Log2Ceiling(uint32_t n) {
 201   // When n == 0, we want the function to return -1.
 202   // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
 203   // why the statement below starts with (n ? 32 : -1).
 204   return (n ? 32 : -1) - CountLeadingZeroBits(n - 1);
 205 }
 206
 207 // Returns a value of type T with a single bit set in the left-most position.
 208 // Can be used instead of manually shifting a 1 to the left.
 209 template <typename T>
 210 constexpr T LeftmostBit() {
 211   static_assert(std::is_integral<T>::value,
 212                 "This function can only be used with integral types.");
 213   T one(1u);
 214   return one << ((CHAR_BIT * sizeof(T) - 1));
 215 }
 216
 217 }  // namespace bits
 218 }  // namespace base
 219
 220 #endif  // BASE_BITS_H_