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


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.

• 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? :) – Quuxplusone Jan 5 '16 at 5:33
• 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. – MAG Jan 5 '16 at 5:39
• 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? – Quuxplusone Jan 5 '16 at 5:54
• 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) – MAG Jan 5 '16 at 6:01

### 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.

• Ah I can't believe I missed that second one, thanks – MAG Jan 5 '16 at 20:53