TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pg_bitutils.c
4 : * Miscellaneous functions for bit-wise operations.
5 : *
6 : * Copyright (c) 2019-2023, PostgreSQL Global Development Group
7 : *
8 : * IDENTIFICATION
9 : * src/port/pg_bitutils.c
10 : *
11 : *-------------------------------------------------------------------------
12 : */
13 : #include "c.h"
14 :
15 : #ifdef HAVE__GET_CPUID
16 : #include <cpuid.h>
17 : #endif
18 : #ifdef HAVE__CPUID
19 : #include <intrin.h>
20 : #endif
21 :
22 : #include "port/pg_bitutils.h"
23 :
24 :
25 : /*
26 : * Array giving the position of the left-most set bit for each possible
27 : * byte value. We count the right-most position as the 0th bit, and the
28 : * left-most the 7th bit. The 0th entry of the array should not be used.
29 : *
30 : * Note: this is not used by the functions in pg_bitutils.h when
31 : * HAVE__BUILTIN_CLZ is defined, but we provide it anyway, so that
32 : * extensions possibly compiled with a different compiler can use it.
33 : */
34 : const uint8 pg_leftmost_one_pos[256] = {
35 : 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
36 : 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
37 : 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
38 : 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
39 : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
40 : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
41 : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
42 : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
43 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
44 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
45 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
46 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
47 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
48 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
49 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
50 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
51 : };
52 :
53 : /*
54 : * Array giving the position of the right-most set bit for each possible
55 : * byte value. We count the right-most position as the 0th bit, and the
56 : * left-most the 7th bit. The 0th entry of the array should not be used.
57 : *
58 : * Note: this is not used by the functions in pg_bitutils.h when
59 : * HAVE__BUILTIN_CTZ is defined, but we provide it anyway, so that
60 : * extensions possibly compiled with a different compiler can use it.
61 : */
62 : const uint8 pg_rightmost_one_pos[256] = {
63 : 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
64 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
65 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
66 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
67 : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
68 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
69 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
70 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71 : 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
72 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
73 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
74 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
75 : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
76 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
77 : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
78 : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
79 : };
80 :
81 : /*
82 : * Array giving the number of 1-bits in each possible byte value.
83 : *
84 : * Note: we export this for use by functions in which explicit use
85 : * of the popcount functions seems unlikely to be a win.
86 : */
87 : const uint8 pg_number_of_ones[256] = {
88 : 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
89 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
91 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
93 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
95 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
97 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
98 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
99 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
100 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
101 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
102 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
103 : 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
104 : };
105 :
106 : static int pg_popcount32_slow(uint32 word);
107 : static int pg_popcount64_slow(uint64 word);
108 :
109 : #ifdef TRY_POPCNT_FAST
110 : static bool pg_popcount_available(void);
111 : static int pg_popcount32_choose(uint32 word);
112 : static int pg_popcount64_choose(uint64 word);
113 : static int pg_popcount32_fast(uint32 word);
114 : static int pg_popcount64_fast(uint64 word);
115 :
116 : int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
117 : int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
118 : #endif /* TRY_POPCNT_FAST */
119 :
120 : #ifdef TRY_POPCNT_FAST
121 :
122 : /*
123 : * Return true if CPUID indicates that the POPCNT instruction is available.
124 : */
125 : static bool
126 CBC 3841 : pg_popcount_available(void)
127 : {
128 3841 : unsigned int exx[4] = {0, 0, 0, 0};
129 :
130 : #if defined(HAVE__GET_CPUID)
131 3841 : __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
132 : #elif defined(HAVE__CPUID)
133 : __cpuid(exx, 1);
134 : #else
135 : #error cpuid instruction not available
136 : #endif
137 :
138 3841 : return (exx[2] & (1 << 23)) != 0; /* POPCNT */
139 : }
140 :
141 : /*
142 : * These functions get called on the first call to pg_popcount32 etc.
143 : * They detect whether we can use the asm implementations, and replace
144 : * the function pointers so that subsequent calls are routed directly to
145 : * the chosen implementation.
146 : */
147 : static int
148 4 : pg_popcount32_choose(uint32 word)
149 : {
150 4 : if (pg_popcount_available())
151 : {
152 4 : pg_popcount32 = pg_popcount32_fast;
153 4 : pg_popcount64 = pg_popcount64_fast;
154 : }
155 : else
156 : {
157 UBC 0 : pg_popcount32 = pg_popcount32_slow;
158 0 : pg_popcount64 = pg_popcount64_slow;
159 : }
160 :
161 CBC 4 : return pg_popcount32(word);
162 : }
163 :
164 : static int
165 3837 : pg_popcount64_choose(uint64 word)
166 : {
167 3837 : if (pg_popcount_available())
168 : {
169 3837 : pg_popcount32 = pg_popcount32_fast;
170 3837 : pg_popcount64 = pg_popcount64_fast;
171 : }
172 : else
173 : {
174 UBC 0 : pg_popcount32 = pg_popcount32_slow;
175 0 : pg_popcount64 = pg_popcount64_slow;
176 : }
177 :
178 CBC 3837 : return pg_popcount64(word);
179 : }
180 :
181 : /*
182 : * pg_popcount32_fast
183 : * Return the number of 1 bits set in word
184 : */
185 : static int
186 82 : pg_popcount32_fast(uint32 word)
187 : {
188 : #ifdef _MSC_VER
189 : return __popcnt(word);
190 : #else
191 : uint32 res;
192 :
193 82 : __asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
194 82 : return (int) res;
195 : #endif
196 : }
197 :
198 : /*
199 : * pg_popcount64_fast
200 : * Return the number of 1 bits set in word
201 : */
202 : static int
203 17272658 : pg_popcount64_fast(uint64 word)
204 : {
205 : #ifdef _MSC_VER
206 : return __popcnt64(word);
207 : #else
208 : uint64 res;
209 :
210 17272658 : __asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
211 17272658 : return (int) res;
212 : #endif
213 : }
214 :
215 : #endif /* TRY_POPCNT_FAST */
216 :
217 :
218 : /*
219 : * pg_popcount32_slow
220 : * Return the number of 1 bits set in word
221 : */
222 : static int
223 UBC 0 : pg_popcount32_slow(uint32 word)
224 : {
225 : #ifdef HAVE__BUILTIN_POPCOUNT
226 0 : return __builtin_popcount(word);
227 : #else /* !HAVE__BUILTIN_POPCOUNT */
228 : int result = 0;
229 :
230 : while (word != 0)
231 : {
232 : result += pg_number_of_ones[word & 255];
233 : word >>= 8;
234 : }
235 :
236 : return result;
237 : #endif /* HAVE__BUILTIN_POPCOUNT */
238 : }
239 :
240 : /*
241 : * pg_popcount64_slow
242 : * Return the number of 1 bits set in word
243 : */
244 : static int
245 0 : pg_popcount64_slow(uint64 word)
246 : {
247 : #ifdef HAVE__BUILTIN_POPCOUNT
248 : #if defined(HAVE_LONG_INT_64)
249 0 : return __builtin_popcountl(word);
250 : #elif defined(HAVE_LONG_LONG_INT_64)
251 : return __builtin_popcountll(word);
252 : #else
253 : #error must have a working 64-bit integer datatype
254 : #endif
255 : #else /* !HAVE__BUILTIN_POPCOUNT */
256 : int result = 0;
257 :
258 : while (word != 0)
259 : {
260 : result += pg_number_of_ones[word & 255];
261 : word >>= 8;
262 : }
263 :
264 : return result;
265 : #endif /* HAVE__BUILTIN_POPCOUNT */
266 : }
267 :
268 : #ifndef TRY_POPCNT_FAST
269 :
270 : /*
271 : * When the POPCNT instruction is not available, there's no point in using
272 : * function pointers to vary the implementation between the fast and slow
273 : * method. We instead just make these actual external functions when
274 : * TRY_POPCNT_FAST is not defined. The compiler should be able to inline
275 : * the slow versions here.
276 : */
277 : int
278 : pg_popcount32(uint32 word)
279 : {
280 : return pg_popcount32_slow(word);
281 : }
282 :
283 : int
284 : pg_popcount64(uint64 word)
285 : {
286 : return pg_popcount64_slow(word);
287 : }
288 :
289 : #endif /* !TRY_POPCNT_FAST */
290 :
291 : /*
292 : * pg_popcount
293 : * Returns the number of 1-bits in buf
294 : */
295 : uint64
296 CBC 5396 : pg_popcount(const char *buf, int bytes)
297 : {
298 5396 : uint64 popcnt = 0;
299 :
300 : #if SIZEOF_VOID_P >= 8
301 : /* Process in 64-bit chunks if the buffer is aligned. */
302 5396 : if (buf == (const char *) TYPEALIGN(8, buf))
303 : {
304 5314 : const uint64 *words = (const uint64 *) buf;
305 :
306 5314 : while (bytes >= 8)
307 : {
308 UBC 0 : popcnt += pg_popcount64(*words++);
309 0 : bytes -= 8;
310 : }
311 :
312 CBC 5314 : buf = (const char *) words;
313 : }
314 : #else
315 : /* Process in 32-bit chunks if the buffer is aligned. */
316 : if (buf == (const char *) TYPEALIGN(4, buf))
317 : {
318 : const uint32 *words = (const uint32 *) buf;
319 :
320 : while (bytes >= 4)
321 : {
322 : popcnt += pg_popcount32(*words++);
323 : bytes -= 4;
324 : }
325 :
326 : buf = (const char *) words;
327 : }
328 : #endif
329 :
330 : /* Process any remaining bytes */
331 10828 : while (bytes--)
332 5432 : popcnt += pg_number_of_ones[(unsigned char) *buf++];
333 :
334 5396 : return popcnt;
335 : }
|
