Improved reduction

4 files changed, 100 insertions, 63 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java
index f7548708..ed5cce2e 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java
@@ -130,7 +130,29 @@ public class SecP192R1Field
 
     public static void reduce32(int x, int[] z)
     {
-        if ((x != 0 && (Nat.addWordTo(6, x, z) + Nat.addWordAt(6, x, z, 2) != 0))
+        long cc = 0;
+
+        if (x != 0)
+        {
+            long xx06 = x & M;
+    
+            cc += (z[0] & M) + xx06;
+            z[0] = (int)cc;
+            cc >>= 32;
+            if (cc != 0)
+            {
+                cc += (z[1] & M);
+                z[1] = (int)cc;
+                cc >>= 32;
+            }
+            cc += (z[2] & M) + xx06;
+            z[2] = (int)cc;
+            cc >>= 32;
+
+//            assert cc == 0 || cc == 1;
+        }
+
+        if ((cc != 0 && Nat.incAt(6, z, 3) != 0)
             || (z[5] == P5 && Nat192.gte(z, P)))
         {
             addPInvTo(z);
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java
index 19f88cfb..593053c0 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java
@@ -98,8 +98,10 @@ public class SecP224R1Field
         long t1 = xx08 + xx12;
         long t2 = xx09 + xx13;
 
+        final long n = 1;
+
         long cc = 0;
-        cc += (xx[0] & M) - t0;
+        cc += (xx[0] & M) - t0 + n;
         z[0] = (int)cc;
         cc >>= 32;
         cc += (xx[1] & M) - t1;
@@ -108,7 +110,7 @@ public class SecP224R1Field
         cc += (xx[2] & M) - t2;
         z[2] = (int)cc;
         cc >>= 32;
-        cc += (xx[3] & M) + t0 - xx10;
+        cc += (xx[3] & M) + t0 - xx10 - n;
         z[3] = (int)cc;
         cc >>= 32;
         cc += (xx[4] & M) + t1 - xx11;
@@ -120,21 +122,41 @@ public class SecP224R1Field
         cc += (xx[6] & M) + xx10 - xx13;
         z[6] = (int)cc;
         cc >>= 32;
+        cc += n;
 
-        int c = (int)cc;
-        if (c >= 0)
-        {
-            reduce32(c, z);
-        }
-        else
-        {
-            subPInvFrom(z);
-        }
+//        assert cc >= 0;
+
+        reduce32((int)cc, z);
     }
 
     public static void reduce32(int x, int[] z)
     {
-        if ((x != 0 && (Nat.subWordFrom(7, x, z) + Nat.addWordAt(7, x, z, 3) != 0))
+        long cc = 0;
+
+        if (x != 0)
+        {
+            long xx07 = x & M;
+    
+            cc += (z[0] & M) - xx07;
+            z[0] = (int)cc;
+            cc >>= 32;
+            if (cc != 0)
+            {
+                cc += (z[1] & M);
+                z[1] = (int)cc;
+                cc >>= 32;
+                cc += (z[2] & M);
+                z[2] = (int)cc;
+                cc >>= 32;
+            }
+            cc += (z[3] & M) + xx07;
+            z[3] = (int)cc;
+            cc >>= 32;
+
+//            assert cc == 0 || cc == 1;
+        }
+
+        if ((cc != 0 && Nat.incAt(7, z, 4) != 0)
             || (z[6] == P6 && Nat224.gte(z, P)))
         {
             addPInvTo(z);
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java
index 46e9d8e2..52d1bfcc 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java
@@ -14,8 +14,6 @@ public class SecP256R1Field
     static final int[] PExt = new int[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
         0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE,
         0x00000002, 0xFFFFFFFE };
-    private static final int[] _2P = new int[]{ 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000000,
-        0x00000002, 0xFFFFFFFE, 0x00000001 };
     private static final int P7 = 0xFFFFFFFF;
     private static final int PExt15 = 0xFFFFFFFF;
 
@@ -101,8 +99,10 @@ public class SecP256R1Field
         long t5 = xx13 + xx14;
         long t6 = xx14 + xx15;
 
+        final long n = 6;
+
         long cc = 0;
-        cc += (xx[0] & M) + t0 - t3 - t5;
+        cc += (xx[0] & M) + t0 - t3 - t5 - n;
         z[0] = (int)cc;
         cc >>= 32;
         cc += (xx[1] & M) + t1 - t4 - t6;
@@ -111,7 +111,7 @@ public class SecP256R1Field
         cc += (xx[2] & M) + t2 - t5 - xx15;
         z[2] = (int)cc;
         cc >>= 32;
-        cc += (xx[3] & M) + (t3 << 1) + xx13 - xx15 - t0;
+        cc += (xx[3] & M) + (t3 << 1) + xx13 - xx15 - t0 + n;
         z[3] = (int)cc;
         cc >>= 32;
         cc += (xx[4] & M) + (t4 << 1) + xx14 - t1;
@@ -120,29 +120,16 @@ public class SecP256R1Field
         cc += (xx[5] & M) + (t5 << 1) + xx15 - t2;
         z[5] = (int)cc;
         cc >>= 32;
-        cc += (xx[6] & M) + (t6 << 1) + t5 - t0;
+        cc += (xx[6] & M) + (t6 << 1) + t5 - t0 + n;
         z[6] = (int)cc;
         cc >>= 32;
-        cc += (xx[7] & M) + (xx15 << 1) + xx15 + xx08 - t2 - t4;
+        cc += (xx[7] & M) + (xx15 << 1) + xx15 + xx08 - t2 - t4 - n;
         z[7] = (int)cc;
         cc >>= 32;
+        cc += n;
 
-        int c = (int)cc;
-        if (c >= 0)
-        {
-            reduce32(c, z);
-        }
-        else
-        {
-            while (c < -1)
-            {
-                c += Nat256.addTo(_2P, z) + 1;
-            }
-            while (c < 0)
-            {
-                c += Nat256.addTo(P, z);
-            }
-        }
+//        assert cc >= 0;
+        reduce32((int)cc, z);
     }
 
     public static void reduce32(int x, int[] z)
@@ -156,21 +143,27 @@ public class SecP256R1Field
             cc += (z[0] & M) + xx08;
             z[0] = (int)cc;
             cc >>= 32;
-            cc += (z[1] & M);
-            z[1] = (int)cc;
-            cc >>= 32;
-            cc += (z[2] & M);
-            z[2] = (int)cc;
-            cc >>= 32;
+            if (cc != 0)
+            {
+                cc += (z[1] & M);
+                z[1] = (int)cc;
+                cc >>= 32;
+                cc += (z[2] & M);
+                z[2] = (int)cc;
+                cc >>= 32;
+            }
             cc += (z[3] & M) - xx08;
             z[3] = (int)cc;
             cc >>= 32;
-            cc += (z[4] & M);
-            z[4] = (int)cc;
-            cc >>= 32;
-            cc += (z[5] & M);
-            z[5] = (int)cc;
-            cc >>= 32;
+            if (cc != 0)
+            {
+                cc += (z[4] & M);
+                z[4] = (int)cc;
+                cc >>= 32;
+                cc += (z[5] & M);
+                z[5] = (int)cc;
+                cc >>= 32;
+            }
             cc += (z[6] & M) - xx08;
             z[6] = (int)cc;
             cc >>= 32;
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Field.java
index 0a5e97f0..b9681946 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Field.java
@@ -98,20 +98,22 @@ public class SecP384R1Field
         long xx16 = xx[16] & M, xx17 = xx[17] & M, xx18 = xx[18] & M, xx19 = xx[19] & M;
         long xx20 = xx[20] & M, xx21 = xx[21] & M, xx22 = xx[22] & M, xx23 = xx[23] & M;
 
+        final long n = 1;
+
         long cc = 0;
-        cc += (xx[0] & M) + xx12 + xx20 + xx21 - xx23;
+        cc += (xx[0] & M) + xx12 + xx20 + xx21 - xx23 - n;
         z[0] = (int)cc;
         cc >>= 32;
-        cc += (xx[1] & M) + xx13 + xx22 + xx23 - xx12 - xx20;
+        cc += (xx[1] & M) + xx13 + xx22 + xx23 - xx12 - xx20 + n;
         z[1] = (int)cc;
         cc >>= 32;
         cc += (xx[2] & M) + xx14 + xx23 - xx13 - xx21;
         z[2] = (int)cc;
         cc >>= 32;
-        cc += (xx[3] & M) + xx12 + xx15 + xx20 + xx21 - xx14 - xx22 - xx23;
+        cc += (xx[3] & M) + xx12 + xx15 + xx20 + xx21 - xx14 - xx22 - xx23 - n;
         z[3] = (int)cc;
         cc >>= 32;
-        cc += (xx[4] & M) + xx12 + xx13 + xx16 + xx20 + ((xx21 - xx23) << 1) + xx22 - xx15;
+        cc += (xx[4] & M) + xx12 + xx13 + xx16 + xx20 + ((xx21 - xx23) << 1) + xx22 - xx15 - n;
         z[4] = (int)cc;
         cc >>= 32;
         cc += (xx[5] & M) + xx13 + xx14 + xx17 + xx21 + (xx22 << 1) + xx23 - xx16;
@@ -135,16 +137,11 @@ public class SecP384R1Field
         cc += (xx[11] & M) + xx19 + xx20 + xx23 - xx22;
         z[11] = (int)cc;
         cc >>= 32;
+        cc += n;
 
-        int c = (int)cc;
-        if (c >= 0)
-        {
-            reduce32(c, z);
-        }
-        else
-        {
-            subPInvFrom(z);
-        }
+//        assert cc >= 0;
+
+        reduce32((int)cc, z);
     }
 
     public static void reduce32(int x, int[] z)
@@ -161,9 +158,12 @@ public class SecP384R1Field
             cc += (z[1] & M) - xx12;
             z[1] = (int)cc;
             cc >>= 32;
-            cc += (z[2] & M);
-            z[2] = (int)cc;
-            cc >>= 32;
+            if (cc != 0)
+            {
+                cc += (z[2] & M);
+                z[2] = (int)cc;
+                cc >>= 32;
+            }
             cc += (z[3] & M) + xx12;
             z[3] = (int)cc;
             cc >>= 32;