MobilityDB 1.1
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
17extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
18extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
19extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
20#else
21extern const uint8 pg_leftmost_one_pos[256];
22extern const uint8 pg_rightmost_one_pos[256];
23extern 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 */
31static 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 */
54static 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 */
84static 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 */
110static 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 */
145static 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 */
168static inline uint64
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 */
201static 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 */
214static inline uint64
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 */
234static 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 */
247static inline uint64
249{
250 if (num < 2)
251 return 0;
252 else
253 return pg_leftmost_one_pos64(num - 1) + 1;
254}
255
256/* Count the number of one-bits in a uint32 or uint64 */
257extern int (*pg_popcount32) (uint32 word);
258extern int (*pg_popcount64) (uint64 word);
259
260/* Count the number of one-bits in a byte array */
261extern uint64 pg_popcount(const char *buf, int bytes);
262
263/*
264 * Rotate the bits of "word" to the right by n bits.
265 */
266static inline uint32
268{
269 return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
270}
271
272#endif /* PG_BITUTILS_H */
#define PGDLLIMPORT
Definition: c.h:1321
#define PG_UINT32_MAX
Definition: c.h:530
#define Assert(condition)
Definition: c.h:811
#define PG_UINT64_MAX
Definition: c.h:533
int(* pg_popcount64)(uint64 word)
Definition: pg_bitutils.c:133
PGDLLIMPORT const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
static int pg_rightmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:111
static uint32 pg_nextpower2_32(uint32 num)
Definition: pg_bitutils.h:146
static uint64 pg_ceil_log2_64(uint64 num)
Definition: pg_bitutils.h:248
static uint32 pg_rotate_right32(uint32 word, int n)
Definition: pg_bitutils.h:267
static int pg_rightmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:85
static uint64 pg_nextpower2_64(uint64 num)
Definition: pg_bitutils.h:169
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:32
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:235
static uint32 pg_prevpower2_32(uint32 num)
Definition: pg_bitutils.h:202
static uint64 pg_prevpower2_64(uint64 num)
Definition: pg_bitutils.h:215
int(* pg_popcount32)(uint32 word)
Definition: pg_bitutils.c:132
uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.c:282
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:55
#define BITS_PER_BYTE
Definition: pg_config_manual.h:132
unsigned int uint32
Definition: pg_ext_defs.in.h:13
unsigned char uint8
Definition: pg_ext_defs.in.h:11
unsigned long int uint64
Definition: pg_ext_defs.in.h:14