text: /*
     +----------------------------------------------------------------------+
     | 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
  }
  
  /* Number of leading zero bits (Undefined for zero) */
  static zend_always_inline int zend_ulong_nlz(zend_ulong num)
  {
  #if (defined(__GNUC__) || __has_builtin(__builtin_clzl)) \
  	&& SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CLZL)
  	return __builtin_clzl(num);
  #elif (defined(__GNUC__) || __has_builtin(__builtin_clzll)) && defined(PHP_HAVE_BUILTIN_CLZLL)
  	return __builtin_clzll(num);
  #elif defined(_WIN32)
  	unsigned long index;
  
  #if defined(_WIN64)
  	if (!BitScanReverse64(&index, num)) {
  #else
  	if (!BitScanReverse(&index, num)) {
  #endif
  		/* undefined behavior */
  		return SIZEOF_ZEND_LONG * 8;
  	}
  
  	return (int) (SIZEOF_ZEND_LONG * 8 - 1)- index;
  #else
  	zend_ulong x;
  	int n;
  
  #if SIZEOF_ZEND_LONG == 8
  	n = 64;
  	x = num >> 32; if (x != 0) {n -= 32; num = x;}
  #else
  	n = 32;
  #endif
  	x = num >> 16; if (x != 0) {n -= 16; num = x;}
  	x = num >> 8;  if (x != 0) {n -=  8; num = x;}
  	x = num >> 4;  if (x != 0) {n -=  4; num = x;}
  	x = num >> 2;  if (x != 0) {n -=  2; num = x;}
  	x = num >> 1;  if (x != 0) return n - 2;
  	return n - num;
  #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 bool 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_ */
  