#define HOST_UTILS_H 1
#include "qemu/compiler.h" /* QEMU_GNUC_PREREQ */
+#include "qemu/bswap.h"
+#include <limits.h>
+#include <stdbool.h>
-#if defined(__x86_64__)
-#define __HAVE_FAST_MULU64__
+#ifdef CONFIG_INT128
static inline void mulu64(uint64_t *plow, uint64_t *phigh,
uint64_t a, uint64_t b)
{
- __asm__ ("mul %0\n\t"
- : "=d" (*phigh), "=a" (*plow)
- : "a" (a), "0" (b));
+ __uint128_t r = (__uint128_t)a * b;
+ *plow = r;
+ *phigh = r >> 64;
}
-#define __HAVE_FAST_MULS64__
+
static inline void muls64(uint64_t *plow, uint64_t *phigh,
int64_t a, int64_t b)
{
- __asm__ ("imul %0\n\t"
- : "=d" (*phigh), "=a" (*plow)
- : "a" (a), "0" (b));
+ __int128_t r = (__int128_t)a * b;
+ *plow = r;
+ *phigh = r >> 64;
+}
+
+/* compute with 96 bit intermediate result: (a*b)/c */
+static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
+{
+ return (__int128_t)a * b / c;
+}
+
+static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
+{
+ if (divisor == 0) {
+ return 1;
+ } else {
+ __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
+ __uint128_t result = dividend / divisor;
+ *plow = result;
+ *phigh = dividend % divisor;
+ return result > UINT64_MAX;
+ }
+}
+
+static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor)
+{
+ if (divisor == 0) {
+ return 1;
+ } else {
+ __int128_t dividend = ((__int128_t)*phigh << 64) | *plow;
+ __int128_t result = dividend / divisor;
+ *plow = result;
+ *phigh = dividend % divisor;
+ return result != *plow;
+ }
}
#else
void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
+int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
+int divs128(int64_t *plow, int64_t *phigh, int64_t divisor);
+
+static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
+{
+ union {
+ uint64_t ll;
+ struct {
+#ifdef HOST_WORDS_BIGENDIAN
+ uint32_t high, low;
+#else
+ uint32_t low, high;
#endif
+ } l;
+ } u, res;
+ uint64_t rl, rh;
-/* Binary search for leading zeros. */
+ u.ll = a;
+ rl = (uint64_t)u.l.low * (uint64_t)b;
+ rh = (uint64_t)u.l.high * (uint64_t)b;
+ rh += (rl >> 32);
+ res.l.high = rh / c;
+ res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c;
+ return res.ll;
+}
+#endif
+/**
+ * clz32 - count leading zeros in a 32-bit value.
+ * @val: The value to search
+ *
+ * Returns 32 if the value is zero. Note that the GCC builtin is
+ * undefined if the value is zero.
+ */
static inline int clz32(uint32_t val)
{
#if QEMU_GNUC_PREREQ(3, 4)
- if (val)
- return __builtin_clz(val);
- else
- return 32;
+ return val ? __builtin_clz(val) : 32;
#else
+ /* Binary search for the leading one bit. */
int cnt = 0;
if (!(val & 0xFFFF0000U)) {
#endif
}
+/**
+ * clo32 - count leading ones in a 32-bit value.
+ * @val: The value to search
+ *
+ * Returns 32 if the value is -1.
+ */
static inline int clo32(uint32_t val)
{
return clz32(~val);
}
+/**
+ * clz64 - count leading zeros in a 64-bit value.
+ * @val: The value to search
+ *
+ * Returns 64 if the value is zero. Note that the GCC builtin is
+ * undefined if the value is zero.
+ */
static inline int clz64(uint64_t val)
{
#if QEMU_GNUC_PREREQ(3, 4)
- if (val)
- return __builtin_clzll(val);
- else
- return 64;
+ return val ? __builtin_clzll(val) : 64;
#else
int cnt = 0;
#endif
}
+/**
+ * clo64 - count leading ones in a 64-bit value.
+ * @val: The value to search
+ *
+ * Returns 64 if the value is -1.
+ */
static inline int clo64(uint64_t val)
{
return clz64(~val);
}
+/**
+ * ctz32 - count trailing zeros in a 32-bit value.
+ * @val: The value to search
+ *
+ * Returns 32 if the value is zero. Note that the GCC builtin is
+ * undefined if the value is zero.
+ */
static inline int ctz32(uint32_t val)
{
#if QEMU_GNUC_PREREQ(3, 4)
- if (val)
- return __builtin_ctz(val);
- else
- return 32;
+ return val ? __builtin_ctz(val) : 32;
#else
+ /* Binary search for the trailing one bit. */
int cnt;
cnt = 0;
#endif
}
+/**
+ * cto32 - count trailing ones in a 32-bit value.
+ * @val: The value to search
+ *
+ * Returns 32 if the value is -1.
+ */
static inline int cto32(uint32_t val)
{
return ctz32(~val);
}
+/**
+ * ctz64 - count trailing zeros in a 64-bit value.
+ * @val: The value to search
+ *
+ * Returns 64 if the value is zero. Note that the GCC builtin is
+ * undefined if the value is zero.
+ */
static inline int ctz64(uint64_t val)
{
#if QEMU_GNUC_PREREQ(3, 4)
- if (val)
- return __builtin_ctzll(val);
- else
- return 64;
+ return val ? __builtin_ctzll(val) : 64;
#else
int cnt;
#endif
}
+/**
+ * cto64 - count trailing ones in a 64-bit value.
+ * @val: The value to search
+ *
+ * Returns 64 if the value is -1.
+ */
static inline int cto64(uint64_t val)
{
return ctz64(~val);
}
+/**
+ * clrsb32 - count leading redundant sign bits in a 32-bit value.
+ * @val: The value to search
+ *
+ * Returns the number of bits following the sign bit that are equal to it.
+ * No special cases; output range is [0-31].
+ */
+static inline int clrsb32(uint32_t val)
+{
+#if QEMU_GNUC_PREREQ(4, 7)
+ return __builtin_clrsb(val);
+#else
+ return clz32(val ^ ((int32_t)val >> 1)) - 1;
+#endif
+}
+
+/**
+ * clrsb64 - count leading redundant sign bits in a 64-bit value.
+ * @val: The value to search
+ *
+ * Returns the number of bits following the sign bit that are equal to it.
+ * No special cases; output range is [0-63].
+ */
+static inline int clrsb64(uint64_t val)
+{
+#if QEMU_GNUC_PREREQ(4, 7)
+ return __builtin_clrsbll(val);
+#else
+ return clz64(val ^ ((int64_t)val >> 1)) - 1;
+#endif
+}
+
+/**
+ * ctpop8 - count the population of one bits in an 8-bit value.
+ * @val: The value to search
+ */
static inline int ctpop8(uint8_t val)
{
+#if QEMU_GNUC_PREREQ(3, 4)
+ return __builtin_popcount(val);
+#else
val = (val & 0x55) + ((val >> 1) & 0x55);
val = (val & 0x33) + ((val >> 2) & 0x33);
val = (val & 0x0f) + ((val >> 4) & 0x0f);
return val;
+#endif
}
+/**
+ * ctpop16 - count the population of one bits in a 16-bit value.
+ * @val: The value to search
+ */
static inline int ctpop16(uint16_t val)
{
+#if QEMU_GNUC_PREREQ(3, 4)
+ return __builtin_popcount(val);
+#else
val = (val & 0x5555) + ((val >> 1) & 0x5555);
val = (val & 0x3333) + ((val >> 2) & 0x3333);
val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f);
val = (val & 0x00ff) + ((val >> 8) & 0x00ff);
return val;
+#endif
}
+/**
+ * ctpop32 - count the population of one bits in a 32-bit value.
+ * @val: The value to search
+ */
static inline int ctpop32(uint32_t val)
{
#if QEMU_GNUC_PREREQ(3, 4)
#endif
}
+/**
+ * ctpop64 - count the population of one bits in a 64-bit value.
+ * @val: The value to search
+ */
static inline int ctpop64(uint64_t val)
{
#if QEMU_GNUC_PREREQ(3, 4)
#endif
}
+/**
+ * revbit8 - reverse the bits in an 8-bit value.
+ * @x: The value to modify.
+ */
+static inline uint8_t revbit8(uint8_t x)
+{
+ /* Assign the correct nibble position. */
+ x = ((x & 0xf0) >> 4)
+ | ((x & 0x0f) << 4);
+ /* Assign the correct bit position. */
+ x = ((x & 0x88) >> 3)
+ | ((x & 0x44) >> 1)
+ | ((x & 0x22) << 1)
+ | ((x & 0x11) << 3);
+ return x;
+}
+
+/**
+ * revbit16 - reverse the bits in a 16-bit value.
+ * @x: The value to modify.
+ */
+static inline uint16_t revbit16(uint16_t x)
+{
+ /* Assign the correct byte position. */
+ x = bswap16(x);
+ /* Assign the correct nibble position. */
+ x = ((x & 0xf0f0) >> 4)
+ | ((x & 0x0f0f) << 4);
+ /* Assign the correct bit position. */
+ x = ((x & 0x8888) >> 3)
+ | ((x & 0x4444) >> 1)
+ | ((x & 0x2222) << 1)
+ | ((x & 0x1111) << 3);
+ return x;
+}
+
+/**
+ * revbit32 - reverse the bits in a 32-bit value.
+ * @x: The value to modify.
+ */
+static inline uint32_t revbit32(uint32_t x)
+{
+ /* Assign the correct byte position. */
+ x = bswap32(x);
+ /* Assign the correct nibble position. */
+ x = ((x & 0xf0f0f0f0u) >> 4)
+ | ((x & 0x0f0f0f0fu) << 4);
+ /* Assign the correct bit position. */
+ x = ((x & 0x88888888u) >> 3)
+ | ((x & 0x44444444u) >> 1)
+ | ((x & 0x22222222u) << 1)
+ | ((x & 0x11111111u) << 3);
+ return x;
+}
+
+/**
+ * revbit64 - reverse the bits in a 64-bit value.
+ * @x: The value to modify.
+ */
+static inline uint64_t revbit64(uint64_t x)
+{
+ /* Assign the correct byte position. */
+ x = bswap64(x);
+ /* Assign the correct nibble position. */
+ x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
+ | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
+ /* Assign the correct bit position. */
+ x = ((x & 0x8888888888888888ull) >> 3)
+ | ((x & 0x4444444444444444ull) >> 1)
+ | ((x & 0x2222222222222222ull) << 1)
+ | ((x & 0x1111111111111111ull) << 3);
+ return x;
+}
+
+/* Host type specific sizes of these routines. */
+
+#if ULONG_MAX == UINT32_MAX
+# define clzl clz32
+# define ctzl ctz32
+# define clol clo32
+# define ctol cto32
+# define ctpopl ctpop32
+# define revbitl revbit32
+#elif ULONG_MAX == UINT64_MAX
+# define clzl clz64
+# define ctzl ctz64
+# define clol clo64
+# define ctol cto64
+# define ctpopl ctpop64
+# define revbitl revbit64
+#else
+# error Unknown sizeof long
+#endif
+
+static inline bool is_power_of_2(uint64_t value)
+{
+ if (!value) {
+ return 0;
+ }
+
+ return !(value & (value - 1));
+}
+
+/* round down to the nearest power of 2*/
+static inline int64_t pow2floor(int64_t value)
+{
+ if (!is_power_of_2(value)) {
+ value = 0x8000000000000000ULL >> clz64(value);
+ }
+ return value;
+}
+
+/* round up to the nearest power of 2 (0 if overflow) */
+static inline uint64_t pow2ceil(uint64_t value)
+{
+ uint8_t nlz = clz64(value);
+
+ if (is_power_of_2(value)) {
+ return value;
+ }
+ if (!nlz) {
+ return 0;
+ }
+ return 1ULL << (64 - nlz);
+}
+
#endif
projects / qemu.git / blobdiff