[PATCH v3 07/13] x86: Add functions for 64-bit integer arithmetic

[Haozhong Zhang <haozhong.zhang@intel.com>]

This patch adds several functions to take multiplication, division and
shifting involving 64-bit integers. Those functions are derived from
Linux kernel and will be used by later patches to calculate scaling
ratio and scaled TSC.

Signed-off-by: Haozhong Zhang <haozhong.zhang@intel.com>
---
Changes in v3:
 (addressing Boris Ostrovsky's comments in v2 patch 9 & 10)
 * Move all math64 stuffs to this standalone patch.
 * Add comments to state these functions are derived from Linux kernel.

 xen/include/asm-x86/math64.h | 105 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 105 insertions(+)
 create mode 100644 xen/include/asm-x86/math64.h

diff --git a/xen/include/asm-x86/math64.h b/xen/include/asm-x86/math64.h
new file mode 100644
index 0000000..f7624ef
--- /dev/null
+++ b/xen/include/asm-x86/math64.h
@@ -0,0 +1,105 @@
+#ifndef __X86_MATH64
+#define __X86_MATH64
+
+/*
+ * Functions defined in this file are derived from Linux kernel
+ * (include/linux/math64.h).
+ */
+
+/*
+ * (a * mul) / divisor
+ */
+static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 divisor)
+{
+    union {
+        u64 ll;
+        struct {
+            u32 low, high;
+        } l;
+    } u, rl, rh;
+
+    u.ll = a;
+    rl.ll = (u64)u.l.low * mul;
+    rh.ll = (u64)u.l.high * mul + rl.l.high;
+
+    /* Bits 32-63 of the result will be in rh.l.low. */
+    rl.l.high = do_div(rh.ll, divisor);
+
+    /* Bits 0-31 of the result will be in rl.l.low. */
+    do_div(rl.ll, divisor);
+
+    rl.l.high = rh.l.low;
+    return rl.ll;
+}
+
+/*
+ * Multiply two 64-bit unsigned integers a and b. The most and least
+ * significant 64 bits of the 128-bit result are returned through hi
+ * and lo respectively.
+ */
+static inline void mul64(u64 *lo, u64 *hi, u64 a, u64 b)
+{
+    typedef union {
+        u64 ll;
+        struct {
+            u32 low, high;
+        } l;
+    } LL;
+    LL rl, rm, rn, rh, a0, b0;
+    u64 c;
+
+    a0.ll = a;
+    b0.ll = b;
+
+    rl.ll = (u64)a0.l.low * b0.l.low;
+    rm.ll = (u64)a0.l.low * b0.l.high;
+    rn.ll = (u64)a0.l.high * b0.l.low;
+    rh.ll = (u64)a0.l.high * b0.l.high;
+
+    c = (u64)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 += (u32)(c >> 32);
+
+    *lo = rl.ll;
+    *hi = rh.ll;
+}
+
+/*
+ * Right shift a 128-bit unsigned integer by n bits. The most and
+ * least significant 64 bits of the 128-bit integer are passed through
+ * hi and lo respectively. The most and least significant 64 bits of
+ * the result are also returned through hi and lo respectively.
+ */
+static inline void rshift128(u64 *lo, u64 *hi, unsigned int n)
+{
+    u64 h;
+    if ( !n )
+        return;
+    h = *hi >> (n & 63);
+    if ( n >= 64 )
+    {
+        *hi = 0;
+        *lo = h;
+    }
+    else
+    {
+        *lo = (*lo >> n) | (*hi << (64 - n));
+        *hi = h;
+    }
+}
+
+/*
+ * (a * mul) >> n
+ */
+static inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int n)
+{
+    u64 lo, hi;
+    mul64(&lo, &hi, a, mul);
+    rshift128(&lo, &hi, n);
+    return lo;
+}
+
+#endif
-- 
2.4.8