From b9f0dceb0ccf79356ec33dec264a1687a3edc622 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Sun, 26 Jan 2014 10:17:26 +0700 Subject: Adjust first-digit optimization to not be so conservative --- crypto/src/math/ec/multiplier/WNafMultiplier.cs | 19 +++++++------------ 1 file changed, 7 insertions(+), 12 deletions(-) (limited to 'crypto/src/math/ec/multiplier/WNafMultiplier.cs') diff --git a/crypto/src/math/ec/multiplier/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafMultiplier.cs index c2bb8c465..06ad76031 100644 --- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WNafMultiplier.cs @@ -32,7 +32,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier int i = wnaf.Length; /* - * NOTE This code optimizes the first window using the precomputed points to substitute an + * NOTE: We try to optimize the first window using the precomputed points to substitute an * addition for 2 or more doublings. */ if (i > 1) @@ -43,19 +43,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier int n = System.Math.Abs(digit); ECPoint[] table = digit < 0 ? preCompNeg : preComp; - /* - * NOTE: We use this optimization conservatively, since some coordinate systems have - * significantly cheaper doubling relative to addition. - * - * (n << 2) selects precomputed values in the lower half of the table - * (n << 3) selects precomputed values in the lower quarter of the table - */ - //if ((n << 2) < (1 << width)) - if ((n << 3) < (1 << width)) + // Optimization can only be used for values in the lower half of the table + if ((n << 2) < (1 << width)) { int highest = LongArray.BitLengths[n]; - int lowBits = n ^ (1 << (highest - 1)); + + // TODO Get addition/doubling cost ratio from curve and compare to 'scale' to see if worth substituting? int scale = width - highest; + int lowBits = n ^ (1 << (highest - 1)); int i1 = ((1 << (width - 1)) - 1); int i2 = (lowBits << scale) + 1; @@ -63,7 +58,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier zeroes -= scale; - // Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); + //Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); } else { -- cgit 1.4.1