1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___BITS 11#define _LIBCPP___BITS 12 13#include <__config> 14 15#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 16# pragma GCC system_header 17# pragma clang include_instead(<algorithm>) 18# pragma clang include_instead(<bit>) 19# pragma clang include_instead(<bitset>) 20# pragma clang include_instead(<numeric>) 21# pragma clang include_instead(<random>) 22# pragma clang include_instead(<unordered_map>) 23# pragma clang include_instead(<unordered_set>) 24# pragma clang include_instead(<vector>) 25#endif 26 27_LIBCPP_PUSH_MACROS 28#include <__undef_macros> 29 30 31_LIBCPP_BEGIN_NAMESPACE_STD 32 33#ifndef _LIBCPP_COMPILER_MSVC 34 35inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 36int __libcpp_ctz(unsigned __x) _NOEXCEPT { return __builtin_ctz(__x); } 37 38inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 39int __libcpp_ctz(unsigned long __x) _NOEXCEPT { return __builtin_ctzl(__x); } 40 41inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 42int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); } 43 44 45inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 46int __libcpp_clz(unsigned __x) _NOEXCEPT { return __builtin_clz(__x); } 47 48inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 49int __libcpp_clz(unsigned long __x) _NOEXCEPT { return __builtin_clzl(__x); } 50 51inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 52int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); } 53 54 55inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 56int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); } 57 58inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 59int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); } 60 61inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 62int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); } 63 64#else // _LIBCPP_COMPILER_MSVC 65 66// Precondition: __x != 0 67inline _LIBCPP_INLINE_VISIBILITY 68int __libcpp_ctz(unsigned __x) { 69 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 70 static_assert(sizeof(unsigned long) == 4, ""); 71 unsigned long __where; 72 if (_BitScanForward(&__where, __x)) 73 return static_cast<int>(__where); 74 return 32; 75} 76 77inline _LIBCPP_INLINE_VISIBILITY 78int __libcpp_ctz(unsigned long __x) { 79 static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); 80 return __ctz(static_cast<unsigned>(__x)); 81} 82 83inline _LIBCPP_INLINE_VISIBILITY 84int __libcpp_ctz(unsigned long long __x) { 85 unsigned long __where; 86#if defined(_LIBCPP_HAS_BITSCAN64) 87 if (_BitScanForward64(&__where, __x)) 88 return static_cast<int>(__where); 89#else 90 // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. 91 if (_BitScanForward(&__where, static_cast<unsigned long>(__x))) 92 return static_cast<int>(__where); 93 if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32))) 94 return static_cast<int>(__where + 32); 95#endif 96 return 64; 97} 98 99// Precondition: __x != 0 100inline _LIBCPP_INLINE_VISIBILITY 101int __libcpp_clz(unsigned __x) { 102 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 103 static_assert(sizeof(unsigned long) == 4, ""); 104 unsigned long __where; 105 if (_BitScanReverse(&__where, __x)) 106 return static_cast<int>(31 - __where); 107 return 32; // Undefined Behavior. 108} 109 110inline _LIBCPP_INLINE_VISIBILITY 111int __libcpp_clz(unsigned long __x) { 112 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 113 return __libcpp_clz(static_cast<unsigned>(__x)); 114} 115 116inline _LIBCPP_INLINE_VISIBILITY 117int __libcpp_clz(unsigned long long __x) { 118 unsigned long __where; 119#if defined(_LIBCPP_HAS_BITSCAN64) 120 if (_BitScanReverse64(&__where, __x)) 121 return static_cast<int>(63 - __where); 122#else 123 // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls. 124 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32))) 125 return static_cast<int>(63 - (__where + 32)); 126 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x))) 127 return static_cast<int>(63 - __where); 128#endif 129 return 64; // Undefined Behavior. 130} 131 132inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) { 133 static_assert(sizeof(unsigned) == 4, ""); 134 return __popcnt(__x); 135} 136 137inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) { 138 static_assert(sizeof(unsigned long) == 4, ""); 139 return __popcnt(__x); 140} 141 142inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long long __x) { 143 static_assert(sizeof(unsigned long long) == 8, ""); 144 return __popcnt64(__x); 145} 146 147#endif // _LIBCPP_COMPILER_MSVC 148 149_LIBCPP_END_NAMESPACE_STD 150 151_LIBCPP_POP_MACROS 152 153#endif // _LIBCPP___BITS 154