pg_bitutils.h

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * pg_bitutils.h
 *    Miscellaneous functions for bit-wise operations.
 *
 *
 * Copyright (c) 2019-2026, PostgreSQL Global Development Group
 *
 * src/include/port/pg_bitutils.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef PG_BITUTILS_H
#define PG_BITUTILS_H
 
#ifdef _MSC_VER
#include <intrin.h>
#define HAVE_BITSCAN_FORWARD
#define HAVE_BITSCAN_REVERSE
 
#else
#if defined(HAVE__BUILTIN_CTZ)
#define HAVE_BITSCAN_FORWARD
#endif
 
#if defined(HAVE__BUILTIN_CLZ)
#define HAVE_BITSCAN_REVERSE
#endif
#endif                          /* _MSC_VER */
 
extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
 
/*
 * pg_leftmost_one_pos32
 *      Returns the position of the most significant set bit in "word",
 *      measured from the least significant bit.  word must not be 0.
 */
static inline int
pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
    Assert(word != 0);
 
    return 31 - __builtin_clz(word);
#elif defined(_MSC_VER)
    unsigned long result;
    bool        non_zero;
 
    Assert(word != 0);
 
    non_zero = _BitScanReverse(&result, word);
    return (int) result;
#else
    int         shift = 32 - 8;
 
    Assert(word != 0);
 
    while ((word >> shift) == 0)
        shift -= 8;
 
    return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif                          /* HAVE__BUILTIN_CLZ */
}
 
/*
 * pg_leftmost_one_pos64
 *      As above, but for a 64-bit word.
 */
static inline int
pg_leftmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
    Assert(word != 0);
 
#if SIZEOF_LONG == 8
    return 63 - __builtin_clzl(word);
#elif SIZEOF_LONG_LONG == 8
    return 63 - __builtin_clzll(word);
#else
#error "cannot find integer type of the same size as uint64_t"
#endif
 
#elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))
    unsigned long result;
    bool        non_zero;
 
    Assert(word != 0);
 
    non_zero = _BitScanReverse64(&result, word);
    return (int) result;
#else
    int         shift = 64 - 8;
 
    Assert(word != 0);
 
    while ((word >> shift) == 0)
        shift -= 8;
 
    return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif                          /* HAVE__BUILTIN_CLZ */
}
 
/*
 * pg_rightmost_one_pos32
 *      Returns the position of the least significant set bit in "word",
 *      measured from the least significant bit.  word must not be 0.
 */
static inline int
pg_rightmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CTZ
    Assert(word != 0);
 
    return __builtin_ctz(word);
#elif defined(_MSC_VER)
    unsigned long result;
    bool        non_zero;
 
    Assert(word != 0);
 
    non_zero = _BitScanForward(&result, word);
    return (int) result;
#else
    int         result = 0;
 
    Assert(word != 0);
 
    while ((word & 255) == 0)
    {
        word >>= 8;
        result += 8;
    }
    result += pg_rightmost_one_pos[word & 255];
    return result;
#endif                          /* HAVE__BUILTIN_CTZ */
}
 
/*
 * pg_rightmost_one_pos64
 *      As above, but for a 64-bit word.
 */
static inline int
pg_rightmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CTZ
    Assert(word != 0);
 
#if SIZEOF_LONG == 8
    return __builtin_ctzl(word);
#elif SIZEOF_LONG_LONG == 8
    return __builtin_ctzll(word);
#else
#error "cannot find integer type of the same size as uint64_t"
#endif
 
#elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_ARM64))
    unsigned long result;
    bool        non_zero;
 
    Assert(word != 0);
 
    non_zero = _BitScanForward64(&result, word);
    return (int) result;
#else
    int         result = 0;
 
    Assert(word != 0);
 
    while ((word & 255) == 0)
    {
        word >>= 8;
        result += 8;
    }
    result += pg_rightmost_one_pos[word & 255];
    return result;
#endif                          /* HAVE__BUILTIN_CTZ */
}
 
/*
 * pg_nextpower2_32
 *      Returns the next higher power of 2 above 'num', or 'num' if it's
 *      already a power of 2.
 *
 * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.
 */
static inline uint32
pg_nextpower2_32(uint32 num)
{
    Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
 
    /*
     * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
     * will turn on all previous bits resulting in no common bits being set
     * between num and num-1.
     */
    if ((num & (num - 1)) == 0)
        return num;             /* already power 2 */
 
    return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
}
 
/*
 * pg_nextpower2_64
 *      Returns the next higher power of 2 above 'num', or 'num' if it's
 *      already a power of 2.
 *
 * 'num' mustn't be 0 or be above PG_UINT64_MAX / 2  + 1.
 */
static inline uint64
pg_nextpower2_64(uint64 num)
{
    Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
 
    /*
     * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
     * will turn on all previous bits resulting in no common bits being set
     * between num and num-1.
     */
    if ((num & (num - 1)) == 0)
        return num;             /* already power 2 */
 
    return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
}
 
/*
 * pg_prevpower2_32
 *      Returns the next lower power of 2 below 'num', or 'num' if it's
 *      already a power of 2.
 *
 * 'num' mustn't be 0.
 */
static inline uint32
pg_prevpower2_32(uint32 num)
{
    return ((uint32) 1) << pg_leftmost_one_pos32(num);
}
 
