From 4de18964f35fc169cb94058dcfe2e1ccb59b2524 Mon Sep 17 00:00:00 2001
From: Peter Dettman <peter.dettman@bouncycastle.org>
Date: Wed, 1 Mar 2023 17:20:21 +0700
Subject: Add Integers.PopCount

---
 crypto/src/math/BigInteger.cs                   | 17 +-----------
 crypto/src/pqc/crypto/picnic/PicnicUtilities.cs | 35 +++----------------------
 crypto/src/util/Integers.cs                     | 21 +++++++++++++++
 crypto/test/src/util/utiltest/IntegersTest.cs   | 33 +++++++++++++++++++++++
 4 files changed, 58 insertions(+), 48 deletions(-)

diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index 5b2ea0d87..d84680de5 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -942,7 +942,7 @@ namespace Org.BouncyCastle.Math
                         int sum = 0;
                         for (int i = 0; i < magnitude.Length; ++i)
                         {
-                            sum += BitCnt(magnitude[i]);
+                            sum += Integers.PopCount(magnitude[i]);
                         }
                         nBits = sum;
                     }
@@ -952,21 +952,6 @@ namespace Org.BouncyCastle.Math
             }
         }
 
-        internal static int BitCnt(uint u)
-        {
-#if NETCOREAPP3_0_OR_GREATER
-            return BitOperations.PopCount(u);
-#else
-            u = u - ((u >> 1) & 0x55555555);
-            u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
-            u = (u + (u >> 4)) & 0x0f0f0f0f;
-            u += (u >> 8);
-            u += (u >> 16);
-            u &= 0x3f;
-            return (int)u;
-#endif
-        }
-
         private static int CalcBitLength(int sign, int indx, uint[]	mag)
         {
             for (;;)
diff --git a/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs b/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs
index a2f1ca080..d77d7ce29 100644
--- a/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs
+++ b/crypto/src/pqc/crypto/picnic/PicnicUtilities.cs
@@ -34,48 +34,19 @@ namespace Org.BouncyCastle.Pqc.Crypto.Picnic
                 x ^= data[i];
             }
 
-            return (int)Parity16(x);
+            return Integers.PopCount(x) & 1;
         }
 
         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);
-            y ^= (y >> 4);
-            y ^= (y >> 8);
-            return y & 1;
+            return (uint)(Integers.PopCount(x & 0xFFFF) & 1);
         }
 
         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
-             */
-            uint y = (x ^ (x >> 1));
-            y ^= (y >> 2);
-            y ^= (y >> 4);
-            y ^= (y >> 8);
-            y ^= (y >> 16);
-            return (y & 1);
+            return (uint)(Integers.PopCount(x) & 1);
         }
 
-
         /* Set a specific bit in a byte array to a given value */
         internal static void SetBitInWordArray(uint[] array, int bitNumber, uint val)
         {
diff --git a/crypto/src/util/Integers.cs b/crypto/src/util/Integers.cs
index eff7056b6..87ba9cbb0 100644
--- a/crypto/src/util/Integers.cs
+++ b/crypto/src/util/Integers.cs
@@ -79,6 +79,27 @@ namespace Org.BouncyCastle.Utilities
 #endif
         }
 
+        public static int PopCount(int i)
+        {
+            return PopCount((uint)i);
+        }
+
+        [CLSCompliant(false)]
+        public static int PopCount(uint u)
+        {
+#if NETCOREAPP3_0_OR_GREATER
+            return BitOperations.PopCount(u);
+#else
+            u -= (u >> 1) & 0x55555555;
+            u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
+            u = (u + (u >> 4)) & 0x0f0f0f0f;
+            u += (u >> 8);
+            u += (u >> 16);
+            u &= 0x3f;
+            return (int)u;
+#endif
+        }
+
         public static int Reverse(int i)
         {
             return (int)Reverse((uint)i);
diff --git a/crypto/test/src/util/utiltest/IntegersTest.cs b/crypto/test/src/util/utiltest/IntegersTest.cs
index a661144db..91c0bf2b6 100644
--- a/crypto/test/src/util/utiltest/IntegersTest.cs
+++ b/crypto/test/src/util/utiltest/IntegersTest.cs
@@ -32,5 +32,38 @@ namespace Org.BouncyCastle.Utilities.UtilTests
             Assert.AreEqual(31, Integers.NumberOfTrailingZeros(int.MinValue));
             Assert.AreEqual(32, Integers.NumberOfTrailingZeros(0));
         }
+
+        [Test]
+        public void TestPopCount()
+        {
+            Random random = new Random();
+
+            for (int pos = 0; pos <= 24; ++pos)
+            {
+                int seed = Integers.RotateLeft(random.Next(0xFFFFFF) << 8, pos);
+                ImplTestPopCountRange(seed, pos, 0xFF);
+            }
+        }
+
+        private static void ImplTestPopCountRange(int seed, int pos, int count)
+        {
+            for (int i = 0; i < count; ++i)
+            {
+                int n = seed + (i << pos);
+                int expected = SimpleBitCount(n);
+                Assert.AreEqual(expected, Integers.PopCount(n));
+                Assert.AreEqual(expected, Integers.PopCount((uint)n));
+            }
+        }
+
+        private static int SimpleBitCount(int n)
+        {
+            int count = 0;
+            for (int i = 0; i < 32; ++i)
+            {
+                count += (n >> i) & 1;
+            }
+            return count;
+        }
     }
 }
-- 
cgit 1.4.1