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
41 1346428188 : pg_leftmost_one_pos32(uint32 word)
42 : {
43 : #ifdef HAVE__BUILTIN_CLZ
44 : Assert(word != 0);
45 :
46 1346428188 : 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
72 4808948 : pg_leftmost_one_pos64(uint64 word)
73 : {
74 : #ifdef HAVE__BUILTIN_CLZ
75 : Assert(word != 0);
76 :
77 : #if SIZEOF_LONG == 8
78 4808948 : 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
111 5545256 : pg_rightmost_one_pos32(uint32 word)
112 : {
113 : #ifdef HAVE__BUILTIN_CTZ
114 : Assert(word != 0);
115 :
116 5545256 : 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
145 24277432 : pg_rightmost_one_pos64(uint64 word)
146 : {
147 : #ifdef HAVE__BUILTIN_CTZ
148 : Assert(word != 0);
149 :
150 : #if SIZEOF_LONG == 8
151 24277432 : 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
189 154931484 : 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 154931484 : if ((num & (num - 1)) == 0)
199 146574962 : return num; /* already power 2 */
200 :
201 8356522 : 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 180712 : 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 180712 : if ((num & (num - 1)) == 0)
222 94128 : return num; /* already power 2 */
223 :
224 86584 : 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
235 36 : pg_prevpower2_32(uint32 num)
236 : {
237 36 : 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 1056642 : pg_prevpower2_64(uint64 num)
249 : {
250 1056642 : 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
258 712812 : pg_ceil_log2_32(uint32 num)
259 : {
260 712812 : if (num < 2)
261 0 : return 0;
262 : else
263 712812 : 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 1111496 : pg_ceil_log2_64(uint64 num)
272 : {
273 1111496 : if (num < 2)
274 462758 : return 0;
275 : else
276 648738 : 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.
311 : */
312 : #ifdef USE_AVX512_POPCNT_WITH_RUNTIME_CHECK
313 : extern bool pg_popcount_avx512_available(void);
314 : extern uint64 pg_popcount_avx512(const char *buf, int bytes);
315 : extern uint64 pg_popcount_masked_avx512(const char *buf, int bytes, bits8 mask);
316 : #endif
317 :
318 : #else
319 : /* Use a portable implementation -- no need for a function pointer. */
320 : extern int pg_popcount32(uint32 word);
321 : extern int pg_popcount64(uint64 word);
322 : extern uint64 pg_popcount_optimized(const char *buf, int bytes);
323 : extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask);
324 :
325 : #endif /* TRY_POPCNT_FAST */
326 :
327 : /*
328 : * Returns the number of 1-bits in buf.
329 : *
330 : * If there aren't many bytes to process, the function call overhead of the
331 : * optimized versions isn't worth taking, so we inline a loop that consults
332 : * pg_number_of_ones in that case. If there are many bytes to process, we
333 : * accept the function call overhead because the optimized versions are likely
334 : * to be faster.
335 : */
336 : static inline uint64
337 10710 : pg_popcount(const char *buf, int bytes)
338 : {
339 : /*
340 : * We set the threshold to the point at which we'll first use special
341 : * instructions in the optimized version.
342 : */
343 : #if SIZEOF_VOID_P >= 8
344 10710 : int threshold = 8;
345 : #else
346 : int threshold = 4;
347 : #endif
348 :
349 10710 : if (bytes < threshold)
350 : {
351 10682 : uint64 popcnt = 0;
352 :
353 21444 : while (bytes--)
354 10762 : popcnt += pg_number_of_ones[(unsigned char) *buf++];
355 10682 : return popcnt;
356 : }
357 :
358 28 : return pg_popcount_optimized(buf, bytes);
359 : }
360 :
361 : /*
362 : * Returns the number of 1-bits in buf after applying the mask to each byte.
363 : *
364 : * Similar to pg_popcount(), we only take on the function pointer overhead when
365 : * it's likely to be faster.
366 : */
367 : static inline uint64
368 52584 : pg_popcount_masked(const char *buf, int bytes, bits8 mask)
369 : {
370 : /*
371 : * We set the threshold to the point at which we'll first use special
372 : * instructions in the optimized version.
373 : */
374 : #if SIZEOF_VOID_P >= 8
375 52584 : int threshold = 8;
376 : #else
377 : int threshold = 4;
378 : #endif
379 :
380 52584 : if (bytes < threshold)
381 : {
382 0 : uint64 popcnt = 0;
383 :
384 0 : while (bytes--)
385 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
386 0 : return popcnt;
387 : }
388 :
389 52584 : return pg_popcount_masked_optimized(buf, bytes, mask);
390 : }
391 :
392 : /*
393 : * Rotate the bits of "word" to the right/left by n bits.
394 : */
395 : static inline uint32
396 13177226 : pg_rotate_right32(uint32 word, int n)
397 : {
398 13177226 : return (word >> n) | (word << (32 - n));
399 : }
400 :
401 : static inline uint32
402 4951388056 : pg_rotate_left32(uint32 word, int n)
403 : {
404 4951388056 : return (word << n) | (word >> (32 - n));
405 : }
406 :
407 : /* size_t variants of the above, as required */
408 :
409 : #if SIZEOF_SIZE_T == 4
410 : #define pg_leftmost_one_pos_size_t pg_leftmost_one_pos32
411 : #define pg_nextpower2_size_t pg_nextpower2_32
412 : #define pg_prevpower2_size_t pg_prevpower2_32
413 : #else
414 : #define pg_leftmost_one_pos_size_t pg_leftmost_one_pos64
415 : #define pg_nextpower2_size_t pg_nextpower2_64
416 : #define pg_prevpower2_size_t pg_prevpower2_64
417 : #endif
418 :
419 : #endif /* PG_BITUTILS_H */
|
