Saturation to negative minimum fails one bit short

[hbe72]

Describe the bug:

The test "static_number_saturation_min" fails. Saturation produces -32767.

    namespace static_number_saturation_max {
        static constexpr auto n = cnl::static_number<15,-15, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t>{1.0};
        static constexpr auto n_rep = static_cast<int32_t> (to_rep(n));
        static constexpr auto expected = 32767;
        static_assert(identical(n_rep, expected));
    }

    namespace static_number_saturation_min {
        static constexpr auto n = cnl::static_number<15,-15, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t>{-1.0};
        static constexpr auto n_rep = static_cast<int32_t> (to_rep(n));
        static constexpr auto expected = -32768;
        static_assert(identical(n_rep, expected));
    }

I'm suspecting that _impl/limits/lowest.h needs the following fix:

        template<class Rep>
        struct lowest<Rep, true> {
            [[nodiscard]] constexpr auto operator()(Rep const& max) const noexcept
            {
                // return static_cast<Rep>(-max);
                return static_cast<Rep>(-max-1);
            }
        };

Need to find suitable place for the tests above and verify that this is correct fix.

• OS: macOS 10.15.7
• Compiler version: gcc-10 (Homebrew GCC 10.2.0_4) 10.2.0
• CNL version: f902baac060f15b8c382bfc0a5594a76b187dd47

[johnmcfarlane]

This is another case where the type avoids pitfalls for inexperienced users. From P0828:

For two's complement signed types, the most negative number is not in the range allowed by the type. This avoids certain edge cases, e.g. where -INT_MIN exceeds INT_MAX, thus requiring an entire extra digit.

Another example would be cnl::numeric_limits<T>::lowest() / -1.

I'm thinking that a note in the documentation might help clarify these surprises. But not sure where -- given that again, this applies to all the elastic_ and static_ types.

[hbe72]

This is incorrect. Absolute value of 2's complement negative minimum is one LSB larger than positive maximum. Still, the number of "digits" is still the same. 0x8000 = -32768, 0x8001 = -32767, ... , 0x7fff = 32767. All of them have 15 digits, all of them are 16 bit wide. That's how computers and integers operate. That is how signed fixed-point arithmetic has been done in all CPU's, DSP's and ASIPs of the world. Without it there will be 1 LSB bit difference between CNL and HW implementation.

My primary use case is fixed-point modelling of algorithms rather than final implementation of them. Reason is that compiling directly from CNL to a DSP/ASIP target would require specialised compiler with understanding of rounding, saturation and overflow control registers or availability of specialized compound instructions doing all of that together with arithmetic in a single clock cycle. That requirement may be in place one day, but not very soon.

It is fine for a "safe" type to do this for inexperienced users, but there has to be datatype with correct behaviour.

[johnmcfarlane]

there has to be datatype with correct behaviour.

I'm happy to consider such a type. Feedback from LEWGI in Cologne in 2019 may point to a solution which is more flexible. It highlights that elastic_integer is a poor design which combines two concerns:

1. It handles the specification of fundamental types in terms based on range.
2. It also provides generalised promotion, i.e. the widening of arithmetic results.

You clearly don't need 1) for your application and it's not entirely clear that you need 2) either. If that's the case then elastic_integer might only be an impediment. Combining feedback from here and #849, can I suggest a type like static_number but without elastic_integer or Digits?

As you seek greater control over the type, it will fall to the user to ensure that arithmetic does not saturate range. That means occasionally casting to a wider type to accommodate results. Is that workable for now?

This is incorrect. Absolute value of 2's complement negative minimum is one LSB larger than positive maximum. Still, the number of "digits" is still the same. 0x8000 = -32768, 0x8001 = -32767, ... , 0x7fff = 32767. All of them have 15 digits, all of them are 16 bit wide. That's how computers and integers operate. That is how signed fixed-point arithmetic has been done in all CPU's, DSP's and ASIPs of the world. Without it there will be 1 LSB bit difference between CNL and HW implementation.

Prohibition of the MNN is not some oversight; it is deliberate and necessary. Something I forgot to mention here in #849 is that there is a clear expectation for fixed-point to provide an alternative to floating-point. That may be unfortunate, but it is inevitable. And static_number represents the current response to that demand. It would not work as advertised if it occasionally failed in surprising -- and entirely avoidable -- ways.

