OLD | NEW |
---|---|
1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // This file defines some bit utilities. | 5 // This file defines some bit utilities. |
6 | 6 |
7 #ifndef BASE_BITS_H_ | 7 #ifndef BASE_BITS_H_ |
8 #define BASE_BITS_H_ | 8 #define BASE_BITS_H_ |
9 | 9 |
10 #include <stddef.h> | 10 #include <stddef.h> |
11 #include <stdint.h> | 11 #include <stdint.h> |
12 | 12 |
13 #include "base/compiler_specific.h" | |
13 #include "base/logging.h" | 14 #include "base/logging.h" |
14 | 15 |
16 #if defined(COMPILER_MSVC) | |
17 #include <intrin.h> | |
18 #endif | |
19 | |
15 namespace base { | 20 namespace base { |
16 namespace bits { | 21 namespace bits { |
17 | 22 |
18 // Returns the integer i such as 2^i <= n < 2^(i+1) | 23 // Returns the integer i such as 2^i <= n < 2^(i+1) |
19 inline int Log2Floor(uint32_t n) { | 24 inline int Log2Floor(uint32_t n) { |
20 if (n == 0) | 25 if (n == 0) |
21 return -1; | 26 return -1; |
22 int log = 0; | 27 int log = 0; |
23 uint32_t value = n; | 28 uint32_t value = n; |
24 for (int i = 4; i >= 0; --i) { | 29 for (int i = 4; i >= 0; --i) { |
(...skipping 17 matching lines...) Expand all Loading... | |
42 return 1 + Log2Floor(n - 1); | 47 return 1 + Log2Floor(n - 1); |
43 } | 48 } |
44 } | 49 } |
45 | 50 |
46 // Round up |size| to a multiple of alignment, which must be a power of two. | 51 // Round up |size| to a multiple of alignment, which must be a power of two. |
47 inline size_t Align(size_t size, size_t alignment) { | 52 inline size_t Align(size_t size, size_t alignment) { |
48 DCHECK_EQ(alignment & (alignment - 1), 0u); | 53 DCHECK_EQ(alignment & (alignment - 1), 0u); |
49 return (size + alignment - 1) & ~(alignment - 1); | 54 return (size + alignment - 1) & ~(alignment - 1); |
50 } | 55 } |
51 | 56 |
57 // These functions count the number of leading zeros in a binary value, starting | |
58 // with the most significant bit. C does not have an operator to do this, but | |
59 // fortunately the various compilers have built-ins that map to fast underlying | |
60 // processor instructions. | |
61 #if defined(COMPILER_MSVC) | |
62 | |
63 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { | |
64 unsigned long index; | |
65 return LIKELY(_BitScanReverse(&index, x)) ? (31 - index) : 32; | |
66 } | |
67 | |
68 #if defined(ARCH_CPU_64_BITS) | |
69 | |
70 // MSVC only supplies _BitScanForward64 when building for a 64-bit target. | |
71 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { | |
72 unsigned long index; | |
73 return LIKELY(_BitScanReverse64(&index, x)) ? (63 - index) : 64; | |
74 } | |
75 | |
76 #endif | |
77 | |
78 #elif defined(COMPILER_GCC) | |
79 | |
80 // This is very annoying. __builtin_clz has undefined behaviour for an input of | |
81 // 0, even though these's clearly a return value that makes sense, and even | |
dcheng
2016/11/17 20:06:25
these's?
I wonder if this comment meant to write
palmer
2016/11/17 20:18:27
Done.
| |
82 // though nascent processor clz instructions have defined behaviour for 0. | |
dcheng
2016/11/17 20:06:25
Not sure if it's still nascent ;-)
palmer
2016/11/17 20:18:27
Done.
| |
83 // We could drop to raw __asm__ to do better, but we'll avoid doing that unless | |
84 // we see proof that we need to. | |
85 ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { | |
86 return LIKELY(x) ? __builtin_clz(x) : 32; | |
87 } | |
88 | |
89 ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { | |
90 return LIKELY(x) ? __builtin_clzll(x) : 64; | |
91 } | |
92 | |
93 #endif | |
94 | |
95 #if defined(ARCH_CPU_64_BITS) | |
96 | |
97 ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) { | |
98 return CountLeadingZeroBits64(x); | |
99 } | |
100 | |
101 #else | |
102 | |
103 ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) { | |
104 return CountLeadingZeroBits32(x); | |
105 } | |
106 | |
107 #endif | |
108 | |
52 } // namespace bits | 109 } // namespace bits |
53 } // namespace base | 110 } // namespace base |
54 | 111 |
55 #endif // BASE_BITS_H_ | 112 #endif // BASE_BITS_H_ |
OLD | NEW |