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-2023, 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  non_zero = _BitScanReverse(&result, word);
52  Assert(non_zero);
53  return (int) result;
54 #else
55  int shift = 32 - 8;
56 
57  Assert(word != 0);
58 
59  while ((word >> shift) == 0)
60  shift -= 8;
61 
62  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
63 #endif /* HAVE__BUILTIN_CLZ */
64 }
65 
66 /*
67  * pg_leftmost_one_pos64
68  * As above, but for a 64-bit word.
69  */
70 static inline int
72 {
73 #ifdef HAVE__BUILTIN_CLZ
74  Assert(word != 0);
75 
76 #if defined(HAVE_LONG_INT_64)
77  return 63 - __builtin_clzl(word);
78 #elif defined(HAVE_LONG_LONG_INT_64)
79  return 63 - __builtin_clzll(word);
80 #else
81 #error must have a working 64-bit integer datatype
82 #endif /* HAVE_LONG_INT_64 */
83 
84 #elif defined(_MSC_VER)
85  unsigned long result;
86  bool non_zero;
87 
88  non_zero = _BitScanReverse64(&result, word);
89  Assert(non_zero);
90  return (int) result;
91 #else
92  int shift = 64 - 8;
93 
94  Assert(word != 0);
95 
96  while ((word >> shift) == 0)
97  shift -= 8;
98 
99  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
100 #endif /* HAVE__BUILTIN_CLZ */
101 }
102 
103 /*
104  * pg_rightmost_one_pos32
105  * Returns the position of the least significant set bit in "word",
106  * measured from the least significant bit. word must not be 0.
107  */
108 static inline int
110 {
111 #ifdef HAVE__BUILTIN_CTZ
112  Assert(word != 0);
113 
114  return __builtin_ctz(word);
115 #elif defined(_MSC_VER)
116  unsigned long result;
117  bool non_zero;
118 
119  non_zero = _BitScanForward(&result, word);
120  Assert(non_zero);
121  return (int) result;
122 #else
123  int result = 0;
124 
125  Assert(word != 0);
126 
127  while ((word & 255) == 0)
128  {
129  word >>= 8;
130  result += 8;
131  }
132  result += pg_rightmost_one_pos[word & 255];
133  return result;
134 #endif /* HAVE__BUILTIN_CTZ */
135 }
136 
137 /*
138  * pg_rightmost_one_pos64
139  * As above, but for a 64-bit word.
140  */
141 static inline int
143 {
144 #ifdef HAVE__BUILTIN_CTZ
145  Assert(word != 0);
146 
147 #if defined(HAVE_LONG_INT_64)
148  return __builtin_ctzl(word);
149 #elif defined(HAVE_LONG_LONG_INT_64)
150  return __builtin_ctzll(word);
151 #else
152 #error must have a working 64-bit integer datatype
153 #endif /* HAVE_LONG_INT_64 */
154 
155 #elif defined(_MSC_VER)
156  unsigned long result;
157  bool non_zero;
158 
159  non_zero = _BitScanForward64(&result, word);
160  Assert(non_zero);
161  return (int) result;
162 #else
163  int result = 0;
164 
165  Assert(word != 0);
166 
167  while ((word & 255) == 0)
168  {
169  word >>= 8;
170  result += 8;
171  }
172  result += pg_rightmost_one_pos[word & 255];
173  return result;
174 #endif /* HAVE__BUILTIN_CTZ */
175 }
176 
177 /*
178  * pg_nextpower2_32
179  * Returns the next higher power of 2 above 'num', or 'num' if it's
180  * already a power of 2.
181  *
182  * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.
183  */
184 static inline uint32
186 {
187  Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
188 
189  /*
190  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
191  * will turn on all previous bits resulting in no common bits being set
192  * between num and num-1.
193  */
194  if ((num & (num - 1)) == 0)
195  return num; /* already power 2 */
196 
197  return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
198 }
199 
200 /*
201  * pg_nextpower2_64
202  * Returns the next higher power of 2 above 'num', or 'num' if it's
203  * already a power of 2.
204  *
205  * 'num' mustn't be 0 or be above PG_UINT64_MAX / 2 + 1.
206  */
207 static inline uint64
208 pg_nextpower2_64(uint64 num)
209 {
210  Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
211 
212  /*
213  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
214  * will turn on all previous bits resulting in no common bits being set
215  * between num and num-1.
216  */
217  if ((num & (num - 1)) == 0)
218  return num; /* already power 2 */
219 
220  return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
221 }
222 
223 /*
224  * pg_prevpower2_32
225  * Returns the next lower power of 2 below 'num', or 'num' if it's
226  * already a power of 2.
227  *
228  * 'num' mustn't be 0.
229  */
230 static inline uint32
232 {
233  return ((uint32) 1) << pg_leftmost_one_pos32(num);
234 }
235 
236 /*
237  * pg_prevpower2_64
238  * Returns the next lower power of 2 below 'num', or 'num' if it's
239  * already a power of 2.
240  *
241  * 'num' mustn't be 0.
242  */
243 static inline uint64
244 pg_prevpower2_64(uint64 num)
245 {
246  return ((uint64) 1) << pg_leftmost_one_pos64(num);
247 }
248 
249 /*
250  * pg_ceil_log2_32
251  * Returns equivalent of ceil(log2(num))
252  */
253 static inline uint32
255 {
256  if (num < 2)
257  return 0;
258  else
259  return pg_leftmost_one_pos32(num - 1) + 1;
260 }
261 
262 /*
263  * pg_ceil_log2_64
264  * Returns equivalent of ceil(log2(num))
265  */
266 static inline uint64
267 pg_ceil_log2_64(uint64 num)
268 {
269  if (num < 2)
270  return 0;
271  else
272  return pg_leftmost_one_pos64(num - 1) + 1;
273 }
274 
275 /*
276  * With MSVC on x86_64 builds, try using native popcnt instructions via the
277  * __popcnt and __popcnt64 intrinsics. These don't work the same as GCC's
278  * __builtin_popcount* intrinsic functions as they always emit popcnt
279  * instructions.
280  */
281 #if defined(_MSC_VER) && defined(_M_AMD64)
282 #define HAVE_X86_64_POPCNTQ
283 #endif
284 
285 /*
286  * On x86_64, we can use the hardware popcount instruction, but only if
287  * we can verify that the CPU supports it via the cpuid instruction.
288  *
289  * Otherwise, we fall back to a hand-rolled implementation.
290  */
291 #ifdef HAVE_X86_64_POPCNTQ
292 #if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
293 #define TRY_POPCNT_FAST 1
294 #endif
295 #endif
296 
297 #ifdef TRY_POPCNT_FAST
298 /* Attempt to use the POPCNT instruction, but perform a runtime check first */
299 extern int (*pg_popcount32) (uint32 word);
300 extern int (*pg_popcount64) (uint64 word);
301 
302 #else
303 /* Use a portable implementation -- no need for a function pointer. */
304 extern int pg_popcount32(uint32 word);
305 extern int pg_popcount64(uint64 word);
306 
307 #endif /* TRY_POPCNT_FAST */
308 
309 /* Count the number of one-bits in a byte array */
310 extern uint64 pg_popcount(const char *buf, int bytes);
311 
312 /*
313  * Rotate the bits of "word" to the right/left by n bits.
314  */
315 static inline uint32
317 {
318  return (word >> n) | (word << (32 - n));
319 }
320 
321 static inline uint32
323 {
324  return (word << n) | (word >> (32 - n));
325 }
326 
327 /* size_t variants of the above, as required */
328 
329 #if SIZEOF_SIZE_T == 4
330 #define pg_leftmost_one_pos_size_t pg_leftmost_one_pos32
331 #define pg_nextpower2_size_t pg_nextpower2_32
332 #define pg_prevpower2_size_t pg_prevpower2_32
333 #else
334 #define pg_leftmost_one_pos_size_t pg_leftmost_one_pos64
335 #define pg_nextpower2_size_t pg_nextpower2_64
336 #define pg_prevpower2_size_t pg_prevpower2_64
337 #endif
338 
339 #endif /* PG_BITUTILS_H */
unsigned int uint32
Definition: c.h:490
#define PGDLLIMPORT
Definition: c.h:1321
#define PG_UINT32_MAX
Definition: c.h:574
#define PG_UINT64_MAX
Definition: c.h:577
unsigned char uint8
Definition: c.h:488
Assert(fmt[strlen(fmt) - 1] !='\n')
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:322
static int pg_rightmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:142
static uint32 pg_nextpower2_32(uint32 num)
Definition: pg_bitutils.h:185
static uint64 pg_ceil_log2_64(uint64 num)
Definition: pg_bitutils.h:267
static uint32 pg_rotate_right32(uint32 word, int n)
Definition: pg_bitutils.h:316
int pg_popcount64(uint64 word)
Definition: pg_bitutils.c:284
int pg_popcount32(uint32 word)
Definition: pg_bitutils.c:278
static int pg_rightmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:109
static uint64 pg_nextpower2_64(uint64 num)
Definition: pg_bitutils.h:208
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:254
static uint32 pg_prevpower2_32(uint32 num)
Definition: pg_bitutils.h:231
static uint64 pg_prevpower2_64(uint64 num)
Definition: pg_bitutils.h:244
uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.c:296
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:71
static char * buf
Definition: pg_test_fsync.c:67
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1474