1 /* count-one-bits.h -- counts the number of 1-bits in a word.
2 Copyright (C) 2007-2020 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3 of the License, or
7 (at your option) any later version.
9 This program 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 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17 /* Written by Ben Pfaff. */
19 #ifndef COUNT_ONE_BITS_H
20 #define COUNT_ONE_BITS_H 1
25 #ifndef _GL_INLINE_HEADER_BEGIN
26 #error "Please include config.h first."
28 _GL_INLINE_HEADER_BEGIN
29 #ifndef COUNT_ONE_BITS_INLINE
30 # define COUNT_ONE_BITS_INLINE _GL_INLINE
37 /* Expand to code that computes the number of 1-bits of the local
38 variable 'x' of type TYPE (an unsigned integer type) and return it
39 from the current function. */
40 #define COUNT_ONE_BITS_GENERIC(TYPE) \
45 for (bits = 0; bits < sizeof (TYPE) * CHAR_BIT; bits += 32) \
47 count += count_one_bits_32 (x); \
54 /* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTIN,
55 expand to code that computes the number of 1-bits of the local
56 variable 'x' of type TYPE (an unsigned integer type) and return it
57 from the current function. */
58 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
59 # define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) return BUILTIN (x)
62 /* Compute and return the number of 1-bits set in the least
63 significant 32 bits of X. */
64 COUNT_ONE_BITS_INLINE
int
65 count_one_bits_32 (unsigned int x
)
67 x
= ((x
& 0xaaaaaaaaU
) >> 1) + (x
& 0x55555555U
);
68 x
= ((x
& 0xccccccccU
) >> 2) + (x
& 0x33333333U
);
69 x
= (x
>> 16) + (x
& 0xffff);
70 x
= ((x
& 0xf0f0) >> 4) + (x
& 0x0f0f);
71 return (x
>> 8) + (x
& 0x00ff);
74 # if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64)
76 /* While gcc falls back to its own generic code if the machine
77 on which it's running doesn't support popcount, with Microsoft's
78 compiler we need to detect and fallback ourselves. */
79 # pragma intrinsic __cpuid
80 # pragma intrinsic __popcnt
81 # pragma intrinsic __popcnt64
83 /* Return nonzero if popcount is supported. */
85 /* 1 if supported, 0 if not supported, -1 if unknown. */
86 extern int popcount_support
;
88 COUNT_ONE_BITS_INLINE
int
89 popcount_supported (void)
91 if (popcount_support
< 0)
94 __cpuid (cpu_info
, 1);
95 popcount_support
= (cpu_info
[2] >> 23) & 1; /* See MSDN. */
97 return popcount_support
;
100 # define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) \
103 if (popcount_supported ()) \
104 return MSC_BUILTIN (x); \
106 COUNT_ONE_BITS_GENERIC (TYPE); \
110 # define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) \
111 COUNT_ONE_BITS_GENERIC (TYPE)
115 /* Compute and return the number of 1-bits set in X. */
116 COUNT_ONE_BITS_INLINE
int
117 count_one_bits (unsigned int x
)
119 COUNT_ONE_BITS (__builtin_popcount
, __popcnt
, unsigned int);
122 /* Compute and return the number of 1-bits set in X. */
123 COUNT_ONE_BITS_INLINE
int
124 count_one_bits_l (unsigned long int x
)
126 COUNT_ONE_BITS (__builtin_popcountl
, __popcnt
, unsigned long int);
129 /* Compute and return the number of 1-bits set in X. */
130 COUNT_ONE_BITS_INLINE
int
131 count_one_bits_ll (unsigned long long int x
)
133 COUNT_ONE_BITS (__builtin_popcountll
, __popcnt64
, unsigned long long int);
140 _GL_INLINE_HEADER_END
142 #endif /* COUNT_ONE_BITS_H */
This page took 0.039925 seconds and 4 git commands to generate.