/src/php-src/Zend/zend_bitset.h

Source (jump to first uncovered line)
/*
   +----------------------------------------------------------------------+
   | Zend OPcache JIT                                                     |
   +----------------------------------------------------------------------+
   | Copyright (c) The PHP Group                                          |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | http://www.php.net/license/3_01.txt                                  |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
   | Authors: Dmitry Stogov <dmitry@php.net>                              |
   +----------------------------------------------------------------------+
*/

#ifndef _ZEND_BITSET_H_
#define _ZEND_BITSET_H_

typedef zend_ulong *zend_bitset;

#define ZEND_BITSET_ELM_SIZE sizeof(zend_ulong)

#if SIZEOF_ZEND_LONG == 4
# define ZEND_BITSET_ELM_NUM(n)   ((n) >> 5)
# define ZEND_BITSET_BIT_NUM(n)   ((zend_ulong)(n) & Z_UL(0x1f))
#elif SIZEOF_ZEND_LONG == 8
# define ZEND_BITSET_ELM_NUM(n)   ((n) >> 6)
# define ZEND_BITSET_BIT_NUM(n)   ((zend_ulong)(n) & Z_UL(0x3f))
#else
# define ZEND_BITSET_ELM_NUM(n)   ((n) / (sizeof(zend_long) * 8))
# define ZEND_BITSET_BIT_NUM(n)   ((n) % (sizeof(zend_long) * 8))
#endif

#define ZEND_BITSET_ALLOCA(n, use_heap) \
  (zend_bitset)do_alloca((n) * ZEND_BITSET_ELM_SIZE, use_heap)

/* Number of trailing zero bits (0x01 -> 0; 0x40 -> 6; 0x00 -> LEN) */
static zend_always_inline int zend_ulong_ntz(zend_ulong num)
{
#if (defined(__GNUC__) || __has_builtin(__builtin_ctzl)) \
  && SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CTZL)
  return __builtin_ctzl(num);
#elif (defined(__GNUC__) || __has_builtin(__builtin_ctzll)) && defined(PHP_HAVE_BUILTIN_CTZLL)
  return __builtin_ctzll(num);
#elif defined(_WIN32)
  unsigned long index;

#if defined(_WIN64)
  if (!BitScanForward64(&index, num)) {
#else
  if (!BitScanForward(&index, num)) {
#endif
    /* undefined behavior */
    return SIZEOF_ZEND_LONG * 8;
  }

  return (int) index;
#else
  int n;

  if (num == Z_UL(0)) return SIZEOF_ZEND_LONG * 8;

  n = 1;
#if SIZEOF_ZEND_LONG == 8
  if ((num & 0xffffffff) == 0) {n += 32; num = num >> Z_UL(32);}
#endif
  if ((num & 0x0000ffff) == 0) {n += 16; num = num >> 16;}
  if ((num & 0x000000ff) == 0) {n +=  8; num = num >>  8;}
  if ((num & 0x0000000f) == 0) {n +=  4; num = num >>  4;}
  if ((num & 0x00000003) == 0) {n +=  2; num = num >>  2;}
  return n - (num & 1);
#endif
}

/* Returns the number of zend_ulong words needed to store a bitset that is N
   bits long.  */
static inline uint32_t zend_bitset_len(uint32_t n)
{
  return (n + ((sizeof(zend_long) * 8) - 1)) / (sizeof(zend_long) * 8);
}

static inline zend_bool zend_bitset_in(zend_bitset set, uint32_t n)
{
  return ZEND_BIT_TEST(set, n);
}

static inline void zend_bitset_incl(zend_bitset set, uint32_t n)
{
  set[ZEND_BITSET_ELM_NUM(n)] |= Z_UL(1) << ZEND_BITSET_BIT_NUM(n);
}

static inline void zend_bitset_excl(zend_bitset set, uint32_t n)
{
  set[ZEND_BITSET_ELM_NUM(n)] &= ~(Z_UL(1) << ZEND_BITSET_BIT_NUM(n));
}

