Averaging accumulator template with overflow detection/prevention

Question

This is a class/template I just wrote for my embedded project (IAR EW ARM - Cortex/ARM7TDMI - Atmel SAM7, SAM4, SAMG). I am gathering data from CAN BUS (FMS), e.g. Engine Revolutions (Per Minute), and wanted to replace current fields with some class that won't break existing code (that is assigning value to it somewhere and then reading somewhere else) but would add averaging to it (to not only record last known value on demand, as it currently does, but also average since last record).

I was also thinking about prevention/solution for overflow situation, when somebody forgets to record and reset the average fast enough (goal is to gather unsigned 16bit value 100x/s and record the average every 10s), because somebody else may in the future use the system and make a mistake. So, I want it to behave reasonably - it will loose precision, but the average should still be reasonably good: it just halves the accumulator and number of samples if overflow would occur.

It turned out to be a bit more complicated than I originally anticipated, especially when I considered signed values. I am probably invoking undefined behaviour in my sum_would_overflow helper, but I know the compiler and cannot trade performance for compatibility with some exotic architecture we will never use. I can even code that little helper in assembler, but I wanted something that works and is OK C++. (I mean no log or division, these are too expensive, but bit shifts and builtins like CLZ are acceptable.)

...but this overview is not only about me and my needs, so feel free to comment/review anything without limitations. I just wanted to give you my background, nothing more.

#ifndef LIB_AVERAGER_HPP
#define LIB_AVERAGER_HPP
#include <type_traits>
//include "core/typedefs.h" .... typedef unsigned short word; typedef unsigned uint;
/// Helper to check possible overflow
/// (to reduce accumulator and counter before adding value)
template<
 class Accu = uint,
 class Value = word>
 static inline constexpr std::enable_if_t<
 std::is_unsigned<Accu>::value && std::is_unsigned<Value>::value,
 bool> sum_would_overflow(Accu accu, Value value)
{
 return accu + value < accu;
}
template<
 class Accu = uint,
 class Value = word>
 static inline constexpr std::enable_if_t<
 std::is_signed<Accu>::value && std::is_signed<Value>::value,
 bool> sum_would_overflow(Accu accu, Value value)
{
 auto a = static_cast<std::make_unsigned_t<Accu>>(accu);
 auto v = static_cast<std::make_unsigned_t<Value>>(value);
 if (accu < 0) a = -a;
 if (value < 0) v = -v;
 return static_cast<Accu>(a + v) < 0;
}
/// Current Value + Average (used in CAN Bus)
template<
 class Accu = uint,
 class Value = word,
 class Cntr = word>
 class Averager
{
 static_assert(
 std::is_signed<Value>::value == std::is_signed<Accu>::value,
 "Value and Accu must both be signed or both unsigned");
 static_assert(
 sizeof(Accu) >= sizeof(Value),
 "Accu must have at least as many bits as Value");
 static_assert(
 std::is_signed<Cntr>::value == false,
 "Cntr must be unsigned");
 Accu accu; ///< accumulator
 Value curr; ///< current/last value
 Cntr cntr; ///< number of samples
public:
 void reset() {
 accu = 0;
 cntr = 0;
 }
 Value value() const {
 return curr;
 }
 Value average() const {
 return cntr ? accu / cntr : curr;
 }
 void add(Value value) {
 curr = value;
 if (cntr+1 == 0 || sum_would_overflow(accu, value)) {
 accu /= 2;
 cntr /= 2;
 }
 cntr++;
 accu += value;
 }
 operator Value() const {
 return curr;
 }
 Averager& operator=(Value value) {
 add(value);
 return *this;
 }
};
#endif

It would often be used as Averager<uint, word, word> where simple word used to be. The accumulator would be bigger, but I allowed same size in the static_assert. Some code is already using assigmnet (erpm = value) and some other fetching last value (record.addU16(erpm)). Now I want to add record.addU16(erpm.average()); erpm.reset();. And then for many other, some 16bit, some 32bit, some signed, some unsigned.

The sum_would_overflow helper was quite tricky to write and invoking the overflow to check the result, knowing 2's complement arithmetic, is probably UB, but as I said, I know the compiler and this is for embedded system, so I have to be more careful about performance than I would be when writing this for PC. I still used accu /= 2 even thoug I know accu >>= 1 would be faster for unsigned types if the compiler wasn't smart enough, but I believe IAR will optimize that... will check the assembler output and optimize my self if I find IAR is not that smart. accu /= 2 is clear, that is why I want it that way, if not hurting performance.

