modules/platforms/dotnet/Apache.Ignite/Internal/Proto/HashUtils.cs (173 lines of code) (raw):
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
namespace Apache.Ignite.Internal.Proto;
using System;
using System.Buffers.Binary;
using System.Numerics;
using NodaTime;
using Table;
/// <summary>
/// Hash function based on MurmurHash3
/// (https://commons.apache.org/proper/commons-codec/jacoco/org.apache.commons.codec.digest/MurmurHash3.java.html).
/// <para />
/// Ported from org/apache/ignite/internal/util/HashUtils.java.
/// </summary>
internal static class HashUtils
{
private const ulong C1 = 0x87c37b91114253d5L;
private const ulong C2 = 0x4cf5ad432745937fL;
private const int R1 = 31;
private const int R2 = 27;
private const int R3 = 33;
private const int M = 5;
private const int N1 = 0x52dce729;
private const int N2 = 0x38495ab5;
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(sbyte data) => Hash32Internal(unchecked((byte)data), 0, 1);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(short data) => Hash32Internal(unchecked((ushort)data), 0, 2);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(int data) => Hash32(data, 0);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <param name="seed">Seed.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(int data, int seed) => Hash32Internal(unchecked((uint)data), (ulong)seed, 4);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(long data) => Hash32(data, 0);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <param name="seed">Seed.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(long data, int seed) => Hash32Internal(unchecked((ulong)data), (ulong)seed, 8);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(float data) => Hash32(BitConverter.SingleToInt32Bits(data));
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(double data) => Hash32(BitConverter.DoubleToInt64Bits(data));
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(Span<byte> data) => data.IsEmpty ? 0 : Hash32Internal(data, 0);
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(LocalDate data) => Hash32(data.Day, Hash32(data.Month, Hash32(data.Year)));
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <param name="precision">Precision.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(LocalTime data, int precision)
{
var nanos = TemporalTypes.NormalizeNanos(data.NanosecondOfSecond, precision);
return Hash32(nanos, Hash32(data.Second, Hash32(data.Minute, Hash32(data.Hour))));
}
/// <summary>
/// Generates 32-bit hash.
/// </summary>
/// <param name="data">Input data.</param>
/// <param name="precision">Precision.</param>
/// <returns>Resulting hash.</returns>
public static int Hash32(LocalDateTime data, int precision) => Combine(Hash32(data.Date), Hash32(data.TimeOfDay, precision));
/// <summary>
/// Combines two hashes.
/// </summary>
/// <param name="hash1">Hash 1.</param>
/// <param name="hash2">Hash 2.</param>
/// <returns>Combined hash.</returns>
public static int Combine(int hash1, int hash2) => Hash32Internal(unchecked((uint)hash1), unchecked((ulong)hash2), 4);
private static int Hash32Internal(ulong data, ulong seed, byte byteCount)
{
var hash64 = Hash64Internal(data, seed, byteCount);
return (int)(hash64 ^ (hash64 >> 32));
}
private static ulong Hash64Internal(ulong data, ulong seed, byte byteCount)
{
unchecked
{
ulong h1 = seed;
ulong h2 = seed;
ulong k1 = 0;
k1 ^= data;
k1 *= C1;
k1 = BitOperations.RotateLeft(k1, R1);
k1 *= C2;
h1 ^= k1;
// finalization
h1 ^= byteCount;
h2 ^= byteCount;
h1 += h2;
h2 += h1;
h1 = Fmix64(h1);
h2 = Fmix64(h2);
return h1 + h2;
}
}
private static int Hash32Internal(Span<byte> data, ulong seed)
{
var hash64 = Hash64Internal(data, seed);
return (int)(hash64 ^ (hash64 >> 32));
}
private static ulong Hash64Internal(Span<byte> data, ulong seed)
{
unchecked
{
ulong h1 = seed;
ulong h2 = seed;
var length = data.Length;
int nblocks = length >> 4;
// body
for (int i = 0; i < nblocks; i++)
{
int idx = (i << 4);
ulong kk1 = BinaryPrimitives.ReadUInt64LittleEndian(data.Slice(idx));
ulong kk2 = BinaryPrimitives.ReadUInt64LittleEndian(data.Slice(idx + 8));
// mix functions for k1
kk1 *= C1;
kk1 = BitOperations.RotateLeft(kk1, R1);
kk1 *= C2;
h1 ^= kk1;
h1 = BitOperations.RotateLeft(h1, R2);
h1 += h2;
h1 = h1 * M + N1;
// mix functions for k2
kk2 *= C2;
kk2 = BitOperations.RotateLeft(kk2, R3);
kk2 *= C1;
h2 ^= kk2;
h2 = BitOperations.RotateLeft(h2, R1);
h2 += h1;
h2 = h2 * M + N2;
}
// tail
ulong k1 = 0;
ulong k2 = 0;
int index = nblocks << 4;
switch (length - index)
{
case 15:
k2 ^= ((ulong)data[index + 14] & 0xff) << 48;
goto case 14;
case 14:
k2 ^= ((ulong)data[index + 13] & 0xff) << 40;
goto case 13;
case 13:
k2 ^= ((ulong)data[index + 12] & 0xff) << 32;
goto case 12;
case 12:
k2 ^= ((ulong)data[index + 11] & 0xff) << 24;
goto case 11;
case 11:
k2 ^= ((ulong)data[index + 10] & 0xff) << 16;
goto case 10;
case 10:
k2 ^= ((ulong)data[index + 9] & 0xff) << 8;
goto case 9;
case 9:
k2 ^= (ulong)data[index + 8] & 0xff;
k2 *= C2;
k2 = BitOperations.RotateLeft(k2, R3);
k2 *= C1;
h2 ^= k2;
goto case 8;
case 8:
k1 ^= ((ulong)data[index + 7] & 0xff) << 56;
goto case 7;
case 7:
k1 ^= ((ulong)data[index + 6] & 0xff) << 48;
goto case 6;
case 6:
k1 ^= ((ulong)data[index + 5] & 0xff) << 40;
goto case 5;
case 5:
k1 ^= ((ulong)data[index + 4] & 0xff) << 32;
goto case 4;
case 4:
k1 ^= ((ulong)data[index + 3] & 0xff) << 24;
goto case 3;
case 3:
k1 ^= ((ulong)data[index + 2] & 0xff) << 16;
goto case 2;
case 2:
k1 ^= ((ulong)data[index + 1] & 0xff) << 8;
goto case 1;
case 1:
k1 ^= (ulong)data[index] & 0xff;
k1 *= C1;
k1 = BitOperations.RotateLeft(k1, R1);
k1 *= C2;
h1 ^= k1;
break;
}
// finalization
h1 ^= (ulong)length;
h2 ^= (ulong)length;
h1 += h2;
h2 += h1;
h1 = Fmix64(h1);
h2 = Fmix64(h2);
return h1 + h2;
}
}
private static ulong Fmix64(ulong hash)
{
unchecked
{
hash ^= hash >> 33;
hash *= 0xff51afd7ed558ccdL;
hash ^= hash >> 33;
hash *= 0xc4ceb9fe1a85ec53L;
hash ^= hash >> 33;
return hash;
}
}
}