Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pg_bitutils.h
4 : : * Miscellaneous functions for bit-wise operations.
5 : : *
6 : : *
7 : : * Copyright (c) 2019-2025, PostgreSQL Global Development Group
8 : : *
9 : : * src/include/port/pg_bitutils.h
10 : : *
11 : : *-------------------------------------------------------------------------
12 : : */
13 : : #ifndef PG_BITUTILS_H
14 : : #define PG_BITUTILS_H
15 : :
16 : : #ifdef _MSC_VER
17 : : #include <intrin.h>
18 : : #define HAVE_BITSCAN_FORWARD
19 : : #define HAVE_BITSCAN_REVERSE
20 : :
21 : : #else
22 : : #if defined(HAVE__BUILTIN_CTZ)
23 : : #define HAVE_BITSCAN_FORWARD
24 : : #endif
25 : :
26 : : #if defined(HAVE__BUILTIN_CLZ)
27 : : #define HAVE_BITSCAN_REVERSE
28 : : #endif
29 : : #endif /* _MSC_VER */
30 : :
31 : : extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
32 : : extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
33 : : extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
34 : :
35 : : /*
36 : : * pg_leftmost_one_pos32
37 : : * Returns the position of the most significant set bit in "word",
38 : : * measured from the least significant bit. word must not be 0.
39 : : */
40 : : static inline int
2395 tgl@sss.pgh.pa.us 41 :CBC 479639364 : pg_leftmost_one_pos32(uint32 word)
42 : : {
43 : : #ifdef HAVE__BUILTIN_CLZ
927 john.naylor@postgres 44 [ - + ]: 479639364 : Assert(word != 0);
45 : :
46 : 479639364 : return 31 - __builtin_clz(word);
47 : : #elif defined(_MSC_VER)
48 : : unsigned long result;
49 : : bool non_zero;
50 : :
51 : : Assert(word != 0);
52 : :
53 : : non_zero = _BitScanReverse(&result, word);
54 : : return (int) result;
55 : : #else
56 : : int shift = 32 - 8;
57 : :
58 : : Assert(word != 0);
59 : :
60 : : while ((word >> shift) == 0)
61 : : shift -= 8;
62 : :
63 : : return shift + pg_leftmost_one_pos[(word >> shift) & 255];
64 : : #endif /* HAVE__BUILTIN_CLZ */
65 : : }
66 : :
67 : : /*
68 : : * pg_leftmost_one_pos64
69 : : * As above, but for a 64-bit word.
70 : : */
71 : : static inline int
2395 tgl@sss.pgh.pa.us 72 : 2286212 : pg_leftmost_one_pos64(uint64 word)
73 : : {
74 : : #ifdef HAVE__BUILTIN_CLZ
75 [ - + ]: 2286212 : Assert(word != 0);
76 : :
77 : : #if SIZEOF_LONG == 8
927 john.naylor@postgres 78 : 2286212 : return 63 - __builtin_clzl(word);
79 : : #elif SIZEOF_LONG_LONG == 8
80 : : return 63 - __builtin_clzll(word);
81 : : #else
82 : : #error "cannot find integer type of the same size as uint64_t"
83 : : #endif
84 : :
85 : : #elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))
86 : : unsigned long result;
87 : : bool non_zero;
88 : :
89 : : Assert(word != 0);
90 : :
91 : : non_zero = _BitScanReverse64(&result, word);
92 : : return (int) result;
93 : : #else
94 : : int shift = 64 - 8;
95 : :
96 : : Assert(word != 0);
97 : :
98 : : while ((word >> shift) == 0)
99 : : shift -= 8;
100 : :
101 : : return shift + pg_leftmost_one_pos[(word >> shift) & 255];
102 : : #endif /* HAVE__BUILTIN_CLZ */
103 : : }
104 : :
105 : : /*
106 : : * pg_rightmost_one_pos32
107 : : * Returns the position of the least significant set bit in "word",
108 : : * measured from the least significant bit. word must not be 0.
109 : : */
110 : : static inline int
2395 tgl@sss.pgh.pa.us 111 : 2829094 : pg_rightmost_one_pos32(uint32 word)
112 : : {
113 : : #ifdef HAVE__BUILTIN_CTZ
927 john.naylor@postgres 114 [ - + ]: 2829094 : Assert(word != 0);
115 : :
116 : 2829094 : return __builtin_ctz(word);
117 : : #elif defined(_MSC_VER)
118 : : unsigned long result;
119 : : bool non_zero;
120 : :
121 : : Assert(word != 0);
122 : :
123 : : non_zero = _BitScanForward(&result, word);
124 : : return (int) result;
125 : : #else
126 : : int result = 0;
127 : :
128 : : Assert(word != 0);
129 : :
130 : : while ((word & 255) == 0)
131 : : {
132 : : word >>= 8;
133 : : result += 8;
134 : : }
135 : : result += pg_rightmost_one_pos[word & 255];
136 : : return result;
137 : : #endif /* HAVE__BUILTIN_CTZ */
138 : : }
139 : :
140 : : /*
141 : : * pg_rightmost_one_pos64
142 : : * As above, but for a 64-bit word.
143 : : */
144 : : static inline int
2395 tgl@sss.pgh.pa.us 145 : 7183164 : pg_rightmost_one_pos64(uint64 word)
146 : : {
147 : : #ifdef HAVE__BUILTIN_CTZ
927 john.naylor@postgres 148 [ - + ]: 7183164 : Assert(word != 0);
149 : :
150 : : #if SIZEOF_LONG == 8
151 : 7183164 : return __builtin_ctzl(word);
152 : : #elif SIZEOF_LONG_LONG == 8
153 : : return __builtin_ctzll(word);
154 : : #else
155 : : #error "cannot find integer type of the same size as uint64_t"
156 : : #endif
157 : :
158 : : #elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))
159 : : unsigned long result;
160 : : bool non_zero;
161 : :
162 : : Assert(word != 0);
163 : :
164 : : non_zero = _BitScanForward64(&result, word);
165 : : return (int) result;
166 : : #else
167 : : int result = 0;
168 : :
169 : : Assert(word != 0);
170 : :
171 : : while ((word & 255) == 0)
172 : : {
173 : : word >>= 8;
174 : : result += 8;
175 : : }
176 : : result += pg_rightmost_one_pos[word & 255];
177 : : return result;
178 : : #endif /* HAVE__BUILTIN_CTZ */
179 : : }
180 : :
181 : : /*
182 : : * pg_nextpower2_32
183 : : * Returns the next higher power of 2 above 'num', or 'num' if it's
184 : : * already a power of 2.
185 : : *
186 : : * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.
187 : : */
188 : : static inline uint32
1977 drowley@postgresql.o 189 : 39313497 : pg_nextpower2_32(uint32 num)
190 : : {
191 [ + - - + ]: 39313497 : Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
192 : :
193 : : /*
194 : : * A power 2 number has only 1 bit set. Subtracting 1 from such a number
195 : : * will turn on all previous bits resulting in no common bits being set
196 : : * between num and num-1.
197 : : */
198 [ + + ]: 39313497 : if ((num & (num - 1)) == 0)
199 : 38113257 : return num; /* already power 2 */
200 : :
201 : 1200240 : return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
202 : : }
203 : :
204 : : /*
205 : : * pg_nextpower2_64
206 : : * Returns the next higher power of 2 above 'num', or 'num' if it's
207 : : * already a power of 2.
208 : : *
209 : : * 'num' mustn't be 0 or be above PG_UINT64_MAX / 2 + 1.
210 : : */
211 : : static inline uint64
212 : 102317 : pg_nextpower2_64(uint64 num)
213 : : {
214 [ + - + + ]: 102317 : Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
215 : :
216 : : /*
217 : : * A power 2 number has only 1 bit set. Subtracting 1 from such a number
218 : : * will turn on all previous bits resulting in no common bits being set
219 : : * between num and num-1.
220 : : */
221 [ + + ]: 102317 : if ((num & (num - 1)) == 0)
222 : 53178 : return num; /* already power 2 */
223 : :
224 : 49139 : return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
225 : : }
226 : :
227 : : /*
228 : : * pg_prevpower2_32
229 : : * Returns the next lower power of 2 below 'num', or 'num' if it's
230 : : * already a power of 2.
231 : : *
232 : : * 'num' mustn't be 0.
233 : : */
234 : : static inline uint32
1504 tgl@sss.pgh.pa.us 235 : 18 : pg_prevpower2_32(uint32 num)
236 : : {
237 : 18 : return ((uint32) 1) << pg_leftmost_one_pos32(num);
238 : : }
239 : :
240 : : /*
241 : : * pg_prevpower2_64
242 : : * Returns the next lower power of 2 below 'num', or 'num' if it's
243 : : * already a power of 2.
244 : : *
245 : : * 'num' mustn't be 0.
246 : : */
247 : : static inline uint64
248 : 339545 : pg_prevpower2_64(uint64 num)
249 : : {
250 : 339545 : return ((uint64) 1) << pg_leftmost_one_pos64(num);
251 : : }
252 : :
253 : : /*
254 : : * pg_ceil_log2_32
255 : : * Returns equivalent of ceil(log2(num))
256 : : */
257 : : static inline uint32
1977 drowley@postgresql.o 258 : 363141 : pg_ceil_log2_32(uint32 num)
259 : : {
260 [ - + ]: 363141 : if (num < 2)
1977 drowley@postgresql.o 261 :UBC 0 : return 0;
262 : : else
1977 drowley@postgresql.o 263 :CBC 363141 : return pg_leftmost_one_pos32(num - 1) + 1;
264 : : }
265 : :
266 : : /*
267 : : * pg_ceil_log2_64
268 : : * Returns equivalent of ceil(log2(num))
269 : : */
270 : : static inline uint64
271 : 753813 : pg_ceil_log2_64(uint64 num)
272 : : {
273 [ + + ]: 753813 : if (num < 2)
274 : 325560 : return 0;
275 : : else
276 : 428253 : return pg_leftmost_one_pos64(num - 1) + 1;
277 : : }
278 : :
279 : : /*
280 : : * With MSVC on x86_64 builds, try using native popcnt instructions via the
281 : : * __popcnt and __popcnt64 intrinsics. These don't work the same as GCC's
282 : : * __builtin_popcount* intrinsic functions as they always emit popcnt
283 : : * instructions.
284 : : */
285 : : #if defined(_MSC_VER) && defined(_M_AMD64)
286 : : #define HAVE_X86_64_POPCNTQ
287 : : #endif
288 : :
289 : : /*
290 : : * On x86_64, we can use the hardware popcount instruction, but only if
291 : : * we can verify that the CPU supports it via the cpuid instruction.
292 : : *
293 : : * Otherwise, we fall back to a hand-rolled implementation.
294 : : */
295 : : #ifdef HAVE_X86_64_POPCNTQ
296 : : #if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
297 : : #define TRY_POPCNT_X86_64 1
298 : : #endif
299 : : #endif
300 : :
301 : : /*
302 : : * On AArch64, we can use Neon instructions if the compiler provides access to
303 : : * them (as indicated by __ARM_NEON). As in simd.h, we assume that all
304 : : * available 64-bit hardware has Neon support.
305 : : */
306 : : #if defined(__aarch64__) && defined(__ARM_NEON)
307 : : #define POPCNT_AARCH64 1
308 : : #endif
309 : :
310 : : #ifdef TRY_POPCNT_X86_64
311 : : /* Attempt to use the POPCNT instruction, but perform a runtime check first */
312 : : extern PGDLLIMPORT int (*pg_popcount32) (uint32 word);
313 : : extern PGDLLIMPORT int (*pg_popcount64) (uint64 word);
314 : : extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
315 : : extern PGDLLIMPORT uint64 (*pg_popcount_masked_optimized) (const char *buf, int bytes, bits8 mask);
316 : :
317 : : /*
318 : : * We can also try to use the AVX-512 popcount instruction on some systems.
319 : : * The implementation of that is located in its own file.
320 : : */
321 : : #ifdef USE_AVX512_POPCNT_WITH_RUNTIME_CHECK
322 : : extern bool pg_popcount_avx512_available(void);
323 : : extern uint64 pg_popcount_avx512(const char *buf, int bytes);
324 : : extern uint64 pg_popcount_masked_avx512(const char *buf, int bytes, bits8 mask);
325 : : #endif
326 : :
327 : : #elif POPCNT_AARCH64
328 : : /* Use the Neon version of pg_popcount{32,64} without function pointer. */
329 : : extern int pg_popcount32(uint32 word);
330 : : extern int pg_popcount64(uint64 word);
331 : :
332 : : /*
333 : : * We can try to use an SVE-optimized pg_popcount() on some systems For that,
334 : : * we do use a function pointer.
335 : : */
336 : : #ifdef USE_SVE_POPCNT_WITH_RUNTIME_CHECK
337 : : extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
338 : : extern PGDLLIMPORT uint64 (*pg_popcount_masked_optimized) (const char *buf, int bytes, bits8 mask);
339 : : #else
340 : : extern uint64 pg_popcount_optimized(const char *buf, int bytes);
341 : : extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask);
342 : : #endif
343 : :
344 : : #else
345 : : /* Use a portable implementation -- no need for a function pointer. */
346 : : extern int pg_popcount32(uint32 word);
347 : : extern int pg_popcount64(uint64 word);
348 : : extern uint64 pg_popcount_optimized(const char *buf, int bytes);
349 : : extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask);
350 : :
351 : : #endif /* TRY_POPCNT_X86_64 */
352 : :
353 : : /*
354 : : * Returns the number of 1-bits in buf.
355 : : *
356 : : * If there aren't many bytes to process, the function call overhead of the
357 : : * optimized versions isn't worth taking, so we inline a loop that consults
358 : : * pg_number_of_ones in that case. If there are many bytes to process, we
359 : : * accept the function call overhead because the optimized versions are likely
360 : : * to be faster.
361 : : */
362 : : static inline uint64
521 nathan@postgresql.or 363 : 5353 : pg_popcount(const char *buf, int bytes)
364 : : {
365 : : /*
366 : : * We set the threshold to the point at which we'll first use special
367 : : * instructions in the optimized version.
368 : : */
369 : : #if SIZEOF_VOID_P >= 8
370 : 5353 : int threshold = 8;
371 : : #else
372 : : int threshold = 4;
373 : : #endif
374 : :
375 [ + + ]: 5353 : if (bytes < threshold)
376 : : {
377 : 5320 : uint64 popcnt = 0;
378 : :
379 [ + + ]: 10680 : while (bytes--)
380 : 5360 : popcnt += pg_number_of_ones[(unsigned char) *buf++];
381 : 5320 : return popcnt;
382 : : }
383 : :
384 : 33 : return pg_popcount_optimized(buf, bytes);
385 : : }
386 : :
387 : : /*
388 : : * Returns the number of 1-bits in buf after applying the mask to each byte.
389 : : *
390 : : * Similar to pg_popcount(), we only take on the function pointer overhead when
391 : : * it's likely to be faster.
392 : : */
393 : : static inline uint64
518 394 : 16249 : pg_popcount_masked(const char *buf, int bytes, bits8 mask)
395 : : {
396 : : /*
397 : : * We set the threshold to the point at which we'll first use special
398 : : * instructions in the optimized version.
399 : : */
400 : : #if SIZEOF_VOID_P >= 8
401 : 16249 : int threshold = 8;
402 : : #else
403 : : int threshold = 4;
404 : : #endif
405 : :
406 [ - + ]: 16249 : if (bytes < threshold)
407 : : {
518 nathan@postgresql.or 408 :UBC 0 : uint64 popcnt = 0;
409 : :
410 [ # # ]: 0 : while (bytes--)
411 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
412 : 0 : return popcnt;
413 : : }
414 : :
518 nathan@postgresql.or 415 :CBC 16249 : return pg_popcount_masked_optimized(buf, bytes, mask);
416 : : }
417 : :
418 : : /*
419 : : * Rotate the bits of "word" to the right/left by n bits.
420 : : */
421 : : static inline uint32
2083 tmunro@postgresql.or 422 : 7785290 : pg_rotate_right32(uint32 word, int n)
423 : : {
1294 john.naylor@postgres 424 : 7785290 : return (word >> n) | (word << (32 - n));
425 : : }
426 : :
427 : : static inline uint32
428 : 2628417690 : pg_rotate_left32(uint32 word, int n)
429 : : {
430 : 2628417690 : return (word << n) | (word >> (32 - n));
431 : : }
432 : :
433 : : /* size_t variants of the above, as required */
434 : :
435 : : #if SIZEOF_SIZE_T == 4
436 : : #define pg_leftmost_one_pos_size_t pg_leftmost_one_pos32
437 : : #define pg_nextpower2_size_t pg_nextpower2_32
438 : : #define pg_prevpower2_size_t pg_prevpower2_32
439 : : #else
440 : : #define pg_leftmost_one_pos_size_t pg_leftmost_one_pos64
441 : : #define pg_nextpower2_size_t pg_nextpower2_64
442 : : #define pg_prevpower2_size_t pg_prevpower2_64
443 : : #endif
444 : :
445 : : #endif /* PG_BITUTILS_H */
|
