Add method to support adding an IntArray left-shifted by some number of

bits

2 files changed, 53 insertions, 20 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
index 4c8882cb..d584efac 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
@@ -1178,7 +1178,7 @@ public abstract class ECFieldElement
             // checkFieldElements(this, b);
             IntArray iarrClone = (IntArray)this.x.clone();
             F2m bF2m = (F2m)b;
-            iarrClone.addShifted(bF2m.x, 0);
+            iarrClone.addShiftedByWords(bF2m.x, 0);
             return new F2m(m, ks, iarrClone);
         }
 
@@ -1283,18 +1283,11 @@ public abstract class ECFieldElement
                 // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
                 // = deg(u(z))
                 // uz = uz.xor(vz.shiftLeft(j));
-                // jInt = n / 32
-                int jInt = j >> 5;
-                // jInt = n % 32
-                int jBit = j & 0x1F;
-                IntArray vzShift = vz.shiftLeft(jBit);
-                uz.addShifted(vzShift, jInt);
+                uz.addShiftedByBits(vz, j);
 
                 // g1(z) := g1(z) + z^j * g2(z)
 //                g1z = g1z.xor(g2z.shiftLeft(j));
-                IntArray g2zShift = g2z.shiftLeft(jBit);
-                g1z.addShifted(g2zShift, jInt);
-                
+                g1z.addShiftedByBits(g2z, j);
             }
             return new ECFieldElement.F2m(this.m, this.ks, g2z);
         }
diff --git a/core/src/main/java/org/bouncycastle/math/ec/IntArray.java b/core/src/main/java/org/bouncycastle/math/ec/IntArray.java
index ebb6310a..670c8c26 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/IntArray.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/IntArray.java
@@ -281,7 +281,7 @@ class IntArray
         if (n > 31)
         {
             throw new IllegalArgumentException("shiftLeft() for max 31 bits "
-                + ", " + n + "bit shift is not possible");
+                + ", " + n + " bit shift is not possible");
         }
 
         int[] newInts = new int[usedLen + 1];
@@ -309,19 +309,59 @@ class IntArray
         m_ints[shift] ^= 1;
     }
 
-    public void addShifted(IntArray other, int shift)
+    public void addShiftedByBits(IntArray other, int bits)
     {
-        int usedLenOther = other.getUsedLength();
-        int newMinUsedLen = usedLenOther + shift;
-        if (newMinUsedLen > m_ints.length)
+        int words = bits >> 5;
+        int shift = bits & 0x1F;
+
+//        IntArray vzShift = other.shiftLeft(shift);
+//        addShiftedByWords(vzShift, words);
+
+        if (shift == 0)
         {
-            m_ints = resizedInts(newMinUsedLen);
-            //System.out.println("Resize required");
+            addShiftedByWords(other, words);
+            return;
+        }
+
+        int otherUsedLen = other.getUsedLength();
+        if (otherUsedLen == 0)
+        {
+            return;
+        }
+
+        int minLen = otherUsedLen + words + 1;
+        if (minLen > m_ints.length)
+        {
+            m_ints = resizedInts(minLen);
+        }
+
+        int shiftInv = 32 - shift, prev = 0;
+        for (int i = 0; i < otherUsedLen; ++i)
+        {
+            int next = other.m_ints[i];
+            m_ints[i + words] ^= (next << shift) | (prev >>> shiftInv);
+            prev = next;
+        }
+        m_ints[otherUsedLen + words] ^= prev >>> shiftInv;
+    }
+
+    public void addShiftedByWords(IntArray other, int words)
+    {
+        int otherUsedLen = other.getUsedLength();
+        if (otherUsedLen == 0)
+        {
+            return;
+        }
+
+        int minLen = otherUsedLen + words;
+        if (minLen > m_ints.length)
+        {
+            m_ints = resizedInts(minLen);
         }
 
-        for (int i = 0; i < usedLenOther; i++)
+        for (int i = 0; i < otherUsedLen; i++)
         {
-            m_ints[i + shift] ^= other.m_ints[i];
+            m_ints[words + i] ^= other.m_ints[i];
         }
     }
 
@@ -436,7 +476,7 @@ class IntArray
                 if ((m_ints[j] & testBit) != 0)
                 {
                     // The kth bit of m_ints[j] is set
-                    c.addShifted(b, j);
+                    c.addShiftedByWords(b, j);
                 }
             }
             if ((testBit <<= 1) == 0)