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 "base/compiler_specific.h" 14 #include "base/logging.h" 15 16 #if defined(COMPILER_MSVC) 17 #include <intrin.h> 18 #endif 19 20 namespace base { 21 namespace bits { 22 23 // Returns the integer i such as 2^i <= n < 2^(i+1) 24 inline int Log2Floor(uint32_t n) { 25 if (n == 0) 26 return -1; 27 int log = 0; 28 uint32_t value = n; 29 for (int i = 4; i >= 0; --i) { 30 int shift = (1 << i); 31 uint32_t x = value >> shift; 32 if (x != 0) { 33 value = x; 34 log += shift; 35 } 36 } 37 DCHECK_EQ(value, 1u); 38 return log; 39 } 40 41 // Returns the integer i such as 2^(i-1) < n <= 2^i 42 inline int Log2Ceiling(uint32_t n) { 43 if (n == 0) { 44 return -1; 45 } else { 46 // Log2Floor returns -1 for 0, so the following works correctly for n=1. 47 return 1 + Log2Floor(n - 1); 48 } 49 } 50 51 // Round up |size| to a multiple of alignment, which must be a power of two. 52 inline size_t Align(size_t size, size_t alignment) { 53 DCHECK_EQ(alignment & (alignment - 1), 0u); 54 return (size + alignment - 1) & ~(alignment - 1); 55 } 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 109 } // namespace bits 110 } // namespace base 111 112 #endif // BASE_BITS_H_ 113