#include <assert.h>
#include <stdint.h>
+#include <stdbool.h>
#include <string.h>
#if defined(_MSC_VER)
#include <intrin.h>
#endif
+#if defined(__POPCNT__)
+#include <popcntintrin.h>
+#endif
+
#include "c99_compat.h"
#ifdef __cplusplus
#define ffs __builtin_ffs
#elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64)
static inline
-int ffs(unsigned i)
+int ffs(int i)
{
unsigned long index;
if (_BitScanForward(&index, i))
}
#else
extern
-int ffs(unsigned i);
+int ffs(int i);
#endif
#ifdef HAVE___BUILTIN_FFSLL
#define ffsll __builtin_ffsll
-#elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
+#elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM64 || _M_IA64)
static inline int
-ffsll(uint64_t i)
+ffsll(long long int i)
{
unsigned long index;
if (_BitScanForward64(&index, i))
}
#else
extern int
-ffsll(uint64_t val);
+ffsll(long long int val);
#endif
return i;
}
+/* Determine if an unsigned value is a power of two.
+ *
+ * \note
+ * Zero is treated as a power of two.
+ */
+static inline bool
+util_is_power_of_two_or_zero(unsigned v)
+{
+ return (v & (v - 1)) == 0;
+}
+
+/* Determine if an uint64_t value is a power of two.
+ *
+ * \note
+ * Zero is treated as a power of two.
+ */
+static inline bool
+util_is_power_of_two_or_zero64(uint64_t v)
+{
+ return (v & (v - 1)) == 0;
+}
+
+/* Determine if an unsigned value is a power of two.
+ *
+ * \note
+ * Zero is \b not treated as a power of two.
+ */
+static inline bool
+util_is_power_of_two_nonzero(unsigned v)
+{
+ /* __POPCNT__ is different from HAVE___BUILTIN_POPCOUNT. The latter
+ * indicates the existence of the __builtin_popcount function. The former
+ * indicates that _mm_popcnt_u32 exists and is a native instruction.
+ *
+ * The other alternative is to use SSE 4.2 compile-time flags. This has
+ * two drawbacks. First, there is currently no build infrastructure for
+ * SSE 4.2 (only 4.1), so that would have to be added. Second, some AMD
+ * CPUs support POPCNT but not SSE 4.2 (e.g., Barcelona).
+ */
+#ifdef __POPCNT__
+ return _mm_popcnt_u32(v) == 1;
+#else
+ return v != 0 && (v & (v - 1)) == 0;
+#endif
+}
+
/* For looping over a bitmask when you want to loop over consecutive bits
* manually, for example:
*
static inline void
u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count)
{
- if (*mask == ~0llu) {
+ if (*mask == ~0ull) {
*start = 0;
*count = 64;
*mask = 0;
{
#if defined(HAVE___BUILTIN_CLZLL)
return u == 0 ? 0 : 64 - __builtin_clzll(u);
-#elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
+#elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM64 || _M_IA64)
unsigned long index;
if (_BitScanReverse64(&index, u))
return index + 1;
return ((1u << count) - 1) << start;
}
+static inline uint64_t
+u_bit_consecutive64(unsigned start, unsigned count)
+{
+ assert(start + count <= 64);
+ if (count == 64)
+ return ~(uint64_t)0;
+ return (((uint64_t)1 << count) - 1) << start;
+}
+
+/**
+ * Return number of bits set in n.
+ */
+static inline unsigned
+util_bitcount(unsigned n)
+{
+#if defined(HAVE___BUILTIN_POPCOUNT)
+ return __builtin_popcount(n);
+#else
+ /* K&R classic bitcount.
+ *
+ * For each iteration, clear the LSB from the bitfield.
+ * Requires only one iteration per set bit, instead of
+ * one iteration per bit less than highest set bit.
+ */
+ unsigned bits;
+ for (bits = 0; n; bits++) {
+ n &= n - 1;
+ }
+ return bits;
+#endif
+}
+
+static inline unsigned
+util_bitcount64(uint64_t n)
+{
+#ifdef HAVE___BUILTIN_POPCOUNTLL
+ return __builtin_popcountll(n);
+#else
+ return util_bitcount(n) + util_bitcount(n >> 32);
+#endif
+}
#ifdef __cplusplus
}