1  using Ryujinx.Common.Memory;
  2  using System;
  3  using System.Numerics;
  4  
  5  namespace Ryujinx.Graphics.Vulkan
  6  {
  7      interface IBitMapListener
  8      {
  9          void BitMapSignal(int index, int count);
 10      }
 11  
 12      struct BitMapStruct<T> where T : IArray<long>
 13      {
 14          public const int IntSize = 64;
 15  
 16          private const int IntShift = 6;
 17          private const int IntMask = IntSize - 1;
 18  
 19          private T _masks;
 20  
 21          public BitMapStruct()
 22          {
 23              _masks = default;
 24          }
 25  
 26          public bool BecomesUnsetFrom(in BitMapStruct<T> from, ref BitMapStruct<T> into)
 27          {
 28              bool result = false;
 29  
 30              int masks = _masks.Length;
 31              for (int i = 0; i < masks; i++)
 32              {
 33                  long fromMask = from._masks[i];
 34                  long unsetMask = (~fromMask) & (fromMask ^ _masks[i]);
 35                  into._masks[i] = unsetMask;
 36  
 37                  result |= unsetMask != 0;
 38              }
 39  
 40              return result;
 41          }
 42  
 43          public void SetAndSignalUnset<T2>(in BitMapStruct<T> from, ref T2 listener) where T2 : struct, IBitMapListener
 44          {
 45              BitMapStruct<T> result = new();
 46  
 47              if (BecomesUnsetFrom(from, ref result))
 48              {
 49                  // Iterate the set bits in the result, and signal them.
 50  
 51                  int offset = 0;
 52                  int masks = _masks.Length;
 53                  ref T resultMasks = ref result._masks;
 54                  for (int i = 0; i < masks; i++)
 55                  {
 56                      long value = resultMasks[i];
 57                      while (value != 0)
 58                      {
 59                          int bit = BitOperations.TrailingZeroCount((ulong)value);
 60  
 61                          listener.BitMapSignal(offset + bit, 1);
 62  
 63                          value &= ~(1L << bit);
 64                      }
 65  
 66                      offset += IntSize;
 67                  }
 68              }
 69  
 70              _masks = from._masks;
 71          }
 72  
 73          public void SignalSet(Action<int, int> action)
 74          {
 75              // Iterate the set bits in the result, and signal them.
 76  
 77              int offset = 0;
 78              int masks = _masks.Length;
 79              for (int i = 0; i < masks; i++)
 80              {
 81                  long value = _masks[i];
 82                  while (value != 0)
 83                  {
 84                      int bit = BitOperations.TrailingZeroCount((ulong)value);
 85  
 86                      action(offset + bit, 1);
 87  
 88                      value &= ~(1L << bit);
 89                  }
 90  
 91                  offset += IntSize;
 92              }
 93          }
 94  
 95          public bool AnySet()
 96          {
 97              for (int i = 0; i < _masks.Length; i++)
 98              {
 99                  if (_masks[i] != 0)
100                  {
101                      return true;
102                  }
103              }
104  
105              return false;
106          }
107  
108          public bool IsSet(int bit)
109          {
110              int wordIndex = bit >> IntShift;
111              int wordBit = bit & IntMask;
112  
113              long wordMask = 1L << wordBit;
114  
115              return (_masks[wordIndex] & wordMask) != 0;
116          }
117  
118          public bool IsSet(int start, int end)
119          {
120              if (start == end)
121              {
122                  return IsSet(start);
123              }
124  
125              int startIndex = start >> IntShift;
126              int startBit = start & IntMask;
127              long startMask = -1L << startBit;
128  
129              int endIndex = end >> IntShift;
130              int endBit = end & IntMask;
131              long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
132  
133              if (startIndex == endIndex)
134              {
135                  return (_masks[startIndex] & startMask & endMask) != 0;
136              }
137  
138              if ((_masks[startIndex] & startMask) != 0)
139              {
140                  return true;
141              }
142  
143              for (int i = startIndex + 1; i < endIndex; i++)
144              {
145                  if (_masks[i] != 0)
146                  {
147                      return true;
148                  }
149              }
150  
151              if ((_masks[endIndex] & endMask) != 0)
152              {
153                  return true;
154              }
155  
156              return false;
157          }
158  
159          public bool Set(int bit)
160          {
161              int wordIndex = bit >> IntShift;
162              int wordBit = bit & IntMask;
163  
164              long wordMask = 1L << wordBit;
165  
166              if ((_masks[wordIndex] & wordMask) != 0)
167              {
168                  return false;
169              }
170  
171              _masks[wordIndex] |= wordMask;
172  
173              return true;
174          }
175  
176          public void Set(int bit, bool value)
177          {
178              if (value)
179              {
180                  Set(bit);
181              }
182              else
183              {
184                  Clear(bit);
185              }
186          }
187  
188          public void SetRange(int start, int end)
189          {
190              if (start == end)
191              {
192                  Set(start);
193                  return;
194              }
195  
196              int startIndex = start >> IntShift;
197              int startBit = start & IntMask;
198              long startMask = -1L << startBit;
199  
200              int endIndex = end >> IntShift;
201              int endBit = end & IntMask;
202              long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
203  
204              if (startIndex == endIndex)
205              {
206                  _masks[startIndex] |= startMask & endMask;
207              }
208              else
209              {
210                  _masks[startIndex] |= startMask;
211  
212                  for (int i = startIndex + 1; i < endIndex; i++)
213                  {
214                      _masks[i] |= -1L;
215                  }
216  
217                  _masks[endIndex] |= endMask;
218              }
219          }
220  
221          public BitMapStruct<T> Union(BitMapStruct<T> other)
222          {
223              var result = new BitMapStruct<T>();
224  
225              ref var masks = ref _masks;
226              ref var otherMasks = ref other._masks;
227              ref var newMasks = ref result._masks;
228  
229              for (int i = 0; i < masks.Length; i++)
230              {
231                  newMasks[i] = masks[i] | otherMasks[i];
232              }
233  
234              return result;
235          }
236  
237          public void Clear(int bit)
238          {
239              int wordIndex = bit >> IntShift;
240              int wordBit = bit & IntMask;
241  
242              long wordMask = 1L << wordBit;
243  
244              _masks[wordIndex] &= ~wordMask;
245          }
246  
247          public void Clear()
248          {
249              for (int i = 0; i < _masks.Length; i++)
250              {
251                  _masks[i] = 0;
252              }
253          }
254  
255          public void ClearInt(int start, int end)
256          {
257              for (int i = start; i <= end; i++)
258              {
259                  _masks[i] = 0;
260              }
261          }
262      }
263  }