1  using Ryujinx.Common;
  2  using System;
  3  using System.Numerics;
  4  
  5  namespace Ryujinx.HLE.HOS.Kernel.Memory
  6  {
  7      class KPageBitmap
  8      {
  9          private struct RandomNumberGenerator
 10          {
 11              private uint _entropy;
 12              private uint _bitsAvailable;
 13  
 14              private void RefreshEntropy()
 15              {
 16                  _entropy = 0;
 17                  _bitsAvailable = sizeof(uint) * 8;
 18              }
 19  
 20              private bool GenerateRandomBit()
 21              {
 22                  if (_bitsAvailable == 0)
 23                  {
 24                      RefreshEntropy();
 25                  }
 26  
 27                  bool bit = (_entropy & 1) != 0;
 28  
 29                  _entropy >>= 1;
 30                  _bitsAvailable--;
 31  
 32                  return bit;
 33              }
 34  
 35              public int SelectRandomBit(ulong bitmap)
 36              {
 37                  int selected = 0;
 38  
 39                  int bitsCount = UInt64BitSize / 2;
 40                  ulong mask = (1UL << bitsCount) - 1;
 41  
 42                  while (bitsCount != 0)
 43                  {
 44                      ulong low = bitmap & mask;
 45                      ulong high = (bitmap >> bitsCount) & mask;
 46  
 47                      bool chooseLow;
 48  
 49                      if (high == 0)
 50                      {
 51                          chooseLow = true;
 52                      }
 53                      else if (low == 0)
 54                      {
 55                          chooseLow = false;
 56                      }
 57                      else
 58                      {
 59                          chooseLow = GenerateRandomBit();
 60                      }
 61  
 62                      if (chooseLow)
 63                      {
 64                          bitmap = low;
 65                      }
 66                      else
 67                      {
 68                          bitmap = high;
 69                          selected += bitsCount;
 70                      }
 71  
 72                      bitsCount /= 2;
 73                      mask >>= bitsCount;
 74                  }
 75  
 76                  return selected;
 77              }
 78          }
 79  
 80          private const int UInt64BitSize = sizeof(ulong) * 8;
 81          private const int MaxDepth = 4;
 82  
 83          private readonly RandomNumberGenerator _rng;
 84          private readonly ArraySegment<ulong>[] _bitStorages;
 85          private int _usedDepths;
 86  
 87          public int BitsCount { get; private set; }
 88  
 89          public int HighestDepthIndex => _usedDepths - 1;
 90  
 91          public KPageBitmap()
 92          {
 93              _rng = new RandomNumberGenerator();
 94              _bitStorages = new ArraySegment<ulong>[MaxDepth];
 95          }
 96  
 97          public ArraySegment<ulong> Initialize(ArraySegment<ulong> storage, ulong size)
 98          {
 99              _usedDepths = GetRequiredDepth(size);
100  
101              for (int depth = HighestDepthIndex; depth >= 0; depth--)
102              {
103                  _bitStorages[depth] = storage;
104                  size = BitUtils.DivRoundUp<ulong>(size, (ulong)UInt64BitSize);
105                  storage = storage.Slice((int)size);
106              }
107  
108              return storage;
109          }
110  
111          public ulong FindFreeBlock(bool random)
112          {
113              ulong offset = 0;
114              int depth = 0;
115  
116              if (random)
117              {
118                  do
119                  {
120                      ulong v = _bitStorages[depth][(int)offset];
121  
122                      if (v == 0)
123                      {
124                          return ulong.MaxValue;
125                      }
126  
127                      offset = offset * UInt64BitSize + (ulong)_rng.SelectRandomBit(v);
128                  }
129                  while (++depth < _usedDepths);
130              }
131              else
132              {
133                  do
134                  {
135                      ulong v = _bitStorages[depth][(int)offset];
136  
137                      if (v == 0)
138                      {
139                          return ulong.MaxValue;
140                      }
141  
142                      offset = offset * UInt64BitSize + (ulong)BitOperations.TrailingZeroCount(v);
143                  }
144                  while (++depth < _usedDepths);
145              }
146  
147              return offset;
148          }
149  
150          public void SetBit(ulong offset)
151          {
152              SetBit(HighestDepthIndex, offset);
153              BitsCount++;
154          }
155  
156          public void ClearBit(ulong offset)
157          {
158              ClearBit(HighestDepthIndex, offset);
159              BitsCount--;
160          }
161  
162          public bool ClearRange(ulong offset, int count)
163          {
164              int depth = HighestDepthIndex;
165              var bits = _bitStorages[depth];
166  
167              int bitInd = (int)(offset / UInt64BitSize);
168  
169              if (count < UInt64BitSize)
170              {
171                  int shift = (int)(offset % UInt64BitSize);
172  
173                  ulong mask = ((1UL << count) - 1) << shift;
174  
175                  ulong v = bits[bitInd];
176  
177                  if ((v & mask) != mask)
178                  {
179                      return false;
180                  }
181  
182                  v &= ~mask;
183                  bits[bitInd] = v;
184  
185                  if (v == 0)
186                  {
187                      ClearBit(depth - 1, (ulong)bitInd);
188                  }
189              }
190              else
191              {
192                  int remaining = count;
193                  int i = 0;
194  
195                  do
196                  {
197                      if (bits[bitInd + i++] != ulong.MaxValue)
198                      {
199                          return false;
200                      }
201  
202                      remaining -= UInt64BitSize;
203                  }
204                  while (remaining > 0);
205  
206                  remaining = count;
207                  i = 0;
208  
209                  do
210                  {
211                      bits[bitInd + i] = 0;
212                      ClearBit(depth - 1, (ulong)(bitInd + i));
213                      i++;
214                      remaining -= UInt64BitSize;
215                  }
216                  while (remaining > 0);
217              }
218  
219              BitsCount -= count;
220              return true;
221          }
222  
223          private void SetBit(int depth, ulong offset)
224          {
225              while (depth >= 0)
226              {
227                  int ind = (int)(offset / UInt64BitSize);
228                  int which = (int)(offset % UInt64BitSize);
229  
230                  ulong mask = 1UL << which;
231  
232                  ulong v = _bitStorages[depth][ind];
233  
234                  _bitStorages[depth][ind] = v | mask;
235  
236                  if (v != 0)
237                  {
238                      break;
239                  }
240  
241                  offset = (ulong)ind;
242                  depth--;
243              }
244          }
245  
246          private void ClearBit(int depth, ulong offset)
247          {
248              while (depth >= 0)
249              {
250                  int ind = (int)(offset / UInt64BitSize);
251                  int which = (int)(offset % UInt64BitSize);
252  
253                  ulong mask = 1UL << which;
254  
255                  ulong v = _bitStorages[depth][ind];
256  
257                  v &= ~mask;
258  
259                  _bitStorages[depth][ind] = v;
260  
261                  if (v != 0)
262                  {
263                      break;
264                  }
265  
266                  offset = (ulong)ind;
267                  depth--;
268              }
269          }
270  
271          private static int GetRequiredDepth(ulong regionSize)
272          {
273              int depth = 0;
274  
275              do
276              {
277                  regionSize /= UInt64BitSize;
278                  depth++;
279              }
280              while (regionSize != 0);
281  
282              return depth;
283          }
284  
285          public static int CalculateManagementOverheadSize(ulong regionSize)
286          {
287              int overheadBits = 0;
288  
289              for (int depth = GetRequiredDepth(regionSize) - 1; depth >= 0; depth--)
290              {
291                  regionSize = BitUtils.DivRoundUp<ulong>(regionSize, UInt64BitSize);
292                  overheadBits += (int)regionSize;
293              }
294  
295              return overheadBits * sizeof(ulong);
296          }
297      }
298  }