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
count_one_bits(unsigned int x)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
count_one_bits_l(unsigned long int x)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
count_one_bits_ll(unsigned long long int x)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