From d64985881f898bc4779d31cf618e1a04b1cece6f Mon Sep 17 00:00:00 2001
From: Peter Dettman <peter.dettman@bouncycastle.org>
Date: Fri, 24 Jan 2014 10:40:37 +0700
Subject: Track uvLen to reduce shifting for small operands

---
 crypto/src/math/ec/Mod.cs | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)

(limited to 'crypto/src/math/ec')

diff --git a/crypto/src/math/ec/Mod.cs b/crypto/src/math/ec/Mod.cs
index 57f75ed12..465aa5e41 100644
--- a/crypto/src/math/ec/Mod.cs
+++ b/crypto/src/math/ec/Mod.cs
@@ -21,7 +21,7 @@ namespace Org.BouncyCastle.Math.EC
 
             if ((u[0] & 1) == 0)
             {
-                InversionStep(p, u, a);
+                InversionStep(p, u, len, a);
             }
             if (Nat.IsOne(len, u))
             {
@@ -32,15 +32,22 @@ namespace Org.BouncyCastle.Math.EC
             uint[] v = Nat.Copy(len, p);
             uint[] b = Nat.Create(len);
 
+            int uvLen = len;
+
             for (;;)
             {
+                while (u[uvLen - 1] == 0 && v[uvLen - 1] == 0)
+                {
+                    --uvLen;
+                }
+
                 if (Nat.Gte(len, u, v))
                 {
                     Subtract(p, a, b, a);
                     Nat.Sub(len, u, v, u);
                     if ((u[0] & 1) == 0)
                     {
-                        InversionStep(p, u, a);
+                        InversionStep(p, u, uvLen, a);
                     }
                     if (Nat.IsOne(len, u))
                     {
@@ -54,7 +61,7 @@ namespace Org.BouncyCastle.Math.EC
                     Nat.Sub(len, v, u, v);
                     if ((v[0] & 1) == 0)
                     {
-                        InversionStep(p, v, b);
+                        InversionStep(p, v, uvLen, b);
                     }
                     if (Nat.IsOne(len, v))
                     {
@@ -75,21 +82,23 @@ namespace Org.BouncyCastle.Math.EC
             }
         }
 
-        private static void InversionStep(uint[] p, uint[] u, uint[] x)
+        private static void InversionStep(uint[] p, uint[] u, int uLen, uint[] x)
         {
             int len = p.Length;
             int count = 0;
             while (u[0] == 0)
             {
-                Nat.ShiftDownWord(u, len, 0);
+                Nat.ShiftDownWord(u, uLen, 0);
                 count += 32;
             }
 
-            int zeroes = GetTrailingZeroes(u[0]);
-            if (zeroes > 0)
             {
-                Nat.ShiftDownBits(u, len, zeroes, 0);
-                count += zeroes;
+                int zeroes = GetTrailingZeroes(u[0]);
+                if (zeroes > 0)
+                {
+                    Nat.ShiftDownBits(u, uLen, zeroes, 0);
+                    count += zeroes;
+                }
             }
 
             for (int i = 0; i < count; ++i)
-- 
cgit 1.4.1