base/bits.h

   1 // Copyright 2013 The Chromium Authors
   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 namespace base {
  21 namespace bits {
  22
  23 // Returns true iff |value| is a power of 2.
  24 //
  25 // TODO(pkasting): When C++20 is available, replace with std::has_single_bit().
  26 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
  27 constexpr 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 down |size| to a multiple of alignment, which must be a power of two.
  38 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
  39 constexpr T AlignDown(T size, T alignment) {
  40   DCHECK(IsPowerOfTwo(alignment));
  41   return size & ~(alignment - 1);
  42 }
  43
  44 // Move |ptr| back to the previous multiple of alignment, which must be a power
  45 // of two. Defined for types where sizeof(T) is one byte.
  46 template <typename T, typename = typename std::enable_if<sizeof(T) == 1>::type>
  47 inline T* AlignDown(T* ptr, uintptr_t alignment) {
  48   return reinterpret_cast<T*>(
  49       AlignDown(reinterpret_cast<uintptr_t>(ptr), alignment));
  50 }
  51
  52 // Round up |size| to a multiple of alignment, which must be a power of two.
  53 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
  54 constexpr T AlignUp(T size, T alignment) {
  55   DCHECK(IsPowerOfTwo(alignment));
  56   return (size + alignment - 1) & ~(alignment - 1);
  57 }
  58
  59 // Advance |ptr| to the next multiple of alignment, which must be a power of
  60 // two. Defined for types where sizeof(T) is one byte.
  61 template <typename T, typename = typename std::enable_if<sizeof(T) == 1>::type>
  62 inline T* AlignUp(T* ptr, uintptr_t alignment) {
  63   return reinterpret_cast<T*>(
  64       AlignUp(reinterpret_cast<uintptr_t>(ptr), alignment));
  65 }
  66
  67 // CountLeadingZeroBits(value) returns the number of zero bits following the
  68 // most significant 1 bit in |value| if |value| is non-zero, otherwise it
  69 // returns {sizeof(T) * 8}.
  70 // Example: 00100010 -> 2
  71 //
  72 // CountTrailingZeroBits(value) returns the number of zero bits preceding the
  73 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
  74 // returns {sizeof(T) * 8}.
  75 // Example: 00100010 -> 1
  76 //
  77 // C does not have an operator to do this, but fortunately the various
  78 // compilers have built-ins that map to fast underlying processor instructions.
  79 //
  80 // TODO(pkasting): When C++20 is available, replace with std::countl_zero() and
  81 // similar.
  82
  83 // __builtin_clz has undefined behaviour for an input of 0, even though there's
  84 // clearly a return value that makes sense, and even though some processor clz
  85 // instructions have defined behaviour for 0. We could drop to raw __asm__ to
  86 // do better, but we'll avoid doing that unless we see proof that we need to.
  87 template <typename T, int bits = sizeof(T) * 8>
  88 ALWAYS_INLINE constexpr
  89     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
  90                             int>::type
  91     CountLeadingZeroBits(T value) {
  92   static_assert(bits > 0, "invalid instantiation");
  93   return LIKELY(value)
  94              ? bits == 64
  95                    ? __builtin_clzll(static_cast<uint64_t>(value))
  96                    : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits)
  97              : bits;
  98 }
  99
 100 template <typename T, int bits = sizeof(T) * 8>
 101 ALWAYS_INLINE constexpr
 102     typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
 103                             int>::type
 104     CountTrailingZeroBits(T value) {
 105   return LIKELY(value) ? bits == 64
 106                              ? __builtin_ctzll(static_cast<uint64_t>(value))
 107                              : __builtin_ctz(static_cast<uint32_t>(value))
 108                        : bits;
 109 }
 110
 111 // Returns the integer i such as 2^i <= n < 2^(i+1).
 112 //
 113 // There is a common `BitLength` function, which returns the number of bits
 114 // required to represent a value. Rather than implement that function,
 115 // use `Log2Floor` and add 1 to the result.
 116 //
 117 // TODO(pkasting): When C++20 is available, replace with std::bit_xxx().
 118 constexpr int Log2Floor(uint32_t n) {
 119   return 31 - CountLeadingZeroBits(n);
 120 }
 121
 122 // Returns the integer i such as 2^(i-1) < n <= 2^i.
 123 constexpr int Log2Ceiling(uint32_t n) {
 124   // When n == 0, we want the function to return -1.
 125   // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
 126   // why the statement below starts with (n ? 32 : -1).
 127   return (n ? 32 : -1) - CountLeadingZeroBits(n - 1);
 128 }
 129
 130 // Returns a value of type T with a single bit set in the left-most position.
 131 // Can be used instead of manually shifting a 1 to the left.
 132 template <typename T>
 133 constexpr T LeftmostBit() {
 134   static_assert(std::is_integral<T>::value,
 135                 "This function can only be used with integral types.");
 136   T one(1u);
 137   return one << ((CHAR_BIT * sizeof(T) - 1));
 138 }
 139
 140 }  // namespace bits
 141 }  // namespace base
 142
 143 #endif  // BASE_BITS_H_