Unsigned bit twiddling

[Thomas Wuerthinger]

Thanks for the patch, Jim. I will integrate it. - thomas

On 26 Feb 2014, at 05:16, Christian Thalinger <christian.thalinger at oracle.com> wrote:

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