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 32 pg_leftmost_one_pos32(uint32 word) 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 55 pg_leftmost_one_pos64(uint64 word) 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 85 pg_rightmost_one_pos32(uint32 word) 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 111 pg_rightmost_one_pos64(uint64 word) 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 higher power of 2 above '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 146 pg_nextpower2_32(uint32 num) 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 higher power of 2 above '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_nextpower2_size_t 186 * Returns the next higher power of 2 above 'num', for a size_t input. 187 */ 188 #if SIZEOF_SIZE_T == 4 189 #define pg_nextpower2_size_t(num) pg_nextpower2_32(num) 190 #else 191 #define pg_nextpower2_size_t(num) pg_nextpower2_64(num) 192 #endif 193 194 /* 195 * pg_prevpower2_32 196 * Returns the next lower power of 2 below 'num', or 'num' if it's 197 * already a power of 2. 198 * 199 * 'num' mustn't be 0. 200 */ 201 static inline uint32 202 pg_prevpower2_32(uint32 num) 203 { 204 return ((uint32) 1) << pg_leftmost_one_pos32(num); 205 } 206 207 /* 208 * pg_prevpower2_64 209 * Returns the next lower power of 2 below 'num', or 'num' if it's 210 * already a power of 2. 211 * 212 * 'num' mustn't be 0. 213 */ 214 static inline uint64 215 pg_prevpower2_64(uint64 num) 216 { 217 return ((uint64) 1) << pg_leftmost_one_pos64(num); 218 } 219 220 /* 221 * pg_prevpower2_size_t 222 * Returns the next lower power of 2 below 'num', for a size_t input. 223 */ 224 #if SIZEOF_SIZE_T == 4 225 #define pg_prevpower2_size_t(num) pg_prevpower2_32(num) 226 #else 227 #define pg_prevpower2_size_t(num) pg_prevpower2_64(num) 228 #endif 229 230 /* 231 * pg_ceil_log2_32 232 * Returns equivalent of ceil(log2(num)) 233 */ 234 static inline uint32 235 pg_ceil_log2_32(uint32 num) 236 { 237 if (num < 2) 238 return 0; 239 else 240 return pg_leftmost_one_pos32(num - 1) + 1; 241 } 242 243 /* 244 * pg_ceil_log2_64 245 * Returns equivalent of ceil(log2(num)) 246 */ 247 static inline uint64 248 pg_ceil_log2_64(uint64 num) 249 { 250 if (num < 2) 251 return 0; 252 else 253 return pg_leftmost_one_pos64(num - 1) + 1; 254 } 255 256 /* Count the number of one-bits in a uint32 or uint64 */ 257 extern int (*pg_popcount32) (uint32 word); 258 extern int (*pg_popcount64) (uint64 word); 259 260 /* Count the number of one-bits in a byte array */ 261 extern uint64 pg_popcount(const char *buf, int bytes); 262 263 /* 264 * Rotate the bits of "word" to the right by n bits. 265 */ 266 static inline uint32 267 pg_rotate_right32(uint32 word, int n) 268 { 269 return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n)); 270 } 271 272 #endif /* PG_BITUTILS_H */ 273