Main

// 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 <ostream>

#include <exception>

#include <cstddef> // for size_t

#include <cstdint>

#include <type_traits>

namespace numeric {

template <size_t I, size_t F>

class fixed;

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 <size_t T>

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<value_type>::type;

using signed_type = std::make_signed<value_type>::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<value_type>::type;

using signed_type = std::make_signed<value_type>::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<value_type>::type;

using signed_type = std::make_signed<value_type>::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<value_type>::type;

using signed_type = std::make_signed<value_type>::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 <class B, class N>

constexpr B next_to_base(N rhs) {

return static_cast<B>(rhs);

}

struct divide_by_zero : std::exception {

};

template <size_t I, size_t F>

CONSTEXPR14 fixed<I,F> divide(fixed<I, F> numerator, fixed<I, F> denominator, fixed<I,F> &remainder, typename std::enable_if<type_from_size<I+F>::next_size::is_specialized>::type* = nullptr) {

using next_type = typename fixed<I,F>::next_type;

using base_type = typename fixed<I,F>::base_type;

constexpr size_t fractional_bits = fixed<I,F>::fractional_bits;

next_type t(numerator.to_raw());

t <<= fractional_bits;

fixed<I,F> quotient;

quotient = fixed<I,F>::from_base(next_to_base<base_type>(t / denominator.to_raw()));

remainder = fixed<I,F>::from_base(next_to_base<base_type>(t % denominator.to_raw()));

return quotient;

}

template <size_t I, size_t F>

CONSTEXPR14 fixed<I,F> divide(fixed<I,F> numerator, fixed<I,F> denominator, fixed<I,F> &remainder, typename std::enable_if<!type_from_size<I+F>::next_size::is_specialized>::type* = nullptr) {

using base_type = typename fixed<I,F>::base_type;

using unsigned_type = typename fixed<I,F>::unsigned_type;

constexpr int bits = fixed<I,F>::total_bits;

if(denominator == 0) {

throw divide_by_zero();

} else {

int sign = 0;

fixed<I,F> 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 = fixed<I,F>::from_base((answer << F) | lo);

remainder = n;

if(sign) {

quotient = -quotient;

}

return quotient;

}

}

// this is the usual implementation of multiplication

template <size_t I, size_t F>

CONSTEXPR14 fixed<I,F> multiply(fixed<I, F> lhs, fixed<I, F> rhs, typename std::enable_if<type_from_size<I+F>::next_size::is_specialized>::type* = nullptr) {

using next_type = typename fixed<I,F>::next_type;

using base_type = typename fixed<I,F>::base_type;

constexpr size_t fractional_bits = fixed<I,F>::fractional_bits;

next_type t (static_cast<next_type>(lhs.to_raw()) * static_cast<next_type>(rhs.to_raw()));

t >>= fractional_bits;

return fixed<I,F>::from_base(next_to_base<base_type>(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 <size_t I, size_t F>

CONSTEXPR14 fixed<I,F> multiply(fixed<I, F> lhs, fixed<I, F> rhs, typename std::enable_if<!type_from_size<I+F>::next_size::is_specialized>::type* = nullptr) {

using base_type = typename fixed<I,F>::base_type;

constexpr size_t fractional_bits = fixed<I,F>::fractional_bits;

constexpr base_type integer_mask = fixed<I,F>::integer_mask;

constexpr base_type fractional_mask = fixed<I,F>::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 fixed<I,F>::from_base((x1 << fractional_bits) + (x3 + x2) + (x4 >> fractional_bits));

}

}

template <size_t I, size_t F>

class fixed {

static_assert(detail::type_from_size<I + F>::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<total_bits>;

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<unsigned_type>(~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

fixed() = default;

fixed(const fixed &) = default;

fixed& operator=(const fixed &) = default;

template <class Number>

constexpr fixed(Number n, typename std::enable_if<std::is_arithmetic<Number>::value>::type* = nullptr) : data_(static_cast<base_type>(n * one)) {

}

public: // conversion

template <size_t I2, size_t F2>

CONSTEXPR14 explicit fixed(fixed<I2, F2> other) {

static_assert(I2 <= I && F2 <= F, "Scaling conversion can only upgrade types");

using T = fixed<I2,F2>;

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 fixed point object from

// a native type without scaling

// use "fixed::from_base" in order to perform this.

struct NoScale {};

constexpr fixed(base_type n, const NoScale &) : data_(n) {

}

public:

constexpr static fixed from_base(base_type n) {

return fixed(n, NoScale());

}

public: // comparison operators

constexpr bool operator==(fixed rhs) const {

return data_ == rhs.data_;

}

constexpr bool operator!=(fixed rhs) const {

return data_ != rhs.data_;

}

constexpr bool operator<(fixed rhs) const {

return data_ < rhs.data_;

}

constexpr bool operator>(fixed rhs) const {

return data_ > rhs.data_;

}

constexpr bool operator<=(fixed rhs) const {

return data_ <= rhs.data_;

}

constexpr bool operator>=(fixed rhs) const {

return data_ >= rhs.data_;

}

public: // unary operators

constexpr bool operator!() const {

return !data_;

}

constexpr fixed 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 fixed::from_base(~data_);

}

constexpr fixed operator-() const {

return fixed::from_base(-data_);

}

constexpr fixed operator+() const {

return fixed::from_base(+data_);

}

CONSTEXPR14 fixed &operator++() {

data_ += one;

return *this;

}

CONSTEXPR14 fixed &operator--() {

data_ -= one;

return *this;

}

CONSTEXPR14 fixed operator++(int) {

fixed tmp(*this);

data_ += one;

return tmp;

}

CONSTEXPR14 fixed operator--(int) {

fixed tmp(*this);

data_ -= one;

return tmp;

}

public: // basic math operators

CONSTEXPR14 fixed& operator+=(fixed n) {

data_ += n.data_;

return *this;

}

CONSTEXPR14 fixed& operator-=(fixed n) {

data_ -= n.data_;

return *this;

}

CONSTEXPR14 fixed& operator*=(fixed n) {

return assign(detail::multiply(*this, n));

}

CONSTEXPR14 fixed& operator/=(fixed n) {

fixed temp;

return assign(detail::divide(*this, n, temp));

}

private:

CONSTEXPR14 fixed& assign(fixed 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 fixed& operator&=(fixed n) {

data_ &= n.data_;

return *this;

}

CONSTEXPR14 fixed& operator|=(fixed n) {

data_ |= n.data_;

return *this;

}

CONSTEXPR14 fixed& operator^=(fixed n) {

data_ ^= n.data_;

return *this;

}

template <class Integer, class = typename std::enable_if<std::is_integral<Integer>::value>::type>

CONSTEXPR14 fixed& operator>>=(Integer n) {

data_ >>= n;

return *this;

}

template <class Integer, class = typename std::enable_if<std::is_integral<Integer>::value>::type>

CONSTEXPR14 fixed& operator<<=(Integer n) {

data_ <<= n;

return *this;

}

public: // conversion to basic types

constexpr int to_int() const {

return (data_ & integer_mask) >> fractional_bits;

}

constexpr unsigned int to_uint() const {

return static_cast<unsigned int>(data_ & integer_mask) >> fractional_bits;

}

constexpr float to_float() const {

return static_cast<float>(data_) / fixed::one;

}

constexpr double to_double() const {

return static_cast<double>(data_) / fixed::one;

}

constexpr base_type to_raw() const {

return data_;

}

public:

CONSTEXPR14 void swap(fixed &rhs) {

using std::swap;

swap(data_, rhs.data_);

}

public:

base_type data_ = 0;

};

// if we have the same fractional portion, but differing integer portions, we trivially upgrade the smaller type

template <size_t I1, size_t I2, size_t F>

CONSTEXPR14 typename std::conditional<I1 >= I2, fixed<I1,F>, fixed<I2,F>>::type operator+(fixed<I1, F> lhs, fixed<I2, F> rhs) {

using T = typename std::conditional<

I1 >= I2,

fixed<I1,F>,

fixed<I2,F>

>::type;

const T l = T::from_base(lhs.to_raw());

const T r = T::from_base(rhs.to_raw());

return l + r;

}

template <size_t I1, size_t I2, size_t F>

CONSTEXPR14 typename std::conditional<I1 >= I2, fixed<I1,F>, fixed<I2,F>>::type operator-(fixed<I1, F> lhs, fixed<I2, F> rhs) {

using T = typename std::conditional<

I1 >= I2,

fixed<I1,F>,

fixed<I2,F>

>::type;

const T l = T::from_base(lhs.to_raw());

const T r = T::from_base(rhs.to_raw());

return l - r;

}

template <size_t I1, size_t I2, size_t F>

CONSTEXPR14 typename std::conditional<I1 >= I2, fixed<I1,F>, fixed<I2,F>>::type operator*(fixed<I1, F> lhs, fixed<I2, F> rhs) {

using T = typename std::conditional<

I1 >= I2,

fixed<I1,F>,

fixed<I2,F>

>::type;

const T l = T::from_base(lhs.to_raw());

const T r = T::from_base(rhs.to_raw());

return l * r;

}

template <size_t I1, size_t I2, size_t F>

CONSTEXPR14 typename std::conditional<I1 >= I2, fixed<I1,F>, fixed<I2,F>>::type operator/(fixed<I1, F> lhs, fixed<I2, F> rhs) {

using T = typename std::conditional<

I1 >= I2,

fixed<I1,F>,

fixed<I2,F>

>::type;

const T l = T::from_base(lhs.to_raw());

const T r = T::from_base(rhs.to_raw());

return l / r;

}

template <size_t I, size_t F>

std::ostream &operator<<(std::ostream &os, fixed<I, F> f) {

os << f.to_double();

return os;

}

// basic math operators

template <size_t I, size_t F> CONSTEXPR14 fixed<I, F> operator+(fixed<I, F> lhs, fixed<I, F> rhs) { lhs += rhs; return lhs; }

template <size_t I, size_t F> CONSTEXPR14 fixed<I, F> operator-(fixed<I, F> lhs, fixed<I, F> rhs) { lhs -= rhs; return lhs; }

template <size_t I, size_t F> CONSTEXPR14 fixed<I, F> operator*(fixed<I, F> lhs, fixed<I, F> rhs) { lhs *= rhs; return lhs; }

template <size_t I, size_t F> CONSTEXPR14 fixed<I, F> operator/(fixed<I, F> lhs, fixed<I, F> rhs) { lhs /= rhs; return lhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator+(fixed<I, F> lhs, Number rhs) { lhs += fixed<I, F>(rhs); return lhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator-(fixed<I, F> lhs, Number rhs) { lhs -= fixed<I, F>(rhs); return lhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator*(fixed<I, F> lhs, Number rhs) { lhs *= fixed<I, F>(rhs); return lhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator/(fixed<I, F> lhs, Number rhs) { lhs /= fixed<I, F>(rhs); return lhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator+(Number lhs, fixed<I, F> rhs) { fixed<I, F> tmp(lhs); tmp += rhs; return tmp; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator-(Number lhs, fixed<I, F> rhs) { fixed<I, F> tmp(lhs); tmp -= rhs; return tmp; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator*(Number lhs, fixed<I, F> rhs) { fixed<I, F> tmp(lhs); tmp *= rhs; return tmp; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> CONSTEXPR14 fixed<I, F> operator/(Number lhs, fixed<I, F> rhs) { fixed<I, F> tmp(lhs); tmp /= rhs; return tmp; }

// shift operators

template <size_t I, size_t F, class Integer, class = typename std::enable_if<std::is_integral<Integer>::value>::type> CONSTEXPR14 fixed<I, F> operator<<(fixed<I, F> lhs, Integer rhs) { lhs <<= rhs; return lhs; }

template <size_t I, size_t F, class Integer, class = typename std::enable_if<std::is_integral<Integer>::value>::type> CONSTEXPR14 fixed<I, F> operator>>(fixed<I, F> lhs, Integer rhs) { lhs >>= rhs; return lhs; }

// comparison operators

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator>(fixed<I, F> lhs, Number rhs) { return lhs > fixed<I, F>(rhs); }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator<(fixed<I, F> lhs, Number rhs) { return lhs < fixed<I, F>(rhs); }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator>=(fixed<I, F> lhs, Number rhs) { return lhs >= fixed<I, F>(rhs); }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator<=(fixed<I, F> lhs, Number rhs) { return lhs <= fixed<I, F>(rhs); }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator==(fixed<I, F> lhs, Number rhs) { return lhs == fixed<I, F>(rhs); }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator!=(fixed<I, F> lhs, Number rhs) { return lhs != fixed<I, F>(rhs); }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator>(Number lhs, fixed<I, F> rhs) { return fixed<I, F>(lhs) > rhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator<(Number lhs, fixed<I, F> rhs) { return fixed<I, F>(lhs) < rhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator>=(Number lhs, fixed<I, F> rhs) { return fixed<I, F>(lhs) >= rhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator<=(Number lhs, fixed<I, F> rhs) { return fixed<I, F>(lhs) <= rhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator==(Number lhs, fixed<I, F> rhs) { return fixed<I, F>(lhs) == rhs; }

template <size_t I, size_t F, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> constexpr bool operator!=(Number lhs, fixed<I, F> rhs) { return fixed<I, F>(lhs) != rhs; }

}

#undef CONSTEXPR14

#endif

#ifndef FPM_FIXED_HPP

#define FPM_FIXED_HPP

#include <cassert>

#include <cmath>

#include <cstdint>

#include <functional>

#include <limits>

#include <type_traits>

namespace fpm

{

//! Fixed-point number type

//! \tparam BaseType the base integer type used to store the fixed-point number. This can be a signed or unsigned type.

//! \tparam IntermediateType the integer type used to store intermediate results during calculations.

//! \tparam FractionBits the number of bits of the BaseType used to store the fraction

template <typename BaseType, typename IntermediateType, unsigned int FractionBits>

class fixed

{

static_assert(std::is_integral<BaseType>::value, "BaseType must be an integral type");

static_assert(FractionBits > 0, "FractionBits must be greater than zero");

static_assert(FractionBits <= sizeof(BaseType) * 8, "BaseType must at least be able to contain entire fraction");

static_assert(FractionBits <= 62, "Fraction may be no more than 62 bits");

static_assert(sizeof(IntermediateType) > sizeof(BaseType), "IntermediateType must be larger than BaseType");

static_assert(std::is_signed<IntermediateType>::value == std::is_signed<BaseType>::value, "IntermediateType must have same signedness as BaseType");

static constexpr BaseType FRACTION_MULT = BaseType(1) << FractionBits;

struct raw_construct_tag {};

constexpr inline fixed(BaseType val, raw_construct_tag) noexcept : m_value(val) {}

public:

inline fixed() noexcept {}

// Converts an integral number to the fixed-point type.

// Like static_cast, this truncates bits that don't fit.

template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline explicit fixed(T val) noexcept

: m_value(static_cast<BaseType>(val * FRACTION_MULT))

{}

// Converts an floating-point number to the fixed-point type.

// Like static_cast, this truncates bits that don't fit.

template <typename T, typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>

constexpr inline explicit fixed(T val) noexcept

: m_value(static_cast<BaseType>((val >= 0.0) ? (val * FRACTION_MULT + T{0.5}) : (val * FRACTION_MULT - T{0.5})))

{}

// Constructs from another fixed-point type with possibly different underlying representation.

// Like static_cast, this truncates bits that don't fit.

template <typename B, typename I, unsigned int F>

constexpr inline explicit fixed(fixed<B,I,F> val) noexcept

: m_value(from_fixed_point<F>(val.raw_value()).raw_value())

{}

// Explicit conversion to a floating-point type

template <typename T, typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>

constexpr inline explicit operator T() const noexcept

{

return static_cast<T>(m_value) / FRACTION_MULT;

}

// Explicit conversion to an integral type

template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline explicit operator T() const noexcept

{

return static_cast<T>(m_value / FRACTION_MULT);

}

// Returns the raw underlying value of this type.

// Do not use this unless you know what you're doing.

constexpr inline BaseType raw_value() const noexcept

{

return m_value;

}

//! Constructs a fixed-point number from another fixed-point number.

//! \tparam NumFractionBits the number of bits used by the fraction in \a value.

//! \param value the integer fixed-point number

template <unsigned int NumFractionBits, typename T, typename std::enable_if<(NumFractionBits > FractionBits)>::type* = nullptr>

static constexpr inline fixed from_fixed_point(T value) noexcept

{

// To correctly round the last bit in the result, we need one more bit of information.

// We do this by multiplying by two before dividing and adding the LSB to the real result.

return fixed(static_cast<BaseType>(

value / (T(1) << (NumFractionBits - FractionBits)) +

(value / (T(1) << (NumFractionBits - FractionBits - 1)) % 2)),

raw_construct_tag{});

}

template <unsigned int NumFractionBits, typename T, typename std::enable_if<(NumFractionBits <= FractionBits)>::type* = nullptr>

static constexpr inline fixed from_fixed_point(T value) noexcept

{

return fixed(static_cast<BaseType>(

value * (T(1) << (FractionBits - NumFractionBits))),

raw_construct_tag{});

}

// Constructs a fixed-point number from its raw underlying value.

// Do not use this unless you know what you're doing.

static constexpr inline fixed from_raw_value(BaseType value) noexcept

{

return fixed(value, raw_construct_tag{});

}

//

// Constants

//

static constexpr fixed e() { return from_fixed_point<61>(6267931151224907085ll); }

static constexpr fixed pi() { return from_fixed_point<61>(7244019458077122842ll); }

static constexpr fixed half_pi() { return from_fixed_point<62>(7244019458077122842ll); }

static constexpr fixed two_pi() { return from_fixed_point<60>(7244019458077122842ll); }

//

// Arithmetic member operators

//

constexpr inline fixed operator-() const noexcept

{

return fixed::from_raw_value(-m_value);

}

inline fixed& operator+=(const fixed& y) noexcept

{

m_value += y.m_value;

return *this;

}

template <typename I, typename std::enable_if<std::is_integral<I>::value>::type* = nullptr>

inline fixed& operator+=(I y) noexcept

{

m_value += y * FRACTION_MULT;

return *this;

}

inline fixed& operator-=(const fixed& y) noexcept

{

m_value -= y.m_value;

return *this;

}

template <typename I, typename std::enable_if<std::is_integral<I>::value>::type* = nullptr>

inline fixed& operator-=(I y) noexcept

{

m_value -= y * FRACTION_MULT;

return *this;

}

inline fixed& operator*=(const fixed& y) noexcept

{

// Normal fixed-point multiplication is: x * y / 2**FractionBits.

// To correctly round the last bit in the result, we need one more bit of information.

// We do this by multiplying by two before dividing and adding the LSB to the real result.

auto value = (static_cast<IntermediateType>(m_value) * y.m_value) / (FRACTION_MULT / 2);

m_value = static_cast<BaseType>((value / 2) + (value % 2));

return *this;

}

template <typename I, typename std::enable_if<std::is_integral<I>::value>::type* = nullptr>

inline fixed& operator*=(I y) noexcept

{

m_value *= y;

return *this;

}

inline fixed& operator/=(const fixed& y) noexcept

{

assert(y.m_value != 0);

// Normal fixed-point division is: x * 2**FractionBits / y.

// To correctly round the last bit in the result, we need one more bit of information.

// We do this by multiplying by two before dividing and adding the LSB to the real result.

auto value = (static_cast<IntermediateType>(m_value) * FRACTION_MULT * 2) / y.m_value;

m_value = static_cast<BaseType>((value / 2) + (value % 2));

return *this;

}

template <typename I, typename std::enable_if<std::is_integral<I>::value>::type* = nullptr>

inline fixed& operator/=(I y) noexcept

{

m_value /= y;

return *this;

}

private:

BaseType m_value;

};

//

// Convenience typedefs

//

using fixed_16_16 = fixed<std::int32_t, std::int64_t, 16>;

using fixed_24_8 = fixed<std::int32_t, std::int64_t, 8>;

using fixed_8_24 = fixed<std::int32_t, std::int64_t, 24>;

//

// Addition

//

template <typename B, typename I, unsigned int F>

constexpr inline fixed<B, I, F> operator+(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(x) += y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator+(const fixed<B, I, F>& x, T y) noexcept

{

return fixed<B, I, F>(x) += y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator+(T x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(y) += x;

}

//

// Subtraction

//

template <typename B, typename I, unsigned int F>

constexpr inline fixed<B, I, F> operator-(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(x) -= y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator-(const fixed<B, I, F>& x, T y) noexcept

{

return fixed<B, I, F>(x) -= y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator-(T x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(x) -= y;

}

//

// Multiplication

//

template <typename B, typename I, unsigned int F>

constexpr inline fixed<B, I, F> operator*(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(x) *= y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator*(const fixed<B, I, F>& x, T y) noexcept

{

return fixed<B, I, F>(x) *= y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator*(T x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(y) *= x;

}

//

// Division

//

template <typename B, typename I, unsigned int F>

constexpr inline fixed<B, I, F> operator/(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(x) /= y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator/(const fixed<B, I, F>& x, T y) noexcept

{

return fixed<B, I, F>(x) /= y;

}

template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>

constexpr inline fixed<B, I, F> operator/(T x, const fixed<B, I, F>& y) noexcept

{

return fixed<B, I, F>(x) /= y;

}

//

// Comparison operators

//

template <typename B, typename I, unsigned int F>

constexpr inline bool operator==(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return x.raw_value() == y.raw_value();

}

template <typename B, typename I, unsigned int F>

constexpr inline bool operator!=(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return x.raw_value() != y.raw_value();

}

template <typename B, typename I, unsigned int F>

constexpr inline bool operator<(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return x.raw_value() < y.raw_value();

}

template <typename B, typename I, unsigned int F>

constexpr inline bool operator>(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return x.raw_value() > y.raw_value();

}

template <typename B, typename I, unsigned int F>

constexpr inline bool operator<=(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return x.raw_value() <= y.raw_value();

}

template <typename B, typename I, unsigned int F>

constexpr inline bool operator>=(const fixed<B, I, F>& x, const fixed<B, I, F>& y) noexcept

{

return x.raw_value() >= y.raw_value();

}

namespace detail

{

// Number of base-10 digits required to fully represent a number of bits

static constexpr int max_digits10(int bits)

{

// 8.24 fixed-point equivalent of (int)ceil(bits * std::log10(2));

using T = long long;

return static_cast<int>((T{bits} * 5050445 + (T{1} << 24) - 1) >> 24);

}

// Number of base-10 digits that can be fully represented by a number of bits

static constexpr int digits10(int bits)

{

// 8.24 fixed-point equivalent of (int)(bits * std::log10(2));

using T = long long;

return static_cast<int>((T{bits} * 5050445) >> 24);

}

} // namespace detail

} // namespace fpm

// Specializations for customization points

namespace std

{

template <typename B, typename I, unsigned int F>

struct hash<fpm::fixed<B,I,F>>

{

using argument_type = fpm::fixed<B, I, F>;

using result_type = std::size_t;

result_type operator()(argument_type arg) const noexcept(noexcept(std::declval<std::hash<B>>()(arg.raw_value()))) {

return m_hash(arg.raw_value());

}

private:

std::hash<B> m_hash;

};

template <typename B, typename I, unsigned int F>

struct numeric_limits<fpm::fixed<B,I,F>>

{

static constexpr bool is_specialized = true;

static constexpr bool is_signed = std::numeric_limits<B>::is_signed;

static constexpr bool is_integer = false;

static constexpr bool is_exact = true;

static constexpr bool has_infinity = false;

static constexpr bool has_quiet_NaN = false;

static constexpr bool has_signaling_NaN = false;

static constexpr bool has_denorm = std::denorm_absent;

static constexpr bool has_denorm_loss = false;

static constexpr std::float_round_style round_style = std::round_to_nearest;

static constexpr bool is_iec_559 = false;

static constexpr bool is_bounded = true;

static constexpr bool is_modulo = std::numeric_limits<B>::is_modulo;

static constexpr int digits = std::numeric_limits<B>::digits;

// Any number with `digits10` significant base-10 digits (that fits in

// the range of the type) is guaranteed to be convertible from text and

// back without change. Worst case, this is 0.000...001, so we can only

// guarantee this case. Nothing more.

static constexpr int digits10 = 1;

// This is equal to max_digits10 for the integer and fractional part together.

static constexpr int max_digits10 =

fpm::detail::max_digits10(std::numeric_limits<B>::digits - F) + fpm::detail::max_digits10(F);

static constexpr int radix = 2;

static constexpr int min_exponent = 1 - F;

static constexpr int min_exponent10 = -fpm::detail::digits10(F);

static constexpr int max_exponent = std::numeric_limits<B>::digits - F;

static constexpr int max_exponent10 = fpm::detail::digits10(std::numeric_limits<B>::digits - F);

static constexpr bool traps = true;

static constexpr bool tinyness_before = false;

static constexpr fpm::fixed<B,I,F> lowest() noexcept {

return fpm::fixed<B,I,F>::from_raw_value(std::numeric_limits<B>::lowest());

};

static constexpr fpm::fixed<B,I,F> min() noexcept {

return lowest();

}

static constexpr fpm::fixed<B,I,F> max() noexcept {

return fpm::fixed<B,I,F>::from_raw_value(std::numeric_limits<B>::max());

};

static constexpr fpm::fixed<B,I,F> epsilon() noexcept {

return fpm::fixed<B,I,F>::from_raw_value(1);

};

static constexpr fpm::fixed<B,I,F> round_error() noexcept {

return fpm::fixed<B,I,F>(1) / 2;

};

static constexpr fpm::fixed<B,I,F> denorm_min() noexcept {

return min();

}

};

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_specialized;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_signed;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_integer;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_exact;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::has_infinity;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::has_quiet_NaN;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::has_signaling_NaN;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::has_denorm;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::has_denorm_loss;

template <typename B, typename I, unsigned int F>

constexpr std::float_round_style numeric_limits<fpm::fixed<B,I,F>>::round_style;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_iec_559;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_bounded;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::is_modulo;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::digits;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::digits10;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::max_digits10;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::radix;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::min_exponent;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::min_exponent10;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::max_exponent;

template <typename B, typename I, unsigned int F>

constexpr int numeric_limits<fpm::fixed<B,I,F>>::max_exponent10;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::traps;

template <typename B, typename I, unsigned int F>

constexpr bool numeric_limits<fpm::fixed<B,I,F>>::tinyness_before;

}

#endif

#ifndef FIXED_H_

#define FIXED_H_

#include <cmath>

#include <cstdint>

#include <limits>

#include <type_traits>

template <typename IntegerType, typename FractionalType>

class fixed

{

static_assert(std::is_integral<IntegerType>::value, "IntegerType must be an integral type");

static_assert(std::is_integral<FractionalType>::value, "FractionalType must be an integral type");

static_assert(std::is_signed<IntegerType>::value, "IntegerType must be a signed type");

static_assert(std::is_unsigned<FractionalType>::value, "FractionalType must be an unsigned type");

public:

static constexpr size_t integer_bits = sizeof(IntegerType) * 8;

static constexpr size_t fractional_bits = sizeof(FractionalType) * 8;

static constexpr size_t integer_decimal_digits = std::floor(std::log10(std::numeric_limits<IntegerType>::max()));

static constexpr size_t fractional_decimal_digits = std::floor(std::log10(std::numeric_limits<FractionalType>::max()));

static constexpr size_t MAX_INTEGER_VALUE = (static_cast<uint64_t>(std::pow(10, integer_decimal_digits)) - 1);

static constexpr size_t MIN_INTEGER_VALUE = 0;

static constexpr size_t MAX_FRACTIONAL_VALUE = (static_cast<uint64_t>(std::pow(10, fractional_decimal_digits)) - 1);

static constexpr size_t MIN_FRACTIONAL_VALUE = 0;

fixed()

: m_integer(0), m_fractional(0) {}

fixed(IntegerType integerVal, FractionalType fractionalVal)

: m_integer(integerVal), m_fractional(fractionalVal) {}

// Default copy constructor, and assignment operator

fixed(const fixed&) = default;

fixed& operator=(const fixed&) = default;

void parse(const char* input)

{

}

constexpr inline fixed operator-() const noexcept = delete;

inline fixed& operator+=(const fixed& y) noexcept = delete;

inline fixed& operator-=(const fixed& y) noexcept = delete;

inline fixed& operator*=(const fixed& y) noexcept = delete;

inline fixed& operator/=(const fixed& y) noexcept = delete;

// Comparison operators

template <typename I, typename F>

friend constexpr inline bool operator==(const fixed<I, F>& x, const fixed<I, F>& y) noexcept;

template <typename I, typename F>

friend constexpr inline bool operator!=(const fixed<I, F>& x, const fixed<I, F>& y) noexcept;

template <typename I, typename F>

friend constexpr inline bool operator<(const fixed<I, F>& x, const fixed<I, F>& y) noexcept;

template <typename I, typename F>

friend constexpr inline bool operator>(const fixed<I, F>& x, const fixed<I, F>& y) noexcept;

template <typename I, typename F>

friend constexpr inline bool operator<=(const fixed<I, F>& x, const fixed<I, F>& y) noexcept;

template <typename I, typename F>

friend constexpr inline bool operator>=(const fixed<I, F>& x, const fixed<I, F>& y) noexcept;

private:

IntegerType m_integer;

FractionalType m_fractional;

};

using fixed_64_64 = fixed<int64_t, uint64_t>;

template <typename I, typename F>

constexpr inline bool operator==(const fixed<I, F>& x, const fixed<I, F>& y) noexcept

{

return (x.m_integer == y.m_integer && x.m_fractional == y.m_fractional);

}

template <typename I, typename F>

constexpr inline bool operator!=(const fixed<I, F>& x, const fixed<I, F>& y) noexcept

{

return (! x == y);

}

template <typename I, typename F>

constexpr inline bool operator<(const fixed<I, F>& x, const fixed<I, F>& y) noexcept

{

if (x.m_integer == y.m_integer)

{

return (x.m_fractional < y.m_fractional);

}

else

{

return (x.m_integer < y.m_integer);

}

return false;

}

template <typename I, typename F>

constexpr inline bool operator>(const fixed<I, F>& x, const fixed<I, F>& y) noexcept

{

if (x.m_integer == y.m_integer)

{

return (x.m_fractional > y.m_fractional);

}

else

{

return (x.m_integer > y.m_integer);

}

return false;

}

template <typename I, typename F>

constexpr inline bool operator<=(const fixed<I, F>& x, const fixed<I, F>& y) noexcept

{

if (x.m_integer == y.m_integer)

{

return (x.m_fractional <= y.m_fractional);

}

else

{

return (x.m_integer < y.m_integer);

}

return false;

}

template <typename I, typename F>

constexpr inline bool operator>=(const fixed<I, F>& x, const fixed<I, F>& y) noexcept

{

if (x.m_integer == y.m_integer)

{

return (x.m_fractional > y.m_fractional);

}

else

{

return (x.m_integer > y.m_integer);

}

return false;

}

// Addition

template <typename I, typename F>

constexpr inline fixed<I, F> operator+(const fixed<I, F>& x, const fixed<I, F>& y) noexcept = delete;

// Subtraction

template <typename I, typename F>

constexpr inline fixed<I, F> operator-(const fixed<I, F>& x, const fixed<I, F>& y) noexcept = delete;

// Multiplication

template <typename I, typename F>

constexpr inline fixed<I, F> operator*(const fixed<I, F>& x, const fixed<I, F>& y) noexcept = delete;

// Division

template <typename I, typename F>

constexpr inline fixed<I, F> operator/(const fixed<I, F>& x, const fixed<I, F>& y) noexcept = delete;

#endif // FIXED_H_

#include <cmath>

#include <cstdint>

#include <iomanip>

#include <iostream>

#include "fixed.h"

// g++ fixed_text.cc -o fixed_test

int main(int argc, char** argv)

{

std::cout << "Fixed Type Test Util\n" << std::endl;

fixed_64_64 foobar;

std::cout << "Type size: " << sizeof(fixed_64_64) << std::endl;

std::cout << "Integer decimal digits: " << fixed_64_64::integer_decimal_digits << std::endl;

std::cout << "Fractional decimal digits: " << fixed_64_64::fractional_decimal_digits << std::endl;

std::cout << "Max integer value: " << fixed_64_64::MAX_INTEGER_VALUE << std::endl;

std::cout << "Max fractional value: " << fixed_64_64::MAX_FRACTIONAL_VALUE << std::endl;

//~ double foo = std::pow(10, 18);

//~ std::cout << "Foo: " << std::fixed << std::setprecision(0) << foo << std::endl;

//~ std::cout << "Foo: " << std::fixed << std::setprecision(0) << (static_cast<uint64_t>(foo) - 1) << std::endl;

return 0;

}