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.
5 // This file defines some bit utilities.
14 #include <type_traits>
16 #include "base/check.h"
17 #include "base/compiler_specific.h"
18 #include "build/build_config.h"
20 #if defined(COMPILER_MSVC)
27 // Returns true iff |value| is a power of 2.
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.
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;
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);
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);
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
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
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)
66 template <typename T, unsigned bits = sizeof(T) * 8>
68 typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4,
70 CountLeadingZeroBits(T x) {
71 static_assert(bits > 0, "invalid instantiation");
73 return LIKELY(_BitScanReverse(&index, static_cast<uint32_t>(x)))
74 ? (31 - index - (32 - bits))
78 template <typename T, unsigned bits = sizeof(T) * 8>
80 typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8,
82 CountLeadingZeroBits(T x) {
83 static_assert(bits > 0, "invalid instantiation");
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)))
91 uint32_t left = static_cast<uint32_t>(x >> 32);
92 if (LIKELY(_BitScanReverse(&index, left)))
95 uint32_t right = static_cast<uint32_t>(x);
96 if (LIKELY(_BitScanReverse(&index, right)))
103 template <typename T, unsigned bits = sizeof(T) * 8>
105 typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4,
107 CountTrailingZeroBits(T x) {
108 static_assert(bits > 0, "invalid instantiation");
110 return LIKELY(_BitScanForward(&index, static_cast<uint32_t>(x))) ? index
114 template <typename T, unsigned bits = sizeof(T) * 8>
116 typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8,
118 CountTrailingZeroBits(T x) {
119 static_assert(bits > 0, "invalid instantiation");
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
126 uint32_t right = static_cast<uint32_t>(x);
127 if (LIKELY(_BitScanForward(&index, right)))
130 uint32_t left = static_cast<uint32_t>(x >> 32);
131 if (LIKELY(_BitScanForward(&index, left)))
138 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
139 return CountLeadingZeroBits(x);
142 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
143 return CountLeadingZeroBits(x);
146 #elif defined(COMPILER_GCC)
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>
154 typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
156 CountLeadingZeroBits(T value) {
157 static_assert(bits > 0, "invalid instantiation");
160 ? __builtin_clzll(static_cast<uint64_t>(value))
161 : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits)
165 template <typename T, unsigned bits = sizeof(T) * 8>
167 typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
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))
176 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
177 return CountLeadingZeroBits(x);
180 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
181 return CountLeadingZeroBits(x);
186 ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) {
187 return CountLeadingZeroBits(x);
190 ALWAYS_INLINE size_t CountTrailingZeroBitsSizeT(size_t x) {
191 return CountTrailingZeroBits(x);
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);
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);
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.");
214 return one << ((CHAR_BIT * sizeof(T) - 1));
220 #endif // BASE_BITS_H_