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)
 
static uint64 pg_popcount_slow (const char *buf, int bytes)
 
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 413 of file pg_bitutils.c.

414 {
415  return pg_popcount_slow(buf, bytes);
416 }
static uint64 pg_popcount_slow(const char *buf, int bytes)
Definition: pg_bitutils.c:346
static char * buf
Definition: pg_test_fsync.c:73

References buf, and pg_popcount_slow().

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

◆ pg_popcount32()

int pg_popcount32 ( uint32  word)

Definition at line 397 of file pg_bitutils.c.

398 {
399  return pg_popcount32_slow(word);
400 }
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:296
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1474

References pg_popcount32_slow(), and word().

Referenced by plan_single_revoke().

◆ pg_popcount32_slow()

static int pg_popcount32_slow ( uint32  word)
inlinestatic

Definition at line 296 of file pg_bitutils.c.

297 {
298 #ifdef HAVE__BUILTIN_POPCOUNT
299  return __builtin_popcount(word);
300 #else /* !HAVE__BUILTIN_POPCOUNT */
301  int result = 0;
302 
303  while (word != 0)
304  {
305  result += pg_number_of_ones[word & 255];
306  word >>= 8;
307  }
308 
309  return result;
310 #endif /* HAVE__BUILTIN_POPCOUNT */
311 }
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87

References pg_number_of_ones, and word().

Referenced by pg_popcount32(), and pg_popcount_slow().

◆ pg_popcount64()

int pg_popcount64 ( uint64  word)

Definition at line 403 of file pg_bitutils.c.

404 {
405  return pg_popcount64_slow(word);
406 }
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:318

References pg_popcount64_slow(), and word().

Referenced by visibilitymap_count().

◆ pg_popcount64_slow()

static int pg_popcount64_slow ( uint64  word)
inlinestatic

Definition at line 318 of file pg_bitutils.c.

319 {
320 #ifdef HAVE__BUILTIN_POPCOUNT
321 #if defined(HAVE_LONG_INT_64)
322  return __builtin_popcountl(word);
323 #elif defined(HAVE_LONG_LONG_INT_64)
324  return __builtin_popcountll(word);
325 #else
326 #error must have a working 64-bit integer datatype
327 #endif
328 #else /* !HAVE__BUILTIN_POPCOUNT */
329  int result = 0;
330 
331  while (word != 0)
332  {
333  result += pg_number_of_ones[word & 255];
334  word >>= 8;
335  }
336 
337  return result;
338 #endif /* HAVE__BUILTIN_POPCOUNT */
339 }

References pg_number_of_ones, and word().

Referenced by pg_popcount64(), and pg_popcount_slow().

◆ pg_popcount_slow()

static uint64 pg_popcount_slow ( const char *  buf,
int  bytes 
)
static

Definition at line 346 of file pg_bitutils.c.

347 {
348  uint64 popcnt = 0;
349 
350 #if SIZEOF_VOID_P >= 8
351  /* Process in 64-bit chunks if the buffer is aligned. */
352  if (buf == (const char *) TYPEALIGN(8, buf))
353  {
354  const uint64 *words = (const uint64 *) buf;
355 
356  while (bytes >= 8)
357  {
358  popcnt += pg_popcount64_slow(*words++);
359  bytes -= 8;
360  }
361 
362  buf = (const char *) words;
363  }
364 #else
365  /* Process in 32-bit chunks if the buffer is aligned. */
366  if (buf == (const char *) TYPEALIGN(4, buf))
367  {
368  const uint32 *words = (const uint32 *) buf;
369 
370  while (bytes >= 4)
371  {
372  popcnt += pg_popcount32_slow(*words++);
373  bytes -= 4;
374  }
375 
376  buf = (const char *) words;
377  }
378 #endif
379 
380  /* Process any remaining bytes */
381  while (bytes--)
382  popcnt += pg_number_of_ones[(unsigned char) *buf++];
383 
384  return popcnt;
385 }
unsigned int uint32
Definition: c.h:493
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:791

References buf, pg_number_of_ones, pg_popcount32_slow(), pg_popcount64_slow(), and TYPEALIGN.

Referenced by pg_popcount().

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_popcount32_slow(), pg_popcount64_slow(), and pg_popcount_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().