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 if (_BitScanForward64(&__where, __x)) 80 return static_cast<int>(__where); 81#else 82 // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. 83 if (_BitScanForward(&__where, static_cast<unsigned long>(__x))) 84 return static_cast<int>(__where); 85 if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32))) 86 return static_cast<int>(__where + 32); 87#endif 88 return 64; 89} 90 91// Precondition: __x != 0 92inline _LIBCPP_INLINE_VISIBILITY 93int __libcpp_clz(unsigned __x) { 94 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 95 static_assert(sizeof(unsigned long) == 4, ""); 96 unsigned long __where; 97 if (_BitScanReverse(&__where, __x)) 98 return static_cast<int>(31 - __where); 99 return 32; // Undefined Behavior. 100} 101 102inline _LIBCPP_INLINE_VISIBILITY 103int __libcpp_clz(unsigned long __x) { 104 static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); 105 return __libcpp_clz(static_cast<unsigned>(__x)); 106} 107 108inline _LIBCPP_INLINE_VISIBILITY 109int __libcpp_clz(unsigned long long __x) { 110 unsigned long __where; 111#if defined(_LIBCPP_HAS_BITSCAN64) 112 if (_BitScanReverse64(&__where, __x)) 113 return static_cast<int>(63 - __where); 114#else 115 // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls. 116 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32))) 117 return static_cast<int>(63 - (__where + 32)); 118 if (_BitScanReverse(&__where, static_cast<unsigned long>(__x))) 119 return static_cast<int>(63 - __where); 120#endif 121 return 64; // Undefined Behavior. 122} 123 124inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) { 125 static_assert(sizeof(unsigned) == 4, ""); 126 return __popcnt(__x); 127} 128 129inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) { 130 static_assert(sizeof(unsigned long) == 4, ""); 131 return __popcnt(__x); 132} 133 134inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long long __x) { 135 static_assert(sizeof(unsigned long long) == 8, ""); 136 return __popcnt64(__x); 137} 138 139#endif // _LIBCPP_COMPILER_MSVC 140 141_LIBCPP_END_NAMESPACE_STD 142 143_LIBCPP_POP_MACROS 144 145#endif // _LIBCPP___BITS 146