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-2024, 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
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  */
71 static inline int
73 {
74 #ifdef HAVE__BUILTIN_CLZ
75  Assert(word != 0);
76 
77 #if defined(HAVE_LONG_INT_64)
78  return 63 - __builtin_clzl(word);
79 #elif defined(HAVE_LONG_LONG_INT_64)
80  return 63 - __builtin_clzll(word);
81 #else
82 #error must have a working 64-bit integer datatype
83 #endif /* HAVE_LONG_INT_64 */
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
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  */
144 static inline int
146 {
147 #ifdef HAVE__BUILTIN_CTZ
148  Assert(word != 0);
149 
150 #if defined(HAVE_LONG_INT_64)
151  return __builtin_ctzl(word);
152 #elif defined(HAVE_LONG_LONG_INT_64)
153  return __builtin_ctzll(word);
154 #else
155 #error must have a working 64-bit integer datatype
156 #endif /* HAVE_LONG_INT_64 */
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
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  */
211 static 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  */
234 static 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  */
247 static 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  */
257 static 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  */
270 static 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_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 */
303 extern PGDLLIMPORT int (*pg_popcount32) (uint32 word);
304 extern PGDLLIMPORT int (*pg_popcount64) (uint64 word);
305 extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
306 extern 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
315 extern bool pg_popcount_avx512_available(void);
316 extern uint64 pg_popcount_avx512(const char *buf, int bytes);
317 extern 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. */
322 extern int pg_popcount32(uint32 word);
323 extern int pg_popcount64(uint64 word);
324 extern uint64 pg_popcount_optimized(const char *buf, int bytes);
325 extern 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  */
338 static inline uint64
339 pg_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  */
369 static inline uint64
370 pg_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  */
397 static inline uint32
399 {
400  return (word >> n) | (word << (32 - n));
401 }
402 
403 static 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 */
unsigned int uint32
Definition: c.h:506
#define PGDLLIMPORT
Definition: c.h:1307
#define PG_UINT32_MAX
Definition: c.h:581
#define Assert(condition)
Definition: c.h:849
uint8 bits8
Definition: c.h:512
#define PG_UINT64_MAX
Definition: c.h:584
unsigned char uint8
Definition: c.h:504
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:73
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1474