NTZ for 0 should be 32/64 resp.

- add tests for NLZ, NTZ
- round out methods for Longs class

6 files changed, 113 insertions, 4 deletions

diff --git a/crypto/crypto.csproj b/crypto/crypto.csproj
index a4b45afc3..374482709 100644
--- a/crypto/crypto.csproj
+++ b/crypto/crypto.csproj
@@ -13867,6 +13867,16 @@
                     BuildAction = "Compile"
                 />
                 <File
+                    RelPath = "test\src\util\utiltest\IntegersTest.cs"
+                    SubType = "Code"
+                    BuildAction = "Compile"
+                />
+                <File
+                    RelPath = "test\src\util\utiltest\LongsTest.cs"
+                    SubType = "Code"
+                    BuildAction = "Compile"
+                />
+                <File
                     RelPath = "test\src\x509\test\TestCertificateGen.cs"
                     SubType = "Code"
                     BuildAction = "Compile"
diff --git a/crypto/src/util/Integers.cs b/crypto/src/util/Integers.cs
index 11045d9e3..cc46862bd 100644
--- a/crypto/src/util/Integers.cs
+++ b/crypto/src/util/Integers.cs
@@ -10,9 +10,8 @@ namespace Org.BouncyCastle.Utilities
         public const int NumBytes = 4;
 
         private static readonly byte[] DeBruijnTZ = {
-            0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
-            0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
-            0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B };
+            0x1F, 0x00, 0x1B, 0x01, 0x1C, 0x0D, 0x17, 0x02, 0x1D, 0x15, 0x13, 0x0E, 0x18, 0x10, 0x03, 0x07,
+            0x1E, 0x1A, 0x0C, 0x16, 0x14, 0x12, 0x0F, 0x06, 0x19, 0x0B, 0x11, 0x05, 0x0A, 0x04, 0x09, 0x08 };
 
         public static int NumberOfLeadingZeros(int i)
         {
@@ -31,7 +30,9 @@ namespace Org.BouncyCastle.Utilities
 
         public static int NumberOfTrailingZeros(int i)
         {
-            return DeBruijnTZ[(uint)((i & -i) * 0x04D7651F) >> 27];
+            int n = DeBruijnTZ[(uint)((i & -i) * 0x0EF96A62) >> 27];
+            int m = (((i & 0xFFFF) | (int)((uint)i >> 16)) - 1) >> 31;
+            return n - m;
         }
 
         public static int Reverse(int i)
diff --git a/crypto/src/util/Longs.cs b/crypto/src/util/Longs.cs
index 91dee2b50..66b14b95c 100644
--- a/crypto/src/util/Longs.cs
+++ b/crypto/src/util/Longs.cs
@@ -9,6 +9,30 @@ namespace Org.BouncyCastle.Utilities
         public const int NumBits = 64;
         public const int NumBytes = 8;
 
+        private static readonly byte[] DeBruijnTZ = {
+            0x3F, 0x00, 0x01, 0x34, 0x02, 0x06, 0x35, 0x1A, 0x03, 0x25, 0x28, 0x07, 0x21, 0x36, 0x2F, 0x1B,
+            0x3D, 0x04, 0x26, 0x2D, 0x2B, 0x29, 0x15, 0x08, 0x17, 0x22, 0x3A, 0x37, 0x30, 0x11, 0x1C, 0x0A,
+            0x3E, 0x33, 0x05, 0x19, 0x24, 0x27, 0x20, 0x2E, 0x3C, 0x2C, 0x2A, 0x14, 0x16, 0x39, 0x10, 0x09,
+            0x32, 0x18, 0x23, 0x1F, 0x3B, 0x13, 0x38, 0x0F, 0x31, 0x1E, 0x12, 0x0E, 0x1D, 0x0D, 0x0C, 0x0B };
+
+        public static int NumberOfLeadingZeros(long i)
+        {
+            int x = (int)(i >> 32), n = 0;
+            if (x == 0)
+            {
+                n = 32;
+                x = (int)i;
+            }
+            return n + Integers.NumberOfLeadingZeros(x);
+        }
+
+        public static int NumberOfTrailingZeros(long i)
+        {
+            int n = DeBruijnTZ[(uint)((ulong)((i & -i) * 0x045FBAC7992A70DAL) >> 58)];
+            long m = (((i & 0xFFFFFFFFL) | (long)((ulong)i >> 32)) - 1L) >> 63;
+            return n - (int)m;
+        }
+
         public static long Reverse(long i)
         {
             i = (long)Bits.BitPermuteStepSimple((ulong)i, 0x5555555555555555UL, 1);
diff --git a/crypto/test/UnitTests.csproj b/crypto/test/UnitTests.csproj
index 2164d2949..58737f9ce 100644
--- a/crypto/test/UnitTests.csproj
+++ b/crypto/test/UnitTests.csproj
@@ -486,6 +486,8 @@
     <Compile Include="src\util\test\TestRandomBigInteger.cs" />
     <Compile Include="src\util\test\TestRandomData.cs" />
     <Compile Include="src\util\test\UncloseableStream.cs" />
+    <Compile Include="src\util\utiltest\IntegersTest.cs" />
+    <Compile Include="src\util\utiltest\LongsTest.cs" />
     <Compile Include="src\x509\test\TestCertificateGen.cs" />
   </ItemGroup>
   <ItemGroup>
diff --git a/crypto/test/src/util/utiltest/IntegersTest.cs b/crypto/test/src/util/utiltest/IntegersTest.cs
new file mode 100644
index 000000000..a661144db
--- /dev/null
+++ b/crypto/test/src/util/utiltest/IntegersTest.cs
@@ -0,0 +1,36 @@
+using System;
+
+using NUnit.Framework;
+
+namespace Org.BouncyCastle.Utilities.UtilTests
+{
+    [TestFixture]
+    public class IntegersTest
+    {
+        [Test]
+        public void TestNumberOfLeadingZeros()
+        {
+            for (int i = 0; i < 31; ++i)
+            {
+                Assert.AreEqual(i, Integers.NumberOfLeadingZeros((int)(0x80000000U >> i)));
+                Assert.AreEqual(i, Integers.NumberOfLeadingZeros((int)(0xFFFFFFFFU >> i)));
+            }
+
+            Assert.AreEqual(31, Integers.NumberOfLeadingZeros(1));
+            Assert.AreEqual(32, Integers.NumberOfLeadingZeros(0));
+        }
+
+        [Test]
+        public void TestNumberOfTrailingZeros()
+        {
+            for (int i = 0; i < 31; ++i)
+            {
+                Assert.AreEqual(i, Integers.NumberOfTrailingZeros(1 << i));
+                Assert.AreEqual(i, Integers.NumberOfTrailingZeros(-1 << i));
+            }
+
+            Assert.AreEqual(31, Integers.NumberOfTrailingZeros(int.MinValue));
+            Assert.AreEqual(32, Integers.NumberOfTrailingZeros(0));
+        }
+    }
+}
diff --git a/crypto/test/src/util/utiltest/LongsTest.cs b/crypto/test/src/util/utiltest/LongsTest.cs
new file mode 100644
index 000000000..b2ddb6656
--- /dev/null
+++ b/crypto/test/src/util/utiltest/LongsTest.cs
@@ -0,0 +1,36 @@
+using System;
+
+using NUnit.Framework;
+
+namespace Org.BouncyCastle.Utilities.UtilTests
+{
+    [TestFixture]
+    public class LongsTest
+    {
+        [Test]
+        public void TestNumberOfLeadingZeros()
+        {
+            for (int i = 0; i < 63; ++i)
+            {
+                Assert.AreEqual(i, Longs.NumberOfLeadingZeros((long)(0x8000000000000000UL >> i)));
+                Assert.AreEqual(i, Longs.NumberOfLeadingZeros((long)(0xFFFFFFFFFFFFFFFFUL >> i)));
+            }
+
+            Assert.AreEqual(63, Longs.NumberOfLeadingZeros(1L));
+            Assert.AreEqual(64, Longs.NumberOfLeadingZeros(0L));
+        }
+
+        [Test]
+        public void TestNumberOfTrailingZeros()
+        {
+            for (int i = 0; i < 63; ++i)
+            {
+                Assert.AreEqual(i, Longs.NumberOfTrailingZeros(1L << i));
+                Assert.AreEqual(i, Longs.NumberOfTrailingZeros(-1L << i));
+            }
+
+            Assert.AreEqual(63, Longs.NumberOfTrailingZeros(long.MinValue));
+            Assert.AreEqual(64, Longs.NumberOfTrailingZeros(0L));
+        }
+    }
+}