pg_bitutils.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * pg_bitutils.c
 *    Miscellaneous functions for bit-wise operations.
 *
 * Copyright (c) 2019-2026, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *    src/port/pg_bitutils.c
 *
 *-------------------------------------------------------------------------
 */
#include "c.h"
 
#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
};
 
/*
 * pg_popcount32_portable
 *      Return the number of 1 bits set in word
 */
int
pg_popcount32_portable(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_portable
 *      Return the number of 1 bits set in word
 */
int
pg_popcount64_portable(uint64 word)
{
#ifdef HAVE__BUILTIN_POPCOUNT
#if SIZEOF_LONG == 8
    return __builtin_popcountl(word);
#elif SIZEOF_LONG_LONG == 8
    return __builtin_popcountll(word);
#else
#error "cannot find integer of the same size as uint64_t"
#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_portable
 *      Returns the number of 1-bits in buf
 */
uint64
pg_popcount_portable(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_portable(*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_portable(*words++);
            bytes -= 4;
        }
 
        buf = (const char *) words;
    }
#endif
 
    /* Process any remaining bytes */
    while (bytes--)
        popcnt += pg_number_of_ones[(unsigned char) *buf++];
 
    return popcnt;
}
 
/*
 * pg_popcount_masked_portable
 *      Returns the number of 1-bits in buf after applying the mask to each byte
 */
uint64
pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask)
{
    uint64      popcnt = 0;
 
#if SIZEOF_VOID_P >= 8
    /* Process in 64-bit chunks if the buffer is aligned */
    uint64      maskv = ~UINT64CONST(0) / 0xFF * mask;
 
    if (buf == (const char *) TYPEALIGN(8, buf))
    {
        const uint64 *words = (const uint64 *) buf;
 
        while (bytes >= 8)
        {
            popcnt += pg_popcount64_portable(*words++ & maskv);
            bytes -= 8;
        }
 
        buf = (const char *) words;
    }
#else
    /* Process in 32-bit chunks if the buffer is aligned. */
    uint32      maskv = ~((uint32) 0) / 0xFF * mask;
 
    if (buf == (const char *) TYPEALIGN(4, buf))
    {
        const uint32 *words = (const uint32 *) buf;
 
        while (bytes >= 4)
        {
            popcnt += pg_popcount32_portable(*words++ & maskv);
            bytes -= 4;
        }
 
        buf = (const char *) words;
    }
#endif
 
    /* Process any remaining bytes */
    while (bytes--)
        popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
 
    return popcnt;
}
 
#if !defined(HAVE_X86_64_POPCNTQ) && !defined(USE_NEON)
 
/*
 * When special CPU instructions are not available, there's no point in using
 * function pointers to vary the implementation.  We instead just make these
 * actual external functions.  The compiler should be able to inline the
 * portable versions here.
 */
int
pg_popcount32(uint32 word)
{
    return pg_popcount32_portable(word);
}
 
int
pg_popcount64(uint64 word)
{
    return pg_popcount64_portable(word);
}
 
/*
 * pg_popcount_optimized
 *      Returns the number of 1-bits in buf
 */
uint64
pg_popcount_optimized(const char *buf, int bytes)
{
    return pg_popcount_portable(buf, bytes);
}
 
/*
 * pg_popcount_masked_optimized
 *      Returns the number of 1-bits in buf after applying the mask to each byte
 */
uint64
pg_popcount_masked_optimized(const char *buf, int bytes, bits8 mask)
{
    return pg_popcount_masked_portable(buf, bytes, mask);
}
 
#endif                          /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */