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-2020, 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 #ifndef FRONTEND
17 extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
18 extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
19 extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
20 #else
21 extern const uint8 pg_leftmost_one_pos[256];
22 extern const uint8 pg_rightmost_one_pos[256];
23 extern const uint8 pg_number_of_ones[256];
24 #endif
25 
26 /*
27  * pg_leftmost_one_pos32
28  * Returns the position of the most significant set bit in "word",
29  * measured from the least significant bit. word must not be 0.
30  */
31 static inline int
33 {
34 #ifdef HAVE__BUILTIN_CLZ
35  Assert(word != 0);
36 
37  return 31 - __builtin_clz(word);
38 #else
39  int shift = 32 - 8;
40 
41  Assert(word != 0);
42 
43  while ((word >> shift) == 0)
44  shift -= 8;
45 
46  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
47 #endif /* HAVE__BUILTIN_CLZ */
48 }
49 
50 /*
51  * pg_leftmost_one_pos64
52  * As above, but for a 64-bit word.
53  */
54 static inline int
56 {
57 #ifdef HAVE__BUILTIN_CLZ
58  Assert(word != 0);
59 
60 #if defined(HAVE_LONG_INT_64)
61  return 63 - __builtin_clzl(word);
62 #elif defined(HAVE_LONG_LONG_INT_64)
63  return 63 - __builtin_clzll(word);
64 #else
65 #error must have a working 64-bit integer datatype
66 #endif
67 #else /* !HAVE__BUILTIN_CLZ */
68  int shift = 64 - 8;
69 
70  Assert(word != 0);
71 
72  while ((word >> shift) == 0)
73  shift -= 8;
74 
75  return shift + pg_leftmost_one_pos[(word >> shift) & 255];
76 #endif /* HAVE__BUILTIN_CLZ */
77 }
78 
79 /*
80  * pg_rightmost_one_pos32
81  * Returns the position of the least significant set bit in "word",
82  * measured from the least significant bit. word must not be 0.
83  */
84 static inline int
86 {
87 #ifdef HAVE__BUILTIN_CTZ
88  Assert(word != 0);
89 
90  return __builtin_ctz(word);
91 #else
92  int result = 0;
93 
94  Assert(word != 0);
95 
96  while ((word & 255) == 0)
97  {
98  word >>= 8;
99  result += 8;
100  }
101  result += pg_rightmost_one_pos[word & 255];
102  return result;
103 #endif /* HAVE__BUILTIN_CTZ */
104 }
105 
106 /*
107  * pg_rightmost_one_pos64
108  * As above, but for a 64-bit word.
109  */
110 static inline int
112 {
113 #ifdef HAVE__BUILTIN_CTZ
114  Assert(word != 0);
115 
116 #if defined(HAVE_LONG_INT_64)
117  return __builtin_ctzl(word);
118 #elif defined(HAVE_LONG_LONG_INT_64)
119  return __builtin_ctzll(word);
120 #else
121 #error must have a working 64-bit integer datatype
122 #endif
123 #else /* !HAVE__BUILTIN_CTZ */
124  int result = 0;
125 
126  Assert(word != 0);
127 
128  while ((word & 255) == 0)
129  {
130  word >>= 8;
131  result += 8;
132  }
133  result += pg_rightmost_one_pos[word & 255];
134  return result;
135 #endif /* HAVE__BUILTIN_CTZ */
136 }
137 
138 /*
139  * pg_nextpower2_32
140  * Returns the next highest power of 2 of 'num', or 'num', if it's
141  * already a power of 2.
142  *
143  * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.
144  */
145 static inline uint32
147 {
148  Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
149 
150  /*
151  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
152  * will turn on all previous bits resulting in no common bits being set
153  * between num and num-1.
154  */
155  if ((num & (num - 1)) == 0)
156  return num; /* already power 2 */
157 
158  return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
159 }
160 
161 /*
162  * pg_nextpower2_64
163  * Returns the next highest power of 2 of 'num', or 'num', if it's
164  * already a power of 2.
165  *
166  * 'num' mustn't be 0 or be above PG_UINT64_MAX / 2 + 1.
167  */
168 static inline uint64
169 pg_nextpower2_64(uint64 num)
170 {
171  Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
172 
173  /*
174  * A power 2 number has only 1 bit set. Subtracting 1 from such a number
175  * will turn on all previous bits resulting in no common bits being set
176  * between num and num-1.
177  */
178  if ((num & (num - 1)) == 0)
179  return num; /* already power 2 */
180 
181  return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
182 }
183 
184 /*
185  * pg_ceil_log2_32
186  * Returns equivalent of ceil(log2(num))
187  */
188 static inline uint32
190 {
191  if (num < 2)
192  return 0;
193  else
194  return pg_leftmost_one_pos32(num - 1) + 1;
195 }
196 
197 /*
198  * pg_ceil_log2_64
199  * Returns equivalent of ceil(log2(num))
200  */
201 static inline uint64
202 pg_ceil_log2_64(uint64 num)
203 {
204  if (num < 2)
205  return 0;
206  else
207  return pg_leftmost_one_pos64(num - 1) + 1;
208 }
209 
210 /* Count the number of one-bits in a uint32 or uint64 */
211 extern int (*pg_popcount32) (uint32 word);
212 extern int (*pg_popcount64) (uint64 word);
213 
214 /* Count the number of one-bits in a byte array */
215 extern uint64 pg_popcount(const char *buf, int bytes);
216 
217 /*
218  * Rotate the bits of "word" to the right by n bits.
219  */
220 static inline uint32
222 {
223  return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
224 }
225 
226 #endif /* PG_BITUTILS_H */
#define PG_UINT64_MAX
Definition: c.h:454
#define BITS_PER_BYTE
def bytes(source, encoding='ascii', errors='strict')
unsigned char uint8
Definition: c.h:365
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:32
static uint32 pg_rotate_right32(uint32 word, int n)
Definition: pg_bitutils.h:221
#define PG_UINT32_MAX
Definition: c.h:451
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:55
#define PGDLLIMPORT
Definition: c.h:1280
uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.c:282
static uint64 pg_ceil_log2_64(uint64 num)
Definition: pg_bitutils.h:202
PGDLLIMPORT const uint8 pg_leftmost_one_pos[256]
Definition: pg_bitutils.c:34
static uint32 pg_ceil_log2_32(uint32 num)
Definition: pg_bitutils.h:189
static char * buf
Definition: pg_test_fsync.c:67
int(* pg_popcount64)(uint64 word)
Definition: pg_bitutils.c:133
static uint32 pg_nextpower2_32(uint32 num)
Definition: pg_bitutils.h:146
unsigned int uint32
Definition: c.h:367
int(* pg_popcount32)(uint32 word)
Definition: pg_bitutils.c:132
static uint64 pg_nextpower2_64(uint64 num)
Definition: pg_bitutils.h:169
static int pg_rightmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:111
#define Assert(condition)
Definition: c.h:738
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:85