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