MurmurHash3.cs 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452
  1. using System;
  2. using System.Collections.Generic;
  3. using System.IO;
  4. using System.Linq;
  5. using System.Runtime.CompilerServices;
  6. using System.Runtime.InteropServices;
  7. using System.Text;
  8. using System.Threading.Tasks;
  9. namespace TEAMModelOS.SDK
  10. {
  11. public static class MurmurHash3
  12. {
  13. public static uint Hash32(string input)
  14. {
  15. var buffer = Encoding.UTF8.GetBytes(input);
  16. uint seed = 0;
  17. using var stream = new MemoryStream(buffer);
  18. var result = MurmurHash3.Hash32(stream, seed);
  19. return result;
  20. }
  21. public static string Hash128(string input)
  22. {
  23. var buffer = Encoding.UTF8.GetBytes(input);
  24. uint seed = 0;
  25. using var stream = new MemoryStream(buffer);
  26. var result = MurmurHash3.Hash128(stream, seed);
  27. return Convert.ToHexString(result);
  28. }
  29. /// <summary>
  30. /// Calculate 32-bit MurmurHash3 hash value using x86 version of the algorithm.
  31. /// </summary>
  32. /// <param name="stream">Input stream.</param>
  33. /// <param name="seed">Seed value.</param>
  34. /// <returns>Hash value.</returns>
  35. public static uint Hash32(Stream stream, uint seed)
  36. {
  37. const int uintSize = sizeof(uint);
  38. const uint final1 = 0x85ebca6b;
  39. const uint final2 = 0xc2b2ae35;
  40. const uint n = 0xe6546b64;
  41. const uint m = 5;
  42. uint hash = seed;
  43. var buffer = new byte[uintSize].AsSpan();
  44. uint length = 0;
  45. int bytesRead;
  46. while ((bytesRead = stream.Read(buffer)) == uintSize)
  47. {
  48. uint k = Bits.ToUInt32(buffer);
  49. round32(ref k, ref hash);
  50. hash = Bits.RotateLeft(hash, 13);
  51. hash *= m;
  52. hash += n;
  53. length += (uint)bytesRead;
  54. }
  55. // process remaning bytes
  56. if (bytesRead > 0)
  57. {
  58. uint remaining = Bits.PartialBytesToUInt32(buffer[..bytesRead]);
  59. round32(ref remaining, ref hash);
  60. length += (uint)bytesRead;
  61. }
  62. hash ^= length;
  63. // finalization mix
  64. hash ^= hash >> 16;
  65. hash *= final1;
  66. hash ^= hash >> 13;
  67. hash *= final2;
  68. hash ^= hash >> 16;
  69. return hash;
  70. }
  71. /// <summary>
  72. /// Calculate 32-bit MurmurHash3 hash value using x86 version of the algorithm.
  73. /// </summary>
  74. /// <param name="stream">Input stream.</param>
  75. /// <param name="seed">Seed value.</param>
  76. /// <returns>A <see cref="Task"/> representing the asynchronous hash operation.</returns>
  77. public static async Task<uint> Hash32Async(Stream stream, uint seed)
  78. {
  79. const int uintSize = sizeof(uint);
  80. const uint final1 = 0x85ebca6b;
  81. const uint final2 = 0xc2b2ae35;
  82. const uint n = 0xe6546b64;
  83. const uint m = 5;
  84. uint hash = seed;
  85. var buffer = new byte[uintSize].AsMemory();
  86. uint length = 0;
  87. int bytesRead;
  88. while ((bytesRead = await stream.ReadAsync(buffer).ConfigureAwait(false)) == uintSize)
  89. {
  90. uint k = Bits.ToUInt32(buffer.Span);
  91. round32(ref k, ref hash);
  92. hash = Bits.RotateLeft(hash, 13);
  93. hash *= m;
  94. hash += n;
  95. length += (uint)bytesRead;
  96. }
  97. // process remaning bytes
  98. if (bytesRead > 0)
  99. {
  100. uint remaining = Bits.PartialBytesToUInt32(buffer[..bytesRead].Span);
  101. round32(ref remaining, ref hash);
  102. length += (uint)bytesRead;
  103. }
  104. hash ^= length;
  105. // finalization mix
  106. hash ^= hash >> 16;
  107. hash *= final1;
  108. hash ^= hash >> 13;
  109. hash *= final2;
  110. hash ^= hash >> 16;
  111. return hash;
  112. }
  113. /// <summary>
  114. /// Calculate 32-bit MurmurHash3 hash value.
  115. /// </summary>
  116. /// <param name="buffer">Input buffer.</param>
  117. /// <param name="seed">Seed value.</param>
  118. /// <returns>Hash value.</returns>
  119. public static uint Hash32(ReadOnlySpan<byte> buffer, uint seed)
  120. {
  121. const int uintSize = sizeof(uint);
  122. const uint final1 = 0x85ebca6b;
  123. const uint final2 = 0xc2b2ae35;
  124. const uint n = 0xe6546b64;
  125. const uint m = 5;
  126. uint hash = seed;
  127. int length = buffer.Length;
  128. var (numUInts, leftBytes) = Math.DivRem(length, uintSize);
  129. int i = 0;
  130. for (; i < numUInts * sizeof(uint); i += sizeof(uint))
  131. {
  132. uint k = Bits.ToUInt32(buffer[i..(i + sizeof(uint))]);
  133. round32(ref k, ref hash);
  134. hash = Bits.RotateLeft(hash, 13);
  135. hash *= m;
  136. hash += n;
  137. }
  138. if (leftBytes > 0)
  139. {
  140. uint remaining = Bits.PartialBytesToUInt32(buffer[i..(i + leftBytes)]);
  141. round32(ref remaining, ref hash);
  142. }
  143. hash ^= (uint)length;
  144. // finalization mix
  145. hash ^= hash >> 16;
  146. hash *= final1;
  147. hash ^= hash >> 13;
  148. hash *= final2;
  149. hash ^= hash >> 16;
  150. return hash;
  151. }
  152. /// <summary>
  153. /// Calculate 128-bit MurmurHash3 hash value using 64-bit version of the algorithm.
  154. /// </summary>
  155. /// <param name="stream">Input stream.</param>
  156. /// <param name="seed">Seed value.</param>
  157. /// <returns>128-bit hash value in a Span.</returns>
  158. public static byte[] Hash128(Stream stream, uint seed)
  159. {
  160. const int ulongSize = sizeof(ulong);
  161. const int blockSize = ulongSize * 2;
  162. const ulong c1 = 0x87c37b91114253d5UL;
  163. const ulong c2 = 0x4cf5ad432745937fUL;
  164. ulong h1 = seed;
  165. ulong h2 = seed;
  166. var buffer = new byte[blockSize].AsSpan();
  167. int outputLength = 0;
  168. int readBytes;
  169. while ((readBytes = stream.Read(buffer)) == blockSize)
  170. {
  171. ulong ik1 = Bits.ToUInt64(buffer);
  172. ulong ik2 = Bits.ToUInt64(buffer[ulongSize..]);
  173. round128(ref ik1, ref h1, c1, c2, h2, 31, 27, 0x52dce729U);
  174. round128(ref ik2, ref h2, c2, c1, h1, 33, 31, 0x38495ab5U);
  175. outputLength += blockSize;
  176. }
  177. ulong k1;
  178. ulong k2;
  179. if (readBytes > ulongSize)
  180. {
  181. k2 = Bits.PartialBytesToUInt64(buffer[ulongSize..]);
  182. tailRound128(ref k2, ref h2, c2, c1, 33);
  183. outputLength += readBytes - ulongSize;
  184. readBytes = ulongSize;
  185. }
  186. if (readBytes > 0)
  187. {
  188. k1 = Bits.PartialBytesToUInt64(buffer[..readBytes]);
  189. tailRound128(ref k1, ref h1, c1, c2, 31);
  190. outputLength += readBytes;
  191. }
  192. h1 ^= (ulong)outputLength;
  193. h2 ^= (ulong)outputLength;
  194. h1 += h2;
  195. h2 += h1;
  196. fmix64(ref h1);
  197. fmix64(ref h2);
  198. h1 += h2;
  199. h2 += h1;
  200. return makeBytes(h1, h2);
  201. }
  202. /// <summary>
  203. /// Calculate 128-bit MurmurHash3 hash value using x64 version of the algorithm.
  204. /// </summary>
  205. /// <param name="buffer">Input buffer.</param>
  206. /// <param name="seed">Seed value.</param>
  207. /// <returns>128-bit hash value as a Span of bytes.</returns>
  208. public static byte[] Hash128(ReadOnlySpan<byte> buffer, uint seed)
  209. {
  210. const int blockSize = 16;
  211. const ulong c1 = 0x87c37b91114253d5UL;
  212. const ulong c2 = 0x4cf5ad432745937fUL;
  213. ulong h1 = seed;
  214. ulong h2 = seed;
  215. int length = buffer.Length;
  216. var (numBlocks, leftBytes) = Math.DivRem(length, blockSize);
  217. int offset = 0;
  218. int end = numBlocks * sizeof(ulong) * 2;
  219. while (offset != end)
  220. {
  221. ulong ik1 = Bits.ToUInt64(buffer[offset..(offset + sizeof(ulong))]);
  222. offset += sizeof(ulong);
  223. ulong ik2 = Bits.ToUInt64(buffer[offset..(offset + sizeof(ulong))]);
  224. offset += sizeof(ulong);
  225. round128(ref ik1, ref h1, c1, c2, h2, 31, 27, 0x52dce729U);
  226. round128(ref ik2, ref h2, c2, c1, h1, 33, 31, 0x38495ab5U);
  227. }
  228. int tail = offset;
  229. ulong k1;
  230. ulong k2;
  231. if (leftBytes > sizeof(ulong))
  232. {
  233. offset += sizeof(ulong);
  234. k2 = Bits.PartialBytesToUInt64(buffer[offset..]);
  235. tailRound128(ref k2, ref h2, c2, c1, 33);
  236. leftBytes = sizeof(ulong);
  237. }
  238. if (leftBytes > 0)
  239. {
  240. k1 = Bits.PartialBytesToUInt64(buffer[tail..(tail + leftBytes)]);
  241. tailRound128(ref k1, ref h1, c1, c2, 31);
  242. }
  243. h1 ^= (ulong)length;
  244. h2 ^= (ulong)length;
  245. h1 += h2;
  246. h2 += h1;
  247. fmix64(ref h1);
  248. fmix64(ref h2);
  249. h1 += h2;
  250. h2 += h1;
  251. return makeBytes(h1, h2);
  252. }
  253. private static byte[] makeBytes(ulong h1, ulong h2)
  254. {
  255. var result = new byte[16];
  256. BitConverter.TryWriteBytes(result, h1);
  257. BitConverter.TryWriteBytes(result.AsSpan()[8..], h2);
  258. return result;
  259. }
  260. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  261. private static void round32(ref uint value, ref uint hash)
  262. {
  263. const uint c1 = 0xcc9e2d51;
  264. const uint c2 = 0x1b873593;
  265. value *= c1;
  266. value = Bits.RotateLeft(value, 15);
  267. value *= c2;
  268. hash ^= value;
  269. }
  270. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  271. private static void round128(
  272. ref ulong k,
  273. ref ulong h,
  274. ulong c1,
  275. ulong c2,
  276. ulong hn,
  277. int krot,
  278. int hrot,
  279. uint x)
  280. {
  281. k *= c1;
  282. k = Bits.RotateLeft(k, krot);
  283. k *= c2;
  284. h ^= k;
  285. h = Bits.RotateLeft(h, hrot);
  286. h += hn;
  287. h = (h * 5) + x;
  288. }
  289. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  290. private static void fmix64(ref ulong h)
  291. {
  292. h ^= h >> 33;
  293. h *= 0xff51afd7ed558ccdUL;
  294. h ^= h >> 33;
  295. h *= 0xc4ceb9fe1a85ec53UL;
  296. h ^= h >> 33;
  297. }
  298. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  299. private static void tailRound128(ref ulong k, ref ulong h, ulong c1, ulong c2, int rot)
  300. {
  301. k *= c1;
  302. k = Bits.RotateLeft(k, rot);
  303. k *= c2;
  304. h ^= k;
  305. }
  306. }
  307. internal static class Bits
  308. {
  309. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  310. internal static ulong RotateLeft(ulong value, int bits)
  311. {
  312. return (value << bits) | (value >> (64 - bits));
  313. }
  314. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  315. internal static uint RotateLeft(uint value, int bits)
  316. {
  317. return (value << bits) | (value >> (32 - bits));
  318. }
  319. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  320. internal static uint RotateRight(uint value, int bits)
  321. {
  322. return (value >> bits) | (value << (32 - bits));
  323. }
  324. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  325. internal static ulong RotateRight(ulong value, int bits)
  326. {
  327. return (value >> bits) | (value << (64 - bits));
  328. }
  329. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  330. internal static ulong ToUInt64(ReadOnlySpan<byte> bytes)
  331. {
  332. return Unsafe.ReadUnaligned<ulong>(ref MemoryMarshal.GetReference(bytes));
  333. }
  334. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  335. internal static uint ToUInt32(ReadOnlySpan<byte> bytes)
  336. {
  337. return Unsafe.ReadUnaligned<uint>(ref MemoryMarshal.GetReference(bytes));
  338. }
  339. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  340. internal static ulong PartialBytesToUInt64(ReadOnlySpan<byte> remainingBytes)
  341. {
  342. // a switch/case approach is slightly faster than the loop but .net
  343. // refuses to inline it due to larger code size.
  344. ulong result = 0;
  345. // trying to modify leftBytes would invalidate inlining
  346. // need to use local variable instead
  347. for (int i = 0; i < remainingBytes.Length; i++)
  348. {
  349. result |= ((ulong)remainingBytes[i]) << (i << 3);
  350. }
  351. return result;
  352. }
  353. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  354. internal static uint PartialBytesToUInt32(ReadOnlySpan<byte> remainingBytes)
  355. {
  356. int len = remainingBytes.Length;
  357. if (len > 3)
  358. {
  359. return Bits.ToUInt32(remainingBytes);
  360. }
  361. // a switch/case approach is slightly faster than the loop but .net
  362. // refuses to inline it due to larger code size.
  363. uint result = remainingBytes[0];
  364. if (len > 1)
  365. {
  366. result |= (uint)(remainingBytes[1] << 8);
  367. }
  368. if (len > 2)
  369. {
  370. result |= (uint)(remainingBytes[2] << 16);
  371. }
  372. return result;
  373. }
  374. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  375. internal static uint SwapBytes32(uint num)
  376. {
  377. return (Bits.RotateLeft(num, 8) & 0x00FF00FFu)
  378. | (Bits.RotateRight(num, 8) & 0xFF00FF00u);
  379. }
  380. [MethodImpl(MethodImplOptions.AggressiveInlining)]
  381. internal static ulong SwapBytes64(ulong num)
  382. {
  383. num = (Bits.RotateLeft(num, 48) & 0xFFFF0000FFFF0000ul)
  384. | (Bits.RotateLeft(num, 16) & 0x0000FFFF0000FFFFul);
  385. return (Bits.RotateLeft(num, 8) & 0xFF00FF00FF00FF00ul)
  386. | (Bits.RotateRight(num, 8) & 0x00FF00FF00FF00FFul);
  387. }
  388. }
  389. }