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