builtins: add 64-bit divide functions from llvm/compiler_rt
Code generated by gcc would crash
Compiler will link with these functions instead of using its
own builtins
Bug: 32308697
Test: run gts simple heap alloc test
Change-Id: I08200251a6853fda286949c7571410bde08763c8
Signed-off-by: Ben Fennema <fennema@google.com>
diff --git a/firmware/app/chre/common/Android.mk b/firmware/app/chre/common/Android.mk
index 9a05b03..0c8302f 100644
--- a/firmware/app/chre/common/Android.mk
+++ b/firmware/app/chre/common/Android.mk
@@ -25,6 +25,7 @@
chre_app.c \
chre_app_syscalls.c \
+LOCAL_STATIC_LIBRARIES += libnanobuiltins
LOCAL_STATIC_LIBRARIES += libnanolibc
include $(BUILD_NANOHUB_APP_STATIC_LIBRARY)
diff --git a/firmware/build/app_chre_executable.mk b/firmware/build/app_chre_executable.mk
index 1007ec7..0169699 100644
--- a/firmware/build/app_chre_executable.mk
+++ b/firmware/build/app_chre_executable.mk
@@ -33,6 +33,7 @@
# add standard libaries
LOCAL_STATIC_LIBRARIES += \
+ libnanobuiltins \
libnanolibc \
libnanolibm \
diff --git a/firmware/lib/builtins/Android.mk b/firmware/lib/builtins/Android.mk
new file mode 100644
index 0000000..c6a1e53
--- /dev/null
+++ b/firmware/lib/builtins/Android.mk
@@ -0,0 +1,37 @@
+#
+# Copyright (C) 2016 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+LOCAL_PATH := $(call my-dir)
+
+include $(CLEAR_NANO_VARS)
+
+LOCAL_MODULE := libnanobuiltins
+LOCAL_MODULE_TAGS := optional
+
+LOCAL_SRC_FILES_cortexm4 := \
+ aeabi_ldivmod.S \
+ aeabi_uldivmod.S \
+ divdi3.c \
+ divmoddi4.c \
+ moddi3.c \
+ udivmoddi4.c \
+ umoddi3.c \
+
+LOCAL_C_INCLUDES = $(LOCAL_PATH)
+LOCAL_EXPORT_C_INCLUDE_DIRS := \
+ $(LOCAL_C_INCLUDES)
+
+include $(BUILD_NANOHUB_APP_STATIC_LIBRARY)
diff --git a/firmware/lib/builtins/CREDITS.TXT b/firmware/lib/builtins/CREDITS.TXT
new file mode 100644
index 0000000..6964eba
--- /dev/null
+++ b/firmware/lib/builtins/CREDITS.TXT
@@ -0,0 +1,36 @@
+This file is a partial list of people who have contributed to the LLVM/CompilerRT
+project. If you have contributed a patch or made some other contribution to
+LLVM/CompilerRT, please submit a patch to this file to add yourself, and it will be
+done!
+
+The list is sorted by surname and formatted to allow easy grepping and
+beautification by scripts. The fields are: name (N), email (E), web-address
+(W), PGP key ID and fingerprint (P), description (D), and snail-mail address
+(S).
+
+N: Craig van Vliet
+E: cvanvliet@auroraux.org
+W: http://www.auroraux.org
+D: Code style and Readability fixes.
+
+N: Edward O'Callaghan
+E: eocallaghan@auroraux.org
+W: http://www.auroraux.org
+D: CMake'ify Compiler-RT build system
+D: Maintain Solaris & AuroraUX ports of Compiler-RT
+
+N: Howard Hinnant
+E: hhinnant@apple.com
+D: Architect and primary author of compiler-rt
+
+N: Guan-Hong Liu
+E: koviankevin@hotmail.com
+D: IEEE Quad-precision functions
+
+N: Joerg Sonnenberger
+E: joerg@NetBSD.org
+D: Maintains NetBSD port.
+
+N: Matt Thomas
+E: matt@NetBSD.org
+D: ARM improvements.
diff --git a/firmware/lib/builtins/LICENSE.TXT b/firmware/lib/builtins/LICENSE.TXT
new file mode 100644
index 0000000..a17dc12
--- /dev/null
+++ b/firmware/lib/builtins/LICENSE.TXT
@@ -0,0 +1,91 @@
+==============================================================================
+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-2016 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-2015 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.
+
diff --git a/firmware/lib/builtins/MODULE_LICENSE_MIT b/firmware/lib/builtins/MODULE_LICENSE_MIT
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/firmware/lib/builtins/MODULE_LICENSE_MIT
diff --git a/firmware/lib/builtins/NOTICE b/firmware/lib/builtins/NOTICE
new file mode 100644
index 0000000..aee8347
--- /dev/null
+++ b/firmware/lib/builtins/NOTICE
@@ -0,0 +1,91 @@
+==============================================================================
+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-2014 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-2014 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.
+
diff --git a/firmware/lib/builtins/aeabi_ldivmod.S b/firmware/lib/builtins/aeabi_ldivmod.S
new file mode 100644
index 0000000..54fd33b
--- /dev/null
+++ b/firmware/lib/builtins/aeabi_ldivmod.S
@@ -0,0 +1,34 @@
+//===-- aeabi_ldivmod.S - EABI ldivmod implementation ---------------------===//
+//
+// 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.
+//
+//===----------------------------------------------------------------------===//
+
+// struct { int64_t quot, int64_t rem}
+// __aeabi_ldivmod(int64_t numerator, int64_t denominator) {
+// int64_t rem, quot;
+// quot = __divmoddi4(numerator, denominator, &rem);
+// return {quot, rem};
+// }
+
+ .syntax unified
+ .text
+ .align 2
+ .global __aeabi_ldivmod
+ .thumb
+ .thumb_func
+ .type __aeabi_ldivmod, %function
+__aeabi_ldivmod:
+ push {lr}
+ sub sp, sp, #16
+ add r12, sp, #8
+ str r12, [sp]
+ bl __divmoddi4
+ ldr r2, [sp, #8]
+ ldr r3, [sp, #12]
+ add sp, sp, #16
+ pop {pc}
+ .size __aeabi_ldivmod, .-__aeabi_ldivmod
diff --git a/firmware/lib/builtins/aeabi_uldivmod.S b/firmware/lib/builtins/aeabi_uldivmod.S
new file mode 100644
index 0000000..8fa1de4
--- /dev/null
+++ b/firmware/lib/builtins/aeabi_uldivmod.S
@@ -0,0 +1,34 @@
+//===-- aeabi_uldivmod.S - EABI uldivmod implementation -------------------===//
+//
+// 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.
+//
+//===----------------------------------------------------------------------===//
+
+// struct { uint64_t quot, uint64_t rem}
+// __aeabi_uldivmod(uint64_t numerator, uint64_t denominator) {
+// uint64_t rem, quot;
+// quot = __udivmoddi4(numerator, denominator, &rem);
+// return {quot, rem};
+// }
+
+ .syntax unified
+ .text
+ .align 2
+ .global __aeabi_uldivmod
+ .thumb
+ .thumb_func
+ .type __aeabi_uldivmod, %function
+__aeabi_uldivmod:
+ push {lr}
+ sub sp, sp, #16
+ add r12, sp, #8
+ str r12, [sp]
+ bl __udivmoddi4
+ ldr r2, [sp, #8]
+ ldr r3, [sp, #12]
+ add sp, sp, #16
+ pop {pc}
+ .size __aeabi_uldivmod, .-__aeabi_uldivmod
diff --git a/firmware/lib/builtins/divdi3.c b/firmware/lib/builtins/divdi3.c
new file mode 100644
index 0000000..c545a80
--- /dev/null
+++ b/firmware/lib/builtins/divdi3.c
@@ -0,0 +1,29 @@
+/* ===-- 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"
+
+/* Returns: a / b */
+
+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/firmware/lib/builtins/divmoddi4.c b/firmware/lib/builtins/divmoddi4.c
new file mode 100644
index 0000000..12309d8
--- /dev/null
+++ b/firmware/lib/builtins/divmoddi4.c
@@ -0,0 +1,25 @@
+/*===-- divmoddi4.c - Implement __divmoddi4 --------------------------------===
+ *
+ * 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 __divmoddi4 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include "int_lib.h"
+
+/* Returns: a / b, *rem = a % b */
+
+di_int
+__divmoddi4(di_int a, di_int b, di_int* rem)
+{
+ di_int d = __divdi3(a,b);
+ *rem = a - (d*b);
+ return d;
+}
diff --git a/firmware/lib/builtins/int_lib.h b/firmware/lib/builtins/int_lib.h
new file mode 100644
index 0000000..2840710
--- /dev/null
+++ b/firmware/lib/builtins/int_lib.h
@@ -0,0 +1,44 @@
+/* ===-- 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
+
+#define CHAR_BIT 8
+
+typedef unsigned su_int;
+typedef unsigned long long du_int;
+typedef long long di_int;
+
+typedef union
+{
+ du_int all;
+ struct
+ {
+ su_int low;
+ su_int high;
+ } s;
+} udwords;
+
+/* Assumption: Signed integral is 2's complement. */
+/* Assumption: Right shift of signed negative is arithmetic shift. */
+
+di_int __divdi3(di_int a, di_int b);
+di_int __moddi3(di_int a, di_int b);
+du_int __umoddi3(du_int a, du_int b);
+di_int __divmoddi4(di_int a, di_int b, di_int* rem);
+du_int __udivmoddi4(du_int a, du_int b, du_int* rem);
+
+#endif /* INT_LIB_H */
diff --git a/firmware/lib/builtins/moddi3.c b/firmware/lib/builtins/moddi3.c
new file mode 100644
index 0000000..5616a0a
--- /dev/null
+++ b/firmware/lib/builtins/moddi3.c
@@ -0,0 +1,30 @@
+/*===-- moddi3.c - Implement __moddi3 -------------------------------------===
+ *
+ * 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 __moddi3 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include "int_lib.h"
+
+/* Returns: a % b */
+
+di_int
+__moddi3(di_int a, di_int b)
+{
+ const int bits_in_dword_m1 = (int)(sizeof(di_int) * CHAR_BIT) - 1;
+ di_int s = b >> bits_in_dword_m1; /* s = b < 0 ? -1 : 0 */
+ b = (b ^ s) - s; /* negate if s == -1 */
+ s = a >> bits_in_dword_m1; /* s = a < 0 ? -1 : 0 */
+ a = (a ^ s) - s; /* negate if s == -1 */
+ du_int r;
+ __udivmoddi4(a, b, &r);
+ return ((di_int)r ^ s) - s; /* negate if s == -1 */
+}
diff --git a/firmware/lib/builtins/udivmoddi4.c b/firmware/lib/builtins/udivmoddi4.c
new file mode 100644
index 0000000..c07f68a
--- /dev/null
+++ b/firmware/lib/builtins/udivmoddi4.c
@@ -0,0 +1,231 @@
+/* ===-- 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 */
+
+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);
+ }
+ }
+ 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;
+ if (sr == n_uword_bits)
+ {
+ q.s.high = n.s.low;
+ r.s.high = 0;
+ r.s.low = n.s.high;
+ }
+ else
+ {
+ 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);
+ }
+ }
+ }
+ /* 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;
+}
diff --git a/firmware/lib/builtins/umoddi3.c b/firmware/lib/builtins/umoddi3.c
new file mode 100644
index 0000000..aeaf0f8
--- /dev/null
+++ b/firmware/lib/builtins/umoddi3.c
@@ -0,0 +1,25 @@
+/* ===-- umoddi3.c - Implement __umoddi3 -----------------------------------===
+ *
+ * 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 __umoddi3 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include "int_lib.h"
+
+/* Returns: a % b */
+
+du_int
+__umoddi3(du_int a, du_int b)
+{
+ du_int r;
+ __udivmoddi4(a, b, &r);
+ return r;
+}
diff --git a/firmware/lib/lib.mk b/firmware/lib/lib.mk
index ef31c14..e964f16 100644
--- a/firmware/lib/lib.mk
+++ b/firmware/lib/lib.mk
@@ -16,7 +16,7 @@
################################################################################
#
-# Nanoapp Libc/Libm build helper script
+# Nanoapp Libc/Libm/Builtins build helper script
#
################################################################################
@@ -70,3 +70,16 @@
SRCS += $(LIBC_PATH)/new.cpp
CFLAGS += -I$(LIBC_PATH)
CFLAGS += -DNANOHUB_PROVIDES_CXX_SUPPORT
+
+# Builtins #####################################################################
+
+BUILTINS_PATH := $(NANOHUB_DIR)/lib/builtins
+
+#SRCS += $(BUILTINS_PATH)/aeabi_ldivmod.S
+#SRCS += $(BUILTINS_PATH)/aeabi_uldivmod.S
+SRCS += $(BUILTINS_PATH)/divdi3.c
+SRCS += $(BUILTINS_PATH)/divmoddi4.c
+SRCS += $(BUILTINS_PATH)/moddi3.c
+SRCS += $(BUILTINS_PATH)/udivmoddi4.c
+SRCS += $(BUILTINS_PATH)/umoddi3.c
+CFLAGS += -I$(BUILTINS_PATH)
