Import libcompiler_rt into HEAD and add Makefiles.

Obtained from:	user/ed/compiler-rt

1 files changed, 256 insertions, 0 deletions

diff --git a/contrib/compiler-rt/lib/udivmodti4.c b/contrib/compiler-rt/lib/udivmodti4.c
new file mode 100644
index 0000000..53b4072
--- /dev/null
+++ b/contrib/compiler-rt/lib/udivmodti4.c
@@ -0,0 +1,256 @@
+/* ===-- udivmodti4.c - Implement __udivmodti4 -----------------------------===
+ *
+ *                    The LLVM Compiler Infrastructure
+ *
+ * This file is distributed under the University of Illinois Open Source
+ * License. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements __udivmodti4 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */ 
+
+#if __x86_64
+
+#include "int_lib.h"
+
+/* Effects: if rem != 0, *rem = a % b 
+ * Returns: a / b 
+ */
+
+/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
+
+tu_int
+__udivmodti4(tu_int a, tu_int b, tu_int* rem)
+{
+    const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
+    const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT;
+    utwords n;
+    n.all = a;
+    utwords d;
+    d.all = b;
+    utwords q;
+    utwords r;
+    unsigned sr;
+    /* special cases, X is unknown, K != 0 */
+    if (n.s.high == 0)
+    {
+        if (d.s.high == 0)
+        {
+            /* 0 X
+             * ---
+             * 0 X
+             */
+            if (rem)
+                *rem = n.s.low % d.s.low;
+            return n.s.low / d.s.low;
+        }
+        /* 0 X
+         * ---
+         * K X
+         */
+        if (rem)
+            *rem = n.s.low;
+        return 0;
+    }
+    /* n.s.high != 0 */
+    if (d.s.low == 0)
+    {
+        if (d.s.high == 0)
+        {
+            /* K X
+             * ---
+             * 0 0
+             */
+            if (rem)
+                *rem = n.s.high % d.s.low;
+            return n.s.high / d.s.low;
+        }
+        /* d.s.high != 0 */
+        if (n.s.low == 0)
+        {
+            /* K 0
+             * ---
+             * K 0
+             */
+            if (rem)
+            {
+                r.s.high = n.s.high % d.s.high;
+                r.s.low = 0;
+                *rem = r.all;
+            }
+            return n.s.high / d.s.high;
+        }
+        /* K K
+         * ---
+         * K 0
+         */
+        if ((d.s.high & (d.s.high - 1)) == 0)     /* if d is a power of 2 */
+        {
+            if (rem)
+            {
+                r.s.low = n.s.low;
+                r.s.high = n.s.high & (d.s.high - 1);
+                *rem = r.all;
+            }
+            return n.s.high >> __builtin_ctzll(d.s.high);
+        }
+        /* K K
+         * ---
+         * K 0
+         */
+        sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
+        /* 0 <= sr <= n_udword_bits - 2 or sr large */
+        if (sr > n_udword_bits - 2)
+        {
+           if (rem)
+                *rem = n.all;
+            return 0;
+        }
+        ++sr;
+        /* 1 <= sr <= n_udword_bits - 1 */
+        /* q.all = n.all << (n_utword_bits - sr); */
+        q.s.low = 0;
+        q.s.high = n.s.low << (n_udword_bits - sr);
+        /* r.all = n.all >> sr; */
+        r.s.high = n.s.high >> sr;
+        r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
+    }
+    else  /* d.s.low != 0 */
+    {
+        if (d.s.high == 0)
+        {
+            /* K X
+             * ---
+             * 0 K
+             */
+            if ((d.s.low & (d.s.low - 1)) == 0)     /* if d is a power of 2 */
+            {
+                if (rem)
+                    *rem = n.s.low & (d.s.low - 1);
+                if (d.s.low == 1)
+                    return n.all;
+                unsigned sr = __builtin_ctzll(d.s.low);
+                q.s.high = n.s.high >> sr;
+                q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
+                return q.all;
+            }
+            /* K X
+             * ---
+             * 0 K
+             */
+            sr = 1 + n_udword_bits + __builtin_clzll(d.s.low)
+                                   - __builtin_clzll(n.s.high);
+            /* 2 <= sr <= n_utword_bits - 1
+             * q.all = n.all << (n_utword_bits - sr);
+             * r.all = n.all >> sr;
+             * if (sr == n_udword_bits)
+             * {
+             *     q.s.low = 0;
+             *     q.s.high = n.s.low;
+             *     r.s.high = 0;
+             *     r.s.low = n.s.high;
+             * }
+             * else if (sr < n_udword_bits)  // 2 <= sr <= n_udword_bits - 1
+             * {
+             *     q.s.low = 0;
+             *     q.s.high = n.s.low << (n_udword_bits - sr);
+             *     r.s.high = n.s.high >> sr;
+             *     r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
+             * }
+             * else              // n_udword_bits + 1 <= sr <= n_utword_bits - 1
+             * {
+             *     q.s.low = n.s.low << (n_utword_bits - sr);
+             *     q.s.high = (n.s.high << (n_utword_bits - sr)) |
+             *              (n.s.low >> (sr - n_udword_bits));
+             *     r.s.high = 0;
+             *     r.s.low = n.s.high >> (sr - n_udword_bits);
+             * }
+             */
+            q.s.low =  (n.s.low << (n_utword_bits - sr)) &
+                     ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1));
+            q.s.high = ((n.s.low << ( n_udword_bits - sr))                        &
+                     ((di_int)(int)(sr - n_udword_bits - 1) >> (n_udword_bits-1))) |
+                     (((n.s.high << (n_utword_bits - sr))                       |
+                     (n.s.low >> (sr - n_udword_bits)))                         &
+                     ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1)));
+            r.s.high = (n.s.high >> sr) &
+                     ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1));
+            r.s.low =  ((n.s.high >> (sr - n_udword_bits))                        &
+                     ((di_int)(int)(n_udword_bits - sr - 1) >> (n_udword_bits-1))) |
+                     (((n.s.high << (n_udword_bits - sr))                       |
+                     (n.s.low >> sr))                                           &
+                     ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)));
+        }
+        else
+        {
+            /* K X
+             * ---
+             * K K
+             */
+            sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
+            /*0 <= sr <= n_udword_bits - 1 or sr large */
+            if (sr > n_udword_bits - 1)
+            {
+               if (rem)
+                    *rem = n.all;
+                return 0;
+            }
+            ++sr;
+            /* 1 <= sr <= n_udword_bits */
+            /* q.all = n.all << (n_utword_bits - sr); */
+            q.s.low = 0;
+            q.s.high = n.s.low << (n_udword_bits - sr);
+            /* r.all = n.all >> sr;
+             * if (sr < n_udword_bits)
+             * {
+             *     r.s.high = n.s.high >> sr;
+             *     r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
+             * }
+             * else
+             * {
+             *     r.s.high = 0;
+             *     r.s.low = n.s.high;
+             * }
+             */
+            r.s.high = (n.s.high >> sr) &
+                     ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1));
+            r.s.low = (n.s.high << (n_udword_bits - sr)) |
+                    ((n.s.low >> sr)                   &
+                    ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)));
+        }
+    }
+    /* Not a special case
+     * q and r are initialized with:
+     * q.all = n.all << (n_utword_bits - sr);
+     * r.all = n.all >> sr;
+     * 1 <= sr <= n_utword_bits - 1
+     */
+    su_int carry = 0;
+    for (; sr > 0; --sr)
+    {
+        /* r:q = ((r:q)  << 1) | carry */
+        r.s.high = (r.s.high << 1) | (r.s.low  >> (n_udword_bits - 1));
+        r.s.low  = (r.s.low  << 1) | (q.s.high >> (n_udword_bits - 1));
+        q.s.high = (q.s.high << 1) | (q.s.low  >> (n_udword_bits - 1));
+        q.s.low  = (q.s.low  << 1) | carry;
+        /* carry = 0;
+         * if (r.all >= d.all)
+         * {
+         *     r.all -= d.all;
+         *      carry = 1;
+         * }
+         */
+        const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_bits - 1);
+        carry = s & 1;
+        r.all -= d.all & s;
+    }
+    q.all = (q.all << 1) | carry;
+    if (rem)
+        *rem = r.all;
+    return q.all;
+}
+
+#endif /* __x86_64 */