7
\$\begingroup\$

I am trying to create a Fixed Point Arithmetics library : I call fixed point a number which has bits reserved for decimal part.
Here is the code :

#ifndef FIXEDPOINTNUMBER_HPP
#define FIXEDPOINTNUMBER_HPP

#include <type_traits>
#include <cstdint>

///////////////////////////////////////////////////////////
////////////////////    DECLARATION    ////////////////////
///////////////////////////////////////////////////////////

/**
* @brief Provides fixed-point number calculations.
* @author Julien Vernay (JDM)
* @date 01-01-2018 (dd-mm-yyyy)
* @arg @c T Underlying type, no overhead
* @arg @c N Number of bits used for decimal part
* @details Fixed-Point Number uses an int value, so we only needs int manipulation with bitshift tricks instead of floating arithmetics.
* @details The underlying value @c val can be represented by : <em>VALUE = val / (2^N)</em>
*/
template<typename T, unsigned char N>
class FixedPointNumber {
public:
FixedPointNumber();                        /**< @brief Constructs with 0 */
FixedPointNumber(T value, bool raw = 0);   /**< @brief Constructs with a @c T value */
FixedPointNumber(float value);             /**< @brief Constructs with a @c float value */

operator T() const;                        /**< @brief Casts to integer value of type @c T (eventually flooring) */
operator float() const;                    /**< @brief Casts to a float value */
T raw() const;                             /**< @brief Returns @c val without any casting */

template<unsigned char N2>
operator FixedPointNumber<T, N2>() const;  /**< @brief Casts to another FixedPointNumber with same underlying type */
template<typename T2>
operator FixedPointNumber<T2, N>() const;  /**< @brief Casts to another FixedPointNumber with same decimal part bits */
template<typename T2, unsigned char N2>
operator FixedPointNumber<T2, N2>() const; /**< @brief Casts to another FixedPointNumber */


FixedPointNumber<T, N>& operator+=(FixedPointNumber<T, N> const& rhs);
FixedPointNumber<T, N>& operator-=(FixedPointNumber<T, N> const& rhs);
FixedPointNumber<T, N>& operator*=(FixedPointNumber<T, N> const& rhs);
FixedPointNumber<T, N>& operator/=(FixedPointNumber<T, N> const& rhs);

FixedPointNumber<T, N> operator-() const;

bool operator==(FixedPointNumber<T, N> const& rhs) const;
bool operator>(FixedPointNumber<T, N> const& rhs) const;

private:
std::enable_if_t<std::is_integral_v<T>, T> val;
};

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator+(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
FixedPointNumber<T, N> operator-(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
FixedPointNumber<T, N> operator*(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
FixedPointNumber<T, N> operator/(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);


template<typename T, unsigned char N>
bool operator!=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
bool operator<(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
bool operator>=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
bool operator<=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);



///////////////////////////////////////////////////////////
////////////////////    DEFINITIONS    ////////////////////
///////////////////////////////////////////////////////////



template<typename T, unsigned char N>
FixedPointNumber<T, N>::FixedPointNumber() : val(0) {}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::FixedPointNumber(T value, bool raw) : val(raw ? value : value << N) {}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::FixedPointNumber(float value) {
std::uint32_t value_int = *reinterpret_cast<std::uint32_t*>(&value);
std::uint32_t mantissa = (value_int & 0x007FFFFF) | 0x00800000;
std::int8_t exponent = ((value_int >> 23) & 0x000000FF) - 150 + N;
if (exponent >= 0)
mantissa <<= exponent;
else
mantissa >>= -exponent;
val = (value_int & 0x80000000) ? -static_cast<T>(mantissa) : static_cast<T>(mantissa);
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::operator T() const {
return val >> (val >= 0) ? N : -N;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::operator float() const {
if (val == 0) return 0.f; //trivial case, needed to prevent infinite loops for CLZ
std::uint32_t mantissa = (val >= 0) ? val : -val;
std::uint8_t fbs = 31; //first bit set : fbs = floor(log2(mantissa))
#if defined(__GNUC__)              //g++ compiler
fbs -= __builtin_clz(mantissa);
#elif defined(_MSC_VER)            //MSVC compiler
fbs -= __lzcnt(mantissa);
#else                              //unknown compiler : using naive algorithm
for (std::uint32_t copy = mantissa; copy & 0x80000000; --fbs) copy <<= 1;
#endif
if (fbs <= 23)
mantissa <<= 23 - fbs;
else
mantissa >>= fbs - 23;
mantissa &= 0x007FFFFF; //keeping mantissa
mantissa |= (val < 0) ? 0x80000000 : 0; //sign
mantissa |= static_cast<std::uint32_t>(127 + fbs - N) << 23; //exponent
return *reinterpret_cast<float*>(&mantissa);
}

template<typename T, unsigned char N>
T FixedPointNumber<T, N>::raw() const {
return val;
}

template<typename T, unsigned char N>
template<unsigned char N2>
FixedPointNumber<T, N>::operator FixedPointNumber<T, N2>() const {
if (N >= N2)
return { static_cast<T>(val >> (N - N2)), true };
else
return { static_cast<T>(val << (N2 - N)), true };
}

template<typename T, unsigned char N>
template<typename T2>
FixedPointNumber<T, N>::operator FixedPointNumber<T2, N>() const {
return { static_cast<T2>(val), true };
}

template<typename T, unsigned char N>
template<typename T2, unsigned char N2>
FixedPointNumber<T, N>::operator FixedPointNumber<T2, N2>() const {
if (N >= N2)
return { static_cast<T2>(static_cast<T2>(val) >> (N - N2)), true };
else
return { static_cast<T2>(static_cast<T2>(val) << (N2 - N)), true };
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator+=(FixedPointNumber<T, N> const& rhs) {
val += rhs.val;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator-=(FixedPointNumber<T, N> const& rhs) {
val -= rhs.val;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator*=(FixedPointNumber<T, N> const& rhs) {
val = ((+val) * (+rhs.val)) >> N;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator/=(FixedPointNumber<T, N> const& rhs) {
val = ((+val) << N) / rhs.val;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> FixedPointNumber<T, N>::operator-() const {
return { static_cast<T>(-val), true };
}


template<typename T, unsigned char N>
bool FixedPointNumber<T, N>::operator==(FixedPointNumber<T, N> const& rhs) const {
return val == rhs.val;
}

template<typename T, unsigned char N>
bool FixedPointNumber<T, N>::operator>(FixedPointNumber<T, N> const& rhs) const {
return val > rhs.val;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator+(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs += rhs;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator-(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs -= rhs;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator*(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs *= rhs;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator/(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs /= rhs;
}

template<typename T, unsigned char N>
bool operator!=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return !(lhs == rhs);
}

template<typename T, unsigned char N>
bool operator<(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return rhs > lhs;
}

template<typename T, unsigned char N>
bool operator>=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return !(rhs > lhs);
}

template<typename T, unsigned char N>
bool operator<=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return !(lhs > rhs);
}

#endif

So to resume it, the class FixedPointNumber contains only one variable of integral type T, which the N least significant bits are the decimal part, and the sizeof(T) - N most significant bits are the integral part.
What was aimed first is to have non-integer value smaller than a float, and all the syntax and casting to go with it.
Operators +,-,*,/ and !=,<, >=, <= are not methods of the class in order to have better encapsulation.
Here is an example for a main.cpp file :

#include "FixedPointNumber.hpp"
#include <iostream>
using namespace std;

using Nbr8 = FixedPointNumber<uint8_t, 8>;     //domain : [0, 1[    epsilon = 1/256          8 bits
using Nbr16A = FixedPointNumber<int16_t, 11>;  //domain : [-16, 16[ epsilon = 1/2048        16 bits
using Nbr16B = FixedPointNumber<uint16_t, 15>; //domain : [-1, 1[   epsilon = 1/32768       16 bits

int main() {
    {
    Nbr8 a = 0.37f, b = 0.52f;
    float af = 0.37f, bf = 0.52f;
    cout << af << " -> " << float(a) << "\t\tError (%) : " << 100 * (af - float(a)) / af << endl;
    cout << bf << " -> " << float(b) << "\t\tError (%) : " << 100 * (bf - float(b)) / bf << endl;
    cout << af + bf << " -> " << float(a + b) << "\t\tError (%) : " << 100 * (af + bf - float(a + b)) / (af + bf) << endl;
    cout << "Nbr8 recap : 25% bits for about 0.5% error if interval correctly chosen" << endl << endl;
    }
    {
    Nbr16B a = 0.37f, b = 0.52f;
    float af = 0.37f, bf = 0.52f;
    cout << af << " -> " << float(a) << "\t\tError (%) : " << 100 * (af - float(a)) / af << endl;
    cout << bf << " -> " << float(b) << "\t\tError (%) : " << 100 * (bf - float(b)) / bf << endl;
    cout << af + bf << " -> " << float(a + b) << "\t\t\tError (%) : " << 100 * (af + bf - float(a + b)) / (af + bf) << endl;
    cout << "Nbr16 recap : 50% bits for about 0.002% error if interval correctly chosen" << endl << endl;

    Nbr16A a2 = a, b2 = b;
    cout << "switching point position, less precision but wider domain !" << endl;
    cout << "a2 = " << float(a2) << " b2 = " << float(b2) << " AGAINST a1 = " << float(a) << " b1 = " <<float(b) << endl;
    cout << "Notice that gap between two consecutive values is constant in a domain, contrary to floating point numbers." << endl << endl;
    }
    return 0;
} 

Complete and updated code can be found here.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please copy your code here, as we'are not sure if the link will be alive in the years to come. Also, it would be helpful to add some explanations and concerns about your code \$\endgroup\$ – Incomputable Jan 1 '18 at 20:45
  • \$\begingroup\$ It is now completed and I added small description :) \$\endgroup\$ – Julien Vernay Jan 1 '18 at 21:21
  • 1
    \$\begingroup\$ Great, voted for reopen. The only thing left would be to provide small example main() to demonstrate the usage of the class. No need to cover all of the library, just something that is "selling" point of your library. It might be precision of your values against built-in, or anything else. \$\endgroup\$ – Incomputable Jan 1 '18 at 21:25
  • \$\begingroup\$ Not enough for a full on review, because some other folks already did this, but they haven't mentioned those two points: 1) constexpr and noexcept 2) Some of your operators aren't found by ADL. The way to do this normally is to make them friends. \$\endgroup\$ – Rakete1111 Jan 2 '18 at 23:52
  • 1
    \$\begingroup\$ @JulienVernay I would make them constexpr, but now I realized that you use compiler builtins, and I don't know if they are constexpr too. I mean, the main reason is "why not?" IMO. Might make your variables more optimization friendly, and then you can use them in constant expressions, which is nice. noexcept can also help the compiler by making optimizations if you are using exceptions (don't know if you are, if you are not, I don't think it makes a big difference). Nice that you ask, because I don't know. On further investigation, it doesn't matter. Ignore that part and cheers :) \$\endgroup\$ – Rakete1111 Jan 3 '18 at 0:14
5
\$\begingroup\$

Looks really good!

A few improvements:

Confusing construction.

Construction from raw is making your constructors more complicated than they need to be.

Your class would be easier to work with if constructing from a value ALWAYS constructs by actual value.

Also consider that boolean arguments are often hard to understand at the call site. Can someone not familiar with your library tell what the following line does without having to sift through your header? No, and it's a problem here since raw construction is clearly going to be an unfamiliar edge case.

FixedPointNumber<char, 4> val(12, true);

To fix these issues, I would instead add a static member function, and get rid of the (T,bool) constructor entirely:

static FixedPointNumber<T, N> from_raw(T data);

My example becomes proper self-documenting code at the call site:

auto val = FixedPointNumber<char, 4>::from_raw(12);

No conversion to/from double

A bit of a no-brainer, but that would definitely be nice.

In fact... it would be nice to support arbitrary floating point formats through a traits type.

Concerns about overflow behavior of multiply/division operation

val = ((+val) * (+rhs.val)) >> N;

I don't really like how inconsistent you are being with the overflow behavior. char and short get promoted, but not int or long? I would rather see everything get promoted, or nothing.

Edit: followup:

I'm not sure to understand what you meant by "through a traits type"

Imagine that you had a type that looks very roughly like this, and your conversion functions used these values to build the resulting float value.

template<typename T>
struct float_traits;

template<>
struct float_traits<float> {
  static constexpr int mantissa_offset = 0;
  static constexpr int mantissa_bits = 23;

  static constexpr int exponent_offset = 23;
  static constexpr int exponent_bits = 8;

  static constexpr int sign_bit_offset = 31;
};

Adding support for double or half-precision floats would just be a matter of adding the proper specialization to float_traits, which a user can even do within their own codebase.

\$\endgroup\$
  • \$\begingroup\$ The "static constructor" for raw is what I was searching, because yes, it looks ugly to have this bool value in the constructor x) . Yes, double would be nice ! I'll give it a try. I'm not sure to understand what you meant by "through a traits type" ? Can you explain please ? Yes overflow is a problem, but even if int can be promoted to long long, how can I promote long long ? Thanks for your review ! \$\endgroup\$ – Julien Vernay Jan 2 '18 at 21:18
  • \$\begingroup\$ @JulienVernay I've ammended the answer itself with the answer to your traits question. \$\endgroup\$ – Frank Jan 2 '18 at 21:58
  • \$\begingroup\$ I understand what you would say, and I think it could be nice to add it ! I'll work on it ! Thanks \$\endgroup\$ – Julien Vernay Jan 2 '18 at 22:30
4
\$\begingroup\$

I recently had my interest in fixed point math piqued as part of a side project I was doing, so this is great to see! Having a C++ class for fixed point numbers would make things so easy!

I'm guessing that the weird formatting is due to copy/paste issues and that your actual code uses indentation. If not, it definitely should.

Description

I notice throughout your comments you say "decimal part". However, you don't use any decimal representation. I was thinking that maybe you were working in BCD or something like that. I would change all references to "decimal" to be "fractional" to be more precise.

Don't Use using namespace std

You've written:

using namespace std;

in your header main.cpp file. That means that every file which includes your header now has all of the std namespace defined, too. If I have my own max() function that's not in std and I include your header, I will now get conflicts on my max() function. See here for more details on why this isn't a good idea.

Usage

Seeing the examples of how to use this type in your example main.cpp file left me very confused, even with a comment describing the range. The way you have it now, I have to know how many bits are in a given type's representation, then subtract from that the number of bits I want for the fractional part in order to figure out the range I'll end up with. I also have to make sure that the type I supply has enough bits for the representation. (What happens if I do using Nbr32 = FixedPointNumber<uint8_t, 17>;?)

Furthermore, the type I supply may be unsigned, but the range of the resulting type can still cover negative values. Does it make sense to have an unsigned fixed point type and a signed fixed point type? I'm not sure. But it is odd to supply an unsigned type and have it end up being signed.

I'm not an expert at templates, so I'm not entirely sure what's possible. I think it would be better to have the template take the number of bits for the integral part and the number of bits for the fractional part and choose the type it uses internally based on that and not require a caller to figure it out.

In other words, I'd like to use it like this:

using Fixed16_16 = FixedPointNumber<16, 16>;
using Fixed8_4 = FixedPointNumber<8, 4>;

As I say, I don't know whether it's possible to make that work, but it sure would be nice. If you can get closer to that, it would be great.

Naming

I'm all for long descriptive names. However, I do feel like FixedPointNumber is too long. We don't call float a floatingPointNumber or int an intNumber. I think it would be fine as FixedPoint or even Fixed (though be aware that Apple has used that type name in the past for 16.16 fixed point numbers).

Future Directions

I'd love to see a whole math library for this type. Things like trigonometric and transcendental functions would be helpful. (You might look into cordics if you plan to pursue something like that.)

\$\endgroup\$
  • \$\begingroup\$ Regarding infering the storage type from the requested number of bits: It's pretty easy to do at face value, but a fair bit of care would be required to ensure that the behavior of the class is consistent. Specifically, I suspect most operations would require explicitly masking out of any unused bits, which would end up being a nasty performance hit. \$\endgroup\$ – Frank Jan 2 '18 at 20:10
  • \$\begingroup\$ I used decimal because I didn't know how to express it in english, thanks for advice. I use using namespace std only in main.cpp so it should be fine ? I will implement static methods like lower() and upper() (constexpr ?) to have access easily to the domain (and maybe integer_bits() and fractional_bits() ?). Unsigned/signed seems correct to me, as unsigned can cover signed domain. In unsigned case, val is specified as unsigned so every operation uses unsigned. For instance, in float conversion, the test val < 0 (for specifying sign of float) is always false, so float > 0. \$\endgroup\$ – Julien Vernay Jan 2 '18 at 21:02
  • \$\begingroup\$ About using more bits for fractional part that available in underlying type, I will try for example that domain of FixedPointNumber<uint8, 9> is [0, 0.5[ (as if the bit not present was 0), and if I can't, I'll do a comparaison sizeof(T)>=N to produce compile-time error. I will add a template<uint TotalBits, uint FracBits> FixedPointNumber version which determines underlying type. The name is too long, I agree, but I think it is not important because people will probably use using or typedef, because it is unlikely to use many types at same moment for number representation. \$\endgroup\$ – Julien Vernay Jan 2 '18 at 21:12
  • \$\begingroup\$ I thing cordics can be implemented, but not in the near future ^^. Thanks for your review ! PS : Indeed, no indentation results of bad copy/pasting x) \$\endgroup\$ – Julien Vernay Jan 2 '18 at 21:21
  • 1
    \$\begingroup\$ Re "Usage": I'd say that is an API decision, do you want an expert interface (the caller can choose all options) or a user-friendly "it just works" interface (the caller tells what he wants and gets something that works). Currently, the interface seems a bit in between those extremes (can choose underlying type and number of fractional bits, cannot choose signedness and "integral bits", though the latter is implied). Of course, one can always put a user-friendly interface on top of an expert one \$\endgroup\$ – hoffmale Jan 2 '18 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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