3
\$\begingroup\$

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:

  1. Header only
  2. Modulo arithmetic for all operations
  3. No undefined behaviour possible when this type is used (given that it is not abused)
  4. Should be hard to use this type wrong
  5. Operations are implemented efficient
  6. no implicit conversion from fixed to built-in types
  7. 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.

\$\endgroup\$
2
  • \$\begingroup\$ Do you know about the "spaceship" operator? Which C++ dialect is this targeting? \$\endgroup\$
    – JDługosz
    Commented May 25, 2021 at 14:22
  • \$\begingroup\$ @JDługosz C++14, spaceship operator is no possibilty thus I fear. \$\endgroup\$
    – tommsch
    Commented May 25, 2021 at 14:31

2 Answers 2

1
\$\begingroup\$

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.

In my implementation (which is Decimal, not power-of-two, and has different design requirements for many of your points), I decided to provide operator+ between identical types only. It would be confusing to have the result be a type that differs from either of the arguments and could lead to use of more distinct types than intended. On the other hand, operator+= does allow mixed types, as the result is implicitly the type of the left-hand operand, and it gives a compile-time error if the right-hand operand is larger in either size to the left of the decimal or size to the right of the decimal.

As for code duplication, I rely on operator= (only) to do the heavy lifting of implicitly widening the type. The addition and subtraction operators call that to condition the right-hand argument.

As for built-in integer type as one argument: are you doing size match checking? If you have, for example a 32-bit int with 5 implied fractional bits, then adding a regular 32-bit value will be too large to the left of the binary point. In my library, I disallow this, but constexpr constructors let me easily mark the regular int with a size that's smaller than the int. E.g. d1 += decimal<3,0>(n); tells it that n has (at most) three decimal digits (recall my library is decimal based) rather than 9 or 10 that would fit in a regular int. Thus, is passes the width checking and automatically widens to the declared type of d1 which is, say, 5 digits to the left and 4 to the right of the decimal point and represented in a 32-bit value.


Doing the underlying work as unsigned integers will be less efficient (less ability to optimize the inlined functions) as using signed values.


Why are your functions static inline instead of just inline? That is not normal.


You have namespaces nested as detail::fixed rather than the other way around? Also odd. Hmm, I see fixed is a class template that is not inside a namespace at all! You should put everything inside a namespace to prevent clashes.


template<typename OUT,typename IN> static inline constexpr OUT safe_numeric_cast( IN in ) {

It's hard to read with the template prefix and following declaration on one line like that. And again, it's quite odd to see inline static. Try:

template<typename OUT,typename IN>
constexpr OUT safe_numeric_cast ( IN in ) 
{

Furthermore, the use of IN and OUT may conflict with other libraries. I've seen those defined as macros that are used to mark parameters as with languages such as Ada or COM/CORBA marshalling.

The inline is not needed here to allow use inside a header. A template is not a function, just like how a cookie-cutter is not a cookie. There is no code there; and the instantiation of the template, which is a function, understands being instantiated in multiple translation units. Note that inline is no longer a hint used to ask to compiler to inline the function — the compiler decides for itself what to inline or not. It is only used to allow definitions to appear in headers so that multiple copies are merged. On the other hand, static means that the instantiated function will not be shared among different translation units, which is the exact opposite in meaning. And why would you want to do that?



\$\endgroup\$
1
  • \$\begingroup\$ 1. signed/unsigned: Why are unsigned ints slower than signed ints? Can you give some reference? 2. inline: I saw in godbolt, that gcc inlines more when the inline keyword is present (not at this example, but on some others). Thats why I added tham. \$\endgroup\$
    – tommsch
    Commented May 25, 2021 at 19:49
1
\$\begingroup\$
fixed<TOTAL,SHIFT,SIGN>

The only time anything other than shift would be useful is if you allowed more exotic sign methods and/or total was not restricted to power 2. Instead you should just do this (note while you tag this as c++14 I'm going to use concepts, using std::enable_if<T>* = nullptr is way too involved on mobile, swap to enable if on your implementation, though even redhat 7 supports c++20 so it's extremely unlikely you're actually stuck on c++14 in 2023, and CUDA supports c++20):

template<std::integral T, std::size_t shift>
class fixed{
...
}

Both sign and total size of type can be derived from just these two parameters. You can also use this to support arbitrary integer sizes if you create arbitrary integers bit length types.

Static asserts and sizeof() * 8 or numeric limits digit to make sure shift is in bounds at compile time.

Don't let users shift your fixed points, force them to cast to the underlying type/ raw units if they want that. If they want to divide, let them divide, the compiler will figure out when shifts are better for integers than you can.

Comparisons should be done the safe way, not the crappy default way, don't rely on default comparison operators. C++ auto casts signed integers to unsigned I'm comparisons. Use c++ 20s <utility> comparisons (cmp_eq etc...) Or make them yourself.

I disagree about the previous authors advice about +, it's only confusing if it's unsafe. A Q32.32 is going to be able to support safe addition with everything signed up to int32, unsigned uint16. Q33.31 can support every integer up to 32bits. You can even have good static asserts messages on failure. Casting rules should be larger type, and fail when you could have invalid arithmetic.

If you have access to consteval, you can support strictly larger set of assignments += etc... and error on larger numbers if you know your at compile time, but this is c++23.

I would also constexpr every function/operator except stream since you should have support for that in c++ 20. You should also be using [[nodiscard]] on every function that returns here, since you shouldn't be discarding output.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.