1  using System;
  2  using System.Runtime.InteropServices;
  3  
  4  namespace Ryujinx.Graphics.Gpu.Shader.HashTable
  5  {
  6      /// <summary>
  7      /// State of a hash calculation.
  8      /// </summary>
  9      struct HashState
 10      {
 11          // This is using a slightly modified implementation of FastHash64.
 12          // Reference: https://github.com/ztanml/fast-hash/blob/master/fasthash.c
 13          private const ulong M = 0x880355f21e6d1965UL;
 14          private ulong _hash;
 15          private int _start;
 16  
 17          /// <summary>
 18          /// One shot hash calculation for a given data.
 19          /// </summary>
 20          /// <param name="data">Data to be hashed</param>
 21          /// <returns>Hash of the given data</returns>
 22          public static uint CalcHash(ReadOnlySpan<byte> data)
 23          {
 24              HashState state = new();
 25  
 26              state.Initialize();
 27              state.Continue(data);
 28              return state.Finalize(data);
 29          }
 30  
 31          /// <summary>
 32          /// Initializes the hash state.
 33          /// </summary>
 34          public void Initialize()
 35          {
 36              _hash = 23;
 37          }
 38  
 39          /// <summary>
 40          /// Calculates the hash of the given data.
 41          /// </summary>
 42          /// <remarks>
 43          /// The full data must be passed on <paramref name="data"/>.
 44          /// If this is not the first time the method is called, then <paramref name="data"/> must start with the data passed on the last call.
 45          /// If a smaller slice of the data was already hashed before, only the additional data will be hashed.
 46          /// This can be used for additive hashing of data in chuncks.
 47          /// </remarks>
 48          /// <param name="data">Data to be hashed</param>
 49          public void Continue(ReadOnlySpan<byte> data)
 50          {
 51              ulong h = _hash;
 52  
 53              ReadOnlySpan<ulong> dataAsUlong = MemoryMarshal.Cast<byte, ulong>(data[_start..]);
 54  
 55              for (int i = 0; i < dataAsUlong.Length; i++)
 56              {
 57                  ulong value = dataAsUlong[i];
 58  
 59                  h ^= Mix(value);
 60                  h *= M;
 61              }
 62  
 63              _hash = h;
 64              _start = data.Length & ~7;
 65          }
 66  
 67          /// <summary>
 68          /// Performs the hash finalization step, and returns the calculated hash.
 69          /// </summary>
 70          /// <remarks>
 71          /// The full data must be passed on <paramref name="data"/>.
 72          /// <paramref name="data"/> must start with the data passed on the last call to <see cref="Continue"/>.
 73          /// No internal state is changed, so one can still continue hashing data with <see cref="Continue"/>
 74          /// after calling this method.
 75          /// </remarks>
 76          /// <param name="data">Data to be hashed</param>
 77          /// <returns>Hash of all the data hashed with this <see cref="HashState"/></returns>
 78          public readonly uint Finalize(ReadOnlySpan<byte> data)
 79          {
 80              ulong h = _hash;
 81  
 82              int remainder = data.Length & 7;
 83              if (remainder != 0)
 84              {
 85                  ulong v = 0;
 86  
 87                  for (int i = data.Length - remainder; i < data.Length; i++)
 88                  {
 89                      v |= (ulong)data[i] << ((i - remainder) * 8);
 90                  }
 91  
 92                  h ^= Mix(v);
 93                  h *= M;
 94              }
 95  
 96              h = Mix(h);
 97              return (uint)(h - (h >> 32));
 98          }
 99  
100          /// <summary>
101          /// Hash mix function.
102          /// </summary>
103          /// <param name="h">Hash to mix</param>
104          /// <returns>Mixed hash</returns>
105          private static ulong Mix(ulong h)
106          {
107              h ^= h >> 23;
108              h *= 0x2127599bf4325c37UL;
109              h ^= h >> 47;
110              return h;
111          }
112      }
113  }