simulate jg instruction(datalab's isGreater)

Question

I am doing CSAPP's datalab, the isGreater function.
Here's the description

isGreater - if x > y  then return 1, else return 0
   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
   Legal ops: ! ~ & ^ | + << >>
   Max ops: 24
   Rating: 3

x and y are both int type.
So i consider to simulate the jg instruction to implement it.Here's my code

int isGreater(int x, int y)
{
    int yComplement = ~y + 1;
    int minusResult = x + yComplement;  // 0xffffffff
    int SF = (minusResult >> 31) & 0x1; // 1
    int ZF = !minusResult; // 0
    int xSign = (x >> 31) & 0x1; // 0 
    int ySign = (yComplement >> 31) & 0x1; // 1
    int OF = !(xSign ^ ySign) & (xSign ^ SF); // 0
    return !(OF ^ SF) & !ZF;
}

The jg instruction need SF == OF and ZF == 0.
But it can't pass a special case, that is, x = 0x7fffffff(INT_MAX), y = 0x80000000(INT_MIN).
I deduce it like this:
x + yComplement = 0xffffffff, so SF = 1, ZF = 0, since xSign != ySign, the OF is set to 0.
So, what's wrong with my code, is my OF setting operation wrong?

Answer 1

You're detecting overflow in the addition x + yComplement, rather than in the overall subtraction

-INT_MIN itself overflows in 2's complement; INT_MIN == -INT_MIN. This is the 2's complement anomaly¹.

You should be getting fast-positive overflow detection for any negative number (other than INT_MIN) minus INT_MIN. The resulting addition will have signed overflow. e.g. -10 + INT_MIN overflows.

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt has a table of input/output signs for add and subtraction. The cases that overflow are where the inputs signs are opposite but the result sign matches y.

      SUBTRACTION SIGN BITS  (for num1 - num2 = sum)
    num1sign num2sign sumsign
   ---------------------------
        0 0 0
        0 0 1
        0 1 0
 *OVER* 0 1 1 (subtracting a negative is the same as adding a positive)
 *OVER* 1 0 0 (subtracting a positive is the same as adding a negative)
        1 0 1
        1 1 0
        1 1 1

You could use this directly with the original x and y, and only use yComplement as part of getting the minusResult. Adjust your logic to match this truth table.

Or you could use int ySign = (~y) >> 31; and leave the rest of your code unmodified. (Use a tmp to hold ~y so you only do the operation once, for this and yComplement). The one's complement inverse (~) does not suffer from the 2's complement anomaly.

---

Footnote 1: sign/magnitude and one's complement have two redundant ways to represent 0, instead of an value with no inverse.

Fun fact: if you make an integer absolute-value function, you should consider the result unsigned to avoid this problem. int can't represent the absolute value of INT_MIN.

---

Efficiency improvements:

If you use unsigned int, you don't need & 1 after a shift because logical shifts don't sign-extend. (And as a bonus, it would avoid C signed-overflow undefined behaviour in +: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html).

Then (if you used uint32_t, or sizeof(unsigned) * CHAR_BIT instead of 31) you'd have a safe and portable implementation of 2's complement comparison. (signed shift semantics for negative numbers are implementation-defined in C.) I think you're using C as a sort of pseudo-code for bit operations, and aren't interested in actually writing a portable implementation, and that's fine. The way you're doing things will work on normal compilers on normal CPUs.

Or you can use & 0x80000000 to leave the high bits in place (but then you'd have to left shift your ! result).

It's just the lab's restriction, you can't use unsigned or any constant larger than 0xff(255)

Ok, so you don't have access to logical right shift. Still, you need at most one &1. It's ok to work with numbers where all you care about is the low bit, but where the rest hold garbage.

You eventually do & !ZF, which is either &0 or &1. Thus, any high garbage in OF` is wiped away.

You can also delay the >> 31 until after XORing together two numbers.

---

This is a fun problem that I want to optimize myself:

// untested, 13 operations
int isGreater_optimized(int x, int y)
{
    int not_y = ~y;
    
    int minus_y = not_y + 1;
    int sum = x + minus_y;

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible

    int OF = (x_vs_y & x_vs_sum) >> 31;   // high bits hold garbage
    int SF = sum >> 31;

    int non_zero = !!sum;              // 0 or 1
    return (~(OF ^ SF)) & non_zero;      // high garbage is nuked by `& 1`
}

Note the use of ~ instead of ! to invert a value that has high garbage.

It looks like there's still some redundancy in calculating OF separately from SF, but actually the XORing of sum twice doesn't cancel out. x ^ sum is an input for &, and we XOR with sum after that.

We can delay the shifts even later, though, and I found some more optimizations by avoiding an extra inversion. This is 11 operations

// replace 31 with  sizeof(int) * CHAR_BIT  if you want.  #include <limit.h>
// or use int32_t

int isGreater_optimized2(int x, int y)
{
    int not_y = ~y;

    int minus_y = not_y + 1;
    int sum = x + minus_y;
    int SF = sum;             // value in the high bit, rest are garbage

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible
    int OF = x_vs_y & x_vs_sum;   // low bits hold garbage

    int less = (OF ^ SF);
    int ZF   = !sum;               // 0 or 1
    int le   = (less >> 31) & ZF;  // clears high garbage
    return  !le;                   // jg == jnle
}

I wondered if any compilers might see through this manual compare and optimize it into cmp edi, esi/ setg al, but no such luck :/ I guess that's not a pattern that they look for, because code that could have been written as x > y tends to be written that way :P

But anyway, here's the x86 asm output from gcc and clang on the Godbolt compiler explorer.

Answer 2

Assuming two's complement, INT_MIN's absolute value isn't representable as an int. So, yComplement == y (ie. still negative), and ySign is 1 instead of the desired 0.

You could instead calculate the sign of y like this (changing as little as possible in your code) :

int ySign = !((y >> 31) & 0x1);

For a more detailed analysis, and a more optimal alternative, check Peter Cordes' answer.