PostgreSQL Source Code  git master
pg_bitutils.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

static int pg_leftmost_one_pos32 (uint32 word)
 
static int pg_leftmost_one_pos64 (uint64 word)
 
static int pg_rightmost_one_pos32 (uint32 word)
 
static int pg_rightmost_one_pos64 (uint64 word)
 
uint64 pg_popcount (const char *buf, int bytes)
 

Variables

PGDLLIMPORT const uint8 pg_leftmost_one_pos [256]
 
PGDLLIMPORT const uint8 pg_rightmost_one_pos [256]
 
PGDLLIMPORT const uint8 pg_number_of_ones [256]
 
int(* pg_popcount32 )(uint32 word)
 
int(* pg_popcount64 )(uint64 word)
 

Function Documentation

◆ pg_leftmost_one_pos32()

static int pg_leftmost_one_pos32 ( uint32  word)
inlinestatic

Definition at line 26 of file pg_bitutils.h.

References Assert, and pg_leftmost_one_pos.

27 {
28 #ifdef HAVE__BUILTIN_CLZ
29  Assert(word != 0);
30 
31  return 31 - __builtin_clz(word);
32 #else
33  int shift = 32 - 8;
34 
35  Assert(word != 0);
36 
37  while ((word >> shift) == 0)
38  shift -= 8;
39 
40  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
41 #endif /* HAVE__BUILTIN_CLZ */
42 }
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
#define Assert(condition)
Definition: c.h:732
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246

◆ pg_leftmost_one_pos64()

static int pg_leftmost_one_pos64 ( uint64  word)
inlinestatic

Definition at line 49 of file pg_bitutils.h.

References Assert, and pg_leftmost_one_pos.

50 {
51 #ifdef HAVE__BUILTIN_CLZ
52  Assert(word != 0);
53 
54 #if defined(HAVE_LONG_INT_64)
55  return 63 - __builtin_clzl(word);
56 #elif defined(HAVE_LONG_LONG_INT_64)
57  return 63 - __builtin_clzll(word);
58 #else
59 #error must have a working 64-bit integer datatype
60 #endif
61 #else /* !HAVE__BUILTIN_CLZ */
62  int shift = 64 - 8;
63 
64  Assert(word != 0);
65 
66  while ((word >> shift) == 0)
67  shift -= 8;
68 
69  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
70 #endif /* HAVE__BUILTIN_CLZ */
71 }
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
#define Assert(condition)
Definition: c.h:732
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246

◆ pg_popcount()

uint64 pg_popcount ( const char *  buf,
int  bytes 
)

Definition at line 282 of file pg_bitutils.c.

References pg_number_of_ones, pg_popcount32, pg_popcount64, and TYPEALIGN.

Referenced by bloom_prop_bits_set(), heap_tuple_infomask_flags(), pg_rightmost_one_pos64(), and sizebitvec().

283 {
284  uint64 popcnt = 0;
285 
286 #if SIZEOF_VOID_P >= 8
287  /* Process in 64-bit chunks if the buffer is aligned. */
288  if (buf == (const char *) TYPEALIGN(8, buf))
289  {
290  const uint64 *words = (const uint64 *) buf;
291 
292  while (bytes >= 8)
293  {
294  popcnt += pg_popcount64(*words++);
295  bytes -= 8;
296  }
297 
298  buf = (const char *) words;
299  }
300 #else
301  /* Process in 32-bit chunks if the buffer is aligned. */
302  if (buf == (const char *) TYPEALIGN(4, buf))
303  {
304  const uint32 *words = (const uint32 *) buf;
305 
306  while (bytes >= 4)
307  {
308  popcnt += pg_popcount32(*words++);
309  bytes -= 4;
310  }
311 
312  buf = (const char *) words;
313  }
314 #endif
315 
316  /* Process any remaining bytes */
317  while (bytes--)
318  popcnt += pg_number_of_ones[(unsigned char) *buf++];
319 
320  return popcnt;
321 }
int(* pg_popcount32)(uint32 word)
Definition: pg_bitutils.c:132
def bytes(source, encoding='ascii', errors='strict')
int(* pg_popcount64)(uint64 word)
Definition: pg_bitutils.c:133
static char * buf
Definition: pg_test_fsync.c:68
unsigned int uint32
Definition: c.h:358
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:678

◆ pg_rightmost_one_pos32()

static int pg_rightmost_one_pos32 ( uint32  word)
inlinestatic

Definition at line 79 of file pg_bitutils.h.

References Assert, and pg_rightmost_one_pos.

80 {
81 #ifdef HAVE__BUILTIN_CTZ
82  Assert(word != 0);
83 
84  return __builtin_ctz(word);
85 #else
86  int result = 0;
87 
88  Assert(word != 0);
89 
90  while ((word & 255) == 0)
91  {
92  word >>= 8;
93  result += 8;
94  }
95  result += pg_rightmost_one_pos[word & 255];
96  return result;
97 #endif /* HAVE__BUILTIN_CTZ */
98 }
#define Assert(condition)
Definition: c.h:732
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62

◆ pg_rightmost_one_pos64()

static int pg_rightmost_one_pos64 ( uint64  word)
inlinestatic

Definition at line 105 of file pg_bitutils.h.

References Assert, buf, generate_unaccent_rules::bytes(), pg_popcount(), pg_popcount32, pg_popcount64, pg_rightmost_one_pos, and word().

106 {
107 #ifdef HAVE__BUILTIN_CTZ
108  Assert(word != 0);
109 
110 #if defined(HAVE_LONG_INT_64)
111  return __builtin_ctzl(word);
112 #elif defined(HAVE_LONG_LONG_INT_64)
113  return __builtin_ctzll(word);
114 #else
115 #error must have a working 64-bit integer datatype
116 #endif
117 #else /* !HAVE__BUILTIN_CTZ */
118  int result = 0;
119 
120  Assert(word != 0);
121 
122  while ((word & 255) == 0)
123  {
124  word >>= 8;
125  result += 8;
126  }
127  result += pg_rightmost_one_pos[word & 255];
128  return result;
129 #endif /* HAVE__BUILTIN_CTZ */
130 }
#define Assert(condition)
Definition: c.h:732
static void word(struct vars *, int, struct state *, struct state *)
Definition: regcomp.c:1246
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62

Variable Documentation

◆ pg_leftmost_one_pos

PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]

Definition at line 34 of file pg_bitutils.c.

Referenced by pg_leftmost_one_pos32(), and pg_leftmost_one_pos64().

◆ pg_number_of_ones

PGDLLIMPORT const uint8 pg_number_of_ones[256]

Definition at line 87 of file pg_bitutils.c.

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

◆ pg_popcount32

int(* pg_popcount32) (uint32 word)

Definition at line 132 of file pg_bitutils.c.

Referenced by pg_popcount(), and pg_rightmost_one_pos64().

◆ pg_popcount64

int(* pg_popcount64) (uint64 word)

Definition at line 133 of file pg_bitutils.c.

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

◆ pg_rightmost_one_pos

PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]

Definition at line 62 of file pg_bitutils.c.

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().