Keccak performance improvements

3 files changed, 106 insertions, 187 deletions

diff --git a/crypto/src/crypto/digests/KeccakDigest.cs b/crypto/src/crypto/digests/KeccakDigest.cs
index 37cc6dc41..8b16e5d3a 100644
--- a/crypto/src/crypto/digests/KeccakDigest.cs
+++ b/crypto/src/crypto/digests/KeccakDigest.cs
@@ -1,4 +1,5 @@
 using System;
+using System.Diagnostics;
 
 using Org.BouncyCastle.Crypto.Utilities;
 using Org.BouncyCastle.Utilities;
@@ -57,12 +58,11 @@ namespace Org.BouncyCastle.Crypto.Digests
             int x, y, t, newX, newY;
 
             int rhoOffset = 0;
-            keccakRhoOffsets[(((0) % 5) + 5 * ((0) % 5))] = rhoOffset;
+            keccakRhoOffsets[0] = rhoOffset;
             x = 1;
             y = 0;
             for (t = 1; t < 25; t++)
             {
-                //rhoOffset = ((t + 1) * (t + 2) / 2) % 64;
                 rhoOffset = (rhoOffset + t) & 63;
                 keccakRhoOffsets[(((x) % 5) + 5 * ((y) % 5))] = rhoOffset;
                 newX = (0 * x + 1 * y) % 5;
@@ -76,24 +76,13 @@ namespace Org.BouncyCastle.Crypto.Digests
 
         private static readonly int STATE_LENGTH = (1600 / 8);
 
-        private ulong[] longState = new ulong[STATE_LENGTH / 8];
-        protected byte[] state = new byte[STATE_LENGTH];
-        protected byte[] dataQueue = new byte[(1536 / 8)];
+        private ulong[] state = new ulong[STATE_LENGTH / 8];
+        protected byte[] dataQueue = new byte[1536 / 8];
         protected int rate;
         protected int bitsInQueue;
         protected int fixedOutputLength;
         protected bool squeezing;
         protected int bitsAvailableForSqueezing;
-        protected byte[] chunk;
-        protected byte[] oneByte;
-
-        private void ClearDataQueueSection(int off, int len)
-        {
-            for (int i = off; i != off + len; i++)
-            {
-                dataQueue[i] = 0;
-            }
-        }
 
         public KeccakDigest()
             : this(288)
@@ -119,8 +108,6 @@ namespace Org.BouncyCastle.Crypto.Digests
             this.fixedOutputLength = source.fixedOutputLength;
             this.squeezing = source.squeezing;
             this.bitsAvailableForSqueezing = source.bitsAvailableForSqueezing;
-            this.chunk = Arrays.Clone(source.chunk);
-            this.oneByte = Arrays.Clone(source.oneByte);
         }
 
         public virtual string AlgorithmName
