*
* pg_bitutils.c
* Miscellaneous functions for bit-wise operations.
*
* Copyright (c) 2019-2021, PostgreSQL Global Development Group
*
* IDENTIFICATION
* src/common/port/pg_bitutils.cpp
*
*-------------------------------------------------------------------------
*/
#include "c.h"
#ifdef HAVE__GET_CPUID
#include <cpuid.h>
#endif
#ifdef HAVE__CPUID
#include <intrin.h>
#endif
#ifdef FRONTEND
#include "postgres_fe.h"
#else
#include "postgres.h"
#endif
#include "port/pg_bitutils.h"
#ifndef Assert
#define Assert(x) assert(x)
#endif
* 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
#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;
}
* 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
* 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
int result = 0;
while (word != 0) {
result += pg_number_of_ones[word & 255];
word >>= 8;
}
return result;
#endif
}
* 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
int result = 0;
while (word != 0) {
result += pg_number_of_ones[word & 255];
word >>= 8;
}
return result;
#endif
}
* 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
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
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
while (bytes--)
popcnt += pg_number_of_ones[(unsigned char)*buf++];
return popcnt;
}