1 /* count-one-bits.h -- counts the number of 1-bits in a word. 2 Copyright (C) 2007-2022 Free Software Foundation, Inc. 3 4 This file is free software: you can redistribute it and/or modify 5 it under the terms of the GNU Lesser General Public License as 6 published by the Free Software Foundation; either version 2.1 of the 7 License, or (at your option) any later version. 8 9 This file is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public License 15 along with this program. If not, see <https://www.gnu.org/licenses/>. */ 16 17 /* Written by Ben Pfaff. */ 18 19 #ifndef COUNT_ONE_BITS_H 20 #define COUNT_ONE_BITS_H 1 21 22 #include <limits.h> 23 #include <stdlib.h> 24 25 #ifndef _GL_INLINE_HEADER_BEGIN 26 #error "Please include config.h first." 27 #endif 28 _GL_INLINE_HEADER_BEGIN 29 #ifndef COUNT_ONE_BITS_INLINE 30 # define COUNT_ONE_BITS_INLINE _GL_INLINE 31 #endif 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 /* Assuming the GCC builtin is GCC_BUILTIN and the MSC builtin is MSC_BUILTIN, 38 expand to code that computes the number of 1-bits of the local 39 variable 'x' of type TYPE (an unsigned integer type) and return it 40 from the current function. */ 41 #if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) \ 42 || (__clang_major__ >= 4) 43 # define COUNT_ONE_BITS(GCC_BUILTIN, MSC_BUILTIN, TYPE) \ 44 return GCC_BUILTIN (x) 45 #else 46 47 /* Compute and return the number of 1-bits set in the least 48 significant 32 bits of X. */ 49 COUNT_ONE_BITS_INLINE int 50 count_one_bits_32 (unsigned int x) 51 { 52 x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U); 53 x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U); 54 x = (x >> 16) + (x & 0xffff); 55 x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f); 56 return (x >> 8) + (x & 0x00ff); 57 } 58 59 /* Expand to code that computes the number of 1-bits of the local 60 variable 'x' of type TYPE (an unsigned integer type) and return it 61 from the current function. */ 62 # define COUNT_ONE_BITS_GENERIC(TYPE) \ 63 do \ 64 { \ 65 int count = 0; \ 66 int bits; \ 67 for (bits = 0; bits < sizeof (TYPE) * CHAR_BIT; bits += 32) \ 68 { \ 69 count += count_one_bits_32 (x); \ 70 x = x >> 31 >> 1; \ 71 } \ 72 return count; \ 73 } \ 74 while (0) 75 76 # if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64) 77 78 /* While gcc falls back to its own generic code if the machine 79 on which it's running doesn't support popcount, with Microsoft's 80 compiler we need to detect and fallback ourselves. */ 81 82 # if 0 83 # include <intrin.h> 84 # else 85 /* Don't pollute the namespace with too many MSVC intrinsics. */ 86 # pragma intrinsic (__cpuid) 87 # pragma intrinsic (__popcnt) 88 # if defined _M_X64 89 # pragma intrinsic (__popcnt64) 90 # endif 91 # endif 92 93 # if !defined _M_X64 94 static inline __popcnt64 (unsigned long long x) 95 { 96 return __popcnt ((unsigned int) (x >> 32)) + __popcnt ((unsigned int) x); 97 } 98 # endif 99 100 /* Return nonzero if popcount is supported. */ 101 102 /* 1 if supported, 0 if not supported, -1 if unknown. */ 103 extern int popcount_support; 104 105 COUNT_ONE_BITS_INLINE int 106 popcount_supported (void) 107 { 108 if (popcount_support < 0) 109 { 110 /* Do as described in 111 <https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64> */ 112 int cpu_info[4]; 113 __cpuid (cpu_info, 1); 114 popcount_support = (cpu_info[2] >> 23) & 1; 115 } 116 return popcount_support; 117 } 118 119 # define COUNT_ONE_BITS(GCC_BUILTIN, MSC_BUILTIN, TYPE) \ 120 do \ 121 { \ 122 if (popcount_supported ()) \ 123 return MSC_BUILTIN (x); \ 124 else \ 125 COUNT_ONE_BITS_GENERIC (TYPE); \ 126 } \ 127 while (0) 128 129 # else 130 131 # define COUNT_ONE_BITS(GCC_BUILTIN, MSC_BUILTIN, TYPE) \ 132 COUNT_ONE_BITS_GENERIC (TYPE) 133 134 # endif 135 #endif 136 137 /* Compute and return the number of 1-bits set in X. */ 138 COUNT_ONE_BITS_INLINE int 139 count_one_bits (unsigned int x) 140 { 141 COUNT_ONE_BITS (__builtin_popcount, __popcnt, unsigned int); 142 } 143 144 /* Compute and return the number of 1-bits set in X. */ 145 COUNT_ONE_BITS_INLINE int 146 count_one_bits_l (unsigned long int x) 147 { 148 COUNT_ONE_BITS (__builtin_popcountl, __popcnt, unsigned long int); 149 } 150 151 /* Compute and return the number of 1-bits set in X. */ 152 COUNT_ONE_BITS_INLINE int 153 count_one_bits_ll (unsigned long long int x) 154 { 155 COUNT_ONE_BITS (__builtin_popcountll, __popcnt64, unsigned long long int); 156 } 157 158 #ifdef __cplusplus 159 } 160 #endif 161 162 _GL_INLINE_HEADER_END 163 164 #endif /* COUNT_ONE_BITS_H */ 165