Age Owner Branch data TLA Line data Source code
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
53 nathan@postgresql.or 104 :UNC 0 : pg_popcount_portable(const char *buf, int bytes)
105 : : {
2585 tgl@sss.pgh.pa.us 106 :UBC 0 : uint64 popcnt = 0;
107 : :
108 : : #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 : : {
112 : 0 : const uint64 *words = (const uint64 *) buf;
113 : :
114 [ # # ]: 0 : while (bytes >= 8)
115 : : {
31 nathan@postgresql.or 116 :UNC 0 : popcnt += pg_popcount64(*words++);
2585 tgl@sss.pgh.pa.us 117 :UBC 0 : bytes -= 8;
118 : : }
119 : :
2585 tgl@sss.pgh.pa.us 120 :UIC 0 : buf = (const char *) words;
121 : : }
122 : : #endif
123 : :
124 : : /* Process any remaining bytes */
2585 tgl@sss.pgh.pa.us 125 [ # # ]:UBC 0 : while (bytes--)
126 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++];
127 : :
128 : 0 : return popcnt;
129 : : }
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
53 nathan@postgresql.or 136 :UNC 0 : pg_popcount_masked_portable(const char *buf, int bytes, bits8 mask)
137 : : {
708 nathan@postgresql.or 138 :UBC 0 : uint64 popcnt = 0;
139 : :
140 : : #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 : : {
146 : 0 : const uint64 *words = (const uint64 *) buf;
147 : :
148 [ # # ]: 0 : while (bytes >= 8)
149 : : {
31 nathan@postgresql.or 150 :UNC 0 : popcnt += pg_popcount64(*words++ & maskv);
708 nathan@postgresql.or 151 :UBC 0 : bytes -= 8;
152 : : }
153 : :
708 nathan@postgresql.or 154 :UIC 0 : buf = (const char *) words;
155 : : }
156 : : #endif
157 : :
158 : : /* Process any remaining bytes */
708 nathan@postgresql.or 159 [ # # ]:UBC 0 : while (bytes--)
160 : 0 : popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
161 : :
162 : 0 : return popcnt;
163 : : }
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, bits8 mask)
190 : : {
191 : : return pg_popcount_masked_portable(buf, bytes, mask);
192 : : }
193 : :
194 : : #endif /* ! HAVE_X86_64_POPCNTQ && ! USE_NEON */
|
