Skip to content

Instantly share code, notes, and snippets.

@cocowalla

cocowalla/WyHash64.cs

Created July 10, 2019 19:46
Show Gist options
  • Save cocowalla/01088281bd0b9e3a2763b00e43ce0ade to your computer and use it in GitHub Desktop.
Save cocowalla/01088281bd0b9e3a2763b00e43ce0ade to your computer and use it in GitHub Desktop.
Download ZIP
Wyhash incremental hash
Raw
WyHash64.cs
using System;
using System.Runtime.CompilerServices;
using System.Security.Cryptography;
// ReSharper disable InconsistentNaming
// ReSharper disable SuggestVarOrType_BuiltInTypes
namespace WyHash
{
/// <inheritdoc />
/// <summary>
/// .NET implementation of the wyhash 64-bit hash algorithm by Wang Yi. Reference implementation (version 20190328):
/// https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h
/// </summary>
public class WyHash64 : HashAlgorithm
{
private ulong seed;
private ulong length;
/// <inheritdoc cref="HashAlgorithm.HashSize"/>
public override int HashSize => 64;
public new static WyHash64 Create() => new WyHash64();
public static WyHash64 Create(ulong seed) => new WyHash64(seed);
private WyHash64() { }
private WyHash64(ulong seed = 0)
{
this.seed = seed;
}
/// <summary>
/// Convenience method to compute a WyHash hash and return the result as a 64-bit unsigned integer
/// </summary>
public static ulong ComputeHash64(byte[] array, ulong seed)
{
seed = WyHashCore(array, 0, array.Length, seed);
return HashFinal(seed, (ulong)array.Length);
}
public static ulong ComputePartialHash64(byte[] array, int length, ulong seed)
{
seed = WyHashCoreNew(array, 0, length, seed);
return seed;
}
public override void Initialize()
{
this.seed = 0;
this.length = 0;
}
/// <inheritdoc />
protected override void HashCore(byte[] array, int ibStart, int cbSize)
{
var len = cbSize - ibStart;
this.length += (ulong)len;
this.seed = WyHashCore(array, ibStart, cbSize, this.seed);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe ulong WyHashCore(byte[] array, int ibStart, int cbSize, ulong seed)
{
fixed (byte* pData = array)
{
byte* ptr = pData;
var len = cbSize - ibStart;
var p = 0;
for (int i = ibStart; i + 32 <= len; i += 32, p += 32)
{
// Storing these in temp variables is slightly more performant (presumably it gives some kind of hint to the jitter)
var m1x = WyCore.Read64(ptr, p) ^ WyCore.Prime1;
var m1y = WyCore.Read64(ptr, p + 8) ^ WyCore.Prime2;
var m2x = WyCore.Read64(ptr, p + 16) ^ WyCore.Prime3;
var m2y = WyCore.Read64(ptr, p + 24) ^ WyCore.Prime4;
seed = WyCore.Mum(seed ^ WyCore.Prime0, WyCore.Mum(m1x, m1y) ^ WyCore.Mum(m2x, m2y));
}
seed ^= WyCore.Prime0;
// After the loop we have between 1 and 31 bytes left to process
switch (len & 31)
{
case 1:
seed = WyCore.Mum(seed, WyCore.Read8(ptr, p) ^ WyCore.Prime1);
break;
case 2:
seed = WyCore.Mum(seed, WyCore.Read16(ptr, p) ^ WyCore.Prime1);
break;
case 3:
seed = WyCore.Mum(seed, ((WyCore.Read16(ptr, p) << 8) | WyCore.Read8(ptr, p + 2)) ^ WyCore.Prime1);
break;
case 4:
seed = WyCore.Mum(seed, WyCore.Read32(ptr, p) ^ WyCore.Prime1);
break;
case 5:
seed = WyCore.Mum(seed, ((WyCore.Read32(ptr, p) << 8) | WyCore.Read8(ptr, p + 4)) ^ WyCore.Prime1);
break;
case 6:
seed = WyCore.Mum(seed, ((WyCore.Read32(ptr, p) << 16) | WyCore.Read16(ptr, p + 4)) ^ WyCore.Prime1);
break;
case 7:
seed = WyCore.Mum(seed, ((WyCore.Read32(ptr, p) << 24) | (WyCore.Read16(ptr, p + 4) << 8) | WyCore.Read8(ptr, p + 6)) ^ WyCore.Prime1);
break;
case 8:
seed = WyCore.Mum(seed, WyCore.Read64Swapped(ptr, p) ^ WyCore.Prime1);
break;
case 9:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read8(ptr, p + 8) ^ WyCore.Prime2);
break;
case 10:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read16(ptr, p + 8) ^ WyCore.Prime2);
break;
case 11:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, ((WyCore.Read16(ptr, p + 8) << 8) | WyCore.Read8(ptr, p + 10)) ^ WyCore.Prime2);
break;
case 12:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read32(ptr, p + 8) ^ WyCore.Prime2);
break;
case 13:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, ((WyCore.Read32(ptr, p + 8) << 8) | WyCore.Read8(ptr, p + 12)) ^ WyCore.Prime2);
break;
case 14:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, ((WyCore.Read32(ptr, p + 8) << 16) | WyCore.Read16(ptr, p + 12)) ^ WyCore.Prime2);
break;
case 15:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, ((WyCore.Read32(ptr, p + 8) << 24) | (WyCore.Read16(ptr, p + 12) << 8) | WyCore.Read8(ptr, p + 14)) ^ WyCore.Prime2);
break;
case 16:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2);
break;
case 17:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read8(ptr, p + 16) ^ WyCore.Prime3);
break;
case 18:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read16(ptr, p + 16) ^ WyCore.Prime3);
break;
case 19:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read16(ptr, p + 16) << 8) | WyCore.Read8(ptr, p + 18)) ^ WyCore.Prime3);
break;
case 20:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read32(ptr, p + 16) ^ WyCore.Prime3);
break;
case 21:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read32(ptr, p + 16) << 8) | WyCore.Read8(ptr, p + 20)) ^ WyCore.Prime3);
break;
case 22:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read32(ptr, p + 16) << 16) | WyCore.Read16(ptr, p + 20)) ^ WyCore.Prime3);
break;
case 23:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read32(ptr, p + 16) << 24) | (WyCore.Read16(ptr, p + 20) << 8) | WyCore.Read8(ptr, p + 22)) ^ WyCore.Prime3);
break;
case 24:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read64Swapped(ptr, p + 16) ^ WyCore.Prime3);
break;
case 25:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, WyCore.Read8(ptr, p + 24) ^ WyCore.Prime4);
break;
case 26:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, WyCore.Read16(ptr, p + 24) ^ WyCore.Prime4);
break;
case 27:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, ((WyCore.Read16(ptr, p + 24) << 8) | WyCore.Read8(ptr, p + 26)) ^ WyCore.Prime4);
break;
case 28:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, WyCore.Read32(ptr, p + 24) ^ WyCore.Prime4);
break;
case 29:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, ((WyCore.Read32(ptr, p + 24) << 8) | WyCore.Read8(ptr, p + 28)) ^ WyCore.Prime4);
break;
case 30:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, ((WyCore.Read32(ptr, p + 24) << 16) | WyCore.Read16(ptr, p + 28)) ^ WyCore.Prime4);
break;
case 31: seed = WyCore.Mum(WyCore.Read64Swapped(ptr, p) ^ seed, WyCore.Read64Swapped(ptr, p + 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, p + 16) ^ seed, ((WyCore.Read32(ptr, p + 24) << 24) | (WyCore.Read16(ptr, p + 28) << 8) | WyCore.Read8(ptr, p + 30)) ^ WyCore.Prime4);
break;
}
}
return seed;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe ulong WyHashCoreNew(byte[] array, int ibStart, int cbSize, ulong seed)
{
fixed (byte* pData = array)
{
byte* ptr = pData;
var len = cbSize - ibStart;
var p = 0;
for (int i = ibStart; i + 32 <= len; i += 32, p += 32)
{
// Storing these in temp variables is slightly more performant (presumably it gives some kind of hint to the jitter)
var m1x = WyCore.Read64(ptr, p) ^ WyCore.Prime1;
var m1y = WyCore.Read64(ptr, p + 8) ^ WyCore.Prime2;
var m2x = WyCore.Read64(ptr, p + 16) ^ WyCore.Prime3;
var m2y = WyCore.Read64(ptr, p + 24) ^ WyCore.Prime4;
seed = WyCore.Mum(seed ^ WyCore.Prime0, WyCore.Mum(m1x, m1y) ^ WyCore.Mum(m2x, m2y));
}
}
return seed;
}
/// <inheritdoc />
protected override byte[] HashFinal()
{
var result = HashFinal(this.seed, this.length);
return BitConverter.GetBytes(result);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static ulong HashFinal(ulong seed, ulong length) =>
WyCore.Mum(seed, length ^ WyCore.Prime5);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static unsafe ulong HashFinal(byte[] finalBlock, ulong seed, int finalBlockLength, ulong totalLength)
{
seed ^= WyCore.Prime0;
fixed (byte* pData = finalBlock)
{
byte* ptr = pData;
// After the loop we have between 1 and 31 bytes left to process
switch (finalBlockLength & 31)
{
case 1:
seed = WyCore.Mum(seed, WyCore.Read8(ptr, 0) ^ WyCore.Prime1);
break;
case 2:
seed = WyCore.Mum(seed, WyCore.Read16(ptr, 0) ^ WyCore.Prime1);
break;
case 3:
seed = WyCore.Mum(seed, ((WyCore.Read16(ptr, 0) << 8) | WyCore.Read8(ptr, 2)) ^ WyCore.Prime1);
break;
case 4:
seed = WyCore.Mum(seed, WyCore.Read32(ptr, 0) ^ WyCore.Prime1);
break;
case 5:
seed = WyCore.Mum(seed, ((WyCore.Read32(ptr, 0) << 8) | WyCore.Read8(ptr, 4)) ^ WyCore.Prime1);
break;
case 6:
seed = WyCore.Mum(seed, ((WyCore.Read32(ptr, 0) << 16) | WyCore.Read16(ptr, 4)) ^ WyCore.Prime1);
break;
case 7:
seed = WyCore.Mum(seed, ((WyCore.Read32(ptr, 0) << 24) | (WyCore.Read16(ptr, 4) << 8) | WyCore.Read8(ptr, 6)) ^ WyCore.Prime1);
break;
case 8:
seed = WyCore.Mum(seed, WyCore.Read64Swapped(ptr, 0) ^ WyCore.Prime1);
break;
case 9:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read8(ptr, 8) ^ WyCore.Prime2);
break;
case 10:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read16(ptr, 8) ^ WyCore.Prime2);
break;
case 11:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, ((WyCore.Read16(ptr, 8) << 8) | WyCore.Read8(ptr, 10)) ^ WyCore.Prime2);
break;
case 12:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read32(ptr, 8) ^ WyCore.Prime2);
break;
case 13:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, ((WyCore.Read32(ptr, 8) << 8) | WyCore.Read8(ptr, 12)) ^ WyCore.Prime2);
break;
case 14:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, ((WyCore.Read32(ptr, 8) << 16) | WyCore.Read16(ptr, 12)) ^ WyCore.Prime2);
break;
case 15:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, ((WyCore.Read32(ptr, 8) << 24) | (WyCore.Read16(ptr, 12) << 8) | WyCore.Read8(ptr, 14)) ^ WyCore.Prime2);
break;
case 16:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2);
break;
case 17:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read8(ptr, 16) ^ WyCore.Prime3);
break;
case 18:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read16(ptr, 16) ^ WyCore.Prime3);
break;
case 19:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read16(ptr, 16) << 8) | WyCore.Read8(ptr, 18)) ^ WyCore.Prime3);
break;
case 20:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read32(ptr, 16) ^ WyCore.Prime3);
break;
case 21:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read32(ptr, 16) << 8) | WyCore.Read8(ptr, 20)) ^ WyCore.Prime3);
break;
case 22:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read32(ptr, 16) << 16) | WyCore.Read16(ptr, 20)) ^ WyCore.Prime3);
break;
case 23:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, ((WyCore.Read32(ptr, 16) << 24) | (WyCore.Read16(ptr, 20) << 8) | WyCore.Read8(ptr, 22)) ^ WyCore.Prime3);
break;
case 24:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(seed, WyCore.Read64Swapped(ptr, 16) ^ WyCore.Prime3);
break;
case 25:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, WyCore.Read8(ptr, 24) ^ WyCore.Prime4);
break;
case 26:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, WyCore.Read16(ptr, 24) ^ WyCore.Prime4);
break;
case 27:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, ((WyCore.Read16(ptr, 24) << 8) | WyCore.Read8(ptr, 26)) ^ WyCore.Prime4);
break;
case 28:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, WyCore.Read32(ptr, 24) ^ WyCore.Prime4);
break;
case 29:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, ((WyCore.Read32(ptr, 24) << 8) | WyCore.Read8(ptr, 28)) ^ WyCore.Prime4);
break;
case 30:
seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, ((WyCore.Read32(ptr, 24) << 16) | WyCore.Read16(ptr, 28)) ^ WyCore.Prime4);
break;
case 31: seed = WyCore.Mum(WyCore.Read64Swapped(ptr, 0) ^ seed, WyCore.Read64Swapped(ptr, 8) ^ WyCore.Prime2) ^
WyCore.Mum(WyCore.Read64Swapped(ptr, 16) ^ seed, ((WyCore.Read32(ptr, 24) << 24) | (WyCore.Read16(ptr, 28) << 8) | WyCore.Read8(ptr, 30)) ^ WyCore.Prime4);
break;
}
}
return WyCore.Mum(seed, totalLength ^ WyCore.Prime5);
}
}
}
Raw
WyHash64Tests.cs
using System;
using System.IO;
using System.Security.Cryptography;
using System.Text;
using Shouldly;
using Xunit;
namespace WyHash.UnitTests
{
public class WyHash64Tests
{
[Fact]
public void Should_hash_stream()
{
const ulong seed = 42;
// Generate some data
var data = new byte[3200];
RandomNumberGenerator.Create().GetNonZeroBytes(data);
// Hash the whole byte array in one go, so we can compare our incremental result
var result1 = WyHash64.ComputeHash64(data, seed);
// Will hold the Wyhash state after each round
ulong state = seed;
// Hash the data in 1024-byte blocks
ulong result2 = 0;
using (var ms = new MemoryStream(data))
{
byte[] block = new byte[1024];
for (int i = 0; i < ms.Length; i += 1024)
{
// Read the next block
int numRead = ms.Read(block, 0, 1024);
state = WyHash64.ComputePartialHash64(block, numRead, state);
if (numRead < 1024 || ms.Position == data.Length)
{
// Transform the final block
result2 = WyHash64.HashFinal(block, state, numRead, (ulong)ms.Length);
}
}
}
result1.ShouldBe(result2);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment