Unsigned bit twiddling

[Jim Laskey (Oracle)]

I had a slight change for com.oracle.graal.api.code.UnsignedMath - doesn’t affect int on 64 bit but does on 32 bit and makes long compares 10% faster. Don’t know if it’s used much in graal, but it irks me when I see complex implementations when it can be done simpler.

-- Jim

diff -r 39076a984c33 graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/UnsignedMath.java
--- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/UnsignedMath.java	Wed Feb 19 00:39:44 2014 -0800
+++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/UnsignedMath.java	Mon Feb 24 13:17:57 2014 -0400
@@ -29,65 +29,81 @@
 /**
  * Utilities for unsigned comparisons. All methods have correct, but slow, standard Java
  * implementations so that they can be used with compilers not supporting the intrinsics.
+ *
+ * The technique employed here is to use the isomorphism between signed and unsigned
+ * ints created by toggling the sign bit.  This maps one from to the other while
+ * preserving comparison order.
+ *
+ * int Map(int x) { return x ^ 0x80000000; }
+ *
+ * Map(0u)          == 0x80000000 (MIN_VALUE)
+ * Map(1u)          == 0x80000001
+ * Map(0x7FFFFFFFu) == -1
+ * Map(0x80000000u) == 0
+ * Map(0x80000001u) == 1
+ * Map(0xFFFFFFFEu) == 0x7FFFFFFE
+ * Map(0xFFFFFFFFu) == 0x7FFFFFFF (MAX_VALUE)
  */
 public class UnsignedMath {
 
+    private static final int  INTTOGGLE  = 0x80000000;
+    private static final long LONGTOGGLE = 0x8000000000000000L;
     private static final long MASK = 0xffffffffL;
 
     /**
      * Unsigned comparison aboveThan for two numbers.
      */
     public static boolean aboveThan(int a, int b) {
-        return (a & MASK) > (b & MASK);
+        return (a ^ INTTOGGLE) > (b ^ INTTOGGLE);
     }
 
     /**
      * Unsigned comparison aboveOrEqual for two numbers.
      */
     public static boolean aboveOrEqual(int a, int b) {
-        return (a & MASK) >= (b & MASK);
+        return (a ^ INTTOGGLE) >= (b ^ INTTOGGLE);
     }
 
     /**
      * Unsigned comparison belowThan for two numbers.
      */
     public static boolean belowThan(int a, int b) {
-        return (a & MASK) < (b & MASK);
+        return (a ^ INTTOGGLE) < (b ^ INTTOGGLE);
     }
 
     /**
      * Unsigned comparison belowOrEqual for two numbers.
      */
     public static boolean belowOrEqual(int a, int b) {
-        return (a & MASK) <= (b & MASK);
+        return (a ^ INTTOGGLE) <= (b ^ INTTOGGLE);
     }
 
     /**
      * Unsigned comparison aboveThan for two numbers.
      */
     public static boolean aboveThan(long a, long b) {
-        return (a > b) ^ ((a < 0) != (b < 0));
+        return (a ^ LONGTOGGLE) > (b ^ LONGTOGGLE);
     }
 
     /**
      * Unsigned comparison aboveOrEqual for two numbers.
      */
     public static boolean aboveOrEqual(long a, long b) {
-        return (a >= b) ^ ((a < 0) != (b < 0));
+        return (a ^ LONGTOGGLE) >= (b ^ LONGTOGGLE);
     }
 
     /**
      * Unsigned comparison belowThan for two numbers.
      */
     public static boolean belowThan(long a, long b) {
-        return (a < b) ^ ((a < 0) != (b < 0));
+        return (a ^ LONGTOGGLE) < (b ^ LONGTOGGLE);
     }
 
     /**
      * Unsigned comparison belowOrEqual for two numbers.
      */
     public static boolean belowOrEqual(long a, long b) {
-        return (a <= b) ^ ((a < 0) != (b < 0));
+        return (a ^ LONGTOGGLE) <= (b ^ LONGTOGGLE);
     }
 
     /**