RFR(L): 8069539: RSA acceleration

[Vladimir Kozlov]

I think it was last mail in open list. There were discussions in private.
Here is upadted webrev:

http://cr.openjdk.java.net/~kvn/8069539/webrev.01/

It include changes in java/math/BigInteger.java which added range checks and moved intrinsified code into private methods.

Andrew Haley has additional suggestions we can discuss now. Andrew, can you show proposed changes to java code?
I would like to have only simple java changes (methods splitting) and do experiments/changes with word-reversal later.

On 4/14/15 10:41 AM, Andrew Haley wrote:
 > On 04/14/2015 06:22 PM, Vladimir Kozlov wrote:
 >
 >> We are discussing how and which checks to add into java code which
 >> calls intrinsified methods to keep intrinsic simple.
 >
 > Yes, good idea.  While you're in there, there's a couple of thoughts I'd
 > like to draw your attention to.
 >
 > Montgomery multiplication and squaring are implemented as separate
 > steps, like so:
 >
 >          a = multiplyToLen(t, modLen, mult, modLen, a);
 >          a = montReduce(a, mod, modLen, inv);
 >
 >          a = squareToLen(t, modLen, a);
 >          a = montReduce(a, mod, modLen, inv);
 >
 > It is possible to interleave the multiplication and Montgomery
 > reduction, and this can lead to a useful speedup on some
 > architectures.  It would be nice if Montgomery multiplication and
 > squaring were factored into separate methods, and then they could be
 > replaced by intrinsics.
 >
 > Also, all these word-reversal and misaligned long stores / loads in
 > the multiplyToLen intrinsic code are a real PITA.  If we word-reversed
 > the arrays so that they were in little-endian form we'd have neither
 > misaligned long stores / loads nor repeated word-reversals.  We could
 > do the word reversal on the stack: AFAICS it's unusual for
 > multiplyToLen to be called for huge bignums, and I suppose if it did
 > happen for a bignum larger than some threshold we could do the word
 > reversal on the heap.
 >
 > Andrew.

Thanks,
Vladimir

On 3/23/15 6:59 AM, Florian Weimer wrote:
> On 03/20/2015 11:45 PM, Viswanathan, Sandhya wrote:
>> Hi Florian,
>>
>> My thoughts on this are as follows:
>>
>> BigInteger.squareToLen is a private method and not a public method.
>> The length calculation code in Java version of this method does not have the overflow check and the intrinsic follows the Java code.
>>
>> private static final int[] squareToLen(int[] x, int len, int[] z) {
>>          ...
>>          int zlen = len << 1;
>>          if (z == null || z.length < zlen)
>>              z = new int[zlen];
>>          ...
>>    }
>
> The difference is that the Java code will still perform the bounds
> checks on each array access, I think, so even if zlen turns out negative
> (and thus no reallocation happens), damage from out-of-bounds accesses
> will be non-existent.
>
>> Also the underlying array in BigInteger cannot be greater than MAX_MAG_LENGTH which is defined as:
>>
>> private static final int MAX_MAG_LENGTH = Integer.MAX_VALUE / Integer.SIZE + 1; // (1 << 26)
>>
>> So zlen calculation cannot overflow as int array x and its length len is coming from a BigInteger array.
>
> Maybe can you add this as a comment to the intrinsic?  I think this
> would be a useful addition, especially if at some point in the future,
> someone else uses your code as a template to implement their own intrinsic.
>
>> Similarly mulAdd is a package private method and its inputs are allocated or verified at call sites.
>
> Same here.
>