1  using System.Runtime.CompilerServices;
  2  
  3  namespace Ryujinx.Memory.Tracking
  4  {
  5      /// <summary>
  6      /// A bitmap that can check or set large ranges of true/false values at once.
  7      /// </summary>
  8      readonly struct BitMap
  9      {
 10          public const int IntSize = 64;
 11  
 12          private const int IntShift = 6;
 13          private const int IntMask = IntSize - 1;
 14  
 15          /// <summary>
 16          /// Masks representing the bitmap. Least significant bit first, 64-bits per mask.
 17          /// </summary>
 18          public readonly long[] Masks;
 19  
 20          /// <summary>
 21          /// Create a new bitmap.
 22          /// </summary>
 23          /// <param name="count">The number of bits to reserve</param>
 24          public BitMap(int count)
 25          {
 26              Masks = new long[(count + IntMask) / IntSize];
 27          }
 28  
 29          /// <summary>
 30          /// Check if any bit in the bitmap is set.
 31          /// </summary>
 32          /// <returns>True if any bits are set, false otherwise</returns>
 33          public bool AnySet()
 34          {
 35              for (int i = 0; i < Masks.Length; i++)
 36              {
 37                  if (Masks[i] != 0)
 38                  {
 39                      return true;
 40                  }
 41              }
 42  
 43              return false;
 44          }
 45  
 46          /// <summary>
 47          /// Check if a bit in the bitmap is set.
 48          /// </summary>
 49          /// <param name="bit">The bit index to check</param>
 50          /// <returns>True if the bit is set, false otherwise</returns>
 51          [MethodImpl(MethodImplOptions.AggressiveInlining)]
 52          public bool IsSet(int bit)
 53          {
 54              int wordIndex = bit >> IntShift;
 55              int wordBit = bit & IntMask;
 56  
 57              long wordMask = 1L << wordBit;
 58  
 59              return (Masks[wordIndex] & wordMask) != 0;
 60          }
 61  
 62          /// <summary>
 63          /// Check if any bit in a range of bits in the bitmap are set. (inclusive)
 64          /// </summary>
 65          /// <param name="start">The first bit index to check</param>
 66          /// <param name="end">The last bit index to check</param>
 67          /// <returns>True if a bit is set, false otherwise</returns>
 68          public bool IsSet(int start, int end)
 69          {
 70              if (start == end)
 71              {
 72                  return IsSet(start);
 73              }
 74  
 75              int startIndex = start >> IntShift;
 76              int startBit = start & IntMask;
 77              long startMask = -1L << startBit;
 78  
 79              int endIndex = end >> IntShift;
 80              int endBit = end & IntMask;
 81              long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
 82  
 83              if (startIndex == endIndex)
 84              {
 85                  return (Masks[startIndex] & startMask & endMask) != 0;
 86              }
 87  
 88              if ((Masks[startIndex] & startMask) != 0)
 89              {
 90                  return true;
 91              }
 92  
 93              for (int i = startIndex + 1; i < endIndex; i++)
 94              {
 95                  if (Masks[i] != 0)
 96                  {
 97                      return true;
 98                  }
 99              }
100  
101              if ((Masks[endIndex] & endMask) != 0)
102              {
103                  return true;
104              }
105  
106              return false;
107          }
108  
109          /// <summary>
110          /// Set a bit at a specific index to 1.
111          /// </summary>
112          /// <param name="bit">The bit index to set</param>
113          /// <returns>True if the bit is set, false if it was already set</returns>
114          public bool Set(int bit)
115          {
116              int wordIndex = bit >> IntShift;
117              int wordBit = bit & IntMask;
118  
119              long wordMask = 1L << wordBit;
120  
121              if ((Masks[wordIndex] & wordMask) != 0)
122              {
123                  return false;
124              }
125  
126              Masks[wordIndex] |= wordMask;
127  
128              return true;
129          }
130  
131          /// <summary>
132          /// Set a range of bits in the bitmap to 1.
133          /// </summary>
134          /// <param name="start">The first bit index to set</param>
135          /// <param name="end">The last bit index to set</param>
136          public void SetRange(int start, int end)
137          {
138              if (start == end)
139              {
140                  Set(start);
141                  return;
142              }
143  
144              int startIndex = start >> IntShift;
145              int startBit = start & IntMask;
146              long startMask = -1L << startBit;
147  
148              int endIndex = end >> IntShift;
149              int endBit = end & IntMask;
150              long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
151  
152              if (startIndex == endIndex)
153              {
154                  Masks[startIndex] |= startMask & endMask;
155              }
156              else
157              {
158                  Masks[startIndex] |= startMask;
159  
160                  for (int i = startIndex + 1; i < endIndex; i++)
161                  {
162                      Masks[i] |= -1;
163                  }
164  
165                  Masks[endIndex] |= endMask;
166              }
167          }
168  
169          /// <summary>
170          /// Clear a bit at a specific index to 0.
171          /// </summary>
172          /// <param name="bit">The bit index to clear</param>
173          /// <returns>True if the bit was set, false if it was not</returns>
174          public bool Clear(int bit)
175          {
176              int wordIndex = bit >> IntShift;
177              int wordBit = bit & IntMask;
178  
179              long wordMask = 1L << wordBit;
180  
181              bool wasSet = (Masks[wordIndex] & wordMask) != 0;
182  
183              Masks[wordIndex] &= ~wordMask;
184  
185              return wasSet;
186          }
187  
188          /// <summary>
189          /// Clear the bitmap entirely, setting all bits to 0.
190          /// </summary>
191          public void Clear()
192          {
193              for (int i = 0; i < Masks.Length; i++)
194              {
195                  Masks[i] = 0;
196              }
197          }
198      }
199  }