Add __mulodi4 source to src/ext

We need to define this function when compiling with clang -m32 -ftrapv,
since otherwise we get link errors, since apparently some versions
of libclang_rt.builtins don't define a version of it that works? Or
clang doesn't know to look for it?

This definition is taken from the LLVM source at
  https://llvm.org/svn/llvm-project/compiler-rt/trunk/lib/builtins/mulodi4.c

I've also included the license (dual BSD-ish/MIT-ish).

3 files changed, 162 insertions, 0 deletions

diff --git a/src/ext/README b/src/ext/README
index c180927b86..dfe620ed16 100644
--- a/src/ext/README
+++ b/src/ext/README
@@ -77,3 +77,10 @@ readpassphrase.[ch]
 timeouts/
 
     William Ahern's hierarchical timer-wheel implementation. MIT license.
+
+mulodi/
+
+    Contains an overflow-checking 64-bit signed integer multiply
+    from LLVM's compiler_rt.  For some reason, this is missing from
+    32-bit libclang in many places. Dual licensed MIT-license and
+    BSD-like license; see mulodi/LICENSE.TXT.
diff --git a/src/ext/mulodi/LICENSE.TXT b/src/ext/mulodi/LICENSE.TXT
new file mode 100644
index 0000000000..a17dc12b27
--- /dev/null
+++ b/src/ext/mulodi/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/src/ext/mulodi/mulodi4.c b/src/ext/mulodi/mulodi4.c
new file mode 100644
index 0000000000..7e3dfdae34
--- /dev/null
+++ b/src/ext/mulodi/mulodi4.c
@@ -0,0 +1,64 @@
+/*===-- mulodi4.c - Implement __mulodi4 -----------------------------------===
+ *
+ *                     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 __mulodi4 for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#if 0
+#include "int_lib.h"
+#else
+#define COMPILER_RT_ABI
+#define di_int int64_t
+#include "torint.h"
+#endif
+
+/* Returns: a * b */
+
+/* Effects: sets *overflow to 1  if a * b overflows */
+
+COMPILER_RT_ABI di_int
+__mulodi4(di_int a, di_int b, int* overflow)
+{
+    const int N = (int)(sizeof(di_int) * CHAR_BIT);
+    const di_int MIN = (di_int)1 << (N-1);
+    const di_int MAX = ~MIN;
+    *overflow = 0; 
+    di_int result = a * b;
+    if (a == MIN)
+    {
+        if (b != 0 && b != 1)
+	    *overflow = 1;
+	return result;
+    }
+    if (b == MIN)
+    {
+        if (a != 0 && a != 1)
+	    *overflow = 1;
+        return result;
+    }
+    di_int sa = a >> (N - 1);
+    di_int abs_a = (a ^ sa) - sa;
+    di_int sb = b >> (N - 1);
+    di_int abs_b = (b ^ sb) - sb;
+    if (abs_a < 2 || abs_b < 2)
+        return result;
+    if (sa == sb)
+    {
+        if (abs_a > MAX / abs_b)
+            *overflow = 1;
+    }
+    else
+    {
+        if (abs_a > MIN / -abs_b)
+            *overflow = 1;
+    }
+    return result;
+}