PostgreSQL Source Code  git master
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

static int pg_popcount32_slow (uint32 word)
 
static int pg_popcount64_slow (uint64 word)
 
int pg_popcount32 (uint32 word)
 
int pg_popcount64 (uint64 word)
 
uint64 pg_popcount (const char *buf, int bytes)
 

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_popcount()

uint64 pg_popcount ( const char *  buf,
int  bytes 
)

Definition at line 296 of file pg_bitutils.c.

References pg_number_of_ones, pg_popcount32(), pg_popcount64(), and TYPEALIGN.

Referenced by bit_bit_count(), bloom_prop_bits_set(), bytea_bit_count(), heap_tuple_infomask_flags(), pg_ceil_log2_64(), process_pipe_input(), and sizebitvec().

297 {
298  uint64 popcnt = 0;
299 
300 #if SIZEOF_VOID_P >= 8
301  /* Process in 64-bit chunks if the buffer is aligned. */
302  if (buf == (const char *) TYPEALIGN(8, buf))
303  {
304  const uint64 *words = (const uint64 *) buf;
305 
306  while (bytes >= 8)
307  {
308  popcnt += pg_popcount64(*words++);
309  bytes -= 8;
310  }
311 
312  buf = (const char *) words;
313  }
314 #else
315  /* Process in 32-bit chunks if the buffer is aligned. */
316  if (buf == (const char *) TYPEALIGN(4, buf))
317  {
318  const uint32 *words = (const uint32 *) buf;
319 
320  while (bytes >= 4)
321  {
322  popcnt += pg_popcount32(*words++);
323  bytes -= 4;
324  }
325 
326  buf = (const char *) words;
327  }
328 #endif
329 
330  /* Process any remaining bytes */
331  while (bytes--)
332  popcnt += pg_number_of_ones[(unsigned char) *buf++];
333 
334  return popcnt;
335 }
int pg_popcount32(uint32 word)
Definition: pg_bitutils.c:278
def bytes(source, encoding='ascii', errors='strict')
int pg_popcount64(uint64 word)
Definition: pg_bitutils.c:284
static char * buf
Definition: pg_test_fsync.c:68
unsigned int uint32
Definition: c.h:441
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:750

◆ pg_popcount32()

int pg_popcount32 ( uint32  word)

Definition at line 278 of file pg_bitutils.c.

References pg_popcount32_slow().

Referenced by pg_ceil_log2_64(), and pg_popcount().

279 {
280  return pg_popcount32_slow(word);
281 }
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:223
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1432

◆ pg_popcount32_slow()

static int pg_popcount32_slow ( uint32  word)
static

Definition at line 223 of file pg_bitutils.c.

References pg_number_of_ones.

Referenced by pg_popcount32().

224 {
225 #ifdef HAVE__BUILTIN_POPCOUNT
226  return __builtin_popcount(word);
227 #else /* !HAVE__BUILTIN_POPCOUNT */
228  int result = 0;
229 
230  while (word != 0)
231  {
232  result += pg_number_of_ones[word & 255];
233  word >>= 8;
234  }
235 
236  return result;
237 #endif /* HAVE__BUILTIN_POPCOUNT */
238 }
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1432

◆ pg_popcount64()

int pg_popcount64 ( uint64  word)

Definition at line 284 of file pg_bitutils.c.

References pg_popcount64_slow().

Referenced by pg_ceil_log2_64(), pg_popcount(), and visibilitymap_count().

285 {
286  return pg_popcount64_slow(word);
287 }
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:245
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1432

◆ pg_popcount64_slow()

static int pg_popcount64_slow ( uint64  word)
static

Definition at line 245 of file pg_bitutils.c.

References pg_number_of_ones.

Referenced by pg_popcount64().

246 {
247 #ifdef HAVE__BUILTIN_POPCOUNT
248 #if defined(HAVE_LONG_INT_64)
249  return __builtin_popcountl(word);
250 #elif defined(HAVE_LONG_LONG_INT_64)
251  return __builtin_popcountll(word);
252 #else
253 #error must have a working 64-bit integer datatype
254 #endif
255 #else /* !HAVE__BUILTIN_POPCOUNT */
256  int result = 0;
257 
258  while (word != 0)
259  {
260  result += pg_number_of_ones[word & 255];
261  word >>= 8;
262  }
263 
264  return result;
265 #endif /* HAVE__BUILTIN_POPCOUNT */
266 }
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1432

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 34 of file pg_bitutils.c.

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 87 of file pg_bitutils.c.

Referenced by hemdistsign(), pg_popcount(), pg_popcount32_slow(), and pg_popcount64_slow().

◆ 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 62 of file pg_bitutils.c.

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().