1  using System;
  2  using System.Collections.Generic;
  3  
  4  namespace Ryujinx.Memory.Range
  5  {
  6      /// <summary>
  7      /// Sequence of physical memory regions that a single non-contiguous virtual memory region maps to.
  8      /// </summary>
  9      public readonly struct MultiRange : IEquatable<MultiRange>
 10      {
 11          private const ulong InvalidAddress = ulong.MaxValue;
 12  
 13          private readonly MemoryRange _singleRange;
 14          private readonly MemoryRange[] _ranges;
 15  
 16          private bool HasSingleRange => _ranges == null;
 17  
 18          /// <summary>
 19          /// Indicates that the range is fully unmapped.
 20          /// </summary>
 21          public bool IsUnmapped => HasSingleRange && _singleRange.Address == InvalidAddress;
 22  
 23          /// <summary>
 24          /// Total of physical sub-ranges on the virtual memory region.
 25          /// </summary>
 26          public int Count => HasSingleRange ? 1 : _ranges.Length;
 27  
 28          /// <summary>
 29          /// Creates a new multi-range with a single physical region.
 30          /// </summary>
 31          /// <param name="address">Start address of the region</param>
 32          /// <param name="size">Size of the region in bytes</param>
 33          public MultiRange(ulong address, ulong size)
 34          {
 35              _singleRange = new MemoryRange(address, size);
 36              _ranges = null;
 37          }
 38  
 39          /// <summary>
 40          /// Creates a new multi-range with multiple physical regions.
 41          /// </summary>
 42          /// <param name="ranges">Array of physical regions</param>
 43          /// <exception cref="ArgumentNullException"><paramref name="ranges"/> is null</exception>
 44          public MultiRange(MemoryRange[] ranges)
 45          {
 46              ArgumentNullException.ThrowIfNull(ranges);
 47  
 48              if (ranges.Length == 1)
 49              {
 50                  _singleRange = ranges[0];
 51                  _ranges = null;
 52              }
 53              else
 54              {
 55                  _singleRange = MemoryRange.Empty;
 56                  _ranges = ranges;
 57              }
 58          }
 59  
 60          /// <summary>
 61          /// Gets a slice of the multi-range.
 62          /// </summary>
 63          /// <param name="offset">Offset of the slice into the multi-range in bytes</param>
 64          /// <param name="size">Size of the slice in bytes</param>
 65          /// <returns>A new multi-range representing the given slice of this one</returns>
 66          public MultiRange Slice(ulong offset, ulong size)
 67          {
 68              if (HasSingleRange)
 69              {
 70                  ArgumentOutOfRangeException.ThrowIfGreaterThan(size, _singleRange.Size - offset);
 71  
 72                  return new MultiRange(_singleRange.Address + offset, size);
 73              }
 74              else
 75              {
 76                  var ranges = new List<MemoryRange>();
 77  
 78                  foreach (MemoryRange range in _ranges)
 79                  {
 80                      if ((long)offset <= 0)
 81                      {
 82                          ranges.Add(new MemoryRange(range.Address, Math.Min(size, range.Size)));
 83                          size -= range.Size;
 84                      }
 85                      else if (offset < range.Size)
 86                      {
 87                          ulong sliceSize = Math.Min(size, range.Size - offset);
 88  
 89                          if (range.Address == InvalidAddress)
 90                          {
 91                              ranges.Add(new MemoryRange(range.Address, sliceSize));
 92                          }
 93                          else
 94                          {
 95                              ranges.Add(new MemoryRange(range.Address + offset, sliceSize));
 96                          }
 97  
 98                          size -= sliceSize;
 99                      }
100  
101                      if ((long)size <= 0)
102                      {
103                          break;
104                      }
105  
106                      offset -= range.Size;
107                  }
108  
109                  return ranges.Count == 1 ? new MultiRange(ranges[0].Address, ranges[0].Size) : new MultiRange(ranges.ToArray());
110              }
111          }
112  
113          /// <summary>
114          /// Gets the physical region at the specified index.
115          /// </summary>
116          /// <param name="index">Index of the physical region</param>
117          /// <returns>Region at the index specified</returns>
118          /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is invalid</exception>
119          public MemoryRange GetSubRange(int index)
120          {
121              if (HasSingleRange)
122              {
123                  ArgumentOutOfRangeException.ThrowIfNotEqual(index, 0);
124  
125                  return _singleRange;
126              }
127              else
128              {
129                  if ((uint)index >= _ranges.Length)
130                  {
131                      throw new ArgumentOutOfRangeException(nameof(index));
132                  }
133  
134                  return _ranges[index];
135              }
136          }
137  
138          /// <summary>
139          /// Gets the physical region at the specified index, without explicit bounds checking.
140          /// </summary>
141          /// <param name="index">Index of the physical region</param>
142          /// <returns>Region at the index specified</returns>
143          private MemoryRange GetSubRangeUnchecked(int index)
144          {
145              return HasSingleRange ? _singleRange : _ranges[index];
146          }
147  
148          /// <summary>
149          /// Check if two multi-ranges overlap with each other.
150          /// </summary>
151          /// <param name="other">Other multi-range to check for overlap</param>
152          /// <returns>True if any sub-range overlaps, false otherwise</returns>
153          public bool OverlapsWith(MultiRange other)
154          {
155              if (HasSingleRange && other.HasSingleRange)
156              {
157                  return _singleRange.OverlapsWith(other._singleRange);
158              }
159              else
160              {
161                  for (int i = 0; i < Count; i++)
162                  {
163                      MemoryRange currentRange = GetSubRangeUnchecked(i);
164  
165                      for (int j = 0; j < other.Count; j++)
166                      {
167                          if (currentRange.OverlapsWith(other.GetSubRangeUnchecked(j)))
168                          {
169                              return true;
170                          }
171                      }
172                  }
173              }
174  
175              return false;
176          }
177  
178          /// <summary>
179          /// Checks if a given multi-range is fully contained inside another.
180          /// </summary>
181          /// <param name="other">Multi-range to be checked</param>
182          /// <returns>True if all the sub-ranges on <paramref name="other"/> are contained inside the multi-range, with the same order, false otherwise</returns>
183          public bool Contains(MultiRange other)
184          {
185              return FindOffset(other) >= 0;
186          }
187  
188          /// <summary>
189          /// Calculates the offset of a given multi-range inside another, when the multi-range is fully contained
190          /// inside the other multi-range, otherwise returns -1.
191          /// </summary>
192          /// <param name="other">Multi-range that should be fully contained inside this one</param>
193          /// <returns>Offset in bytes if fully contained, otherwise -1</returns>
194          public int FindOffset(MultiRange other)
195          {
196              int thisCount = Count;
197              int otherCount = other.Count;
198  
199              if (thisCount == 1 && otherCount == 1)
200              {
201                  MemoryRange otherFirstRange = other.GetSubRangeUnchecked(0);
202                  MemoryRange currentFirstRange = GetSubRangeUnchecked(0);
203  
204                  if (otherFirstRange.Address >= currentFirstRange.Address &&
205                      otherFirstRange.EndAddress <= currentFirstRange.EndAddress)
206                  {
207                      return (int)(otherFirstRange.Address - currentFirstRange.Address);
208                  }
209              }
210              else if (thisCount >= otherCount)
211              {
212                  ulong baseOffset = 0;
213  
214                  MemoryRange otherFirstRange = other.GetSubRangeUnchecked(0);
215                  MemoryRange otherLastRange = other.GetSubRangeUnchecked(otherCount - 1);
216  
217                  for (int i = 0; i < (thisCount - otherCount) + 1; baseOffset += GetSubRangeUnchecked(i).Size, i++)
218                  {
219                      MemoryRange currentFirstRange = GetSubRangeUnchecked(i);
220                      MemoryRange currentLastRange = GetSubRangeUnchecked(i + otherCount - 1);
221  
222                      if (otherCount > 1)
223                      {
224                          if (otherFirstRange.Address < currentFirstRange.Address ||
225                              otherFirstRange.EndAddress != currentFirstRange.EndAddress)
226                          {
227                              continue;
228                          }
229  
230                          if (otherLastRange.Address != currentLastRange.Address ||
231                              otherLastRange.EndAddress > currentLastRange.EndAddress)
232                          {
233                              continue;
234                          }
235  
236                          bool fullMatch = true;
237  
238                          for (int j = 1; j < otherCount - 1; j++)
239                          {
240                              if (!GetSubRangeUnchecked(i + j).Equals(other.GetSubRangeUnchecked(j)))
241                              {
242                                  fullMatch = false;
243                                  break;
244                              }
245                          }
246  
247                          if (!fullMatch)
248                          {
249                              continue;
250                          }
251                      }
252                      else if (currentFirstRange.Address > otherFirstRange.Address ||
253                               currentFirstRange.EndAddress < otherFirstRange.EndAddress)
254                      {
255                          continue;
256                      }
257  
258                      return (int)(baseOffset + (otherFirstRange.Address - currentFirstRange.Address));
259                  }
260              }
261  
262              return -1;
263          }
264  
265          /// <summary>
266          /// Gets the total size of all sub-ranges in bytes.
267          /// </summary>
268          /// <returns>Total size in bytes</returns>
269          public ulong GetSize()
270          {
271              if (HasSingleRange)
272              {
273                  return _singleRange.Size;
274              }
275  
276              ulong sum = 0;
277  
278              foreach (MemoryRange range in _ranges)
279              {
280                  sum += range.Size;
281              }
282  
283              return sum;
284          }
285  
286          public override bool Equals(object obj)
287          {
288              return obj is MultiRange other && Equals(other);
289          }
290  
291          public bool Equals(MultiRange other)
292          {
293              if (HasSingleRange && other.HasSingleRange)
294              {
295                  return _singleRange.Equals(other._singleRange);
296              }
297  
298              int thisCount = Count;
299              if (thisCount != other.Count)
300              {
301                  return false;
302              }
303  
304              for (int i = 0; i < thisCount; i++)
305              {
306                  if (!GetSubRangeUnchecked(i).Equals(other.GetSubRangeUnchecked(i)))
307                  {
308                      return false;
309                  }
310              }
311  
312              return true;
313          }
314  
315          public override int GetHashCode()
316          {
317              if (HasSingleRange)
318              {
319                  return _singleRange.GetHashCode();
320              }
321  
322              HashCode hash = new();
323  
324              foreach (MemoryRange range in _ranges)
325              {
326                  hash.Add(range);
327              }
328  
329              return hash.ToHashCode();
330          }
331  
332          /// <summary>
333          /// Returns a string summary of the ranges contained in the MultiRange.
334          /// </summary>
335          /// <returns>A string summary of the ranges contained within</returns>
336          public override string ToString()
337          {
338              return HasSingleRange ? _singleRange.ToString() : string.Join(", ", _ranges);
339          }
340  
341          public static bool operator ==(MultiRange left, MultiRange right)
342          {
343              return left.Equals(right);
344          }
345  
346          public static bool operator !=(MultiRange left, MultiRange right)
347          {
348              return !(left == right);
349          }
350      }
351  }