static inline void zend_bitset_clear(zend_bitset set, uint32_t len)
{
  memset(set, 0, len * ZEND_BITSET_ELM_SIZE);
}

static inline int zend_bitset_empty(zend_bitset set, uint32_t len)
{
  uint32_t i;
  for (i = 0; i < len; i++) {
    if (set[i]) {
      return 0;
    }
  }
  return 1;
}

static inline void zend_bitset_fill(zend_bitset set, uint32_t len)
{
  memset(set, 0xff, len * ZEND_BITSET_ELM_SIZE);
}

static inline zend_bool zend_bitset_equal(zend_bitset set1, zend_bitset set2, uint32_t len)
{
    return memcmp(set1, set2, len * ZEND_BITSET_ELM_SIZE) == 0;
}

static inline void zend_bitset_copy(zend_bitset set1, zend_bitset set2, uint32_t len)
{
    memcpy(set1, set2, len * ZEND_BITSET_ELM_SIZE);
}

static inline void zend_bitset_intersection(zend_bitset set1, zend_bitset set2, uint32_t len)
{
    uint32_t i;

    for (i = 0; i < len; i++) {
    set1[i] &= set2[i];
  }
}

static inline void zend_bitset_union(zend_bitset set1, zend_bitset set2, uint32_t len)
{
  uint32_t i;

  for (i = 0; i < len; i++) {
    set1[i] |= set2[i];
  }
}

static inline void zend_bitset_difference(zend_bitset set1, zend_bitset set2, uint32_t len)
{
  uint32_t i;

  for (i = 0; i < len; i++) {
    set1[i] = set1[i] & ~set2[i];
  }
}

