/*------------------------------------------------------------------------- * * pg_bitutils.c * miscellaneous functions for bit-wise operations. * * Portions Copyright (c) 2019, PostgreSQL Global Development Group * * IDENTIFICATION * src/port/pg_bitutils.c * *------------------------------------------------------------------------- */ #include "postgres.h" #ifdef HAVE__GET_CPUID #include #endif #ifdef HAVE__CPUID #include #endif #include "port/pg_bitutils.h" #if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID) static bool pg_popcount_available(void); static int pg_popcount32_choose(uint32 word); static int pg_popcount32_sse42(uint32 word); static int pg_popcount64_choose(uint64 word); static int pg_popcount64_sse42(uint64 word); #endif static int pg_popcount32_slow(uint32 word); static int pg_popcount64_slow(uint64 word); #if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ)) static bool pg_lzcnt_available(void); #endif #if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID) static int pg_rightmost_one32_choose(uint32 word); static int pg_rightmost_one32_abm(uint32 word); static int pg_rightmost_one64_choose(uint64 word); static int pg_rightmost_one64_abm(uint64 word); #endif static int pg_rightmost_one32_slow(uint32 word); static int pg_rightmost_one64_slow(uint64 word); #if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID) static int pg_leftmost_one32_choose(uint32 word); static int pg_leftmost_one32_abm(uint32 word); static int pg_leftmost_one64_choose(uint64 word); static int pg_leftmost_one64_abm(uint64 word); #endif static int pg_leftmost_one32_slow(uint32 word); static int pg_leftmost_one64_slow(uint64 word); #if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID) int (*pg_popcount32) (uint32 word) = pg_popcount32_choose; int (*pg_popcount64) (uint64 word) = pg_popcount64_choose; #else int (*pg_popcount32) (uint32 word) = pg_popcount32_slow; int (*pg_popcount64) (uint64 word) = pg_popcount64_slow; #endif #if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID) int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose; int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose; #else int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow; int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow; #endif #if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID) int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose; int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose; #else int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow; int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow; #endif /* Array marking the number of 1-bits for each value of 0-255. */ static const uint8 number_of_ones[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; /* * Array marking the position of the right-most set bit for each value of * 1-255. We count the right-most position as the 0th bit, and the * left-most the 7th bit. The 0th index of the array must not be used. */ static const uint8 rightmost_one_pos[256] = { 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 }; /* * Array marking the position of the left-most set bit for each value of * 1-255. We count the right-most position as the 0th bit, and the * left-most the 7th bit. The 0th index of the array must not be used. */ static const uint8 leftmost_one_pos[256] = { 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 }; #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT) static bool pg_popcount_available(void) { unsigned int exx[4] = { 0, 0, 0, 0 }; #if defined(HAVE__GET_CPUID) __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]); #elif defined(HAVE__CPUID) __cpuid(exx, 1); #else #error cpuid instruction not available #endif return (exx[2] & (1 << 23)) != 0; /* POPCNT */ } #endif #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT) /* * This gets called on the first call. It replaces the function pointer * so that subsequent calls are routed directly to the chosen implementation. */ static int pg_popcount32_choose(uint32 word) { if (pg_popcount_available()) pg_popcount32 = pg_popcount32_sse42; else pg_popcount32 = pg_popcount32_slow; return pg_popcount32(word); } static int pg_popcount32_sse42(uint32 word) { return __builtin_popcount(word); } #endif /* * pg_popcount32_slow * Return the number of 1 bits set in word */ static int pg_popcount32_slow(uint32 word) { int result = 0; while (word != 0) { result += number_of_ones[word & 255]; word >>= 8; } return result; } /* * pg_popcount * Returns the number of 1-bits in buf */ uint64 pg_popcount(const char *buf, int bytes) { uint64 popcnt = 0; #if SIZEOF_VOID_P >= 8 /* Process in 64-bit chunks if the buffer is aligned. */ if (buf == (char *) TYPEALIGN(8, buf)) { uint64 *words = (uint64 *) buf; while (bytes >= 8) { popcnt += pg_popcount64(*words++); bytes -= 8; } buf = (char *) words; } #else /* Process in 32-bit chunks if the buffer is aligned. */ if (buf == (char *) TYPEALIGN(4, buf)) { uint32 *words = (uint32 *) buf; while (bytes >= 4) { popcnt += pg_popcount32(*words++); bytes -= 4; } buf = (char *) words; } #endif /* Process any remaining bytes */ while (bytes--) popcnt += number_of_ones[(unsigned char) *buf++]; return popcnt; } #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT) /* * This gets called on the first call. It replaces the function pointer * so that subsequent calls are routed directly to the chosen implementation. */ static int pg_popcount64_choose(uint64 word) { if (pg_popcount_available()) pg_popcount64 = pg_popcount64_sse42; else pg_popcount64 = pg_popcount64_slow; return pg_popcount64(word); } static int pg_popcount64_sse42(uint64 word) { #if defined(HAVE_LONG_INT_64) return __builtin_popcountl(word); #elif defined(HAVE_LONG_LONG_INT_64) return __builtin_popcountll(word); #else /* shouldn't happen */ #error must have a working 64-bit integer datatype #endif } #endif /* * pg_popcount64_slow * Return the number of 1 bits set in word */ static int pg_popcount64_slow(uint64 word) { int result = 0; while (word != 0) { result += number_of_ones[word & 255]; word >>= 8; } return result; } #if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ)) static bool pg_lzcnt_available(void) { unsigned int exx[4] = { 0, 0, 0, 0 }; #if defined(HAVE__GET_CPUID) __get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]); #elif defined(HAVE__CPUID) __cpuid(exx, 0x80000001); #else #error cpuid instruction not available #endif return (exx[2] & (1 << 5)) != 0; /* LZCNT */ } #endif #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ) /* * This gets called on the first call. It replaces the function pointer * so that subsequent calls are routed directly to the chosen implementation. */ static int pg_rightmost_one32_choose(uint32 word) { if (pg_lzcnt_available()) pg_rightmost_one32 = pg_rightmost_one32_abm; else pg_rightmost_one32 = pg_rightmost_one32_slow; return pg_rightmost_one32(word); } static int pg_rightmost_one32_abm(uint32 word) { return __builtin_ctz(word); } #endif /* * pg_rightmost_one32_slow * Returns the number of trailing 0-bits in word, starting at the least * significant bit position. word must not be 0. */ static int pg_rightmost_one32_slow(uint32 word) { int result = 0; Assert(word != 0); while ((word & 255) == 0) { word >>= 8; result += 8; } result += rightmost_one_pos[word & 255]; return result; } #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ) /* * This gets called on the first call. It replaces the function pointer * so that subsequent calls are routed directly to the chosen implementation. */ static int pg_rightmost_one64_choose(uint64 word) { if (pg_lzcnt_available()) pg_rightmost_one64 = pg_rightmost_one64_abm; else pg_rightmost_one64 = pg_rightmost_one64_slow; return pg_rightmost_one64(word); } static int pg_rightmost_one64_abm(uint64 word) { #if defined(HAVE_LONG_INT_64) return __builtin_ctzl(word); #elif defined(HAVE_LONG_LONG_INT_64) return __builtin_ctzll(word); #else /* shouldn't happen */ #error must have a working 64-bit integer datatype #endif } #endif /* * pg_rightmost_one64_slow * Returns the number of trailing 0-bits in word, starting at the least * significant bit position. word must not be 0. */ static int pg_rightmost_one64_slow(uint64 word) { int result = 0; Assert(word != 0); while ((word & 255) == 0) { word >>= 8; result += 8; } result += rightmost_one_pos[word & 255]; return result; } #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ) /* * This gets called on the first call. It replaces the function pointer * so that subsequent calls are routed directly to the chosen implementation. */ static int pg_leftmost_one32_choose(uint32 word) { if (pg_lzcnt_available()) pg_leftmost_one32 = pg_leftmost_one32_abm; else pg_leftmost_one32 = pg_leftmost_one32_slow; return pg_leftmost_one32(word); } static int pg_leftmost_one32_abm(uint32 word) { return 31 - __builtin_clz(word); } #endif /* * pg_leftmost_one32_slow * Returns the 0-based position of the most significant set bit in word * measured from the least significant bit. word must not be 0. */ static int pg_leftmost_one32_slow(uint32 word) { int shift = 32 - 8; Assert(word != 0); while ((word >> shift) == 0) shift -= 8; return shift + leftmost_one_pos[(word >> shift) & 255]; } #if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ) /* * This gets called on the first call. It replaces the function pointer * so that subsequent calls are routed directly to the chosen implementation. */ static int pg_leftmost_one64_choose(uint64 word) { if (pg_lzcnt_available()) pg_leftmost_one64 = pg_leftmost_one64_abm; else pg_leftmost_one64 = pg_leftmost_one64_slow; return pg_leftmost_one64(word); } static int pg_leftmost_one64_abm(uint64 word) { #if defined(HAVE_LONG_INT_64) return 63 - __builtin_clzl(word); #elif defined(HAVE_LONG_LONG_INT_64) return 63 - __builtin_clzll(word); #else /* shouldn't happen */ #error must have a working 64-bit integer datatype #endif } #endif /* * pg_leftmost_one64_slow * Returns the 0-based position of the most significant set bit in word * measured from the least significant bit. word must not be 0. */ static int pg_leftmost_one64_slow(uint64 word) { int shift = 64 - 8; Assert(word != 0); while ((word >> shift) == 0) shift -= 8; return shift + leftmost_one_pos[(word >> shift) & 255]; }