1 // -*- C++ -*- 2 //===------------------------------ bit ----------------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===---------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_BIT 12 #define _LIBCPP_BIT 13 14 /* 15 bit synopsis 16 17 namespace std { 18 19 } // namespace std 20 21 */ 22 23 #include <__config> 24 #include <version> 25 26 #if defined(__IBMCPP__) 27 #include "support/ibm/support.h" 28 #endif 29 #if defined(_LIBCPP_COMPILER_MSVC) 30 #include <intrin.h> 31 #endif 32 33 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 34 #pragma GCC system_header 35 #endif 36 37 _LIBCPP_BEGIN_NAMESPACE_STD 38 39 #ifndef _LIBCPP_COMPILER_MSVC 40 41 inline _LIBCPP_INLINE_VISIBILITY 42 int __ctz(unsigned __x) { return __builtin_ctz(__x); } 43 44 inline _LIBCPP_INLINE_VISIBILITY 45 int __ctz(unsigned long __x) { return __builtin_ctzl(__x); } 46 47 inline _LIBCPP_INLINE_VISIBILITY 48 int __ctz(unsigned long long __x) { return __builtin_ctzll(__x); } 49 50 51 inline _LIBCPP_INLINE_VISIBILITY 52 int __clz(unsigned __x) { return __builtin_clz(__x); } 53 54 inline _LIBCPP_INLINE_VISIBILITY 55 int __clz(unsigned long __x) { return __builtin_clzl(__x); } 56 57 inline _LIBCPP_INLINE_VISIBILITY 58 int __clz(unsigned long long __x) { return __builtin_clzll(__x); } 59 60 61 inline _LIBCPP_INLINE_VISIBILITY 62 int __popcount(unsigned __x) { return __builtin_popcount(__x); } 63 64 inline _LIBCPP_INLINE_VISIBILITY 65 int __popcount(unsigned long __x) { return __builtin_popcountl(__x); } 66 67 inline _LIBCPP_INLINE_VISIBILITY 68 int __popcount(unsigned long long __x) { return __builtin_popcountll(__x); } 69 70 #else // _LIBCPP_COMPILER_MSVC 71 72 // Precondition: __x != 0 73 inline _LIBCPP_INLINE_VISIBILITY 74 int __ctz(unsigned __x) { 75 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 76 static_assert(sizeof(unsigned long) == 4, ""); 77 unsigned long __where; 78 if (_BitScanForward(&__where, __x)) 79 return static_cast<int>(__where); 80 return 32; 81 } 82 83 inline _LIBCPP_INLINE_VISIBILITY 84 int __ctz(unsigned long __x) { 85 static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); 86 return __ctz(static_cast<unsigned>(__x)); 87 } 88 89 inline _LIBCPP_INLINE_VISIBILITY 90 int __ctz(unsigned long long __x) { 91 unsigned long __where; 92 #if defined(_LIBCPP_HAS_BITSCAN64) 93 (defined(_M_AMD64) || defined(__x86_64__)) 94 if (_BitScanForward64(&__where, __x)) 95 return static_cast<int>(__where); 96 #else 97 // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. 98 if (_BitScanForward(&__where, static_cast<unsigned long>(__x))) 99 return static_cast<int>(__where); 100 if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32))) 101 return static_cast<int>(__where + 32); 102 #endif 103 return 64; 104 } 105 106 // Precondition: __x != 0 107 inline _LIBCPP_INLINE_VISIBILITY 108 int __clz(unsigned __x) { 109 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 110 static_assert(sizeof(unsigned long) == 4, ""); 111 unsigned long __where; 112 if (_BitScanReverse(&__where, __x)) 113 return static_cast<int>(31 - __where); 114 return 32; // Undefined Behavior. 115 } 116 117 inline _LIBCPP_INLINE_VISIBILITY 118 int __clz(unsigned long __x) { 119 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 120 return __clz(static_cast<unsigned>(__x)); 121 } 122 123 inline _LIBCPP_INLINE_VISIBILITY 124 int __clz(unsigned long long __x) { 125 unsigned long __where; 126 #if defined(_LIBCPP_HAS_BITSCAN64) 127 if (_BitScanReverse64(&__where, __x)) 128 return static_cast<int>(63 - __where); 129 #else 130 // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls. 131 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32))) 132 return static_cast<int>(63 - (__where + 32)); 133 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x))) 134 return static_cast<int>(63 - __where); 135 #endif 136 return 64; // Undefined Behavior. 137 } 138 139 inline _LIBCPP_INLINE_VISIBILITY int __popcount(unsigned __x) { 140 static_assert(sizeof(unsigned) == 4, ""); 141 return __popcnt(__x); 142 } 143 144 inline _LIBCPP_INLINE_VISIBILITY int __popcount(unsigned long __x) { 145 static_assert(sizeof(unsigned long) == 4, ""); 146 return __popcnt(__x); 147 } 148 149 inline _LIBCPP_INLINE_VISIBILITY int __popcount(unsigned long long __x) { 150 static_assert(sizeof(unsigned long long) == 8, ""); 151 return __popcnt64(__x); 152 } 153 154 #endif // _LIBCPP_COMPILER_MSVC 155 156 _LIBCPP_END_NAMESPACE_STD 157 158 #endif // _LIBCPP_BIT 159
