1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
/*------------------------------------------------------------------------ -
*
* pg_bitutils.h
* miscellaneous functions for bit-wise operations.
*
*
* Portions Copyright(c) 2019, PostgreSQL Global Development Group
*
* src/include/port/pg_bitutils.h
*
*------------------------------------------------------------------------ -
*/
#ifndef PG_BITUTILS_H
#define PG_BITUTILS_H
extern int (*pg_popcount32) (uint32 word);
extern int (*pg_popcount64) (uint64 word);
extern uint64 pg_popcount(const char *buf, int bytes);
/* in pg_bitutils_hwpopcnt.c */
extern int pg_popcount32_hw(uint32 word);
extern int pg_popcount64_hw(uint64 word);
#ifndef HAVE__BUILTIN_CTZ
/*
* Array marking the position of the right-most set bit for each value of
* 1-255. We count the right-most position as the 0th bit, and the
* left-most the 7th bit. The 0th index of the array must not be used.
*/
static const uint8 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
};
#endif /* !HAVE__BUILTIN_CTZ */
/*
* pg_rightmost_one32
* Returns the number of trailing 0-bits in word, starting at the least
* significant bit position. word must not be 0.
*/
static inline int
pg_rightmost_one32(uint32 word)
{
int result = 0;
Assert(word != 0);
#ifdef HAVE__BUILTIN_CTZ
result = __builtin_ctz(word);
#else
while ((word & 255) == 0)
{
word >>= 8;
result += 8;
}
result += rightmost_one_pos[word & 255];
#endif /* HAVE__BUILTIN_CTZ */
return result;
}
/*
* pg_rightmost_one64
* Returns the number of trailing 0-bits in word, starting at the least
* significant bit position. word must not be 0.
*/
static inline int
pg_rightmost_one64(uint64 word)
{
int result = 0;
Assert(word != 0);
#ifdef HAVE__BUILTIN_CTZ
#if defined(HAVE_LONG_INT_64)
return __builtin_ctzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
return __builtin_ctzll(word);
#else
#error must have a working 64-bit integer datatype
#endif
#else /* HAVE__BUILTIN_CTZ */
while ((word & 255) == 0)
{
word >>= 8;
result += 8;
}
result += rightmost_one_pos[word & 255];
#endif
return result;
}
#ifndef HAVE__BUILTIN_CLZ
/*
* Array marking the position of the left-most set bit for each value of
* 1-255. We count the right-most position as the 0th bit, and the
* left-most the 7th bit. The 0th index of the array must not be used.
*/
static const uint8 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
};
#endif /* !HAVE_BUILTIN_CLZ */
/*
* pg_leftmost_one32
* Returns the 0-based 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_one32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
Assert(word != 0);
return 31 - __builtin_clz(word);
#else
int shift = 32 - 8;
Assert(word != 0);
while ((word >> shift) == 0)
shift -= 8;
return shift + leftmost_one_pos[(word >> shift) & 255];
#endif /* HAVE__BUILTIN_CLZ */
}
/*
* pg_leftmost_one64
* Returns the 0-based 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_one64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
Assert(word != 0);
#if defined(HAVE_LONG_INT_64)
return 63 - __builtin_clzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
return 63 - __builtin_clzll(word);
#else
#error must have a working 64-bit integer datatype
#endif
#else /* HAVE__BUILTIN_CLZ */
int shift = 64 - 8;
Assert(word != 0);
while ((word >> shift) == 0)
shift -= 8;
return shift + leftmost_one_pos[(word >> shift) & 255];
#endif /* !HAVE__BUIILTIN_CLZ */
}
#endif /* PG_BITUTILS_H */
|
