diff options
Diffstat (limited to 'src/port/pg_bitutils.c')
| -rw-r--r-- | src/port/pg_bitutils.c | 321 |
1 files changed, 321 insertions, 0 deletions
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c new file mode 100644 index 0000000..2252021 --- /dev/null +++ b/src/port/pg_bitutils.c @@ -0,0 +1,321 @@ +/*------------------------------------------------------------------------- + * + * pg_bitutils.c + * Miscellaneous functions for bit-wise operations. + * + * Copyright (c) 2019-2021, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/port/pg_bitutils.c + * + *------------------------------------------------------------------------- + */ +#include "c.h" + +#ifdef HAVE__GET_CPUID +#include <cpuid.h> +#endif +#ifdef HAVE__CPUID +#include <intrin.h> +#endif + +#include "port/pg_bitutils.h" + + +/* + * Array giving the position of the left-most set bit for each possible + * byte value. We count the right-most position as the 0th bit, and the + * left-most the 7th bit. The 0th entry of the array should not be used. + * + * Note: this is not used by the functions in pg_bitutils.h when + * HAVE__BUILTIN_CLZ is defined, but we provide it anyway, so that + * extensions possibly compiled with a different compiler can use it. + */ +const uint8 pg_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 +}; + +/* + * Array giving the position of the right-most set bit for each possible + * byte value. We count the right-most position as the 0th bit, and the + * left-most the 7th bit. The 0th entry of the array should not be used. + * + * Note: this is not used by the functions in pg_bitutils.h when + * HAVE__BUILTIN_CTZ is defined, but we provide it anyway, so that + * extensions possibly compiled with a different compiler can use it. + */ +const uint8 pg_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 giving the number of 1-bits in each possible byte value. + * + * Note: we export this for use by functions in which explicit use + * of the popcount functions seems unlikely to be a win. + */ +const uint8 pg_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 +}; + +/* + * On x86_64, we can use the hardware popcount instruction, but only if + * we can verify that the CPU supports it via the cpuid instruction. + * + * Otherwise, we fall back to __builtin_popcount if the compiler has that, + * or a hand-rolled implementation if not. + */ +#ifdef HAVE_X86_64_POPCNTQ +#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID) +#define USE_POPCNT_ASM 1 +#endif +#endif + +static int pg_popcount32_slow(uint32 word); +static int pg_popcount64_slow(uint64 word); + +#ifdef USE_POPCNT_ASM +static bool pg_popcount_available(void); +static int pg_popcount32_choose(uint32 word); +static int pg_popcount64_choose(uint64 word); +static int pg_popcount32_asm(uint32 word); +static int pg_popcount64_asm(uint64 word); + +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 /* USE_POPCNT_ASM */ + +#ifdef USE_POPCNT_ASM + +/* + * Return true if CPUID indicates that the POPCNT instruction is available. + */ +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 */ +} + +/* + * These functions get called on the first call to pg_popcount32 etc. + * They detect whether we can use the asm implementations, and replace + * the function pointers 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_asm; + pg_popcount64 = pg_popcount64_asm; + } + else + { + pg_popcount32 = pg_popcount32_slow; + pg_popcount64 = pg_popcount64_slow; + } + + return pg_popcount32(word); +} + +static int +pg_popcount64_choose(uint64 word) +{ + if (pg_popcount_available()) + { + pg_popcount32 = pg_popcount32_asm; + pg_popcount64 = pg_popcount64_asm; + } + else + { + pg_popcount32 = pg_popcount32_slow; + pg_popcount64 = pg_popcount64_slow; + } + + return pg_popcount64(word); +} + +/* + * pg_popcount32_asm + * Return the number of 1 bits set in word + */ +static int +pg_popcount32_asm(uint32 word) +{ + uint32 res; + +__asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc"); + return (int) res; +} + +/* + * pg_popcount64_asm + * Return the number of 1 bits set in word + */ +static int +pg_popcount64_asm(uint64 word) +{ + uint64 res; + +__asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc"); + return (int) res; +} + +#endif /* USE_POPCNT_ASM */ + + +/* + * pg_popcount32_slow + * Return the number of 1 bits set in word + */ +static int +pg_popcount32_slow(uint32 word) +{ +#ifdef HAVE__BUILTIN_POPCOUNT + return __builtin_popcount(word); +#else /* !HAVE__BUILTIN_POPCOUNT */ + int result = 0; + + while (word != 0) + { + result += pg_number_of_ones[word & 255]; + word >>= 8; + } + + return result; +#endif /* HAVE__BUILTIN_POPCOUNT */ +} + +/* + * pg_popcount64_slow + * Return the number of 1 bits set in word + */ +static int +pg_popcount64_slow(uint64 word) +{ +#ifdef HAVE__BUILTIN_POPCOUNT +#if defined(HAVE_LONG_INT_64) + return __builtin_popcountl(word); +#elif defined(HAVE_LONG_LONG_INT_64) + return __builtin_popcountll(word); +#else +#error must have a working 64-bit integer datatype +#endif +#else /* !HAVE__BUILTIN_POPCOUNT */ + int result = 0; + + while (word != 0) + { + result += pg_number_of_ones[word & 255]; + word >>= 8; + } + + return result; +#endif /* HAVE__BUILTIN_POPCOUNT */ +} + + +/* + * 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 == (const char *) TYPEALIGN(8, buf)) + { + const uint64 *words = (const uint64 *) buf; + + while (bytes >= 8) + { + popcnt += pg_popcount64(*words++); + bytes -= 8; + } + + buf = (const char *) words; + } +#else + /* Process in 32-bit chunks if the buffer is aligned. */ + if (buf == (const char *) TYPEALIGN(4, buf)) + { + const uint32 *words = (const uint32 *) buf; + + while (bytes >= 4) + { + popcnt += pg_popcount32(*words++); + bytes -= 4; + } + + buf = (const char *) words; + } +#endif + + /* Process any remaining bytes */ + while (bytes--) + popcnt += pg_number_of_ones[(unsigned char) *buf++]; + + return popcnt; +} |