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
104 0 : pg_popcount_portable(const char *buf, int bytes)
105 : {
106 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 : {
116 0 : popcnt += pg_popcount64(*words++);
117 0 : bytes -= 8;
118 : }
119 :
120 0 : buf = (const char *) words;
121 : }
122 : #endif
123 :
124 : /* Process any remaining bytes */
125 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
136 0 : pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask)
137 : {
138 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 : {
150 0 : popcnt += pg_popcount64(*words++ & maskv);
151 0 : bytes -= 8;
152 : }
153 :
154 0 : buf = (const char *) words;
155 : }
156 : #endif
157 :
158 : /* Process any remaining bytes */
159 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, bits8 mask)
190 : {
191 : return pg_popcount_masked_portable(buf, bytes, mask);
192 : }
193 :
194 : #endif /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */
|
