PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
pg_bitutils.h
Go to the documentation of this file.
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
31extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
32extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
33extern 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 */
40static inline int
42{
43#ifdef HAVE__BUILTIN_CLZ
44 Assert(word != 0);
45
46 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 */
71static inline int
73{
74#ifdef HAVE__BUILTIN_CLZ
75 Assert(word != 0);
76
77#if SIZEOF_LONG == 8
78 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 */
110static inline int
112{
113#ifdef HAVE__BUILTIN_CTZ
114 Assert(word != 0);
115
116 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 */
144static inline int
146{
147#ifdef HAVE__BUILTIN_CTZ
148 Assert(word != 0);
149
150#if SIZEOF_LONG == 8
151 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 */
188static inline uint32
190{
191 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 if ((num & (num - 1)) == 0)
199 return num; /* already power 2 */
200
201 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 */
211static inline uint64
213{
214 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 if ((num & (num - 1)) == 0)
222 return num; /* already power 2 */
223
224 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 */
234static inline uint32
236{
237 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 */
247static inline uint64
249{
250 return ((uint64) 1) << pg_leftmost_one_pos64(num);
251}
252
253/*
254 * pg_ceil_log2_32
255 * Returns equivalent of ceil(log2(num))
256 */
257static inline uint32
259{
260 if (num < 2)
261 return 0;
262 else
263 return pg_leftmost_one_pos32(num - 1) + 1;
264}
265
266/*
267 * pg_ceil_log2_64
268 * Returns equivalent of ceil(log2(num))
269 */
270static inline uint64
272{
273 if (num < 2)
274 return 0;
275 else
276 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_FAST 1
298#endif
299#endif
300
301#ifdef TRY_POPCNT_FAST
302/* Attempt to use the POPCNT instruction, but perform a runtime check first */
303extern PGDLLIMPORT int (*pg_popcount32) (uint32 word);
304extern PGDLLIMPORT int (*pg_popcount64) (uint64 word);
305extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
306extern PGDLLIMPORT uint64 (*pg_popcount_masked_optimized) (const char *buf, int bytes, bits8 mask);
307
308/*
309 * We can also try to use the AVX-512 popcount instruction on some systems.
310 * The implementation of that is located in its own file because it may
311 * require special compiler flags that we don't want to apply to any other
312 * files.
313 */
314#ifdef USE_AVX512_POPCNT_WITH_RUNTIME_CHECK
315extern bool pg_popcount_avx512_available(void);
316extern uint64 pg_popcount_avx512(const char *buf, int bytes);
317extern uint64 pg_popcount_masked_avx512(const char *buf, int bytes, bits8 mask);
318#endif
319
320#else
321/* Use a portable implementation -- no need for a function pointer. */
322extern int pg_popcount32(uint32 word);
323extern int pg_popcount64(uint64 word);
324extern uint64 pg_popcount_optimized(const char *buf, int bytes);
325extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask);
326
327#endif /* TRY_POPCNT_FAST */
328
329/*
330 * Returns the number of 1-bits in buf.
331 *
332 * If there aren't many bytes to process, the function call overhead of the
333 * optimized versions isn't worth taking, so we inline a loop that consults
334 * pg_number_of_ones in that case. If there are many bytes to process, we
335 * accept the function call overhead because the optimized versions are likely
336 * to be faster.
337 */
338static inline uint64
339pg_popcount(const char *buf, int bytes)
340{
341 /*
342 * We set the threshold to the point at which we'll first use special
343 * instructions in the optimized version.
344 */
345#if SIZEOF_VOID_P >= 8
346 int threshold = 8;
347#else
348 int threshold = 4;
349#endif
350
351 if (bytes < threshold)
352 {
353 uint64 popcnt = 0;
354
355 while (bytes--)
356 popcnt += pg_number_of_ones[(unsigned char) *buf++];
357 return popcnt;
358 }
359
360 return pg_popcount_optimized(buf, bytes);
361}
362
363/*
364 * Returns the number of 1-bits in buf after applying the mask to each byte.
365 *
366 * Similar to pg_popcount(), we only take on the function pointer overhead when
367 * it's likely to be faster.
368 */
369static inline uint64
370pg_popcount_masked(const char *buf, int bytes, bits8 mask)
371{
372 /*
373 * We set the threshold to the point at which we'll first use special
374 * instructions in the optimized version.
375 */
376#if SIZEOF_VOID_P >= 8
377 int threshold = 8;
378#else
379 int threshold = 4;
380#endif
381
382 if (bytes < threshold)
383 {
384 uint64 popcnt = 0;
385
386 while (bytes--)
387 popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
388 return popcnt;
389 }
390
391 return pg_popcount_masked_optimized(buf, bytes, mask);
392}
393
394/*
395 * Rotate the bits of "word" to the right/left by n bits.
396 */
397static inline uint32
399{
400 return (word >> n) | (word << (32 - n));
401}
402
403static inline uint32
405{
406 return (word << n) | (word >> (32 - n));
407}
408
409/* size_t variants of the above, as required */
410
411#if SIZEOF_SIZE_T == 4
412#define pg_leftmost_one_pos_size_t pg_leftmost_one_pos32
413#define pg_nextpower2_size_t pg_nextpower2_32
414#define pg_prevpower2_size_t pg_prevpower2_32
415#else
416#define pg_leftmost_one_pos_size_t pg_leftmost_one_pos64
417#define pg_nextpower2_size_t pg_nextpower2_64
418#define pg_prevpower2_size_t pg_prevpower2_64
419#endif
420
421#endif /* PG_BITUTILS_H */
#define PGDLLIMPORT
Definition: c.h:1274
uint8_t uint8
Definition: c.h:483
#define PG_UINT32_MAX
Definition: c.h:544
#define Assert(condition)
Definition: c.h:812
uint8 bits8
Definition: c.h:492
uint64_t uint64
Definition: c.h:486
uint32_t uint32
Definition: c.h:485
#define PG_UINT64_MAX
Definition: c.h:547
uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.c:525
PGDLLIMPORT const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
static uint32 pg_rotate_left32(uint32 word, int n)
Definition: pg_bitutils.h:404
static int pg_rightmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:145
static uint32 pg_nextpower2_32(uint32 num)
Definition: pg_bitutils.h:189
static uint64 pg_ceil_log2_64(uint64 num)
Definition: pg_bitutils.h:271
static uint32 pg_rotate_right32(uint32 word, int n)
Definition: pg_bitutils.h:398
uint64 pg_popcount_optimized(const char *buf, int bytes)
Definition: pg_bitutils.c:515
int pg_popcount64(uint64 word)
Definition: pg_bitutils.c:505
int pg_popcount32(uint32 word)
Definition: pg_bitutils.c:499
static int pg_rightmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:111
static uint64 pg_nextpower2_64(uint64 num)
Definition: pg_bitutils.h:212
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:41
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62
static uint32 pg_ceil_log2_32(uint32 num)
Definition: pg_bitutils.h:258
static uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.h:339
static uint32 pg_prevpower2_32(uint32 num)
Definition: pg_bitutils.h:235
static uint64 pg_prevpower2_64(uint64 num)
Definition: pg_bitutils.h:248
static uint64 pg_popcount_masked(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.h:370
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:72
static char * buf
Definition: pg_test_fsync.c:72
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1476