1 /*-------------------------------------------------------------------------
2 *
3 * pg_bitutils.h
4 * Miscellaneous functions for bit-wise operations.
5 *
6 *
7 * Copyright (c) 2019-2020, 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
pg_leftmost_one_pos32(uint32 word)32 pg_leftmost_one_pos32(uint32 word)
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
pg_leftmost_one_pos64(uint64 word)55 pg_leftmost_one_pos64(uint64 word)
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
pg_rightmost_one_pos32(uint32 word)85 pg_rightmost_one_pos32(uint32 word)
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
pg_rightmost_one_pos64(uint64 word)111 pg_rightmost_one_pos64(uint64 word)
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
pg_nextpower2_32(uint32 num)146 pg_nextpower2_32(uint32 num)
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
pg_nextpower2_64(uint64 num)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
pg_prevpower2_32(uint32 num)202 pg_prevpower2_32(uint32 num)
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
pg_prevpower2_64(uint64 num)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
pg_ceil_log2_32(uint32 num)235 pg_ceil_log2_32(uint32 num)
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
pg_ceil_log2_64(uint64 num)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 /* Count the number of one-bits in a uint32 or uint64 */
257 extern int (*pg_popcount32) (uint32 word);
258 extern int (*pg_popcount64) (uint64 word);
259
260 /* Count the number of one-bits in a byte array */
261 extern uint64 pg_popcount(const char *buf, int bytes);
262
263 /*
264 * Rotate the bits of "word" to the right by n bits.
265 */
266 static inline uint32
pg_rotate_right32(uint32 word,int n)267 pg_rotate_right32(uint32 word, int n)
268 {
269 return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
270 }
271
272 #endif /* PG_BITUTILS_H */
273