Unsigned bit twiddling

[Christian Thalinger]

On Feb 24, 2014, at 9:23 AM, Jim Laskey (Oracle) <james.laskey at oracle.com> wrote:

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

Looking at the history of that file it got imported from the Maxine project so I’m not sure if anyone feels responsible for that.  Maybe Doug.

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