add compiler-rt files for 64-bit math

11 files changed, 874 insertions, 0 deletions

diff --git a/system/lib/compiler-rt/LICENSE.TXT b/system/lib/compiler-rt/LICENSE.TXT
new file mode 100644
index 00000000..6aab1f69
--- /dev/null
+++ b/system/lib/compiler-rt/LICENSE.TXT
@@ -0,0 +1,97 @@
+==============================================================================
+compiler_rt License
+==============================================================================
+
+The compiler_rt library is dual licensed under both the University of Illinois
+"BSD-Like" license and the MIT license.  As a user of this code you may choose
+to use it under either license.  As a contributor, you agree to allow your code
+to be used under both.
+
+Full text of the relevant licenses is included below.
+
+==============================================================================
+
+University of Illinois/NCSA
+Open Source License
+
+Copyright (c) 2009-2013 by the contributors listed in CREDITS.TXT
+
+All rights reserved.
+
+Developed by:
+
+    LLVM Team
+
+    University of Illinois at Urbana-Champaign
+
+    http://llvm.org
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal with
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+of the Software, and to permit persons to whom the Software is furnished to do
+so, subject to the following conditions:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimers.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimers in the
+      documentation and/or other materials provided with the distribution.
+
+    * Neither the names of the LLVM Team, University of Illinois at
+      Urbana-Champaign, nor the names of its contributors may be used to
+      endorse or promote products derived from this Software without specific
+      prior written permission.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
+SOFTWARE.
+
+==============================================================================
+
+Copyright (c) 2009-2013 by the contributors listed in CREDITS.TXT
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+
+==============================================================================
+Copyrights and Licenses for Third Party Software Distributed with LLVM:
+==============================================================================
+The LLVM software contains code written by third parties.  Such software will
+have its own individual LICENSE.TXT file in the directory in which it appears.
+This file will describe the copyrights, license, and restrictions which apply
+to that code.
+
+The disclaimer of warranty in the University of Illinois Open Source License
+applies to all code in the LLVM Distribution, and nothing in any of the
+other licenses gives permission to use the names of the LLVM Team or the
+University of Illinois to endorse or promote products derived from this
+Software.
+
+The following pieces of software have additional or alternate copyrights,
+licenses, and/or restrictions:
+
+Program             Directory
+-------             ---------
+mach_override       lib/interception/mach_override
diff --git a/system/lib/compiler-rt/divdi3.c b/system/lib/compiler-rt/divdi3.c
new file mode 100644
index 00000000..2c2bcc26
--- /dev/null
+++ b/system/lib/compiler-rt/divdi3.c
@@ -0,0 +1,31 @@
+/* ===-- divdi3.c - Implement __divdi3 -------------------------------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements __divdi3 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include "int_lib.h"
+
+du_int COMPILER_RT_ABI __udivmoddi4(du_int a, du_int b, du_int* rem);
+
+/* Returns: a / b */
+
+COMPILER_RT_ABI di_int
+__divdi3(di_int a, di_int b)
+{
+    const int bits_in_dword_m1 = (int)(sizeof(di_int) * CHAR_BIT) - 1;
+    di_int s_a = a >> bits_in_dword_m1;           /* s_a = a < 0 ? -1 : 0 */
+    di_int s_b = b >> bits_in_dword_m1;           /* s_b = b < 0 ? -1 : 0 */
+    a = (a ^ s_a) - s_a;                         /* negate if s_a == -1 */
+    b = (b ^ s_b) - s_b;                         /* negate if s_b == -1 */
+    s_a ^= s_b;                                  /*sign of quotient */
+    return (__udivmoddi4(a, b, (du_int*)0) ^ s_a) - s_a;  /* negate if s_a == -1 */
+}
diff --git a/system/lib/compiler-rt/int_endianness.h b/system/lib/compiler-rt/int_endianness.h
new file mode 100644
index 00000000..17905355
--- /dev/null
+++ b/system/lib/compiler-rt/int_endianness.h
@@ -0,0 +1,116 @@
+/* ===-- int_endianness.h - configuration header for compiler-rt ------------===
+ *
+ *		       The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file is a configuration header for compiler-rt.
+ * This file is not part of the interface of this library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#ifndef INT_ENDIANNESS_H
+#define INT_ENDIANNESS_H
+
+#if defined(__SVR4) && defined(__sun)
+#include <sys/byteorder.h>
+
+#if _BYTE_ORDER == _BIG_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 0
+#define _YUGA_BIG_ENDIAN    1
+#elif _BYTE_ORDER == _LITTLE_ENDIAN 
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+#endif /* _BYTE_ORDER */
+
+#endif /* Solaris and AuroraUX. */
+
+/* .. */
+
+#if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__DragonFly__) || defined(__minix)
+#include <sys/endian.h>
+
+#if _BYTE_ORDER == _BIG_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 0
+#define _YUGA_BIG_ENDIAN    1
+#elif _BYTE_ORDER == _LITTLE_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+#endif /* _BYTE_ORDER */
+
+#endif /* *BSD */
+
+#if defined(__OpenBSD__) || defined(__Bitrig__)
+#include <machine/endian.h>
+
+#if _BYTE_ORDER == _BIG_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 0
+#define _YUGA_BIG_ENDIAN    1
+#elif _BYTE_ORDER == _LITTLE_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+#endif /* _BYTE_ORDER */
+
+#endif /* OpenBSD and Bitrig. */
+
+/* .. */
+
+/* Mac OSX has __BIG_ENDIAN__ or __LITTLE_ENDIAN__ automatically set by the compiler (at least with GCC) */
+#if defined(__APPLE__) && defined(__MACH__) || defined(__ellcc__ )
+
+#ifdef __BIG_ENDIAN__
+#if __BIG_ENDIAN__
+#define _YUGA_LITTLE_ENDIAN 0
+#define _YUGA_BIG_ENDIAN    1
+#endif
+#endif /* __BIG_ENDIAN__ */
+
+#ifdef __LITTLE_ENDIAN__
+#if __LITTLE_ENDIAN__
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+#endif
+#endif /* __LITTLE_ENDIAN__ */
+
+#endif /* Mac OSX */
+
+/* .. */
+
+#if defined(__linux__)
+#include <endian.h>
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 0
+#define _YUGA_BIG_ENDIAN    1
+#elif __BYTE_ORDER == __LITTLE_ENDIAN
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+#endif /* __BYTE_ORDER */
+
+#endif /* GNU/Linux */
+
+#if defined(_WIN32)
+
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+
+#endif /* Windows */
+
+#if defined(EMSCRIPTEN)
+
+#define _YUGA_LITTLE_ENDIAN 1
+#define _YUGA_BIG_ENDIAN    0
+
+#endif /* emscripten */
+
+/* . */
+
+#if !defined(_YUGA_LITTLE_ENDIAN) || !defined(_YUGA_BIG_ENDIAN)
+#error Unable to determine endian
+#endif /* Check we found an endianness correctly. */
+
+#endif /* INT_ENDIANNESS_H */
diff --git a/system/lib/compiler-rt/int_lib.h b/system/lib/compiler-rt/int_lib.h
new file mode 100644
index 00000000..a87426c5
--- /dev/null
+++ b/system/lib/compiler-rt/int_lib.h
@@ -0,0 +1,46 @@
+/* ===-- int_lib.h - configuration header for compiler-rt  -----------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file is a configuration header for compiler-rt.
+ * This file is not part of the interface of this library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#ifndef INT_LIB_H
+#define INT_LIB_H
+
+/* Assumption: Signed integral is 2's complement. */
+/* Assumption: Right shift of signed negative is arithmetic shift. */
+/* Assumption: Endianness is little or big (not mixed). */
+
+/* ABI macro definitions */
+
+#if __ARM_EABI__
+# define ARM_EABI_FNALIAS(aeabi_name, name)         \
+  void __aeabi_##aeabi_name() __attribute__((alias("__" #name)));
+# define COMPILER_RT_ABI __attribute__((pcs("aapcs")))
+#else
+# define ARM_EABI_FNALIAS(aeabi_name, name)
+# define COMPILER_RT_ABI
+#endif
+
+/* Include the standard compiler builtin headers we use functionality from. */
+#include <limits.h>
+#include <stdint.h>
+#include <stdbool.h>
+#include <float.h>
+
+/* Include the commonly used internal type definitions. */
+#include "int_types.h"
+
+/* Include internal utility function declarations. */
+#include "int_util.h"
+
+#endif /* INT_LIB_H */
diff --git a/system/lib/compiler-rt/int_math.h b/system/lib/compiler-rt/int_math.h
new file mode 100644
index 00000000..d6b4bdae
--- /dev/null
+++ b/system/lib/compiler-rt/int_math.h
@@ -0,0 +1,67 @@
+/* ===-- int_math.h - internal math inlines ---------------------------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===-----------------------------------------------------------------------===
+ *
+ * This file is not part of the interface of this library.
+ *
+ * This file defines substitutes for the libm functions used in some of the
+ * compiler-rt implementations, defined in such a way that there is not a direct
+ * dependency on libm or math.h. Instead, we use the compiler builtin versions
+ * where available. This reduces our dependencies on the system SDK by foisting
+ * the responsibility onto the compiler.
+ *
+ * ===-----------------------------------------------------------------------===
+ */
+
+#ifndef INT_MATH_H
+#define INT_MATH_H
+
+#ifndef __has_builtin
+#  define  __has_builtin(x) 0
+#endif
+
+#define CRT_INFINITY __builtin_huge_valf()
+
+#define crt_isinf(x) __builtin_isinf((x))
+#define crt_isnan(x) __builtin_isnan((x))
+
+/* Define crt_isfinite in terms of the builtin if available, otherwise provide
+ * an alternate version in terms of our other functions. This supports some
+ * versions of GCC which didn't have __builtin_isfinite.
+ */
+#if __has_builtin(__builtin_isfinite)
+#  define crt_isfinite(x) __builtin_isfinite((x))
+#else
+#  define crt_isfinite(x) \
+  __extension__(({ \
+      __typeof((x)) x_ = (x); \
+      !crt_isinf(x_) && !crt_isnan(x_); \
+    }))
+#endif
+
+#define crt_copysign(x, y) __builtin_copysign((x), (y))
+#define crt_copysignf(x, y) __builtin_copysignf((x), (y))
+#define crt_copysignl(x, y) __builtin_copysignl((x), (y))
+
+#define crt_fabs(x) __builtin_fabs((x))
+#define crt_fabsf(x) __builtin_fabsf((x))
+#define crt_fabsl(x) __builtin_fabsl((x))
+
+#define crt_fmax(x, y) __builtin_fmax((x), (y))
+#define crt_fmaxf(x, y) __builtin_fmaxf((x), (y))
+#define crt_fmaxl(x, y) __builtin_fmaxl((x), (y))
+
+#define crt_logb(x) __builtin_logb((x))
+#define crt_logbf(x) __builtin_logbf((x))
+#define crt_logbl(x) __builtin_logbl((x))
+
+#define crt_scalbn(x, y) __builtin_scalbn((x), (y))
+#define crt_scalbnf(x, y) __builtin_scalbnf((x), (y))
+#define crt_scalbnl(x, y) __builtin_scalbnl((x), (y))
+
+#endif /* INT_MATH_H */
diff --git a/system/lib/compiler-rt/int_types.h b/system/lib/compiler-rt/int_types.h
new file mode 100644
index 00000000..fcce390f
--- /dev/null
+++ b/system/lib/compiler-rt/int_types.h
@@ -0,0 +1,140 @@
+/* ===-- int_lib.h - configuration header for compiler-rt  -----------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file is not part of the interface of this library.
+ *
+ * This file defines various standard types, most importantly a number of unions
+ * used to access parts of larger types.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#ifndef INT_TYPES_H
+#define INT_TYPES_H
+
+#include "int_endianness.h"
+
+typedef      int si_int;
+typedef unsigned su_int;
+
+typedef          long long di_int;
+typedef unsigned long long du_int;
+
+typedef union
+{
+    di_int all;
+    struct
+    {
+#if _YUGA_LITTLE_ENDIAN
+        su_int low;
+        si_int high;
+#else
+        si_int high;
+        su_int low;
+#endif /* _YUGA_LITTLE_ENDIAN */
+    }s;
+} dwords;
+
+typedef union
+{
+    du_int all;
+    struct
+    {
+#if _YUGA_LITTLE_ENDIAN
+        su_int low;
+        su_int high;
+#else
+        su_int high;
+        su_int low;
+#endif /* _YUGA_LITTLE_ENDIAN */
+    }s;
+} udwords;
+
+#if __x86_64
+
+typedef int      ti_int __attribute__ ((mode (TI)));
+typedef unsigned tu_int __attribute__ ((mode (TI)));
+
+typedef union
+{
+    ti_int all;
+    struct
+    {
+#if _YUGA_LITTLE_ENDIAN
+        du_int low;
+        di_int high;
+#else
+        di_int high;
+        du_int low;
+#endif /* _YUGA_LITTLE_ENDIAN */
+    }s;
+} twords;
+
+typedef union
+{
+    tu_int all;
+    struct
+    {
+#if _YUGA_LITTLE_ENDIAN
+        du_int low;
+        du_int high;
+#else
+        du_int high;
+        du_int low;
+#endif /* _YUGA_LITTLE_ENDIAN */
+    }s;
+} utwords;
+
+static inline ti_int make_ti(di_int h, di_int l) {
+    twords r;
+    r.s.high = h;
+    r.s.low = l;
+    return r.all;
+}
+
+static inline tu_int make_tu(du_int h, du_int l) {
+    utwords r;
+    r.s.high = h;
+    r.s.low = l;
+    return r.all;
+}
+
+#endif /* __x86_64 */
+
+typedef union
+{
+    su_int u;
+    float f;
+} float_bits;
+
+typedef union
+{
+    udwords u;
+    double  f;
+} double_bits;
+
+typedef struct
+{
+#if _YUGA_LITTLE_ENDIAN
+    udwords low;
+    udwords high;
+#else
+    udwords high;
+    udwords low;
+#endif /* _YUGA_LITTLE_ENDIAN */
+} uqwords;
+
+typedef union
+{
+    uqwords     u;
+    long double f;
+} long_double_bits;
+
+#endif /* INT_TYPES_H */
+
diff --git a/system/lib/compiler-rt/int_util.h b/system/lib/compiler-rt/int_util.h
new file mode 100644
index 00000000..1348b85e
--- /dev/null
+++ b/system/lib/compiler-rt/int_util.h
@@ -0,0 +1,29 @@
+/* ===-- int_util.h - internal utility functions ----------------------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===-----------------------------------------------------------------------===
+ *
+ * This file is not part of the interface of this library.
+ *
+ * This file defines non-inline utilities which are available for use in the
+ * library. The function definitions themselves are all contained in int_util.c
+ * which will always be compiled into any compiler-rt library.
+ *
+ * ===-----------------------------------------------------------------------===
+ */
+
+#ifndef INT_UTIL_H
+#define INT_UTIL_H
+
+/** \brief Trigger a program abort (or panic for kernel code). */
+#define compilerrt_abort() compilerrt_abort_impl(__FILE__, __LINE__, \
+                                                 __FUNCTION__)
+
+void compilerrt_abort_impl(const char *file, int line,
+                           const char *function) __attribute__((noreturn));
+
+#endif /* INT_UTIL_H */
diff --git a/system/lib/compiler-rt/muldi3.c b/system/lib/compiler-rt/muldi3.c
new file mode 100644
index 00000000..2dae44c1
--- /dev/null
+++ b/system/lib/compiler-rt/muldi3.c
@@ -0,0 +1,56 @@
+/* ===-- muldi3.c - Implement __muldi3 -------------------------------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements __muldi3 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include "int_lib.h"
+
+/* Returns: a * b */
+
+static
+di_int
+__muldsi3(su_int a, su_int b)
+{
+    dwords r;
+    const int bits_in_word_2 = (int)(sizeof(si_int) * CHAR_BIT) / 2;
+    const su_int lower_mask = (su_int)~0 >> bits_in_word_2;
+    r.s.low = (a & lower_mask) * (b & lower_mask);
+    su_int t = r.s.low >> bits_in_word_2;
+    r.s.low &= lower_mask;
+    t += (a >> bits_in_word_2) * (b & lower_mask);
+    r.s.low += (t & lower_mask) << bits_in_word_2;
+    r.s.high = t >> bits_in_word_2;
+    t = r.s.low >> bits_in_word_2;
+    r.s.low &= lower_mask;
+    t += (b >> bits_in_word_2) * (a & lower_mask);
+    r.s.low += (t & lower_mask) << bits_in_word_2;
+    r.s.high += t >> bits_in_word_2;
+    r.s.high += (a >> bits_in_word_2) * (b >> bits_in_word_2);
+    return r.all;
+}
+
+/* Returns: a * b */
+
+ARM_EABI_FNALIAS(lmul, muldi3)
+
+COMPILER_RT_ABI di_int
+__muldi3(di_int a, di_int b)
+{
+    dwords x;
+    x.all = a;
+    dwords y;
+    y.all = b;
+    dwords r;
+    r.all = __muldsi3(x.s.low, y.s.low);
+    r.s.high += x.s.high * y.s.low + x.s.low * y.s.high;
+    return r.all;
+}
diff --git a/system/lib/compiler-rt/readme.txt b/system/lib/compiler-rt/readme.txt
new file mode 100644
index 00000000..1fc97635
--- /dev/null
+++ b/system/lib/compiler-rt/readme.txt
@@ -0,0 +1,16 @@
+These files are from compiler-rt,
+
+Last Changed Rev: 179380
+Last Changed Date: 2013-04-12 07:57:03 -0700 (Fri, 12 Apr 2013)
+
+===========================================================================
+
+Changes: add emscripten endianness to int_endianness.h
+
+===========================================================================
+
+Compile with something like
+
+./emcc system/lib/compiler-rt/*.c -Isystem/lib/compiler-rt/ -o rt.bc
+./emcc -O2 -s ASM_JS=1 -g rt.bc -s LINKABLE=1
+
diff --git a/system/lib/compiler-rt/udivdi3.c b/system/lib/compiler-rt/udivdi3.c
new file mode 100644
index 00000000..6c0303df
--- /dev/null
+++ b/system/lib/compiler-rt/udivdi3.c
@@ -0,0 +1,25 @@
+/* ===-- udivdi3.c - Implement __udivdi3 -----------------------------------===
+ *
+ *                    The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements __udivdi3 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include "int_lib.h"
+
+du_int COMPILER_RT_ABI __udivmoddi4(du_int a, du_int b, du_int* rem);
+
+/* Returns: a / b */
+
+COMPILER_RT_ABI du_int
+__udivdi3(du_int a, du_int b)
+{
+    return __udivmoddi4(a, b, 0);
+}
diff --git a/system/lib/compiler-rt/udivmoddi4.c b/system/lib/compiler-rt/udivmoddi4.c
new file mode 100644
index 00000000..57282d5b
--- /dev/null
+++ b/system/lib/compiler-rt/udivmoddi4.c
@@ -0,0 +1,251 @@
+/* ===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements __udivmoddi4 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#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 */
+
+COMPILER_RT_ABI du_int
+__udivmoddi4(du_int a, du_int b, du_int* rem)
+{
+    const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
+    const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
+    udwords n;
+    n.all = a;
+    udwords d;
+    d.all = b;
+    udwords q;
+    udwords 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_ctz(d.s.high);
+        }
+        /* K K
+         * ---
+         * K 0
+         */
+        sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
+        /* 0 <= sr <= n_uword_bits - 2 or sr large */
+        if (sr > n_uword_bits - 2)
+        {
+           if (rem)
+                *rem = n.all;
+            return 0;
+        }
+        ++sr;
+        /* 1 <= sr <= n_uword_bits - 1 */
+        /* q.all = n.all << (n_udword_bits - sr); */
+        q.s.low = 0;
+        q.s.high = n.s.low << (n_uword_bits - sr);
+        /* r.all = n.all >> sr; */
+        r.s.high = n.s.high >> sr;
+        r.s.low = (n.s.high << (n_uword_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;
+                sr = __builtin_ctz(d.s.low);
+                q.s.high = n.s.high >> sr;
+                q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
+                return q.all;
+            }
+            /* K X
+             * ---
+             *0 K
+             */
+            sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high);
+            /* 2 <= sr <= n_udword_bits - 1
+             * q.all = n.all << (n_udword_bits - sr);
+             * r.all = n.all >> sr;
+             * if (sr == n_uword_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_uword_bits)  // 2 <= sr <= n_uword_bits - 1
+             * {
+             *     q.s.low = 0;
+             *     q.s.high = n.s.low << (n_uword_bits - sr);
+             *     r.s.high = n.s.high >> sr;
+             *     r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
+             * }
+             * else              // n_uword_bits + 1 <= sr <= n_udword_bits - 1
+             * {
+             *     q.s.low = n.s.low << (n_udword_bits - sr);
+             *     q.s.high = (n.s.high << (n_udword_bits - sr)) |
+             *              (n.s.low >> (sr - n_uword_bits));
+             *     r.s.high = 0;
+             *     r.s.low = n.s.high >> (sr - n_uword_bits);
+             * }
+             */
+            q.s.low =  (n.s.low << (n_udword_bits - sr)) &
+                     ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1));
+            q.s.high = ((n.s.low << ( n_uword_bits - sr))                       &
+                     ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) |
+                     (((n.s.high << (n_udword_bits - sr))                     |
+                     (n.s.low >> (sr - n_uword_bits)))                        &
+                     ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)));
+            r.s.high = (n.s.high >> sr) &
+                     ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
+            r.s.low =  ((n.s.high >> (sr - n_uword_bits))                       &
+                     ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) |
+                     (((n.s.high << (n_uword_bits - sr))                      |
+                     (n.s.low >> sr))                                         &
+                     ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
+        }
+        else
+        {
+            /* K X
+             * ---
+             * K K
+             */
+            sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
+            /* 0 <= sr <= n_uword_bits - 1 or sr large */
+            if (sr > n_uword_bits - 1)
+            {
+               if (rem)
+                    *rem = n.all;
+                return 0;
+            }
+            ++sr;
+            /* 1 <= sr <= n_uword_bits */
+            /*  q.all = n.all << (n_udword_bits - sr); */
+            q.s.low = 0;
+            q.s.high = n.s.low << (n_uword_bits - sr);
+            /* r.all = n.all >> sr;
+             * if (sr < n_uword_bits)
+             * {
+             *     r.s.high = n.s.high >> sr;
+             *     r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
+             * }
+             * else
+             * {
+             *     r.s.high = 0;
+             *     r.s.low = n.s.high;
+             * }
+             */
+            r.s.high = (n.s.high >> sr) &
+                     ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
+            r.s.low = (n.s.high << (n_uword_bits - sr)) |
+                    ((n.s.low >> sr)                  &
+                    ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
+        }
+    }
+    /* Not a special case
+     * q and r are initialized with:
+     * q.all = n.all << (n_udword_bits - sr);
+     * r.all = n.all >> sr;
+     * 1 <= sr <= n_udword_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_uword_bits - 1));
+        r.s.low  = (r.s.low  << 1) | (q.s.high >> (n_uword_bits - 1));
+        q.s.high = (q.s.high << 1) | (q.s.low  >> (n_uword_bits - 1));
+        q.s.low  = (q.s.low  << 1) | carry;
+        /* carry = 0;
+         * if (r.all >= d.all)
+         * {
+         *      r.all -= d.all;
+         *      carry = 1;
+         * }
+         */
+        const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
+        carry = s & 1;
+        r.all -= d.all & s;
+    }
+    q.all = (q.all << 1) | carry;
+    if (rem)
+        *rem = r.all;
+    return q.all;
+}