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.

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");