[Qemu-devel] [PATCH] int128: optimize

[Qemu-devel] [PATCH] int128: optimize

[Paolo Bonzini]

For add and sub, carry computation only requires checking one of the
arguments (any for add, the LHS for sub because the RHS is negated).
For neg, we can similarly optimize computation of the carry.

For ge, we can just do lexicographic order.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
	Will post unit tests soon.

 include/qemu/int128.h | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)

diff --git a/include/qemu/int128.h b/include/qemu/int128.h
index bfe7678..d36cc7a 100644
--- a/include/qemu/int128.h
+++ b/include/qemu/int128.h
@@ -55,21 +55,20 @@ static inline Int128 int128_rshift(Int128 a, int n)
 
 static inline Int128 int128_add(Int128 a, Int128 b)
 {
-    Int128 r = { a.lo + b.lo, a.hi + b.hi };
-    r.hi += (r.lo < a.lo) || (r.lo < b.lo);
-    return r;
+    uint64_t lo = a.lo + b.lo;
+    return (Int128) { lo, (lo < a.lo) + a.hi + b.hi };
 }
 
 static inline Int128 int128_neg(Int128 a)
 {
-    a.lo = ~a.lo;
-    a.hi = ~a.hi;
-    return int128_add(a, int128_one());
+    uint64_t lo = -a.lo;
+    return (Int128) { lo, ~a.hi + !lo };
 }
 
 static inline Int128 int128_sub(Int128 a, Int128 b)
 {
-    return int128_add(a, int128_neg(b));
+    uint64_t lo = a.lo - b.lo;
+    return (Int128) { lo, (lo < a.lo) + a.hi - b.hi };
 }
 
 static inline bool int128_nonneg(Int128 a)
@@ -89,7 +88,7 @@ static inline bool int128_ne(Int128 a, Int128 b)
 
 static inline bool int128_ge(Int128 a, Int128 b)
 {
-    return int128_nonneg(int128_sub(a, b));
+    return a.hi > b.hi || (a.hi == b.hi && a.lo >= b.lo);
 }
 
 static inline bool int128_lt(Int128 a, Int128 b)
-- 
1.8.1.4

Re: [Qemu-devel] [PATCH] int128: optimize

[Richard Henderson]

On 06/20/2013 08:00 AM, Paolo Bonzini wrote:
>  static inline Int128 int128_sub(Int128 a, Int128 b)
>  {
> -    return int128_add(a, int128_neg(b));
> +    uint64_t lo = a.lo - b.lo;
> +    return (Int128) { lo, (lo < a.lo) + a.hi - b.hi };

This one isn't right.  Consider { 2, 0 } - { 2, 0 }

  lo = 2 - 2 = 0;
  = { 0, (0 < 2) + 0 - 0 }
  = { 0, 1 }

I'd be happier with a more traditional

  (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };


r~

Re: [Qemu-devel] [PATCH] int128: optimize

[Paolo Bonzini]

Il 20/06/2013 18:46, Richard Henderson ha scritto:
> On 06/20/2013 08:00 AM, Paolo Bonzini wrote:
>>  static inline Int128 int128_sub(Int128 a, Int128 b)
>>  {
>> -    return int128_add(a, int128_neg(b));
>> +    uint64_t lo = a.lo - b.lo;
>> +    return (Int128) { lo, (lo < a.lo) + a.hi - b.hi };
> 
> This one isn't right.  Consider { 2, 0 } - { 2, 0 }
> 
>   lo = 2 - 2 = 0;
>   = { 0, (0 < 2) + 0 - 0 }
>   = { 0, 1 }
> 
> I'd be happier with a more traditional
> 
>   (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };

Yeah, I wasn't quite sure of this and I was waiting for testcases to
prove me wrong...  To fix it in the style I used you need

   (Int128){ lo, a.hi - b.hi - (lo > a.lo) }

(We have to sum a + ~b + 1.  We have lo = a.lo + ~b.lo + 1, from which
the carry-out is either lo <= a.lo or lo <= ~b.lo, using <= because of
the carry-in.  Then the high part is

       a.hi + ~b.hi       + (lo <= a.lo)
     = a.hi + (-1 - b.hi) + 1 - (lo > a.lo)
     = a.hi - b.hi        - (lo > a.lo)

).  But I'll go with your version, it probably generates better code
too.

Paolo

[Qemu-devel] [PATCH] int128: optimize

[Jay Foad]

[-- Attachment #1: Type: text/plain, Size: 632 bytes --]

>  static inline Int128 int128_neg(Int128 a)
>  {
> -    a.lo = ~a.lo;
> -    a.hi = ~a.hi;
> -    return int128_add(a, int128_one());
> +    uint64_t lo = -a.lo;
> +    return (Int128) { lo, ~a.hi + !lo };
>  }

This leaves int128_one unused. (Also the temporary lo seems a bit
pointless, since you could just as well write -a.lo and !a.lo.)

>  static inline bool int128_ge(Int128 a, Int128 b)
>  {
> -    return int128_nonneg(int128_sub(a, b));
> +    return a.hi > b.hi || (a.hi == b.hi && a.lo >= b.lo);
>  }

This is a bug fix. The old version gives the wrong answer when a and b are
both large and have opposite signs.

Jay.

[-- Attachment #2: Type: text/html, Size: 958 bytes --]

Re: [Qemu-devel] [PATCH] int128: optimize

[Paolo Bonzini]

Il 02/07/2013 14:46, Jay Foad ha scritto:
>>  static inline Int128 int128_neg(Int128 a)
>>  {
>> -    a.lo = ~a.lo;
>> -    a.hi = ~a.hi;
>> -    return int128_add(a, int128_one());
>> +    uint64_t lo = -a.lo;
>> +    return (Int128) { lo, ~a.hi + !lo };
>>  }
> 
> This leaves int128_one unused. (Also the temporary lo seems a bit
> pointless, since you could just as well write -a.lo and !a.lo.)

The unused int128_one is not a problem, someone might find a use later.

>>  static inline bool int128_ge(Int128 a, Int128 b)
>>  {
>> -    return int128_nonneg(int128_sub(a, b));
>> +    return a.hi > b.hi || (a.hi == b.hi && a.lo >= b.lo);
>>  }
> 
> This is a bug fix. The old version gives the wrong answer when a and b
> are both large and have opposite signs.

We don't really use Int128's that are bigger than 2^64, but you are
right.  I'll add this to the commit message.

Paolo