I am implementing a fixed point type, which mostly is used to be able store numbers as multiples of some base (power of 2). Apart from that, the type should be able to replace double/float values without the need of modifying some code. In its current implementation only basic arithmetic operations are possible but it should not be hard to extend the type.
I stripped away a lot of code which repeats other code - e.g. in the following only operator< is defined; all other comparison operators are defined in the same way.
The implementation trusts a lot that the compiler optimizes most of the code - e.g. instead of shift operations I wrote multiplications.
Things I want from this type:
- Header only
- Modulo arithmetic for all operations
- No undefined behaviour possible when this type is used (given that it is not abused)
- Should be hard to use this type wrong
- Operations are implemented efficient
- no implicit conversion from
fixedto built-in types - Radix point can be "outside" of the range of underlying bits - e.g. fixed<8,10>, which has range -2^17 to 2^17-1, with an ulp of 2^10 is possible.
For points 1, 2, 4 and 7 I am quite sure I succeeded, for the other points I am nut sure.
Target Version
- C++14 Since this libarary must also be usable for CUDA and in the rest of the codebase there are problems with C++17 and Cuda.
Things I don't like currently
I want most binary functions (operator+, etc...) to be compatible with two fixed objects, as well with one fixed object and one built-in arithmetic type - e.g. fixed + fixed, fixed + int, int + fixed. This currently leads to a lot of code duplication which I would like to get rid of.
Unit Tests
I wrote a lot of unit tests too, which I can always post if wanted. The unit tests use code from other parts of my projects too, thus I would have to rewrite them to a large extent in order to be able to post them here
#ifndef FIXED_HPP
#define FIXED_HPP
/**
* This is an implementation of a fixed point type
* Usage: fixed<TOTAL,SHIFT,SIGN> value
* TOTAL integer, number of total bits of underlying type, must be 8,16,32 or 64
* SHIFT integer, defines how much the radix point is shifted to the right. Can be negative.
* SIGN enum class signed_e, default=signed_e:signed, defines whether the type is signed or not.
* T (experimental) underlying type, default = determined by TOTAL
*
* Implemented operations:
* all casts to other basic types
* +, -, ~, !, >>, <<, as well as the operators +=, -=, ...
* ++ and -- operators are only defined when the number one can be represented
*
* Notes:
* In Debug mode, when a fixed object is created using a value, it is checked whether the value is in the proper range.
* All (subsequent) calculations are done using 2-complements unsigned integers, and thus, wrap around.
*/
#include <cassert>
#include <cmath>
#include <cstdint>
#include <limits>
#include <ostream>
#include <type_traits>
namespace detail { namespace fixed {
static inline constexpr double pow2_worker( double res, int n ) {
if ( n<0 ) {
return pow2_worker( res/2., n+1 );
} else if ( n>0 ) {
return pow2_worker( res*2., n-1 );
} else {
return res;
}
}
} }
static inline constexpr double pow2( int n ) {
return detail::fixed::pow2_worker( 1, n );
}
template<typename OUT,typename IN> static inline constexpr OUT safe_numeric_cast( IN in ) {
// taken from stackoverflow.com/questions/25857843
if ( std::isnan(in) ) {
return 0;
}
int exp;
std::frexp( in, &exp );
if( std::isfinite(in) && exp<= 63 ) {
return static_cast<int64_t>( in );
} else {
return std::signbit( in ) ? std::numeric_limits<int64_t>::min() : std::numeric_limits<int64_t>::max();
}
}
template<typename T>
static inline constexpr T rightshift( T value, int8_t shift ) {
static_assert( ((-4)>>1) == -2, "This library assumes sign-extending right shift" );
assert( sizeof(value)*8 >= (shift>0?shift:-shift) );
if ( shift>0 ) {
return value >> shift;
} else if ( shift<0 ) {
return value << -shift;
} else {
return value;
}
}
enum class signed_e {
signed_t, unsigned_t
};
template <int TOTAL, int SHIFT, signed_e SIGN, typename T> class fixed;
template<typename Number=long long> inline constexpr
void inrange( Number n, int TOTAL, int SHIFT, signed_e S ) noexcept {
auto I = TOTAL + SHIFT;
assert( ((void)"(Out of range) Given number not representable in target format",
S==signed_e::signed_t ?
n >= -pow2( I-1 ) && n <= pow2( I-1 ) - pow2( SHIFT ) :
n >= 0 && n <= pow2( I ) - pow2( SHIFT )
) );
}
namespace detail { namespace fixed {
struct NoScale {};
template <int T,signed_e S> struct type_from_size { // unspecialized type, compilation fails if this is chosen
};
template <> struct type_from_size<8,signed_e::signed_t> {
using value_type = uint8_t;
};
template <> struct type_from_size<8,signed_e::unsigned_t> {
using value_type = uint8_t;
};
template <> struct type_from_size<16,signed_e::signed_t> {
using value_type = uint16_t;
};
// etc...
} }
template<int TOTAL, int SHIFT=TOTAL/2, signed_e SIGN=signed_e::signed_t, typename T = typename detail::fixed::type_from_size<TOTAL,SIGN>::value_type>
class fixed {
public:
/// member variables
using base_type = T;
using compare_type = typename std::conditional< SIGN==signed_e::signed_t, typename std::make_signed<base_type>::type, base_type >::type;
base_type data_;
static_assert( -1 == ~0, "This library assumes 2-complement integers" );
/// constructors
fixed() noexcept = default;
fixed( const fixed & ) noexcept = default;
fixed& operator=( const fixed & ) noexcept = default;
template <class Number> inline constexpr
fixed( Number n, typename std::enable_if<std::is_arithmetic<Number>::value>::type* = nullptr ) noexcept :
data_( safe_numeric_cast<base_type>(n * pow2(-SHIFT)) ) {
inrange( n );
}
inline constexpr
fixed( base_type n, const detail::fixed::NoScale & ) noexcept : data_(n) {
}
inline constexpr static
fixed from_base( base_type n ) noexcept {
return fixed( n, detail::fixed::NoScale() );
}
/// helper functions
public:
template<typename Number> inline constexpr
void inrange( Number n ) const noexcept {
::inrange<Number>( n, TOTAL, SHIFT, SIGN );
}
/// comparison operators
inline constexpr
bool operator<( fixed rhs ) const noexcept {
return static_cast<compare_type>( data_ ) < static_cast<compare_type>( rhs.data_ );
}
// etc...
/// unary operators
inline constexpr
bool operator!() const noexcept {
return !data_;
}
// etc...
inline constexpr
fixed & operator++() noexcept {
static_assert( SHIFT<=0 && -SHIFT<=TOTAL, "++ operator not possible" );
data_ += pow2( -SHIFT );
return *this;
}
inline constexpr
const fixed operator++( int ) noexcept {
static_assert( SHIFT<=0 && -SHIFT<=TOTAL, "++ operator not possible" );
fixed tmp(*this);
data_ += pow2( -SHIFT );
return tmp;
}
//etc...
public: // basic math operators
inline constexpr
fixed& operator+=( fixed n ) noexcept {
data_ += n.data_;
return *this;
}
inline constexpr
fixed& operator-=( fixed n ) noexcept {
data_ -= n.data_;
return *this;
}
public:
/// binary math operators
inline constexpr
fixed& operator&=( fixed n ) noexcept {
data_ &= n.data_;
return *this;
}
//etc...
/// conversion to basic types
template<typename OUT, typename std::enable_if_t<std::is_integral<OUT>::value,bool> = false >
inline constexpr explicit
operator OUT () const noexcept {
return rightshift( static_cast<OUT>(data_), -SHIFT );
}
template<typename OUT, typename std::enable_if_t<std::is_floating_point<OUT>::value,bool> = false >
inline constexpr explicit
operator OUT () const noexcept {
return static_cast<OUT>( data_ ) * static_cast<OUT>( pow2(SHIFT) );
}
inline constexpr
base_type raw() const noexcept {
return data_;
}
public:
inline constexpr
void swap( fixed &rhs ) noexcept {
using std::swap;
swap( data_, rhs.data_ );
}
};
template <int T, int SH, signed_e SI>
std::ostream &operator<<( std::ostream &os, fixed<T,SH,SI> f ) {
os << static_cast<double>( f );
return os;
}
// basic math operators
template <int T, int SH, signed_e SI> inline constexpr
fixed<T,SH,SI> operator+( fixed<T,SH,SI> lhs, fixed<T,SH,SI> rhs ) noexcept {
lhs += rhs;
return lhs;
}
template <int T, int SH, signed_e SI, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> inline constexpr
fixed<T,SH,SI> operator+( fixed<T,SH,SI> lhs, Number rhs ) noexcept {
lhs += fixed<T,SH,SI>( rhs );
return lhs;
}
template <int T, int SH, signed_e SI, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> inline constexpr
fixed<T,SH,SI> operator+( Number lhs, fixed<T,SH,SI> rhs ) noexcept {
fixed<T,SH,SI> tmp(lhs);
tmp += rhs;
return tmp;
}
//etc...
// shift operators
template <int T, int SH, signed_e SI, class Integer, class = typename std::enable_if<std::is_integral<Integer>::value>::type> inline constexpr
fixed<T,SH,SI> operator<<( fixed<T,SH,SI> lhs, Integer rhs ) noexcept {
lhs <<= rhs;
return lhs;
}
template <int T, int SH, signed_e SI, class Integer, class = typename std::enable_if<std::is_integral<Integer>::value>::type> inline constexpr
fixed<T,SH,SI> operator>>( fixed<T,SH,SI> lhs, Integer rhs ) noexcept {
lhs >>= rhs;
return lhs;
}
// comparison operators
template <int T, int SH, signed_e SI, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> inline constexpr
bool operator<( fixed<T,SH,SI> lhs, Number rhs ) noexcept {
return lhs < fixed<T,SH,SI>( rhs );
}
template <int T, int SH, signed_e SI, class Number, class = typename std::enable_if<std::is_arithmetic<Number>::value>::type> inline constexpr
bool operator<( Number lhs, fixed<T,SH,SI> rhs ) noexcept {
return fixed<T,SH,SI>(lhs) < rhs;
}
namespace std {
/// specialization of std::numeric_limits
template<int TOTAL,int SHIFT,signed_e SIGNED> struct numeric_limits<::fixed<TOTAL,SHIFT,SIGNED>> {
static constexpr bool is_specialized = true;
static constexpr double lowest() noexcept { return SIGNED==signed_e::signed_t ? -pow2( TOTAL + SHIFT - 1 ) : 0; }
static constexpr double max() noexcept { return SIGNED==signed_e::signed_t ? pow2( TOTAL + SHIFT - 1 ) - pow2( SHIFT ) : pow2( TOTAL + SHIFT ) - pow2( SHIFT ); }
// etc.
};
}
int main() {
fixed<16,-8> x = -10;
x+=-2;
auto r = x<-5;
auto y = x + 100;
return (int)x;
}
#endif //FIXED_HPP
Credits
This type is a heavily modified fixed point type written by Evan Teran.
