PostgreSQL Source Code git master
Loading...
Searching...
No Matches
Functions | Variables
pg_bitutils.c File Reference
#include "c.h"
#include "port/pg_bitutils.h"
Include dependency graph for pg_bitutils.c:

Go to the source code of this file.

Functions

int pg_popcount32_portable (uint32 word)
 
int pg_popcount64_portable (uint64 word)
 
uint64 pg_popcount_portable (const char *buf, int bytes)
 
uint64 pg_popcount_masked_portable (const char *buf, int bytes, bits8 mask)
 
int pg_popcount32 (uint32 word)
 
int pg_popcount64 (uint64 word)
 
uint64 pg_popcount_optimized (const char *buf, int bytes)
 
uint64 pg_popcount_masked_optimized (const char *buf, int bytes, bits8 mask)
 

Variables

const uint8 pg_leftmost_one_pos [256]
 
const uint8 pg_rightmost_one_pos [256]
 
const uint8 pg_number_of_ones [256]
 

Function Documentation

◆ pg_popcount32()

int pg_popcount32 ( uint32  word)

Definition at line 254 of file pg_bitutils.c.

255{
256 return pg_popcount32_portable(word);
257}
pg_popcount32_portable
int pg_popcount32_portable(uint32 word)
Definition pg_bitutils.c:104
word
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition regcomp.c:1476

References pg_popcount32_portable(), and word().

Referenced by plan_single_revoke().

◆ pg_popcount32_portable()

int pg_popcount32_portable ( uint32  word)

Definition at line 104 of file pg_bitutils.c.

105{
106#ifdef HAVE__BUILTIN_POPCOUNT
107 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}
pg_number_of_ones
const uint8 pg_number_of_ones[256]
Definition pg_bitutils.c:80
fb
static int fb(int x)
Definition preproc-init.c:92

References fb(), pg_number_of_ones, and word().

Referenced by pg_popcount32(), pg_popcount_masked_portable(), and pg_popcount_portable().

◆ pg_popcount64()

int pg_popcount64 ( uint64  word)

Definition at line 260 of file pg_bitutils.c.

261{
262 return pg_popcount64_portable(word);
263}
pg_popcount64_portable
int pg_popcount64_portable(uint64 word)
Definition pg_bitutils.c:126

References pg_popcount64_portable(), and word().

Referenced by select_best_grantor().

◆ pg_popcount64_portable()

int pg_popcount64_portable ( uint64  word)

Definition at line 126 of file pg_bitutils.c.

127{
128#ifdef HAVE__BUILTIN_POPCOUNT
129#if SIZEOF_LONG == 8
130 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}

References fb(), pg_number_of_ones, and word().

Referenced by pg_popcount64(), pg_popcount_masked_portable(), and pg_popcount_portable().

◆ pg_popcount_masked_optimized()

uint64 pg_popcount_masked_optimized ( const char *  buf,
int  bytes,
bits8  mask 
)

Definition at line 280 of file pg_bitutils.c.

281{
282 return pg_popcount_masked_portable(buf, bytes, mask);
283}
pg_popcount_masked_portable
uint64 pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask)
Definition pg_bitutils.c:200
buf
static char buf[DEFAULT_XLOG_SEG_SIZE]
Definition pg_test_fsync.c:71

References buf, and pg_popcount_masked_portable().

Referenced by pg_popcount_masked().

◆ pg_popcount_masked_portable()

uint64 pg_popcount_masked_portable ( const char *  buf,
int  bytes,
bits8  mask 
)

Definition at line 200 of file pg_bitutils.c.

201{
202 uint64 popcnt = 0;
203
204#if SIZEOF_VOID_P >= 8
205 /* Process in 64-bit chunks if the buffer is aligned */
206 uint64 maskv = ~UINT64CONST(0) / 0xFF * mask;
207
208 if (buf == (const char *) TYPEALIGN(8, buf))
209 {
210 const uint64 *words = (const uint64 *) buf;
211
212 while (bytes >= 8)
213 {
214 popcnt += pg_popcount64_portable(*words++ & maskv);
215 bytes -= 8;
216 }
217
218 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 while (bytes--)
240 popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
241
242 return popcnt;
243}
TYPEALIGN
#define TYPEALIGN(ALIGNVAL, LEN)
Definition c.h:819
uint64
uint64_t uint64
Definition c.h:547
uint32
uint32_t uint32
Definition c.h:546

References buf, fb(), pg_number_of_ones, pg_popcount32_portable(), pg_popcount64_portable(), and TYPEALIGN.

Referenced by pg_popcount_masked_optimized().

◆ pg_popcount_optimized()

uint64 pg_popcount_optimized ( const char *  buf,
int  bytes 
)

Definition at line 270 of file pg_bitutils.c.

271{
272 return pg_popcount_portable(buf, bytes);
273}
pg_popcount_portable
uint64 pg_popcount_portable(const char *buf, int bytes)
Definition pg_bitutils.c:154

References buf, and pg_popcount_portable().

Referenced by pg_popcount().

◆ pg_popcount_portable()

uint64 pg_popcount_portable ( const char *  buf,
int  bytes 
)

Definition at line 154 of file pg_bitutils.c.

155{
156 uint64 popcnt = 0;
157
158#if SIZEOF_VOID_P >= 8
159 /* Process in 64-bit chunks if the buffer is aligned. */
160 if (buf == (const char *) TYPEALIGN(8, buf))
161 {
162 const uint64 *words = (const uint64 *) buf;
163
164 while (bytes >= 8)
165 {
166 popcnt += pg_popcount64_portable(*words++);
167 bytes -= 8;
168 }
169
170 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 while (bytes--)
190 popcnt += pg_number_of_ones[(unsigned char) *buf++];
191
192 return popcnt;
193}

References buf, fb(), pg_number_of_ones, pg_popcount32_portable(), pg_popcount64_portable(), and TYPEALIGN.

Referenced by pg_popcount_optimized().

Variable Documentation

◆ pg_leftmost_one_pos

const uint8 pg_leftmost_one_pos[256]
Initial value:
= {
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
}

Definition at line 27 of file pg_bitutils.c.

27 {
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};

Referenced by AllocSetFreeIndex(), pg_leftmost_one_pos32(), and pg_leftmost_one_pos64().

◆ pg_number_of_ones

const uint8 pg_number_of_ones[256]
Initial value:
= {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
}

Definition at line 80 of file pg_bitutils.c.

80 {
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};

Referenced by hemdistsign(), hemdistsign(), hemdistsign(), hemdistsign(), pg_popcount(), pg_popcount32_portable(), pg_popcount64_portable(), pg_popcount_masked(), pg_popcount_masked_portable(), pg_popcount_portable(), and process_pipe_input().

◆ pg_rightmost_one_pos

const uint8 pg_rightmost_one_pos[256]
Initial value:
= {
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
}

Definition at line 55 of file pg_bitutils.c.

55 {
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};

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().