PostgreSQL Source Code  git master
pg_bitutils.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * pg_bitutils.c
4  * Miscellaneous functions for bit-wise operations.
5  *
6  * Copyright (c) 2019-2021, PostgreSQL Global Development Group
7  *
8  * IDENTIFICATION
9  * src/port/pg_bitutils.c
10  *
11  *-------------------------------------------------------------------------
12  */
13 #include "c.h"
14 
15 #ifdef HAVE__GET_CPUID
16 #include <cpuid.h>
17 #endif
18 #ifdef HAVE__CPUID
19 #include <intrin.h>
20 #endif
21 
22 #include "port/pg_bitutils.h"
23 
24 
25 /*
26  * Array giving the position of the left-most set bit for each possible
27  * byte value. We count the right-most position as the 0th bit, and the
28  * left-most the 7th bit. The 0th entry of the array should not be used.
29  *
30  * Note: this is not used by the functions in pg_bitutils.h when
31  * HAVE__BUILTIN_CLZ is defined, but we provide it anyway, so that
32  * extensions possibly compiled with a different compiler can use it.
33  */
34 const uint8 pg_leftmost_one_pos[256] = {
35  0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
36  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
37  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
38  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
39  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
40  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
41  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
42  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
43  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
44  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
45  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
46  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
47  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
48  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
49  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
50  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
51 };
52 
53 /*
54  * Array giving the position of the right-most set bit for each possible
55  * byte value. We count the right-most position as the 0th bit, and the
56  * left-most the 7th bit. The 0th entry of the array should not be used.
57  *
58  * Note: this is not used by the functions in pg_bitutils.h when
59  * HAVE__BUILTIN_CTZ is defined, but we provide it anyway, so that
60  * extensions possibly compiled with a different compiler can use it.
61  */
63  0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
64  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
65  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
66  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
67  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
68  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
69  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
70  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71  7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
72  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
73  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
74  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
75  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
76  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
77  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
78  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
79 };
80 
81 /*
82  * Array giving the number of 1-bits in each possible byte value.
83  *
84  * Note: we export this for use by functions in which explicit use
85  * of the popcount functions seems unlikely to be a win.
86  */
87 const uint8 pg_number_of_ones[256] = {
88  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
89  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
91  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
93  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
95  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
97  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
98  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
99  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
100  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
101  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
102  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
103  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
104 };
105 
106 static int pg_popcount32_slow(uint32 word);
107 static int pg_popcount64_slow(uint64 word);
108 
109 #ifdef TRY_POPCNT_FAST
110 static bool pg_popcount_available(void);
111 static int pg_popcount32_choose(uint32 word);
112 static int pg_popcount64_choose(uint64 word);
113 static int pg_popcount32_fast(uint32 word);
114 static int pg_popcount64_fast(uint64 word);
115 
116 int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
117 int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
118 #endif /* TRY_POPCNT_FAST */
119 
120 #ifdef TRY_POPCNT_FAST
121 
122 /*
123  * Return true if CPUID indicates that the POPCNT instruction is available.
124  */
125 static bool
126 pg_popcount_available(void)
127 {
128  unsigned int exx[4] = {0, 0, 0, 0};
129 
130 #if defined(HAVE__GET_CPUID)
131  __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
132 #elif defined(HAVE__CPUID)
133  __cpuid(exx, 1);
134 #else
135 #error cpuid instruction not available
136 #endif
137 
138  return (exx[2] & (1 << 23)) != 0; /* POPCNT */
139 }
140 
141 /*
142  * These functions get called on the first call to pg_popcount32 etc.
143  * They detect whether we can use the asm implementations, and replace
144  * the function pointers so that subsequent calls are routed directly to
145  * the chosen implementation.
146  */
147 static int
148 pg_popcount32_choose(uint32 word)
149 {
150  if (pg_popcount_available())
151  {
152  pg_popcount32 = pg_popcount32_fast;
153  pg_popcount64 = pg_popcount64_fast;
154  }
155  else
156  {
159  }
160 
161  return pg_popcount32(word);
162 }
163 
164 static int
165 pg_popcount64_choose(uint64 word)
166 {
167  if (pg_popcount_available())
168  {
169  pg_popcount32 = pg_popcount32_fast;
170  pg_popcount64 = pg_popcount64_fast;
171  }
172  else
173  {
176  }
177 
178  return pg_popcount64(word);
179 }
180 
181 /*
182  * pg_popcount32_fast
183  * Return the number of 1 bits set in word
184  */
185 static int
186 pg_popcount32_fast(uint32 word)
187 {
188 #ifdef _MSC_VER
189  return __popcnt(word);
190 #else
191  uint32 res;
192 
193 __asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
194  return (int) res;
195 #endif
196 }
197 
198 /*
199  * pg_popcount64_fast
200  * Return the number of 1 bits set in word
201  */
202 static int
203 pg_popcount64_fast(uint64 word)
204 {
205 #ifdef _MSC_VER
206  return __popcnt64(word);
207 #else
208  uint64 res;
209 
210 __asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
211  return (int) res;
212 #endif
213 }
214 
215 #endif /* TRY_POPCNT_FAST */
216 
217 
218 /*
219  * pg_popcount32_slow
220  * Return the number of 1 bits set in word
221  */
222 static int
224 {
225 #ifdef HAVE__BUILTIN_POPCOUNT
226  return __builtin_popcount(word);
227 #else /* !HAVE__BUILTIN_POPCOUNT */
228  int result = 0;
229 
230  while (word != 0)
231  {
232  result += pg_number_of_ones[word & 255];
233  word >>= 8;
234  }
235 
236  return result;
237 #endif /* HAVE__BUILTIN_POPCOUNT */
238 }
239 
240 /*
241  * pg_popcount64_slow
242  * Return the number of 1 bits set in word
243  */
244 static int
246 {
247 #ifdef HAVE__BUILTIN_POPCOUNT
248 #if defined(HAVE_LONG_INT_64)
249  return __builtin_popcountl(word);
250 #elif defined(HAVE_LONG_LONG_INT_64)
251  return __builtin_popcountll(word);
252 #else
253 #error must have a working 64-bit integer datatype
254 #endif
255 #else /* !HAVE__BUILTIN_POPCOUNT */
256  int result = 0;
257 
258  while (word != 0)
259  {
260  result += pg_number_of_ones[word & 255];
261  word >>= 8;
262  }
263 
264  return result;
265 #endif /* HAVE__BUILTIN_POPCOUNT */
266 }
267 
268 #ifndef TRY_POPCNT_FAST
269 
270 /*
271  * When the POPCNT instruction is not available, there's no point in using
272  * function pointers to vary the implementation between the fast and slow
273  * method. We instead just make these actual external functions when
274  * TRY_POPCNT_FAST is not defined. The compiler should be able to inline
275  * the slow versions here.
276  */
277 int
279 {
280  return pg_popcount32_slow(word);
281 }
282 
283 int
285 {
286  return pg_popcount64_slow(word);
287 }
288 
289 #endif /* !TRY_POPCNT_FAST */
290 
291 /*
292  * pg_popcount
293  * Returns the number of 1-bits in buf
294  */
295 uint64
296 pg_popcount(const char *buf, int bytes)
297 {
298  uint64 popcnt = 0;
299 
300 #if SIZEOF_VOID_P >= 8
301  /* Process in 64-bit chunks if the buffer is aligned. */
302  if (buf == (const char *) TYPEALIGN(8, buf))
303  {
304  const uint64 *words = (const uint64 *) buf;
305 
306  while (bytes >= 8)
307  {
308  popcnt += pg_popcount64(*words++);
309  bytes -= 8;
310  }
311 
312  buf = (const char *) words;
313  }
314 #else
315  /* Process in 32-bit chunks if the buffer is aligned. */
316  if (buf == (const char *) TYPEALIGN(4, buf))
317  {
318  const uint32 *words = (const uint32 *) buf;
319 
320  while (bytes >= 4)
321  {
322  popcnt += pg_popcount32(*words++);
323  bytes -= 4;
324  }
325 
326  buf = (const char *) words;
327  }
328 #endif
329 
330  /* Process any remaining bytes */
331  while (bytes--)
332  popcnt += pg_number_of_ones[(unsigned char) *buf++];
333 
334  return popcnt;
335 }
int pg_popcount32(uint32 word)
Definition: pg_bitutils.c:278
def bytes(source, encoding='ascii', errors='strict')
uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.c:296
unsigned char uint8
Definition: c.h:439
int pg_popcount64(uint64 word)
Definition: pg_bitutils.c:284
static char * buf
Definition: pg_test_fsync.c:68
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:245
unsigned int uint32
Definition: c.h:441
const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:750
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:223
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1432