497 lines
20 KiB
C#
497 lines
20 KiB
C#
// Licensed to the .NET Foundation under one or more agreements.
|
|
// The .NET Foundation licenses this file to you under the MIT license.
|
|
// See the LICENSE file in the project root for more information.
|
|
|
|
using System.Collections.Generic;
|
|
using System.ComponentModel;
|
|
using System.Runtime.CompilerServices;
|
|
using System.Runtime.InteropServices;
|
|
using System.Security.Cryptography;
|
|
|
|
#pragma warning disable CS0809
|
|
|
|
namespace System;
|
|
|
|
/// <summary>
|
|
/// A polyfill type that mirrors some methods from <see cref="HashCode"/> on .NET 6.
|
|
/// </summary>
|
|
internal struct HashCode
|
|
{
|
|
private const uint Prime1 = 2654435761U;
|
|
private const uint Prime2 = 2246822519U;
|
|
private const uint Prime3 = 3266489917U;
|
|
private const uint Prime4 = 668265263U;
|
|
private const uint Prime5 = 374761393U;
|
|
|
|
private static readonly uint seed = GenerateGlobalSeed();
|
|
|
|
private uint v1, v2, v3, v4;
|
|
private uint queue1, queue2, queue3;
|
|
private uint length;
|
|
|
|
/// <summary>
|
|
/// Initializes the default seed.
|
|
/// </summary>
|
|
/// <returns>A random seed.</returns>
|
|
private static unsafe uint GenerateGlobalSeed()
|
|
{
|
|
byte[] bytes = new byte[4];
|
|
|
|
RandomNumberGenerator.Create().GetBytes(bytes);
|
|
|
|
return BitConverter.ToUInt32(bytes, 0);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines a value into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the value to combine into the hash code.</typeparam>
|
|
/// <param name="value">The value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the value.</returns>
|
|
public static int Combine<T1>(T1 value)
|
|
{
|
|
uint hc1 = (uint)(value?.GetHashCode() ?? 0);
|
|
uint hash = MixEmptyState();
|
|
|
|
hash += 4;
|
|
hash = QueueRound(hash, hc1);
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines two values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2>(T1 value1, T2 value2)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hash = MixEmptyState();
|
|
|
|
hash += 8;
|
|
hash = QueueRound(hash, hc1);
|
|
hash = QueueRound(hash, hc2);
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines three values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T3">The type of the third value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <param name="value3">The third value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2, T3>(T1 value1, T2 value2, T3 value3)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
|
|
uint hash = MixEmptyState();
|
|
|
|
hash += 12;
|
|
hash = QueueRound(hash, hc1);
|
|
hash = QueueRound(hash, hc2);
|
|
hash = QueueRound(hash, hc3);
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines four values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T3">The type of the third value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T4">The type of the fourth value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <param name="value3">The third value to combine into the hash code.</param>
|
|
/// <param name="value4">The fourth value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2, T3, T4>(T1 value1, T2 value2, T3 value3, T4 value4)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
|
|
uint hc4 = (uint)(value4?.GetHashCode() ?? 0);
|
|
|
|
Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
|
|
|
|
v1 = Round(v1, hc1);
|
|
v2 = Round(v2, hc2);
|
|
v3 = Round(v3, hc3);
|
|
v4 = Round(v4, hc4);
|
|
|
|
uint hash = MixState(v1, v2, v3, v4);
|
|
|
|
hash += 16;
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines five values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T3">The type of the third value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T4">The type of the fourth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T5">The type of the fifth value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <param name="value3">The third value to combine into the hash code.</param>
|
|
/// <param name="value4">The fourth value to combine into the hash code.</param>
|
|
/// <param name="value5">The fifth value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2, T3, T4, T5>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
|
|
uint hc4 = (uint)(value4?.GetHashCode() ?? 0);
|
|
uint hc5 = (uint)(value5?.GetHashCode() ?? 0);
|
|
|
|
Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
|
|
|
|
v1 = Round(v1, hc1);
|
|
v2 = Round(v2, hc2);
|
|
v3 = Round(v3, hc3);
|
|
v4 = Round(v4, hc4);
|
|
|
|
uint hash = MixState(v1, v2, v3, v4);
|
|
|
|
hash += 20;
|
|
hash = QueueRound(hash, hc5);
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines six values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T3">The type of the third value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T4">The type of the fourth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T5">The type of the fifth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T6">The type of the sixth value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <param name="value3">The third value to combine into the hash code.</param>
|
|
/// <param name="value4">The fourth value to combine into the hash code.</param>
|
|
/// <param name="value5">The fifth value to combine into the hash code.</param>
|
|
/// <param name="value6">The sixth value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2, T3, T4, T5, T6>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
|
|
uint hc4 = (uint)(value4?.GetHashCode() ?? 0);
|
|
uint hc5 = (uint)(value5?.GetHashCode() ?? 0);
|
|
uint hc6 = (uint)(value6?.GetHashCode() ?? 0);
|
|
|
|
Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
|
|
|
|
v1 = Round(v1, hc1);
|
|
v2 = Round(v2, hc2);
|
|
v3 = Round(v3, hc3);
|
|
v4 = Round(v4, hc4);
|
|
|
|
uint hash = MixState(v1, v2, v3, v4);
|
|
|
|
hash += 24;
|
|
hash = QueueRound(hash, hc5);
|
|
hash = QueueRound(hash, hc6);
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines seven values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T3">The type of the third value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T4">The type of the fourth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T5">The type of the fifth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T6">The type of the sixth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T7">The type of the seventh value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <param name="value3">The third value to combine into the hash code.</param>
|
|
/// <param name="value4">The fourth value to combine into the hash code.</param>
|
|
/// <param name="value5">The fifth value to combine into the hash code.</param>
|
|
/// <param name="value6">The sixth value to combine into the hash code.</param>
|
|
/// <param name="value7">The seventh value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2, T3, T4, T5, T6, T7>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6, T7 value7)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
|
|
uint hc4 = (uint)(value4?.GetHashCode() ?? 0);
|
|
uint hc5 = (uint)(value5?.GetHashCode() ?? 0);
|
|
uint hc6 = (uint)(value6?.GetHashCode() ?? 0);
|
|
uint hc7 = (uint)(value7?.GetHashCode() ?? 0);
|
|
|
|
Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
|
|
|
|
v1 = Round(v1, hc1);
|
|
v2 = Round(v2, hc2);
|
|
v3 = Round(v3, hc3);
|
|
v4 = Round(v4, hc4);
|
|
|
|
uint hash = MixState(v1, v2, v3, v4);
|
|
|
|
hash += 28;
|
|
hash = QueueRound(hash, hc5);
|
|
hash = QueueRound(hash, hc6);
|
|
hash = QueueRound(hash, hc7);
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combines eight values into a hash code.
|
|
/// </summary>
|
|
/// <typeparam name="T1">The type of the first value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T2">The type of the second value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T3">The type of the third value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T4">The type of the fourth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T5">The type of the fifth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T6">The type of the sixth value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T7">The type of the seventh value to combine into the hash code.</typeparam>
|
|
/// <typeparam name="T8">The type of the eighth value to combine into the hash code.</typeparam>
|
|
/// <param name="value1">The first value to combine into the hash code.</param>
|
|
/// <param name="value2">The second value to combine into the hash code.</param>
|
|
/// <param name="value3">The third value to combine into the hash code.</param>
|
|
/// <param name="value4">The fourth value to combine into the hash code.</param>
|
|
/// <param name="value5">The fifth value to combine into the hash code.</param>
|
|
/// <param name="value6">The sixth value to combine into the hash code.</param>
|
|
/// <param name="value7">The seventh value to combine into the hash code.</param>
|
|
/// <param name="value8">The eighth value to combine into the hash code.</param>
|
|
/// <returns>The hash code that represents the values.</returns>
|
|
public static int Combine<T1, T2, T3, T4, T5, T6, T7, T8>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6, T7 value7, T8 value8)
|
|
{
|
|
uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
|
|
uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
|
|
uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
|
|
uint hc4 = (uint)(value4?.GetHashCode() ?? 0);
|
|
uint hc5 = (uint)(value5?.GetHashCode() ?? 0);
|
|
uint hc6 = (uint)(value6?.GetHashCode() ?? 0);
|
|
uint hc7 = (uint)(value7?.GetHashCode() ?? 0);
|
|
uint hc8 = (uint)(value8?.GetHashCode() ?? 0);
|
|
|
|
Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
|
|
|
|
v1 = Round(v1, hc1);
|
|
v2 = Round(v2, hc2);
|
|
v3 = Round(v3, hc3);
|
|
v4 = Round(v4, hc4);
|
|
|
|
v1 = Round(v1, hc5);
|
|
v2 = Round(v2, hc6);
|
|
v3 = Round(v3, hc7);
|
|
v4 = Round(v4, hc8);
|
|
|
|
uint hash = MixState(v1, v2, v3, v4);
|
|
|
|
hash += 32;
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Adds a single value to the current hash.
|
|
/// </summary>
|
|
/// <typeparam name="T">The type of the value to add into the hash code.</typeparam>
|
|
/// <param name="value">The value to add into the hash code.</param>
|
|
public void Add<T>(T value)
|
|
{
|
|
Add(value?.GetHashCode() ?? 0);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Adds a single value to the current hash.
|
|
/// </summary>
|
|
/// <typeparam name="T">The type of the value to add into the hash code.</typeparam>
|
|
/// <param name="value">The value to add into the hash code.</param>
|
|
/// <param name="comparer">The <see cref="IEqualityComparer{T}"/> instance to use.</param>
|
|
public void Add<T>(T value, IEqualityComparer<T>? comparer)
|
|
{
|
|
Add(value is null ? 0 : (comparer?.GetHashCode(value) ?? value.GetHashCode()));
|
|
}
|
|
|
|
/// <summary>
|
|
/// Adds a span of bytes to the hash code.
|
|
/// </summary>
|
|
/// <param name="value">The span.</param>
|
|
public void AddBytes(ReadOnlySpan<byte> value)
|
|
{
|
|
ref byte pos = ref MemoryMarshal.GetReference(value);
|
|
ref byte end = ref Unsafe.Add(ref pos, value.Length);
|
|
|
|
while ((nint)Unsafe.ByteOffset(ref pos, ref end) >= sizeof(int))
|
|
{
|
|
Add(Unsafe.ReadUnaligned<int>(ref pos));
|
|
pos = ref Unsafe.Add(ref pos, sizeof(int));
|
|
}
|
|
|
|
while (Unsafe.IsAddressLessThan(ref pos, ref end))
|
|
{
|
|
Add((int)pos);
|
|
pos = ref Unsafe.Add(ref pos, 1);
|
|
}
|
|
}
|
|
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static void Initialize(out uint v1, out uint v2, out uint v3, out uint v4)
|
|
{
|
|
v1 = seed + Prime1 + Prime2;
|
|
v2 = seed + Prime2;
|
|
v3 = seed;
|
|
v4 = seed - Prime1;
|
|
}
|
|
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static uint Round(uint hash, uint input)
|
|
{
|
|
return RotateLeft(hash + input * Prime2, 13) * Prime1;
|
|
}
|
|
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static uint QueueRound(uint hash, uint queuedValue)
|
|
{
|
|
return RotateLeft(hash + queuedValue * Prime3, 17) * Prime4;
|
|
}
|
|
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static uint MixState(uint v1, uint v2, uint v3, uint v4)
|
|
{
|
|
return RotateLeft(v1, 1) + RotateLeft(v2, 7) + RotateLeft(v3, 12) + RotateLeft(v4, 18);
|
|
}
|
|
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static uint MixEmptyState()
|
|
{
|
|
return seed + Prime5;
|
|
}
|
|
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static uint MixFinal(uint hash)
|
|
{
|
|
hash ^= hash >> 15;
|
|
hash *= Prime2;
|
|
hash ^= hash >> 13;
|
|
hash *= Prime3;
|
|
hash ^= hash >> 16;
|
|
|
|
return hash;
|
|
}
|
|
|
|
private void Add(int value)
|
|
{
|
|
uint val = (uint)value;
|
|
uint previousLength = this.length++;
|
|
uint position = previousLength % 4;
|
|
|
|
if (position == 0)
|
|
{
|
|
this.queue1 = val;
|
|
}
|
|
else if (position == 1)
|
|
{
|
|
this.queue2 = val;
|
|
}
|
|
else if (position == 2)
|
|
{
|
|
this.queue3 = val;
|
|
}
|
|
else
|
|
{
|
|
if (previousLength == 3)
|
|
{
|
|
Initialize(out this.v1, out this.v2, out this.v3, out this.v4);
|
|
}
|
|
|
|
this.v1 = Round(this.v1, this.queue1);
|
|
this.v2 = Round(this.v2, this.queue2);
|
|
this.v3 = Round(this.v3, this.queue3);
|
|
this.v4 = Round(this.v4, val);
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the resulting hashcode from the current instance.
|
|
/// </summary>
|
|
/// <returns>The resulting hashcode from the current instance.</returns>
|
|
public int ToHashCode()
|
|
{
|
|
uint length = this.length;
|
|
uint position = length % 4;
|
|
uint hash = length < 4 ? MixEmptyState() : MixState(this.v1, this.v2, this.v3, this.v4);
|
|
|
|
hash += length * 4;
|
|
|
|
if (position > 0)
|
|
{
|
|
hash = QueueRound(hash, this.queue1);
|
|
|
|
if (position > 1)
|
|
{
|
|
hash = QueueRound(hash, this.queue2);
|
|
|
|
if (position > 2)
|
|
{
|
|
hash = QueueRound(hash, this.queue3);
|
|
}
|
|
}
|
|
}
|
|
|
|
hash = MixFinal(hash);
|
|
|
|
return (int)hash;
|
|
}
|
|
|
|
/// <inheritdoc/>
|
|
[Obsolete("HashCode is a mutable struct and should not be compared with other HashCodes. Use ToHashCode to retrieve the computed hash code.", error: true)]
|
|
[EditorBrowsable(EditorBrowsableState.Never)]
|
|
public override int GetHashCode() => throw new NotSupportedException();
|
|
|
|
/// <inheritdoc/>
|
|
[Obsolete("HashCode is a mutable struct and should not be compared with other HashCodes.", error: true)]
|
|
[EditorBrowsable(EditorBrowsableState.Never)]
|
|
public override bool Equals(object? obj) => throw new NotSupportedException();
|
|
|
|
/// <summary>
|
|
/// Rotates the specified value left by the specified number of bits.
|
|
/// Similar in behavior to the x86 instruction ROL.
|
|
/// </summary>
|
|
/// <param name="value">The value to rotate.</param>
|
|
/// <param name="offset">The number of bits to rotate by.
|
|
/// Any value outside the range [0..31] is treated as congruent mod 32.</param>
|
|
/// <returns>The rotated value.</returns>
|
|
[MethodImpl(MethodImplOptions.AggressiveInlining)]
|
|
private static uint RotateLeft(uint value, int offset)
|
|
{
|
|
return (value << offset) | (value >> (32 - offset));
|
|
}
|
|
} |