I'm thinking about how to phrase this in the FAQ to make it crystal clear in future. You're welcome to review once I put up a request.

[hbe72]

For me this looks magic ;) This "new" type could work. I will do some experimentation.

What I typically do in fixed-point design is that I do not care what is the width of the datatype due to arithmetic (+. -, *, /), I let the datatype expand naturally without loss of precision. Then I assign or convert the result to narrower datatype with desired properties (rounding, overflow, saturation). It is my design decision how much I allow widths to expand and where to narrow the type. Then later on it is design decision of VHDL/Verilog designer how he implementes the datapath, i.e. does he really need the whole width of the intermediate results. Only thing what matters is that input is bit accurate and output is bit accurate.

[johnmcfarlane]

I let the datatype expand naturally without loss of precision

I think we're on the same page but to make it clear: with this type, you must cast to a wider type manually. That's something you lose when not using elastic, e.g.

constexpr auto n = hbe_number<16,-15, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t>{1.0};
constexpr auto nn = set_width_t<std::remove_cvref_t<decltype(n)>, 60>{n} * n;

[hbe72]

Is this what I'm seeing here:

    static constexpr auto a = hbe_number<16,-15, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t>{0.5};
    static constexpr auto b = hbe_number<16,-15, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t>{0.75};
    static constexpr auto c = a + b;
    static constexpr hbe_number<10, -9, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t> d = c;
    static constexpr hbe_number<16, -15, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t> e = c;
    static constexpr hbe_number<17, -16, cnl::neg_inf_rounding_tag, cnl::saturated_overflow_tag, int16_t> f = c;
    std::cout << "a = " << a << " = " << to_rep(a) << std::endl;
    std::cout << "b = " << b << " = " << to_rep(b) << std::endl;
    std::cout << "c = " << c << " = " << to_rep(c) << std::endl;
    std::cout << "d = " << d << " = " << to_rep(d) << std::endl;
    std::cout << "e = " << e << " = " << to_rep(e) << std::endl;
    std::cout << "f = " << f << " = " << to_rep(f) << std::endl;

Output:

a = .5 = 16384
b = .75 = 24576
c = 1.25 = 40960
d = 1.25 = 640                                 //Should have saturated
e = .999969482421875 = 32767  //This is the only one which saturates properly
f = 1.25 = 81920                              //Should have saturated

But naturally saturation logic does not exist as types are:

c type = cnl::_impl::wrapper<cnl::_impl::wrapper<cnl::_impl::wrapper<int, cnl::neg_inf_rounding_tag>, cnl::saturated_overflow_tag>, cnl::power<-15, 2> > const
d type = cnl::_impl::wrapper<cnl::_impl::wrapper<cnl::_impl::wrapper<short, cnl::neg_inf_rounding_tag>, cnl::saturated_overflow_tag>, cnl::power<-9, 2> > const
e type = cnl::_impl::wrapper<cnl::_impl::wrapper<cnl::_impl::wrapper<short, cnl::neg_inf_rounding_tag>, cnl::saturated_overflow_tag>, cnl::power<-15, 2> > const
f type = cnl::_impl::wrapper<cnl::_impl::wrapper<cnl::_impl::wrapper<int, cnl::neg_inf_rounding_tag>, cnl::saturated_overflow_tag>, cnl::power<-16, 2> > const

Although bit ugly, I can maintain in my code a patch against CNL to correct the negative minimum to static_cast<Rep>(-max-1), at least for the time being.

[johnmcfarlane]

Sorry, saturation won't work as desired because overflow_integer doesn't know how many bits the alias has.

You are looking for a type which doesn't currently exist in CNL. It's similar to elastic_integer but it's not the same. Whatever such type is, it has a MNN. However, elastic_integer does not have a MNN and its minimum is minus its maximum.

I've opened an issue to split apart elastic_integer, #864, which tracks this.

[hbe72]

Thanks, I can live with Digits vs. Width, both are fine.

MNN even with potential problems is the negative saturation limit in most DSPs.