Do we need an unsigned multiplyHigh?

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Do we need an unsigned multiplyHigh?

Andrew Haley
We now have a multiplyHigh intrinsic, but it is signed.  Unsigned
multiplyHigh is in general a more useful primitive for crypto than
signed, and I wonder if we need an intrinsic for that as well.  I've
looked at cooking up an unsigned multiplyHigh in Java, and I think the
fastest way is this:

    private static final long unsignedMultiplyHigh(long a, long b) {
        long result = Math.multiplyHigh(a, b);
        if (a < 0)  result += b;
        if (b < 0)  result += a;
        // Can also be written as:
        // result += (a >> 63) & b;
        // result += (b >> 63) & a;
        return result;
    }

It's still about 50% slower than the signed multiplyHigh, though.
Thoughts?

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Adam Petcher
I agree that an unsigned multiplyHigh would be useful for crypto
purposes, and we should consider adding it. Of course, I would much
rather have multiply operations that return both 64-bit parts of the
result, but that is going to be hard to do well without value types. So
it would be nice to have something like this in the meantime.

If we are going to add this operation, it should probably be added along
with an intrinsic. I think the Java code can simply factor out the else
branch from the existing multiplyHigh code. This way,
unsignedMultiplyHigh will be at least as fast as multiplyHigh, whether
the intrinsic implementation is available or not.

If possible, the implementation of this operation should not branch on
either operand. This would make it more widely useful for constant-time
crypto implementations. Though this property would need to go into the
spec in order for constant-time crypto code to use this method, and I
don't know how reasonable it is to put something like this in the spec.

Side note: at the moment, I am using signed arithmetic in prototypes for
Poly1305, X25519, and EdDSA, partially due to lack of support for
unsigned operations like this one. I don't think having
unsignedMultiplyHigh would, on its own, convince me to use an unsigned
representation, but the forces are different for each
algorithm/implementation.


On 9/25/2017 10:50 AM, Andrew Haley wrote:

> We now have a multiplyHigh intrinsic, but it is signed.  Unsigned
> multiplyHigh is in general a more useful primitive for crypto than
> signed, and I wonder if we need an intrinsic for that as well.  I've
> looked at cooking up an unsigned multiplyHigh in Java, and I think the
> fastest way is this:
>
>      private static final long unsignedMultiplyHigh(long a, long b) {
>          long result = Math.multiplyHigh(a, b);
>          if (a < 0)  result += b;
>          if (b < 0)  result += a;
>          // Can also be written as:
>          // result += (a >> 63) & b;
>          // result += (b >> 63) & a;
>          return result;
>      }
>
> It's still about 50% slower than the signed multiplyHigh, though.
> Thoughts?
>

Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Andrew Haley
On 25/09/17 18:21, Adam Petcher wrote:
> I agree that an unsigned multiplyHigh would be useful for crypto
> purposes, and we should consider adding it. Of course, I would much
> rather have multiply operations that return both 64-bit parts of the
> result, but that is going to be hard to do well without value types. So
> it would be nice to have something like this in the meantime.

I take your point, but it won't be excruciatingly difficult for the C2
compiler to turn the multiply operations into a single one, if the CPU
can do that.  From what I've seen recently, though, on non-x86 it's
common for the two halves of the result to be calculated by separate
instructions.

> If we are going to add this operation, it should probably be added
> along with an intrinsic. I think the Java code can simply factor out
> the else branch from the existing multiplyHigh code. This way,
> unsignedMultiplyHigh will be at least as fast as multiplyHigh,
> whether the intrinsic implementation is available or not.

Sure.  I can do that.

> If possible, the implementation of this operation should not branch on
> either operand. This would make it more widely useful for constant-time
> crypto implementations. Though this property would need to go into the
> spec in order for constant-time crypto code to use this method, and I
> don't know how reasonable it is to put something like this in the spec.

OK.  I can do it so that there are no branches in the Java.  The Java
code for signed multiplyHigh has some data-dependent branches in an
attempt to speed it up, though.  I don't know how effective they are,
and I could have a look at taking them out.

> Side note: at the moment, I am using signed arithmetic in prototypes for
> Poly1305, X25519, and EdDSA, partially due to lack of support for
> unsigned operations like this one. I don't think having
> unsignedMultiplyHigh would, on its own, convince me to use an unsigned
> representation, but the forces are different for each
> algorithm/implementation.

Sure.  I don't think it really matters from a performance point of
view which you use, given intrinsics for both.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Andrew Haley
On 26/09/17 08:25, Peter Lawrey wrote:
> I am looking forward to intrinsic support for 128 bit math using ?Long2?
> and XMM (or even YMM, ZMM) instructions.
> This is the best way forward, I hope.
>
> Personally I would like to see a long long type, or even uint128, uint256,
> uint512 style notation.
>
> Another option might be something like long<128> or an annotation like
> @uint128 long or even @decimal128 double but who knows.

Do you actually need any of that?  I think vector types make more sense.
Java already has a great many scalar types.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Andrew Haley
On 26/09/17 11:20, Peter Lawrey wrote:
> We have arrays already but we don't have primitive types of more than
> 64-bit. If we had uint128 for example we wouldn't need this method.

Perhaps not, but why is needing this method a problem?

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Andrew Haley
On 26/09/17 15:53, Peter Lawrey wrote:
> None, except you end up jumping through hoops to implement 128 bit
> arithmetic efficiently or cleanly. At some point language support for such
> a basic operation is the simplest and clearest solution.

There's nothing inefficient about this approach.  I don't quite see
how 128-bit types help with cleanliness, because then you'd need a
multiplyHigh for 128-bit types, surely?  You need that for the type
system to be complete.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Andrew Haley
On 27/09/17 11:28, Peter Lawrey wrote:
> If you need multiplyHigh for 128-bit then you need uint256. At some point
> you have to decide whether you need that many bits as a supported
> operation.  When Java was created a 64-bit long as the widest type made
> sense, however CPUs such as x64 now support 128, 256 and 512 bit natively
> and having the JVM dong its best to work this out is not as clean as
> defining it explicitly.

I guess cleanliness is in the eye of the beholder.  IMO multiplyHigh is
as clean as we need, and I'd rather see more complexity there than in
the type system.  It'd be nice to be able to return more than one scalar
value from a method, for sure.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

John Rose-3
On Sep 27, 2017, at 8:25 AM, Peter Lawrey <[hidden email]> wrote:

Perhaps project Valhalla will be a way to return multiple values by having
a composite value type, or panama with it's support for XMM instructions
(or both)

That seems likely; we are aiming in both of those directions,
to support direct programming with AVX-type registers (not
just x86 specific, by the way) and general support for by-value
return of structured objects (starting with "minimal value types").

For now, though, every method is limited to at most 64 bits
of return value "payload", which means that 128-bit operations
need to be split into two method calls, or else buffer their
result into a temp object (e.g., array).  The JIT knows how
to combine two intrinsic calls into a single machine operation,
in some very limited circumstances, notably the classic
"div/rem" instructions.  This technique would probably work
for 64-to-128 multiplies.  (Also AES-128, by the way.)

— John