package org.bouncycastle.math.ec;

import java.math.BigInteger;

public abstract class WNafUtil
{
    private static int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 };

    /**
     * Computes the Window NAF (non-adjacent Form) of an integer.
     * @param width The width <code>w</code> of the Window NAF. The width is
     * defined as the minimal number <code>w</code>, such that for any
     * <code>w</code> consecutive digits in the resulting representation, at
     * most one is non-zero.
     * @param k The integer of which the Window NAF is computed.
     * @return The Window NAF of the given width, such that the following holds:
     * <code>k = &sum;<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
     * </code>, where the <code>k<sub>i</sub></code> denote the elements of the
     * returned <code>byte[]</code>.
     */
    public static byte[] generateWindowNaf(int width, BigInteger k)
    {
        if (width < 2 || width > 8)
        {
            throw new IllegalArgumentException("'width' must be in the range [2, 8]");
        }

        // The window NAF is at most 1 element longer than the binary
        // representation of the integer k. byte can be used instead of short or
        // int unless the window width is larger than 8. For larger width use
        // short or int. However, a width of more than 8 is not efficient for
        // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than
        // 1000 Bits are currently not used in practice.
        byte[] wnaf = new byte[k.bitLength() + 1];

        // 2^width and a mask and sign bit set accordingly
        int pow2 = 1 << width;
        int mask = pow2 - 1;
        int sign = pow2 >>> 1;

        int i = 0;

        // The actual length of the WNAF
        int length = 0;

        // while k >= 1
        while (k.signum() > 0)
        {
            // if k is odd
            if (k.testBit(0))
            {
                // k mod 2^width
                int digit = k.intValue() & mask;
                if ((digit & sign) != 0)
                {
                    digit -= pow2;
                }

                // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1]
                wnaf[i] = (byte)digit;

                k = k.subtract(BigInteger.valueOf(digit));
                length = i;
            }
            else
            {
                wnaf[i] = 0;
            }

            // k = k/2
            k = k.shiftRight(1);
            i++;
        }

        length++;

        // Reduce the WNAF array to its actual length
        if (wnaf.length > length)
        {
            wnaf = trim(wnaf, length);
        }
        
        return wnaf;
    }

    public static WNafPreCompInfo getWNafPreCompInfo(PreCompInfo preCompInfo)
    {
        if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo))
        {
            return (WNafPreCompInfo)preCompInfo;
        }

        return new WNafPreCompInfo();
    }

    /**
     * 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
     */
    public static int getWindowSize(int bits)
    {
        return getWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS);
    }

    /**
     * Determine window width to use for a scalar multiplication of the given size.
     * 
     * @param bits the bit-length of the scalar to multiply by
     * @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width
     * @return the window size to use
     */
    public static int getWindowSize(int bits, int[] windowSizeCutoffs)
    {
        int w = 0;
        for (; w < windowSizeCutoffs.length; ++w)
        {
            if (bits < windowSizeCutoffs[w])
            {
                break;
            }
        }
        return w + 2;
    }

    public static WNafPreCompInfo precompute(ECPoint p, PreCompInfo preCompInfo, int width)
    {
        WNafPreCompInfo wnafPreCompInfo = getWNafPreCompInfo(preCompInfo);

        ECPoint[] preComp = wnafPreCompInfo.getPreComp();
        if (preComp == null)
        {
            preComp = new ECPoint[]{ p.normalize() };
        }

        int preCompLen = preComp.length;
        int reqPreCompLen = 1 << Math.max(0, width - 2);

        if (preCompLen < reqPreCompLen)
        {
            ECPoint twiceP = wnafPreCompInfo.getTwiceP();
            if (twiceP == null)
            {
                twiceP = p.twice().normalize();
                wnafPreCompInfo.setTwiceP(twiceP);
            }

            preComp = resizeTable(preComp, reqPreCompLen);
            for (int i = preCompLen; i < reqPreCompLen; i++)
            {
                /*
                 * Compute the new ECPoints for the precomputation array. The values 1, 3, 5, ...,
                 * 2^(width-1)-1 times p are computed
                 */
                preComp[i] = twiceP.add(preComp[i - 1]).normalize();
            }            
        }

        wnafPreCompInfo.setPreComp(preComp);
        p.setPreCompInfo(wnafPreCompInfo);

        return wnafPreCompInfo;
    }

    private static byte[] trim(byte[] bs, int length)
    {
        byte[] result = new byte[length];
        System.arraycopy(bs, 0, result, 0, result.length);
        return result;
    }

    private static ECPoint[] resizeTable(ECPoint[] ps, int length)
    {
        ECPoint[] result = new ECPoint[length];
        System.arraycopy(ps, 0, result, 0, ps.length);
        return result;
    }
}

@@ -189,16 +189,453 @@
 305 %7D;%0A%0A
+    public static byte%5B%5D generateNaf(BigInteger k)%0A    %7B%0A        BigInteger _3k = k.shiftLeft(1).add(k);%0A%0A        int digits = _3k.bitLength() - 1;%0A        byte%5B%5D wnaf = new byte%5Bdigits%5D;%0A%0A        for (int i = 1; i %3C= digits; ++i)%0A        %7B%0A            boolean _3kBit = _3k.testBit(i);%0A            boolean kBit = k.testBit(i);%0A%0A            wnaf%5Bi - 1%5D = (byte)(_3kBit == kBit ? 0 : kBit ? -1 : 1);%0A        %7D%0A%0A        return wnaf;%0A    %7D%0A%0A
     /**%0A
@@ -1369,32 +1369,112 @@
 nteger k)%0A    %7B%0A
+        if (width == 2)%0A        %7B%0A            return generateNaf(k);%0A        %7D%0A%0A
         if (widt

Add generateNaf as special case with window width 2