From 6d8c3444e09561e5957491b3cc1ae858e0abdd14 Mon Sep 17 00:00:00 2001 From: vnugent Date: Mon, 18 Mar 2024 16:13:20 -0400 Subject: feat: Add FNV1a software checksum and basic correction tests --- lib/Hashing.Portable/src/Checksums/FNV1a.cs | 113 ++++++++++++++++++++++++++++ lib/Hashing.Portable/tests/Fnv1aTests.cs | 47 ++++++++++++ 2 files changed, 160 insertions(+) create mode 100644 lib/Hashing.Portable/src/Checksums/FNV1a.cs create mode 100644 lib/Hashing.Portable/tests/Fnv1aTests.cs 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 +{ + /// + /// A managed software implementation of the FNV-1a 64-bit non cryptographic hash algorithm + /// + 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; + + /// + /// Computes the next 64-bit FNV-1a hash value using the current hash + /// value and the next byte of data. + /// + /// The inital hash to begin the computation with + /// + /// + /// The next value of the checksum representing current and previously computed segments + /// + 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; + } + + /// + /// Computes the next 64-bit FNV-1a hash value using the current hash + /// value and the next byte of data. + /// + /// The initial hash to begin the computation with + /// A span structure pointing to the memory block to compute the digest of + /// The next value of the checksum representing current and previously computed segments + /// + public static ulong Update64(ulong initalizer, ReadOnlySpan data) + { + ref byte r0 = ref MemoryMarshal.GetReference(data); + return Update64(initalizer, ref r0, (nuint)data.Length); + } + + /// + /// 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 + /// + /// A managed pointer to the first byte of the sequence to compute + /// A platform specific integer representing the length of the input data + /// The 64bit unsigned integer representing the message sum or digest + /// + /// 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 + /// + public static ulong Compute64(ref byte data, nuint length) => Update64(FNV_OFFSET_BASIS, ref data, length); + + /// + /// Provides a managed software implementation of the FNV-1a 64-bit + /// non cryptographic hash algorithm + /// + /// A span structure pointing to the memory block to compute the digest of + /// The 64bit unsigned integer representng the message sum or digest + /// + /// 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 + /// + public static ulong Compute64(ReadOnlySpan 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 -- cgit