codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * pg_bitutils.h4 *	  Miscellaneous functions for bit-wise operations.5 *6 *7 * Copyright (c) 2019-2023, PostgreSQL Global Development Group8 *9 * src/include/port/pg_bitutils.h10 *11 *-------------------------------------------------------------------------12 */13#ifndef PG_BITUTILS_H14#define PG_BITUTILS_H15 16#ifdef _MSC_VER17#include <intrin.h>18#define HAVE_BITSCAN_FORWARD19#define HAVE_BITSCAN_REVERSE20 21#else22#if defined(HAVE__BUILTIN_CTZ)23#define HAVE_BITSCAN_FORWARD24#endif25 26#if defined(HAVE__BUILTIN_CLZ)27#define HAVE_BITSCAN_REVERSE28#endif29#endif							/* _MSC_VER */30 31extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];32extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];33extern PGDLLIMPORT const uint8 pg_number_of_ones[256];34 35/*36 * pg_leftmost_one_pos3237 *		Returns the position of the most significant set bit in "word",38 *		measured from the least significant bit.  word must not be 0.39 */40static inline int41pg_leftmost_one_pos32(uint32 word)42{43#ifdef HAVE__BUILTIN_CLZ44	Assert(word != 0);45 46	return 31 - __builtin_clz(word);47#elif defined(_MSC_VER)48	unsigned long result;49	bool		non_zero;50 51	non_zero = _BitScanReverse(&result, word);52	Assert(non_zero);53	return (int) result;54#else55	int			shift = 32 - 8;56 57	Assert(word != 0);58 59	while ((word >> shift) == 0)60		shift -= 8;61 62	return shift + pg_leftmost_one_pos[(word >> shift) & 255];63#endif							/* HAVE__BUILTIN_CLZ */64}65 66/*67 * pg_leftmost_one_pos6468 *		As above, but for a 64-bit word.69 */70static inline int71pg_leftmost_one_pos64(uint64 word)72{73#ifdef HAVE__BUILTIN_CLZ74	Assert(word != 0);75 76#if defined(HAVE_LONG_INT_64)77	return 63 - __builtin_clzl(word);78#elif defined(HAVE_LONG_LONG_INT_64)79	return 63 - __builtin_clzll(word);80#else81#error must have a working 64-bit integer datatype82#endif							/* HAVE_LONG_INT_64 */83 84#elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))85	unsigned long result;86	bool		non_zero;87 88	non_zero = _BitScanReverse64(&result, word);89	Assert(non_zero);90	return (int) result;91#else92	int			shift = 64 - 8;93 94	Assert(word != 0);95 96	while ((word >> shift) == 0)97		shift -= 8;98 99	return shift + pg_leftmost_one_pos[(word >> shift) & 255];100#endif							/* HAVE__BUILTIN_CLZ */101}102 103/*104 * pg_rightmost_one_pos32105 *		Returns the position of the least significant set bit in "word",106 *		measured from the least significant bit.  word must not be 0.107 */108static inline int109pg_rightmost_one_pos32(uint32 word)110{111#ifdef HAVE__BUILTIN_CTZ112	Assert(word != 0);113 114	return __builtin_ctz(word);115#elif defined(_MSC_VER)116	unsigned long result;117	bool		non_zero;118 119	non_zero = _BitScanForward(&result, word);120	Assert(non_zero);121	return (int) result;122#else123	int			result = 0;124 125	Assert(word != 0);126 127	while ((word & 255) == 0)128	{129		word >>= 8;130		result += 8;131	}132	result += pg_rightmost_one_pos[word & 255];133	return result;134#endif							/* HAVE__BUILTIN_CTZ */135}136 137/*138 * pg_rightmost_one_pos64139 *		As above, but for a 64-bit word.140 */141static inline int142pg_rightmost_one_pos64(uint64 word)143{144#ifdef HAVE__BUILTIN_CTZ145	Assert(word != 0);146 147#if defined(HAVE_LONG_INT_64)148	return __builtin_ctzl(word);149#elif defined(HAVE_LONG_LONG_INT_64)150	return __builtin_ctzll(word);151#else152#error must have a working 64-bit integer datatype153#endif							/* HAVE_LONG_INT_64 */154 155#elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))156	unsigned long result;157	bool		non_zero;158 159	non_zero = _BitScanForward64(&result, word);160	Assert(non_zero);161	return (int) result;162#else163	int			result = 0;164 165	Assert(word != 0);166 167	while ((word & 255) == 0)168	{169		word >>= 8;170		result += 8;171	}172	result += pg_rightmost_one_pos[word & 255];173	return result;174#endif							/* HAVE__BUILTIN_CTZ */175}176 177/*178 * pg_nextpower2_32179 *		Returns the next higher power of 2 above 'num', or 'num' if it's180 *		already a power of 2.181 *182 * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.183 */184static inline uint32185pg_nextpower2_32(uint32 num)186{187	Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);188 189	/*190	 * A power 2 number has only 1 bit set.  Subtracting 1 from such a number191	 * will turn on all previous bits resulting in no common bits being set192	 * between num and num-1.193	 */194	if ((num & (num - 1)) == 0)195		return num;				/* already power 2 */196 197	return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);198}199 200/*201 * pg_nextpower2_64202 *		Returns the next higher power of 2 above 'num', or 'num' if it's203 *		already a power of 2.204 *205 * 'num' mustn't be 0 or be above PG_UINT64_MAX / 2  + 1.206 */207static inline uint64208pg_nextpower2_64(uint64 num)209{210	Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);211 212	/*213	 * A power 2 number has only 1 bit set.  Subtracting 1 from such a number214	 * will turn on all previous bits resulting in no common bits being set215	 * between num and num-1.216	 */217	if ((num & (num - 1)) == 0)218		return num;				/* already power 2 */219 220	return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);221}222 223/*224 * pg_prevpower2_32225 *		Returns the next lower power of 2 below 'num', or 'num' if it's226 *		already a power of 2.227 *228 * 'num' mustn't be 0.229 */230static inline uint32231pg_prevpower2_32(uint32 num)232{233	return ((uint32) 1) << pg_leftmost_one_pos32(num);234}235 236/*237 * pg_prevpower2_64238 *		Returns the next lower power of 2 below 'num', or 'num' if it's239 *		already a power of 2.240 *241 * 'num' mustn't be 0.242 */243static inline uint64244pg_prevpower2_64(uint64 num)245{246	return ((uint64) 1) << pg_leftmost_one_pos64(num);247}248 249/*250 * pg_ceil_log2_32251 *		Returns equivalent of ceil(log2(num))252 */253static inline uint32254pg_ceil_log2_32(uint32 num)255{256	if (num < 2)257		return 0;258	else259		return pg_leftmost_one_pos32(num - 1) + 1;260}261 262/*263 * pg_ceil_log2_64264 *		Returns equivalent of ceil(log2(num))265 */266static inline uint64267pg_ceil_log2_64(uint64 num)268{269	if (num < 2)270		return 0;271	else272		return pg_leftmost_one_pos64(num - 1) + 1;273}274 275/*276 * With MSVC on x86_64 builds, try using native popcnt instructions via the277 * __popcnt and __popcnt64 intrinsics.  These don't work the same as GCC's278 * __builtin_popcount* intrinsic functions as they always emit popcnt279 * instructions.280 */281#if defined(_MSC_VER) && defined(_M_AMD64)282#define HAVE_X86_64_POPCNTQ283#endif284 285/*286 * On x86_64, we can use the hardware popcount instruction, but only if287 * we can verify that the CPU supports it via the cpuid instruction.288 *289 * Otherwise, we fall back to a hand-rolled implementation.290 */291#ifdef HAVE_X86_64_POPCNTQ292#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)293#define TRY_POPCNT_FAST 1294#endif295#endif296 297#ifdef TRY_POPCNT_FAST298/* Attempt to use the POPCNT instruction, but perform a runtime check first */299extern int	(*pg_popcount32) (uint32 word);300extern int	(*pg_popcount64) (uint64 word);301 302#else303/* Use a portable implementation -- no need for a function pointer. */304extern int	pg_popcount32(uint32 word);305extern int	pg_popcount64(uint64 word);306 307#endif							/* TRY_POPCNT_FAST */308 309/* Count the number of one-bits in a byte array */310extern uint64 pg_popcount(const char *buf, int bytes);311 312/*313 * Rotate the bits of "word" to the right/left by n bits.314 */315static inline uint32316pg_rotate_right32(uint32 word, int n)317{318	return (word >> n) | (word << (32 - n));319}320 321static inline uint32322pg_rotate_left32(uint32 word, int n)323{324	return (word << n) | (word >> (32 - n));325}326 327/* size_t variants of the above, as required */328 329#if SIZEOF_SIZE_T == 4330#define pg_leftmost_one_pos_size_t pg_leftmost_one_pos32331#define pg_nextpower2_size_t pg_nextpower2_32332#define pg_prevpower2_size_t pg_prevpower2_32333#else334#define pg_leftmost_one_pos_size_t pg_leftmost_one_pos64335#define pg_nextpower2_size_t pg_nextpower2_64336#define pg_prevpower2_size_t pg_prevpower2_64337#endif338 339#endif							/* PG_BITUTILS_H */340