static inline void zend_bitset_union_with_intersection(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
{
  uint32_t i;

  for (i = 0; i < len; i++) {
    set1[i] = set2[i] | (set3[i] & set4[i]);
  }
}

static inline void zend_bitset_union_with_difference(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
{
  uint32_t i;

  for (i = 0; i < len; i++) {
    set1[i] = set2[i] | (set3[i] & ~set4[i]);
  }
}

static inline zend_bool zend_bitset_subset(zend_bitset set1, zend_bitset set2, uint32_t len)
{
  uint32_t i;

  for (i = 0; i < len; i++) {
    if (set1[i] & ~set2[i]) {
      return 0;
    }
  }
  return 1;
}

static inline int zend_bitset_first(zend_bitset set, uint32_t len)
{
  uint32_t i;

  for (i = 0; i < len; i++) {
    if (set[i]) {
      return ZEND_BITSET_ELM_SIZE * 8 * i + zend_ulong_ntz(set[i]);
    }
  }
  return -1; /* empty set */
}

static inline int zend_bitset_last(zend_bitset set, uint32_t len)
{
  uint32_t i = len;

  while (i > 0) {
    i--;
    if (set[i]) {
      int j = ZEND_BITSET_ELM_SIZE * 8 * i - 1;
      zend_ulong x = set[i];
      while (x != Z_UL(0)) {
        x = x >> Z_UL(1);
        j++;
      }
      return j;
    }
  }
  return -1; /* empty set */
}

#define ZEND_BITSET_FOREACH(set, len, bit) do { \
  zend_bitset _set = (set); \
  uint32_t _i, _len = (len); \
  for (_i = 0; _i < _len; _i++) { \
    zend_ulong _x = _set[_i]; \
    if (_x) { \
      (bit) = ZEND_BITSET_ELM_SIZE * 8 * _i; \
      for (; _x != 0; _x >>= Z_UL(1), (bit)++) { \
        if (!(_x & Z_UL(1))) continue;

#define ZEND_BITSET_REVERSE_FOREACH(set, len, bit) do { \
  zend_bitset _set = (set); \
  uint32_t _i = (len); \
  zend_ulong _test = Z_UL(1) << (ZEND_BITSET_ELM_SIZE * 8 - 1); \
  while (_i-- > 0) { \
    zend_ulong _x = _set[_i]; \
    if (_x) { \
      (bit) = ZEND_BITSET_ELM_SIZE * 8 * (_i + 1) - 1; \
      for (; _x != 0; _x <<= Z_UL(1), (bit)--) { \
        if (!(_x & _test)) continue; \

#define ZEND_BITSET_FOREACH_END() \
      } \
    } \
  } \
} while (0)

static inline int zend_bitset_pop_first(zend_bitset set, uint32_t len) {
  int i = zend_bitset_first(set, len);
  if (i >= 0) {
    zend_bitset_excl(set, i);
  }
  return i;
}

#endif /* _ZEND_BITSET_H_ */

Coverage Report

Created: 2022-07-02 04:24

Line	Count	Source (jump to first uncovered line)
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	0	#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	0	# define ZEND_BITSET_ELM_NUM(n) ((n) >> 6)
31	0	# 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	0	(zend_bitset)do_alloca((n) * ZEND_BITSET_ELM_SIZE, use_heap)
39
40		/* Number of trailing zero bits (0x01 -> 0; 0x40 -> 6; 0x00 -> LEN) */
41		static zend_always_inline int zend_ulong_ntz(zend_ulong num)
42	0	{
43	0	#if (defined(__GNUC__) \|\| __has_builtin(__builtin_ctzl)) \
44	0	&& SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CTZL)
45	0	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	0	} Unexecuted instantiation: array.c:zend_ulong_ntz Unexecuted instantiation: string.c:zend_ulong_ntz Unexecuted instantiation: zend_alloc.c:zend_ulong_ntz
77
78		/* Returns the number of zend_ulong words needed to store a bitset that is N
79		bits long. */
80		static inline uint32_t zend_bitset_len(uint32_t n)
81	0	{
82	0	return (n + ((sizeof(zend_long) * 8) - 1)) / (sizeof(zend_long) * 8);
83	0	} Unexecuted instantiation: array.c:zend_bitset_len Unexecuted instantiation: string.c:zend_bitset_len Unexecuted instantiation: zend_alloc.c:zend_bitset_len
84
85		static inline zend_bool zend_bitset_in(zend_bitset set, uint32_t n)
86	0	{
87	0	return ZEND_BIT_TEST(set, n);
88	0	} Unexecuted instantiation: array.c:zend_bitset_in Unexecuted instantiation: string.c:zend_bitset_in Unexecuted instantiation: zend_alloc.c:zend_bitset_in
89
90		static inline void zend_bitset_incl(zend_bitset set, uint32_t n)
91	0	{
92	0	set[ZEND_BITSET_ELM_NUM(n)] \|= Z_UL(1) << ZEND_BITSET_BIT_NUM(n);
93	0	} Unexecuted instantiation: array.c:zend_bitset_incl Unexecuted instantiation: string.c:zend_bitset_incl Unexecuted instantiation: zend_alloc.c:zend_bitset_incl
94
95		static inline void zend_bitset_excl(zend_bitset set, uint32_t n)
96	0	{
97	0	set[ZEND_BITSET_ELM_NUM(n)] &= ~(Z_UL(1) << ZEND_BITSET_BIT_NUM(n));
98	0	} Unexecuted instantiation: array.c:zend_bitset_excl Unexecuted instantiation: string.c:zend_bitset_excl Unexecuted instantiation: zend_alloc.c:zend_bitset_excl
99
100		static inline void zend_bitset_clear(zend_bitset set, uint32_t len)
101	0	{
102	0	memset(set, 0, len * ZEND_BITSET_ELM_SIZE);
103	0	} Unexecuted instantiation: array.c:zend_bitset_clear Unexecuted instantiation: string.c:zend_bitset_clear Unexecuted instantiation: zend_alloc.c:zend_bitset_clear
104
105		static inline int zend_bitset_empty(zend_bitset set, uint32_t len)
106	0	{
107	0	uint32_t i;
108	0	for (i = 0; i < len; i++) {
109	0	if (set[i]) {
110	0	return 0;
111	0	}
112	0	}
113	0	return 1;
114	0	} Unexecuted instantiation: array.c:zend_bitset_empty Unexecuted instantiation: string.c:zend_bitset_empty Unexecuted instantiation: zend_alloc.c:zend_bitset_empty
115
116		static inline void zend_bitset_fill(zend_bitset set, uint32_t len)
117	0	{
118	0	memset(set, 0xff, len * ZEND_BITSET_ELM_SIZE);
119	0	} Unexecuted instantiation: array.c:zend_bitset_fill Unexecuted instantiation: string.c:zend_bitset_fill Unexecuted instantiation: zend_alloc.c:zend_bitset_fill
120
121		static inline zend_bool zend_bitset_equal(zend_bitset set1, zend_bitset set2, uint32_t len)
122	0	{
123	0	return memcmp(set1, set2, len * ZEND_BITSET_ELM_SIZE) == 0;
124	0	} Unexecuted instantiation: array.c:zend_bitset_equal Unexecuted instantiation: string.c:zend_bitset_equal Unexecuted instantiation: zend_alloc.c:zend_bitset_equal
125
126		static inline void zend_bitset_copy(zend_bitset set1, zend_bitset set2, uint32_t len)
127	0	{
128	0	memcpy(set1, set2, len * ZEND_BITSET_ELM_SIZE);
129	0	} Unexecuted instantiation: array.c:zend_bitset_copy Unexecuted instantiation: string.c:zend_bitset_copy Unexecuted instantiation: zend_alloc.c:zend_bitset_copy
130
131		static inline void zend_bitset_intersection(zend_bitset set1, zend_bitset set2, uint32_t len)
132	0	{
133	0	uint32_t i;
134	0
135	0	for (i = 0; i < len; i++) {
136	0	set1[i] &= set2[i];
137	0	}
138	0	} Unexecuted instantiation: array.c:zend_bitset_intersection Unexecuted instantiation: string.c:zend_bitset_intersection Unexecuted instantiation: zend_alloc.c:zend_bitset_intersection
139
140		static inline void zend_bitset_union(zend_bitset set1, zend_bitset set2, uint32_t len)
141	0	{
142	0	uint32_t i;
143	0
144	0	for (i = 0; i < len; i++) {
145	0	set1[i] \|= set2[i];
146	0	}
147	0	} Unexecuted instantiation: array.c:zend_bitset_union Unexecuted instantiation: string.c:zend_bitset_union Unexecuted instantiation: zend_alloc.c:zend_bitset_union
148
149		static inline void zend_bitset_difference(zend_bitset set1, zend_bitset set2, uint32_t len)
150	0	{
151	0	uint32_t i;
152	0
153	0	for (i = 0; i < len; i++) {
154	0	set1[i] = set1[i] & ~set2[i];
155	0	}
156	0	} Unexecuted instantiation: array.c:zend_bitset_difference Unexecuted instantiation: string.c:zend_bitset_difference Unexecuted instantiation: zend_alloc.c:zend_bitset_difference
157
158		static inline void zend_bitset_union_with_intersection(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
159	0	{
160	0	uint32_t i;
161	0
162	0	for (i = 0; i < len; i++) {
163	0	set1[i] = set2[i] \| (set3[i] & set4[i]);
164	0	}
165	0	} Unexecuted instantiation: array.c:zend_bitset_union_with_intersection Unexecuted instantiation: string.c:zend_bitset_union_with_intersection Unexecuted instantiation: zend_alloc.c:zend_bitset_union_with_intersection
166
167		static inline void zend_bitset_union_with_difference(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
168	0	{
169	0	uint32_t i;
170	0
171	0	for (i = 0; i < len; i++) {
172	0	set1[i] = set2[i] \| (set3[i] & ~set4[i]);
173	0	}
174	0	} Unexecuted instantiation: array.c:zend_bitset_union_with_difference Unexecuted instantiation: string.c:zend_bitset_union_with_difference Unexecuted instantiation: zend_alloc.c:zend_bitset_union_with_difference
175
176		static inline zend_bool zend_bitset_subset(zend_bitset set1, zend_bitset set2, uint32_t len)
177	0	{
178	0	uint32_t i;
179	0
180	0	for (i = 0; i < len; i++) {
181	0	if (set1[i] & ~set2[i]) {
182	0	return 0;
183	0	}
184	0	}
185	0	return 1;
186	0	} Unexecuted instantiation: array.c:zend_bitset_subset Unexecuted instantiation: string.c:zend_bitset_subset Unexecuted instantiation: zend_alloc.c:zend_bitset_subset
187
188		static inline int zend_bitset_first(zend_bitset set, uint32_t len)
189	0	{
190	0	uint32_t i;
191	0
192	0	for (i = 0; i < len; i++) {
193	0	if (set[i]) {
194	0	return ZEND_BITSET_ELM_SIZE * 8 * i + zend_ulong_ntz(set[i]);
195	0	}
196	0	}
197	0	return -1; /* empty set */
198	0	} Unexecuted instantiation: array.c:zend_bitset_first Unexecuted instantiation: string.c:zend_bitset_first Unexecuted instantiation: zend_alloc.c:zend_bitset_first
199
200		static inline int zend_bitset_last(zend_bitset set, uint32_t len)
201	0	{
202	0	uint32_t i = len;
203	0
204	0	while (i > 0) {
205	0	i--;
206	0	if (set[i]) {
207	0	int j = ZEND_BITSET_ELM_SIZE * 8 * i - 1;
208	0	zend_ulong x = set[i];
209	0	while (x != Z_UL(0)) {
210	0	x = x >> Z_UL(1);
211	0	j++;
212	0	}
213	0	return j;
214	0	}
215	0	}
216	0	return -1; /* empty set */
217	0	} Unexecuted instantiation: array.c:zend_bitset_last Unexecuted instantiation: string.c:zend_bitset_last Unexecuted instantiation: zend_alloc.c:zend_bitset_last
218
219		#define ZEND_BITSET_FOREACH(set, len, bit) do { \
220		zend_bitset _set = (set); \
221		uint32_t _i, _len = (len); \
222		for (_i = 0; _i < _len; _i++) { \
223		zend_ulong _x = _set[_i]; \
224		if (_x) { \
225		(bit) = ZEND_BITSET_ELM_SIZE * 8 * _i; \
226		for (; _x != 0; _x >>= Z_UL(1), (bit)++) { \
227		if (!(_x & Z_UL(1))) continue;
228
229		#define ZEND_BITSET_REVERSE_FOREACH(set, len, bit) do { \
230		zend_bitset _set = (set); \
231		uint32_t _i = (len); \
232		zend_ulong _test = Z_UL(1) << (ZEND_BITSET_ELM_SIZE * 8 - 1); \
233		while (_i-- > 0) { \
234		zend_ulong _x = _set[_i]; \
235		if (_x) { \
236		(bit) = ZEND_BITSET_ELM_SIZE * 8 * (_i + 1) - 1; \
237		for (; _x != 0; _x <<= Z_UL(1), (bit)--) { \
238		if (!(_x & _test)) continue; \
239
240		#define ZEND_BITSET_FOREACH_END() \
241		} \
242		} \
243		} \
244		} while (0)
245
246	0	static inline int zend_bitset_pop_first(zend_bitset set, uint32_t len) {
247	0	int i = zend_bitset_first(set, len);
248	0	if (i >= 0) {
249	0	zend_bitset_excl(set, i);
250	0	}
251	0	return i;
252	0	} Unexecuted instantiation: array.c:zend_bitset_pop_first Unexecuted instantiation: string.c:zend_bitset_pop_first Unexecuted instantiation: zend_alloc.c:zend_bitset_pop_first
253
254		#endif /* _ZEND_BITSET_H_ */