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