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