Accu is biggest, so I placed it first (not to invoke padding - this is 32bit ARM), Cntr would probably always be 16bit, Value can be 8/16/32, signed or unsigned.

• JDługosz: The compiler is much smarter about constants then you suppose. Always write the intent, not your own tricks; the compiler knows more tricks, specific to the instruction set and even neighboring code!

Answer 1

Conformance

As the question is c++11, we should be using std::enable_if<>::type rather than std::enable_if_t<>. Alternatively, switch to C++14, and use the other short aliases, such as std::is_signed_v<>.

Overflow prediction

The unsigned version of sum_would_overflow() looks safe to me.

The unsigned version doesn't appear to have undefined behaviour, but does have implementation-defined behaviour that might be avoided - the cast of negative values, and the negation of an unsigned type. It's also pessimistic - if the values are of different sign, and Accu has at least the range of Value, then it can't overflow. If Accu is narrower than Value, we can't do very much anyway, so it might be worth testing that in the enable_if (or perhaps a static_assert, so we give a clearer indication of why it can't be called, or make it a static method of Averager, which already has that constraint).

Overflow handling

We're actually implementing a weighted average, due to this:

 if (cntr+1 == 0 || sum_would_overflow(accu, value)) {
 accu /= 2;
 cntr /= 2;
 }

If the value becomes too large for the accumulator, then older values have half the weight of the newer values (and even older values end up with a quarter of the weight, and so on).

We could counter that by keeping a "scale" value, which we increase when we decrease accu, instead of decreasing cntr. Then divide new entries by scale as we add them. That loses precision, of course, so we might need a minor and a major accumulator, one unscaled and one scaled. And we'd still need to handle counter overflow somehow. It's up to you whether that complexity is worth it, or whether you want to simply document that more recent values carry more weight in the average.

Correctness

I couldn't actually make the code work in the presence of overflow:

#include <cstdint>
#include <iostream>
int main()
{
 Averager<std::uint8_t, std::uint8_t> a;
 a.reset();
 for (auto i: {125, 125, 125, 125}) {
 a.add(i);
 // cast to avoid being formatted as a character
 std::cout << static_cast<unsigned>(a.average()) << '\n';
 }
}

Surprising result:

125
125
39
61

I even tried with the default template types:

Averager b;
b.reset();
for (int i = 0; i < 65539; ++i) {
 b.add(15);
}
std::cout << b.average() << '\n';
b.add(15);
std::cout << b.average() << '\n';

15
49167

Style

We shouldn't need to call reset() before using the averager for the first time:

Accu accu = 0; ///< accumulator
Value curr = 0; ///< current/last value
Cntr cntr = 0; ///< number of samples

We don't need to compare is_signed against false:

static_assert(
 std::is_unsigned<Cntr>::value,
 "Cntr must be unsigned");

• user52292: Thank you, upvoted already. I need to process this, especially why the safe-guard of halving does not work as expected (125+125=250, 250+125 mod 256 = 119 which is smaller than 250, so, it should have accu=125 and cntr=1 before adding, then again accu=250, cntr=2 after and keep that state). Need to step that to find what is wrong. Maybe I need to cast it to Accu (to force the modulo), but that only explains why uint8_t does not work, unless you compiled for 64bits and it promotes all types to 64bits. You are right about C++11 vs. 14 and thanks for is_signed_v and note about reset.
• user52292: One note about why I have used is_unsigned... = false: I was thinking that somebody could, in theory, use custom class with custom arithmetics, for which neither is_signed nor is_unsigned will be defined / have value = true. In other words, I made the assert "fail if I am sure it is wrong" rather than "fail if I am not sure it is correct".
• Toby Speight: Thanks for your explanation. I'm struggling to imagine a type where is_unsigned is defined but inconsistent with is_signed - if this is a meaningful case and you care about the distinction, perhaps the assertion message should change to "Cntr must not be signed" (as an alternative to my proposed switch to is_unsigned)?
• user52292: Adding the cast to unsigned helper fixed it: return static_cast<Accu>(accu + value) < accu; - en.cppreference.com/w/cpp/language/implicit_conversion - Integral promotion
• Toby Speight: BTW, does your compiler have overflow-detecting arithmetic builtins, as GCC does? That could gain you speed at the expense of portability, if that's important.