/src/postgres/src/port/pg_bitutils.c

Source
/*-------------------------------------------------------------------------
 *
 * 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_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(*words++);
      bytes -= 8;
    }

    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, uint8 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(*words++ & maskv);
      bytes -= 8;
    }

    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.
 */

/*
 * 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, uint8 mask)
{
  return pg_popcount_masked_portable(buf, bytes, mask);
}

#endif              /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */

Line	Count	Source
1		/*-------------------------------------------------------------------------
2		*
3		* pg_bitutils.c
4		* Miscellaneous functions for bit-wise operations.
5		*
6		* Copyright (c) 2019-2026, PostgreSQL Global Development Group
7		*
8		* IDENTIFICATION
9		* src/port/pg_bitutils.c
10		*
11		*-------------------------------------------------------------------------
12		*/
13		#include "c.h"
14
15		#include "port/pg_bitutils.h"
16
17
18		/*
19		* Array giving the position of the left-most set bit for each possible
20		* byte value. We count the right-most position as the 0th bit, and the
21		* left-most the 7th bit. The 0th entry of the array should not be used.
22		*
23		* Note: this is not used by the functions in pg_bitutils.h when
24		* HAVE__BUILTIN_CLZ is defined, but we provide it anyway, so that
25		* extensions possibly compiled with a different compiler can use it.
26		*/
27		const uint8 pg_leftmost_one_pos[256] = {
28		0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
29		4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
30		5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
31		5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
32		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
33		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
34		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
35		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
36		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
37		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
38		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
39		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
40		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
41		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
42		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
43		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
44		};
45
46		/*
47		* Array giving the position of the right-most set bit for each possible
48		* byte value. We count the right-most position as the 0th bit, and the
49		* left-most the 7th bit. The 0th entry of the array should not be used.
50		*
51		* Note: this is not used by the functions in pg_bitutils.h when
52		* HAVE__BUILTIN_CTZ is defined, but we provide it anyway, so that
53		* extensions possibly compiled with a different compiler can use it.
54		*/
55		const uint8 pg_rightmost_one_pos[256] = {
56		0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
57		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
58		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
59		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
60		6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
61		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
62		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
63		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
64		7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
65		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
66		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
67		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
68		6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
69		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
70		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
72		};
73
74		/*
75		* Array giving the number of 1-bits in each possible byte value.
76		*
77		* Note: we export this for use by functions in which explicit use
78		* of the popcount functions seems unlikely to be a win.
79		*/
80		const uint8 pg_number_of_ones[256] = {
81		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
82		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
83		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
84		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
85		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
86		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
87		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
88		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
89		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
91		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
93		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
95		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
97		};
98
99		/*
100		* pg_popcount_portable
101		* Returns the number of 1-bits in buf
102		*/
103		uint64
104		pg_popcount_portable(const char *buf, int bytes)
105	0	{
106	0	uint64 popcnt = 0;
107
108	0	#if SIZEOF_VOID_P >= 8
109		/* Process in 64-bit chunks if the buffer is aligned. */
110	0	if (buf == (const char *) TYPEALIGN(8, buf))
111	0	{
112	0	const uint64 words = (const uint64 ) buf;
113
114	0	while (bytes >= 8)
115	0	{
116	0	popcnt += pg_popcount64(*words++);
117	0	bytes -= 8;
118	0	}
119
120	0	buf = (const char *) words;
121	0	}
122	0	#endif
123
124		/* Process any remaining bytes */
125	0	while (bytes--)
126	0	popcnt += pg_number_of_ones[(unsigned char) *buf++];
127
128	0	return popcnt;
129	0	}
130
131		/*
132		* pg_popcount_masked_portable
133		* Returns the number of 1-bits in buf after applying the mask to each byte
134		*/
135		uint64
136		pg_popcount_masked_portable(const char *buf, int bytes, uint8 mask)
137	0	{
138	0	uint64 popcnt = 0;
139
140	0	#if SIZEOF_VOID_P >= 8
141		/* Process in 64-bit chunks if the buffer is aligned */
142	0	uint64 maskv = ~UINT64CONST(0) / 0xFF * mask;
143
144	0	if (buf == (const char *) TYPEALIGN(8, buf))
145	0	{
146	0	const uint64 words = (const uint64 ) buf;
147
148	0	while (bytes >= 8)
149	0	{
150	0	popcnt += pg_popcount64(*words++ & maskv);
151	0	bytes -= 8;
152	0	}
153
154	0	buf = (const char *) words;
155	0	}
156	0	#endif
157
158		/* Process any remaining bytes */
159	0	while (bytes--)
160	0	popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
161
162	0	return popcnt;
163	0	}
164
165		#if !defined(HAVE_X86_64_POPCNTQ) && !defined(USE_NEON)
166
167		/*
168		* When special CPU instructions are not available, there's no point in using
169		* function pointers to vary the implementation. We instead just make these
170		* actual external functions. The compiler should be able to inline the
171		* portable versions here.
172		*/
173
174		/*
175		* pg_popcount_optimized
176		* Returns the number of 1-bits in buf
177		*/
178		uint64
179		pg_popcount_optimized(const char *buf, int bytes)
180		{
181		return pg_popcount_portable(buf, bytes);
182		}
183
184		/*
185		* pg_popcount_masked_optimized
186		* Returns the number of 1-bits in buf after applying the mask to each byte
187		*/
188		uint64
189		pg_popcount_masked_optimized(const char *buf, int bytes, uint8 mask)
190		{
191		return pg_popcount_masked_portable(buf, bytes, mask);
192		}
193
194		#endif /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */

Coverage Report

Created: 2026-09-28 06:55