From 458da8a94877677f086f06cdeecf959ec4283a33 Mon Sep 17 00:00:00 2001 From: Kelebek1 Date: Sat, 16 Jul 2022 23:48:45 +0100 Subject: Project Andio --- src/common/fixed_point.h | 726 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 726 insertions(+) create mode 100644 src/common/fixed_point.h (limited to 'src/common/fixed_point.h') diff --git a/src/common/fixed_point.h b/src/common/fixed_point.h new file mode 100644 index 000000000..1d45e51b3 --- /dev/null +++ b/src/common/fixed_point.h @@ -0,0 +1,726 @@ +// From: https://github.com/eteran/cpp-utilities/blob/master/fixed/include/cpp-utilities/fixed.h +// See also: http://stackoverflow.com/questions/79677/whats-the-best-way-to-do-fixed-point-math +/* + * The MIT License (MIT) + * + * Copyright (c) 2015 Evan Teran + * + * 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. + */ + +#ifndef FIXED_H_ +#define FIXED_H_ + +#if __cplusplus >= 201402L +#define CONSTEXPR14 constexpr +#else +#define CONSTEXPR14 +#endif + +#include // for size_t +#include +#include +#include +#include + +namespace Common { + +template +class FixedPoint; + +namespace detail { + +// helper templates to make magic with types :) +// these allow us to determine resonable types from +// a desired size, they also let us infer the next largest type +// from a type which is nice for the division op +template +struct type_from_size { + using value_type = void; + using unsigned_type = void; + using signed_type = void; + static constexpr bool is_specialized = false; +}; + +#if defined(__GNUC__) && defined(__x86_64__) && !defined(__STRICT_ANSI__) +template <> +struct type_from_size<128> { + static constexpr bool is_specialized = true; + static constexpr size_t size = 128; + + using value_type = __int128; + using unsigned_type = unsigned __int128; + using signed_type = __int128; + using next_size = type_from_size<256>; +}; +#endif + +template <> +struct type_from_size<64> { + static constexpr bool is_specialized = true; + static constexpr size_t size = 64; + + using value_type = int64_t; + using unsigned_type = std::make_unsigned::type; + using signed_type = std::make_signed::type; + using next_size = type_from_size<128>; +}; + +template <> +struct type_from_size<32> { + static constexpr bool is_specialized = true; + static constexpr size_t size = 32; + + using value_type = int32_t; + using unsigned_type = std::make_unsigned::type; + using signed_type = std::make_signed::type; + using next_size = type_from_size<64>; +}; + +template <> +struct type_from_size<16> { + static constexpr bool is_specialized = true; + static constexpr size_t size = 16; + + using value_type = int16_t; + using unsigned_type = std::make_unsigned::type; + using signed_type = std::make_signed::type; + using next_size = type_from_size<32>; +}; + +template <> +struct type_from_size<8> { + static constexpr bool is_specialized = true; + static constexpr size_t size = 8; + + using value_type = int8_t; + using unsigned_type = std::make_unsigned::type; + using signed_type = std::make_signed::type; + using next_size = type_from_size<16>; +}; + +// this is to assist in adding support for non-native base +// types (for adding big-int support), this should be fine +// unless your bit-int class doesn't nicely support casting +template +constexpr B next_to_base(N rhs) { + return static_cast(rhs); +} + +struct divide_by_zero : std::exception {}; + +template +CONSTEXPR14 FixedPoint divide( + FixedPoint numerator, FixedPoint denominator, FixedPoint& remainder, + typename std::enable_if::next_size::is_specialized>::type* = nullptr) { + + using next_type = typename FixedPoint::next_type; + using base_type = typename FixedPoint::base_type; + constexpr size_t fractional_bits = FixedPoint::fractional_bits; + + next_type t(numerator.to_raw()); + t <<= fractional_bits; + + FixedPoint quotient; + + quotient = FixedPoint::from_base(next_to_base(t / denominator.to_raw())); + remainder = FixedPoint::from_base(next_to_base(t % denominator.to_raw())); + + return quotient; +} + +template +CONSTEXPR14 FixedPoint divide( + FixedPoint numerator, FixedPoint denominator, FixedPoint& remainder, + typename std::enable_if::next_size::is_specialized>::type* = nullptr) { + + using unsigned_type = typename FixedPoint::unsigned_type; + + constexpr int bits = FixedPoint::total_bits; + + if (denominator == 0) { + throw divide_by_zero(); + } else { + + int sign = 0; + + FixedPoint quotient; + + if (numerator < 0) { + sign ^= 1; + numerator = -numerator; + } + + if (denominator < 0) { + sign ^= 1; + denominator = -denominator; + } + + unsigned_type n = numerator.to_raw(); + unsigned_type d = denominator.to_raw(); + unsigned_type x = 1; + unsigned_type answer = 0; + + // egyptian division algorithm + while ((n >= d) && (((d >> (bits - 1)) & 1) == 0)) { + x <<= 1; + d <<= 1; + } + + while (x != 0) { + if (n >= d) { + n -= d; + answer += x; + } + + x >>= 1; + d >>= 1; + } + + unsigned_type l1 = n; + unsigned_type l2 = denominator.to_raw(); + + // calculate the lower bits (needs to be unsigned) + while (l1 >> (bits - F) > 0) { + l1 >>= 1; + l2 >>= 1; + } + const unsigned_type lo = (l1 << F) / l2; + + quotient = FixedPoint::from_base((answer << F) | lo); + remainder = n; + + if (sign) { + quotient = -quotient; + } + + return quotient; + } +} + +// this is the usual implementation of multiplication +template +CONSTEXPR14 FixedPoint multiply( + FixedPoint lhs, FixedPoint rhs, + typename std::enable_if::next_size::is_specialized>::type* = nullptr) { + + using next_type = typename FixedPoint::next_type; + using base_type = typename FixedPoint::base_type; + + constexpr size_t fractional_bits = FixedPoint::fractional_bits; + + next_type t(static_cast(lhs.to_raw()) * static_cast(rhs.to_raw())); + t >>= fractional_bits; + + return FixedPoint::from_base(next_to_base(t)); +} + +// this is the fall back version we use when we don't have a next size +// it is slightly slower, but is more robust since it doesn't +// require and upgraded type +template +CONSTEXPR14 FixedPoint multiply( + FixedPoint lhs, FixedPoint rhs, + typename std::enable_if::next_size::is_specialized>::type* = nullptr) { + + using base_type = typename FixedPoint::base_type; + + constexpr size_t fractional_bits = FixedPoint::fractional_bits; + constexpr base_type integer_mask = FixedPoint::integer_mask; + constexpr base_type fractional_mask = FixedPoint::fractional_mask; + + // more costly but doesn't need a larger type + const base_type a_hi = (lhs.to_raw() & integer_mask) >> fractional_bits; + const base_type b_hi = (rhs.to_raw() & integer_mask) >> fractional_bits; + const base_type a_lo = (lhs.to_raw() & fractional_mask); + const base_type b_lo = (rhs.to_raw() & fractional_mask); + + const base_type x1 = a_hi * b_hi; + const base_type x2 = a_hi * b_lo; + const base_type x3 = a_lo * b_hi; + const base_type x4 = a_lo * b_lo; + + return FixedPoint::from_base((x1 << fractional_bits) + (x3 + x2) + + (x4 >> fractional_bits)); +} +} // namespace detail + +template +class FixedPoint { + static_assert(detail::type_from_size::is_specialized, "invalid combination of sizes"); + +public: + static constexpr size_t fractional_bits = F; + static constexpr size_t integer_bits = I; + static constexpr size_t total_bits = I + F; + + using base_type_info = detail::type_from_size; + + using base_type = typename base_type_info::value_type; + using next_type = typename base_type_info::next_size::value_type; + using unsigned_type = typename base_type_info::unsigned_type; + +public: +#ifdef __GNUC__ +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Woverflow" +#endif + static constexpr base_type fractional_mask = + ~(static_cast(~base_type(0)) << fractional_bits); + static constexpr base_type integer_mask = ~fractional_mask; +#ifdef __GNUC__ +#pragma GCC diagnostic pop +#endif + +public: + static constexpr base_type one = base_type(1) << fractional_bits; + +public: // constructors + FixedPoint() = default; + FixedPoint(const FixedPoint&) = default; + FixedPoint(FixedPoint&&) = default; + FixedPoint& operator=(const FixedPoint&) = default; + + template + constexpr FixedPoint( + Number n, typename std::enable_if::value>::type* = nullptr) + : data_(static_cast(n * one)) {} + +public: // conversion + template + CONSTEXPR14 explicit FixedPoint(FixedPoint other) { + static_assert(I2 <= I && F2 <= F, "Scaling conversion can only upgrade types"); + using T = FixedPoint; + + const base_type fractional = (other.data_ & T::fractional_mask); + const base_type integer = (other.data_ & T::integer_mask) >> T::fractional_bits; + data_ = + (integer << fractional_bits) | (fractional << (fractional_bits - T::fractional_bits)); + } + +private: + // this makes it simpler to create a FixedPoint point object from + // a native type without scaling + // use "FixedPoint::from_base" in order to perform this. + struct NoScale {}; + + constexpr FixedPoint(base_type n, const NoScale&) : data_(n) {} + +public: + static constexpr FixedPoint from_base(base_type n) { + return FixedPoint(n, NoScale()); + } + +public: // comparison operators + constexpr bool operator==(FixedPoint rhs) const { + return data_ == rhs.data_; + } + + constexpr bool operator!=(FixedPoint rhs) const { + return data_ != rhs.data_; + } + + constexpr bool operator<(FixedPoint rhs) const { + return data_ < rhs.data_; + } + + constexpr bool operator>(FixedPoint rhs) const { + return data_ > rhs.data_; + } + + constexpr bool operator<=(FixedPoint rhs) const { + return data_ <= rhs.data_; + } + + constexpr bool operator>=(FixedPoint rhs) const { + return data_ >= rhs.data_; + } + +public: // unary operators + constexpr bool operator!() const { + return !data_; + } + + constexpr FixedPoint operator~() const { + // NOTE(eteran): this will often appear to "just negate" the value + // that is not an error, it is because -x == (~x+1) + // and that "+1" is adding an infinitesimally small fraction to the + // complimented value + return FixedPoint::from_base(~data_); + } + + constexpr FixedPoint operator-() const { + return FixedPoint::from_base(-data_); + } + + constexpr FixedPoint operator+() const { + return FixedPoint::from_base(+data_); + } + + CONSTEXPR14 FixedPoint& operator++() { + data_ += one; + return *this; + } + + CONSTEXPR14 FixedPoint& operator--() { + data_ -= one; + return *this; + } + + CONSTEXPR14 FixedPoint operator++(int) { + FixedPoint tmp(*this); + data_ += one; + return tmp; + } + + CONSTEXPR14 FixedPoint operator--(int) { + FixedPoint tmp(*this); + data_ -= one; + return tmp; + } + +public: // basic math operators + CONSTEXPR14 FixedPoint& operator+=(FixedPoint n) { + data_ += n.data_; + return *this; + } + + CONSTEXPR14 FixedPoint& operator-=(FixedPoint n) { + data_ -= n.data_; + return *this; + } + + CONSTEXPR14 FixedPoint& operator*=(FixedPoint n) { + return assign(detail::multiply(*this, n)); + } + + CONSTEXPR14 FixedPoint& operator/=(FixedPoint n) { + FixedPoint temp; + return assign(detail::divide(*this, n, temp)); + } + +private: + CONSTEXPR14 FixedPoint& assign(FixedPoint rhs) { + data_ = rhs.data_; + return *this; + } + +public: // binary math operators, effects underlying bit pattern since these + // don't really typically make sense for non-integer values + CONSTEXPR14 FixedPoint& operator&=(FixedPoint n) { + data_ &= n.data_; + return *this; + } + + CONSTEXPR14 FixedPoint& operator|=(FixedPoint n) { + data_ |= n.data_; + return *this; + } + + CONSTEXPR14 FixedPoint& operator^=(FixedPoint n) { + data_ ^= n.data_; + return *this; + } + + template ::value>::type> + CONSTEXPR14 FixedPoint& operator>>=(Integer n) { + data_ >>= n; + return *this; + } + + template ::value>::type> + CONSTEXPR14 FixedPoint& operator<<=(Integer n) { + data_ <<= n; + return *this; + } + +public: // conversion to basic types + constexpr void round_up() { + data_ += (data_ & fractional_mask) >> 1; + } + + constexpr int to_int() { + round_up(); + return static_cast((data_ & integer_mask) >> fractional_bits); + } + + constexpr unsigned int to_uint() const { + round_up(); + return static_cast((data_ & integer_mask) >> fractional_bits); + } + + constexpr int64_t to_long() { + round_up(); + return static_cast((data_ & integer_mask) >> fractional_bits); + } + + constexpr int to_int_floor() const { + return static_cast((data_ & integer_mask) >> fractional_bits); + } + + constexpr int64_t to_long_floor() { + return static_cast((data_ & integer_mask) >> fractional_bits); + } + + constexpr unsigned int to_uint_floor() const { + return static_cast((data_ & integer_mask) >> fractional_bits); + } + + constexpr float to_float() const { + return static_cast(data_) / FixedPoint::one; + } + + constexpr double to_double() const { + return static_cast(data_) / FixedPoint::one; + } + + constexpr base_type to_raw() const { + return data_; + } + + constexpr void clear_int() { + data_ &= fractional_mask; + } + + constexpr base_type get_frac() const { + return data_ & fractional_mask; + } + +public: + CONSTEXPR14 void swap(FixedPoint& rhs) { + using std::swap; + swap(data_, rhs.data_); + } + +public: + base_type data_; +}; + +// if we have the same fractional portion, but differing integer portions, we trivially upgrade the +// smaller type +template +CONSTEXPR14 typename std::conditional= I2, FixedPoint, FixedPoint>::type +operator+(FixedPoint lhs, FixedPoint rhs) { + + using T = typename std::conditional= I2, FixedPoint, FixedPoint>::type; + + const T l = T::from_base(lhs.to_raw()); + const T r = T::from_base(rhs.to_raw()); + return l + r; +} + +template +CONSTEXPR14 typename std::conditional= I2, FixedPoint, FixedPoint>::type +operator-(FixedPoint lhs, FixedPoint rhs) { + + using T = typename std::conditional= I2, FixedPoint, FixedPoint>::type; + + const T l = T::from_base(lhs.to_raw()); + const T r = T::from_base(rhs.to_raw()); + return l - r; +} + +template +CONSTEXPR14 typename std::conditional= I2, FixedPoint, FixedPoint>::type +operator*(FixedPoint lhs, FixedPoint rhs) { + + using T = typename std::conditional= I2, FixedPoint, FixedPoint>::type; + + const T l = T::from_base(lhs.to_raw()); + const T r = T::from_base(rhs.to_raw()); + return l * r; +} + +template +CONSTEXPR14 typename std::conditional= I2, FixedPoint, FixedPoint>::type +operator/(FixedPoint lhs, FixedPoint rhs) { + + using T = typename std::conditional= I2, FixedPoint, FixedPoint>::type; + + const T l = T::from_base(lhs.to_raw()); + const T r = T::from_base(rhs.to_raw()); + return l / r; +} + +template +std::ostream& operator<<(std::ostream& os, FixedPoint f) { + os << f.to_double(); + return os; +} + +// basic math operators +template +CONSTEXPR14 FixedPoint operator+(FixedPoint lhs, FixedPoint rhs) { + lhs += rhs; + return lhs; +} +template +CONSTEXPR14 FixedPoint operator-(FixedPoint lhs, FixedPoint rhs) { + lhs -= rhs; + return lhs; +} +template +CONSTEXPR14 FixedPoint operator*(FixedPoint lhs, FixedPoint rhs) { + lhs *= rhs; + return lhs; +} +template +CONSTEXPR14 FixedPoint operator/(FixedPoint lhs, FixedPoint rhs) { + lhs /= rhs; + return lhs; +} + +template ::value>::type> +CONSTEXPR14 FixedPoint operator+(FixedPoint lhs, Number rhs) { + lhs += FixedPoint(rhs); + return lhs; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator-(FixedPoint lhs, Number rhs) { + lhs -= FixedPoint(rhs); + return lhs; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator*(FixedPoint lhs, Number rhs) { + lhs *= FixedPoint(rhs); + return lhs; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator/(FixedPoint lhs, Number rhs) { + lhs /= FixedPoint(rhs); + return lhs; +} + +template ::value>::type> +CONSTEXPR14 FixedPoint operator+(Number lhs, FixedPoint rhs) { + FixedPoint tmp(lhs); + tmp += rhs; + return tmp; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator-(Number lhs, FixedPoint rhs) { + FixedPoint tmp(lhs); + tmp -= rhs; + return tmp; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator*(Number lhs, FixedPoint rhs) { + FixedPoint tmp(lhs); + tmp *= rhs; + return tmp; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator/(Number lhs, FixedPoint rhs) { + FixedPoint tmp(lhs); + tmp /= rhs; + return tmp; +} + +// shift operators +template ::value>::type> +CONSTEXPR14 FixedPoint operator<<(FixedPoint lhs, Integer rhs) { + lhs <<= rhs; + return lhs; +} +template ::value>::type> +CONSTEXPR14 FixedPoint operator>>(FixedPoint lhs, Integer rhs) { + lhs >>= rhs; + return lhs; +} + +// comparison operators +template ::value>::type> +constexpr bool operator>(FixedPoint lhs, Number rhs) { + return lhs > FixedPoint(rhs); +} +template ::value>::type> +constexpr bool operator<(FixedPoint lhs, Number rhs) { + return lhs < FixedPoint(rhs); +} +template ::value>::type> +constexpr bool operator>=(FixedPoint lhs, Number rhs) { + return lhs >= FixedPoint(rhs); +} +template ::value>::type> +constexpr bool operator<=(FixedPoint lhs, Number rhs) { + return lhs <= FixedPoint(rhs); +} +template ::value>::type> +constexpr bool operator==(FixedPoint lhs, Number rhs) { + return lhs == FixedPoint(rhs); +} +template ::value>::type> +constexpr bool operator!=(FixedPoint lhs, Number rhs) { + return lhs != FixedPoint(rhs); +} + +template ::value>::type> +constexpr bool operator>(Number lhs, FixedPoint rhs) { + return FixedPoint(lhs) > rhs; +} +template ::value>::type> +constexpr bool operator<(Number lhs, FixedPoint rhs) { + return FixedPoint(lhs) < rhs; +} +template ::value>::type> +constexpr bool operator>=(Number lhs, FixedPoint rhs) { + return FixedPoint(lhs) >= rhs; +} +template ::value>::type> +constexpr bool operator<=(Number lhs, FixedPoint rhs) { + return FixedPoint(lhs) <= rhs; +} +template ::value>::type> +constexpr bool operator==(Number lhs, FixedPoint rhs) { + return FixedPoint(lhs) == rhs; +} +template ::value>::type> +constexpr bool operator!=(Number lhs, FixedPoint rhs) { + return FixedPoint(lhs) != rhs; +} + +} // namespace Common + +#undef CONSTEXPR14 + +#endif -- cgit v1.2.3