Picnic perf. opts.

3 files changed, 86 insertions, 72 deletions

diff --git a/crypto/src/pqc/crypto/picnic/PicnicEngine.cs b/crypto/src/pqc/crypto/picnic/PicnicEngine.cs
index e813d8977..1fb04f3a2 100644
--- a/crypto/src/pqc/crypto/picnic/PicnicEngine.cs
+++ b/crypto/src/pqc/crypto/picnic/PicnicEngine.cs
@@ -3,6 +3,7 @@ using System;
 using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Crypto.Digests;
 using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Math.Raw;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
@@ -2175,8 +2176,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
         {
             for (int i = 0; i < numMPCParties; i++)
             {
-                 uint w_i = PicnicUtilities.GetBit(Pack.UInt32_To_LE(w), i);
-                PicnicUtilities.SetBit(msg.msgs[i], msg.pos, (byte) (w_i & 0xff));
+                uint w_i = PicnicUtilities.GetBit(w, i);
+                PicnicUtilities.SetBit(msg.msgs[i], msg.pos, (byte)w_i);
             }
 
             msg.pos++;
@@ -2187,13 +2188,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
             uint and_helper = tape.TapesToWord(); // The special mask value setup during preprocessing for each AND gate
             uint s_shares = (Extend(a) & mask_b) ^ (Extend(b) & mask_a) ^ and_helper;
 
-            byte[] temp = Pack.UInt32_To_LE(s_shares);
-
             if (msg.unopened >= 0)
             {
-                 uint unopenedPartyBit = PicnicUtilities.GetBit(msg.msgs[msg.unopened], msg.pos);
-                PicnicUtilities.SetBit(temp, msg.unopened, (byte) (unopenedPartyBit & 0xff));
-                s_shares = Pack.LE_To_UInt32(temp, 0);
+                uint unopenedPartyBit = PicnicUtilities.GetBit(msg.msgs[msg.unopened], msg.pos);
+                s_shares = PicnicUtilities.SetBit(s_shares, msg.unopened, unopenedPartyBit);
             }
 
             // Broadcast each share of s
@@ -2489,6 +2487,13 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
             uint[] temp = new uint[LOWMC_MAX_WORDS];
             temp[stateSizeWords - 1] = 0;
             int wholeWords = stateSizeBits / WORD_SIZE_BITS;
+            int unusedStateBits = stateSizeWords * WORD_SIZE_BITS - stateSizeBits;
+
+            // The final word mask, with bits reversed within each byte
+            uint partialWordMask = uint.MaxValue >> unusedStateBits;
+            partialWordMask = Bits.BitPermuteStepSimple(partialWordMask, 0x55555555U, 1);
+            partialWordMask = Bits.BitPermuteStepSimple(partialWordMask, 0x33333333U, 2);
+            partialWordMask = Bits.BitPermuteStepSimple(partialWordMask, 0x0F0F0F0FU, 4);
 
             for (int i = 0; i < stateSizeBits; i++)
             {
@@ -2496,15 +2501,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
                 for (int j = 0; j < wholeWords; j++)
                 {
                     int index = i * stateSizeWords + j;
-                    prod ^= state[j + stateOffset] & matrix[matrixOffset + index];
+                    prod ^= state[j + stateOffset] &
+                            matrix[matrixOffset + index];
                 }
-
-                for (int j = wholeWords * WORD_SIZE_BITS; j < stateSizeBits; j++)
+                if (unusedStateBits > 0)
                 {
-                    int index = i * stateSizeWords * WORD_SIZE_BITS + j;
-                    uint bit = PicnicUtilities.GetBitFromWordArray(state, stateOffset * 32 + j)
-                             & PicnicUtilities.GetBitFromWordArray(matrix, matrixOffset * 32 + index);
-                    prod ^= bit;
+                    int index = i * stateSizeWords + wholeWords;
+                    prod ^= state[stateOffset + wholeWords] &
+                            matrix[matrixOffset + index] &
+                            partialWordMask;
                 }
 
                 PicnicUtilities.SetBit(temp, i, PicnicUtilities.Parity32(prod));
diff --git a/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs b/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs
index c3be46840..a2f1ca080 100644
--- a/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs
+++ b/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs
@@ -1,3 +1,9 @@
+#if NETCOREAPP3_0_OR_GREATER
+using System.Runtime.Intrinsics.X86;
+#endif
+
+using Org.BouncyCastle.Utilities;
+
 namespace Org.BouncyCastle.Pqc.Crypto.Picnic
 {
     internal static class PicnicUtilities
@@ -16,47 +22,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
 
         internal static uint ceil_log2(uint x)
         {
-            if (x == 0)
-            {
-                return 0;
-            }
-
-            return 32 - nlz(x - 1);
-        }
-
-        private static uint nlz(uint x)
-        {
-            uint n;
-
-            if (x == 0) return (32);
-            n = 1;
-            if ((x >> 16) == 0)
-            {
-                n = n + 16;
-                x = x << 16;
-            }
-
-            if ((x >> 24) == 0)
-            {
-                n = n + 8;
-                x = x << 8;
-            }
-
-            if ((x >> 28) == 0)
-            {
-                n = n + 4;
-                x = x << 4;
-            }
-
-            if ((x >> 30) == 0)
-            {
-                n = n + 2;
-                x = x << 2;
-            }
-
-            n = (n - (x >> 31));
-
-            return n;
+            return x == 0 ? 0 : 32 - (uint)Integers.NumberOfLeadingZeros((int)(x - 1));
         }
 
         internal static int Parity(byte[] data, int len)
@@ -68,20 +34,18 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
                 x ^= data[i];
             }
 
-            /* Compute parity of x using code from Section 5-2 of
-             * H.S. Warren, *Hacker's Delight*, Pearson Education, 2003.
-             * http://www.hackersdelight.org/hdcodetxt/parity.c.txt
-             */
-            int y = x ^ (x >> 1);
-            y ^= (y >> 2);
-            y ^= (y >> 4);
-            y ^= (y >> 8);
-            y ^= (y >> 16);
-            return y & 1;
+            return (int)Parity16(x);
         }
 
         internal static uint Parity16(uint x)
         {
+#if NETCOREAPP3_0_OR_GREATER
+            if (Popcnt.IsSupported)
+            {
+                return Popcnt.PopCount(x & 0xFFFF) & 1U;
+            }
+#endif
+
             uint y = x ^ (x >> 1);
 
             y ^= (y >> 2);
@@ -92,6 +56,13 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
 
         internal static uint Parity32(uint x)
         {
+#if NETCOREAPP3_0_OR_GREATER
+            if (Popcnt.IsSupported)
+            {
+                return Popcnt.PopCount(x) & 1U;
+            }
+#endif
+
             /* Compute parity of x using code from Section 5-2 of
              * H.S. Warren, *Hacker's Delight*, Pearson Education, 2003.
              * http://www.hackersdelight.org/hdcodetxt/parity.c.txt
@@ -124,6 +95,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
             return (byte)((array[arrayPos] >> bitPos) & 1);
         }
 
+        internal static uint GetBit(uint word, int bitNumber)
+        {
+            int bitPos = bitNumber ^ 7;
+            return (word >> bitPos) & 1U;
+        }
+
         /* Get one bit from a byte array */
         internal static uint GetBit(uint[] array, int bitNumber)
         {
@@ -140,6 +117,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
             array[arrayPos] = (byte)t;
         }
 
+        internal static uint SetBit(uint word, int bitNumber, uint bit)
+        {
+            int bitPos = bitNumber ^ 7;
+            word &= ~(1U << bitPos);
+            word |= bit << bitPos;
+            return word;
+        }
+
         /* Set a specific bit in a int array to a given value */
         internal static void SetBit(uint[] array, int bitNumber, uint val)
         {
diff --git a/crypto/src/pqc/crypto/picnic/Tape.cs b/crypto/src/pqc/crypto/picnic/Tape.cs
index 9f72bc4dd..700207dea 100644
--- a/crypto/src/pqc/crypto/picnic/Tape.cs
+++ b/crypto/src/pqc/crypto/picnic/Tape.cs
@@ -114,15 +114,39 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
 
         internal uint TapesToWord()
         {
-            byte[] shares = new byte[4];
+            //byte[] shares = new byte[4];
+            //for (int i = 0; i < 16; i++)
+            //{
+            //    byte bit = PicnicUtilities.GetBit(this.tapes[i], this.pos);
+            //    PicnicUtilities.SetBit(shares, i, bit);
+            //}
+            //this.pos++;
+            //return Pack.LE_To_UInt32(shares, 0);
+
+            uint shares = 0U;
+            int arrayPos = pos >> 3, bitPos = (pos & 7) ^ 7;
+            uint bitMask = 1U << bitPos;
+
+            shares |= (tapes[ 0][arrayPos] & bitMask) <<  7;
+            shares |= (tapes[ 1][arrayPos] & bitMask) <<  6;
+            shares |= (tapes[ 2][arrayPos] & bitMask) <<  5;
+            shares |= (tapes[ 3][arrayPos] & bitMask) <<  4;
+            shares |= (tapes[ 4][arrayPos] & bitMask) <<  3;
+            shares |= (tapes[ 5][arrayPos] & bitMask) <<  2;
+            shares |= (tapes[ 6][arrayPos] & bitMask) <<  1;
+            shares |= (tapes[ 7][arrayPos] & bitMask) <<  0;
+
+            shares |= (tapes[ 8][arrayPos] & bitMask) << 15;
+            shares |= (tapes[ 9][arrayPos] & bitMask) << 14;
+            shares |= (tapes[10][arrayPos] & bitMask) << 13;
+            shares |= (tapes[11][arrayPos] & bitMask) << 12;
+            shares |= (tapes[12][arrayPos] & bitMask) << 11;
+            shares |= (tapes[13][arrayPos] & bitMask) << 10;
+            shares |= (tapes[14][arrayPos] & bitMask) <<  9;
+            shares |= (tapes[15][arrayPos] & bitMask) <<  8;
 
-            for (int i = 0; i < 16; i++)
-            {
-                byte bit = PicnicUtilities.GetBit(this.tapes[i], this.pos);
-                PicnicUtilities.SetBit(shares, i, bit);
-            }
             this.pos++;
-            return Pack.LE_To_UInt32(shares, 0);
+            return shares >> bitPos;
         }
     }
 }