feat: Add FNV1a software checksum and basic correction tests

2 files changed, 160 insertions, 0 deletions

diff --git a/lib/Hashing.Portable/src/Checksums/FNV1a.cs b/lib/Hashing.Portable/src/Checksums/FNV1a.cs
new file mode 100644
index 0000000..5bac86f
--- /dev/null
+++ b/lib/Hashing.Portable/src/Checksums/FNV1a.cs
@@ -0,0 +1,113 @@
+/*
+* Copyright (c) 2024 Vaughn Nugent
+* 
+* Library: VNLib
+* Package: VNLib.Hashing.Portable
+* File: FNV1a.cs 
+*
+* FNV1a.cs is part of VNLib.Hashing.Portable which is part of the larger 
+* VNLib collection of libraries and utilities.
+*
+* VNLib.Hashing.Portable is free software: you can redistribute it and/or modify 
+* it under the terms of the GNU General Public License as published
+* by the Free Software Foundation, either version 2 of the License,
+* or (at your option) any later version.
+*
+* VNLib.Hashing.Portable is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
+* General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License 
+* along with VNLib.Hashing.Portable. If not, see http://www.gnu.org/licenses/.
+*/
+
+using System;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+namespace VNLib.Hashing.Checksums
+{
+    /// <summary>
+    /// A managed software implementation of the FNV-1a 64-bit non cryptographic hash algorithm
+    /// </summary>
+    public static class FNV1a
+    {
+        /* 
+        * Constants taken from the spec 
+        * https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+        */
+        const ulong FNV_PRIME = 0x100000001b3UL;
+        const ulong FNV_OFFSET_BASIS = 0xcbf29ce484222325UL;
+
+        /// <summary>
+        /// Computes the next 64-bit FNV-1a hash value using the current hash 
+        /// value and the next byte of data. 
+        /// </summary>
+        /// <param name="initalizer">The inital hash to begin the computation with</param>
+        /// <param name="data"></param>
+        /// <param name="length"></param>
+        /// <returns>The next value of the checksum representing current and previously computed segments</returns>
+        /// <exception cref="ArgumentNullException"></exception>
+        public static ulong Update64(ulong initalizer, ref byte data, nuint length)
+        {
+            if (Unsafe.IsNullRef(ref data))
+            {
+                throw new ArgumentNullException(nameof(data));
+            }
+
+            ulong digest = initalizer;
+
+            for (nuint i = 0; i < length; i++)
+            {
+                digest ^= Unsafe.AddByteOffset(ref data, i);
+                digest *= FNV_PRIME;
+            }
+
+            return digest;
+        }
+
+        /// <summary>
+        /// Computes the next 64-bit FNV-1a hash value using the current hash
+        /// value and the next byte of data.
+        /// </summary>
+        /// <param name="initalizer">The initial hash to begin the computation with</param>
+        /// <param name="data">A span structure pointing to the memory block to compute the digest of</param>
+        /// <returns>The next value of the checksum representing current and previously computed segments</returns>
+        /// <exception cref="ArgumentNullException"></exception>
+        public static ulong Update64(ulong initalizer, ReadOnlySpan<byte> data)
+        {
+            ref byte r0 = ref MemoryMarshal.GetReference(data);
+            return Update64(initalizer, ref r0, (nuint)data.Length);
+        }
+
+        /// <summary>
+        /// Begins computing the FNV-1a 64-bit hash of the input data and returns the 
+        /// initial hash value which may be updated if more data is available
+        /// </summary>
+        /// <param name="data">A managed pointer to the first byte of the sequence to compute</param>
+        /// <param name="length">A platform specific integer representing the length of the input data</param>
+        /// <returns>The 64bit unsigned integer representing the message sum or digest</returns>
+        /// <remarks>
+        /// WARNING: This function produces a non-cryptographic hash and should not be used for
+        /// security or cryptographic purposes. It is intended for fast data integrity checks
+        /// </remarks>
+        public static ulong Compute64(ref byte data, nuint length) => Update64(FNV_OFFSET_BASIS, ref data, length);
+
+        /// <summary>
+        /// Provides a managed software implementation of the FNV-1a 64-bit 
+        /// non cryptographic hash algorithm
+        /// </summary>
+        /// <param name="data">A span structure pointing to the memory block to compute the digest of</param>
+        /// <returns>The 64bit unsigned integer representng the message sum or digest</returns>
+        /// <remarks>
+        /// WARNING: This function produces a non-cryptographic hash and should not be used for
+        /// security or cryptographic purposes. It is intended for fast data integrity checks
+        /// </remarks>
+        public static ulong Compute64(ReadOnlySpan<byte> data)
+        {
+            ref byte r0 = ref MemoryMarshal.GetReference(data);
+            return Compute64(ref r0, (nuint)data.Length);
+        }
+    }
+}
diff --git a/lib/Hashing.Portable/tests/Fnv1aTests.cs b/lib/Hashing.Portable/tests/Fnv1aTests.cs
new file mode 100644
index 0000000..2c6431f
--- /dev/null
+++ b/lib/Hashing.Portable/tests/Fnv1aTests.cs
@@ -0,0 +1,47 @@
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+using System.Text;
+
+using VNLib.Hashing.Checksums;
+
+namespace VNLib.Hashing.Tests
+{
+    [TestClass()]
+    public class Fnv1aTests
+    {
+        const string KnownDataInputUtf81 = "Hello world, this is a test of the FNV1a algorithm";
+        const string KnownData64ChecksumHex1 = "033b9d1635f1c2ad";
+
+        const string KnownDataInputUtf82 = "Hello world, this is another, slightly different test of the FNV1a algorithm!";
+        const string KnownData64ChecksumHex2 = "a802c807e941c5d3";
+
+        [TestMethod()]
+        public void Fnv1a64Known1()
+        {
+            TestKnownData(KnownDataInputUtf81, KnownData64ChecksumHex1);
+            TestKnownData(KnownDataInputUtf82, KnownData64ChecksumHex2);
+        }
+      
+        static void TestKnownData(string input, string knownChecksumHex)
+        {
+            byte[] knownInput = Encoding.UTF8.GetBytes(input);
+            ulong knownChecksum = Convert.ToUInt64(knownChecksumHex, 16);
+
+            ulong checksum = FNV1a.Compute64(knownInput);
+
+            Assert.AreEqual(knownChecksum, checksum);
+
+            //Split input into 2 parts
+            byte[] part1 = knownInput[..(knownInput.Length / 2)];
+            byte[] part2 = knownInput[(knownInput.Length / 2)..];
+
+            //Compute checksum of part1
+            ulong checksum1 = FNV1a.Compute64(part1);
+            ulong outputChecksum = FNV1a.Update64(checksum1, part2);
+
+            Assert.AreNotEqual(checksum1, outputChecksum);
+            Assert.AreEqual(knownChecksum, outputChecksum);
+        }
+
+    }
+}
\ No newline at end of file