summaryrefslogtreecommitdiffstats
path: root/tools/source/misc/fix16.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'tools/source/misc/fix16.cxx')
-rw-r--r--tools/source/misc/fix16.cxx172
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: */