From 3d98e1361b2f1c3993aa7f1e9b1ac49fc5b6e512 Mon Sep 17 00:00:00 2001
From: riperiperi <rhy3756547@hotmail.com>
Date: Sat, 29 Oct 2022 23:07:37 +0100
Subject: GPU: Use a bitmap to track buffer modified flags. (#3775)
* Initial implementation
* Some improvements.
* Fix incorrect cast
* Performance improvement and improved correctness
* Add very fast path when all handles are checked.
* Slightly faster
* Add comment
* De-virtualize region handle
All region handles are now bitmap backed.
* Remove non-bitmap tracking
* Remove unused methods
* Add docs, remove unused methods
* Address Feedback
* Rename file
---
Ryujinx.Memory/Tracking/BitMap.cs | 199 ++++++++++++++++++++++++++++++++++++++
1 file changed, 199 insertions(+)
create mode 100644 Ryujinx.Memory/Tracking/BitMap.cs
(limited to 'Ryujinx.Memory/Tracking/BitMap.cs')
diff --git a/Ryujinx.Memory/Tracking/BitMap.cs b/Ryujinx.Memory/Tracking/BitMap.cs
new file mode 100644
index 00000000..d3f15994
--- /dev/null
+++ b/Ryujinx.Memory/Tracking/BitMap.cs
@@ -0,0 +1,199 @@
+using System.Runtime.CompilerServices;
+
+namespace Ryujinx.Memory.Tracking
+{
+ /// <summary>
+ /// A bitmap that can check or set large ranges of true/false values at once.
+ /// </summary>
+ struct BitMap
+ {
+ public const int IntSize = 64;
+
+ private const int IntShift = 6;
+ private const int IntMask = IntSize - 1;
+
+ /// <summary>
+ /// Masks representing the bitmap. Least significant bit first, 64-bits per mask.
+ /// </summary>
+ public readonly long[] Masks;
+
+ /// <summary>
+ /// Create a new bitmap.
+ /// </summary>
+ /// <param name="count">The number of bits to reserve</param>
+ public BitMap(int count)
+ {
+ Masks = new long[(count + IntMask) / IntSize];
+ }
+
+ /// <summary>
+ /// Check if any bit in the bitmap is set.
+ /// </summary>
+ /// <returns>True if any bits are set, false otherwise</returns>
+ public bool AnySet()
+ {
+ for (int i = 0; i < Masks.Length; i++)
+ {
+ if (Masks[i] != 0)
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ /// <summary>
+ /// Check if a bit in the bitmap is set.
+ /// </summary>
+ /// <param name="bit">The bit index to check</param>
+ /// <returns>True if the bit is set, false otherwise</returns>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ public bool IsSet(int bit)
+ {
+ int wordIndex = bit >> IntShift;
+ int wordBit = bit & IntMask;
+
+ long wordMask = 1L << wordBit;
+
+ return (Masks[wordIndex] & wordMask) != 0;
+ }
+
+ /// <summary>
+ /// Check if any bit in a range of bits in the bitmap are set. (inclusive)
+ /// </summary>
+ /// <param name="start">The first bit index to check</param>
+ /// <param name="end">The last bit index to check</param>
+ /// <returns>True if a bit is set, false otherwise</returns>
+ public bool IsSet(int start, int end)
+ {
+ if (start == end)
+ {
+ return IsSet(start);
+ }
+
+ int startIndex = start >> IntShift;
+ int startBit = start & IntMask;
+ long startMask = -1L << startBit;
+
+ int endIndex = end >> IntShift;
+ int endBit = end & IntMask;
+ long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
+
+ if (startIndex == endIndex)
+ {
+ return (Masks[startIndex] & startMask & endMask) != 0;
+ }
+
+ if ((Masks[startIndex] & startMask) != 0)
+ {
+ return true;
+ }
+
+ for (int i = startIndex + 1; i < endIndex; i++)
+ {
+ if (Masks[i] != 0)
+ {
+ return true;
+ }
+ }
+
+ if ((Masks[endIndex] & endMask) != 0)
+ {
+ return true;
+ }
+
+ return false;
+ }
+
+ /// <summary>
+ /// Set a bit at a specific index to 1.
+ /// </summary>
+ /// <param name="bit">The bit index to set</param>
+ /// <returns>True if the bit is set, false if it was already set</returns>
+ public bool Set(int bit)
+ {
+ int wordIndex = bit >> IntShift;
+ int wordBit = bit & IntMask;
+
+ long wordMask = 1L << wordBit;
+
+ if ((Masks[wordIndex] & wordMask) != 0)
+ {
+ return false;
+ }
+
+ Masks[wordIndex] |= wordMask;
+
+ return true;
+ }
+
+ /// <summary>
+ /// Set a range of bits in the bitmap to 1.
+ /// </summary>
+ /// <param name="start">The first bit index to set</param>
+ /// <param name="end">The last bit index to set</param>
+ public void SetRange(int start, int end)
+ {
+ if (start == end)
+ {
+ Set(start);
+ return;
+ }
+
+ int startIndex = start >> IntShift;
+ int startBit = start & IntMask;
+ long startMask = -1L << startBit;
+
+ int endIndex = end >> IntShift;
+ int endBit = end & IntMask;
+ long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
+
+ if (startIndex == endIndex)
+ {
+ Masks[startIndex] |= startMask & endMask;
+ }
+ else
+ {
+ Masks[startIndex] |= startMask;
+
+ for (int i = startIndex + 1; i < endIndex; i++)
+ {
+ Masks[i] |= -1;
+ }
+
+ Masks[endIndex] |= endMask;
+ }
+ }
+
+ /// <summary>
+ /// Clear a bit at a specific index to 0.
+ /// </summary>
+ /// <param name="bit">The bit index to clear</param>
+ /// <returns>True if the bit was set, false if it was not</returns>
+ public bool Clear(int bit)
+ {
+ int wordIndex = bit >> IntShift;
+ int wordBit = bit & IntMask;
+
+ long wordMask = 1L << wordBit;
+
+ bool wasSet = (Masks[wordIndex] & wordMask) != 0;
+
+ Masks[wordIndex] &= ~wordMask;
+
+ return wasSet;
+ }
+
+ /// <summary>
+ /// Clear the bitmap entirely, setting all bits to 0.
+ /// </summary>
+ public void Clear()
+ {
+ for (int i = 0; i < Masks.Length; i++)
+ {
+ Masks[i] = 0;
+ }
+ }
+ }
+}
--
cgit v1.2.3-70-g09d2