@@ -130,24 +117,22 @@ namespace Org.BouncyCastle.Crypto.Digests
 
         public virtual int GetDigestSize()
         {
-            return fixedOutputLength / 8;
+            return fixedOutputLength >> 3;
         }
 
         public virtual void Update(byte input)
         {
-            oneByte[0] = input;
-
-            Absorb(oneByte, 0, 8L);
+            Absorb(new byte[]{ input }, 0, 1);
         }
 
         public virtual void BlockUpdate(byte[] input, int inOff, int len)
         {
-            Absorb(input, inOff, len * 8L);
+            Absorb(input, inOff, len);
         }
 
         public virtual int DoFinal(byte[] output, int outOff)
         {
-            Squeeze(output, outOff, fixedOutputLength);
+            Squeeze(output, outOff, fixedOutputLength >> 3);
 
             Reset();
 
@@ -161,11 +146,10 @@ namespace Org.BouncyCastle.Crypto.Digests
         {
             if (partialBits > 0)
             {
-                oneByte[0] = partialByte;
-                Absorb(oneByte, 0, partialBits);
+                AbsorbBits(partialByte, partialBits);
             }
 
-            Squeeze(output, outOff, fixedOutputLength);
+            Squeeze(output, outOff, fixedOutputLength >> 3);
 
             Reset();
 
@@ -184,7 +168,7 @@ namespace Org.BouncyCastle.Crypto.Digests
          */
         public virtual int GetByteLength()
         {
-            return rate / 8;
+            return rate >> 3;
         }
 
         private void Init(int bitLength)
@@ -192,220 +176,170 @@ namespace Org.BouncyCastle.Crypto.Digests
             switch (bitLength)
             {
                 case 128:
-                    InitSponge(1344, 256);
-                    break;
                 case 224:
-                    InitSponge(1152, 448);
-                    break;
                 case 256:
-                    InitSponge(1088, 512);
-                    break;
                 case 288:
-                    InitSponge(1024, 576);
-                    break;
                 case 384:
-                    InitSponge(832, 768);
-                    break;
                 case 512:
-                    InitSponge(576, 1024);
+                    InitSponge(1600 - (bitLength << 1));
                     break;
                 default:
                     throw new ArgumentException("must be one of 128, 224, 256, 288, 384, or 512.", "bitLength");
             }
         }
 
-        private void InitSponge(int rate, int capacity)
+        private void InitSponge(int rate)
         {
-            if (rate + capacity != 1600)
-            {
-                throw new InvalidOperationException("rate + capacity != 1600");
-            }
-            if ((rate <= 0) || (rate >= 1600) || ((rate % 64) != 0))
-            {
+            if (rate <= 0 || rate >= 1600 || (rate & 63) != 0)
                 throw new InvalidOperationException("invalid rate value");
-            }
 
             this.rate = rate;
-            // this is never read, need to check to see why we want to save it
-            //  this.capacity = capacity;
-            this.fixedOutputLength = 0;
-            Arrays.Fill(this.state, (byte)0);
+            Array.Clear(state, 0, state.Length);
             Arrays.Fill(this.dataQueue, (byte)0);
             this.bitsInQueue = 0;
             this.squeezing = false;
             this.bitsAvailableForSqueezing = 0;
-            this.fixedOutputLength = capacity / 2;
-            this.chunk = new byte[rate / 8];
-            this.oneByte = new byte[1];
-        }
-
-        private void AbsorbQueue()
-        {
-            KeccakAbsorb(state, dataQueue, rate / 8);
-
-            bitsInQueue = 0;
+            this.fixedOutputLength = (1600 - rate) >> 1;
         }
 
-        protected virtual void Absorb(byte[] data, int off, long databitlen)
+        protected void Absorb(byte[] data, int off, int len)
         {
-            long i, j, wholeBlocks;
-
-            if ((bitsInQueue % 8) != 0)
-            {
+            if ((bitsInQueue & 7) != 0)
                 throw new InvalidOperationException("attempt to absorb with odd length queue");
-            }
             if (squeezing)
-            {
                 throw new InvalidOperationException("attempt to absorb while squeezing");
-            }
 
-            i = 0;
-            while (i < databitlen)
+            int bytesInQueue = bitsInQueue >> 3;
+            int rateBytes = rate >> 3;
+
+            int count = 0;
+            while (count < len)
             {
-                if ((bitsInQueue == 0) && (databitlen >= rate) && (i <= (databitlen - rate)))
+                if (bytesInQueue == 0 && count <= (len - rateBytes))
                 {
-                    wholeBlocks = (databitlen - i) / rate;
-
-                    for (j = 0; j < wholeBlocks; j++)
+                    do
                     {
-                        Array.Copy(data, (int)(off + (i / 8) + (j * chunk.Length)), chunk, 0, chunk.Length);
-
-                        KeccakAbsorb(state, chunk, chunk.Length);
+                        KeccakAbsorb(data, off + count);
+                        count += rateBytes;
                     }
-
-                    i += wholeBlocks * rate;
+                    while (count <= (len - rateBytes));
                 }
                 else
                 {
-                    int partialBlock = (int)(databitlen - i);
-                    if (partialBlock + bitsInQueue > rate)
-                    {
-                        partialBlock = rate - bitsInQueue;
-                    }
-                    int partialByte = partialBlock % 8;
-                    partialBlock -= partialByte;
-                    Array.Copy(data, off + (int)(i / 8), dataQueue, bitsInQueue / 8, partialBlock / 8);
+                    int partialBlock = System.Math.Min(rateBytes - bytesInQueue, len - count);
+                    Array.Copy(data, off + count, dataQueue, bytesInQueue, partialBlock);
 
-                    bitsInQueue += partialBlock;
-                    i += partialBlock;
-                    if (bitsInQueue == rate)
-                    {
-                        AbsorbQueue();
-                    }
-                    if (partialByte > 0)
+                    bytesInQueue += partialBlock;
+                    count += partialBlock;
+
+                    if (bytesInQueue == rateBytes)
                     {
-                        int mask = (1 << partialByte) - 1;
-                        dataQueue[bitsInQueue / 8] = (byte)(data[off + ((int)(i / 8))] & mask);
-                        bitsInQueue += partialByte;
-                        i += partialByte;
+                        KeccakAbsorb(dataQueue, 0);
+                        bytesInQueue = 0;
                     }
                 }
             }
+
+            bitsInQueue = bytesInQueue << 3;
+        }
+
+        protected void AbsorbBits(int data, int bits)
+        {
+            if (bits < 1 || bits > 7)
+                throw new ArgumentException("must be in the range 1 to 7", "bits");
+            if ((bitsInQueue & 7) != 0)
+                throw new InvalidOperationException("attempt to absorb with odd length queue");
+            if (squeezing)
+                throw new InvalidOperationException("attempt to absorb while squeezing");
+
+            int mask = (1 << bits) - 1;
+            dataQueue[bitsInQueue >> 3] = (byte)(data & mask);
+
+            // NOTE: After this, bitsInQueue is no longer a multiple of 8, so no more absorbs will work
+            bitsInQueue += bits;
         }
 
         private void PadAndSwitchToSqueezingPhase()
         {
-            if (bitsInQueue + 1 == rate)
-            {
-                dataQueue[bitsInQueue / 8] |= (byte)(1U << (bitsInQueue % 8));
-                AbsorbQueue();
-                ClearDataQueueSection(0, rate / 8);
-            }
-            else
-            {
-                ClearDataQueueSection((bitsInQueue + 7) / 8, rate / 8 - (bitsInQueue + 7) / 8);
-                dataQueue[bitsInQueue / 8] |= (byte)(1U << (bitsInQueue % 8));
-            }
-            dataQueue[(rate - 1) / 8] |= (byte)(1U << ((rate - 1) % 8));
-            AbsorbQueue();
+            Debug.Assert(bitsInQueue < rate);
+
+            dataQueue[bitsInQueue >> 3] |= (byte)(1U << (bitsInQueue & 7));
 
-            if (rate == 1024)
+            if (++bitsInQueue == rate)
             {
-                KeccakExtract1024bits(state, dataQueue);
-                bitsAvailableForSqueezing = 1024;
+                KeccakAbsorb(dataQueue, 0);
+                bitsInQueue = 0;
             }
-            else
+
             {
-                KeccakExtract(state, dataQueue, rate / 64);
-                bitsAvailableForSqueezing = rate;
+                int full = bitsInQueue >> 6, partial = bitsInQueue & 63;
+                int off = 0;
+                for (int i = 0; i < full; ++i)
+                {
+                    state[i] ^= Pack.LE_To_UInt64(dataQueue, off);
+                    off += 8;
+                }
+                if (partial > 0)
+                {
+                    ulong mask = (1UL << partial) - 1UL;
+                    state[full] ^= Pack.LE_To_UInt64(dataQueue, off) & mask;
+                }
+                state[(rate - 1) >> 6] ^= (1UL << 63);
             }
 
+            KeccakPermutation();
+            KeccakExtract();
+            bitsAvailableForSqueezing = rate;
+
+            bitsInQueue = 0;
             squeezing = true;
         }
 
-        protected virtual void Squeeze(byte[] output, int offset, long outputLength)
+        protected void Squeeze(byte[] output, int off, int len)
         {
-            long i;
-            int partialBlock;
-
             if (!squeezing)
             {
                 PadAndSwitchToSqueezingPhase();
             }
-            if ((outputLength % 8) != 0)
-            {
-                throw new InvalidOperationException("outputLength not a multiple of 8");
-            }
 
-            i = 0;
+            long outputLength = (long)len << 3;
+            long i = 0;
             while (i < outputLength)
             {
                 if (bitsAvailableForSqueezing == 0)
                 {
-                    KeccakPermutation(state);
-
-                    if (rate == 1024)
-                    {
-                        KeccakExtract1024bits(state, dataQueue);
-                        bitsAvailableForSqueezing = 1024;
-                    }
-                    else
-                    {
-                        KeccakExtract(state, dataQueue, rate / 64);
-                        bitsAvailableForSqueezing = rate;
-                    }
-                }
-                partialBlock = bitsAvailableForSqueezing;
-                if ((long)partialBlock > outputLength - i)
-                {
-                    partialBlock = (int)(outputLength - i);
+                    KeccakPermutation();
+                    KeccakExtract();
+                    bitsAvailableForSqueezing = rate;
                 }
 
-                Array.Copy(dataQueue, (rate - bitsAvailableForSqueezing) / 8, output, offset + (int)(i / 8), partialBlock / 8);
+                int partialBlock = (int)System.Math.Min((long)bitsAvailableForSqueezing, outputLength - i);
+                Array.Copy(dataQueue, (rate - bitsAvailableForSqueezing) >> 3, output, off + (int)(i >> 3), partialBlock >> 3);
                 bitsAvailableForSqueezing -= partialBlock;
                 i += partialBlock;
             }
         }
 
-        private void KeccakPermutation(byte[] state)
-        {
-            Pack.LE_To_UInt64(state, 0, longState);
-
-            KeccakPermutationOnWords(longState);
-
-            Pack.UInt64_To_LE(longState, state, 0);
-        }
-
-        private void KeccakPermutationAfterXor(byte[] state, byte[] data, int dataLengthInBytes)
+        private void KeccakAbsorb(byte[] data, int off)
         {
-            for (int i = 0; i < dataLengthInBytes; i++)
+            int count = rate >> 6;
+            for (int i = 0; i < count; ++i)
             {
-                state[i] ^= data[i];
+                state[i] ^= Pack.LE_To_UInt64(data, off);
+                off += 8;
             }
 
-            KeccakPermutation(state);
+            KeccakPermutation();
         }
 
-        private void KeccakAbsorb(byte[] byteState, byte[] data, int dataInBytes)
+        private void KeccakExtract()
         {
-            KeccakPermutationAfterXor(byteState, data, dataInBytes);
+            Pack.UInt64_To_LE(state, 0, rate >> 6, dataQueue, 0);
         }
 
-        private static void KeccakPermutationOnWords(ulong[] state)
+        private void KeccakPermutation()
         {
-            int i;
-
-            for (i = 0; i < 24; i++)
+            for (int i = 0; i < 24; i++)
             {
                 Theta(state);
                 Rho(state);
@@ -417,7 +351,7 @@ namespace Org.BouncyCastle.Crypto.Digests
 
         private static ulong leftRotate(ulong v, int r)
         {
-            return (v << r) | (v >> (64 - r));
+            return (v << r) | (v >> -r);
         }
 
         private static void Theta(ulong[] A)
@@ -532,16 +466,6 @@ namespace Org.BouncyCastle.Crypto.Digests
             A[0] ^= KeccakRoundConstants[indexRound];
         }
 
-        private static void KeccakExtract1024bits(byte[] byteState, byte[] data)
-        {
-            Array.Copy(byteState, 0, data, 0, 128);
-        }
-
-        private static void KeccakExtract(byte[] byteState, byte[] data, int laneCount)
-        {
-            Array.Copy(byteState, 0, data, 0, laneCount * 8);
-        }
-
         public virtual IMemoable Copy()
         {
             return new KeccakDigest(this);
@@ -549,9 +473,7 @@ namespace Org.BouncyCastle.Crypto.Digests
 
         public virtual void Reset(IMemoable other)
         {
-            KeccakDigest d = (KeccakDigest)other;
-
-            CopyIn(d);
+            CopyIn((KeccakDigest)other);
         }
     }
 }
diff --git a/crypto/src/crypto/digests/SHA3Digest.cs b/crypto/src/crypto/digests/SHA3Digest.cs
index 890b665cf..4683af5b3 100644
--- a/crypto/src/crypto/digests/SHA3Digest.cs
+++ b/crypto/src/crypto/digests/SHA3Digest.cs
@@ -50,7 +50,7 @@ namespace Org.BouncyCastle.Crypto.Digests
 
         public override int DoFinal(byte[] output, int outOff)
         {
-            Absorb(new byte[]{ 0x02 }, 0, 2);
+            AbsorbBits(0x02, 2);
 
             return base.DoFinal(output,  outOff);
         }
@@ -69,8 +69,7 @@ namespace Org.BouncyCastle.Crypto.Digests
 
             if (finalBits >= 8)
             {
-                oneByte[0] = (byte)finalInput;
-                Absorb(oneByte, 0, 8);
+                Absorb(new byte[]{ (byte)finalInput }, 0, 1);
                 finalBits -= 8;
                 finalInput >>= 8;
             }
diff --git a/crypto/src/crypto/digests/ShakeDigest.cs b/crypto/src/crypto/digests/ShakeDigest.cs
index a7bddccba..13e8838c1 100644
--- a/crypto/src/crypto/digests/ShakeDigest.cs
+++ b/crypto/src/crypto/digests/ShakeDigest.cs
@@ -64,10 +64,10 @@ namespace Org.BouncyCastle.Crypto.Digests
         {
             if (!squeezing)
             {
-                Absorb(new byte[] { 0x0F }, 0, 4);
+                AbsorbBits(0x0F, 4);
             }
 
-            Squeeze(output, outOff, ((long)outLen) * 8);
+            Squeeze(output, outOff, outLen);
 
             return outLen;
         }
@@ -94,19 +94,17 @@ namespace Org.BouncyCastle.Crypto.Digests
 
             if (finalBits >= 8)
             {
-                oneByte[0] = (byte)finalInput;
-                Absorb(oneByte, 0, 8);
+                Absorb(new byte[]{ (byte)finalInput }, 0, 1);
                 finalBits -= 8;
                 finalInput >>= 8;
             }
 
             if (finalBits > 0)
             {
-                oneByte[0] = (byte)finalInput;
-                Absorb(oneByte, 0, finalBits);
+                AbsorbBits(finalInput, finalBits);
             }
 
-            Squeeze(output, outOff, ((long)outLen) * 8);
+            Squeeze(output, outOff, outLen);
 
             Reset();