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