Branch data 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_popcount32_portable
101 : : * Return the number of 1 bits set in word
102 : : */
103 : : int
104 : 0 : pg_popcount32_portable(uint32 word)
105 : : {
106 : : #ifdef HAVE__BUILTIN_POPCOUNT
107 : 0 : return __builtin_popcount(word);
108 : : #else /* !HAVE__BUILTIN_POPCOUNT */
109 : : int result = 0;
110 : :
111 : : while (word != 0)
112 : : {
113 : : result += pg_number_of_ones[word & 255];
114 : : word >>= 8;
115 : : }
116 : :
117 : : return result;
118 : : #endif /* HAVE__BUILTIN_POPCOUNT */
119 : : }
120 : :
121 : : /*
122 : : * pg_popcount64_portable
123 : : * Return the number of 1 bits set in word
124 : : */
125 : : int
126 : 0 : pg_popcount64_portable(uint64 word)
127 : : {
128 : : #ifdef HAVE__BUILTIN_POPCOUNT
129 : : #if SIZEOF_LONG == 8
130 : 0 : return __builtin_popcountl(word);
131 : : #elif SIZEOF_LONG_LONG == 8
132 : : return __builtin_popcountll(word);
133 : : #else
134 : : #error "cannot find integer of the same size as uint64_t"
135 : : #endif
136 : : #else /* !HAVE__BUILTIN_POPCOUNT */
137 : : int result = 0;
138 : :
139 : : while (word != 0)
140 : : {
141 : : result += pg_number_of_ones[word & 255];
142 : : word >>= 8;
143 : : }
144 : :
145 : : return result;
146 : : #endif /* HAVE__BUILTIN_POPCOUNT */
147 : : }
148 : :
149 : : /*
150 : : * pg_popcount_portable
151 : : * Returns the number of 1-bits in buf
152 : : */
153 : : uint64
154 : 0 : pg_popcount_portable(const char *buf, int bytes)
155 : : {
156 : 0 : uint64 popcnt = 0;
157 : :
158 : : #if SIZEOF_VOID_P >= 8
159 : : /* Process in 64-bit chunks if the buffer is aligned. */
160 [ # # ]: 0 : if (buf == (const char *) TYPEALIGN(8, buf))
161 : : {
162 : 0 : const uint64 *words = (const uint64 *) buf;
163 : :
164 [ # # ]: 0 : while (bytes >= 8)
165 : : {
166 : 0 : popcnt += pg_popcount64_portable(*words++);
167 : 0 : bytes -= 8;
168 : : }
169 : :
170 : 0 : buf = (const char *) words;
171 : 0 : }
172 : : #else
173 : : /* Process in 32-bit chunks if the buffer is aligned. */
174 : : if (buf == (const char *) TYPEALIGN(4, buf))
175 : : {
176 : : const uint32 *words = (const uint32 *) buf;
177 : :
178 : : while (bytes >= 4)
179 : : {
180 : : popcnt += pg_popcount32_portable(*words++);
181 : : bytes -= 4;
182 : : }
183 : :
184 : : buf = (const char *) words;
185 : : }
186 : : #endif
187 : :
188 : : /* Process any remaining bytes */
189 [ # # ]: 0 : while (bytes--)
190 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++];
191 : :
192 : 0 : return popcnt;
193 : 0 : }
194 : :
195 : : /*
196 : : * pg_popcount_masked_portable
197 : : * Returns the number of 1-bits in buf after applying the mask to each byte
198 : : */
199 : : uint64
200 : 0 : pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask)
201 : : {
202 : 0 : uint64 popcnt = 0;
203 : :
204 : : #if SIZEOF_VOID_P >= 8
205 : : /* Process in 64-bit chunks if the buffer is aligned */
206 : 0 : uint64 maskv = ~UINT64CONST(0) / 0xFF * mask;
207 : :
208 [ # # ]: 0 : if (buf == (const char *) TYPEALIGN(8, buf))
209 : : {
210 : 0 : const uint64 *words = (const uint64 *) buf;
211 : :
212 [ # # ]: 0 : while (bytes >= 8)
213 : : {
214 : 0 : popcnt += pg_popcount64_portable(*words++ & maskv);
215 : 0 : bytes -= 8;
216 : : }
217 : :
218 : 0 : buf = (const char *) words;
219 : 0 : }
220 : : #else
221 : : /* Process in 32-bit chunks if the buffer is aligned. */
222 : : uint32 maskv = ~((uint32) 0) / 0xFF * mask;
223 : :
224 : : if (buf == (const char *) TYPEALIGN(4, buf))
225 : : {
226 : : const uint32 *words = (const uint32 *) buf;
227 : :
228 : : while (bytes >= 4)
229 : : {
230 : : popcnt += pg_popcount32_portable(*words++ & maskv);
231 : : bytes -= 4;
232 : : }
233 : :
234 : : buf = (const char *) words;
235 : : }
236 : : #endif
237 : :
238 : : /* Process any remaining bytes */
239 [ # # ]: 0 : while (bytes--)
240 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
241 : :
242 : 0 : return popcnt;
243 : 0 : }
244 : :
245 : : #if !defined(HAVE_X86_64_POPCNTQ) && !defined(USE_NEON)
246 : :
247 : : /*
248 : : * When special CPU instructions are not available, there's no point in using
249 : : * function pointers to vary the implementation. We instead just make these
250 : : * actual external functions. The compiler should be able to inline the
251 : : * portable versions here.
252 : : */
253 : : int
254 : : pg_popcount32(uint32 word)
255 : : {
256 : : return pg_popcount32_portable(word);
257 : : }
258 : :
259 : : int
260 : : pg_popcount64(uint64 word)
261 : : {
262 : : return pg_popcount64_portable(word);
263 : : }
264 : :
265 : : /*
266 : : * pg_popcount_optimized
267 : : * Returns the number of 1-bits in buf
268 : : */
269 : : uint64
270 : : pg_popcount_optimized(const char *buf, int bytes)
271 : : {
272 : : return pg_popcount_portable(buf, bytes);
273 : : }
274 : :
275 : : /*
276 : : * pg_popcount_masked_optimized
277 : : * Returns the number of 1-bits in buf after applying the mask to each byte
278 : : */
279 : : uint64
280 : : pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
281 : : {
282 : : return pg_popcount_masked_portable(buf, bytes, mask);
283 : : }
284 : :
285 : : #endif /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */
|
