123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452 |
- 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);
- }
- }
- }
|