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#endif 18 19_LIBCPP_PUSH_MACROS 20#include <__undef_macros> 21 22 23_LIBCPP_BEGIN_NAMESPACE_STD 24 25#ifndef _LIBCPP_COMPILER_MSVC 26 27inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 28int __libcpp_ctz(unsigned __x) _NOEXCEPT { return __builtin_ctz(__x); } 29 30inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 31int __libcpp_ctz(unsigned long __x) _NOEXCEPT { return __builtin_ctzl(__x); } 32 33inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 34int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); } 35 36 37inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 38int __libcpp_clz(unsigned __x) _NOEXCEPT { return __builtin_clz(__x); } 39 40inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 41int __libcpp_clz(unsigned long __x) _NOEXCEPT { return __builtin_clzl(__x); } 42 43inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 44int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); } 45 46 47inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 48int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); } 49 50inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 51int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); } 52 53inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 54int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); } 55 56#else // _LIBCPP_COMPILER_MSVC 57 58// Precondition: __x != 0 59inline _LIBCPP_INLINE_VISIBILITY 60int __libcpp_ctz(unsigned __x) { 61 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 62 static_assert(sizeof(unsigned long) == 4, ""); 63 unsigned long __where; 64 if (_BitScanForward(&__where, __x)) 65 return static_cast<int>(__where); 66 return 32; 67} 68 69inline _LIBCPP_INLINE_VISIBILITY 70int __libcpp_ctz(unsigned long __x) { 71 static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); 72 return __ctz(static_cast<unsigned>(__x)); 73} 74 75inline _LIBCPP_INLINE_VISIBILITY 76int __libcpp_ctz(unsigned long long __x) { 77 unsigned long __where; 78#if defined(_LIBCPP_HAS_BITSCAN64) 79 (defined(_M_AMD64) || defined(__x86_64__)) 80 if (_BitScanForward64(&__where, __x)) 81 return static_cast<int>(__where); 82#else 83 // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. 84 if (_BitScanForward(&__where, static_cast<unsigned long>(__x))) 85 return static_cast<int>(__where); 86 if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32))) 87 return static_cast<int>(__where + 32); 88#endif 89 return 64; 90} 91 92// Precondition: __x != 0 93inline _LIBCPP_INLINE_VISIBILITY 94int __libcpp_clz(unsigned __x) { 95 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 96 static_assert(sizeof(unsigned long) == 4, ""); 97 unsigned long __where; 98 if (_BitScanReverse(&__where, __x)) 99 return static_cast<int>(31 - __where); 100 return 32; // Undefined Behavior. 101} 102 103inline _LIBCPP_INLINE_VISIBILITY 104int __libcpp_clz(unsigned long __x) { 105 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 106 return __libcpp_clz(static_cast<unsigned>(__x)); 107} 108 109inline _LIBCPP_INLINE_VISIBILITY 110int __libcpp_clz(unsigned long long __x) { 111 unsigned long __where; 112#if defined(_LIBCPP_HAS_BITSCAN64) 113 if (_BitScanReverse64(&__where, __x)) 114 return static_cast<int>(63 - __where); 115#else 116 // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls. 117 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32))) 118 return static_cast<int>(63 - (__where + 32)); 119 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x))) 120 return static_cast<int>(63 - __where); 121#endif 122 return 64; // Undefined Behavior. 123} 124 125inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) { 126 static_assert(sizeof(unsigned) == 4, ""); 127 return __popcnt(__x); 128} 129 130inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) { 131 static_assert(sizeof(unsigned long) == 4, ""); 132 return __popcnt(__x); 133} 134 135inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long long __x) { 136 static_assert(sizeof(unsigned long long) == 8, ""); 137 return __popcnt64(__x); 138} 139 140#endif // _LIBCPP_COMPILER_MSVC 141 142_LIBCPP_END_NAMESPACE_STD 143 144_LIBCPP_POP_MACROS 145 146#endif // _LIBCPP__BITS 147