xref: /PHP-8.3/Zend/zend_bitset.h (revision c8ec2ed7)
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 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 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