1 /*
2 +----------------------------------------------------------------------+
3 | Zend OPcache JIT |
4 +----------------------------------------------------------------------+
5 | Copyright (c) The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | https://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Dmitry Stogov <dmitry@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 #ifndef _ZEND_BITSET_H_
20 #define _ZEND_BITSET_H_
21
22 #include <stdint.h>
23 #include <stdbool.h>
24 #include <string.h>
25
26 #include "zend_portability.h"
27 #include "zend_long.h"
28
29 typedef zend_ulong *zend_bitset;
30
31 #define ZEND_BITSET_ELM_SIZE sizeof(zend_ulong)
32
33 #if SIZEOF_ZEND_LONG == 4
34 # define ZEND_BITSET_ELM_NUM(n) ((n) >> 5)
35 # define ZEND_BITSET_BIT_NUM(n) ((zend_ulong)(n) & Z_UL(0x1f))
36 #elif SIZEOF_ZEND_LONG == 8
37 # define ZEND_BITSET_ELM_NUM(n) ((n) >> 6)
38 # define ZEND_BITSET_BIT_NUM(n) ((zend_ulong)(n) & Z_UL(0x3f))
39 #else
40 # define ZEND_BITSET_ELM_NUM(n) ((n) / (sizeof(zend_long) * 8))
41 # define ZEND_BITSET_BIT_NUM(n) ((n) % (sizeof(zend_long) * 8))
42 #endif
43
44 #define ZEND_BITSET_ALLOCA(n, use_heap) \
45 (zend_bitset)do_alloca((n) * ZEND_BITSET_ELM_SIZE, use_heap)
46
47 /* Number of trailing zero bits (0x01 -> 0; 0x40 -> 6; 0x00 -> LEN) */
zend_ulong_ntz(zend_ulong num)48 ZEND_ATTRIBUTE_CONST static zend_always_inline int zend_ulong_ntz(zend_ulong num)
49 {
50 #if (defined(__GNUC__) || __has_builtin(__builtin_ctzl)) \
51 && SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CTZL)
52 return __builtin_ctzl(num);
53 #elif (defined(__GNUC__) || __has_builtin(__builtin_ctzll)) && defined(PHP_HAVE_BUILTIN_CTZLL)
54 return __builtin_ctzll(num);
55 #elif defined(_WIN32)
56 unsigned long index;
57
58 #if defined(_WIN64)
59 if (!BitScanForward64(&index, num)) {
60 #else
61 if (!BitScanForward(&index, num)) {
62 #endif
63 /* undefined behavior */
64 return SIZEOF_ZEND_LONG * 8;
65 }
66
67 return (int) index;
68 #else
69 int n;
70
71 if (num == Z_UL(0)) return SIZEOF_ZEND_LONG * 8;
72
73 n = 1;
74 #if SIZEOF_ZEND_LONG == 8
75 if ((num & 0xffffffff) == 0) {n += 32; num = num >> Z_UL(32);}
76 #endif
77 if ((num & 0x0000ffff) == 0) {n += 16; num = num >> 16;}
78 if ((num & 0x000000ff) == 0) {n += 8; num = num >> 8;}
79 if ((num & 0x0000000f) == 0) {n += 4; num = num >> 4;}
80 if ((num & 0x00000003) == 0) {n += 2; num = num >> 2;}
81 return n - (num & 1);
82 #endif
83 }
84
85 /* Number of leading zero bits (Undefined for zero) */
86 ZEND_ATTRIBUTE_CONST static zend_always_inline int zend_ulong_nlz(zend_ulong num)
87 {
88 #if (defined(__GNUC__) || __has_builtin(__builtin_clzl)) \
89 && SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CLZL)
90 return __builtin_clzl(num);
91 #elif (defined(__GNUC__) || __has_builtin(__builtin_clzll)) && defined(PHP_HAVE_BUILTIN_CLZLL)
92 return __builtin_clzll(num);
93 #elif defined(_WIN32)
94 unsigned long index;
95
96 #if defined(_WIN64)
97 if (!BitScanReverse64(&index, num)) {
98 #else
99 if (!BitScanReverse(&index, num)) {
100 #endif
101 /* undefined behavior */
102 return SIZEOF_ZEND_LONG * 8;
103 }
104
105 return (int) (SIZEOF_ZEND_LONG * 8 - 1)- index;
106 #else
107 zend_ulong x;
108 int n;
109
110 #if SIZEOF_ZEND_LONG == 8
111 n = 64;
112 x = num >> 32; if (x != 0) {n -= 32; num = x;}
113 #else
114 n = 32;
115 #endif
116 x = num >> 16; if (x != 0) {n -= 16; num = x;}
117 x = num >> 8; if (x != 0) {n -= 8; num = x;}
118 x = num >> 4; if (x != 0) {n -= 4; num = x;}
119 x = num >> 2; if (x != 0) {n -= 2; num = x;}
120 x = num >> 1; if (x != 0) return n - 2;
121 return n - num;
122 #endif
123 }
124
125 /* Returns the number of zend_ulong words needed to store a bitset that is N
126 bits long. */
127 static inline uint32_t zend_bitset_len(uint32_t n)
128 {
129 return (n + ((sizeof(zend_long) * 8) - 1)) / (sizeof(zend_long) * 8);
130 }
131
132 static inline bool zend_bitset_in(zend_bitset set, uint32_t n)
133 {
134 return ZEND_BIT_TEST(set, n);
135 }
136
137 static inline void zend_bitset_incl(zend_bitset set, uint32_t n)
138 {
139 set[ZEND_BITSET_ELM_NUM(n)] |= Z_UL(1) << ZEND_BITSET_BIT_NUM(n);
140 }
141
142 static inline void zend_bitset_excl(zend_bitset set, uint32_t n)
143 {
144 set[ZEND_BITSET_ELM_NUM(n)] &= ~(Z_UL(1) << ZEND_BITSET_BIT_NUM(n));
145 }
146
147 static inline void zend_bitset_clear(zend_bitset set, uint32_t len)
148 {
149 memset(set, 0, len * ZEND_BITSET_ELM_SIZE);
150 }
151
152 static inline bool zend_bitset_empty(zend_bitset set, uint32_t len)
153 {
154 uint32_t i;
155 for (i = 0; i < len; i++) {
156 if (set[i]) {
157 return 0;
158 }
159 }
160 return 1;
161 }
162
163 static inline void zend_bitset_fill(zend_bitset set, uint32_t len)
164 {
165 memset(set, 0xff, len * ZEND_BITSET_ELM_SIZE);
166 }
167
168 static inline bool zend_bitset_equal(zend_bitset set1, zend_bitset set2, uint32_t len)
169 {
170 return memcmp(set1, set2, len * ZEND_BITSET_ELM_SIZE) == 0;
171 }
172
173 static inline void zend_bitset_copy(zend_bitset set1, zend_bitset set2, uint32_t len)
174 {
175 memcpy(set1, set2, len * ZEND_BITSET_ELM_SIZE);
176 }
177
178 static inline void zend_bitset_intersection(zend_bitset set1, zend_bitset set2, uint32_t len)
179 {
180 uint32_t i;
181
182 for (i = 0; i < len; i++) {
183 set1[i] &= set2[i];
184 }
185 }
186
187 static inline void zend_bitset_union(zend_bitset set1, zend_bitset set2, uint32_t len)
188 {
189 uint32_t i;
190
191 for (i = 0; i < len; i++) {
192 set1[i] |= set2[i];
193 }
194 }
195
196 static inline void zend_bitset_difference(zend_bitset set1, zend_bitset set2, uint32_t len)
197 {
198 uint32_t i;
199
200 for (i = 0; i < len; i++) {
201 set1[i] = set1[i] & ~set2[i];
202 }
203 }
204
205 static inline void zend_bitset_union_with_intersection(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
206 {
207 uint32_t i;
208
209 for (i = 0; i < len; i++) {
210 set1[i] = set2[i] | (set3[i] & set4[i]);
211 }
212 }
213
214 static inline void zend_bitset_union_with_difference(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
215 {
216 uint32_t i;
217
218 for (i = 0; i < len; i++) {
219 set1[i] = set2[i] | (set3[i] & ~set4[i]);
220 }
221 }
222
223 static inline bool zend_bitset_subset(zend_bitset set1, zend_bitset set2, uint32_t len)
224 {
225 uint32_t i;
226
227 for (i = 0; i < len; i++) {
228 if (set1[i] & ~set2[i]) {
229 return 0;
230 }
231 }
232 return 1;
233 }
234
235 static inline int zend_bitset_first(zend_bitset set, uint32_t len)
236 {
237 uint32_t i;
238
239 for (i = 0; i < len; i++) {
240 if (set[i]) {
241 return ZEND_BITSET_ELM_SIZE * 8 * i + zend_ulong_ntz(set[i]);
242 }
243 }
244 return -1; /* empty set */
245 }
246
247 static inline int zend_bitset_last(zend_bitset set, uint32_t len)
248 {
249 uint32_t i = len;
250
251 while (i > 0) {
252 i--;
253 if (set[i]) {
254 int j = ZEND_BITSET_ELM_SIZE * 8 * i - 1;
255 zend_ulong x = set[i];
256 while (x != Z_UL(0)) {
257 x = x >> Z_UL(1);
258 j++;
259 }
260 return j;
261 }
262 }
263 return -1; /* empty set */
264 }
265
266 #define ZEND_BITSET_FOREACH(set, len, bit) do { \
267 zend_bitset _set = (set); \
268 uint32_t _i, _len = (len); \
269 for (_i = 0; _i < _len; _i++) { \
270 zend_ulong _x = _set[_i]; \
271 if (_x) { \
272 (bit) = ZEND_BITSET_ELM_SIZE * 8 * _i; \
273 for (; _x != 0; _x >>= Z_UL(1), (bit)++) { \
274 if (!(_x & Z_UL(1))) continue;
275
276 #define ZEND_BITSET_REVERSE_FOREACH(set, len, bit) do { \
277 zend_bitset _set = (set); \
278 uint32_t _i = (len); \
279 zend_ulong _test = Z_UL(1) << (ZEND_BITSET_ELM_SIZE * 8 - 1); \
280 while (_i-- > 0) { \
281 zend_ulong _x = _set[_i]; \
282 if (_x) { \
283 (bit) = ZEND_BITSET_ELM_SIZE * 8 * (_i + 1) - 1; \
284 for (; _x != 0; _x <<= Z_UL(1), (bit)--) { \
285 if (!(_x & _test)) continue; \
286
287 #define ZEND_BITSET_FOREACH_END() \
288 } \
289 } \
290 } \
291 } while (0)
292
293 static inline int zend_bitset_pop_first(zend_bitset set, uint32_t len) {
294 int i = zend_bitset_first(set, len);
295 if (i >= 0) {
296 zend_bitset_excl(set, i);
297 }
298 return i;
299 }
300
301 #endif /* _ZEND_BITSET_H_ */
302
