package org.bouncycastle.math.ec;

import java.math.BigInteger;

/**
 * Class implementing the WNAF (Window Non-Adjacent Form) multiplication
 * algorithm.
 */
public class WNafL2RMultiplier extends AbstractECMultiplier
{
    /**
     * Multiplies <code>this</code> by an integer <code>k</code> using the
     * Window NAF method.
     * @param k The integer by which <code>this</code> is multiplied.
     * @return A new <code>ECPoint</code> which equals <code>this</code>
     * multiplied by <code>k</code>.
     */
    protected ECPoint multiplyPositive(ECPoint p, BigInteger k)
    {
        // Clamp the window width in the range [2, 16]
        int width = Math.max(2, Math.min(16, getWindowSize(k.bitLength())));

        WNafPreCompInfo wnafPreCompInfo = WNafUtil.precompute(p, width, true);
        ECPoint[] preComp = wnafPreCompInfo.getPreComp();
        ECPoint[] preCompNeg = wnafPreCompInfo.getPreCompNeg();

        int[] wnaf = WNafUtil.generateCompactWindowNaf(width, k);

        ECPoint R = p.getCurve().getInfinity();

        int i = wnaf.length;
        while (--i >= 0)
        {
            int wi = wnaf[i];
            int digit = wi >> 16, zeroes = wi & 0xFFFF;

            int index = Math.abs(digit) >>> 1;
            ECPoint r = digit < 0 ? preCompNeg[index] : preComp[index];

            R = R.twicePlus(r);
            R = R.timesPow2(zeroes);
        }

        return R;
    }

    /**
     * Determine window width to use for a scalar multiplication of the given size.
     * 
     * @param bits the bit-length of the scalar to multiply by
     * @return the window size to use
     */
    protected int getWindowSize(int bits)
    {
        return WNafUtil.getWindowSize(bits);
    }
}

@@ -1062,24 +1062,25 @@
 length;%0A
+%0A
         
 while (-
@@ -1075,25 +1075,350 @@
     
-while (--i %3E= 0)%0A
+/*%0A         * NOTE This code optimizes the first window using the precomputed points to substitute an%0A         * addition for 2 or more doublings. Not enabled until performance can be analyzed more,%0A         * especially for coordinate systems where doubling is significantly cheaper than addition.%0A         */%0A        //        if (i %3E 1)%0A//
     
@@ -1419,24 +1419,26 @@
 //        %7B%0A
+//
             
@@ -1455,12 +1455,16 @@
 naf%5B
+--
 i%5D;%0A
+//
     
@@ -1515,17 +1515,21 @@
 0xFFFF;%0A
-%0A
+//%0A//
         
@@ -1536,21 +1536,17 @@
     int 
-index
+n
  = Math.
@@ -1559,16 +1559,12 @@
 git)
- %3E%3E%3E 1
 ;%0A
+//
     
@@ -1578,18 +1578,24 @@
  ECPoint
- r
+%5B%5D table
  = digit
@@ -1615,31 +1615,1005 @@
 pNeg
-%5Bindex%5D : preComp%5Bindex
+ : preComp;%0A//%0A//            int window = width - 1;%0A//            if ((n %3C%3C 1) %3C (1 %3C%3C window))%0A//            %7B%0A//                int highest = IntArray.bitLengths%5Bn%5D - 1;%0A//                int lowBits =  n %5E (1 %3C%3C highest);%0A//                int scale = window - highest;%0A//%0A//                int i1 = ((1 %3C%3C window) - 1);%0A//                int i2 = (lowBits %3C%3C scale) + 1;%0A//%0A//                R = table%5Bi1 %3E%3E%3E 1%5D.add(table%5Bi2 %3E%3E%3E 1%5D);%0A//                zeroes -= scale;%0A//%0A////              System.out.println(%22Optimized: 2%5E%22 + scale + %22 * %22 + n + %22 = %22 + i1 + %22 + %22 + i2);%0A//            %7D%0A//            else%0A//            %7B%0A//                R = table%5Bn %3E%3E%3E 1%5D;%0A//            %7D%0A//%0A//            R = R.timesPow2(zeroes);%0A//        %7D%0A%0A        while (i %3E 0)%0A        %7B%0A            int wi = wnaf%5B--i%5D;%0A            int digit = wi %3E%3E 16, zeroes = wi & 0xFFFF;%0A%0A            int n = Math.abs(digit);%0A            ECPoint%5B%5D table = digit %3C 0 ? preCompNeg : preComp;%0A            ECPoint r = table%5Bn %3E%3E%3E 1
 %5D;%0A%0A

Implement first-digit optimization for WNaf (disabled for the moment)