Allow "reinterpretation" of framebuffer/zeta formats (#418)

* (Re)Implement format reinterpretation, other changes

* Implement writeback to guest memory, some refactoring

* More refactoring, implement reinterpretation the old way again

* Clean up

* Some fixes on M2MF (old Dma engine), added partial support for P2MF, fix conditional ssy, add Z24S8 zeta format, other fixes

* nit: Formatting

* Address PR feedback

2 files changed, 33 insertions, 271 deletions

diff --git a/Ryujinx.Graphics/Memory/NvGpuBufferType.cs b/Ryujinx.Graphics/Memory/NvGpuBufferType.cs
deleted file mode 100644
index 6f0d2571..00000000
--- a/Ryujinx.Graphics/Memory/NvGpuBufferType.cs
+++ /dev/null
@@ -1,11 +0,0 @@
-namespace Ryujinx.Graphics.Memory
-{
-    public enum NvGpuBufferType
-    {
-        Index,
-        Vertex,
-        Texture,
-        ConstBuffer,
-        Count
-    }
-}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Memory/NvGpuVmmCache.cs b/Ryujinx.Graphics/Memory/NvGpuVmmCache.cs
index 56979e1f..f1c16a36 100644
--- a/Ryujinx.Graphics/Memory/NvGpuVmmCache.cs
+++ b/Ryujinx.Graphics/Memory/NvGpuVmmCache.cs
@@ -1,309 +1,82 @@
 using ChocolArm64.Memory;
 using System;
-using System.Collections.Generic;
 
 namespace Ryujinx.Graphics.Memory
 {
     class NvGpuVmmCache
     {
-        private const long RamSize = 4L * 1024 * 1024 * 1024;
-
-        private const int MaxCpCount     = 10000;
-        private const int MaxCpTimeDelta = 60000;
-
-        private class CachedPage
-        {
-            private struct Range
-            {
-                public long Start;
-                public long End;
-
-                public Range(long Start, long End)
-                {
-                    this.Start = Start;
-                    this.End = End;
-                }
-            }
-
-            private List<Range>[] Regions;
-
-            private HashSet<long> ResidencyKeys;
-
-            public LinkedListNode<long> Node { get; set; }
-
-            public int Timestamp { get; private set; }
-
-            public CachedPage()
-            {
-                Regions = new List<Range>[(int)NvGpuBufferType.Count];
-
-                for (int Index = 0; Index < Regions.Length; Index++)
-                {
-                    Regions[Index] = new List<Range>();
-                }
-
-                ResidencyKeys = new HashSet<long>();
-            }
-
-            public void AddResidency(long Key)
-            {
-                ResidencyKeys.Add(Key);
-            }
-
-            public void RemoveResidency(HashSet<long>[] Residency, long PageSize)
-            {
-                for (int i = 0; i < (int)NvGpuBufferType.Count; i++)
-                {
-                    foreach (Range Region in Regions[i])
-                    {
-                        foreach (long Key in ResidencyKeys)
-                        {
-                            Residency[Region.Start / PageSize].Remove(Key);
-                        }
-                    }
-                }
-            }
-
-            public bool AddRange(long Start, long End, NvGpuBufferType BufferType)
-            {
-                List<Range> BtRegions = Regions[(int)BufferType];
-
-                for (int Index = 0; Index < BtRegions.Count; Index++)
-                {
-                    Range Rg = BtRegions[Index];
-
-                    if (Start >= Rg.Start && End <= Rg.End)
-                    {
-                        return false;
-                    }
-
-                    if (Start <= Rg.End && Rg.Start <= End)
-                    {
-                        long MinStart = Math.Min(Rg.Start, Start);
-                        long MaxEnd   = Math.Max(Rg.End,   End);
-
-                        BtRegions[Index] = new Range(MinStart, MaxEnd);
-
-                        Timestamp = Environment.TickCount;
-
-                        return true;
-                    }
-                }
-
-                BtRegions.Add(new Range(Start, End));
-
-                Timestamp = Environment.TickCount;
-
-                return true;
-            }
-
-            public int GetTotalCount()
-            {
-                int Count = 0;
-
-                for (int Index = 0; Index < Regions.Length; Index++)
-                {
-                    Count += Regions[Index].Count;
-                }
-
-                return Count;
-            }
-        }
-
-        private Dictionary<long, CachedPage> Cache;
-
-        private LinkedList<long> SortedCache;
-
-        private HashSet<long>[] Residency;
-
-        private long ResidencyPageSize;
-
-        private int CpCount;
+        private ValueRangeSet<int> CachedRanges;
 
         public NvGpuVmmCache()
         {
-            Cache = new Dictionary<long, CachedPage>();
-
-            SortedCache = new LinkedList<long>();
+            CachedRanges = new ValueRangeSet<int>();
         }
 
         public bool IsRegionModified(AMemory Memory, NvGpuBufferType BufferType, long PA, long Size)
         {
             (bool[] Modified, long ModifiedCount) = Memory.IsRegionModified(PA, Size);
 
-            PA = Memory.GetPhysicalAddress(PA);
-
-            ClearCachedPagesIfNeeded();
-
-            long PageSize = AMemory.PageSize;
-
-            EnsureResidencyInitialized(PageSize);
-
-            bool HasResidents = AddResidency(PA, Size);
-
-            if (!HasResidents && ModifiedCount == 0)
-            {
-                return false;
-            }
-
-            long Mask = PageSize - 1;
-
-            long ResidencyKey = PA;
-
-            long PAEnd = PA + Size;
-
-            bool RegMod = false;
-
+            //Remove all modified ranges.
             int Index = 0;
 
-            while (PA < PAEnd)
-            {
-                long Key = PA & ~AMemory.PageMask;
-
-                long PAPgEnd = Math.Min((PA + AMemory.PageSize) & ~AMemory.PageMask, PAEnd);
-
-                bool IsCached = Cache.TryGetValue(Key, out CachedPage Cp);
-
-                if (IsCached)
-                {
-                    CpCount -= Cp.GetTotalCount();
-
-                    SortedCache.Remove(Cp.Node);
-                }
-                else
-                {
-                    Cp = new CachedPage();
-
-                    Cache.Add(Key, Cp);
-                }
+            long Position = PA & ~NvGpuVmm.PageMask;
 
-                if (Modified[Index++] && IsCached)
+            while (ModifiedCount > 0)
+            {
+                if (Modified[Index++])
                 {
-                    Cp = new CachedPage();
+                    CachedRanges.Remove(new ValueRange<int>(Position, Position + NvGpuVmm.PageSize));
 
-                    Cache[Key] = Cp;
+                    ModifiedCount--;
                 }
 
-                Cp.AddResidency(ResidencyKey);
-
-                Cp.Node = SortedCache.AddLast(Key);
-
-                RegMod |= Cp.AddRange(PA, PAPgEnd, BufferType);
-
-                CpCount += Cp.GetTotalCount();
-
-                PA = PAPgEnd;
+                Position += NvGpuVmm.PageSize;
             }
 
-            return RegMod;
-        }
+            //Mask has the bit set for the current resource type.
+            //If the region is not yet present on the list, then a new ValueRange
+            //is directly added with the current resource type as the only bit set.
+            //Otherwise, it just sets the bit for this new resource type on the current mask.
+            int Mask = 1 << (int)BufferType;
 
-        private bool AddResidency(long PA, long Size)
-        {
-            long PageSize = ResidencyPageSize;
+            ValueRange<int> NewCached = new ValueRange<int>(PA, PA + Size);
 
-            long Mask = PageSize - 1;
+            ValueRange<int>[] Ranges = CachedRanges.GetAllIntersections(NewCached);
 
-            long Key = PA;
+            long LastEnd = NewCached.Start;
 
-            bool ResidentFound = false;
+            long Coverage = 0;
 
-            for (long Cursor = PA & ~Mask; Cursor < ((PA + Size + PageSize - 1) & ~Mask); Cursor += PageSize)
+            for (Index = 0; Index < Ranges.Length; Index++)
             {
-                long PageIndex = Cursor / PageSize;
-
-                Residency[PageIndex].Add(Key);
+                ValueRange<int> Current = Ranges[Index];
 
-                if (Residency[PageIndex].Count > 1)
-                {
-                    ResidentFound = true;
-                }
-            }
-
-            return ResidentFound;
-        }
-
-        private void EnsureResidencyInitialized(long PageSize)
-        {
-            if (Residency == null)
-            {
-                Residency = new HashSet<long>[RamSize / PageSize];
+                long RgStart = Math.Max(Current.Start, NewCached.Start);
+                long RgEnd   = Math.Min(Current.End,   NewCached.End);
 
-                for (int i = 0; i < Residency.Length; i++)
+                if ((Current.Value & Mask) == 0)
                 {
-                    Residency[i] = new HashSet<long>();
+                    CachedRanges.Add(new ValueRange<int>(RgStart, RgEnd, Current.Value | Mask));
                 }
-
-                ResidencyPageSize = PageSize;
-            }
-            else
-            {
-                if (ResidencyPageSize != PageSize)
+                else
                 {
-                    throw new InvalidOperationException("Tried to change residency page size");
+                    Coverage += RgEnd - RgStart;
                 }
-            }
-        }
-
-        private void ClearCachedPagesIfNeeded()
-        {
-            if (CpCount <= MaxCpCount)
-            {
-                return;
-            }
-
-            int Timestamp = Environment.TickCount;
 
-            int TimeDelta;
-
-            do
-            {
-                if (!TryPopOldestCachedPageKey(Timestamp, out long Key))
+                if (RgStart > LastEnd)
                 {
-                    break;
+                    CachedRanges.Add(new ValueRange<int>(LastEnd, RgStart, Mask));
                 }
 
-                CachedPage Cp = Cache[Key];
-
-                Cp.RemoveResidency(Residency, ResidencyPageSize);
-
-                Cache.Remove(Key);
-
-                CpCount -= Cp.GetTotalCount();
-
-                TimeDelta = RingDelta(Cp.Timestamp, Timestamp);
+                LastEnd = RgEnd;
             }
-            while (CpCount > (MaxCpCount >> 1) || (uint)TimeDelta > (uint)MaxCpTimeDelta);
-        }
-
-        private bool TryPopOldestCachedPageKey(int Timestamp, out long Key)
-        {
-            LinkedListNode<long> Node = SortedCache.First;
 
-            if (Node == null)
+            if (LastEnd < NewCached.End)
             {
-                Key = 0;
-
-                return false;
+                CachedRanges.Add(new ValueRange<int>(LastEnd, NewCached.End, Mask));
             }
 
-            SortedCache.Remove(Node);
-
-            Key = Node.Value;
-
-            return true;
-        }
-
-        private int RingDelta(int Old, int New)
-        {
-            if ((uint)New < (uint)Old)
-            {
-                return New + (~Old + 1);
-            }
-            else
-            {
-                return New - Old;
-            }
+            return Coverage != Size;
         }
     }
 }
\ No newline at end of file