1 files changed, 172 insertions, 0 deletions
diff --git a/tools/source/misc/fix16.cxx b/tools/source/misc/fix16.cxx
new file mode 100644
index 000000000..978f77291
--- /dev/null
+++ b/tools/source/misc/fix16.cxx
@@ -0,0 +1,172 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; fill-column: 100 -*- */
+/*
+ * libfixmath is Copyright (c) 2011-2021 Flatmush <Flatmush@gmail.com>,
+ * Petteri Aimonen <Petteri.Aimonen@gmail.com>, & libfixmath AUTHORS
+ *
+ * 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.
+ */
+
+#include <tools/fix16.hxx>
+
+const fix16_t fix16_minimum = 0x80000000; /*!< the minimum value of fix16_t */
+const fix16_t fix16_overflow = 0x80000000; /*!< the value used to indicate overflows */
+
+static inline uint32_t fix_abs(fix16_t in)
+{
+    if (in == fix16_minimum)
+    {
+        // minimum negative number has same representation as
+        // its absolute value in unsigned
+        return 0x80000000;
+    }
+    else
+    {
+        return (in >= 0) ? in : -in;
+    }
+}
+
+/* 64-bit implementation for fix16_mul. Fastest version for e.g. ARM Cortex M3.
+ * Performs a 32*32 -> 64bit multiplication. The middle 32 bits are the result,
+ * bottom 16 bits are used for rounding, and upper 16 bits are used for overflow
+ * detection.
+ */
+
+fix16_t fix16_mul(fix16_t inArg0, fix16_t inArg1)
+{
+    int64_t product = static_cast<int64_t>(inArg0) * inArg1;
+
+    // The upper 17 bits should all be the same (the sign).
+    uint32_t upper = (product >> 47);
+
+    if (product < 0)
+    {
+        if (~upper)
+            return fix16_overflow;
+
+        // This adjustment is required in order to round -1/2 correctly
+        product--;
+    }
+    else
+    {
+        if (upper)
+            return fix16_overflow;
+    }
+
+    fix16_t result = product >> 16;
+    result += (product & 0x8000) >> 15;
+
+    return result;
+}
+
+/* 32-bit implementation of fix16_div. Fastest version for e.g. ARM Cortex M3.
+ * Performs 32-bit divisions repeatedly to reduce the remainder. For this to
+ * be efficient, the processor has to have 32-bit hardware division.
+ */
+#ifdef __GNUC__
+// Count leading zeros, using processor-specific instruction if available.
+#define clz(x) (__builtin_clzl(x) - (8 * sizeof(long) - 32))
+#else
+static uint8_t clz(uint32_t x)
+{
+    uint8_t result = 0;
+    if (x == 0)
+        return 32;
+    while (!(x & 0xF0000000))
+    {
+        result += 4;
+        x <<= 4;
+    }
+    while (!(x & 0x80000000))
+    {
+        result += 1;
+        x <<= 1;
+    }
+    return result;
+}
+#endif
+
+fix16_t fix16_div(fix16_t a, fix16_t b)
+{
+    // This uses a hardware 32/32 bit division multiple times, until we have
+    // computed all the bits in (a<<17)/b. Usually this takes 1-3 iterations.
+
+    if (b == 0)
+        return fix16_minimum;
+
+    uint32_t remainder = fix_abs(a);
+    uint32_t divider = fix_abs(b);
+    uint64_t quotient = 0;
+    int bit_pos = 17;
+
+    // Kick-start the division a bit.
+    // This improves speed in the worst-case scenarios where N and D are large
+    // It gets a lower estimate for the result by N/(D >> 17 + 1).
+    if (divider & 0xFFF00000)
+    {
+        uint32_t shifted_div = (divider >> 17) + 1;
+        quotient = remainder / shifted_div;
+        uint64_t tmp = (quotient * static_cast<uint64_t>(divider)) >> 17;
+        remainder -= static_cast<uint32_t>(tmp);
+    }
+
+    // If the divider is divisible by 2^n, take advantage of it.
+    while (!(divider & 0xF) && bit_pos >= 4)
+    {
+        divider >>= 4;
+        bit_pos -= 4;
+    }
+
+    while (remainder && bit_pos >= 0)
+    {
+        // Shift remainder as much as we can without overflowing
+        int shift = clz(remainder);
+        if (shift > bit_pos)
+            shift = bit_pos;
+        remainder <<= shift;
+        bit_pos -= shift;
+
+        uint32_t div = remainder / divider;
+        remainder = remainder % divider;
+        quotient += static_cast<uint64_t>(div) << bit_pos;
+
+        if (div & ~(0xFFFFFFFF >> bit_pos))
+            return fix16_overflow;
+
+        remainder <<= 1;
+        bit_pos--;
+    }
+
+    // Quotient is always positive so rounding is easy
+    quotient++;
+
+    fix16_t result = quotient >> 1;
+
+    // Figure out the sign of the result
+    if ((a ^ b) & 0x80000000)
+    {
+        if (result == fix16_minimum)
+            return fix16_overflow;
+
+        result = -result;
+    }
+
+    return result;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab cinoptions=b1,g0,N-s cinkeys+=0=break: */