content: package local.org.bouncycastle.math.ec;
  
  import java.math.BigInteger;
  
  /**
   * Class implementing the WNAF (Window Non-Adjacent Form) multiplication
   * algorithm.
   */
  class WNafMultiplier implements ECMultiplier
  {
      /**
       * 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 byte[] windowNaf(byte width, BigInteger k)
      {
          // 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 as short and BigInteger
          short pow2wB = (short)(1 << width);
          BigInteger pow2wBI = BigInteger.valueOf(pow2wB);
  
          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
                  BigInteger remainder = k.mod(pow2wBI);
  
                  // if remainder > 2^(width - 1) - 1
                  if (remainder.testBit(width - 1))
                  {
                      wnaf[i] = (byte)(remainder.intValue() - pow2wB);
                  }
                  else
                  {
                      wnaf[i] = (byte)remainder.intValue();
                  }
                  // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1]
  
                  k = k.subtract(BigInteger.valueOf(wnaf[i]));
                  length = i;
              }
              else
              {
                  wnaf[i] = 0;
              }
  
              // k = k/2
              k = k.shiftRight(1);
              i++;
          }
  
          length++;
  
          // Reduce the WNAF array to its actual length
          byte[] wnafShort = new byte[length];
          System.arraycopy(wnaf, 0, wnafShort, 0, length);
          return wnafShort;
      }
  
      /**
       * 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>.
       */
      public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo)
      {
          WNafPreCompInfo wnafPreCompInfo;
  
          if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo))
          {
              wnafPreCompInfo = (WNafPreCompInfo)preCompInfo;
          }
          else
          {
              // Ignore empty PreCompInfo or PreCompInfo of incorrect type
              wnafPreCompInfo = new WNafPreCompInfo();
          }
  
          // floor(log2(k))
          int m = k.bitLength();
  
          // width of the Window NAF
          byte width;
  
          // Required length of precomputation array
          int reqPreCompLen;
  
          // Determine optimal width and corresponding length of precomputation
          // array based on literature values
          if (m < 13)
          {
              width = 2;
              reqPreCompLen = 1;
          }
          else
          {
              if (m < 41)
              {
                  width = 3;
                  reqPreCompLen = 2;
              }
              else
              {
                  if (m < 121)
                  {
                      width = 4;
                      reqPreCompLen = 4;
                  }
                  else
                  {
                      if (m < 337)
                      {
                          width = 5;
                          reqPreCompLen = 8;
                      }
                      else
                      {
                          if (m < 897)
                          {
                              width = 6;
                              reqPreCompLen = 16;
                          }
                          else
                          {
                              if (m < 2305)
                              {
                                  width = 7;
                                  reqPreCompLen = 32;
                              }
                              else
                              {
                                  width = 8;
                                  reqPreCompLen = 127;
                              }
                          }
                      }
                  }
              }
          }
  
          // The length of the precomputation array
          int preCompLen = 1;
  
          ECPoint[] preComp = wnafPreCompInfo.getPreComp();
          ECPoint twiceP = wnafPreCompInfo.getTwiceP();
  
          // Check if the precomputed ECPoints already exist
          if (preComp == null)
          {
              // Precomputation must be performed from scratch, create an empty
              // precomputation array of desired length
              preComp = new ECPoint[]{ p };
          }
          else
          {
              // Take the already precomputed ECPoints to start with
              preCompLen = preComp.length;
          }
  
          if (twiceP == null)
          {
              // Compute twice(p)
              twiceP = p.twice();
          }
  
          if (preCompLen < reqPreCompLen)
          {
              // Precomputation array must be made bigger, copy existing preComp
              // array into the larger new preComp array
              ECPoint[] oldPreComp = preComp;
              preComp = new ECPoint[reqPreCompLen];
              System.arraycopy(oldPreComp, 0, preComp, 0, preCompLen);
  
              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]);
              }            
          }
  
          // Compute the Window NAF of the desired width
          byte[] wnaf = windowNaf(width, k);
          int l = wnaf.length;
  
          // Apply the Window NAF to p using the precomputed ECPoint values.
          ECPoint q = p.getCurve().getInfinity();
          for (int i = l - 1; i >= 0; i--)
          {
              q = q.twice();
  
              if (wnaf[i] != 0)
              {
                  if (wnaf[i] > 0)
                  {
                      q = q.add(preComp[(wnaf[i] - 1)/2]);
                  }
                  else
                  {
                      // wnaf[i] < 0
                      q = q.subtract(preComp[(-wnaf[i] - 1)/2]);
                  }
              }
          }
  
          // Set PreCompInfo in ECPoint, such that it is available for next
          // multiplication.
          wnafPreCompInfo.setPreComp(preComp);
          wnafPreCompInfo.setTwiceP(twiceP);
          p.setPreCompInfo(wnafPreCompInfo);
          return q;
      }
  
  }
  