/*
 * pg_prevpower2_64
 *      Returns the next lower power of 2 below 'num', or 'num' if it's
 *      already a power of 2.
 *
 * 'num' mustn't be 0.
 */
static inline uint64
pg_prevpower2_64(uint64 num)
{
    return ((uint64) 1) << pg_leftmost_one_pos64(num);
}
 
/*
 * pg_ceil_log2_32
 *      Returns equivalent of ceil(log2(num))
 */
static inline uint32
pg_ceil_log2_32(uint32 num)
{
    if (num < 2)
        return 0;
    else
        return pg_leftmost_one_pos32(num - 1) + 1;
}
 
/*
 * pg_ceil_log2_64
 *      Returns equivalent of ceil(log2(num))
 */
static inline uint64
pg_ceil_log2_64(uint64 num)
{
    if (num < 2)
        return 0;
    else
        return pg_leftmost_one_pos64(num - 1) + 1;
}
 
extern uint64 pg_popcount_portable(const char *buf, int bytes);
extern uint64 pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask);
 
#if defined(HAVE_X86_64_POPCNTQ) || defined(USE_SVE_POPCNT_WITH_RUNTIME_CHECK)
/*
 * Attempt to use specialized CPU instructions, but perform a runtime check
 * first.
 */
extern PGDLLIMPORT uint64 (*pg_popcount_optimized) (const char *buf, int bytes);
extern PGDLLIMPORT uint64 (*pg_popcount_masked_optimized) (const char *buf, int bytes, bits8 mask);
 
#else
/* Use a portable implementation -- no need for a function pointer. */
extern uint64 pg_popcount_optimized(const char *buf, int bytes);
extern uint64 pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask);
 
#endif
 
/*
 * pg_popcount32
 *      Return the number of 1 bits set in word
 *
 * Adapted from
 * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
 *
 * Note that newer versions of popular compilers will automatically replace
 * this with a special popcount instruction if possible, so we don't bother
 * using builtin functions or intrinsics.
 */
static inline int
pg_popcount32(uint32 word)
{
    word -= (word >> 1) & 0x55555555;
    word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
    return (((word + (word >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
}
 
/*
 * pg_popcount64
 *      Return the number of 1 bits set in word
 *
 * Adapted from
 * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel.
 *
 * Note that newer versions of popular compilers will automatically replace
 * this with a special popcount instruction if possible, so we don't bother
 * using builtin functions or intrinsics.
 */
static inline int
pg_popcount64(uint64 word)
{
    word -= (word >> 1) & UINT64CONST(0x5555555555555555);
    word = (word & UINT64CONST(0x3333333333333333)) +
        ((word >> 2) & UINT64CONST(0x3333333333333333));
    word = (word + (word >> 4)) & UINT64CONST(0xf0f0f0f0f0f0f0f);
    return (word * UINT64CONST(0x101010101010101)) >> 56;
}
 
/*
 * Returns the number of 1-bits in buf.
 *
 * If there aren't many bytes to process, the function call overhead of the
 * optimized versions isn't worth taking, so we inline a loop that consults
 * pg_number_of_ones in that case.  If there are many bytes to process, we
 * accept the function call overhead because the optimized versions are likely
 * to be faster.
 */
static inline uint64
pg_popcount(const char *buf, int bytes)
{
    /*
     * We set the threshold to the point at which we'll first use special
     * instructions in the optimized version.
     */
    if (bytes < 8)
    {
        uint64      popcnt = 0;
 
        while (bytes--)
            popcnt += pg_number_of_ones[(unsigned char) *buf++];
        return popcnt;
    }
 
    return pg_popcount_optimized(buf, bytes);
}
 
/*
 * Returns the number of 1-bits in buf after applying the mask to each byte.
 *
 * Similar to pg_popcount(), we only take on the function pointer overhead when
 * it's likely to be faster.
 */
static inline uint64
pg_popcount_masked(const char *buf, int bytes, bits8 mask)
{
    /*
     * We set the threshold to the point at which we'll first use special
     * instructions in the optimized version.
     */
    if (bytes < 8)
    {
        uint64      popcnt = 0;
 
        while (bytes--)
            popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
        return popcnt;
    }
 
    return pg_popcount_masked_optimized(buf, bytes, mask);
}
 
/*
 * Rotate the bits of "word" to the right/left by n bits.
 */
static inline uint32
pg_rotate_right32(uint32 word, int n)
{
    return (word >> n) | (word << (32 - n));
}
 
static inline uint32
pg_rotate_left32(uint32 word, int n)
{
    return (word << n) | (word >> (32 - n));
}
 
/* size_t variants of the above, as required */
 
#if SIZEOF_SIZE_T == 4
#define pg_leftmost_one_pos_size_t pg_leftmost_one_pos32
#define pg_nextpower2_size_t pg_nextpower2_32
#define pg_prevpower2_size_t pg_prevpower2_32
#else
#define pg_leftmost_one_pos_size_t pg_leftmost_one_pos64
#define pg_nextpower2_size_t pg_nextpower2_64
#define pg_prevpower2_size_t pg_prevpower2_64
#endif
 
#endif                          /* PG_BITUTILS_H */