PostgreSQL Source Code: src/include/port/pg_bitutils.h Source File

PostgreSQL Source Code git master
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
41 pg_leftmost_one_pos32(uint32 word)
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
72 pg_leftmost_one_pos64(uint64 word)
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
111 pg_rightmost_one_pos32(uint32 word)
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
145 pg_rightmost_one_pos64(uint64 word)
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
189 pg_nextpower2_32(uint32 num)
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
212 pg_nextpower2_64(uint64 num)
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
235 pg_prevpower2_32(uint32 num)
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
248 pg_prevpower2_64(uint64 num)
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
258 pg_ceil_log2_32(uint32 num)
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
271 pg_ceil_log2_64(uint64 num)
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_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 */
312extern PGDLLIMPORT int (*pg_popcount32) (uint32 word);
313extern PGDLLIMPORT int (*pg_popcount64) (uint64 word);
314extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
315extern 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
322extern bool pg_popcount_avx512_available(void);
323extern uint64 pg_popcount_avx512(const char *buf, int bytes);
324extern 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. */
329extern int pg_popcount32(uint32 word);
330extern 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
337extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
338extern PGDLLIMPORT uint64 (*pg_popcount_masked_optimized) (const char *buf, int bytes, bits8 mask);
339#else
340extern uint64 pg_popcount_optimized(const char *buf, int bytes);
341extern 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. */
346extern int pg_popcount32(uint32 word);
347extern int pg_popcount64(uint64 word);
348extern uint64 pg_popcount_optimized(const char *buf, int bytes);
349extern 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 */
362static inline uint64
363 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 int threshold = 8;
371#else
372 int threshold = 4;
373#endif
374
375 if (bytes < threshold)
376 {
377 uint64 popcnt = 0;
378
379 while (bytes--)
380 popcnt += pg_number_of_ones[(unsigned char) *buf++];
381 return popcnt;
382 }
383
384 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 */
393static inline uint64
394 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 int threshold = 8;
402#else
403 int threshold = 4;
404#endif
405
406 if (bytes < threshold)
407 {
408 uint64 popcnt = 0;
409
410 while (bytes--)
411 popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
412 return popcnt;
413 }
414
415 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 */
421static inline uint32
422 pg_rotate_right32(uint32 word, int n)
423{
424 return (word >> n) | (word << (32 - n));
425}
426
427static inline uint32
428 pg_rotate_left32(uint32 word, int n)
429{
430 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 */
#define PGDLLIMPORT
Definition: c.h:1319
uint8_t uint8
Definition: c.h:536
#define PG_UINT32_MAX
Definition: c.h:595
uint8 bits8
Definition: c.h:545
uint64_t uint64
Definition: c.h:539
uint32_t uint32
Definition: c.h:538
#define PG_UINT64_MAX
Definition: c.h:598
Assert(PointerIsAligned(start, uint64))
uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.c:535
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:428
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:422
uint64 pg_popcount_optimized(const char *buf, int bytes)
Definition: pg_bitutils.c:525
int pg_popcount64(uint64 word)
Definition: pg_bitutils.c:515
int pg_popcount32(uint32 word)
Definition: pg_bitutils.c:509
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:363
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:394
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

AltStyle によって変換されたページ (->オリジナル) /