Age Owner TLA Line data Source code
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
1514 tgl 41 GIC 537097964 : pg_leftmost_one_pos32(uint32 word)
42 : {
43 : #ifdef HAVE__BUILTIN_CLZ
46 john.naylor 44 537097964 : Assert(word != 0);
45 :
46 537097964 : 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];
46 john.naylor 63 ECB : #endif /* HAVE__BUILTIN_CLZ */
64 : }
65 :
1514 tgl 66 : /*
67 : * pg_leftmost_one_pos64
68 : * As above, but for a 64-bit word.
69 : */
70 : static inline int
1514 tgl 71 GIC 1941001 : pg_leftmost_one_pos64(uint64 word)
72 : {
73 : #ifdef HAVE__BUILTIN_CLZ
74 1941001 : Assert(word != 0);
75 :
76 : #if defined(HAVE_LONG_INT_64)
46 john.naylor 77 1941001 : 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 */
1514 tgl 101 ECB : }
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
1514 tgl 109 GIC 248 : pg_rightmost_one_pos32(uint32 word)
110 : {
111 : #ifdef HAVE__BUILTIN_CTZ
46 john.naylor 112 248 : Assert(word != 0);
113 :
114 248 : 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
1514 tgl 142 6021068 : pg_rightmost_one_pos64(uint64 word)
143 : {
144 : #ifdef HAVE__BUILTIN_CTZ
46 john.naylor 145 6021068 : Assert(word != 0);
46 john.naylor 146 ECB :
147 : #if defined(HAVE_LONG_INT_64)
46 john.naylor 148 GIC 6021068 : return __builtin_ctzl(word);
46 john.naylor 149 ECB : #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
1096 drowley 185 GIC 42318361 : pg_nextpower2_32(uint32 num)
186 : {
1096 drowley 187 CBC 42318361 : Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
188 :
189 : /*
1096 drowley 190 ECB : * 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 : */
1096 drowley 194 GIC 42318361 : if ((num & (num - 1)) == 0)
195 40561670 : return num; /* already power 2 */
196 :
197 1756691 : 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 28657 : pg_nextpower2_64(uint64 num)
209 : {
210 28657 : 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 28657 : if ((num & (num - 1)) == 0)
218 4999 : return num; /* already power 2 */
219 :
220 23658 : 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.
623 tgl 229 ECB : */
230 : static inline uint32
231 : pg_prevpower2_32(uint32 num)
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
623 tgl 244 GIC 236685 : pg_prevpower2_64(uint64 num)
623 tgl 245 ECB : {
623 tgl 246 GIC 236685 : 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
1096 drowley 254 345616 : pg_ceil_log2_32(uint32 num)
255 : {
256 345616 : if (num < 2)
1096 drowley 257 UIC 0 : return 0;
258 : else
1096 drowley 259 GIC 345616 : 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 547029 : pg_ceil_log2_64(uint64 num)
268 : {
1096 drowley 269 CBC 547029 : if (num < 2)
1096 drowley 270 GIC 205886 : return 0;
1096 drowley 271 ECB : else
1096 drowley 272 GIC 341143 : 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
601 john.naylor 279 ECB : * instructions.
280 : */
281 : #if defined(_MSC_VER) && defined(_M_AMD64)
601 john.naylor 282 EUB : #define HAVE_X86_64_POPCNTQ
283 : #endif
601 john.naylor 284 ECB :
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
1202 tmunro 316 GIC 7629697 : pg_rotate_right32(uint32 word, int n)
317 : {
413 john.naylor 318 7629697 : return (word >> n) | (word << (32 - n));
319 : }
320 :
321 : static inline uint32
322 3373203228 : pg_rotate_left32(uint32 word, int n)
323 : {
324 3373203228 : 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 */
|
