PostgreSQL Source Code  git master
pg_bitutils.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * pg_bitutils.h
4  * Miscellaneous functions for bit-wise operations.
5  *
6  *
7  * Copyright (c) 2019, PostgreSQL Global Development Group
8  *
9  * src/include/port/pg_bitutils.h
10  *
11  *-------------------------------------------------------------------------
12  */
13 #ifndef PG_BITUTILS_H
14 #define PG_BITUTILS_H
15 
16 extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
17 extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
18 extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
19 
20 /*
21  * pg_leftmost_one_pos32
22  * Returns the position of the most significant set bit in "word",
23  * measured from the least significant bit. word must not be 0.
24  */
25 static inline int
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 }
43 
44 /*
45  * pg_leftmost_one_pos64
46  * As above, but for a 64-bit word.
47  */
48 static inline int
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 }
72 
73 /*
74  * pg_rightmost_one_pos32
75  * Returns the position of the least significant set bit in "word",
76  * measured from the least significant bit. word must not be 0.
77  */
78 static inline int
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 }
99 
100 /*
101  * pg_rightmost_one_pos64
102  * As above, but for a 64-bit word.
103  */
104 static inline int
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 }
131 
132 /* Count the number of one-bits in a uint32 or uint64 */
133 extern int (*pg_popcount32) (uint32 word);
134 extern int (*pg_popcount64) (uint64 word);
135 
136 /* Count the number of one-bits in a byte array */
137 extern uint64 pg_popcount(const char *buf, int bytes);
138 
139 #endif /* PG_BITUTILS_H */
def bytes(source, encoding='ascii', errors='strict')
unsigned char uint8
Definition: c.h:356
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:26
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:49
#define PGDLLIMPORT
Definition: c.h:1243
uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.c:282
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
static char * buf
Definition: pg_test_fsync.c:68
int(* pg_popcount64)(uint64 word)
Definition: pg_bitutils.c:133
unsigned int uint32
Definition: c.h:358
int(* pg_popcount32)(uint32 word)
Definition: pg_bitutils.c:132
static int pg_rightmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:105
#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_number_of_ones[256]
Definition: pg_bitutils.c:87
PGDLLIMPORT const uint8 pg_rightmost_one_pos[256]
Definition: pg_bitutils.c:62
static int pg_rightmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:79