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 there's clearly a return value that makes sense, and even |
| 82 // though some processor clz instructions have defined behaviour for 0. We could |
| 83 // drop to raw __asm__ to do better, but we'll avoid doing that unless we see |
| 84 // 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 |