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