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