Tuesday, January 5, 2016

Saturated signed addition

So this a exercise from the book COMPUTERS SYSTEMS A PROGRAMMERS PERSPECTIVE
I need to add two signed numbers and in case it overflows or underflows return TMAX (011..1b) or TMIN (100..0b) respectively. In this case we can assumed two's complement representation.

The book imposes a set of rules that the solution must follow :
Forbidden:
  1. Conditionals, loops, function calls and macros.
  2. Division, modulus and multiplication.
  3. Relative comparison operators (<, >, <= and >=).
Allowed operations:
  1. All bit level and logic operations.
  2. Left and right shifts, but only with shift amounts between 0 and w - 1
  3. Addition and subtraction.
  4. Equality (==) and inequality (!=) tests.
  5. Casting between int and unsigned.

My code
1
2
3
4
5
6
7
8
int saturating_add(int x, int y) 
{
    int sum = (unsigned int)x + y;
    int w = (sizeof(int) << 3) - 1;
    int mask = (~(x ^ y) & (x ^ sum)) >> w;
    int max_min = (1 << w) ^ (sum >> w);
    return  (~mask & sum) + (mask & max_min);
}