Efficient Add of Values with Overflow Protection in C/C++

Question

What is the most efficient way to add two scalars in c/c++ with overflow protection? For example, adding two unsigned chars is 255 if a+b >= 255.

I have:

unsigned char inline add_o(unsigned char x, unsigned char y)
{
    const short int maxVal = 255;
    unsigned short int s_short = (unsigned short int) x + (unsigned short int) y;
    unsigned char s_char = (s_short <= maxVal) ? (unsigned char)s_short : maxVal;
    return s_char;
}

that can be driven by:

unsigned char x = 200;
unsigned char y = 129;
unsigned char mySum = add_o(x,y);

I see some ideas here but I am interested in the fastest way to perform this operation---or at least one that is highly palatable to an optimizing compiler.

Answer 1

You mean unsigned saturating arithmetic?

unsigned char inline add_o(unsigned char x, unsigned char y) {
    unsigned char s = x + y;
    s |= (unsigned)(-(s < x));
    return s;
}

Answer 2

For most modern compilers will generate branch-free code for your current solution, which is already fairly good. Few optimisations which are very hardware dependant (x86 in particular) are

1. replace the comparison by a masked and
2. try to make the overflow protection if a conditional move.

This is how I would have done it:

unsigned char inline add_o(unsigned char x, unsigned char y) {
    unsigned short int s_short = (unsigned short int) x + (unsigned short int) y;
    if (s_short & 0xFF00)
        s_short = 0xFF;

    return s_short;
}

Answer 3

The most efficient way is to pre-fill a table with all possible results, then use the addition of x and y to index into that table.

#include <iostream>

unsigned char add_o_results[255+255];

void pre_fill() {
    for (int i = 0 ; i < 255 + 255 ; ++i) {
        add_o_results[i] = std::min(i, 255);
    }
}

unsigned char inline add_o(unsigned char x, unsigned char y)
{
    return add_o_results[x+y];
}

using namespace std;

int main()
{
    pre_fill();

    cout << int(add_o(150, 151)) << endl;
    cout << int(add_o(10, 150)) << endl;

   return 0;
}