* THE SOFTWARE.
*/
-#include <stdlib.h>
-#include <stdint.h>
+#include "qemu/osdep.h"
#include "qemu/host-utils.h"
-//#define DEBUG_MULDIV
-
+#ifndef CONFIG_INT128
/* Long integer helpers */
-#if !defined(__x86_64__)
-static void add128 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b)
+static inline void mul64(uint64_t *plow, uint64_t *phigh,
+ uint64_t a, uint64_t b)
{
- *plow += a;
- /* carry test */
- if (*plow < a)
- (*phigh)++;
- *phigh += b;
+ typedef union {
+ uint64_t ll;
+ struct {
+#ifdef HOST_WORDS_BIGENDIAN
+ uint32_t high, low;
+#else
+ uint32_t low, high;
+#endif
+ } l;
+ } LL;
+ LL rl, rm, rn, rh, a0, b0;
+ uint64_t c;
+
+ a0.ll = a;
+ b0.ll = b;
+
+ rl.ll = (uint64_t)a0.l.low * b0.l.low;
+ rm.ll = (uint64_t)a0.l.low * b0.l.high;
+ rn.ll = (uint64_t)a0.l.high * b0.l.low;
+ rh.ll = (uint64_t)a0.l.high * b0.l.high;
+
+ c = (uint64_t)rl.l.high + rm.l.low + rn.l.low;
+ rl.l.high = c;
+ c >>= 32;
+ c = c + rm.l.high + rn.l.high + rh.l.low;
+ rh.l.low = c;
+ rh.l.high += (uint32_t)(c >> 32);
+
+ *plow = rl.ll;
+ *phigh = rh.ll;
}
-static void neg128 (uint64_t *plow, uint64_t *phigh)
+/* Unsigned 64x64 -> 128 multiplication */
+void mulu64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b)
{
- *plow = ~*plow;
- *phigh = ~*phigh;
- add128(plow, phigh, 1, 0);
+ mul64(plow, phigh, a, b);
}
-static void mul64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b)
+/* Signed 64x64 -> 128 multiplication */
+void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b)
{
- uint32_t a0, a1, b0, b1;
- uint64_t v;
+ uint64_t rh;
- a0 = a;
- a1 = a >> 32;
+ mul64(plow, &rh, a, b);
- b0 = b;
- b1 = b >> 32;
+ /* Adjust for signs. */
+ if (b < 0) {
+ rh -= a;
+ }
+ if (a < 0) {
+ rh -= b;
+ }
+ *phigh = rh;
+}
- v = (uint64_t)a0 * (uint64_t)b0;
- *plow = v;
- *phigh = 0;
+/* Unsigned 128x64 division. Returns 1 if overflow (divide by zero or */
+/* quotient exceeds 64 bits). Otherwise returns quotient via plow and */
+/* remainder via phigh. */
+int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
+{
+ uint64_t dhi = *phigh;
+ uint64_t dlo = *plow;
+ unsigned i;
+ uint64_t carry = 0;
- v = (uint64_t)a0 * (uint64_t)b1;
- add128(plow, phigh, v << 32, v >> 32);
+ if (divisor == 0) {
+ return 1;
+ } else if (dhi == 0) {
+ *plow = dlo / divisor;
+ *phigh = dlo % divisor;
+ return 0;
+ } else if (dhi > divisor) {
+ return 1;
+ } else {
- v = (uint64_t)a1 * (uint64_t)b0;
- add128(plow, phigh, v << 32, v >> 32);
+ for (i = 0; i < 64; i++) {
+ carry = dhi >> 63;
+ dhi = (dhi << 1) | (dlo >> 63);
+ if (carry || (dhi >= divisor)) {
+ dhi -= divisor;
+ carry = 1;
+ } else {
+ carry = 0;
+ }
+ dlo = (dlo << 1) | carry;
+ }
- v = (uint64_t)a1 * (uint64_t)b1;
- *phigh += v;
+ *plow = dlo;
+ *phigh = dhi;
+ return 0;
+ }
}
-/* Unsigned 64x64 -> 128 multiplication */
-void mulu64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b)
+int divs128(int64_t *plow, int64_t *phigh, int64_t divisor)
{
- mul64(plow, phigh, a, b);
-#if defined(DEBUG_MULDIV)
- printf("mulu64: 0x%016llx * 0x%016llx = 0x%016llx%016llx\n",
- a, b, *phigh, *plow);
+ int sgn_dvdnd = *phigh < 0;
+ int sgn_divsr = divisor < 0;
+ int overflow = 0;
+
+ if (sgn_dvdnd) {
+ *plow = ~(*plow);
+ *phigh = ~(*phigh);
+ if (*plow == (int64_t)-1) {
+ *plow = 0;
+ (*phigh)++;
+ } else {
+ (*plow)++;
+ }
+ }
+
+ if (sgn_divsr) {
+ divisor = 0 - divisor;
+ }
+
+ overflow = divu128((uint64_t *)plow, (uint64_t *)phigh, (uint64_t)divisor);
+
+ if (sgn_dvdnd ^ sgn_divsr) {
+ *plow = 0 - *plow;
+ }
+
+ if (!overflow) {
+ if ((*plow < 0) ^ (sgn_dvdnd ^ sgn_divsr)) {
+ overflow = 1;
+ }
+ }
+
+ return overflow;
+}
#endif
+
+/**
+ * urshift - 128-bit Unsigned Right Shift.
+ * @plow: in/out - lower 64-bit integer.
+ * @phigh: in/out - higher 64-bit integer.
+ * @shift: in - bytes to shift, between 0 and 127.
+ *
+ * Result is zero-extended and stored in plow/phigh, which are
+ * input/output variables. Shift values outside the range will
+ * be mod to 128. In other words, the caller is responsible to
+ * verify/assert both the shift range and plow/phigh pointers.
+ */
+void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift)
+{
+ shift &= 127;
+ if (shift == 0) {
+ return;
+ }
+
+ uint64_t h = *phigh >> (shift & 63);
+ if (shift >= 64) {
+ *plow = h;
+ *phigh = 0;
+ } else {
+ *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63)));
+ *phigh = h;
+ }
}
-/* Signed 64x64 -> 128 multiplication */
-void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b)
+/**
+ * ulshift - 128-bit Unsigned Left Shift.
+ * @plow: in/out - lower 64-bit integer.
+ * @phigh: in/out - higher 64-bit integer.
+ * @shift: in - bytes to shift, between 0 and 127.
+ * @overflow: out - true if any 1-bit is shifted out.
+ *
+ * Result is zero-extended and stored in plow/phigh, which are
+ * input/output variables. Shift values outside the range will
+ * be mod to 128. In other words, the caller is responsible to
+ * verify/assert both the shift range and plow/phigh pointers.
+ */
+void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow)
{
- int sa, sb;
-
- sa = (a < 0);
- if (sa)
- a = -a;
- sb = (b < 0);
- if (sb)
- b = -b;
- mul64(plow, phigh, a, b);
- if (sa ^ sb) {
- neg128(plow, phigh);
+ uint64_t low = *plow;
+ uint64_t high = *phigh;
+
+ shift &= 127;
+ if (shift == 0) {
+ return;
+ }
+
+ /* check if any bit will be shifted out */
+ urshift(&low, &high, 128 - shift);
+ if (low | high) {
+ *overflow = true;
+ }
+
+ if (shift >= 64) {
+ *phigh = *plow << (shift & 63);
+ *plow = 0;
+ } else {
+ *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63));
+ *plow = *plow << shift;
}
-#if defined(DEBUG_MULDIV)
- printf("muls64: 0x%016llx * 0x%016llx = 0x%016llx%016llx\n",
- a, b, *phigh, *plow);
-#endif
}
-#endif /* !defined(__x86_64__) */
projects / mirror_qemu.git / blobdiff