I'm trying the latest cnl updates again and it seems to work well. With the following type definition, the tests pass and are fast, with one exception.

template <
    int IntegerDigits,
    int FractionalDigits,
    class Narrowest = int32_t>
using safe_elastic_fixed_point = cnl::scaled_integer<
    cnl::elastic_integer<
        IntegerDigits + FractionalDigits,
        cnl::rounding_integer<
            cnl::overflow_integer<
                Narrowest,
                cnl::saturated_overflow_tag>,
            cnl::nearest_rounding_tag>>,
    cnl::power<-FractionalDigits>>;

using fp12_t = safe_elastic_fixed_point<11, 12>;

using temp_t = safe_elastic_fixed_point<11, 12>;
using temp_precise_t = safe_elastic_fixed_point<11, 20>;
using temp_wide_t = safe_elastic_fixed_point<19, 12>;

Test case:

    WHEN("conversion_from_long_to_normal_temp")
    {
        // non-clipping/non-overflowing conversion
        temp_wide_t tl = 0.5;

        // conversion to normal format
        temp_t t = tl;
        CHECK(t == temp_t(0.5));

        // clipping conversion should be constrained to min/max
        tl = -15000;
        t = tl;
        CHECK(t == cnl::numeric_limits<temp_t>::lowest());

        tl = 15000;
        t = tl;
        CHECK(t == cnl::numeric_limits<temp_t>::max());
    }

/home/elco/repos/firmware/lib/test/FixedPoint_test.cpp:84: FAILED:
  CHECK( t == cnl::numeric_limits<temp_t>::lowest() )
with expansion:
  -15000 == -2047.999755859375

/home/elco/repos/firmware/lib/test/FixedPoint_test.cpp:88: FAILED:
  CHECK( t == cnl::numeric_limits<temp_t>::max() )
with expansion:
  15000 == 2047.99975585937

What I expect is that on assignment to temp_t, the value would clip to max or lowest. When swapping the order to move the overflow integer up the chain, it will not compile, I think due to #530.

Godbolt example: https://godbolt.org/z/m6ZFD4

Glad to hear that you're trying out the update without too much trouble.

I think in this case, the problem is that overflow_integer is inside elastic_integer and not outside of it. Notice how overflow_integer wraps elastic_integer in the alias, static_integer. When you wrap the other way around, what you get is an elastic_integer with, say, 23 digits which has -- as its rep type -- a 31-digit, saturating overflow_integer whose values are limited to the range [-2^31, 2^31). It is capped to that wider range because the rep type of overflow_integer is 31-digit and that's the rep type which overflow_integer uses to determine when overflow has occurred.

Remember that in temp_t, while elastic_integer 'knows' about overflow_integer, it's not so the other way around. overflow_integer here is just overflow_integer<int32_t, saturated_overflow_tag> and that type has no reason to limit range to 23 digits.

HTH

That is what I thought, I don't think this issue is with overflow, but with elastic integer. It doesn't make sense that it can go beyond its numeric_limits lowest and max. Either the limits are wrong or the behavior is wrong.

Elastic integer provides compile time type promotion to avoid overflow. In this situation, it is defined as a 24 bit wide type, but it exceeds that runtime, without type promotion.

set_digits has a hard coded -1 to compare with, can this be based on the numeric limits of the type being wrapped instead? My compiler also complains about sign mismatch in set_digits positive.

When the outer type that scaled_integer wraps is an overflow integer, the value is clipped. But without 128 bit support, it doesn't compile. I cannot find a combination with the correct behavior that compiles with the current version and no 128bit integer support.

With elastic inside overflow integer: https://godbolt.org/z/_h-r2i

With overflow integer inside elastic: https://godbolt.org/z/sPjFrC

I think the desired behaviour would be:

fp_t a1 = cnl::numeric_limits<fp_t>::max();
fp_t a2 = cnl::numeric_limits<fp_t>::max();
fp_t a3 = a1*a2; // limited to max(), represented by int32_t

fp_t a1 = cnl::numeric_limits<fp_t>::max();
fp_t a2 = cnl::numeric_limits<fp_t>::max();
auto a3 = a1*a2; // not limited to max, represented by int32_t if it fits, promoted type with more bits.

By using auto, I tell the compiler it doesn't have to saturate to 24 bits here. If I assign to an fp_t, it should saturate the result during the assignment.

