TEAMModelOS/TEAMModelOS.SDK/Helper/Security/Hash/MurmurHash3.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace TEAMModelOS.SDK
{
    public static class MurmurHash3
    {
        public static uint Hash32(string input)
        {
            var buffer = Encoding.UTF8.GetBytes(input);
            uint seed = 0;
            using var stream = new MemoryStream(buffer);
            var result = MurmurHash3.Hash32(stream, seed);
            return result;
        }
        public static string Hash128(string input)
        {
            var buffer = Encoding.UTF8.GetBytes(input);
            uint seed = 0;
            using var stream = new MemoryStream(buffer);
            var result = MurmurHash3.Hash128(stream, seed);
            return Convert.ToHexString(result);
        }

        /// <summary>
        /// Calculate 32-bit MurmurHash3 hash value using x86 version of the algorithm.
        /// </summary>
        /// <param name="stream">Input stream.</param>
        /// <param name="seed">Seed value.</param>
        /// <returns>Hash value.</returns>
        public static uint Hash32(Stream stream, uint seed)
        {
            const int uintSize = sizeof(uint);
            const uint final1 = 0x85ebca6b;
            const uint final2 = 0xc2b2ae35;
            const uint n = 0xe6546b64;
            const uint m = 5;

            uint hash = seed;
            var buffer = new byte[uintSize].AsSpan();
            uint length = 0;
            int bytesRead;
            while ((bytesRead = stream.Read(buffer)) == uintSize)
            {
                uint k = Bits.ToUInt32(buffer);
                round32(ref k, ref hash);
                hash = Bits.RotateLeft(hash, 13);
                hash *= m;
                hash += n;
                length += (uint)bytesRead;
            }

            // process remaning bytes
            if (bytesRead > 0)
            {
                uint remaining = Bits.PartialBytesToUInt32(buffer[..bytesRead]);
                round32(ref remaining, ref hash);
                length += (uint)bytesRead;
            }

            hash ^= length;

            // finalization mix
            hash ^= hash >> 16;
            hash *= final1;
            hash ^= hash >> 13;
            hash *= final2;
            hash ^= hash >> 16;
            return hash;
        }

        /// <summary>
        /// Calculate 32-bit MurmurHash3 hash value using x86 version of the algorithm.
        /// </summary>
        /// <param name="stream">Input stream.</param>
        /// <param name="seed">Seed value.</param>
        /// <returns>A <see cref="Task"/> representing the asynchronous hash operation.</returns>
        public static async Task<uint> Hash32Async(Stream stream, uint seed)
        {
            const int uintSize = sizeof(uint);
            const uint final1 = 0x85ebca6b;
            const uint final2 = 0xc2b2ae35;
            const uint n = 0xe6546b64;
            const uint m = 5;

            uint hash = seed;
            var buffer = new byte[uintSize].AsMemory();
            uint length = 0;
            int bytesRead;
            while ((bytesRead = await stream.ReadAsync(buffer).ConfigureAwait(false)) == uintSize)
            {
                uint k = Bits.ToUInt32(buffer.Span);
                round32(ref k, ref hash);
                hash = Bits.RotateLeft(hash, 13);
                hash *= m;
                hash += n;
                length += (uint)bytesRead;
            }

            // process remaning bytes
            if (bytesRead > 0)
            {
                uint remaining = Bits.PartialBytesToUInt32(buffer[..bytesRead].Span);
                round32(ref remaining, ref hash);
                length += (uint)bytesRead;
            }

            hash ^= length;

            // finalization mix
            hash ^= hash >> 16;
            hash *= final1;
            hash ^= hash >> 13;
            hash *= final2;
            hash ^= hash >> 16;
            return hash;
        }

        /// <summary>
        /// Calculate 32-bit MurmurHash3 hash value.
        /// </summary>
        /// <param name="buffer">Input buffer.</param>
        /// <param name="seed">Seed value.</param>
        /// <returns>Hash value.</returns>
        public static uint Hash32(ReadOnlySpan<byte> buffer, uint seed)
        {
            const int uintSize = sizeof(uint);
            const uint final1 = 0x85ebca6b;
            const uint final2 = 0xc2b2ae35;
            const uint n = 0xe6546b64;
            const uint m = 5;

            uint hash = seed;
            int length = buffer.Length;
            var (numUInts, leftBytes) = Math.DivRem(length, uintSize);
            int i = 0;
            for (; i < numUInts * sizeof(uint); i += sizeof(uint))
            {
                uint k = Bits.ToUInt32(buffer[i..(i + sizeof(uint))]);
                round32(ref k, ref hash);
                hash = Bits.RotateLeft(hash, 13);
                hash *= m;
                hash += n;
            }

            if (leftBytes > 0)
            {
                uint remaining = Bits.PartialBytesToUInt32(buffer[i..(i + leftBytes)]);
                round32(ref remaining, ref hash);
            }

            hash ^= (uint)length;

            // finalization mix
            hash ^= hash >> 16;
            hash *= final1;
            hash ^= hash >> 13;
            hash *= final2;
            hash ^= hash >> 16;
            return hash;
        }

        /// <summary>
        /// Calculate 128-bit MurmurHash3 hash value using 64-bit version of the algorithm.
        /// </summary>
        /// <param name="stream">Input stream.</param>
        /// <param name="seed">Seed value.</param>
        /// <returns>128-bit hash value in a Span.</returns>
        public static byte[] Hash128(Stream stream, uint seed)
        {
            const int ulongSize = sizeof(ulong);
            const int blockSize = ulongSize * 2;

            const ulong c1 = 0x87c37b91114253d5UL;
            const ulong c2 = 0x4cf5ad432745937fUL;

            ulong h1 = seed;
            ulong h2 = seed;
            var buffer = new byte[blockSize].AsSpan();
            int outputLength = 0;
            int readBytes;
            while ((readBytes = stream.Read(buffer)) == blockSize)
            {
                ulong ik1 = Bits.ToUInt64(buffer);
                ulong ik2 = Bits.ToUInt64(buffer[ulongSize..]);

                round128(ref ik1, ref h1, c1, c2, h2, 31, 27, 0x52dce729U);
                round128(ref ik2, ref h2, c2, c1, h1, 33, 31, 0x38495ab5U);

                outputLength += blockSize;
            }

            ulong k1;
            ulong k2;

            if (readBytes > ulongSize)
            {
                k2 = Bits.PartialBytesToUInt64(buffer[ulongSize..]);
                tailRound128(ref k2, ref h2, c2, c1, 33);
                outputLength += readBytes - ulongSize;
                readBytes = ulongSize;
            }

            if (readBytes > 0)
            {
                k1 = Bits.PartialBytesToUInt64(buffer[..readBytes]);
                tailRound128(ref k1, ref h1, c1, c2, 31);
                outputLength += readBytes;
            }

            h1 ^= (ulong)outputLength;
            h2 ^= (ulong)outputLength;

            h1 += h2;
            h2 += h1;

            fmix64(ref h1);
            fmix64(ref h2);

            h1 += h2;
            h2 += h1;

            return makeBytes(h1, h2);
        }

        /// <summary>
        /// Calculate 128-bit MurmurHash3 hash value using x64 version of the algorithm.
        /// </summary>
        /// <param name="buffer">Input buffer.</param>
        /// <param name="seed">Seed value.</param>
        /// <returns>128-bit hash value as a Span of bytes.</returns>
        public static byte[] Hash128(ReadOnlySpan<byte> buffer, uint seed)
        {
            const int blockSize = 16;
            const ulong c1 = 0x87c37b91114253d5UL;
            const ulong c2 = 0x4cf5ad432745937fUL;

            ulong h1 = seed;
            ulong h2 = seed;

            int length = buffer.Length;
            var (numBlocks, leftBytes) = Math.DivRem(length, blockSize);

            int offset = 0;
            int end = numBlocks * sizeof(ulong) * 2;
            while (offset != end)
            {
                ulong ik1 = Bits.ToUInt64(buffer[offset..(offset + sizeof(ulong))]);
                offset += sizeof(ulong);
                ulong ik2 = Bits.ToUInt64(buffer[offset..(offset + sizeof(ulong))]);
                offset += sizeof(ulong);

                round128(ref ik1, ref h1, c1, c2, h2, 31, 27, 0x52dce729U);
                round128(ref ik2, ref h2, c2, c1, h1, 33, 31, 0x38495ab5U);
            }

            int tail = offset;
            ulong k1;
            ulong k2;

            if (leftBytes > sizeof(ulong))
            {
                offset += sizeof(ulong);
                k2 = Bits.PartialBytesToUInt64(buffer[offset..]);
                tailRound128(ref k2, ref h2, c2, c1, 33);
                leftBytes = sizeof(ulong);
            }

            if (leftBytes > 0)
            {
                k1 = Bits.PartialBytesToUInt64(buffer[tail..(tail + leftBytes)]);
                tailRound128(ref k1, ref h1, c1, c2, 31);
            }

            h1 ^= (ulong)length;
            h2 ^= (ulong)length;

            h1 += h2;
            h2 += h1;

            fmix64(ref h1);
            fmix64(ref h2);

            h1 += h2;
            h2 += h1;

            return makeBytes(h1, h2);
        }

        private static byte[] makeBytes(ulong h1, ulong h2)
        {
            var result = new byte[16];
            BitConverter.TryWriteBytes(result, h1);
            BitConverter.TryWriteBytes(result.AsSpan()[8..], h2);
            return result;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void round32(ref uint value, ref uint hash)
        {
            const uint c1 = 0xcc9e2d51;
            const uint c2 = 0x1b873593;

            value *= c1;
            value = Bits.RotateLeft(value, 15);
            value *= c2;
            hash ^= value;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void round128(
            ref ulong k,
            ref ulong h,
            ulong c1,
            ulong c2,
            ulong hn,
            int krot,
            int hrot,
            uint x)
        {
            k *= c1;
            k = Bits.RotateLeft(k, krot);
            k *= c2;
            h ^= k;
            h = Bits.RotateLeft(h, hrot);
            h += hn;
            h = (h * 5) + x;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void fmix64(ref ulong h)
        {
            h ^= h >> 33;
            h *= 0xff51afd7ed558ccdUL;
            h ^= h >> 33;
            h *= 0xc4ceb9fe1a85ec53UL;
            h ^= h >> 33;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void tailRound128(ref ulong k, ref ulong h, ulong c1, ulong c2, int rot)
        {
            k *= c1;
            k = Bits.RotateLeft(k, rot);
            k *= c2;
            h ^= k;
        }
    }

    internal static class Bits
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static ulong RotateLeft(ulong value, int bits)
        {
            return (value << bits) | (value >> (64 - bits));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static uint RotateLeft(uint value, int bits)
        {
            return (value << bits) | (value >> (32 - bits));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static uint RotateRight(uint value, int bits)
        {
            return (value >> bits) | (value << (32 - bits));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static ulong RotateRight(ulong value, int bits)
        {
            return (value >> bits) | (value << (64 - bits));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static ulong ToUInt64(ReadOnlySpan<byte> bytes)
        {
            return Unsafe.ReadUnaligned<ulong>(ref MemoryMarshal.GetReference(bytes));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static uint ToUInt32(ReadOnlySpan<byte> bytes)
        {
            return Unsafe.ReadUnaligned<uint>(ref MemoryMarshal.GetReference(bytes));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static ulong PartialBytesToUInt64(ReadOnlySpan<byte> remainingBytes)
        {
            // a switch/case approach is slightly faster than the loop but .net
            // refuses to inline it due to larger code size.
            ulong result = 0;

            // trying to modify leftBytes would invalidate inlining
            // need to use local variable instead
            for (int i = 0; i < remainingBytes.Length; i++)
            {
                result |= ((ulong)remainingBytes[i]) << (i << 3);
            }

            return result;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static uint PartialBytesToUInt32(ReadOnlySpan<byte> remainingBytes)
        {
            int len = remainingBytes.Length;
            if (len > 3)
            {
                return Bits.ToUInt32(remainingBytes);
            }

            // a switch/case approach is slightly faster than the loop but .net
            // refuses to inline it due to larger code size.
            uint result = remainingBytes[0];
            if (len > 1)
            {
                result |= (uint)(remainingBytes[1] << 8);
            }

            if (len > 2)
            {
                result |= (uint)(remainingBytes[2] << 16);
            }

            return result;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static uint SwapBytes32(uint num)
        {
            return (Bits.RotateLeft(num, 8) & 0x00FF00FFu)
                 | (Bits.RotateRight(num, 8) & 0xFF00FF00u);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static ulong SwapBytes64(ulong num)
        {
            num = (Bits.RotateLeft(num, 48) & 0xFFFF0000FFFF0000ul)
                | (Bits.RotateLeft(num, 16) & 0x0000FFFF0000FFFFul);
            return (Bits.RotateLeft(num, 8) & 0xFF00FF00FF00FF00ul)
                 | (Bits.RotateRight(num, 8) & 0x00FF00FF00FF00FFul);
        }
    }
}