1
\$\begingroup\$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.