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