Saturated signed addition

Question

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

int saturating_add(int x , int y) { 
 int sum = x + y;
 int w = (sizeof(int) << 3) -1;
 int mask = (~(x ^ y) & (y ^ sum) & (x ^ sum)) >> w;
 int max_min = (1 << w) ^ (sum >> w);
 return (~mask & sum) + (mask & max_min);
}

Compiled code in my machine

Note: I used the following command -> gcc -O2 -S sat_add.c.

leal (%rdi,%rsi), %edx
 movl %edx, %eax
 movl %edx, %ecx
 xorl %esi, %eax
 xorl %edi, %esi
 xorl %edx, %edi
 notl %esi
 sarl 31,ドル %ecx
 andl %esi, %eax
 addl $-2147483648, %ecx
 andl %edi, %eax
 sarl 31,ドル %eax
 movl %eax, %esi
 andl %ecx, %eax
 notl %esi
 andl %edx, %esi
 leal (%rsi,%rax), %eax
 ret

So I want to know if there is a better solution in terms of elegance and performance. Also if there is a solution that compiles to a single instruction in x86_64 (Maybe PADDS although this instruction may not be the one I am looking for). Also any other kind of feedback is welcome.

• Quuxplusone: The line int sum = x + y; will overflow (and invoke undefined behavior) if x + y is greater than INT_MAX. But you might be able to salvage something by casting x and y to unsigned int first, and then using unsigned int throughout. Care to try again? :)
• MAG: hmmm yes it will overflow , thats the point when it overflows I need to return INT_MAX. Also forgot to mention that two's complement representation is assumed. So casting to unsinged int will result in the same bit level representation.
• Quuxplusone: C doesn't assume two's complement, though. If you get to assume two's complement, then the problem becomes pretty much trivial. Are you looking specifically for the best answer in (inline) x86-64 assembly?
• MAG: Yes I know C doesn't assumed two's complement but the exercise stated it and i forgot to mention it (Already edit it). No Im not looking for a inline x86-64 assembly solution. Just wanted to know if there is a more concise way of doing it and If there is a solution that can be compiled to a single instruction in x86-64 with a certain level of optimization (0g, 01, 02.. etc)

Answer 1

Undefined behavior from signed overflow

Technically, your first line causes undefined behavior:

int sum = x + y;

It should be written instead as:

int sum = (unsigned int) x + y;

In C, signed integer overflow is undefined behavior but unsigned integer overflow is not. Your compiler probably will treat the two lines above identically, but to be safe you should use the unsigned add.

Save a couple of instructions

This line here could be optimized:

int mask = (~(x ^ y) & (y ^ sum) & (x ^ sum)) >> w;

to this:

int mask = (~(x ^ y) & (x ^ sum)) >> w;

If x and y have the same sign, then you only need to check one of them against sum instead of both of them. This saves 2 assembly instructions when you compile it.