1  using System;
 2  using System.Collections.Generic;
 3  
 4  namespace Ryujinx.Graphics.Gpu.Shader.HashTable
 5  {
 6      /// <summary>
 7      /// Smart data accessor that can cache data and hashes to avoid reading and re-hashing the same memory regions.
 8      /// </summary>
 9      ref struct SmartDataAccessor
10      {
11          private readonly IDataAccessor _dataAccessor;
12          private ReadOnlySpan<byte> _data;
13          private readonly SortedList<int, HashState> _cachedHashes;
14  
15          /// <summary>
16          /// Creates a new smart data accessor.
17          /// </summary>
18          /// <param name="dataAccessor">Data accessor</param>
19          public SmartDataAccessor(IDataAccessor dataAccessor)
20          {
21              _dataAccessor = dataAccessor;
22              _data = ReadOnlySpan<byte>.Empty;
23              _cachedHashes = new SortedList<int, HashState>();
24          }
25  
26          /// <summary>
27          /// Get a spans of a given size.
28          /// </summary>
29          /// <remarks>
30          /// The actual length of the span returned depends on the <see cref="IDataAccessor"/>
31          /// and might be less than requested.
32          /// </remarks>
33          /// <param name="length">Size in bytes</param>
34          /// <returns>Span with the requested size</returns>
35          public ReadOnlySpan<byte> GetSpan(int length)
36          {
37              if (_data.Length < length)
38              {
39                  _data = _dataAccessor.GetSpan(0, length);
40              }
41              else if (_data.Length > length)
42              {
43                  return _data[..length];
44              }
45  
46              return _data;
47          }
48  
49          /// <summary>
50          /// Gets a span of the requested size, and a hash of its data.
51          /// </summary>
52          /// <param name="length">Length of the span</param>
53          /// <param name="hash">Hash of the span data</param>
54          /// <returns>Span of data</returns>
55          public ReadOnlySpan<byte> GetSpanAndHash(int length, out uint hash)
56          {
57              ReadOnlySpan<byte> data = GetSpan(length);
58              hash = data.Length == length ? CalcHashCached(data) : 0;
59              return data;
60          }
61  
62          /// <summary>
63          /// Calculates the hash for a requested span.
64          /// This will try to use a cached hash if the data was already accessed before, to avoid re-hashing.
65          /// </summary>
66          /// <param name="data">Data to be hashed</param>
67          /// <returns>Hash of the data</returns>
68          private readonly uint CalcHashCached(ReadOnlySpan<byte> data)
69          {
70              HashState state = default;
71              bool found = false;
72  
73              for (int i = _cachedHashes.Count - 1; i >= 0; i--)
74              {
75                  int cachedHashSize = _cachedHashes.Keys[i];
76  
77                  if (cachedHashSize < data.Length)
78                  {
79                      state = _cachedHashes.Values[i];
80                      found = true;
81                      break;
82                  }
83              }
84  
85              if (!found)
86              {
87                  state = new HashState();
88                  state.Initialize();
89              }
90  
91              state.Continue(data);
92              _cachedHashes[data.Length & ~7] = state;
93              return state.Finalize(data);
94          }
95      }
96  }