bits.h 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143
  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. // This file defines some bit utilities.
  5. #ifndef BASE_BITS_H_
  6. #define BASE_BITS_H_
  7. #include <limits.h>
  8. #include <stddef.h>
  9. #include <stdint.h>
  10. #include <type_traits>
  11. #include "base/check.h"
  12. #include "base/compiler_specific.h"
  13. #include "build/build_config.h"
  14. namespace base {
  15. namespace bits {
  16. // Returns true iff |value| is a power of 2.
  17. //
  18. // TODO(pkasting): When C++20 is available, replace with std::has_single_bit().
  19. template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
  20. constexpr bool IsPowerOfTwo(T value) {
  21. // From "Hacker's Delight": Section 2.1 Manipulating Rightmost Bits.
  22. //
  23. // Only positive integers with a single bit set are powers of two. If only one
  24. // bit is set in x (e.g. 0b00000100000000) then |x-1| will have that bit set
  25. // to zero and all bits to its right set to 1 (e.g. 0b00000011111111). Hence
  26. // |x & (x-1)| is 0 iff x is a power of two.
  27. return value > 0 && (value & (value - 1)) == 0;
  28. }
  29. // Round down |size| to a multiple of alignment, which must be a power of two.
  30. template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
  31. constexpr T AlignDown(T size, T alignment) {
  32. DCHECK(IsPowerOfTwo(alignment));
  33. return size & ~(alignment - 1);
  34. }
  35. // Move |ptr| back to the previous multiple of alignment, which must be a power
  36. // of two. Defined for types where sizeof(T) is one byte.
  37. template <typename T, typename = typename std::enable_if<sizeof(T) == 1>::type>
  38. inline T* AlignDown(T* ptr, uintptr_t alignment) {
  39. return reinterpret_cast<T*>(
  40. AlignDown(reinterpret_cast<uintptr_t>(ptr), alignment));
  41. }
  42. // Round up |size| to a multiple of alignment, which must be a power of two.
  43. template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
  44. constexpr T AlignUp(T size, T alignment) {
  45. DCHECK(IsPowerOfTwo(alignment));
  46. return (size + alignment - 1) & ~(alignment - 1);
  47. }
  48. // Advance |ptr| to the next multiple of alignment, which must be a power of
  49. // two. Defined for types where sizeof(T) is one byte.
  50. template <typename T, typename = typename std::enable_if<sizeof(T) == 1>::type>
  51. inline T* AlignUp(T* ptr, uintptr_t alignment) {
  52. return reinterpret_cast<T*>(
  53. AlignUp(reinterpret_cast<uintptr_t>(ptr), alignment));
  54. }
  55. // CountLeadingZeroBits(value) returns the number of zero bits following the
  56. // most significant 1 bit in |value| if |value| is non-zero, otherwise it
  57. // returns {sizeof(T) * 8}.
  58. // Example: 00100010 -> 2
  59. //
  60. // CountTrailingZeroBits(value) returns the number of zero bits preceding the
  61. // least significant 1 bit in |value| if |value| is non-zero, otherwise it
  62. // returns {sizeof(T) * 8}.
  63. // Example: 00100010 -> 1
  64. //
  65. // C does not have an operator to do this, but fortunately the various
  66. // compilers have built-ins that map to fast underlying processor instructions.
  67. //
  68. // TODO(pkasting): When C++20 is available, replace with std::countl_zero() and
  69. // similar.
  70. // __builtin_clz has undefined behaviour for an input of 0, even though there's
  71. // clearly a return value that makes sense, and even though some processor clz
  72. // instructions have defined behaviour for 0. We could drop to raw __asm__ to
  73. // do better, but we'll avoid doing that unless we see proof that we need to.
  74. template <typename T, int bits = sizeof(T) * 8>
  75. ALWAYS_INLINE constexpr
  76. typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
  77. int>::type
  78. CountLeadingZeroBits(T value) {
  79. static_assert(bits > 0, "invalid instantiation");
  80. return LIKELY(value)
  81. ? bits == 64
  82. ? __builtin_clzll(static_cast<uint64_t>(value))
  83. : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits)
  84. : bits;
  85. }
  86. template <typename T, int bits = sizeof(T) * 8>
  87. ALWAYS_INLINE constexpr
  88. typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
  89. int>::type
  90. CountTrailingZeroBits(T value) {
  91. return LIKELY(value) ? bits == 64
  92. ? __builtin_ctzll(static_cast<uint64_t>(value))
  93. : __builtin_ctz(static_cast<uint32_t>(value))
  94. : bits;
  95. }
  96. // Returns the integer i such as 2^i <= n < 2^(i+1).
  97. //
  98. // There is a common `BitLength` function, which returns the number of bits
  99. // required to represent a value. Rather than implement that function,
  100. // use `Log2Floor` and add 1 to the result.
  101. //
  102. // TODO(pkasting): When C++20 is available, replace with std::bit_xxx().
  103. constexpr int Log2Floor(uint32_t n) {
  104. return 31 - CountLeadingZeroBits(n);
  105. }
  106. // Returns the integer i such as 2^(i-1) < n <= 2^i.
  107. constexpr int Log2Ceiling(uint32_t n) {
  108. // When n == 0, we want the function to return -1.
  109. // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
  110. // why the statement below starts with (n ? 32 : -1).
  111. return (n ? 32 : -1) - CountLeadingZeroBits(n - 1);
  112. }
  113. // Returns a value of type T with a single bit set in the left-most position.
  114. // Can be used instead of manually shifting a 1 to the left.
  115. template <typename T>
  116. constexpr T LeftmostBit() {
  117. static_assert(std::is_integral<T>::value,
  118. "This function can only be used with integral types.");
  119. T one(1u);
  120. return one << ((CHAR_BIT * sizeof(T) - 1));
  121. }
  122. } // namespace bits
  123. } // namespace base
  124. #endif // BASE_BITS_H_