From 43ebd7a9bbba0c1290a9e98b9224f0752627c400 Mon Sep 17 00:00:00 2001 From: gdkchan Date: Sun, 10 Apr 2022 10:49:44 -0300 Subject: New shader cache implementation (#3194) * New shader cache implementation * Remove some debug code * Take transform feedback varying count into account * Create shader cache directory if it does not exist + fragment output map related fixes * Remove debug code * Only check texture descriptors if the constant buffer is bound * Also check CPU VA on GetSpanMapped * Remove more unused code and move cache related code * XML docs + remove more unused methods * Better codegen for TransformFeedbackDescriptor.AsSpan * Support migration from old cache format, remove more unused code Shader cache rebuild now also rewrites the shared toc and data files * Fix migration error with BRX shaders * Add a limit to the async translation queue Avoid async translation threads not being able to keep up and the queue growing very large * Re-create specialization state on recompile This might be required if a new version of the shader translator requires more or less state, or if there is a bug related to the GPU state access * Make shader cache more error resilient * Add some missing XML docs and move GpuAccessor docs to the interface/use inheritdoc * Address early PR feedback * Fix rebase * Remove IRenderer.CompileShader and IShader interface, replace with new ShaderSource struct passed to CreateProgram directly * Handle some missing exceptions * Make shader cache purge delete both old and new shader caches * Register textures on new specialization state * Translate and compile shaders in forward order (eliminates diffs due to different binding numbers) * Limit in-flight shader compilation to the maximum number of compilation threads * Replace ParallelDiskCacheLoader state changed event with a callback function * Better handling for invalid constant buffer 1 data length * Do not create the old cache directory structure if the old cache does not exist * Constant buffer use should be per-stage. This change will invalidate existing new caches (file format version was incremented) * Replace rectangle texture with just coordinate normalization * Skip incompatible shaders that are missing texture information, instead of crashing This is required if we, for example, support new texture instruction to the shader translator, and then they allow access to textures that were not accessed before. In this scenario, the old cache entry is no longer usable * Fix coordinates normalization on cubemap textures * Check if title ID is null before combining shader cache path * More robust constant buffer address validation on spec state * More robust constant buffer address validation on spec state (2) * Regenerate shader cache with one stream, rather than one per shader. * Only create shader cache directory during initialization * Logging improvements * Proper shader program disposal * PR feedback, and add a comment on serialized structs * XML docs for RegisterTexture Co-authored-by: riperiperi --- Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs | 113 ++++++ .../Shader/HashTable/IDataAccessor.cs | 27 ++ .../Shader/HashTable/PartitionHashTable.cs | 452 +++++++++++++++++++++ .../Shader/HashTable/PartitionedHashTable.cs | 244 +++++++++++ .../Shader/HashTable/SmartDataAccessor.cs | 96 +++++ 5 files changed, 932 insertions(+) create mode 100644 Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs create mode 100644 Ryujinx.Graphics.Gpu/Shader/HashTable/IDataAccessor.cs create mode 100644 Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs create mode 100644 Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionedHashTable.cs create mode 100644 Ryujinx.Graphics.Gpu/Shader/HashTable/SmartDataAccessor.cs (limited to 'Ryujinx.Graphics.Gpu/Shader/HashTable') diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs new file mode 100644 index 00000000..584eefdc --- /dev/null +++ b/Ryujinx.Graphics.Gpu/Shader/HashTable/HashState.cs @@ -0,0 +1,113 @@ +using System; +using System.Runtime.InteropServices; + +namespace Ryujinx.Graphics.Gpu.Shader.HashTable +{ + /// + /// State of a hash calculation. + /// + 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; + + /// + /// One shot hash calculation for a given data. + /// + /// Data to be hashed + /// Hash of the given data + public static uint CalcHash(ReadOnlySpan data) + { + HashState state = new HashState(); + + state.Initialize(); + state.Continue(data); + return state.Finalize(data); + } + + /// + /// Initializes the hash state. + /// + public void Initialize() + { + _hash = 23; + } + + /// + /// Calculates the hash of the given data. + /// + /// + /// The full data must be passed on . + /// If this is not the first time the method is called, then 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. + /// + /// Data to be hashed + public void Continue(ReadOnlySpan data) + { + ulong h = _hash; + + ReadOnlySpan dataAsUlong = MemoryMarshal.Cast(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; + } + + /// + /// Performs the hash finalization step, and returns the calculated hash. + /// + /// + /// The full data must be passed on . + /// must start with the data passed on the last call to . + /// No internal state is changed, so one can still continue hashing data with + /// after calling this method. + /// + /// Data to be hashed + /// Hash of all the data hashed with this + public uint Finalize(ReadOnlySpan 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)); + } + + /// + /// Hash mix function. + /// + /// Hash to mix + /// Mixed hash + 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 new file mode 100644 index 00000000..c982cd9f --- /dev/null +++ b/Ryujinx.Graphics.Gpu/Shader/HashTable/IDataAccessor.cs @@ -0,0 +1,27 @@ +using System; + +namespace Ryujinx.Graphics.Gpu.Shader.HashTable +{ + /// + /// Data accessor, used by to access data of unknown length. + /// + /// + /// 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. + /// + public interface IDataAccessor + { + /// + /// Gets a span of shader code at the specified offset, with at most the specified size. + /// + /// + /// This might return a span smaller than the requested if there's + /// no more code available. + /// + /// Offset in shader code + /// Size in bytes + /// Shader code span + ReadOnlySpan GetSpan(int offset, int length); + } +} diff --git a/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs new file mode 100644 index 00000000..6a563c16 --- /dev/null +++ b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionHashTable.cs @@ -0,0 +1,452 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Numerics; + +namespace Ryujinx.Graphics.Gpu.Shader.HashTable +{ + /// + /// Partitioned hash table. + /// + /// Hash table entry type + class PartitionHashTable + { + /// + /// Hash table entry. + /// + private struct Entry + { + /// + /// Hash bytes of . + /// + public readonly uint Hash; + + /// + /// If this entry is only a sub-region of , this indicates the size in bytes + /// of that region. Otherwise, it should be zero. + /// + public readonly int OwnSize; + + /// + /// Data used to compute the hash for this entry. + /// + /// + /// 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 in this case. + /// + public readonly byte[] Data; + + /// + /// Item associated with this entry. + /// + public T Item; + + /// + /// Indicates if the entry is partial, which means that this entry is only for a sub-region of the data. + /// + /// + /// 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. + /// + public bool IsPartial => OwnSize != 0; + + /// + /// Creates a new partial hash table entry. + /// + /// Hash of the data + /// Full data + /// Size of the sub-region of data that belongs to this entry + public Entry(uint hash, byte[] ownerData, int ownSize) + { + Hash = hash; + OwnSize = ownSize; + Data = ownerData; + Item = default; + } + + /// + /// Creates a new full hash table entry. + /// + /// Hash of the data + /// Data + /// Item associated with this entry + public Entry(uint hash, byte[] data, T item) + { + Hash = hash; + OwnSize = 0; + Data = data; + Item = item; + } + + /// + /// Gets the data for this entry, either full or partial. + /// + /// Data sub-region + public ReadOnlySpan GetData() + { + if (OwnSize != 0) + { + return new ReadOnlySpan(Data).Slice(0, OwnSize); + } + + return Data; + } + } + + /// + /// Hash table bucket. + /// + private struct Bucket + { + /// + /// Inline entry, to avoid allocations for the common single entry case. + /// + public Entry InlineEntry; + + /// + /// List of additional entries for the not-so-common multiple entries case. + /// + public List MoreEntries; + } + + private Bucket[] _buckets; + private int _count; + + /// + /// Total amount of entries on the hash table. + /// + public int Count => _count; + + /// + /// Creates a new instance of the partitioned hash table. + /// + public PartitionHashTable() + { + _buckets = Array.Empty(); + } + + /// + /// Gets an item on the table, or adds a new one if not present. + /// + /// Data + /// Hash of the data + /// Item to be added if not found + /// Existing item if found, or if not found + 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; + } + + /// + /// Adds an item to the hash table. + /// + /// Data + /// Hash of the data + /// Item to be added + /// True if the item was added, false due to an item associated with the data already being on the table + 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; + } + + /// + /// Adds a partial entry to the hash table. + /// + /// Full data + /// Size of the sub-region of used by the partial entry + /// True if added, false otherwise + public bool AddPartial(byte[] ownerData, int ownSize) + { + ReadOnlySpan data = new ReadOnlySpan(ownerData).Slice(0, ownSize); + + return AddPartial(ownerData, HashState.CalcHash(data), ownSize); + } + + /// + /// Adds a partial entry to the hash table. + /// + /// Full data + /// Hash of the data sub-region + /// Size of the sub-region of used by the partial entry + /// True if added, false otherwise + public bool AddPartial(byte[] ownerData, uint dataHash, int ownSize) + { + ReadOnlySpan data = new ReadOnlySpan(ownerData).Slice(0, ownSize); + + if (TryFindItem(dataHash, data, out _)) + { + return false; + } + + Entry entry = new Entry(dataHash, ownerData, ownSize); + + AddToBucket(dataHash, ref entry); + + return true; + } + + /// + /// Adds entry with a given hash to the table. + /// + /// Hash of the entry + /// Entry + 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); + } + + /// + /// Adds an entry to a bucket. + /// + /// Bucket to add the entry into + /// Entry to be added + private void AddToBucket(ref Bucket bucket, ref Entry entry) + { + if (bucket.InlineEntry.Data == null) + { + bucket.InlineEntry = entry; + } + else + { + (bucket.MoreEntries ??= new List()).Add(entry); + } + } + + /// + /// Creates partial entries on a new hash table for all existing full entries. + /// + /// + /// 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. + /// + /// New hash table + /// Size of the data on the new hash table + public void FillPartials(PartitionHashTable 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); + } + } + } + } + } + + /// + /// Tries to find an item on the table. + /// + /// Hash of + /// Data to find + /// Item associated with the data + /// True if an item was found, false otherwise + private bool TryFindItem(uint dataHash, ReadOnlySpan 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; + } + + /// + /// Indicates the result of a hash table lookup. + /// + public enum SearchResult + { + /// + /// No entry was found, the search must continue on hash tables of lower size. + /// + NotFound, + + /// + /// A partial entry was found, the search must continue on hash tables of higher size. + /// + FoundPartial, + + /// + /// A full entry was found, the search was concluded and the item can be retrieved. + /// + FoundFull + } + + /// + /// Tries to find an item on the table. + /// + /// Data accessor + /// Size of the hash table data + /// The item on the table, if found, otherwise unmodified + /// The data on the table, if found, otherwise unmodified + /// Table lookup result + public SearchResult TryFindItem(ref SmartDataAccessor dataAccessor, int size, ref T item, ref byte[] data) + { + if (_count == 0) + { + return SearchResult.NotFound; + } + + ReadOnlySpan 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; + } + + /// + /// Rebuilds the table for a new count. + /// + /// New power of two count of the table + 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; + } + + /// + /// Gets the bucket for a given hash. + /// + /// Data hash + /// Bucket for the hash + private ref Bucket GetBucketForHash(uint hash) + { + int index = (int)(hash & (_buckets.Length - 1)); + + return ref _buckets[index]; + } + + /// + /// Gets a power of two count from a regular count. + /// + /// Count + /// Power of two count + 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 new file mode 100644 index 00000000..4c9cc4d4 --- /dev/null +++ b/Ryujinx.Graphics.Gpu/Shader/HashTable/PartitionedHashTable.cs @@ -0,0 +1,244 @@ +using System; +using System.Collections.Generic; +using System.Diagnostics; + +namespace Ryujinx.Graphics.Gpu.Shader.HashTable +{ + /// + /// Partitioned hash table. + /// + /// + public class PartitionedHashTable + { + /// + /// Entry for a given data size. + /// + private struct SizeEntry + { + /// + /// Size for the data that will be stored on the hash table on this entry. + /// + public int Size { get; } + + /// + /// Number of entries on the hash table. + /// + public int TableCount => _table.Count; + + private readonly PartitionHashTable _table; + + /// + /// Creates an entry for a given size. + /// + /// Size of the data to be stored on this entry + public SizeEntry(int size) + { + Size = size; + _table = new PartitionHashTable(); + } + + /// + /// Gets an item for existing data, or adds a new one. + /// + /// Data associated with the item + /// Hash of + /// Item to be added + /// Existing item, or if not present + public T GetOrAdd(byte[] data, uint dataHash, T item) + { + Debug.Assert(data.Length == Size); + return _table.GetOrAdd(data, dataHash, item); + } + + /// + /// Adds a new item. + /// + /// Data associated with the item + /// Hash of + /// Item to be added + /// True if added, false otherwise + public bool Add(byte[] data, uint dataHash, T item) + { + Debug.Assert(data.Length == Size); + return _table.Add(data, dataHash, item); + } + + /// + /// Adds a partial entry. + /// + /// Full entry data + /// Hash of the sub-region of the data that belongs to this entry + /// True if added, false otherwise + public bool AddPartial(byte[] ownerData, uint dataHash) + { + return _table.AddPartial(ownerData, dataHash, Size); + } + + /// + /// Fills a new hash table with "partials" of existing full entries of higher size. + /// + /// Entry with the new hash table + public void FillPartials(SizeEntry newEntry) + { + Debug.Assert(newEntry.Size < Size); + _table.FillPartials(newEntry._table, newEntry.Size); + } + + /// + /// Tries to find an item on the hash table. + /// + /// Data accessor + /// The item on the table, if found, otherwise unmodified + /// The data on the table, if found, otherwise unmodified + /// Table lookup result + public PartitionHashTable.SearchResult TryFindItem(ref SmartDataAccessor dataAccessor, ref T item, ref byte[] data) + { + return _table.TryFindItem(ref dataAccessor, Size, ref item, ref data); + } + } + + private readonly List _sizeTable; + + /// + /// Creates a new partitioned hash table. + /// + public PartitionedHashTable() + { + _sizeTable = new List(); + } + + /// + /// Adds a new item to the table. + /// + /// Data + /// Item associated with the data + public void Add(byte[] data, T item) + { + GetOrAdd(data, item); + } + + /// + /// Gets an existing item from the table, or adds a new one if not present. + /// + /// Data + /// Item associated with the data + /// Existing item, or if not present + 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 dataSlice = new ReadOnlySpan(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); + } + + /// + /// Performs binary search on a list of hash tables, each one with a fixed data size. + /// + /// List of hash tables + /// Size to search for + /// Index of the hash table with the given size, or nearest one otherwise + private static int BinarySearch(List 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; + } + + /// + /// Tries to find an item on the table. + /// + /// Data accessor + /// Item, if found + /// Data, if found + /// True if the item was found on the table, false otherwise + 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.SearchResult result = _sizeTable[index].TryFindItem(ref sda, ref item, ref data); + + if (result == PartitionHashTable.SearchResult.FoundFull) + { + return true; + } + + if (result == PartitionHashTable.SearchResult.NotFound) + { + right = index; + } + else /* if (result == PartitionHashTable.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 new file mode 100644 index 00000000..0632add6 --- /dev/null +++ b/Ryujinx.Graphics.Gpu/Shader/HashTable/SmartDataAccessor.cs @@ -0,0 +1,96 @@ +using System; +using System.Collections.Generic; + +namespace Ryujinx.Graphics.Gpu.Shader.HashTable +{ + /// + /// Smart data accessor that can cache data and hashes to avoid reading and re-hashing the same memory regions. + /// + ref struct SmartDataAccessor + { + private readonly IDataAccessor _dataAccessor; + private ReadOnlySpan _data; + private readonly SortedList _cachedHashes; + + /// + /// Creates a new smart data accessor. + /// + /// Data accessor + public SmartDataAccessor(IDataAccessor dataAccessor) + { + _dataAccessor = dataAccessor; + _data = ReadOnlySpan.Empty; + _cachedHashes = new SortedList(); + } + + /// + /// Get a spans of a given size. + /// + /// + /// The actual length of the span returned depends on the + /// and might be less than requested. + /// + /// Size in bytes + /// Span with the requested size + public ReadOnlySpan GetSpan(int length) + { + if (_data.Length < length) + { + _data = _dataAccessor.GetSpan(0, length); + } + else if (_data.Length > length) + { + return _data.Slice(0, length); + } + + return _data; + } + + /// + /// Gets a span of the requested size, and a hash of its data. + /// + /// Length of the span + /// Hash of the span data + /// Span of data + public ReadOnlySpan GetSpanAndHash(int length, out uint hash) + { + ReadOnlySpan data = GetSpan(length); + hash = data.Length == length ? CalcHashCached(data) : 0; + return data; + } + + /// + /// 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. + /// + /// Data to be hashed + /// Hash of the data + private uint CalcHashCached(ReadOnlySpan 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); + } + } +} -- cgit v1.2.3