pg_bitutils.c File Reference

#include "c.h"
#include "port/pg_bitutils.h"

Include dependency graph for pg_bitutils.c:

Go to the source code of this file.

Functions
static int	pg_popcount32_slow (uint32 word)
static int	pg_popcount64_slow (uint64 word)
static uint64	pg_popcount_slow (const char *buf, int bytes)
static uint64	pg_popcount_masked_slow (const char *buf, int bytes, bits8 mask)
int	pg_popcount32 (uint32 word)
int	pg_popcount64 (uint64 word)
uint64	pg_popcount_optimized (const char *buf, int bytes)
uint64	pg_popcount_masked_optimized (const char *buf, int bytes, bits8 mask)

Variables
const uint8	pg_leftmost_one_pos [256]
const uint8	pg_rightmost_one_pos [256]
const uint8	pg_number_of_ones [256]

Function Documentation

pg_popcount32()

int pg_popcount32

(

uint32

word

)

Definition at line 509 of file pg_bitutils.c.

{
    return pg_popcount32_slow(word);
}

References pg_popcount32_slow(), and word().

Referenced by plan_single_revoke().

pg_popcount32_slow()

static int pg_popcount32_slow ( uint32  word )

inlinestatic

Definition at line 357 of file pg_bitutils.c.

{
#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 */
}

References pg_number_of_ones, and word().

Referenced by pg_popcount32(), pg_popcount_masked_slow(), and pg_popcount_slow().

pg_popcount64()

int pg_popcount64

(

uint64

word

)

Definition at line 515 of file pg_bitutils.c.

{
    return pg_popcount64_slow(word);
}

References pg_popcount64_slow(), and word().

Referenced by select_best_grantor().

pg_popcount64_slow()

static int pg_popcount64_slow ( uint64  word )

inlinestatic

Definition at line 379 of file pg_bitutils.c.

{
#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 */
}

References pg_number_of_ones, and word().

Referenced by pg_popcount64(), pg_popcount_masked_slow(), and pg_popcount_slow().

pg_popcount_masked_optimized()

uint64 pg_popcount_masked_optimized	(	const char *	buf,
		int	bytes,
		bits8	mask
	)

Definition at line 535 of file pg_bitutils.c.

{
    return pg_popcount_masked_slow(buf, bytes, mask);
}

References buf, and pg_popcount_masked_slow().

Referenced by pg_popcount_masked().

pg_popcount_masked_slow()

static uint64 pg_popcount_masked_slow ( const char *  buf, int  bytes, bits8  mask  )

static

Definition at line 453 of file pg_bitutils.c.

{
    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_slow(*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_slow(*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;
}

References buf, pg_number_of_ones, pg_popcount32_slow(), pg_popcount64_slow(), and TYPEALIGN.

Referenced by pg_popcount_masked_optimized().

pg_popcount_optimized()

uint64 pg_popcount_optimized	(	const char *	buf,
		int	bytes
	)

Definition at line 525 of file pg_bitutils.c.

{
    return pg_popcount_slow(buf, bytes);
}

References buf, and pg_popcount_slow().

Referenced by pg_popcount().

pg_popcount_slow()

static uint64 pg_popcount_slow ( const char *  buf, int  bytes  )

static

Definition at line 407 of file pg_bitutils.c.

{
    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_slow(*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_slow(*words++);
            bytes -= 4;
        }
 
        buf = (const char *) words;
    }
#endif
 
    /* Process any remaining bytes */
    while (bytes--)
        popcnt += pg_number_of_ones[(unsigned char) *buf++];
 
    return popcnt;
}

References buf, pg_number_of_ones, pg_popcount32_slow(), pg_popcount64_slow(), and TYPEALIGN.

Referenced by pg_popcount_optimized().

Variable Documentation

pg_leftmost_one_pos

const uint8 pg_leftmost_one_pos[256]

Initial value:

= {
    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
}

Definition at line 34 of file pg_bitutils.c.

Referenced by AllocSetFreeIndex(), pg_leftmost_one_pos32(), and pg_leftmost_one_pos64().

pg_number_of_ones

const uint8 pg_number_of_ones[256]

Initial value:

= {
    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
}

Definition at line 87 of file pg_bitutils.c.

Referenced by hemdistsign(), pg_popcount(), pg_popcount32_slow(), pg_popcount64_slow(), pg_popcount_masked(), pg_popcount_masked_slow(), pg_popcount_slow(), and process_pipe_input().

pg_rightmost_one_pos

const uint8 pg_rightmost_one_pos[256]

Initial value:

= {
    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
}

Definition at line 62 of file pg_bitutils.c.

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().