Either of two things is happening here: 1) CNL is using too many bits or 2) CNL is not preventing overflow from happening. I think that the first is a bug and the second is by design.

1

Yes, it looks like the numbers are being pushed over the 64-bit limit (just). Hopefully you're right that it's #530. I won't close this issue unless I know for sure. Note that if you drop a single bit from temp_precise_t, that will work around the problem.

2

Regarding your expectations for elastic_integer, the responsibility for not overflowing lies with the client code. So it's no different to writing

cnl::elastic_integer<4> e = 16;

or:

int m = 100'000;
short n = m;

When overflow_integer is inside elastic_integer, it's in the wrong place to help; it's doing a different job.

Either the limits are wrong or the behavior is wrong.

The behavior is undefined because the limits are exceeded. That's tough on the client but there's no free way to catch or avoid this.

Elastic integer provides compile time type promotion to avoid overflow. In this situation, it is defined as a 24 bit wide type, but it exceeds that runtime, without type promotion.

Yes. Without promotion, elastic_integer alone is powerless to avoid overflow. If you perform a narrowing conversion, it's inevitable that overflow becomes a concern. Converting from temp_wide_t to temp_t is a narrowing conversion.

I need to do more prevent narrowing conversions (#93) but that wouldn't help in this situation because it relies on uniform initialization:

auto m {100'000};
auto n {m};  // narrowing; not allowed by the language
auto e cnl::elastic_integer<4>{16};  // narrowing; shouldn't compile

(Also, introducing wide_integer makes up for lack of 128-bit integers although not all of the arithmetic for that type is completely solid yet so YMMV.)

I'm avoiding wide_integer because of the extra costs involved, that's why I am not using static_number. Decreasing the number of bits is an option, but there are other errors with types becoming too wide.

https://godbolt.org/z/TUtcsi

using temp_precise_t = safe_elastic_fixed_point<11, 19>;
using temp_wide_t = safe_elastic_fixed_point<18, 12>;

    temp_precise_t t1 = 30.0;
    temp_wide_t t2 = 30.0;
    temp_precise_t t4 = t1 + t2;

If I'm not mistaken, this should only need 38 bits: both types can be converted to <18,19> and then added with 1 extra bit for overflow. I get a compile error for double the amount of bits:


/home/elco/repos/firmware/lib/test/FixedPoint_test.cpp:276:34:   required from here
/home/elco/repos/firmware/lib/test/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../num_traits/set_digits.h:94:16: error: invalid use of incomplete type ‘struct cnl::signed_integer_cannot_have<76>::digits_because_maximum_is<63>’
         struct set_digits_signed<MinNumDigits, enable_for_range_t<MinNumDigits, intmax, void>>
                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Using an auto type for t4 doesn't help, so it is not the narrowing conversion that's triggering the error.

I know it will compile with wide_integer, but that just covers up this bug. The bug will result in a performance hit instead of a compile error.

Looking at the template error trace, the error comes from the multiply operator, could this be happening?

The result of t1+t2 is 38 bits, so it instantiates this larger type.
The multiply op of this new type wants to return a 76 bit wide type, which is correct but results in a compile error.

Even though this code doesn't multiply, the template seems to be instantiated. Possibly by the overflow saturation. Without 128 bit support, the overflow saturated elastic integer should saturate beyond 64 bits instead of trying to grow wider than supported?

Actually, I spoke too soon, sorry. The tests seems to be just as fast with your suggested introduction of wide_integer.

I needed to fix one test though:

using temp_t = safe_elastic_fixed_point<11, 12>;

WHEN("overflowing_multiplication_is_constrained, but only after assignment to a smaller type")
    {
        temp_t t1 = short(120);
        temp_t t2 = short(120);

        auto t3 = t1 * t2;
        temp_t t4 = t3;
        CHECK(t3 == decltype(t3){14400});
        CHECK(t4 == cnl::numeric_limits<temp_t>::max());

        t1 = short(-120);
        t2 = short(120);
        auto t5 = t1 * t2;
        temp_t t6 = t5;

        CHECK(t5 == decltype(t5){-14400});
        CHECK(t6 == cnl::numeric_limits<temp_t>::lowest());
    }

Changed to

using temp_t = safe_elastic_fixed_point<11, 12>;

WHEN("overflowing_multiplication_is_constrained, but only after assignment to a smaller type")
    {
        temp_t t1 = short(120);
        temp_t t2 = short(120);

        auto t3 = t1 * t2;
        temp_t t4 = t3;
        CHECK(t3 == decltype(t3){14400.0});
        CHECK(t4 == cnl::numeric_limits<temp_t>::max());

        t1 = short(-120);
        t2 = short(120);
        auto t5 = t1 * t2;
        temp_t t6 = t5;

        CHECK(t5 == decltype(t5){-14400.0});
        CHECK(t6 == cnl::numeric_limits<temp_t>::lowest());
    }

With the argument as integer instead of double, decltype(t3){14400} is 127.999999940395355224609375, which equals (2^31 - 1) / 2^24. decltype(t3) is ‘cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<46, cnl::_impl::number<cnl::_impl::number<int, cnl::wide_tag<31, int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-24, 2> >’.

So it seems that the value is saturated to INT32_MAX.

The arm binaries however fail to compile, but I cannot reproduce it on Godbolt: https://dev.azure.com/brewblox/brewblox/_build/results?buildId=2377&view=logs&j=530e7fe6-3c37-5e69-795f-17390ab3d2b8&t=557a3f4d-d20e-57a3-07b4-763a86d248a8

Line causing the error: https://github.com/BrewBlox/brewblox-firmware/blob/develop/lib/src/TempSensorOneWire.cpp#L102

The compile error still occurs with v8 of the arm compiler. But I really don't understand why it occurs. Even when I reduce the code to this:

temp_t
TempSensorOneWire::readAndConstrainTemp()
{
    fp12_t val(1.0);
    val += fp12_t(1.0);

    return val2;
}

ENV GCC_ARM_URL="https://armkeil.blob.core.windows.net/developer/Files/downloads/gnu-rm/8-2019q3/RC1.1/gcc-arm-none-eabi-8-2019-q3-update-linux.tar.bz2"
ENV GCC_ARM_VERSION="8-2019-q3-update"


/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/overloads.h: In substitution of 'template<class LhsOperand, class RhsOperand> constexpr decltype (cnl::comparison_operator<typename std::enable_if<cnl::_impl::enable_binary<LhsOperand, RhsOperand>::value, cnl::_impl::less_than_op>::type, LhsOperand, RhsOperand>()(lhs, rhs)) cnl::_impl::operator<(const LhsOperand&, const RhsOperand&) [with LhsOperand = cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >; RhsOperand = int]':
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../number/../num_traits/../rounding/nearest_rounding_tag.h:52:39:   required from 'constexpr decltype ((lhs / rhs)) cnl::binary_operator<cnl::_impl::divide_op, cnl::nearest_rounding_tag, cnl::nearest_rounding_tag, Lhs, Rhs>::operator()(const Lhs&, const Rhs&) const [with Lhs = cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >; Rhs = cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >; decltype ((lhs / rhs)) = cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../number/binary_operator.h:92:71:   required from 'struct cnl::binary_operator<cnl::_impl::divide_op, cnl::_impl::native_tag, cnl::_impl::native_tag, cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>, cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>, void>'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/overloads.h:99:9:   required by substitution of 'template<class LhsOperand, class RhsOperand> constexpr decltype (cnl::binary_operator<typename std::enable_if<cnl::_impl::enable_binary<LhsOperand, RhsOperand>::value, cnl::_impl::divide_op>::type, cnl::_impl::native_tag, cnl::_impl::native_tag, LhsOperand, RhsOperand>()(lhs, rhs)) cnl::_impl::operator/(const LhsOperand&, const RhsOperand&) [with LhsOperand = cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>; RhsOperand = cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/operators.h:82:106:   required by substitution of 'template<class Lhs, class Rhs> constexpr decltype ((lhs / rhs)) cnl::_impl::divide_op::operator()(const Lhs&, const Rhs&) const [with Lhs = cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>; Rhs = cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/generic.h:83:31:   required from 'struct cnl::binary_operator<cnl::_impl::divide_op, cnl::elastic_tag<48, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::elastic_tag<24, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::_impl::number<cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, cnl::nearest_rounding_tag>, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag>, void>'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../number/binary_operator.h:85:53:   [ skipping 12 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/scaled_integer/type.h:72:26:   required from 'constexpr cnl::scaled_integer<Rep, Scale>::scaled_integer(const Number&) [with Number = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<24, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; Rep = cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>; Scale = cnl::power<-12, 2>]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/operators.h:28:55:   required from 'constexpr decltype (static_cast<Destination>(source)) cnl::_impl::convert_op::operator()(const Source&) const [with Destination = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; Source = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<24, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; decltype (static_cast<Destination>(source)) = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../number/../operators/native_tag.h:43:77:   required from 'constexpr Destination cnl::convert_operator<cnl::_impl::native_tag, cnl::_impl::native_tag, Destination, Source>::operator()(const Source&) const [with Destination = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; Source = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<24, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/generic.h:69:44:   required from 'constexpr LhsOperand& cnl::compound_assignment_operator<Operator, LhsTag, RhsTag, LhsOperand, RhsOperand, Enable>::operator()(LhsOperand&, const RhsOperand&) const [with Operator = cnl::_impl::assign_add_op; LhsTag = cnl::_impl::native_tag; RhsTag = cnl::_impl::native_tag; LhsOperand = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; RhsOperand = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; Enable = void]'
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/overloads.h:194:9:   required from 'constexpr cnl::_impl::enable_binary_t<LhsOperand, RhsOperand, decltype (cnl::compound_assignment_operator<cnl::_impl::assign_add_op, cnl::_impl::native_tag, cnl::_impl::native_tag, LhsOperand, RhsOperand>()(lhs, rhs))> cnl::_impl::operator+=(LhsOperand&, const RhsOperand&) [with LhsOperand = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; RhsOperand = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >; cnl::_impl::enable_binary_t<LhsOperand, RhsOperand, decltype (cnl::compound_assignment_operator<cnl::_impl::assign_add_op, cnl::_impl::native_tag, cnl::_impl::native_tag, LhsOperand, RhsOperand>()(lhs, rhs))> = cnl::scaled_integer<cnl::_impl::number<cnl::elastic_integer<23, cnl::_impl::number<cnl::_impl::number<long int, cnl::wide_tag<31, long int, void> >, cnl::nearest_rounding_tag> >, cnl::saturated_overflow_tag>, cnl::power<-12, 2> >&]'
/home/elco/repos/firmware/lib/src/TempSensorOneWire.cpp:84:22:   required from here
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/overloads.h:134:30: error: no match for call to '(cnl::comparison_operator<cnl::_impl::less_than_op, cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >, int, void>) (const cnl::_impl::number<long long int, cnl::wide_tag<48, long int, void> >&, const int&)'
         -> decltype(cnl::comparison_operator< \
                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 enable_binary_t<LhsOperand, RhsOperand, NAME>, LhsOperand, \
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 RhsOperand>()(lhs, rhs)) \
                 ~~~~~~~~~~~~~^~~~~~~~~~
/home/elco/repos/firmware/lib/src/../inc/../cnl/include/cnl/_impl/elastic_integer/../elastic_tag/../operators/overloads.h:143:9: note: in expansion of macro 'CNL_DEFINE_COMPARISON_OPERATOR'
         CNL_DEFINE_COMPARISON_OPERATOR(<, less_than_op)
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../build/module.mk:277: recipe for target '/home/elco/repos/firmware/build/target/user/platform-8-m/firmware/brewblox/lib/src/TempSensorOneWire.o' failed

Yet it compiles without problems on Godbolt: https://godbolt.org/z/tN-gKm

Maybe it is because of the addition using too many bits, but the arm compiler is not smart enough to eventually remove it. I think the addition needing double the number of bits of the operands is probably a bug.

I don't get a compile error when I switch the type to native rounding. The error seems to start from the divide op in nearest_rounding.

FYI, I completely removed the rounding_integer and added some manual rounding when converting to integer types where it was required. I'm now ready to switch to the current version of cnl, so take your time. Any bugs reported here are not hindering me, but might still be actual bugs for you to look at. Feel free to close this issue and/or create more specific bug issues.

If it interests you, this is my "update CNL" PR for brewblox. https://github.com/BrewBlox/brewblox-firmware/pull/158

Thanks for the update. As this issue has valuable reproductions, I'll keep it open until all fixes are applied. I did try removing the rounding as it requires an additional bit to work with but it did not help.

johnmcfarlane / cnl

scaled elastic integer exceeding lowest and max? #550

1

2