diff options
| author | TSR Berry <20988865+TSRBerry@users.noreply.github.com> | 2023-04-08 01:22:00 +0200 |
|---|---|---|
| committer | Mary <thog@protonmail.com> | 2023-04-27 23:51:14 +0200 |
| commit | cee712105850ac3385cd0091a923438167433f9f (patch) | |
| tree | 4a5274b21d8b7f938c0d0ce18736d3f2993b11b1 /Ryujinx.Graphics.Gpu/Shader/HashTable | |
| parent | cd124bda587ef09668a971fa1cac1c3f0cfc9f21 (diff) | |
Move solution and projects to src
Diffstat (limited to 'Ryujinx.Graphics.Gpu/Shader/HashTable')
5 files changed, 0 insertions, 931 deletions
diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs deleted file mode 100644 index 584eefdc..00000000 --- a/Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs +++ /dev/null @@ -1,113 +0,0 @@ -using System; -using System.Runtime.InteropServices; - -namespace Ryujinx.Graphics.Gpu.Shader.HashTable -{ - /// <summary> - /// State of a hash calculation. - /// </summary> - struct HashState - { - // This is using a slightly modified implementation of FastHash64. - // Reference: https://github.com/ztanml/fast-hash/blob/master/fasthash.c - private const ulong M = 0x880355f21e6d1965UL; - private ulong _hash; - private int _start; - - /// <summary> - /// One shot hash calculation for a given data. - /// </summary> - /// <param name="data">Data to be hashed</param> - /// <returns>Hash of the given data</returns> - public static uint CalcHash(ReadOnlySpan<byte> data) - { - HashState state = new HashState(); - - state.Initialize(); - state.Continue(data); - return state.Finalize(data); - } - - /// <summary> - /// Initializes the hash state. - /// </summary> - public void Initialize() - { - _hash = 23; - } - - /// <summary> - /// Calculates the hash of the given data. - /// </summary> - /// <remarks> - /// The full data must be passed on <paramref name="data"/>. - /// 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. - /// If a smaller slice of the data was already hashed before, only the additional data will be hashed. - /// This can be used for additive hashing of data in chuncks. - /// </remarks> - /// <param name="data">Data to be hashed</param> - public void Continue(ReadOnlySpan<byte> data) - { - ulong h = _hash; - - ReadOnlySpan<ulong> dataAsUlong = MemoryMarshal.Cast<byte, ulong>(data.Slice(_start)); - - for (int i = 0; i < dataAsUlong.Length; i++) - { - ulong value = dataAsUlong[i]; - - h ^= Mix(value); - h *= M; - } - - _hash = h; - _start = data.Length & ~7; - } - - /// <summary> - /// Performs the hash finalization step, and returns the calculated hash. - /// </summary> - /// <remarks> - /// The full data must be passed on <paramref name="data"/>. - /// <paramref name="data"/> must start with the data passed on the last call to <see cref="Continue"/>. - /// No internal state is changed, so one can still continue hashing data with <see cref="Continue"/> - /// after calling this method. - /// </remarks> - /// <param name="data">Data to be hashed</param> - /// <returns>Hash of all the data hashed with this <see cref="HashState"/></returns> - public uint Finalize(ReadOnlySpan<byte> data) - { - ulong h = _hash; - - int remainder = data.Length & 7; - if (remainder != 0) - { - ulong v = 0; - - for (int i = data.Length - remainder; i < data.Length; i++) - { - v |= (ulong)data[i] << ((i - remainder) * 8); - } - - h ^= Mix(v); - h *= M; - } - - h = Mix(h); - return (uint)(h - (h >> 32)); - } - - /// <summary> - /// Hash mix function. - /// </summary> - /// <param name="h">Hash to mix</param> - /// <returns>Mixed hash</returns> - private static ulong Mix(ulong h) - { - h ^= h >> 23; - h *= 0x2127599bf4325c37UL; - h ^= h >> 47; - return h; - } - } -} diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/IDataAccessor.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/IDataAccessor.cs deleted file mode 100644 index c982cd9f..00000000 --- a/Ryujinx.Graphics.Gpu/Shader/HashTable/IDataAccessor.cs +++ /dev/null @@ -1,27 +0,0 @@ -using System; - -namespace Ryujinx.Graphics.Gpu.Shader.HashTable -{ - /// <summary> - /// Data accessor, used by <see cref="PartitionedHashTable{T}"/> to access data of unknown length. - /// </summary> - /// <remarks> - /// This will be used to access chuncks of data and try finding a match on the table. - /// This is necessary because the data size is assumed to be unknown, and so the - /// hash table must try to "guess" the size of the data based on the entries on the table. - /// </remarks> - public interface IDataAccessor - { - /// <summary> - /// Gets a span of shader code at the specified offset, with at most the specified size. - /// </summary> - /// <remarks> - /// This might return a span smaller than the requested <paramref name="length"/> if there's - /// no more code available. - /// </remarks> - /// <param name="offset">Offset in shader code</param> - /// <param name="length">Size in bytes</param> - /// <returns>Shader code span</returns> - ReadOnlySpan<byte> GetSpan(int offset, int length); - } -} diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs deleted file mode 100644 index d7cb3d99..00000000 --- a/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs +++ /dev/null @@ -1,451 +0,0 @@ -using System; -using System.Collections.Generic; -using System.Numerics; - -namespace Ryujinx.Graphics.Gpu.Shader.HashTable -{ - /// <summary> - /// Partitioned hash table. - /// </summary> - /// <typeparam name="T">Hash table entry type</typeparam> - class PartitionHashTable<T> - { - /// <summary> - /// Hash table entry. - /// </summary> - private struct Entry - { - /// <summary> - /// Hash <see cref="OwnSize"/> bytes of <see cref="Data"/>. - /// </summary> - public readonly uint Hash; - - /// <summary> - /// If this entry is only a sub-region of <see cref="Data"/>, this indicates the size in bytes - /// of that region. Otherwise, it should be zero. - /// </summary> - public readonly int OwnSize; - - /// <summary> - /// Data used to compute the hash for this entry. - /// </summary> - /// <remarks> - /// To avoid additional allocations, this might be a instance of the full entry data, - /// and only a sub-region of it might be actually used by this entry. Such sub-region - /// has its size indicated by <see cref="OwnSize"/> in this case. - /// </remarks> - public readonly byte[] Data; - - /// <summary> - /// Item associated with this entry. - /// </summary> - public T Item; - - /// <summary> - /// Indicates if the entry is partial, which means that this entry is only for a sub-region of the data. - /// </summary> - /// <remarks> - /// Partial entries have no items associated with them. They just indicates that the data might be present on - /// the table, and one must keep looking for the full entry on other tables of larger data size. - /// </remarks> - public bool IsPartial => OwnSize != 0; - - /// <summary> - /// Creates a new partial hash table entry. - /// </summary> - /// <param name="hash">Hash of the data</param> - /// <param name="ownerData">Full data</param> - /// <param name="ownSize">Size of the sub-region of data that belongs to this entry</param> - public Entry(uint hash, byte[] ownerData, int ownSize) - { - Hash = hash; - OwnSize = ownSize; - Data = ownerData; - Item = default; - } - - /// <summary> - /// Creates a new full hash table entry. - /// </summary> - /// <param name="hash">Hash of the data</param> - /// <param name="data">Data</param> - /// <param name="item">Item associated with this entry</param> - public Entry(uint hash, byte[] data, T item) - { - Hash = hash; - OwnSize = 0; - Data = data; - Item = item; - } - - /// <summary> - /// Gets the data for this entry, either full or partial. - /// </summary> - /// <returns>Data sub-region</returns> - public ReadOnlySpan<byte> GetData() - { - if (OwnSize != 0) - { - return new ReadOnlySpan<byte>(Data).Slice(0, OwnSize); - } - - return Data; - } - } - - /// <summary> - /// Hash table bucket. - /// </summary> - private struct Bucket - { - /// <summary> - /// Inline entry, to avoid allocations for the common single entry case. - /// </summary> - public Entry InlineEntry; - - /// <summary> - /// List of additional entries for the not-so-common multiple entries case. - /// </summary> - public List<Entry> MoreEntries; - } - - private Bucket[] _buckets; - private int _count; - - /// <summary> - /// Total amount of entries on the hash table. - /// </summary> - public int Count => _count; - - /// <summary> - /// Creates a new instance of the partitioned hash table. - /// </summary> - public PartitionHashTable() - { - _buckets = Array.Empty<Bucket>(); - } - - /// <summary> - /// Gets an item on the table, or adds a new one if not present. - /// </summary> - /// <param name="data">Data</param> - /// <param name="dataHash">Hash of the data</param> - /// <param name="item">Item to be added if not found</param> - /// <returns>Existing item if found, or <paramref name="item"/> if not found</returns> - public T GetOrAdd(byte[] data, uint dataHash, T item) - { - if (TryFindItem(dataHash, data, out T existingItem)) - { - return existingItem; - } - - Entry entry = new Entry(dataHash, data, item); - - AddToBucket(dataHash, ref entry); - - return item; - } - - /// <summary> - /// Adds an item to the hash table. - /// </summary> - /// <param name="data">Data</param> - /// <param name="dataHash">Hash of the data</param> - /// <param name="item">Item to be added</param> - /// <returns>True if the item was added, false due to an item associated with the data already being on the table</returns> - public bool Add(byte[] data, uint dataHash, T item) - { - if (TryFindItem(dataHash, data, out _)) - { - return false; - } - - Entry entry = new Entry(dataHash, data, item); - - AddToBucket(dataHash, ref entry); - - return true; - } - - /// <summary> - /// Adds a partial entry to the hash table. - /// </summary> - /// <param name="ownerData">Full data</param> - /// <param name="ownSize">Size of the sub-region of <paramref name="ownerData"/> used by the partial entry</param> - /// <returns>True if added, false otherwise</returns> - public bool AddPartial(byte[] ownerData, int ownSize) - { - ReadOnlySpan<byte> data = new ReadOnlySpan<byte>(ownerData).Slice(0, ownSize); - - return AddPartial(ownerData, HashState.CalcHash(data), ownSize); - } - - /// <summary> - /// Adds a partial entry to the hash table. - /// </summary> - /// <param name="ownerData">Full data</param> - /// <param name="dataHash">Hash of the data sub-region</param> - /// <param name="ownSize">Size of the sub-region of <paramref name="ownerData"/> used by the partial entry</param> - /// <returns>True if added, false otherwise</returns> - public bool AddPartial(byte[] ownerData, uint dataHash, int ownSize) - { - ReadOnlySpan<byte> data = new ReadOnlySpan<byte>(ownerData).Slice(0, ownSize); - - if (TryFindItem(dataHash, data, out _)) - { - return false; - } - - Entry entry = new Entry(dataHash, ownerData, ownSize); - - AddToBucket(dataHash, ref entry); - - return true; - } - - /// <summary> - /// Adds entry with a given hash to the table. - /// </summary> - /// <param name="dataHash">Hash of the entry</param> - /// <param name="entry">Entry</param> - private void AddToBucket(uint dataHash, ref Entry entry) - { - int pow2Count = GetPow2Count(++_count); - if (pow2Count != _buckets.Length) - { - Rebuild(pow2Count); - } - - ref Bucket bucket = ref GetBucketForHash(dataHash); - - AddToBucket(ref bucket, ref entry); - } - - /// <summary> - /// Adds an entry to a bucket. - /// </summary> - /// <param name="bucket">Bucket to add the entry into</param> - /// <param name="entry">Entry to be added</param> - private void AddToBucket(ref Bucket bucket, ref Entry entry) - { - if (bucket.InlineEntry.Data == null) - { - bucket.InlineEntry = entry; - } - else - { - (bucket.MoreEntries ??= new List<Entry>()).Add(entry); - } - } - - /// <summary> - /// Creates partial entries on a new hash table for all existing full entries. - /// </summary> - /// <remarks> - /// This should be called every time a new hash table is created, and there are hash - /// tables with data sizes that are higher than that of the new table. - /// This will then fill the new hash table with "partial" entries of full entries - /// on the hash tables with higher size. - /// </remarks> - /// <param name="newTable">New hash table</param> - /// <param name="newEntrySize">Size of the data on the new hash table</param> - public void FillPartials(PartitionHashTable<T> newTable, int newEntrySize) - { - for (int i = 0; i < _buckets.Length; i++) - { - ref Bucket bucket = ref _buckets[i]; - ref Entry inlineEntry = ref bucket.InlineEntry; - - if (inlineEntry.Data != null) - { - if (!inlineEntry.IsPartial) - { - newTable.AddPartial(inlineEntry.Data, newEntrySize); - } - - if (bucket.MoreEntries != null) - { - foreach (Entry entry in bucket.MoreEntries) - { - if (entry.IsPartial) - { - continue; - } - - newTable.AddPartial(entry.Data, newEntrySize); - } - } - } - } - } - - /// <summary> - /// Tries to find an item on the table. - /// </summary> - /// <param name="dataHash">Hash of <paramref name="data"/></param> - /// <param name="data">Data to find</param> - /// <param name="item">Item associated with the data</param> - /// <returns>True if an item was found, false otherwise</returns> - private bool TryFindItem(uint dataHash, ReadOnlySpan<byte> data, out T item) - { - if (_count == 0) - { - item = default; - return false; - } - - ref Bucket bucket = ref GetBucketForHash(dataHash); - - if (bucket.InlineEntry.Data != null) - { - if (bucket.InlineEntry.Hash == dataHash && bucket.InlineEntry.GetData().SequenceEqual(data)) - { - item = bucket.InlineEntry.Item; - return true; - } - - if (bucket.MoreEntries != null) - { - foreach (Entry entry in bucket.MoreEntries) - { - if (entry.Hash == dataHash && entry.GetData().SequenceEqual(data)) - { - item = entry.Item; - return true; - } - } - } - } - - item = default; - return false; - } - - /// <summary> - /// Indicates the result of a hash table lookup. - /// </summary> - public enum SearchResult - { - /// <summary> - /// No entry was found, the search must continue on hash tables of lower size. - /// </summary> - NotFound, - - /// <summary> - /// A partial entry was found, the search must continue on hash tables of higher size. - /// </summary> - FoundPartial, - - /// <summary> - /// A full entry was found, the search was concluded and the item can be retrieved. - /// </summary> - FoundFull - } - - /// <summary> - /// Tries to find an item on the table. - /// </summary> - /// <param name="dataAccessor">Data accessor</param> - /// <param name="size">Size of the hash table data</param> - /// <param name="item">The item on the table, if found, otherwise unmodified</param> - /// <param name="data">The data on the table, if found, otherwise unmodified</param> - /// <returns>Table lookup result</returns> - public SearchResult TryFindItem(scoped ref SmartDataAccessor dataAccessor, int size, scoped ref T item, scoped ref byte[] data) - { - if (_count == 0) - { - return SearchResult.NotFound; - } - - ReadOnlySpan<byte> dataSpan = dataAccessor.GetSpanAndHash(size, out uint dataHash); - - if (dataSpan.Length != size) - { - return SearchResult.NotFound; - } - - ref Bucket bucket = ref GetBucketForHash(dataHash); - - if (bucket.InlineEntry.Data != null) - { - if (bucket.InlineEntry.Hash == dataHash && bucket.InlineEntry.GetData().SequenceEqual(dataSpan)) - { - item = bucket.InlineEntry.Item; - data = bucket.InlineEntry.Data; - return bucket.InlineEntry.IsPartial ? SearchResult.FoundPartial : SearchResult.FoundFull; - } - - if (bucket.MoreEntries != null) - { - foreach (Entry entry in bucket.MoreEntries) - { - if (entry.Hash == dataHash && entry.GetData().SequenceEqual(dataSpan)) - { - item = entry.Item; - data = entry.Data; - return entry.IsPartial ? SearchResult.FoundPartial : SearchResult.FoundFull; - } - } - } - } - - return SearchResult.NotFound; - } - - /// <summary> - /// Rebuilds the table for a new count. - /// </summary> - /// <param name="newPow2Count">New power of two count of the table</param> - private void Rebuild(int newPow2Count) - { - Bucket[] newBuckets = new Bucket[newPow2Count]; - - uint mask = (uint)newPow2Count - 1; - - for (int i = 0; i < _buckets.Length; i++) - { - ref Bucket bucket = ref _buckets[i]; - - if (bucket.InlineEntry.Data != null) - { - AddToBucket(ref newBuckets[(int)(bucket.InlineEntry.Hash & mask)], ref bucket.InlineEntry); - - if (bucket.MoreEntries != null) - { - foreach (Entry entry in bucket.MoreEntries) - { - Entry entryCopy = entry; - AddToBucket(ref newBuckets[(int)(entry.Hash & mask)], ref entryCopy); - } - } - } - } - - _buckets = newBuckets; - } - - /// <summary> - /// Gets the bucket for a given hash. - /// </summary> - /// <param name="hash">Data hash</param> - /// <returns>Bucket for the hash</returns> - private ref Bucket GetBucketForHash(uint hash) - { - int index = (int)(hash & (_buckets.Length - 1)); - - return ref _buckets[index]; - } - - /// <summary> - /// Gets a power of two count from a regular count. - /// </summary> - /// <param name="count">Count</param> - /// <returns>Power of two count</returns> - private static int GetPow2Count(int count) - { - // This returns the nearest power of two that is lower than count. - // This was done to optimize memory usage rather than performance. - return 1 << BitOperations.Log2((uint)count); - } - } -} diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionedHashTable.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionedHashTable.cs deleted file mode 100644 index e9a4f654..00000000 --- a/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionedHashTable.cs +++ /dev/null @@ -1,244 +0,0 @@ -using System; -using System.Collections.Generic; -using System.Diagnostics; - -namespace Ryujinx.Graphics.Gpu.Shader.HashTable -{ - /// <summary> - /// Partitioned hash table. - /// </summary> - /// <typeparam name="T"></typeparam> - public class PartitionedHashTable<T> - { - /// <summary> - /// Entry for a given data size. - /// </summary> - private readonly struct SizeEntry - { - /// <summary> - /// Size for the data that will be stored on the hash table on this entry. - /// </summary> - public int Size { get; } - - /// <summary> - /// Number of entries on the hash table. - /// </summary> - public int TableCount => _table.Count; - - private readonly PartitionHashTable<T> _table; - - /// <summary> - /// Creates an entry for a given size. - /// </summary> - /// <param name="size">Size of the data to be stored on this entry</param> - public SizeEntry(int size) - { - Size = size; - _table = new PartitionHashTable<T>(); - } - - /// <summary> - /// Gets an item for existing data, or adds a new one. - /// </summary> - /// <param name="data">Data associated with the item</param> - /// <param name="dataHash">Hash of <paramref name="data"/></param> - /// <param name="item">Item to be added</param> - /// <returns>Existing item, or <paramref name="item"/> if not present</returns> - public T GetOrAdd(byte[] data, uint dataHash, T item) - { - Debug.Assert(data.Length == Size); - return _table.GetOrAdd(data, dataHash, item); - } - - /// <summary> - /// Adds a new item. - /// </summary> - /// <param name="data">Data associated with the item</param> - /// <param name="dataHash">Hash of <paramref name="data"/></param> - /// <param name="item">Item to be added</param> - /// <returns>True if added, false otherwise</returns> - public bool Add(byte[] data, uint dataHash, T item) - { - Debug.Assert(data.Length == Size); - return _table.Add(data, dataHash, item); - } - - /// <summary> - /// Adds a partial entry. - /// </summary> - /// <param name="ownerData">Full entry data</param> - /// <param name="dataHash">Hash of the sub-region of the data that belongs to this entry</param> - /// <returns>True if added, false otherwise</returns> - public bool AddPartial(byte[] ownerData, uint dataHash) - { - return _table.AddPartial(ownerData, dataHash, Size); - } - - /// <summary> - /// Fills a new hash table with "partials" of existing full entries of higher size. - /// </summary> - /// <param name="newEntry">Entry with the new hash table</param> - public void FillPartials(SizeEntry newEntry) - { - Debug.Assert(newEntry.Size < Size); - _table.FillPartials(newEntry._table, newEntry.Size); - } - - /// <summary> - /// Tries to find an item on the hash table. - /// </summary> - /// <param name="dataAccessor">Data accessor</param> - /// <param name="item">The item on the table, if found, otherwise unmodified</param> - /// <param name="data">The data on the table, if found, otherwise unmodified</param> - /// <returns>Table lookup result</returns> - public PartitionHashTable<T>.SearchResult TryFindItem(scoped ref SmartDataAccessor dataAccessor, scoped ref T item, scoped ref byte[] data) - { - return _table.TryFindItem(ref dataAccessor, Size, ref item, ref data); - } - } - - private readonly List<SizeEntry> _sizeTable; - - /// <summary> - /// Creates a new partitioned hash table. - /// </summary> - public PartitionedHashTable() - { - _sizeTable = new List<SizeEntry>(); - } - - /// <summary> - /// Adds a new item to the table. - /// </summary> - /// <param name="data">Data</param> - /// <param name="item">Item associated with the data</param> - public void Add(byte[] data, T item) - { - GetOrAdd(data, item); - } - - /// <summary> - /// Gets an existing item from the table, or adds a new one if not present. - /// </summary> - /// <param name="data">Data</param> - /// <param name="item">Item associated with the data</param> - /// <returns>Existing item, or <paramref name="item"/> if not present</returns> - public T GetOrAdd(byte[] data, T item) - { - SizeEntry sizeEntry; - - int index = BinarySearch(_sizeTable, data.Length); - if (index < _sizeTable.Count && _sizeTable[index].Size == data.Length) - { - sizeEntry = _sizeTable[index]; - } - else - { - if (index < _sizeTable.Count && _sizeTable[index].Size < data.Length) - { - index++; - } - - sizeEntry = new SizeEntry(data.Length); - - _sizeTable.Insert(index, sizeEntry); - - for (int i = index + 1; i < _sizeTable.Count; i++) - { - _sizeTable[i].FillPartials(sizeEntry); - } - } - - HashState hashState = new HashState(); - hashState.Initialize(); - - for (int i = 0; i < index; i++) - { - ReadOnlySpan<byte> dataSlice = new ReadOnlySpan<byte>(data).Slice(0, _sizeTable[i].Size); - hashState.Continue(dataSlice); - _sizeTable[i].AddPartial(data, hashState.Finalize(dataSlice)); - } - - hashState.Continue(data); - return sizeEntry.GetOrAdd(data, hashState.Finalize(data), item); - } - - /// <summary> - /// Performs binary search on a list of hash tables, each one with a fixed data size. - /// </summary> - /// <param name="entries">List of hash tables</param> - /// <param name="size">Size to search for</param> - /// <returns>Index of the hash table with the given size, or nearest one otherwise</returns> - private static int BinarySearch(List<SizeEntry> entries, int size) - { - int left = 0; - int middle = 0; - int right = entries.Count - 1; - - while (left <= right) - { - middle = left + ((right - left) >> 1); - - SizeEntry entry = entries[middle]; - - if (size == entry.Size) - { - break; - } - - if (size < entry.Size) - { - right = middle - 1; - } - else - { - left = middle + 1; - } - } - - return middle; - } - - /// <summary> - /// Tries to find an item on the table. - /// </summary> - /// <param name="dataAccessor">Data accessor</param> - /// <param name="item">Item, if found</param> - /// <param name="data">Data, if found</param> - /// <returns>True if the item was found on the table, false otherwise</returns> - public bool TryFindItem(IDataAccessor dataAccessor, out T item, out byte[] data) - { - SmartDataAccessor sda = new SmartDataAccessor(dataAccessor); - - item = default; - data = null; - - int left = 0; - int right = _sizeTable.Count; - - while (left != right) - { - int index = left + ((right - left) >> 1); - - PartitionHashTable<T>.SearchResult result = _sizeTable[index].TryFindItem(ref sda, ref item, ref data); - - if (result == PartitionHashTable<T>.SearchResult.FoundFull) - { - return true; - } - - if (result == PartitionHashTable<T>.SearchResult.NotFound) - { - right = index; - } - else /* if (result == PartitionHashTable<T>.SearchResult.FoundPartial) */ - { - left = index + 1; - } - } - - data = null; - return false; - } - } -} diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/SmartDataAccessor.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/SmartDataAccessor.cs deleted file mode 100644 index 0632add6..00000000 --- a/Ryujinx.Graphics.Gpu/Shader/HashTable/SmartDataAccessor.cs +++ /dev/null @@ -1,96 +0,0 @@ -using System; -using System.Collections.Generic; - -namespace Ryujinx.Graphics.Gpu.Shader.HashTable -{ - /// <summary> - /// Smart data accessor that can cache data and hashes to avoid reading and re-hashing the same memory regions. - /// </summary> - ref struct SmartDataAccessor - { - private readonly IDataAccessor _dataAccessor; - private ReadOnlySpan<byte> _data; - private readonly SortedList<int, HashState> _cachedHashes; - - /// <summary> - /// Creates a new smart data accessor. - /// </summary> - /// <param name="dataAccessor">Data accessor</param> - public SmartDataAccessor(IDataAccessor dataAccessor) - { - _dataAccessor = dataAccessor; - _data = ReadOnlySpan<byte>.Empty; - _cachedHashes = new SortedList<int, HashState>(); - } - - /// <summary> - /// Get a spans of a given size. - /// </summary> - /// <remarks> - /// The actual length of the span returned depends on the <see cref="IDataAccessor"/> - /// and might be less than requested. - /// </remarks> - /// <param name="length">Size in bytes</param> - /// <returns>Span with the requested size</returns> - public ReadOnlySpan<byte> GetSpan(int length) - { - if (_data.Length < length) - { - _data = _dataAccessor.GetSpan(0, length); - } - else if (_data.Length > length) - { - return _data.Slice(0, length); - } - - return _data; - } - - /// <summary> - /// Gets a span of the requested size, and a hash of its data. - /// </summary> - /// <param name="length">Length of the span</param> - /// <param name="hash">Hash of the span data</param> - /// <returns>Span of data</returns> - public ReadOnlySpan<byte> GetSpanAndHash(int length, out uint hash) - { - ReadOnlySpan<byte> data = GetSpan(length); - hash = data.Length == length ? CalcHashCached(data) : 0; - return data; - } - - /// <summary> - /// Calculates the hash for a requested span. - /// This will try to use a cached hash if the data was already accessed before, to avoid re-hashing. - /// </summary> - /// <param name="data">Data to be hashed</param> - /// <returns>Hash of the data</returns> - private uint CalcHashCached(ReadOnlySpan<byte> data) - { - HashState state = default; - bool found = false; - - for (int i = _cachedHashes.Count - 1; i >= 0; i--) - { - int cachedHashSize = _cachedHashes.Keys[i]; - - if (cachedHashSize < data.Length) - { - state = _cachedHashes.Values[i]; - found = true; - break; - } - } - - if (!found) - { - state = new HashState(); - state.Initialize(); - } - - state.Continue(data); - _cachedHashes[data.Length & ~7] = state; - return state.Finalize(data); - } - } -} |
