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