Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pg_bitutils.c
4 : : * Miscellaneous functions for bit-wise operations.
5 : : *
6 : : * Copyright (c) 2019-2026, PostgreSQL Global Development Group
7 : : *
8 : : * IDENTIFICATION
9 : : * src/port/pg_bitutils.c
10 : : *
11 : : *-------------------------------------------------------------------------
12 : : */
13 : : #include "c.h"
14 : :
15 : : #include "port/pg_bitutils.h"
16 : :
17 : :
18 : : /*
19 : : * Array giving the position of the left-most set bit for each possible
20 : : * byte value. We count the right-most position as the 0th bit, and the
21 : : * left-most the 7th bit. The 0th entry of the array should not be used.
22 : : *
23 : : * Note: this is not used by the functions in pg_bitutils.h when
24 : : * HAVE__BUILTIN_CLZ is defined, but we provide it anyway, so that
25 : : * extensions possibly compiled with a different compiler can use it.
26 : : */
27 : : const uint8 pg_leftmost_one_pos[256] = {
28 : : 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
29 : : 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
30 : : 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
31 : : 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
32 : : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
33 : : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
34 : : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
35 : : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
36 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
37 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
38 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
39 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
40 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
41 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
42 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
43 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
44 : : };
45 : :
46 : : /*
47 : : * Array giving the position of the right-most set bit for each possible
48 : : * byte value. We count the right-most position as the 0th bit, and the
49 : : * left-most the 7th bit. The 0th entry of the array should not be used.
50 : : *
51 : : * Note: this is not used by the functions in pg_bitutils.h when
52 : : * HAVE__BUILTIN_CTZ is defined, but we provide it anyway, so that
53 : : * extensions possibly compiled with a different compiler can use it.
54 : : */
55 : : const uint8 pg_rightmost_one_pos[256] = {
56 : : 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
57 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
58 : : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
59 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
60 : : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
61 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
62 : : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
63 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
64 : : 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
65 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
66 : : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
67 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
68 : : 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
69 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
70 : : 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71 : : 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
72 : : };
73 : :
74 : : /*
75 : : * Array giving the number of 1-bits in each possible byte value.
76 : : *
77 : : * Note: we export this for use by functions in which explicit use
78 : : * of the popcount functions seems unlikely to be a win.
79 : : */
80 : : const uint8 pg_number_of_ones[256] = {
81 : : 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
82 : : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
83 : : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
84 : : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
85 : : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
86 : : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
87 : : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
88 : : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
89 : : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90 : : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
91 : : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92 : : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
93 : : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94 : : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
95 : : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96 : : 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
97 : : };
98 : :
99 : : /*
100 : : * pg_popcount_portable
101 : : * Returns the number of 1-bits in buf
102 : : */
103 : : uint64
160 nathan@postgresql.or 104 :UNC 0 : pg_popcount_portable(const char *buf, int bytes)
105 : : {
2692 tgl@sss.pgh.pa.us 106 :UBC 0 : uint64 popcnt = 0;
107 : :
108 : : #if SIZEOF_VOID_P >= 8
109 : : /* Process in 64-bit chunks if the buffer is aligned. */
110 [ # # ]: 0 : if (buf == (const char *) TYPEALIGN(8, buf))
111 : : {
112 : 0 : const uint64 *words = (const uint64 *) buf;
113 : :
114 [ # # ]: 0 : while (bytes >= 8)
115 : : {
138 nathan@postgresql.or 116 :UNC 0 : popcnt += pg_popcount64(*words++);
2692 tgl@sss.pgh.pa.us 117 :UBC 0 : bytes -= 8;
118 : : }
119 : :
2692 tgl@sss.pgh.pa.us 120 :UIC 0 : buf = (const char *) words;
121 : : }
122 : : #endif
123 : :
124 : : /* Process any remaining bytes */
2692 tgl@sss.pgh.pa.us 125 [ # # ]:UBC 0 : while (bytes--)
126 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++];
127 : :
128 : 0 : return popcnt;
129 : : }
130 : :
131 : : /*
132 : : * pg_popcount_masked_portable
133 : : * Returns the number of 1-bits in buf after applying the mask to each byte
134 : : */
135 : : uint64
92 nathan@postgresql.or 136 :UNC 0 : pg_popcount_masked_portable(const char *buf, int bytes, uint8 mask)
137 : : {
815 nathan@postgresql.or 138 :UBC 0 : uint64 popcnt = 0;
139 : :
140 : : #if SIZEOF_VOID_P >= 8
141 : : /* Process in 64-bit chunks if the buffer is aligned */
142 : 0 : uint64 maskv = ~UINT64CONST(0) / 0xFF * mask;
143 : :
144 [ # # ]: 0 : if (buf == (const char *) TYPEALIGN(8, buf))
145 : : {
146 : 0 : const uint64 *words = (const uint64 *) buf;
147 : :
148 [ # # ]: 0 : while (bytes >= 8)
149 : : {
138 nathan@postgresql.or 150 :UNC 0 : popcnt += pg_popcount64(*words++ & maskv);
815 nathan@postgresql.or 151 :UBC 0 : bytes -= 8;
152 : : }
153 : :
815 nathan@postgresql.or 154 :UIC 0 : buf = (const char *) words;
155 : : }
156 : : #endif
157 : :
158 : : /* Process any remaining bytes */
815 nathan@postgresql.or 159 [ # # ]:UBC 0 : while (bytes--)
160 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
161 : :
162 : 0 : return popcnt;
163 : : }
164 : :
165 : : #if !defined(HAVE_X86_64_POPCNTQ) && !defined(USE_NEON)
166 : :
167 : : /*
168 : : * When special CPU instructions are not available, there's no point in using
169 : : * function pointers to vary the implementation. We instead just make these
170 : : * actual external functions. The compiler should be able to inline the
171 : : * portable versions here.
172 : : */
173 : :
174 : : /*
175 : : * pg_popcount_optimized
176 : : * Returns the number of 1-bits in buf
177 : : */
178 : : uint64
179 : : pg_popcount_optimized(const char *buf, int bytes)
180 : : {
181 : : return pg_popcount_portable(buf, bytes);
182 : : }
183 : :
184 : : /*
185 : : * pg_popcount_masked_optimized
186 : : * Returns the number of 1-bits in buf after applying the mask to each byte
187 : : */
188 : : uint64
189 : : pg_popcount_masked_optimized(const char *buf, int bytes, uint8 mask)
190 : : {
191 : : return pg_popcount_masked_portable(buf, bytes, mask);
192 : : }
193 : :
194 : : #endif /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */
195 : : /* BEGIN: function "pg_popcount64_choose" */
196 : : /* (content generated from coverage data) */
197 : : /* ... */
198 : : /* ... */
199 : : /* ... */
200 : : /* ... */
201 : : /* ... */
202 : : /* BEGIN: function "pg_popcount_choose" */
203 : : /* ... */
204 : : /* ... */
205 : : /* ... */
206 : : /* ... */
207 : : /* ... */
208 : : /* ... */
209 : : /* BEGIN: function "pg_popcount_masked_choose" */
210 : : /* ... */
211 : : /* ... */
212 : : /* ... */
213 : : /* ... */
214 : : /* ... */
215 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
216 : : /* (content generated from coverage data) */
217 : : /* ... */
218 : : /* ... */
219 : : /* ... */
220 : : /* BEGIN: function "pg_popcount32_fast" */
221 : : /* ... */
222 : : /* ... */
223 : : /* ... */
224 : : /* ... */
225 : : /* ... */
226 : : /* ... */
227 : : /* ... */
228 : : /* ... */
229 : : /* ... */
230 : : /* ... */
231 : : /* ... */
232 : : /* ... */
233 : : /* ... */
234 : : /* ... */
235 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
236 : : /* (content generated from coverage data) */
237 : : /* BEGIN: function "pg_popcount64_fast" */
238 : : /* ... */
239 : : /* ... */
240 : : /* ... */
241 : : /* ... */
242 : : /* ... */
243 : : /* ... */
244 : : /* ... */
245 : : /* ... */
246 : : /* ... */
247 : : /* ... */
248 : : /* ... */
249 : : /* ... */
250 : : /* ... */
251 : : /* ... */
252 : : /* ... */
253 : : /* ... */
254 : : /* BEGIN: function "pg_popcount_fast" */
255 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
256 : : /* (content generated from coverage data) */
257 : : /* ... */
258 : : /* ... */
259 : : /* ... */
260 : : /* ... */
261 : : /* ... */
262 : : /* ... */
263 : : /* ... */
264 : : /* ... */
265 : : /* ... */
266 : : /* ... */
267 : : /* ... */
268 : : /* ... */
269 : : /* ... */
270 : : /* ... */
271 : : /* ... */
272 : : /* ... */
273 : : /* ... */
274 : : /* ... */
275 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
276 : : /* (content generated from coverage data) */
277 : : /* ... */
278 : : /* ... */
279 : : /* ... */
280 : : /* ... */
281 : : /* ... */
282 : : /* ... */
283 : : /* ... */
284 : : /* ... */
285 : : /* ... */
286 : : /* ... */
287 : : /* ... */
288 : : /* ... */
289 : : /* ... */
290 : : /* ... */
291 : : /* ... */
292 : : /* ... */
293 : : /* ... */
294 : : /* ... */
295 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
296 : : /* (content generated from coverage data) */
297 : : /* ... */
298 : : /* ... */
299 : : /* ... */
300 : : /* BEGIN: function "pg_popcount_masked_fast" */
301 : : /* ... */
302 : : /* ... */
303 : : /* ... */
304 : : /* ... */
305 : : /* ... */
306 : : /* ... */
307 : : /* ... */
308 : : /* ... */
309 : : /* ... */
310 : : /* ... */
311 : : /* ... */
312 : : /* ... */
313 : : /* ... */
314 : : /* ... */
315 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
316 : : /* (content generated from coverage data) */
317 : : /* ... */
318 : : /* ... */
319 : : /* ... */
320 : : /* ... */
321 : : /* ... */
322 : : /* ... */
323 : : /* ... */
324 : : /* ... */
325 : : /* ... */
326 : : /* ... */
327 : : /* ... */
328 : : /* ... */
329 : : /* ... */
330 : : /* ... */
331 : : /* ... */
332 : : /* ... */
333 : : /* ... */
334 : : /* ... */
335 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
336 : : /* (content generated from coverage data) */
337 : : /* ... */
338 : : /* ... */
339 : : /* ... */
340 : : /* ... */
341 : : /* ... */
342 : : /* ... */
343 : : /* ... */
344 : : /* ... */
345 : : /* ... */
346 : : /* ... */
347 : : /* ... */
348 : : /* ... */
349 : : /* ... */
350 : : /* ... */
351 : : /* ... */
352 : : /* ... */
353 : : /* ... */
354 : : /* ... */
355 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
356 : : /* (content generated from coverage data) */
357 : : /* BEGIN: function "pg_popcount32_slow" */
358 : : /* ... */
359 : : /* ... */
360 : : /* ... */
361 : : /* ... */
362 : : /* ... */
363 : : /* ... */
364 : : /* ... */
365 : : /* ... */
366 : : /* ... */
367 : : /* ... */
368 : : /* ... */
369 : : /* ... */
370 : : /* ... */
371 : : /* ... */
372 : : /* ... */
373 : : /* ... */
374 : : /* ... */
375 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
376 : : /* (content generated from coverage data) */
377 : : /* ... */
378 : : /* ... */
379 : : /* BEGIN: function "pg_popcount64_slow" */
380 : : /* ... */
381 : : /* ... */
382 : : /* ... */
383 : : /* ... */
384 : : /* ... */
385 : : /* ... */
386 : : /* ... */
387 : : /* ... */
388 : : /* ... */
389 : : /* ... */
390 : : /* ... */
391 : : /* ... */
392 : : /* ... */
393 : : /* ... */
394 : : /* ... */
395 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
396 : : /* (content generated from coverage data) */
397 : : /* ... */
398 : : /* ... */
399 : : /* ... */
400 : : /* ... */
401 : : /* ... */
402 : : /* ... */
403 : : /* ... */
404 : : /* ... */
405 : : /* ... */
406 : : /* ... */
407 : : /* BEGIN: function "pg_popcount_slow" */
408 : : /* ... */
409 : : /* ... */
410 : : /* ... */
411 : : /* ... */
412 : : /* ... */
413 : : /* ... */
414 : : /* ... */
415 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
416 : : /* (content generated from coverage data) */
417 : : /* ... */
418 : : /* ... */
419 : : /* ... */
420 : : /* ... */
421 : : /* ... */
422 : : /* ... */
423 : : /* ... */
424 : : /* ... */
425 : : /* ... */
426 : : /* ... */
427 : : /* ... */
428 : : /* ... */
429 : : /* ... */
430 : : /* ... */
431 : : /* ... */
432 : : /* ... */
433 : : /* ... */
434 : : /* ... */
435 : : /* /home/coverage/diff-cov-workdir/pg-current/src/port/pg_bitutils.c not long enough */
436 : : /* (content generated from coverage data) */
437 : : /* ... */
438 : : /* ... */
439 : : /* ... */
440 : : /* ... */
441 : : /* ... */
442 : : /* ... */
443 : : /* ... */
444 : : /* ... */
445 : : /* ... */
446 : : /* ... */
447 : : /* ... */
448 : : /* ... */
449 : : /* ... */
450 : : /* ... */
451 : : /* ... */
452 : : /* ... */
453 : : /* BEGIN: function "pg_popcount_masked_slow" */
|
