FeatReq: Overflow Detection

[Klummel69]

Unlike floatingspoint, overflow can occur more quickly when fixed-point operations are used. In applications such as filters or control algorithms, overflow detection would be useful.

Example

fpm::fixed_8_24 x {100}, y;
y = x * 10;

An optional switchable overflow detection would be good. At least for the basic arithmetic operations + - * /.

In the case of multiplication it might be easy to implement:

inline fixed& operator*=(const fixed& y) noexcept
    {
        auto value = (static_cast<IntermediateType>(m_value) * y.m_value) / (FRACTION_MULT / 2);
        // Draft:
        if (value < 2*std::numeric_limits<BaseType>::min() || value > 2*std::numeric_limits<BaseType>::max()) 
           {error_reaction(…);}
        m_value = static_cast<BaseType>((value / 2) + (value % 2));
        return *this;
    }
}

Is there any interest in this? Maybe I will deal with it in the near future.

[MikeLankamp]

I know some other fixed-point libraries have overflow detection, but one of the concerns I have with this is performance: adding these checks slows down basic fast operations like addition and also (but to less, relatively), multiplication. The performance impact on compound operations like trigonometry would have to be investigated, and those operations already suffer from being "emulated".

An argument against overflow detection is that in C++ signed integers and floats also have UB on overflow (although in practice some methods are available to handle fp overflow with exceptions).

If I had to choose, I'd add this with a template argument, to let developers choose whether to have an overflow-safe type or not.

@Klummel69 , is there a particular use case that you have run into that would require this feature?

[Klummel69]

My background is in automation with microcontrollers. Mostly, performance is important, of course. Now I am building a project where performance is less important, but fixed point arithmetic must be used. I will include matrix calculations and would like to have the possibility to detect overflows at least during development. A compiler flag to turn on/off would be OK.

[MikeLankamp]

possibility to detect overflows at least during development.

Another option is to use assert, but then this is only checked in debug builds. Backward compatibility wouldn't be a concern, since overflow is UB anyway. Would this work for you?

A compiler flag to turn on/off would be OK.

That's what I'm trying to avoid, so if this checking needs to happen in a release build as well, I'd favor it being a template argument, e.g. fpm::fixed_16_16_checked or something which aliases to something like fpm::fixed<std::int32_t, std::int64_t, 16, fpm::check_overflow>.

[Klummel69]

Another option is to use assert, but then this is only checked in debug builds. Backward compatibility wouldn't be a concern, since overflow is UB anyway. Would this work for you?

Of course. I have also often modified assert() so that assertions were also caught in the release. Not perfect, but easy to implement.

I'd favor it being a template argument, e.g. fpm::fixed_16_16_checked or something which aliases to something like fpm::fixed<std::int32_t, std::int64_t, 16, fpm::check_overflow>.

That would be the ideal solution, of course.

[pavel-kirienko]

An architecturally cleaner solution is to remove the template parameter constraint that the BaseType shall be a native integral and allow the user to instantiate fpm::fixed<> with BaseType being a custom saturating integer type. Removal of this (unnecessarily restrictive) constraint would also help with https://github.com/MikeLankamp/fpm/issues/8.

using fixed_16_16_checked = fpm::fixed<Saturating<std::int32_t>, std::int64_t, 16>;

A simple saturating wrapper over a native integral type is rather trivial to implement but one might say that it would be out of the scope of this library.

[MikeLankamp]

An interesting idea, @pavel-kirienko. This was considered for #8, but I was afraid I couldn't guarantee that the user wouldn't use weird types such as float or classes. As mentioned in that issue, ideally I'd want a integer duck-typing concept, i.e. accept types that look and feel like integers.

Maybe that's simply too much and I should trust the programmer. Using float will fail the most basic uses of fpm::fixed since it doesn't have operator<<. Classes would probably not compile either unless operator+ and operator<< etc are defined to meaningful things.

[pavel-kirienko]

weird types such as float or classes

A generic type is expected to generalize some behavior for any T irrespective of its identity as long as it meets specific requirements; the problem with the current approach is that it enforces irrelevant requirements (such as T being a native integer) which goes against the principles of metaprogramming. Being able to instantiate this template with a custom class is absolutely essential for it to be useful outside of the most basic scenarios. I see a few adequate solutions:

• Remove all constraints and make it a user's problem.
• Require std::numeric_limits<T>::is_integer. This is not the same as std::is_integral<T> because the former can be specialized for user types, unlike the latter. Say, Saturable<T> from my post above would normally specialize std::numeric_limits<Saturable<T>>.

[MikeLankamp]

I do agree with your argument. The first solution is the one that I was not very happy about. Your second solution looks much nicer. I didn't realize std::numeric_limits<T>::is_integer was an option (despite having implemented it for fpm::fixed 😅). boost::multiprecision seems to specialize it, so that's fine for #8.

I'll switch to that one instead. Many thanks for pointing this out!