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 : }
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 : }
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 : }
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 : }
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 */
|
