diff options
Diffstat (limited to 'src')
44 files changed, 4630 insertions, 4 deletions
diff --git a/src/Ryujinx.HLE/HOS/Horizon.cs b/src/Ryujinx.HLE/HOS/Horizon.cs index f83fd47b..1a402240 100644 --- a/src/Ryujinx.HLE/HOS/Horizon.cs +++ b/src/Ryujinx.HLE/HOS/Horizon.cs @@ -327,8 +327,10 @@ namespace Ryujinx.HLE.HOS private void StartNewServices() { + HorizonFsClient fsClient = new(this); + ServiceTable = new ServiceTable(); - var services = ServiceTable.GetServices(new HorizonOptions(Device.Configuration.IgnoreMissingServices, LibHacHorizonManager.BcatClient)); + var services = ServiceTable.GetServices(new HorizonOptions(Device.Configuration.IgnoreMissingServices, LibHacHorizonManager.BcatClient, fsClient)); foreach (var service in services) { diff --git a/src/Ryujinx.HLE/HOS/HorizonFsClient.cs b/src/Ryujinx.HLE/HOS/HorizonFsClient.cs new file mode 100644 index 00000000..3dbafa88 --- /dev/null +++ b/src/Ryujinx.HLE/HOS/HorizonFsClient.cs @@ -0,0 +1,119 @@ +using LibHac.Common; +using LibHac.Fs.Fsa; +using LibHac.FsSystem; +using LibHac.Ncm; +using LibHac.Tools.FsSystem.NcaUtils; +using Ryujinx.HLE.FileSystem; +using Ryujinx.Horizon; +using Ryujinx.Horizon.Common; +using Ryujinx.Horizon.Sdk.Fs; +using System; +using System.Collections.Concurrent; +using System.IO; + +namespace Ryujinx.HLE.HOS +{ + class HorizonFsClient : IFsClient + { + private readonly Horizon _system; + private readonly LibHac.Fs.FileSystemClient _fsClient; + private readonly ConcurrentDictionary<string, LocalStorage> _mountedStorages; + + public HorizonFsClient(Horizon system) + { + _system = system; + _fsClient = _system.LibHacHorizonManager.FsClient.Fs; + _mountedStorages = new(); + } + + public void CloseFile(FileHandle handle) + { + _fsClient.CloseFile((LibHac.Fs.FileHandle)handle.Value); + } + + public Result GetFileSize(out long size, FileHandle handle) + { + return _fsClient.GetFileSize(out size, (LibHac.Fs.FileHandle)handle.Value).ToHorizonResult(); + } + + public Result MountSystemData(string mountName, ulong dataId) + { + string contentPath = _system.ContentManager.GetInstalledContentPath(dataId, StorageId.BuiltInSystem, NcaContentType.PublicData); + string installPath = VirtualFileSystem.SwitchPathToSystemPath(contentPath); + + if (!string.IsNullOrWhiteSpace(installPath)) + { + string ncaPath = installPath; + + if (File.Exists(ncaPath)) + { + LocalStorage ncaStorage = null; + + try + { + ncaStorage = new LocalStorage(ncaPath, FileAccess.Read, FileMode.Open); + + Nca nca = new(_system.KeySet, ncaStorage); + + using var ncaFileSystem = nca.OpenFileSystem(NcaSectionType.Data, _system.FsIntegrityCheckLevel); + using var ncaFsRef = new UniqueRef<IFileSystem>(ncaFileSystem); + + Result result = _fsClient.Register(mountName.ToU8Span(), ref ncaFsRef.Ref).ToHorizonResult(); + if (result.IsFailure) + { + ncaStorage.Dispose(); + } + else + { + _mountedStorages.TryAdd(mountName, ncaStorage); + } + + return result; + } + catch (HorizonResultException ex) + { + ncaStorage?.Dispose(); + + return ex.ResultValue.ToHorizonResult(); + } + } + } + + // TODO: Return correct result here, this is likely wrong. + + return LibHac.Fs.ResultFs.TargetNotFound.Handle().ToHorizonResult(); + } + + public Result OpenFile(out FileHandle handle, string path, OpenMode openMode) + { + var result = _fsClient.OpenFile(out var libhacHandle, path.ToU8Span(), (LibHac.Fs.OpenMode)openMode); + handle = new(libhacHandle); + + return result.ToHorizonResult(); + } + + public Result QueryMountSystemDataCacheSize(out long size, ulong dataId) + { + // TODO. + + size = 0; + + return Result.Success; + } + + public Result ReadFile(FileHandle handle, long offset, Span<byte> destination) + { + return _fsClient.ReadFile((LibHac.Fs.FileHandle)handle.Value, offset, destination).ToHorizonResult(); + } + + public void Unmount(string mountName) + { + if (_mountedStorages.TryRemove(mountName, out LocalStorage ncaStorage)) + { + ncaStorage.Dispose(); + } + + _fsClient.Unmount(mountName.ToU8Span()); + } + } +} diff --git a/src/Ryujinx.Horizon/HorizonOptions.cs b/src/Ryujinx.Horizon/HorizonOptions.cs index 75cc29b7..e3c862da 100644 --- a/src/Ryujinx.Horizon/HorizonOptions.cs +++ b/src/Ryujinx.Horizon/HorizonOptions.cs @@ -1,4 +1,5 @@ using LibHac; +using Ryujinx.Horizon.Sdk.Fs; namespace Ryujinx.Horizon { @@ -8,12 +9,14 @@ namespace Ryujinx.Horizon public bool ThrowOnInvalidCommandIds { get; } public HorizonClient BcatClient { get; } + public IFsClient FsClient { get; } - public HorizonOptions(bool ignoreMissingServices, HorizonClient bcatClient) + public HorizonOptions(bool ignoreMissingServices, HorizonClient bcatClient, IFsClient fsClient) { IgnoreMissingServices = ignoreMissingServices; ThrowOnInvalidCommandIds = true; BcatClient = bcatClient; + FsClient = fsClient; } } } diff --git a/src/Ryujinx.Horizon/LibHacResultExtensions.cs b/src/Ryujinx.Horizon/LibHacResultExtensions.cs index 01d18164..8c994f14 100644 --- a/src/Ryujinx.Horizon/LibHacResultExtensions.cs +++ b/src/Ryujinx.Horizon/LibHacResultExtensions.cs @@ -2,7 +2,7 @@ namespace Ryujinx.Horizon { - internal static class LibHacResultExtensions + public static class LibHacResultExtensions { public static Result ToHorizonResult(this LibHac.Result result) { diff --git a/src/Ryujinx.Horizon/LogManager/Ipc/LogService.cs b/src/Ryujinx.Horizon/LogManager/Ipc/LogService.cs index 9ac9c27e..c266d0e9 100644 --- a/src/Ryujinx.Horizon/LogManager/Ipc/LogService.cs +++ b/src/Ryujinx.Horizon/LogManager/Ipc/LogService.cs @@ -11,7 +11,7 @@ namespace Ryujinx.Horizon.LogManager.Ipc [CmifCommand(0)] public Result OpenLogger(out LmLogger logger, [ClientProcessId] ulong pid) { - // NOTE: Internal name is Logger, but we rename it LmLogger to avoid name clash with Ryujinx.Common.Logging logger. + // NOTE: Internal name is Logger, but we rename it to LmLogger to avoid name clash with Ryujinx.Common.Logging logger. logger = new LmLogger(this, pid); return Result.Success; diff --git a/src/Ryujinx.Horizon/Ngc/Ipc/Service.cs b/src/Ryujinx.Horizon/Ngc/Ipc/Service.cs new file mode 100644 index 00000000..828c0919 --- /dev/null +++ b/src/Ryujinx.Horizon/Ngc/Ipc/Service.cs @@ -0,0 +1,64 @@ +using Ryujinx.Horizon.Common; +using Ryujinx.Horizon.Sdk.Ngc; +using Ryujinx.Horizon.Sdk.Ngc.Detail; +using Ryujinx.Horizon.Sdk.Sf; +using Ryujinx.Horizon.Sdk.Sf.Hipc; +using System; + +namespace Ryujinx.Horizon.Ngc.Ipc +{ + partial class Service : INgcService + { + private readonly ProfanityFilter _profanityFilter; + + public Service(ProfanityFilter profanityFilter) + { + _profanityFilter = profanityFilter; + } + + [CmifCommand(0)] + public Result GetContentVersion(out uint version) + { + lock (_profanityFilter) + { + return _profanityFilter.GetContentVersion(out version); + } + } + + [CmifCommand(1)] + public Result Check(out uint checkMask, ReadOnlySpan<byte> text, uint regionMask, ProfanityFilterOption option) + { + lock (_profanityFilter) + { + return _profanityFilter.CheckProfanityWords(out checkMask, text, regionMask, option); + } + } + + [CmifCommand(2)] + public Result Mask( + out int maskedWordsCount, + [Buffer(HipcBufferFlags.Out | HipcBufferFlags.MapAlias)] Span<byte> filteredText, + [Buffer(HipcBufferFlags.In | HipcBufferFlags.MapAlias)] ReadOnlySpan<byte> text, + uint regionMask, + ProfanityFilterOption option) + { + lock (_profanityFilter) + { + int length = Math.Min(filteredText.Length, text.Length); + + text[..length].CopyTo(filteredText[..length]); + + return _profanityFilter.MaskProfanityWordsInText(out maskedWordsCount, filteredText, regionMask, option); + } + } + + [CmifCommand(3)] + public Result Reload() + { + lock (_profanityFilter) + { + return _profanityFilter.Reload(); + } + } + } +} diff --git a/src/Ryujinx.Horizon/Ngc/NgcIpcServer.cs b/src/Ryujinx.Horizon/Ngc/NgcIpcServer.cs new file mode 100644 index 00000000..b2a74fb2 --- /dev/null +++ b/src/Ryujinx.Horizon/Ngc/NgcIpcServer.cs @@ -0,0 +1,51 @@ +using Ryujinx.Horizon.Ngc.Ipc; +using Ryujinx.Horizon.Sdk.Fs; +using Ryujinx.Horizon.Sdk.Ngc.Detail; +using Ryujinx.Horizon.Sdk.Sf.Hipc; +using Ryujinx.Horizon.Sdk.Sm; +using System; + +namespace Ryujinx.Horizon.Ngc +{ + class NgcIpcServer + { + private const int MaxSessionsCount = 4; + + private const int PointerBufferSize = 0; + private const int MaxDomains = 0; + private const int MaxDomainObjects = 0; + private const int MaxPortsCount = 1; + + private static readonly ManagerOptions _options = new(PointerBufferSize, MaxDomains, MaxDomainObjects, false); + + private SmApi _sm; + private ServerManager _serverManager; + private ProfanityFilter _profanityFilter; + + public void Initialize(IFsClient fsClient) + { + HeapAllocator allocator = new(); + + _sm = new SmApi(); + _sm.Initialize().AbortOnFailure(); + + _profanityFilter = new(fsClient); + _profanityFilter.Initialize().AbortOnFailure(); + + _serverManager = new ServerManager(allocator, _sm, MaxPortsCount, _options, MaxSessionsCount); + + _serverManager.RegisterObjectForServer(new Service(_profanityFilter), ServiceName.Encode("ngc:u"), MaxSessionsCount); + } + + public void ServiceRequests() + { + _serverManager.ServiceRequests(); + } + + public void Shutdown() + { + _serverManager.Dispose(); + _profanityFilter.Dispose(); + } + } +} diff --git a/src/Ryujinx.Horizon/Ngc/NgcMain.cs b/src/Ryujinx.Horizon/Ngc/NgcMain.cs new file mode 100644 index 00000000..1a584d66 --- /dev/null +++ b/src/Ryujinx.Horizon/Ngc/NgcMain.cs @@ -0,0 +1,21 @@ +namespace Ryujinx.Horizon.Ngc +{ + class NgcMain : IService + { + public static void Main(ServiceTable serviceTable) + { + NgcIpcServer ipcServer = new(); + + ipcServer.Initialize(HorizonStatic.Options.FsClient); + + // TODO: Notification thread, requires implementing OpenSystemDataUpdateEventNotifier on FS. + // The notification thread seems to wait until the event returned by OpenSystemDataUpdateEventNotifier is signalled + // in a loop. When it receives the signal, it calls ContentsReader.Reload and then waits for the next signal. + + serviceTable.SignalServiceReady(); + + ipcServer.ServiceRequests(); + ipcServer.Shutdown(); + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Fs/FileHandle.cs b/src/Ryujinx.Horizon/Sdk/Fs/FileHandle.cs new file mode 100644 index 00000000..1993577d --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Fs/FileHandle.cs @@ -0,0 +1,13 @@ + +namespace Ryujinx.Horizon.Sdk.Fs +{ + public readonly struct FileHandle + { + public object Value { get; } + + public FileHandle(object value) + { + Value = value; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Fs/FsResult.cs b/src/Ryujinx.Horizon/Sdk/Fs/FsResult.cs new file mode 100644 index 00000000..a4b70bd5 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Fs/FsResult.cs @@ -0,0 +1,13 @@ +using Ryujinx.Horizon.Common; + +namespace Ryujinx.Horizon.Sdk.Fs +{ + static class FsResult + { + private const int ModuleId = 2; + + public static Result PathNotFound => new(ModuleId, 1); + public static Result PathAlreadyExists => new(ModuleId, 2); + public static Result TargetNotFound => new(ModuleId, 1002); + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Fs/IFsClient.cs b/src/Ryujinx.Horizon/Sdk/Fs/IFsClient.cs new file mode 100644 index 00000000..caf6b03e --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Fs/IFsClient.cs @@ -0,0 +1,16 @@ +using Ryujinx.Horizon.Common; +using System; + +namespace Ryujinx.Horizon.Sdk.Fs +{ + public interface IFsClient + { + Result QueryMountSystemDataCacheSize(out long size, ulong dataId); + Result MountSystemData(string mountName, ulong dataId); + Result OpenFile(out FileHandle handle, string path, OpenMode openMode); + Result ReadFile(FileHandle handle, long offset, Span<byte> destination); + Result GetFileSize(out long size, FileHandle handle); + void CloseFile(FileHandle handle); + void Unmount(string mountName); + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Fs/OpenMode.cs b/src/Ryujinx.Horizon/Sdk/Fs/OpenMode.cs new file mode 100644 index 00000000..add2ca48 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Fs/OpenMode.cs @@ -0,0 +1,14 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Fs +{ + [Flags] + public enum OpenMode + { + Read = 1, + Write = 2, + AllowAppend = 4, + ReadWrite = 3, + All = 7, + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/AhoCorasick.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/AhoCorasick.cs new file mode 100644 index 00000000..e772427c --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/AhoCorasick.cs @@ -0,0 +1,251 @@ +using System; +using System.Diagnostics; +using System.Text; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class AhoCorasick + { + public delegate bool MatchCallback(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchState state); + public delegate bool MatchCallback<T>(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref T state); + + private readonly SparseSet _wordMap = new(); + private readonly CompressedArray _wordLengths = new(); + private readonly SparseSet _multiWordMap = new(); + private readonly CompressedArray _multiWordIndices = new(); + private readonly SparseSet _nodeMap = new(); + private uint _nodesPerCharacter; + private readonly Bp _bp = new(); + + public bool Import(ref BinaryReader reader) + { + if (!_wordLengths.Import(ref reader) || + !_wordMap.Import(ref reader) || + !_multiWordIndices.Import(ref reader) || + !_multiWordMap.Import(ref reader)) + { + return false; + } + + if (!reader.Read(out _nodesPerCharacter)) + { + return false; + } + + return _nodeMap.Import(ref reader) && _bp.Import(ref reader); + } + + public void Match(ReadOnlySpan<byte> utf8Text, MatchCallback callback, ref MatchState state) + { + int nodeId = 0; + + for (int index = 0; index < utf8Text.Length; index++) + { + long c = utf8Text[index]; + + while (true) + { + long nodeSparseIndex = _nodesPerCharacter * c + (uint)nodeId; + int nodePlainIndex = _nodeMap.Rank1(nodeSparseIndex); + + if (nodePlainIndex != 0) + { + long foundNodeSparseIndex = _nodeMap.Select1Ex(nodePlainIndex - 1); + + if (foundNodeSparseIndex > 0 && foundNodeSparseIndex == nodeSparseIndex) + { + nodeId = nodePlainIndex; + + if (callback != null) + { + // Match full word. + if (_wordMap.Has(nodePlainIndex)) + { + int wordLength = _wordLengths[_wordMap.Rank1((uint)nodePlainIndex) - 1]; + int startIndex = index + 1 - wordLength; + + if (!callback(utf8Text, startIndex, index + 1, nodeId, ref state)) + { + return; + } + } + + // If this is a phrase composed of multiple words, also match each sub-word. + while (_multiWordMap.Has(nodePlainIndex)) + { + nodePlainIndex = _multiWordIndices[_multiWordMap.Rank1((uint)nodePlainIndex) - 1]; + + int wordLength = _wordMap.Has(nodePlainIndex) ? _wordLengths[_wordMap.Rank1(nodePlainIndex) - 1] : 0; + int startIndex = index + 1 - wordLength; + + if (!callback(utf8Text, startIndex, index + 1, nodePlainIndex, ref state)) + { + return; + } + } + } + + break; + } + } + + if (nodeId == 0) + { + break; + } + + int nodePos = _bp.ToPos(nodeId); + nodePos = _bp.Enclose(nodePos); + if (nodePos < 0) + { + return; + } + + nodeId = _bp.ToNodeId(nodePos); + } + } + } + + public void Match<T>(ReadOnlySpan<byte> utf8Text, MatchCallback<T> callback, ref T state) + { + int nodeId = 0; + + for (int index = 0; index < utf8Text.Length; index++) + { + long c = utf8Text[index]; + + while (true) + { + long nodeSparseIndex = _nodesPerCharacter * c + (uint)nodeId; + int nodePlainIndex = _nodeMap.Rank1(nodeSparseIndex); + + if (nodePlainIndex != 0) + { + long foundNodeSparseIndex = _nodeMap.Select1Ex(nodePlainIndex - 1); + + if (foundNodeSparseIndex > 0 && foundNodeSparseIndex == nodeSparseIndex) + { + nodeId = nodePlainIndex; + + if (callback != null) + { + // Match full word. + if (_wordMap.Has(nodePlainIndex)) + { + int wordLength = _wordLengths[_wordMap.Rank1((uint)nodePlainIndex) - 1]; + int startIndex = index + 1 - wordLength; + + if (!callback(utf8Text, startIndex, index + 1, nodeId, ref state)) + { + return; + } + } + + // If this is a phrase composed of multiple words, also match each sub-word. + while (_multiWordMap.Has(nodePlainIndex)) + { + nodePlainIndex = _multiWordIndices[_multiWordMap.Rank1((uint)nodePlainIndex) - 1]; + + int wordLength = _wordMap.Has(nodePlainIndex) ? _wordLengths[_wordMap.Rank1(nodePlainIndex) - 1] : 0; + int startIndex = index + 1 - wordLength; + + if (!callback(utf8Text, startIndex, index + 1, nodePlainIndex, ref state)) + { + return; + } + } + } + + break; + } + } + + if (nodeId == 0) + { + break; + } + + int nodePos = _bp.ToPos(nodeId); + nodePos = _bp.Enclose(nodePos); + if (nodePos < 0) + { + return; + } + + nodeId = _bp.ToNodeId(nodePos); + } + } + } + + public string GetWordList(bool includeMultiWord = true) + { + // Storage must be large enough to fit the largest word in the dictionary. + // Since this is only used for debugging, it's fine to increase the size manually if needed. + StringBuilder sb = new(); + Span<byte> storage = new byte[1024]; + + // Traverse trie from the root. + GetWord(sb, storage, 0, 0, includeMultiWord); + + return sb.ToString(); + } + + private void GetWord(StringBuilder sb, Span<byte> storage, int storageOffset, int nodeId, bool includeMultiWord) + { + int characters = (int)((_nodeMap.RangeEndValue + _nodesPerCharacter - 1) / _nodesPerCharacter); + + for (int c = 0; c < characters; c++) + { + long nodeSparseIndex = _nodesPerCharacter * c + (uint)nodeId; + int nodePlainIndex = _nodeMap.Rank1(nodeSparseIndex); + + if (nodePlainIndex != 0) + { + long foundNodeSparseIndex = _nodeMap.Select1Ex(nodePlainIndex - 1); + + if (foundNodeSparseIndex > 0 && foundNodeSparseIndex == nodeSparseIndex) + { + storage[storageOffset] = (byte)c; + int nextNodeId = nodePlainIndex; + + if (_wordMap.Has(nodePlainIndex)) + { + sb.AppendLine(Encoding.UTF8.GetString(storage[..(storageOffset + 1)])); + + // Some basic validation to ensure we imported the dictionary properly. + int wordLength = _wordLengths[_wordMap.Rank1((uint)nodePlainIndex) - 1]; + + Debug.Assert(storageOffset + 1 == wordLength); + } + + if (includeMultiWord) + { + int lastMultiWordIndex = 0; + string multiWord = ""; + + while (_multiWordMap.Has(nodePlainIndex)) + { + nodePlainIndex = _multiWordIndices[_multiWordMap.Rank1((uint)nodePlainIndex) - 1]; + + int wordLength = _wordMap.Has(nodePlainIndex) ? _wordLengths[_wordMap.Rank1(nodePlainIndex) - 1] : 0; + int startIndex = storageOffset + 1 - wordLength; + + multiWord += Encoding.UTF8.GetString(storage[lastMultiWordIndex..startIndex]) + " "; + lastMultiWordIndex = startIndex; + } + + if (lastMultiWordIndex != 0) + { + multiWord += Encoding.UTF8.GetString(storage[lastMultiWordIndex..(storageOffset + 1)]); + + sb.AppendLine(multiWord); + } + } + + GetWord(sb, storage, storageOffset + 1, nextNodeId, includeMultiWord); + } + } + } + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BinaryReader.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BinaryReader.cs new file mode 100644 index 00000000..5bad376a --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BinaryReader.cs @@ -0,0 +1,63 @@ +using System; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + ref struct BinaryReader + { + private readonly ReadOnlySpan<byte> _data; + private int _offset; + + public BinaryReader(ReadOnlySpan<byte> data) + { + _data = data; + } + + public bool Read<T>(out T value) where T : unmanaged + { + int byteLength = Unsafe.SizeOf<T>(); + + if ((uint)(_offset + byteLength) <= (uint)_data.Length) + { + value = MemoryMarshal.Cast<byte, T>(_data[_offset..])[0]; + _offset += byteLength; + + return true; + } + + value = default; + + return false; + } + + public int AllocateAndReadArray<T>(ref T[] array, int length, int maxLengthExclusive) where T : unmanaged + { + return AllocateAndReadArray(ref array, Math.Min(length, maxLengthExclusive)); + } + + public int AllocateAndReadArray<T>(ref T[] array, int length) where T : unmanaged + { + array = new T[length]; + + return ReadArray(array); + } + + public int ReadArray<T>(T[] array) where T : unmanaged + { + if (array != null) + { + int byteLength = array.Length * Unsafe.SizeOf<T>(); + byteLength = Math.Min(byteLength, _data.Length - _offset); + + MemoryMarshal.Cast<byte, T>(_data.Slice(_offset, byteLength)).CopyTo(array); + + _offset += byteLength; + + return byteLength / Unsafe.SizeOf<T>(); + } + + return 0; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BitVector32.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BitVector32.cs new file mode 100644 index 00000000..f5456201 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BitVector32.cs @@ -0,0 +1,78 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class BitVector32 + { + private const int BitsPerWord = Set.BitsPerWord; + + private int _bitLength; + private uint[] _array; + + public int BitLength => _bitLength; + public uint[] Array => _array; + + public BitVector32() + { + _bitLength = 0; + _array = null; + } + + public BitVector32(int length) + { + _bitLength = length; + _array = new uint[(length + BitsPerWord - 1) / BitsPerWord]; + } + + public bool Has(int index) + { + if ((uint)index < (uint)_bitLength) + { + int wordIndex = index / BitsPerWord; + int wordBitOffset = index % BitsPerWord; + + return ((_array[wordIndex] >> wordBitOffset) & 1u) != 0; + } + + return false; + } + + public bool TurnOn(int index, int count) + { + for (int bit = 0; bit < count; bit++) + { + if (!TurnOn(index + bit)) + { + return false; + } + } + + return true; + } + + public bool TurnOn(int index) + { + if ((uint)index < (uint)_bitLength) + { + int wordIndex = index / BitsPerWord; + int wordBitOffset = index % BitsPerWord; + + _array[wordIndex] |= 1u << wordBitOffset; + + return true; + } + + return false; + } + + public bool Import(ref BinaryReader reader) + { + if (!reader.Read(out _bitLength)) + { + return false; + } + + int arrayLength = (_bitLength + BitsPerWord - 1) / BitsPerWord; + + return reader.AllocateAndReadArray(ref _array, arrayLength) == arrayLength; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Bp.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Bp.cs new file mode 100644 index 00000000..5a8f3df2 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Bp.cs @@ -0,0 +1,54 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class Bp + { + private readonly BpNode _firstNode = new(); + private readonly SbvSelect _sbvSelect = new(); + + public bool Import(ref BinaryReader reader) + { + return _firstNode.Import(ref reader) && _sbvSelect.Import(ref reader); + } + + public int ToPos(int index) + { + return _sbvSelect.Select(_firstNode.Set, index); + } + + public int Enclose(int index) + { + if ((uint)index < (uint)_firstNode.Set.BitVector.BitLength) + { + if (!_firstNode.Set.Has(index)) + { + index = _firstNode.FindOpen(index); + } + + if (index > 0) + { + return _firstNode.Enclose(index); + } + } + + return -1; + } + + public int ToNodeId(int index) + { + if ((uint)index < (uint)_firstNode.Set.BitVector.BitLength) + { + if (!_firstNode.Set.Has(index)) + { + index = _firstNode.FindOpen(index); + } + + if (index >= 0) + { + return _firstNode.Set.Rank1(index) - 1; + } + } + + return -1; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BpNode.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BpNode.cs new file mode 100644 index 00000000..6884cddd --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/BpNode.cs @@ -0,0 +1,241 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class BpNode + { + private readonly Set _set = new(); + private SparseSet _sparseSet; + private BpNode _nextNode; + + public Set Set => _set; + + public bool Import(ref BinaryReader reader) + { + if (!_set.Import(ref reader)) + { + return false; + } + + if (!reader.Read(out byte hasNext)) + { + return false; + } + + if (hasNext == 0) + { + return true; + } + + _sparseSet = new(); + _nextNode = new(); + + return _sparseSet.Import(ref reader) && _nextNode.Import(ref reader); + } + + public int FindOpen(int index) + { + uint membershipBits = _set.BitVector.Array[index / Set.BitsPerWord]; + + int wordBitOffset = index % Set.BitsPerWord; + int unsetBits = 1; + + for (int bit = wordBitOffset - 1; bit >= 0; bit--) + { + if (((membershipBits >> bit) & 1) != 0) + { + if (--unsetBits == 0) + { + return (index & ~(Set.BitsPerWord - 1)) | bit; + } + } + else + { + unsetBits++; + } + } + + int plainIndex = _sparseSet.Rank1(index); + if (plainIndex == 0) + { + return -1; + } + + int newIndex = index; + + if (!_sparseSet.Has(index)) + { + if (plainIndex == 0 || _nextNode == null) + { + return -1; + } + + newIndex = _sparseSet.Select1(plainIndex); + if (newIndex < 0) + { + return -1; + } + } + else + { + plainIndex--; + } + + int openIndex = _nextNode.FindOpen(plainIndex); + if (openIndex < 0) + { + return -1; + } + + int openSparseIndex = _sparseSet.Select1(openIndex); + if (openSparseIndex < 0) + { + return -1; + } + + if (newIndex != index) + { + unsetBits = 1; + + for (int bit = newIndex % Set.BitsPerWord - 1; bit > wordBitOffset; bit--) + { + unsetBits += ((membershipBits >> bit) & 1) != 0 ? -1 : 1; + } + + int bestCandidate = -1; + + membershipBits = _set.BitVector.Array[openSparseIndex / Set.BitsPerWord]; + + for (int bit = openSparseIndex % Set.BitsPerWord + 1; bit < Set.BitsPerWord; bit++) + { + if (unsetBits - 1 == 0) + { + bestCandidate = bit; + } + + unsetBits += ((membershipBits >> bit) & 1) != 0 ? -1 : 1; + } + + return (openSparseIndex & ~(Set.BitsPerWord - 1)) | bestCandidate; + } + else + { + return openSparseIndex; + } + } + + public int Enclose(int index) + { + uint membershipBits = _set.BitVector.Array[index / Set.BitsPerWord]; + + int unsetBits = 1; + + for (int bit = index % Set.BitsPerWord - 1; bit >= 0; bit--) + { + if (((membershipBits >> bit) & 1) != 0) + { + if (--unsetBits == 0) + { + return (index & ~(Set.BitsPerWord - 1)) + bit; + } + } + else + { + unsetBits++; + } + } + + int setBits = 2; + + for (int bit = index % Set.BitsPerWord + 1; bit < Set.BitsPerWord; bit++) + { + if (((membershipBits >> bit) & 1) != 0) + { + setBits++; + } + else + { + if (--setBits == 0) + { + return FindOpen((index & ~(Set.BitsPerWord - 1)) + bit); + } + } + } + + int newIndex = index; + + if (!_sparseSet.Has(index)) + { + newIndex = _sparseSet.Select1(_sparseSet.Rank1(index)); + if (newIndex < 0) + { + return -1; + } + } + + if (!_set.Has(newIndex)) + { + newIndex = FindOpen(newIndex); + if (newIndex < 0) + { + return -1; + } + } + else + { + newIndex = _nextNode.Enclose(_sparseSet.Rank1(newIndex) - 1); + if (newIndex < 0) + { + return -1; + } + + newIndex = _sparseSet.Select1(newIndex); + } + + int nearestIndex = _sparseSet.Select1(_sparseSet.Rank1(newIndex)); + if (nearestIndex < 0) + { + return -1; + } + + setBits = 0; + + membershipBits = _set.BitVector.Array[newIndex / Set.BitsPerWord]; + + if ((newIndex / Set.BitsPerWord) == (nearestIndex / Set.BitsPerWord)) + { + for (int bit = nearestIndex % Set.BitsPerWord - 1; bit >= newIndex % Set.BitsPerWord; bit--) + { + if (((membershipBits >> bit) & 1) != 0) + { + if (++setBits > 0) + { + return (newIndex & ~(Set.BitsPerWord - 1)) + bit; + } + } + else + { + setBits--; + } + } + } + else + { + for (int bit = Set.BitsPerWord - 1; bit >= newIndex % Set.BitsPerWord; bit--) + { + if (((membershipBits >> bit) & 1) != 0) + { + if (++setBits > 0) + { + return (newIndex & ~(Set.BitsPerWord - 1)) + bit; + } + } + else + { + setBits--; + } + } + } + + return -1; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/CompressedArray.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/CompressedArray.cs new file mode 100644 index 00000000..1200f1de --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/CompressedArray.cs @@ -0,0 +1,100 @@ +using System; +using System.Runtime.InteropServices; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class CompressedArray + { + private const int MaxUncompressedEntries = 64; + private const int CompressedEntriesPerBlock = 64; + private const int BitsPerWord = Set.BitsPerWord; + + private readonly struct BitfieldRange + { + private readonly uint _range; + private readonly int _baseValue; + + public int BitfieldIndex => (int)(_range & 0x7ffffff); + public int BitfieldLength => (int)(_range >> 27) + 1; + public int BaseValue => _baseValue; + + public BitfieldRange(uint range, int baseValue) + { + _range = range; + _baseValue = baseValue; + } + } + + private uint[] _bitfieldRanges; + private uint[] _bitfields; + private int[] _uncompressedArray; + + public int Length => (_bitfieldRanges.Length / 2) * CompressedEntriesPerBlock + _uncompressedArray.Length; + + public int this[int index] + { + get + { + var ranges = GetBitfieldRanges(); + + int rangeBlockIndex = index / CompressedEntriesPerBlock; + + if (rangeBlockIndex < ranges.Length) + { + var range = ranges[rangeBlockIndex]; + + int bitfieldLength = range.BitfieldLength; + int bitfieldOffset = (index % CompressedEntriesPerBlock) * bitfieldLength; + int bitfieldIndex = range.BitfieldIndex + (bitfieldOffset / BitsPerWord); + int bitOffset = bitfieldOffset % BitsPerWord; + + ulong bitfieldValue = _bitfields[bitfieldIndex]; + + // If the bit fields crosses the word boundary, let's load the next one to ensure we + // have access to the full value. + if (bitOffset + bitfieldLength > BitsPerWord) + { + bitfieldValue |= (ulong)_bitfields[bitfieldIndex + 1] << 32; + } + + int value = (int)(bitfieldValue >> bitOffset) & ((1 << bitfieldLength) - 1); + + // Sign-extend. + int remainderBits = BitsPerWord - bitfieldLength; + value <<= remainderBits; + value >>= remainderBits; + + return value + range.BaseValue; + } + else if (rangeBlockIndex < _uncompressedArray.Length + _bitfieldRanges.Length * BitsPerWord) + { + return _uncompressedArray[index % MaxUncompressedEntries]; + } + + return 0; + } + } + + private ReadOnlySpan<BitfieldRange> GetBitfieldRanges() + { + return MemoryMarshal.Cast<uint, BitfieldRange>(_bitfieldRanges); + } + + public bool Import(ref BinaryReader reader) + { + if (!reader.Read(out int bitfieldRangesCount) || + reader.AllocateAndReadArray(ref _bitfieldRanges, bitfieldRangesCount) != bitfieldRangesCount) + { + return false; + } + + if (!reader.Read(out int bitfieldsCount) || reader.AllocateAndReadArray(ref _bitfields, bitfieldsCount) != bitfieldsCount) + { + return false; + } + + return reader.Read(out byte uncompressedArrayLength) && + reader.AllocateAndReadArray(ref _uncompressedArray, uncompressedArrayLength, MaxUncompressedEntries) == uncompressedArrayLength; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ContentsReader.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ContentsReader.cs new file mode 100644 index 00000000..cb865fa0 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ContentsReader.cs @@ -0,0 +1,404 @@ +using Ryujinx.Horizon.Common; +using Ryujinx.Horizon.Sdk.Fs; +using System; +using System.IO; +using System.IO.Compression; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class ContentsReader : IDisposable + { + private const string MountName = "NgWord"; + private const string VersionFilePath = $"{MountName}:/version.dat"; + private const ulong DataId = 0x100000000000823UL; + + private enum AcType + { + AcNotB, + AcB1, + AcB2, + AcSimilarForm, + TableSimilarForm, + } + + private readonly IFsClient _fsClient; + private readonly object _lock; + private bool _intialized; + private ulong _cacheSize; + + public ContentsReader(IFsClient fsClient) + { + _lock = new(); + _fsClient = fsClient; + } + + private static void MakeMountPoint(out string path, AcType type, int regionIndex) + { + path = null; + + switch (type) + { + case AcType.AcNotB: + if (regionIndex < 0) + { + path = $"{MountName}:/ac_common_not_b_nx"; + } + else + { + path = $"{MountName}:/ac_{regionIndex}_not_b_nx"; + } + break; + case AcType.AcB1: + if (regionIndex < 0) + { + path = $"{MountName}:/ac_common_b1_nx"; + } + else + { + path = $"{MountName}:/ac_{regionIndex}_b1_nx"; + } + break; + case AcType.AcB2: + if (regionIndex < 0) + { + path = $"{MountName}:/ac_common_b2_nx"; + } + else + { + path = $"{MountName}:/ac_{regionIndex}_b2_nx"; + } + break; + case AcType.AcSimilarForm: + path = $"{MountName}:/ac_similar_form_nx"; + break; + case AcType.TableSimilarForm: + path = $"{MountName}:/table_similar_form_nx"; + break; + } + } + + public Result Initialize(ulong cacheSize) + { + lock (_lock) + { + if (_intialized) + { + return Result.Success; + } + + Result result = _fsClient.QueryMountSystemDataCacheSize(out long dataCacheSize, DataId); + if (result.IsFailure) + { + return result; + } + + if (cacheSize < (ulong)dataCacheSize) + { + return NgcResult.InvalidSize; + } + + result = _fsClient.MountSystemData(MountName, DataId); + if (result.IsFailure) + { + // Official firmware would return the result here, + // we don't to support older firmware where the archive didn't exist yet. + return Result.Success; + } + + _cacheSize = cacheSize; + _intialized = true; + + return Result.Success; + } + } + + public Result Reload() + { + lock (_lock) + { + if (!_intialized) + { + return Result.Success; + } + + _fsClient.Unmount(MountName); + + Result result = Result.Success; + + try + { + result = _fsClient.QueryMountSystemDataCacheSize(out long cacheSize, DataId); + if (result.IsFailure) + { + return result; + } + + if (_cacheSize < (ulong)cacheSize) + { + result = NgcResult.InvalidSize; + return NgcResult.InvalidSize; + } + + result = _fsClient.MountSystemData(MountName, DataId); + if (result.IsFailure) + { + return result; + } + } + finally + { + if (result.IsFailure) + { + _intialized = false; + _cacheSize = 0; + } + } + } + + return Result.Success; + } + + private Result GetFileSize(out long size, string filePath) + { + size = 0; + + lock (_lock) + { + Result result = _fsClient.OpenFile(out FileHandle handle, filePath, OpenMode.Read); + if (result.IsFailure) + { + return result; + } + + try + { + result = _fsClient.GetFileSize(out size, handle); + if (result.IsFailure) + { + return result; + } + } + finally + { + _fsClient.CloseFile(handle); + } + } + + return Result.Success; + } + + private Result GetFileContent(Span<byte> destination, string filePath) + { + lock (_lock) + { + Result result = _fsClient.OpenFile(out FileHandle handle, filePath, OpenMode.Read); + if (result.IsFailure) + { + return result; + } + + try + { + result = _fsClient.ReadFile(handle, 0, destination); + if (result.IsFailure) + { + return result; + } + } + finally + { + _fsClient.CloseFile(handle); + } + } + + return Result.Success; + } + + public Result GetVersionDataSize(out long size) + { + return GetFileSize(out size, VersionFilePath); + } + + public Result GetVersionData(Span<byte> destination) + { + return GetFileContent(destination, VersionFilePath); + } + + public Result ReadDictionaries(out AhoCorasick partialWordsTrie, out AhoCorasick completeWordsTrie, out AhoCorasick delimitedWordsTrie, int regionIndex) + { + completeWordsTrie = null; + delimitedWordsTrie = null; + + MakeMountPoint(out string partialWordsTriePath, AcType.AcNotB, regionIndex); + MakeMountPoint(out string completeWordsTriePath, AcType.AcB1, regionIndex); + MakeMountPoint(out string delimitedWordsTriePath, AcType.AcB2, regionIndex); + + Result result = ReadDictionary(out partialWordsTrie, partialWordsTriePath); + if (result.IsFailure) + { + return NgcResult.DataAccessError; + } + + result = ReadDictionary(out completeWordsTrie, completeWordsTriePath); + if (result.IsFailure) + { + return NgcResult.DataAccessError; + } + + return ReadDictionary(out delimitedWordsTrie, delimitedWordsTriePath); + } + + public Result ReadSimilarFormDictionary(out AhoCorasick similarFormTrie) + { + MakeMountPoint(out string similarFormTriePath, AcType.AcSimilarForm, 0); + + return ReadDictionary(out similarFormTrie, similarFormTriePath); + } + + public Result ReadSimilarFormTable(out SimilarFormTable similarFormTable) + { + similarFormTable = null; + + MakeMountPoint(out string similarFormTablePath, AcType.TableSimilarForm, 0); + + Result result = ReadGZipCompressedArchive(out byte[] data, similarFormTablePath); + if (result.IsFailure) + { + return result; + } + + BinaryReader reader = new(data); + SimilarFormTable table = new(); + + if (!table.Import(ref reader)) + { + // Official firmware doesn't return an error here and just assumes the import was successful. + return NgcResult.DataAccessError; + } + + similarFormTable = table; + + return Result.Success; + } + + public static Result ReadNotSeparatorDictionary(out AhoCorasick notSeparatorTrie) + { + notSeparatorTrie = null; + + BinaryReader reader = new(EmbeddedTries.NotSeparatorTrie); + AhoCorasick ac = new(); + + if (!ac.Import(ref reader)) + { + // Official firmware doesn't return an error here and just assumes the import was successful. + return NgcResult.DataAccessError; + } + + notSeparatorTrie = ac; + + return Result.Success; + } + + private Result ReadDictionary(out AhoCorasick trie, string path) + { + trie = null; + + Result result = ReadGZipCompressedArchive(out byte[] data, path); + if (result.IsFailure) + { + return result; + } + + BinaryReader reader = new(data); + AhoCorasick ac = new(); + + if (!ac.Import(ref reader)) + { + // Official firmware doesn't return an error here and just assumes the import was successful. + return NgcResult.DataAccessError; + } + + trie = ac; + + return Result.Success; + } + + private Result ReadGZipCompressedArchive(out byte[] data, string filePath) + { + data = null; + + Result result = _fsClient.OpenFile(out FileHandle handle, filePath, OpenMode.Read); + if (result.IsFailure) + { + return result; + } + + try + { + result = _fsClient.GetFileSize(out long fileSize, handle); + if (result.IsFailure) + { + return result; + } + + data = new byte[fileSize]; + + result = _fsClient.ReadFile(handle, 0, data.AsSpan()); + if (result.IsFailure) + { + return result; + } + } + finally + { + _fsClient.CloseFile(handle); + } + + try + { + data = DecompressGZipCompressedStream(data); + } + catch (InvalidDataException) + { + // Official firmware returns a different error, but it is translated to this error on the caller. + return NgcResult.DataAccessError; + } + + return Result.Success; + } + + private static byte[] DecompressGZipCompressedStream(byte[] data) + { + using MemoryStream input = new(data); + using GZipStream gZipStream = new(input, CompressionMode.Decompress); + using MemoryStream output = new(); + + gZipStream.CopyTo(output); + + return output.ToArray(); + } + + protected virtual void Dispose(bool disposing) + { + if (disposing) + { + lock (_lock) + { + if (!_intialized) + { + return; + } + + _fsClient.Unmount(MountName); + _intialized = false; + } + } + } + + public void Dispose() + { + Dispose(disposing: true); + GC.SuppressFinalize(this); + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/EmbeddedTries.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/EmbeddedTries.cs new file mode 100644 index 00000000..37ee43fa --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/EmbeddedTries.cs @@ -0,0 +1,266 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + static class EmbeddedTries + { + public static ReadOnlySpan<byte> NotSeparatorTrie => new byte[] + { + 0x1A, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x06, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x09, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x0C, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x0F, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x12, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x15, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x18, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x1B, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x1E, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x21, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x24, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, + 0xE9, 0xFF, 0xE9, 0xFF, 0xF4, 0xFF, 0xFA, 0xBF, 0x00, 0x00, 0x00, 0x00, 0xFE, 0x5F, 0xFF, 0xAF, + 0xFF, 0xEB, 0xFF, 0xFA, 0x00, 0x00, 0x00, 0x00, 0xBF, 0xFF, 0xFB, 0x7F, 0xFF, 0xEF, 0xFF, 0xFD, + 0x00, 0x00, 0x00, 0x00, 0xBF, 0xFF, 0xF7, 0xFF, 0xE8, 0xFF, 0xE9, 0xFF, 0x00, 0x00, 0x00, 0x00, + 0xFC, 0x3F, 0xFF, 0xCF, 0xFF, 0xF3, 0xFF, 0xFA, 0x00, 0x00, 0x00, 0x00, 0x3F, 0xFF, 0xE7, 0xFF, + 0xFC, 0x9F, 0xFF, 0xF3, 0x00, 0x00, 0x00, 0x00, 0x7F, 0xFE, 0x9F, 0xFF, 0xE7, 0xFF, 0xF9, 0x7F, + 0x00, 0x00, 0x00, 0x00, 0xFE, 0x5F, 0xFF, 0xCF, 0xFF, 0xF3, 0xFF, 0xFC, 0x00, 0x00, 0x00, 0x00, + 0x3F, 0xFF, 0xCF, 0xFF, 0xF3, 0xFF, 0xFC, 0x3F, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xCF, 0xFF, 0xF3, + 0xFF, 0xFC, 0x3F, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xCF, 0xFF, 0xFB, 0x7F, 0xFE, 0x9F, 0xFF, 0xF3, + 0x00, 0x00, 0x00, 0x00, 0x7F, 0xFE, 0x9F, 0xFF, 0xF3, 0xFF, 0xFC, 0x9F, 0x00, 0x00, 0x00, 0x00, + 0xFF, 0xF3, 0x7F, 0xFE, 0xCF, 0xFF, 0xF5, 0x7F, 0x00, 0x00, 0x00, 0x00, 0x2E, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, + 0x00, 0x03, 0x00, 0x00, 0x00, 0x8A, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x85, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6E, 0x03, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, + 0x00, 0xAA, 0xAA, 0xAA, 0xAA, 0x54, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, + 0x55, 0x55, 0x55, 0xA9, 0x52, 0x55, 0x55, 0xA9, 0xAA, 0xAA, 0xAA, 0x54, 0x55, 0x55, 0x55, 0x55, + 0x55, 0x55, 0xAA, 0x54, 0x55, 0xA5, 0x4A, 0x55, 0x55, 0x55, 0xAA, 0xAA, 0xAA, 0x52, 0x55, 0x55, + 0x95, 0xAA, 0xAA, 0xAA, 0x54, 0x55, 0x55, 0xA5, 0xAA, 0xAA, 0x2A, 0x55, 0x55, 0x55, 0x55, 0x55, + 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0xA5, 0xAA, 0xAA, 0xAA, 0x54, 0x55, 0x55, 0x55, 0x55, 0x55, + 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, + 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, + 0x55, 0x55, 0x55, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0x4A, + 0x55, 0x55, 0x55, 0xA9, 0xAA, 0xAA, 0x52, 0x55, 0x55, 0xA5, 0xAA, 0xAA, 0x4A, 0x55, 0x55, 0x05, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x7D, 0x00, 0x00, 0x00, 0xF8, 0x00, 0x00, 0x00, 0x77, 0x01, 0x00, + 0x00, 0xF7, 0x01, 0x00, 0x00, 0x77, 0x02, 0x00, 0x00, 0xF7, 0x02, 0x00, 0x00, 0x6E, 0x03, 0x00, + 0x00, 0x6E, 0x03, 0x00, 0x00, 0x6E, 0x03, 0x00, 0x00, 0x6E, 0x03, 0x00, 0x00, 0x6E, 0x03, 0x00, + 0x00, 0x6E, 0x03, 0x00, 0x00, 0x6E, 0x03, 0x00, 0x00, 0x6E, 0x03, 0x00, 0x00, 0x6E, 0x03, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x1F, 0x2F, 0x3F, 0x4E, 0x5E, 0x6D, 0x00, 0x0F, 0x1E, + 0x2E, 0x3D, 0x4C, 0x5C, 0x6B, 0x00, 0x10, 0x20, 0x2F, 0x3F, 0x4F, 0x5F, 0x6F, 0x00, 0x10, 0x20, + 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, + 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, 0x30, 0x3F, 0x4F, 0x5E, 0x6D, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x38, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6E, 0x03, + 0x00, 0x00, 0x01, 0x00, 0x01, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x40, 0x00, 0x40, 0x00, 0x20, + 0x00, 0x20, 0x00, 0x10, 0x00, 0x08, 0x00, 0x08, 0x00, 0x04, 0x00, 0x02, 0x00, 0x02, 0x00, 0x01, + 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, + 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, + 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, + 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, + 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x80, 0x00, 0x40, 0x00, 0x40, 0x00, 0x20, 0x00, 0x10, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x11, 0x00, 0x00, 0x00, + 0x21, 0x00, 0x00, 0x00, 0x31, 0x00, 0x00, 0x00, 0x00, 0x03, 0x05, 0x07, 0x09, 0x0B, 0x0D, 0x0F, + 0x00, 0x02, 0x04, 0x06, 0x08, 0x0A, 0x0C, 0x0E, 0x00, 0x02, 0x04, 0x06, 0x08, 0x0A, 0x0C, 0x0E, + 0x00, 0x02, 0x04, 0x06, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x8A, 0x03, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x8A, 0x03, 0x00, 0x00, 0x00, 0x8A, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4F, 0xC5, 0x01, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x60, 0x51, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x89, 0x03, 0x00, + 0x00, 0x07, 0x00, 0x00, 0x00, 0xC6, 0x00, 0x00, 0x00, 0xCF, 0xED, 0x81, 0x61, 0xD9, 0xDC, 0x8A, + 0xD3, 0xF0, 0xBB, 0x05, 0x6E, 0xEB, 0x0D, 0x88, 0x6C, 0x39, 0x62, 0x01, 0x95, 0x82, 0xCF, 0xEE, + 0x3A, 0x7F, 0x53, 0xDF, 0x09, 0x90, 0xF7, 0x06, 0xA4, 0x7A, 0x2D, 0xB3, 0xE7, 0xFA, 0x20, 0x48, + 0x0F, 0x38, 0x34, 0xED, 0xBC, 0x8A, 0x96, 0xAB, 0x8E, 0xE3, 0xFF, 0xC6, 0xD2, 0xBF, 0xC0, 0x90, + 0x06, 0x34, 0xDF, 0xF0, 0xDB, 0xDE, 0x27, 0x2E, 0xD5, 0x3C, 0xA2, 0x22, 0x72, 0xBD, 0x02, 0x0D, + 0x1F, 0xB2, 0x99, 0xBE, 0x17, 0x26, 0xA1, 0xEF, 0x40, 0xF2, 0x61, 0xE1, 0x16, 0x17, 0xA4, 0xF4, + 0x3A, 0x0F, 0x3C, 0x3A, 0xAB, 0x74, 0x83, 0x93, 0xB2, 0x09, 0x43, 0x52, 0x6E, 0xB8, 0xBF, 0xC8, + 0x9C, 0x6A, 0x73, 0xD3, 0x0C, 0xC8, 0x5C, 0x71, 0xCD, 0x87, 0xCA, 0x28, 0xF6, 0xEB, 0x87, 0x60, + 0x3D, 0xA5, 0x15, 0x9B, 0xAA, 0x99, 0x23, 0x9F, 0xD6, 0x2E, 0x79, 0x58, 0xE9, 0x8E, 0x54, 0xB0, + 0xF8, 0x07, 0x6F, 0x6C, 0x52, 0xB7, 0xE2, 0x34, 0x42, 0x8C, 0x7A, 0xD5, 0xEC, 0xA4, 0xFE, 0x52, + 0x9A, 0x05, 0x9F, 0xDD, 0x8D, 0x73, 0x8B, 0xA6, 0xDB, 0xA7, 0x84, 0xD0, 0xAB, 0xB7, 0xCC, 0x9E, + 0x4B, 0xD8, 0xB2, 0xDC, 0x0F, 0xE8, 0x3A, 0x56, 0xB9, 0x63, 0x75, 0x1C, 0x7F, 0x89, 0xDF, 0x7C, + 0x84, 0xE2, 0x8C, 0xA9, 0x0D, 0xA3, 0xDF, 0xF6, 0x3E, 0xC7, 0xCE, 0x1B, 0x24, 0x94, 0xB8, 0xE8, + 0xD7, 0xDC, 0xA6, 0xEF, 0x85, 0xA1, 0x7D, 0x00, 0xE1, 0x78, 0xD4, 0x8B, 0x13, 0xCB, 0xB6, 0x4B, + 0x5E, 0xCB, 0xF3, 0xC0, 0xA3, 0x09, 0x68, 0x68, 0x4C, 0xF4, 0x98, 0x0D, 0x38, 0x0D, 0xBF, 0xFB, + 0x8B, 0xCC, 0x55, 0x71, 0x21, 0xC1, 0xFC, 0x3B, 0x60, 0x77, 0x9D, 0x3F, 0x54, 0x46, 0x61, 0x4A, + 0xC8, 0xA5, 0xDB, 0x21, 0x8A, 0xCA, 0x73, 0x7D, 0x10, 0xF9, 0xB4, 0xD6, 0x9E, 0x15, 0x8E, 0x58, + 0x94, 0x3C, 0xA9, 0xF1, 0x7F, 0x63, 0x93, 0xBA, 0xD5, 0x51, 0x35, 0xA1, 0x93, 0x93, 0xF5, 0xEE, + 0x13, 0x97, 0xD2, 0x2C, 0xF8, 0x97, 0xFD, 0x98, 0x58, 0xD3, 0x6A, 0x8C, 0x2E, 0x4C, 0x42, 0xAF, + 0xDE, 0x32, 0xC1, 0x4B, 0x5A, 0x61, 0x6D, 0xF9, 0xA3, 0xB3, 0xCA, 0x1D, 0xAB, 0x13, 0xE3, 0x14, + 0xAC, 0xBB, 0xF3, 0x33, 0xA7, 0xDA, 0x30, 0xFA, 0xED, 0x40, 0xBB, 0x6A, 0x62, 0xC0, 0x30, 0x8A, + 0xFD, 0x9A, 0xDB, 0xF4, 0x49, 0x7B, 0xA6, 0x3B, 0x17, 0x90, 0xD6, 0x2E, 0x79, 0x2D, 0xCF, 0x63, + 0xE4, 0xB8, 0x1F, 0x5B, 0xD1, 0xDC, 0x8A, 0xD3, 0xF0, 0xBB, 0xBF, 0x73, 0xEF, 0x11, 0xE2, 0x0F, + 0x29, 0xF8, 0xEC, 0xAE, 0xF3, 0x07, 0x5B, 0x11, 0x5F, 0x90, 0xB0, 0x53, 0xAE, 0x65, 0xF6, 0x5C, + 0x1F, 0x44, 0x80, 0x4F, 0xC1, 0x83, 0x63, 0x9F, 0xE1, 0xAA, 0xE3, 0xF8, 0xBF, 0xB1, 0x51, 0x66, + 0x19, 0x19, 0x13, 0xA0, 0xF7, 0x6D, 0xEF, 0x13, 0x97, 0x12, 0x75, 0xAC, 0xB7, 0x8C, 0x60, 0x3F, + 0xC5, 0x71, 0x9B, 0xBE, 0x17, 0x26, 0xA1, 0x97, 0xB7, 0x0D, 0x6A, 0xE9, 0x28, 0x99, 0x68, 0x79, + 0x1E, 0x78, 0x74, 0x56, 0x39, 0xF4, 0x5D, 0x75, 0x23, 0x7A, 0xB6, 0xEF, 0xFE, 0x22, 0x73, 0xAA, + 0x0D, 0xE5, 0x01, 0x5A, 0xD0, 0x89, 0x2A, 0xE7, 0x0F, 0x95, 0x51, 0xEC, 0xD7, 0xE4, 0x2F, 0x7C, + 0x4B, 0xAC, 0xEC, 0x3D, 0x88, 0x7C, 0x5A, 0xBB, 0xE4, 0xD5, 0x50, 0x41, 0x56, 0xC5, 0xBC, 0x7C, + 0x63, 0x93, 0xBA, 0x15, 0xA7, 0x61, 0xC8, 0x47, 0xFA, 0x65, 0x1B, 0x07, 0x97, 0xD2, 0x2C, 0xF8, + 0xEC, 0xAE, 0x35, 0x29, 0x6E, 0xDA, 0x0E, 0x6D, 0x84, 0x5E, 0xBD, 0x65, 0xF6, 0x5C, 0x27, 0xCD, + 0xCC, 0x73, 0x80, 0xF6, 0xB2, 0xCA, 0x1D, 0xAB, 0xE3, 0xF8, 0xDF, 0xD5, 0x83, 0xF7, 0x15, 0xE4, + 0x50, 0x6D, 0x18, 0xFD, 0xB6, 0xF7, 0x09, 0xDC, 0x51, 0x7F, 0xA0, 0xB8, 0x57, 0xB0, 0x5F, 0x73, + 0x9B, 0xBE, 0x17, 0x26, 0x42, 0x42, 0xC4, 0x83, 0xAF, 0xE9, 0x92, 0xD7, 0xF2, 0x3C, 0xF0, 0xE8, + 0x30, 0x1D, 0x1B, 0x94, 0xE0, 0x47, 0x9C, 0x86, 0xDF, 0xFD, 0x45, 0xE6, 0x64, 0xC5, 0x94, 0x64, + 0x8C, 0xA4, 0xB3, 0xBB, 0xCE, 0x1F, 0x2A, 0xA3, 0x18, 0x58, 0xF4, 0xE2, 0x59, 0xA6, 0xD8, 0x73, + 0x7D, 0x10, 0xF9, 0xB4, 0x76, 0x6A, 0x56, 0xCE, 0xD8, 0x15, 0xC7, 0xFF, 0x8D, 0x4D, 0xEA, 0x56, + 0xA4, 0xDB, 0x86, 0x50, 0xD5, 0x99, 0xBD, 0x4F, 0x5C, 0x4A, 0xB3, 0xE0, 0xD3, 0x0F, 0x6C, 0x6A, + 0x69, 0x71, 0x7B, 0x21, 0xF4, 0xEA, 0x2D, 0xB3, 0x08, 0xE5, 0x95, 0xEC, 0xDB, 0x03, 0x1E, 0xAB, + 0xDC, 0xB1, 0x3A, 0x96, 0x50, 0xC3, 0x6E, 0x64, 0x41, 0x91, 0xA9, 0x0D, 0xA3, 0xDF, 0x36, 0x27, + 0xEA, 0x5D, 0xE3, 0xA5, 0x0F, 0xCA, 0xE8, 0xD7, 0xDC, 0xA6, 0xEF, 0x26, 0x74, 0x5D, 0xC0, 0xCD, + 0x78, 0x5A, 0xC9, 0x6B, 0x79, 0x1E, 0x80, 0xC9, 0xFF, 0x8C, 0x96, 0x79, 0x84, 0xBA, 0x4D, 0xC3, + 0xEF, 0xFE, 0x42, 0xC7, 0x4F, 0x58, 0xE0, 0x2D, 0x59, 0xB0, 0xBB, 0xCE, 0x1F, 0x2A, 0x44, 0xC3, + 0x04, 0xA4, 0xBF, 0xF1, 0x96, 0xE7, 0xFA, 0x20, 0xF2, 0x71, 0x42, 0x3A, 0x2A, 0x42, 0xD0, 0x58, + 0x8D, 0xFF, 0x1B, 0x9B, 0x14, 0x56, 0x73, 0xA2, 0x39, 0x96, 0xD0, 0xEF, 0x3E, 0x71, 0x29, 0xCD, + 0xC4, 0xA4, 0x98, 0x6F, 0x89, 0xE9, 0x54, 0xB5, 0xE9, 0xC2, 0x24, 0xF4, 0xEA, 0xB1, 0x5D, 0x3B, + 0x64, 0x55, 0x44, 0x9E, 0x3F, 0x3A, 0xAB, 0xDC, 0xD1, 0x8E, 0x2B, 0x4A, 0xBF, 0x2C, 0x77, 0x3F, + 0x73, 0xAA, 0x0D, 0xA3, 0x00, 0xE1, 0x93, 0x9B, 0xB6, 0xE1, 0x0F, 0xA3, 0xD8, 0xAF, 0xB9, 0x55, + 0x30, 0xB3, 0xE6, 0x39, 0x50, 0xD0, 0xDA, 0x25, 0xAF, 0x65, 0x8A, 0x75, 0x0C, 0xEF, 0x53, 0xBD, + 0x60, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xEC, 0xBF, 0x70, 0xEF, 0xBF, 0xB0, 0xFB, 0x37, 0xF4, 0xFD, + 0x0D, 0xDD, 0xDF, 0x85, 0xEF, 0xEF, 0x89, 0xF7, 0xFB, 0xC4, 0xFB, 0x3E, 0x78, 0xF7, 0x13, 0xDF, + 0x7D, 0xC5, 0xB7, 0x5F, 0xF8, 0xF6, 0x0B, 0x5F, 0x7F, 0xE1, 0xED, 0x2F, 0xDC, 0xFD, 0x85, 0xBD, + 0xDF, 0xD0, 0xF7, 0xDF, 0xC1, 0xF7, 0x77, 0xF0, 0x7D, 0x0F, 0xBE, 0xEF, 0x83, 0xEF, 0xFB, 0xE0, + 0xBD, 0x1F, 0xBC, 0xF7, 0x0B, 0x77, 0xBF, 0x70, 0xF7, 0x0B, 0xD7, 0xBF, 0x70, 0xFD, 0x0B, 0xD7, + 0xBF, 0xB0, 0xFD, 0x1D, 0xBA, 0xDF, 0x83, 0xF7, 0x7B, 0x70, 0xDF, 0x87, 0xDE, 0xF7, 0x83, 0xFB, + 0xFE, 0xE0, 0xDE, 0x2F, 0xDC, 0xFD, 0x85, 0xDB, 0xDF, 0x70, 0xFB, 0x1B, 0xAE, 0x7F, 0xC3, 0xF5, + 0x6F, 0xD8, 0xFE, 0x0D, 0xDB, 0xDF, 0xA1, 0xFB, 0x3B, 0x78, 0xBF, 0x07, 0xF7, 0xF7, 0xE0, 0x7E, + 0x1F, 0xDC, 0xF7, 0x83, 0x7B, 0x3F, 0xB8, 0xF7, 0x07, 0x77, 0xBF, 0x70, 0xFB, 0x0B, 0xD7, 0xBF, + 0xF0, 0xFA, 0x17, 0xB6, 0xBF, 0x61, 0xF7, 0x37, 0x74, 0xBF, 0x83, 0xF7, 0x3D, 0xB8, 0xDF, 0x83, + 0xFB, 0x3E, 0x78, 0xDF, 0x0F, 0xDE, 0xFD, 0xE0, 0xDD, 0x17, 0xDE, 0x7E, 0xE1, 0xF5, 0x0B, 0x0F, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20, 0x20, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x52, 0x00, 0x00, 0x00, 0xFE, 0x00, 0x00, 0x00, 0xA8, 0x01, 0x00, + 0x00, 0x53, 0x02, 0x00, 0x00, 0xFD, 0x02, 0x00, 0x00, 0x86, 0x03, 0x00, 0x00, 0x88, 0x03, 0x00, + 0x00, 0x89, 0x03, 0x00, 0x00, 0x89, 0x03, 0x00, 0x00, 0x89, 0x03, 0x00, 0x00, 0x89, 0x03, 0x00, + 0x00, 0x89, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0F, 0x27, 0x3B, 0x00, 0x18, 0x2B, 0x42, 0x57, 0x6D, 0x81, + 0x98, 0x00, 0x17, 0x2B, 0x42, 0x56, 0x6D, 0x80, 0x97, 0x00, 0x17, 0x2B, 0x43, 0x56, 0x6D, 0x80, + 0x97, 0x00, 0x16, 0x2B, 0x40, 0x55, 0x69, 0x80, 0x94, 0x00, 0x13, 0x29, 0x3E, 0x52, 0x68, 0x7C, + 0x89, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x1C, 0x00, + 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x25, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x2D, 0x00, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x18, 0x00, 0x00, 0x89, 0x03, 0x00, 0x00, 0x01, 0x80, + 0x00, 0x00, 0x80, 0x00, 0x00, 0x08, 0x00, 0x00, 0x04, 0x00, 0x00, 0x04, 0x00, 0x20, 0x00, 0x00, + 0x10, 0x00, 0x00, 0x02, 0x00, 0x80, 0x00, 0x00, 0x08, 0x00, 0x00, 0x04, 0x00, 0x40, 0x00, 0x00, + 0x20, 0x00, 0x00, 0x02, 0x00, 0x00, 0x01, 0x00, 0x10, 0x00, 0x00, 0x08, 0x00, 0x40, 0x00, 0x00, + 0x20, 0x00, 0x00, 0x01, 0x00, 0x80, 0x00, 0x00, 0x08, 0x00, 0x00, 0x08, 0x00, 0x40, 0x00, 0x00, + 0x20, 0x00, 0x00, 0x01, 0x00, 0x80, 0x00, 0x00, 0x08, 0x00, 0x00, 0x02, 0x00, 0x40, 0x00, 0x00, + 0x08, 0x00, 0x00, 0x01, 0x00, 0x10, 0x00, 0x00, 0x08, 0x00, 0x80, 0x00, 0x00, 0x20, 0x00, 0x00, + 0x01, 0x00, 0x40, 0x00, 0x00, 0x08, 0x00, 0x80, 0x00, 0x00, 0x20, 0x00, 0x00, 0x02, 0x40, 0x01, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x0D, 0x00, 0x00, 0x00, + 0x19, 0x00, 0x00, 0x00, 0x25, 0x00, 0x00, 0x00, 0x00, 0x02, 0x04, 0x05, 0x07, 0x08, 0x0A, 0x0B, + 0x00, 0x01, 0x02, 0x04, 0x06, 0x07, 0x09, 0x0A, 0x00, 0x01, 0x03, 0x04, 0x06, 0x07, 0x09, 0x0A, + 0x00, 0x01, 0x03, 0x04, 0x06, 0x14, 0x07, 0x00, 0x00, 0xAB, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, + 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0x02, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x81, 0x00, 0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0x81, 0x01, 0x00, 0x00, 0x01, 0x02, 0x00, + 0x00, 0x81, 0x02, 0x00, 0x00, 0x01, 0x03, 0x00, 0x00, 0x81, 0x03, 0x00, 0x00, 0x00, 0x11, 0x21, + 0x31, 0x41, 0x51, 0x61, 0x71, 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, + 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, + 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x10, 0x20, + 0x30, 0x40, 0x50, 0x60, 0x70, 0x00, 0x01, 0x14, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x72, + 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x0B, 0x00, 0x00, 0x00, 0x38, 0x8E, 0xE3, 0x38, 0x8E, + 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, + 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x38, + 0x8E, 0xE3, 0x38, 0x8E, 0xE3, 0x18, 0x00, 0x00, 0x02, 0x00, 0x00, 0x51, 0x14, 0x45, 0x51, 0x14, + 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, + 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, 0x14, 0x45, 0x51, + 0x14, 0x45, 0x51, 0x14, 0x45, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x55, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0B, 0x15, 0x20, 0x2B, 0x35, 0x40, 0x4B, 0x00, + 0x0B, 0x16, 0x1D, 0x1D, 0x1D, 0x1D, 0x1D, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x0B, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x72, 0x00, 0x00, 0x00, + 0x01, 0x08, 0x20, 0x00, 0x01, 0x08, 0x20, 0x00, 0x01, 0x08, 0x20, 0x00, 0x01, 0x08, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x06, 0x09, 0x72, 0x00, 0x00, + 0x00, 0xAB, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x11, 0x21, 0x31, 0x01, 0x72, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x71, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x38, 0x8E, + 0x23, 0x00, 0x20, 0x00, 0x00, 0x00, 0x51, 0x14, 0x25, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, + 0x08, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x2B, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x39, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x8A, 0x03, 0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, + 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x30, 0x00, + 0x00, 0x00, 0x00, 0x02, 0x04, 0x06, 0x08, 0x0A, 0x0C, 0x0E, 0x00, 0x02, 0x04, 0x06, 0x08, 0x0A, + 0x0C, 0x0E, 0x00, 0x02, 0x04, 0x06, 0x08, 0x0A, 0x0C, 0x0E, 0x00, 0x02, 0x04, 0x06, 0x08, + }; + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchCheckState.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchCheckState.cs new file mode 100644 index 00000000..4c014578 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchCheckState.cs @@ -0,0 +1,16 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + struct MatchCheckState + { + public uint CheckMask; + public readonly uint RegionMask; + public readonly ProfanityFilterOption Option; + + public MatchCheckState(uint checkMask, uint regionMask, ProfanityFilterOption option) + { + CheckMask = checkMask; + RegionMask = regionMask; + Option = option; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchDelimitedState.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchDelimitedState.cs new file mode 100644 index 00000000..d9b82d42 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchDelimitedState.cs @@ -0,0 +1,24 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + struct MatchDelimitedState + { + public bool Matched; + public readonly bool PrevCharIsWordSeparator; + public readonly bool NextCharIsWordSeparator; + public readonly Sbv NoSeparatorMap; + public readonly AhoCorasick DelimitedWordsTrie; + + public MatchDelimitedState( + bool prevCharIsWordSeparator, + bool nextCharIsWordSeparator, + Sbv noSeparatorMap, + AhoCorasick delimitedWordsTrie) + { + Matched = false; + PrevCharIsWordSeparator = prevCharIsWordSeparator; + NextCharIsWordSeparator = nextCharIsWordSeparator; + NoSeparatorMap = noSeparatorMap; + DelimitedWordsTrie = delimitedWordsTrie; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchRangeList.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchRangeList.cs new file mode 100644 index 00000000..ad2ad7a9 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchRangeList.cs @@ -0,0 +1,113 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + readonly struct MatchRange + { + public readonly int StartOffset; + public readonly int EndOffset; + + public MatchRange(int startOffset, int endOffset) + { + StartOffset = startOffset; + EndOffset = endOffset; + } + } + + struct MatchRangeList + { + private int _capacity; + private int _count; + private MatchRange[] _ranges; + + public readonly int Count => _count; + + public readonly MatchRange this[int index] => _ranges[index]; + + public MatchRangeList() + { + _capacity = 0; + _count = 0; + _ranges = Array.Empty<MatchRange>(); + } + + public void Add(int startOffset, int endOffset) + { + if (_count == _capacity) + { + int newCapacity = _count * 2; + + if (newCapacity == 0) + { + newCapacity = 1; + } + + Array.Resize(ref _ranges, newCapacity); + + _capacity = newCapacity; + } + + _ranges[_count++] = new(startOffset, endOffset); + } + + public readonly MatchRangeList Deduplicate() + { + MatchRangeList output = new(); + + if (_count != 0) + { + int prevStartOffset = _ranges[0].StartOffset; + int prevEndOffset = _ranges[0].EndOffset; + + for (int index = 1; index < _count; index++) + { + int currStartOffset = _ranges[index].StartOffset; + int currEndOffset = _ranges[index].EndOffset; + + if (prevStartOffset == currStartOffset) + { + if (prevEndOffset <= currEndOffset) + { + prevEndOffset = currEndOffset; + } + } + else if (prevEndOffset <= currStartOffset) + { + output.Add(prevStartOffset, prevEndOffset); + + prevStartOffset = currStartOffset; + prevEndOffset = currEndOffset; + } + } + + output.Add(prevStartOffset, prevEndOffset); + } + + return output; + } + + public readonly int Find(int startOffset, int endOffset) + { + int baseIndex = 0; + int range = _count; + + while (range != 0) + { + MatchRange currRange = _ranges[baseIndex + (range / 2)]; + + if (currRange.StartOffset < startOffset || (currRange.StartOffset == startOffset && currRange.EndOffset < endOffset)) + { + int nextHalf = (range / 2) + 1; + baseIndex += nextHalf; + range -= nextHalf; + } + else + { + range /= 2; + } + } + + return baseIndex; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchRangeListState.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchRangeListState.cs new file mode 100644 index 00000000..44a63449 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchRangeListState.cs @@ -0,0 +1,21 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + struct MatchRangeListState + { + public MatchRangeList MatchRanges; + + public MatchRangeListState() + { + MatchRanges = new(); + } + + public static bool AddMatch(ReadOnlySpan<byte> text, int startOffset, int endOffset, int nodeId, ref MatchRangeListState state) + { + state.MatchRanges.Add(startOffset, endOffset); + + return true; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchSimilarFormState.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchSimilarFormState.cs new file mode 100644 index 00000000..eab9bf95 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchSimilarFormState.cs @@ -0,0 +1,18 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + struct MatchSimilarFormState + { + public MatchRangeList MatchRanges; + public SimilarFormTable SimilarFormTable; + public Utf8Text CanonicalText; + public int ReplaceEndOffset; + + public MatchSimilarFormState(MatchRangeList matchRanges, SimilarFormTable similarFormTable) + { + MatchRanges = matchRanges; + SimilarFormTable = similarFormTable; + CanonicalText = new(); + ReplaceEndOffset = 0; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchState.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchState.cs new file mode 100644 index 00000000..04fc1850 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/MatchState.cs @@ -0,0 +1,49 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + readonly ref struct MatchState + { + public readonly Span<byte> OriginalText; + public readonly Span<byte> ConvertedText; + public readonly ReadOnlySpan<sbyte> DeltaTable; + public readonly ref int MaskedCount; + public readonly MaskMode MaskMode; + public readonly Sbv NoSeparatorMap; + public readonly AhoCorasick DelimitedWordsTrie; + + public MatchState( + Span<byte> originalText, + Span<byte> convertedText, + ReadOnlySpan<sbyte> deltaTable, + ref int maskedCount, + MaskMode maskMode, + Sbv noSeparatorMap = null, + AhoCorasick delimitedWordsTrie = null) + { + OriginalText = originalText; + ConvertedText = convertedText; + DeltaTable = deltaTable; + MaskedCount = ref maskedCount; + MaskMode = maskMode; + NoSeparatorMap = noSeparatorMap; + DelimitedWordsTrie = delimitedWordsTrie; + } + + public readonly (int, int) GetOriginalRange(int convertedStartOffest, int convertedEndOffset) + { + int originalStartOffset = 0; + int originalEndOffset = 0; + + for (int index = 0; index < convertedEndOffset; index++) + { + int byteLength = Math.Abs(DeltaTable[index]); + + originalStartOffset += index < convertedStartOffest ? byteLength : 0; + originalEndOffset += byteLength; + } + + return (originalStartOffset, originalEndOffset); + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ProfanityFilter.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ProfanityFilter.cs new file mode 100644 index 00000000..980126a6 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ProfanityFilter.cs @@ -0,0 +1,886 @@ +using Ryujinx.Horizon.Common; +using Ryujinx.Horizon.Sdk.Fs; +using System; +using System.Buffers.Binary; +using System.Numerics; +using System.Text; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class ProfanityFilter : ProfanityFilterBase, IDisposable + { + private const int MaxBufferLength = 0x800; + private const int MaxUtf8CharacterLength = 4; + private const int MaxUtf8Characters = MaxBufferLength / MaxUtf8CharacterLength; + private const int RegionsCount = 16; + private const int MountCacheSize = 0x2000; + + private readonly ContentsReader _contentsReader; + + public ProfanityFilter(IFsClient fsClient) + { + _contentsReader = new(fsClient); + } + + public Result Initialize() + { + return _contentsReader.Initialize(MountCacheSize); + } + + public override Result Reload() + { + return _contentsReader.Reload(); + } + + public override Result GetContentVersion(out uint version) + { + version = 0; + + Result result = _contentsReader.GetVersionDataSize(out long size); + if (result.IsFailure && size != 4) + { + return Result.Success; + } + + Span<byte> data = stackalloc byte[4]; + result = _contentsReader.GetVersionData(data); + if (result.IsFailure) + { + return Result.Success; + } + + version = BinaryPrimitives.ReadUInt32BigEndian(data); + + return Result.Success; + } + + public override Result CheckProfanityWords(out uint checkMask, ReadOnlySpan<byte> word, uint regionMask, ProfanityFilterOption option) + { + checkMask = 0; + + int length = word.IndexOf((byte)0); + if (length >= 0) + { + word = word[..length]; + } + + UTF8Encoding encoding = new(encoderShouldEmitUTF8Identifier: false, throwOnInvalidBytes: true); + + string decodedWord; + + try + { + decodedWord = encoding.GetString(word); + } + catch (ArgumentException) + { + return NgcResult.InvalidUtf8Encoding; + } + + return CheckProfanityWordsMultiRegionImpl(ref checkMask, decodedWord, regionMask, option); + } + + private Result CheckProfanityWordsMultiRegionImpl(ref uint checkMask, string word, uint regionMask, ProfanityFilterOption option) + { + // Check using common dictionary. + Result result = CheckProfanityWordsImpl(ref checkMask, word, 0, option); + if (result.IsFailure) + { + return result; + } + + if (checkMask != 0) + { + checkMask = (ushort)(regionMask | option.SystemRegionMask); + } + + // Check using region specific dictionaries if needed. + for (int regionIndex = 0; regionIndex < RegionsCount; regionIndex++) + { + if (((regionMask | option.SystemRegionMask) & (1 << regionIndex)) != 0) + { + result = CheckProfanityWordsImpl(ref checkMask, word, 1u << regionIndex, option); + if (result.IsFailure) + { + return result; + } + } + } + + return Result.Success; + } + + private Result CheckProfanityWordsImpl(ref uint checkMask, string word, uint regionMask, ProfanityFilterOption option) + { + ConvertUserInputForWord(out string convertedWord, word); + + if (IsIncludesAtSign(convertedWord)) + { + checkMask |= regionMask != 0 ? regionMask : option.SystemRegionMask; + } + + byte[] utf8Text = Encoding.UTF8.GetBytes(convertedWord); + byte[] convertedText = new byte[utf8Text.Length + 5]; + + utf8Text.CopyTo(convertedText.AsSpan().Slice(2, utf8Text.Length)); + + convertedText[0] = (byte)'\\'; + convertedText[1] = (byte)'b'; + convertedText[2 + utf8Text.Length] = (byte)'\\'; + convertedText[3 + utf8Text.Length] = (byte)'b'; + convertedText[4 + utf8Text.Length] = 0; + + int regionIndex = (ushort)regionMask != 0 ? BitOperations.TrailingZeroCount(regionMask) : -1; + + Result result = _contentsReader.ReadDictionaries(out AhoCorasick partialWordsTrie, out _, out AhoCorasick delimitedWordsTrie, regionIndex); + if (result.IsFailure) + { + return result; + } + + if ((checkMask & regionMask) == 0) + { + MatchCheckState state = new(checkMask, regionMask, option); + + partialWordsTrie.Match(convertedText, MatchCheck, ref state); + delimitedWordsTrie.Match(convertedText, MatchCheck, ref state); + + checkMask = state.CheckMask; + } + + return Result.Success; + } + + public override Result MaskProfanityWordsInText(out int maskedWordsCount, Span<byte> text, uint regionMask, ProfanityFilterOption option) + { + maskedWordsCount = 0; + + Span<byte> output = text; + Span<byte> convertedText = new byte[MaxBufferLength]; + Span<sbyte> deltaTable = new sbyte[MaxBufferLength]; + + int nullTerminatorIndex = GetUtf8Length(out _, text, MaxUtf8Characters); + + // Ensure that the text has a null terminator if we can. + // If the text is too long, it will be truncated. + byte replacedCharacter = 0; + + if (nullTerminatorIndex > 0 && nullTerminatorIndex < text.Length) + { + replacedCharacter = text[nullTerminatorIndex]; + text[nullTerminatorIndex] = 0; + } + + // Truncate the text if needed. + int length = text.IndexOf((byte)0); + if (length >= 0) + { + text = text[..length]; + } + + // If requested, mask e-mail addresses. + if (option.SkipAtSignCheck == SkipMode.DoNotSkip) + { + maskedWordsCount += FilterAtSign(text, option.MaskMode); + text = MaskText(text); + } + + // Convert the text to lower case, required for string matching. + ConvertUserInputForText(convertedText, deltaTable, text); + + // Mask words for common and requested regions. + Result result = MaskProfanityWordsInTextMultiRegion(ref maskedWordsCount, ref text, ref convertedText, deltaTable, regionMask, option); + if (result.IsFailure) + { + return result; + } + + // If requested, also try to match and mask the canonicalized string. + if (option.Flags != ProfanityFilterFlags.None) + { + result = MaskProfanityWordsInTextCanonicalizedMultiRegion(ref maskedWordsCount, text, regionMask, option); + if (result.IsFailure) + { + return result; + } + } + + // If we received more text than we can process, copy unprocessed portion to the end of the new text. + if (replacedCharacter != 0) + { + length = text.IndexOf((byte)0); + + if (length < 0) + { + length = text.Length; + } + + output[length++] = replacedCharacter; + int unprocessedLength = output.Length - nullTerminatorIndex - 1; + output.Slice(nullTerminatorIndex + 1, unprocessedLength).CopyTo(output.Slice(length, unprocessedLength)); + } + + return Result.Success; + } + + private Result MaskProfanityWordsInTextMultiRegion( + ref int maskedWordsCount, + ref Span<byte> originalText, + ref Span<byte> convertedText, + Span<sbyte> deltaTable, + uint regionMask, + ProfanityFilterOption option) + { + // Filter using common dictionary. + Result result = MaskProfanityWordsInTextImpl(ref maskedWordsCount, ref originalText, ref convertedText, deltaTable, -1, option); + if (result.IsFailure) + { + return result; + } + + // Filter using region specific dictionaries if needed. + for (int regionIndex = 0; regionIndex < RegionsCount; regionIndex++) + { + if (((regionMask | option.SystemRegionMask) & (1 << regionIndex)) != 0) + { + result = MaskProfanityWordsInTextImpl(ref maskedWordsCount, ref originalText, ref convertedText, deltaTable, regionIndex, option); + if (result.IsFailure) + { + return result; + } + } + } + + return Result.Success; + } + + private Result MaskProfanityWordsInTextImpl( + ref int maskedWordsCount, + ref Span<byte> originalText, + ref Span<byte> convertedText, + Span<sbyte> deltaTable, + int regionIndex, + ProfanityFilterOption option) + { + Result result = _contentsReader.ReadDictionaries( + out AhoCorasick partialWordsTrie, + out AhoCorasick completeWordsTrie, + out AhoCorasick delimitedWordsTrie, + regionIndex); + + if (result.IsFailure) + { + return result; + } + + // Match single words. + + MatchState state = new(originalText, convertedText, deltaTable, ref maskedWordsCount, option.MaskMode); + + partialWordsTrie.Match(convertedText, MatchSingleWord, ref state); + + MaskText(ref originalText, ref convertedText, deltaTable); + + // Match single words and phrases. + // We remove word separators on the string used for the match. + + Span<byte> noSeparatorText = new byte[originalText.Length]; + Sbv noSeparatorMap = new(convertedText.Length); + noSeparatorText = RemoveWordSeparators(noSeparatorText, convertedText, noSeparatorMap); + + state = new( + originalText, + convertedText, + deltaTable, + ref maskedWordsCount, + option.MaskMode, + noSeparatorMap, + delimitedWordsTrie); + + partialWordsTrie.Match(noSeparatorText, MatchMultiWord, ref state); + + MaskText(ref originalText, ref convertedText, deltaTable); + + // Match whole words, which must be surrounded by word separators. + + noSeparatorText = new byte[originalText.Length]; + noSeparatorMap = new(convertedText.Length); + noSeparatorText = RemoveWordSeparators(noSeparatorText, convertedText, noSeparatorMap); + + state = new( + originalText, + convertedText, + deltaTable, + ref maskedWordsCount, + option.MaskMode, + noSeparatorMap, + delimitedWordsTrie); + + completeWordsTrie.Match(noSeparatorText, MatchDelimitedWord, ref state); + + MaskText(ref originalText, ref convertedText, deltaTable); + + return Result.Success; + } + + private static void MaskText(ref Span<byte> originalText, ref Span<byte> convertedText, Span<sbyte> deltaTable) + { + originalText = MaskText(originalText); + UpdateDeltaTable(deltaTable, convertedText); + convertedText = MaskText(convertedText); + } + + private Result MaskProfanityWordsInTextCanonicalizedMultiRegion(ref int maskedWordsCount, Span<byte> text, uint regionMask, ProfanityFilterOption option) + { + // Filter using common dictionary. + Result result = MaskProfanityWordsInTextCanonicalized(ref maskedWordsCount, text, 0, option); + if (result.IsFailure) + { + return result; + } + + // Filter using region specific dictionaries if needed. + for (int index = 0; index < RegionsCount; index++) + { + if ((((regionMask | option.SystemRegionMask) >> index) & 1) != 0) + { + result = MaskProfanityWordsInTextCanonicalized(ref maskedWordsCount, text, 1u << index, option); + if (result.IsFailure) + { + return result; + } + } + } + + return Result.Success; + } + + private Result MaskProfanityWordsInTextCanonicalized(ref int maskedWordsCount, Span<byte> text, uint regionMask, ProfanityFilterOption option) + { + Utf8Text maskedText = new(); + Utf8ParseResult parseResult = Utf8Text.Create(out Utf8Text inputText, text); + if (parseResult != Utf8ParseResult.Success) + { + return NgcResult.InvalidUtf8Encoding; + } + + ReadOnlySpan<byte> prevCharacter = ReadOnlySpan<byte>.Empty; + + int charStartIndex = 0; + + for (int charEndIndex = 1; charStartIndex < inputText.CharacterCount;) + { + ReadOnlySpan<byte> nextCharacter = charEndIndex < inputText.CharacterCount + ? inputText.AsSubstring(charEndIndex, charEndIndex + 1) + : ReadOnlySpan<byte>.Empty; + + Result result = CheckProfanityWordsInTextCanonicalized( + out bool matched, + inputText.AsSubstring(charStartIndex, charEndIndex), + prevCharacter, + nextCharacter, + regionMask, + option); + + if (result.IsFailure && result != NgcResult.InvalidSize) + { + return result; + } + + if (matched) + { + // We had a match, we know where it ends, now we need to find where it starts. + + int previousCharStartIndex = charStartIndex; + + for (; charStartIndex < charEndIndex; charStartIndex++) + { + result = CheckProfanityWordsInTextCanonicalized( + out matched, + inputText.AsSubstring(charStartIndex, charEndIndex), + prevCharacter, + nextCharacter, + regionMask, + option); + + if (result.IsFailure && result != NgcResult.InvalidSize) + { + return result; + } + + // When we get past the start of the matched substring, the match will fail, + // so that's when we know we found the start. + if (!matched) + { + break; + } + } + + // Append substring before the match start. + maskedText = maskedText.Append(inputText.AsSubstring(previousCharStartIndex, charStartIndex - 1)); + + // Mask matched substring with asterisks. + if (option.MaskMode == MaskMode.ReplaceByOneCharacter) + { + maskedText = maskedText.Append("*"u8); + prevCharacter = "*"u8; + } + else if (option.MaskMode == MaskMode.Overwrite && charStartIndex <= charEndIndex) + { + int maskLength = charEndIndex - charStartIndex + 1; + + while (maskLength-- > 0) + { + maskedText = maskedText.Append("*"u8); + } + + prevCharacter = "*"u8; + } + + charStartIndex = charEndIndex; + maskedWordsCount++; + } + + if (charEndIndex < inputText.CharacterCount) + { + charEndIndex++; + } + else if (charStartIndex < inputText.CharacterCount) + { + prevCharacter = inputText.AsSubstring(charStartIndex, charStartIndex + 1); + maskedText = maskedText.Append(prevCharacter); + charStartIndex++; + } + } + + // Replace text with the masked text. + maskedText.CopyTo(text); + + return Result.Success; + } + + private Result CheckProfanityWordsInTextCanonicalized( + out bool matched, + ReadOnlySpan<byte> text, + ReadOnlySpan<byte> prevCharacter, + ReadOnlySpan<byte> nextCharacter, + uint regionMask, + ProfanityFilterOption option) + { + matched = false; + + Span<byte> convertedText = new byte[MaxBufferLength + 1]; + text.CopyTo(convertedText[..text.Length]); + + Result result; + + if (text.Length > 0) + { + // If requested, normalize. + // This will convert different encodings for the same character in their canonical encodings. + if (option.Flags.HasFlag(ProfanityFilterFlags.MatchNormalizedFormKC)) + { + Utf8ParseResult parseResult = Utf8Util.NormalizeFormKC(convertedText, convertedText); + + if (parseResult != Utf8ParseResult.Success) + { + return NgcResult.InvalidUtf8Encoding; + } + } + + // Convert to lower case. + ConvertUserInputForText(convertedText, Span<sbyte>.Empty, convertedText); + + // If requested, also try to replace similar characters with their canonical form. + // For example, vv is similar to w, and 1 or | is similar to i. + if (option.Flags.HasFlag(ProfanityFilterFlags.MatchSimilarForm)) + { + result = ConvertInputTextFromSimilarForm(convertedText, convertedText); + if (result.IsFailure) + { + return result; + } + } + + int length = convertedText.IndexOf((byte)0); + if (length >= 0) + { + convertedText = convertedText[..length]; + } + } + + int regionIndex = (ushort)regionMask != 0 ? BitOperations.TrailingZeroCount(regionMask) : -1; + + result = _contentsReader.ReadDictionaries( + out AhoCorasick partialWordsTrie, + out AhoCorasick completeWordsTrie, + out AhoCorasick delimitedWordsTrie, + regionIndex); + + if (result.IsFailure) + { + return result; + } + + result = ContentsReader.ReadNotSeparatorDictionary(out AhoCorasick notSeparatorTrie); + if (result.IsFailure) + { + return result; + } + + // Match single words. + + bool trieMatched = false; + + partialWordsTrie.Match(convertedText, MatchSimple, ref trieMatched); + + if (trieMatched) + { + matched = true; + + return Result.Success; + } + + // Match single words and phrases. + // We remove word separators on the string used for the match. + + Span<byte> noSeparatorText = new byte[text.Length]; + Sbv noSeparatorMap = new(convertedText.Length); + noSeparatorText = RemoveWordSeparators(noSeparatorText, convertedText, noSeparatorMap, notSeparatorTrie); + + trieMatched = false; + + partialWordsTrie.Match(noSeparatorText, MatchSimple, ref trieMatched); + + if (trieMatched) + { + matched = true; + + return Result.Success; + } + + // Match whole words, which must be surrounded by word separators. + + bool prevCharIsWordSeparator = prevCharacter.Length == 0 || IsWordSeparator(prevCharacter, notSeparatorTrie); + bool nextCharIsWordSeparator = nextCharacter.Length == 0 || IsWordSeparator(nextCharacter, notSeparatorTrie); + + MatchDelimitedState state = new(prevCharIsWordSeparator, nextCharIsWordSeparator, noSeparatorMap, delimitedWordsTrie); + + completeWordsTrie.Match(noSeparatorText, MatchDelimitedWordSimple, ref state); + + if (state.Matched) + { + matched = true; + } + + return Result.Success; + } + + private Result ConvertInputTextFromSimilarForm(Span<byte> convertedText, ReadOnlySpan<byte> text) + { + int length = text.IndexOf((byte)0); + if (length >= 0) + { + text = text[..length]; + } + + Result result = _contentsReader.ReadSimilarFormDictionary(out AhoCorasick similarFormTrie); + if (result.IsFailure) + { + return result; + } + + result = _contentsReader.ReadSimilarFormTable(out SimilarFormTable similarFormTable); + if (result.IsFailure) + { + return result; + } + + // Find all characters that have a similar form. + MatchRangeListState listState = new(); + + similarFormTrie.Match(text, MatchRangeListState.AddMatch, ref listState); + + // Filter found match ranges. + // Because some similar form strings are a subset of others, we need to remove overlapping matches. + // For example, | can be replaced with i, but |-| can be replaced with h. + // We prefer the latter match (|-|) because it is more specific. + MatchRangeList deduplicatedMatches = listState.MatchRanges.Deduplicate(); + + MatchSimilarFormState state = new(deduplicatedMatches, similarFormTable); + + similarFormTrie.Match(text, MatchAndReplace, ref state); + + // Append remaining characters. + state.CanonicalText = state.CanonicalText.Append(text[state.ReplaceEndOffset..]); + + // Set canonical text to output. + ReadOnlySpan<byte> canonicalText = state.CanonicalText.AsSpan(); + canonicalText.CopyTo(convertedText[..canonicalText.Length]); + convertedText[canonicalText.Length] = 0; + + return Result.Success; + } + + private static bool MatchCheck(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchCheckState state) + { + state.CheckMask |= state.RegionMask != 0 ? state.RegionMask : state.Option.SystemRegionMask; + + return true; + } + + private static bool MatchSingleWord(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchState state) + { + MatchCommon(ref state, matchStartOffset, matchEndOffset); + + return true; + } + + private static bool MatchMultiWord(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchState state) + { + int convertedStartOffset = state.NoSeparatorMap.Set.Select0(matchStartOffset); + int convertedEndOffset = state.NoSeparatorMap.Set.Select0(matchEndOffset); + + if (convertedEndOffset < 0) + { + convertedEndOffset = state.NoSeparatorMap.Set.BitVector.BitLength; + } + + int endOffsetBeforeSeparator = TrimEnd(state.ConvertedText, convertedEndOffset); + + MatchCommon(ref state, convertedStartOffset, endOffsetBeforeSeparator); + + return true; + } + + private static bool MatchDelimitedWord(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchState state) + { + int convertedStartOffset = state.NoSeparatorMap.Set.Select0(matchStartOffset); + int convertedEndOffset = state.NoSeparatorMap.Set.Select0(matchEndOffset); + + if (convertedEndOffset < 0) + { + convertedEndOffset = state.NoSeparatorMap.Set.BitVector.BitLength; + } + + int endOffsetBeforeSeparator = TrimEnd(state.ConvertedText, convertedEndOffset); + + Span<byte> delimitedText = new byte[64]; + + // If the word is prefixed by a word separator, insert "\b" delimiter, otherwise insert "a" delimitar. + // The start of the string is also considered a "word separator". + + bool startIsPrefixedByWordSeparator = + convertedStartOffset == 0 || + IsPrefixedByWordSeparator(state.ConvertedText, convertedStartOffset); + + int delimitedTextOffset = 0; + + if (startIsPrefixedByWordSeparator) + { + delimitedText[delimitedTextOffset++] = (byte)'\\'; + delimitedText[delimitedTextOffset++] = (byte)'b'; + } + else + { + delimitedText[delimitedTextOffset++] = (byte)'a'; + } + + // Copy the word to our temporary buffer used for the next match. + + int matchLength = matchEndOffset - matchStartOffset; + + text.Slice(matchStartOffset, matchLength).CopyTo(delimitedText.Slice(delimitedTextOffset, matchLength)); + + delimitedTextOffset += matchLength; + + // If the word is suffixed by a word separator, insert "\b" delimiter, otherwise insert "a" delimiter. + // The end of the string is also considered a "word separator". + + bool endIsSuffixedByWordSeparator = + endOffsetBeforeSeparator == state.NoSeparatorMap.Set.BitVector.BitLength || + state.ConvertedText[endOffsetBeforeSeparator] == 0 || + IsWordSeparator(state.ConvertedText, endOffsetBeforeSeparator); + + if (endIsSuffixedByWordSeparator) + { + delimitedText[delimitedTextOffset++] = (byte)'\\'; + delimitedText[delimitedTextOffset++] = (byte)'b'; + } + else + { + delimitedText[delimitedTextOffset++] = (byte)'a'; + } + + // Create our temporary match state for the next match. + bool matched = false; + + // Insert the null terminator. + delimitedText[delimitedTextOffset] = 0; + + // Check if the delimited word is on the dictionary. + state.DelimitedWordsTrie.Match(delimitedText, MatchSimple, ref matched); + + // If we have a match, mask the word. + if (matched) + { + MatchCommon(ref state, convertedStartOffset, endOffsetBeforeSeparator); + } + + return true; + } + + private static void MatchCommon(ref MatchState state, int matchStartOffset, int matchEndOffset) + { + // If length is zero or negative, there was no match. + if (matchStartOffset >= matchEndOffset) + { + return; + } + + Span<byte> convertedText = state.ConvertedText; + Span<byte> originalText = state.OriginalText; + + int matchLength = matchEndOffset - matchStartOffset; + int characterCount = Encoding.UTF8.GetCharCount(state.ConvertedText.Slice(matchStartOffset, matchLength)); + + // Exit early if there are no character, or if we matched past the end of the string. + if (characterCount == 0 || + (matchStartOffset > 0 && convertedText[matchStartOffset - 1] == 0) || + (matchStartOffset > 1 && convertedText[matchStartOffset - 2] == 0)) + { + return; + } + + state.MaskedCount++; + + (int originalStartOffset, int originalEndOffset) = state.GetOriginalRange(matchStartOffset, matchEndOffset); + + PreMaskCharacterRange(convertedText, matchStartOffset, matchEndOffset, state.MaskMode, characterCount); + PreMaskCharacterRange(originalText, originalStartOffset, originalEndOffset, state.MaskMode, characterCount); + } + + private static bool MatchDelimitedWordSimple(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchDelimitedState state) + { + int convertedStartOffset = state.NoSeparatorMap.Set.Select0(matchStartOffset); + + Span<byte> delimitedText = new byte[64]; + + // If the word is prefixed by a word separator, insert "\b" delimiter, otherwise insert "a" delimitar. + // The start of the string is also considered a "word separator". + + bool startIsPrefixedByWordSeparator = + (convertedStartOffset == 0 && state.PrevCharIsWordSeparator) || + state.NoSeparatorMap.Set.Has(convertedStartOffset - 1); + + int delimitedTextOffset = 0; + + if (startIsPrefixedByWordSeparator) + { + delimitedText[delimitedTextOffset++] = (byte)'\\'; + delimitedText[delimitedTextOffset++] = (byte)'b'; + } + else + { + delimitedText[delimitedTextOffset++] = (byte)'a'; + } + + // Copy the word to our temporary buffer used for the next match. + + int matchLength = matchEndOffset - matchStartOffset; + + text.Slice(matchStartOffset, matchLength).CopyTo(delimitedText.Slice(delimitedTextOffset, matchLength)); + + delimitedTextOffset += matchLength; + + // If the word is suffixed by a word separator, insert "\b" delimiter, otherwise insert "a" delimiter. + // The end of the string is also considered a "word separator". + + int convertedEndOffset = state.NoSeparatorMap.Set.Select0(matchEndOffset); + + bool endIsSuffixedByWordSeparator = + (convertedEndOffset < 0 && state.NextCharIsWordSeparator) || + state.NoSeparatorMap.Set.Has(convertedEndOffset - 1); + + if (endIsSuffixedByWordSeparator) + { + delimitedText[delimitedTextOffset++] = (byte)'\\'; + delimitedText[delimitedTextOffset++] = (byte)'b'; + } + else + { + delimitedText[delimitedTextOffset++] = (byte)'a'; + } + + // Create our temporary match state for the next match. + bool matched = false; + + // Insert the null terminator. + delimitedText[delimitedTextOffset] = 0; + + // Check if the delimited word is on the dictionary. + state.DelimitedWordsTrie.Match(delimitedText, MatchSimple, ref matched); + + // If we have a match, mask the word. + if (matched) + { + state.Matched = true; + } + + return !matched; + } + + private static bool MatchAndReplace(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref MatchSimilarFormState state) + { + if (matchStartOffset < state.ReplaceEndOffset || state.MatchRanges.Count == 0) + { + return true; + } + + // Check if the match range exists on our list of ranges. + int rangeIndex = state.MatchRanges.Find(matchStartOffset, matchEndOffset); + + if ((uint)rangeIndex >= (uint)state.MatchRanges.Count) + { + return true; + } + + MatchRange range = state.MatchRanges[rangeIndex]; + + // We only replace if the match has the same size or is larger than an existing match on the list. + if (range.StartOffset <= matchStartOffset && + (range.StartOffset != matchStartOffset || range.EndOffset <= matchEndOffset)) + { + // Copy all characters since the last match to the output. + int endOffset = state.ReplaceEndOffset; + + if (endOffset < matchStartOffset) + { + state.CanonicalText = state.CanonicalText.Append(text[endOffset..matchStartOffset]); + } + + // Get canonical character from the similar one, and append it. + // For example, |-| is replaced with h, vv is replaced with w, etc. + ReadOnlySpan<byte> matchText = text[matchStartOffset..matchEndOffset]; + state.CanonicalText = state.CanonicalText.AppendNullTerminated(state.SimilarFormTable.FindCanonicalString(matchText)); + state.ReplaceEndOffset = matchEndOffset; + } + + return true; + } + + protected virtual void Dispose(bool disposing) + { + if (disposing) + { + _contentsReader.Dispose(); + } + } + + public void Dispose() + { + Dispose(disposing: true); + GC.SuppressFinalize(this); + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ProfanityFilterBase.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ProfanityFilterBase.cs new file mode 100644 index 00000000..e45c9f47 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/ProfanityFilterBase.cs @@ -0,0 +1,789 @@ +using Ryujinx.Horizon.Common; +using System; +using System.Globalization; +using System.Runtime.InteropServices; +using System.Text; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + abstract class ProfanityFilterBase + { +#pragma warning disable IDE0230 // Use UTF-8 string literal + private static readonly byte[][] _wordSeparators = { + new byte[] { 0x0D }, + new byte[] { 0x0A }, + new byte[] { 0xC2, 0x85 }, + new byte[] { 0xE2, 0x80, 0xA8 }, + new byte[] { 0xE2, 0x80, 0xA9 }, + new byte[] { 0x09 }, + new byte[] { 0x0B }, + new byte[] { 0x0C }, + new byte[] { 0x20 }, + new byte[] { 0xEF, 0xBD, 0xA1 }, + new byte[] { 0xEF, 0xBD, 0xA4 }, + new byte[] { 0x2E }, + new byte[] { 0x2C }, + new byte[] { 0x5B }, + new byte[] { 0x21 }, + new byte[] { 0x22 }, + new byte[] { 0x23 }, + new byte[] { 0x24 }, + new byte[] { 0x25 }, + new byte[] { 0x26 }, + new byte[] { 0x27 }, + new byte[] { 0x28 }, + new byte[] { 0x29 }, + new byte[] { 0x2A }, + new byte[] { 0x2B }, + new byte[] { 0x2F }, + new byte[] { 0x3A }, + new byte[] { 0x3B }, + new byte[] { 0x3C }, + new byte[] { 0x3D }, + new byte[] { 0x3E }, + new byte[] { 0x3F }, + new byte[] { 0x5C }, + new byte[] { 0x40 }, + new byte[] { 0x5E }, + new byte[] { 0x5F }, + new byte[] { 0x60 }, + new byte[] { 0x7B }, + new byte[] { 0x7C }, + new byte[] { 0x7D }, + new byte[] { 0x7E }, + new byte[] { 0x2D }, + new byte[] { 0x5D }, + new byte[] { 0xE3, 0x80, 0x80 }, + new byte[] { 0xE3, 0x80, 0x82 }, + new byte[] { 0xE3, 0x80, 0x81 }, + new byte[] { 0xEF, 0xBC, 0x8E }, + new byte[] { 0xEF, 0xBC, 0x8C }, + new byte[] { 0xEF, 0xBC, 0xBB }, + new byte[] { 0xEF, 0xBC, 0x81 }, + new byte[] { 0xE2, 0x80, 0x9C }, + new byte[] { 0xE2, 0x80, 0x9D }, + new byte[] { 0xEF, 0xBC, 0x83 }, + new byte[] { 0xEF, 0xBC, 0x84 }, + new byte[] { 0xEF, 0xBC, 0x85 }, + new byte[] { 0xEF, 0xBC, 0x86 }, + new byte[] { 0xE2, 0x80, 0x98 }, + new byte[] { 0xE2, 0x80, 0x99 }, + new byte[] { 0xEF, 0xBC, 0x88 }, + new byte[] { 0xEF, 0xBC, 0x89 }, + new byte[] { 0xEF, 0xBC, 0x8A }, + new byte[] { 0xEF, 0xBC, 0x8B }, + new byte[] { 0xEF, 0xBC, 0x8F }, + new byte[] { 0xEF, 0xBC, 0x9A }, + new byte[] { 0xEF, 0xBC, 0x9B }, + new byte[] { 0xEF, 0xBC, 0x9C }, + new byte[] { 0xEF, 0xBC, 0x9D }, + new byte[] { 0xEF, 0xBC, 0x9E }, + new byte[] { 0xEF, 0xBC, 0x9F }, + new byte[] { 0xEF, 0xBC, 0xA0 }, + new byte[] { 0xEF, 0xBF, 0xA5 }, + new byte[] { 0xEF, 0xBC, 0xBE }, + new byte[] { 0xEF, 0xBC, 0xBF }, + new byte[] { 0xEF, 0xBD, 0x80 }, + new byte[] { 0xEF, 0xBD, 0x9B }, + new byte[] { 0xEF, 0xBD, 0x9C }, + new byte[] { 0xEF, 0xBD, 0x9D }, + new byte[] { 0xEF, 0xBD, 0x9E }, + new byte[] { 0xEF, 0xBC, 0x8D }, + new byte[] { 0xEF, 0xBC, 0xBD }, + }; +#pragma warning restore IDE0230 + + private enum SignFilterStep + { + DetectEmailStart, + DetectEmailUserAtSign, + DetectEmailDomain, + DetectEmailEnd, + } + + public abstract Result GetContentVersion(out uint version); + public abstract Result CheckProfanityWords(out uint checkMask, ReadOnlySpan<byte> word, uint regionMask, ProfanityFilterOption option); + public abstract Result MaskProfanityWordsInText(out int maskedWordsCount, Span<byte> text, uint regionMask, ProfanityFilterOption option); + public abstract Result Reload(); + + protected static bool IsIncludesAtSign(string word) + { + for (int index = 0; index < word.Length; index++) + { + if (word[index] == '\0') + { + break; + } + else if (word[index] == '@' || word[index] == '\uFF20') + { + return true; + } + } + + return false; + } + + protected static int FilterAtSign(Span<byte> text, MaskMode maskMode) + { + SignFilterStep step = SignFilterStep.DetectEmailStart; + int matchStart = 0; + int matchCount = 0; + + for (int index = 0; index < text.Length; index++) + { + byte character = text[index]; + + switch (step) + { + case SignFilterStep.DetectEmailStart: + if (char.IsAsciiLetterOrDigit((char)character)) + { + step = SignFilterStep.DetectEmailUserAtSign; + matchStart = index; + } + break; + case SignFilterStep.DetectEmailUserAtSign: + bool hasMatch = false; + + while (IsValidEmailAddressCharacter(character)) + { + hasMatch = true; + + if (index + 1 >= text.Length) + { + break; + } + + character = text[++index]; + } + + step = hasMatch && character == '@' ? SignFilterStep.DetectEmailDomain : SignFilterStep.DetectEmailStart; + break; + case SignFilterStep.DetectEmailDomain: + step = char.IsAsciiLetterOrDigit((char)character) ? SignFilterStep.DetectEmailEnd : SignFilterStep.DetectEmailStart; + break; + case SignFilterStep.DetectEmailEnd: + int domainIndex = index; + + while (index + 1 < text.Length && IsValidEmailAddressCharacter(text[++index])) + { + } + + int addressLastIndex = index - 1; + int lastIndex = 0; + bool lastIndexSet = false; + + while (matchStart < addressLastIndex) + { + character = text[addressLastIndex]; + + if (char.IsAsciiLetterOrDigit((char)character)) + { + if (!lastIndexSet) + { + lastIndexSet = true; + lastIndex = addressLastIndex; + } + } + else if (lastIndexSet) + { + break; + } + + addressLastIndex--; + } + + step = SignFilterStep.DetectEmailStart; + + if (domainIndex < addressLastIndex && character == '.') + { + PreMaskCharacterRange(text, matchStart, lastIndex + 1, maskMode, (lastIndex - matchStart) + 1); + matchCount++; + } + else + { + index = domainIndex - 1; + } + break; + } + } + + return matchCount; + } + + private static bool IsValidEmailAddressCharacter(byte character) + { + return char.IsAsciiLetterOrDigit((char)character) || character == '-' || character == '.' || character == '_'; + } + + protected static void PreMaskCharacterRange(Span<byte> text, int startOffset, int endOffset, MaskMode maskMode, int characterCount) + { + int byteLength = endOffset - startOffset; + + if (byteLength == 1) + { + text[startOffset] = 0xc1; + } + else if (byteLength == 2) + { + if (maskMode == MaskMode.Overwrite && Encoding.UTF8.GetCharCount(text.Slice(startOffset, 2)) != 1) + { + text[startOffset] = 0xc1; + text[startOffset + 1] = 0xc1; + } + else if (maskMode == MaskMode.Overwrite || maskMode == MaskMode.ReplaceByOneCharacter) + { + text[startOffset] = 0xc0; + text[startOffset + 1] = 0xc0; + } + } + else + { + text[startOffset++] = 0; + + if (byteLength >= 0xff) + { + int fillLength = (byteLength - 0xff) / 0xff + 1; + + text.Slice(startOffset++, fillLength).Fill(0xff); + + byteLength -= fillLength * 0xff; + startOffset += fillLength; + } + + text[startOffset++] = (byte)byteLength; + + if (maskMode == MaskMode.ReplaceByOneCharacter) + { + text[startOffset++] = 1; + } + else if (maskMode == MaskMode.Overwrite) + { + if (characterCount >= 0xff) + { + int fillLength = (characterCount - 0xff) / 0xff + 1; + + text.Slice(startOffset, fillLength).Fill(0xff); + + characterCount -= fillLength * 0xff; + startOffset += fillLength; + } + + text[startOffset++] = (byte)characterCount; + } + + if (startOffset < endOffset) + { + text[startOffset..endOffset].Fill(0xc1); + } + } + } + + protected static void ConvertUserInputForWord(out string outputText, string inputText) + { + outputText = inputText.ToLowerInvariant(); + } + + protected static void ConvertUserInputForText(Span<byte> outputText, Span<sbyte> deltaTable, ReadOnlySpan<byte> inputText) + { + int outputIndex = 0; + int deltaTableIndex = 0; + + for (int index = 0; index < inputText.Length;) + { + byte character = inputText[index]; + bool isInvalid = false; + int characterByteLength = 1; + + if (character == 0xef && index + 4 < inputText.Length) + { + if (((inputText[index + 1] == 0xbd && inputText[index + 2] >= 0xa6 && inputText[index + 2] < 0xe6) || + (inputText[index + 1] == 0xbe && inputText[index + 2] >= 0x80 && inputText[index + 2] < 0xa0)) && + inputText[index + 3] == 0xef && + inputText[index + 4] == 0xbe) + { + characterByteLength = 6; + } + else + { + characterByteLength = 3; + } + } + else if ((character & 0x80) != 0) + { + if (character >= 0xc2 && character < 0xe0) + { + characterByteLength = 2; + } + else if ((character & 0xf0) == 0xe0) + { + characterByteLength = 3; + } + else if ((character & 0xf8) == 0xf0) + { + characterByteLength = 4; + } + else + { + isInvalid = true; + } + } + + isInvalid |= index + characterByteLength > inputText.Length; + + string str = null; + + if (!isInvalid) + { + str = Encoding.UTF8.GetString(inputText.Slice(index, characterByteLength)); + + foreach (char chr in str) + { + if (chr == '\uFFFD') + { + isInvalid = true; + break; + } + } + } + + int convertedByteLength = 1; + + if (isInvalid) + { + characterByteLength = 1; + outputText[outputIndex++] = inputText[index]; + } + else + { + convertedByteLength = Encoding.UTF8.GetBytes(str.ToLowerInvariant().AsSpan(), outputText[outputIndex..]); + outputIndex += convertedByteLength; + } + + if (deltaTable.Length != 0 && convertedByteLength != 0) + { + // Calculate how many bytes we need to advance for each converted byte to match + // the character on the original text. + // The official service does this as part of the conversion (to lower case) process, + // but since we use .NET for that here, this is done separately. + + int distribution = characterByteLength / convertedByteLength; + + deltaTable[deltaTableIndex++] = (sbyte)(characterByteLength - distribution * convertedByteLength + distribution); + + for (int byteIndex = 1; byteIndex < convertedByteLength; byteIndex++) + { + deltaTable[deltaTableIndex++] = (sbyte)distribution; + } + } + + index += characterByteLength; + } + + if (outputIndex < outputText.Length) + { + outputText[outputIndex] = 0; + } + } + + protected static Span<byte> MaskText(Span<byte> text) + { + if (text.Length == 0) + { + return text; + } + + for (int index = 0; index < text.Length; index++) + { + byte character = text[index]; + + if (character == 0xc1) + { + text[index] = (byte)'*'; + } + else if (character == 0xc0) + { + if (index + 1 < text.Length && text[index + 1] == 0xc0) + { + text[index++] = (byte)'*'; + text[index] = 0; + } + } + else if (character == 0 && index + 1 < text.Length) + { + // There are two sequences of 0xFF followed by another value. + // The first indicates the length of the sub-string to replace in bytes. + // The second indicates the character count. + + int lengthSequenceIndex = index + 1; + int byteLength = CountMaskLengthBytes(text, ref lengthSequenceIndex); + int characterCount = CountMaskLengthBytes(text, ref lengthSequenceIndex); + + if (byteLength != 0) + { + for (int replaceIndex = 0; replaceIndex < byteLength; replaceIndex++) + { + text[index++] = (byte)(replaceIndex < characterCount ? '*' : '\0'); + } + + index--; + } + } + } + + // Move null-terminators to the end. + MoveZeroValuesToEnd(text); + + // Find new length of the text. + int length = text.IndexOf((byte)0); + + if (length >= 0) + { + return text[..length]; + } + + return text; + } + + protected static void UpdateDeltaTable(Span<sbyte> deltaTable, ReadOnlySpan<byte> text) + { + if (text.Length == 0) + { + return; + } + + // Update values to account for the characters that will be removed. + for (int index = 0; index < text.Length; index++) + { + byte character = text[index]; + + if (character == 0 && index + 1 < text.Length) + { + // There are two sequences of 0xFF followed by another value. + // The first indicates the length of the sub-string to replace in bytes. + // The second indicates the character count. + + int lengthSequenceIndex = index + 1; + int byteLength = CountMaskLengthBytes(text, ref lengthSequenceIndex); + int characterCount = CountMaskLengthBytes(text, ref lengthSequenceIndex); + + if (byteLength != 0) + { + for (int replaceIndex = 0; replaceIndex < byteLength; replaceIndex++) + { + deltaTable[index++] = (sbyte)(replaceIndex < characterCount ? 1 : 0); + } + } + } + } + + // Move zero values of the removed bytes to the end. + MoveZeroValuesToEnd(MemoryMarshal.Cast<sbyte, byte>(deltaTable)); + } + + private static int CountMaskLengthBytes(ReadOnlySpan<byte> text, ref int index) + { + int totalLength = 0; + + for (; index < text.Length; index++) + { + int length = text[index]; + totalLength += length; + + if (length != 0xff) + { + index++; + break; + } + } + + return totalLength; + } + + private static void MoveZeroValuesToEnd(Span<byte> text) + { + for (int index = 0; index < text.Length; index++) + { + int nullCount = 0; + + for (; index + nullCount < text.Length; nullCount++) + { + byte character = text[index + nullCount]; + if (character != 0) + { + break; + } + } + + if (nullCount != 0) + { + int fillLength = text.Length - (index + nullCount); + + text[(index + nullCount)..].CopyTo(text.Slice(index, fillLength)); + text.Slice(index + fillLength, nullCount).Clear(); + } + } + } + + protected static Span<byte> RemoveWordSeparators(Span<byte> output, ReadOnlySpan<byte> input, Sbv map) + { + int outputIndex = 0; + + if (map.Set.BitVector.BitLength != 0) + { + for (int index = 0; index < input.Length; index++) + { + bool isWordSeparator = false; + + for (int separatorIndex = 0; separatorIndex < _wordSeparators.Length; separatorIndex++) + { + ReadOnlySpan<byte> separator = _wordSeparators[separatorIndex]; + + if (index + separator.Length < input.Length && input.Slice(index, separator.Length).SequenceEqual(separator)) + { + map.Set.TurnOn(index, separator.Length); + + index += separator.Length - 1; + isWordSeparator = true; + break; + } + } + + if (!isWordSeparator) + { + output[outputIndex++] = input[index]; + } + } + } + + map.Build(); + + return output[..outputIndex]; + } + + protected static int TrimEnd(ReadOnlySpan<byte> text, int offset) + { + for (int separatorIndex = 0; separatorIndex < _wordSeparators.Length; separatorIndex++) + { + ReadOnlySpan<byte> separator = _wordSeparators[separatorIndex]; + + if (offset >= separator.Length && text.Slice(offset - separator.Length, separator.Length).SequenceEqual(separator)) + { + offset -= separator.Length; + separatorIndex = -1; + } + } + + return offset; + } + + protected static bool IsPrefixedByWordSeparator(ReadOnlySpan<byte> text, int offset) + { + for (int separatorIndex = 0; separatorIndex < _wordSeparators.Length; separatorIndex++) + { + ReadOnlySpan<byte> separator = _wordSeparators[separatorIndex]; + + if (offset >= separator.Length && text.Slice(offset - separator.Length, separator.Length).SequenceEqual(separator)) + { + return true; + } + } + + return false; + } + + protected static bool IsWordSeparator(ReadOnlySpan<byte> text, int offset) + { + for (int separatorIndex = 0; separatorIndex < _wordSeparators.Length; separatorIndex++) + { + ReadOnlySpan<byte> separator = _wordSeparators[separatorIndex]; + + if (offset + separator.Length <= text.Length && text.Slice(offset, separator.Length).SequenceEqual(separator)) + { + return true; + } + } + + return false; + } + + protected static Span<byte> RemoveWordSeparators(Span<byte> output, ReadOnlySpan<byte> input, Sbv map, AhoCorasick notSeparatorTrie) + { + int outputIndex = 0; + + if (map.Set.BitVector.BitLength != 0) + { + for (int index = 0; index < input.Length;) + { + byte character = input[index]; + int characterByteLength = 1; + + if ((character & 0x80) != 0) + { + if (character >= 0xc2 && character < 0xe0) + { + characterByteLength = 2; + } + else if ((character & 0xf0) == 0xe0) + { + characterByteLength = 3; + } + else if ((character & 0xf8) == 0xf0) + { + characterByteLength = 4; + } + } + + characterByteLength = Math.Min(characterByteLength, input.Length - index); + + bool isWordSeparator = IsWordSeparator(input.Slice(index, characterByteLength), notSeparatorTrie); + if (isWordSeparator) + { + map.Set.TurnOn(index, characterByteLength); + } + else + { + output[outputIndex++] = input[index]; + } + + index += characterByteLength; + } + } + + map.Build(); + + return output[..outputIndex]; + } + + protected static bool IsWordSeparator(ReadOnlySpan<byte> text, AhoCorasick notSeparatorTrie) + { + string str = Encoding.UTF8.GetString(text); + + if (str.Length == 0) + { + return false; + } + + char character = str[0]; + + switch (character) + { + case '\0': + case '\uD800': + case '\uDB7F': + case '\uDB80': + case '\uDBFF': + case '\uDC00': + case '\uDFFF': + return false; + case '\u02E4': + case '\u02EC': + case '\u02EE': + case '\u0374': + case '\u037A': + case '\u0559': + case '\u0640': + case '\u06E5': + case '\u06E6': + case '\u07F4': + case '\u07F5': + case '\u07FA': + case '\u1C78': + case '\u1C79': + case '\u1C7A': + case '\u1C7B': + case '\u1C7C': + case '\uA4F8': + case '\uA4F9': + case '\uA4FA': + case '\uA4FB': + case '\uA4FC': + case '\uA4FD': + case '\uFF70': + case '\uFF9A': + case '\uFF9B': + return true; + } + + bool matched = false; + + notSeparatorTrie.Match(text, MatchSimple, ref matched); + + if (!matched) + { + switch (char.GetUnicodeCategory(character)) + { + case UnicodeCategory.NonSpacingMark: + case UnicodeCategory.SpacingCombiningMark: + case UnicodeCategory.EnclosingMark: + case UnicodeCategory.SpaceSeparator: + case UnicodeCategory.LineSeparator: + case UnicodeCategory.ParagraphSeparator: + case UnicodeCategory.Control: + case UnicodeCategory.Format: + case UnicodeCategory.Surrogate: + case UnicodeCategory.PrivateUse: + case UnicodeCategory.ConnectorPunctuation: + case UnicodeCategory.DashPunctuation: + case UnicodeCategory.OpenPunctuation: + case UnicodeCategory.ClosePunctuation: + case UnicodeCategory.InitialQuotePunctuation: + case UnicodeCategory.FinalQuotePunctuation: + case UnicodeCategory.OtherPunctuation: + case UnicodeCategory.MathSymbol: + case UnicodeCategory.CurrencySymbol: + return true; + } + } + + return false; + } + + protected static int GetUtf8Length(out int characterCount, ReadOnlySpan<byte> text, int maxCharacters) + { + int index; + + for (index = 0, characterCount = 0; index < text.Length && characterCount < maxCharacters; characterCount++) + { + byte character = text[index]; + int characterByteLength; + + if ((character & 0x80) != 0 || character == 0) + { + if (character >= 0xc2 && character < 0xe0) + { + characterByteLength = 2; + } + else if ((character & 0xf0) == 0xe0) + { + characterByteLength = 3; + } + else if ((character & 0xf8) == 0xf0) + { + characterByteLength = 4; + } + else + { + index = 0; + break; + } + } + else + { + characterByteLength = 1; + } + + index += characterByteLength; + } + + return index; + } + + protected static bool MatchSimple(ReadOnlySpan<byte> text, int matchStartOffset, int matchEndOffset, int nodeId, ref bool matched) + { + matched = true; + + return false; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Sbv.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Sbv.cs new file mode 100644 index 00000000..d6d0bfd6 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Sbv.cs @@ -0,0 +1,34 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class Sbv + { + private readonly SbvSelect _sbvSelect; + private readonly Set _set; + + public SbvSelect SbvSelect => _sbvSelect; + public Set Set => _set; + + public Sbv() + { + _sbvSelect = new(); + _set = new(); + } + + public Sbv(int length) + { + _sbvSelect = new(); + _set = new(length); + } + + public void Build() + { + _set.Build(); + _sbvSelect.Build(_set.BitVector.Array, _set.BitVector.BitLength); + } + + public bool Import(ref BinaryReader reader) + { + return _set.Import(ref reader) && _sbvSelect.Import(ref reader); + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SbvRank.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SbvRank.cs new file mode 100644 index 00000000..c541b1f5 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SbvRank.cs @@ -0,0 +1,162 @@ +using System; +using System.Numerics; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class SbvRank + { + private const int BitsPerWord = Set.BitsPerWord; + private const int Rank1Entries = 8; + private const int BitsPerRank0Entry = BitsPerWord * Rank1Entries; + + private uint[] _rank0; + private byte[] _rank1; + + public SbvRank() + { + } + + public SbvRank(ReadOnlySpan<uint> bitmap, int setCapacity) + { + Build(bitmap, setCapacity); + } + + public void Build(ReadOnlySpan<uint> bitmap, int setCapacity) + { + _rank0 = new uint[CalculateRank0Length(setCapacity)]; + _rank1 = new byte[CalculateRank1Length(setCapacity)]; + + BuildRankDictionary(_rank0, _rank1, (setCapacity + BitsPerWord - 1) / BitsPerWord, bitmap); + } + + private static void BuildRankDictionary(Span<uint> rank0, Span<byte> rank1, int length, ReadOnlySpan<uint> bitmap) + { + uint rank0Count; + uint rank1Count = 0; + + for (int index = 0; index < length; index++) + { + if ((index % Rank1Entries) != 0) + { + rank0Count = rank0[index / Rank1Entries]; + } + else + { + rank0[index / Rank1Entries] = rank1Count; + rank0Count = rank1Count; + } + + rank1[index] = (byte)(rank1Count - rank0Count); + + rank1Count += (uint)BitOperations.PopCount(bitmap[index]); + } + } + + public bool Import(ref BinaryReader reader, int setCapacity) + { + if (setCapacity == 0) + { + return true; + } + + int rank0Length = CalculateRank0Length(setCapacity); + int rank1Length = CalculateRank1Length(setCapacity); + + return reader.AllocateAndReadArray(ref _rank0, rank0Length) == rank0Length && + reader.AllocateAndReadArray(ref _rank1, rank1Length) == rank1Length; + } + + public int CalcRank1(int index, uint[] membershipBitmap) + { + int rank0Index = index / BitsPerRank0Entry; + int rank1Index = index / BitsPerWord; + + uint membershipBits = membershipBitmap[rank1Index] & (uint.MaxValue >> (BitsPerWord - 1 - (index % BitsPerWord))); + + return (int)_rank0[rank0Index] + _rank1[rank1Index] + BitOperations.PopCount(membershipBits); + } + + public int CalcSelect0(int index, int length, uint[] membershipBitmap) + { + int rank0Index; + + if (length > BitsPerRank0Entry) + { + int left = 0; + int right = (length + BitsPerRank0Entry - 1) / BitsPerRank0Entry; + + while (true) + { + int range = right - left; + if (range < 0) + { + range++; + } + + int middle = left + (range / 2); + + int foundIndex = middle * BitsPerRank0Entry - (int)_rank0[middle]; + + if ((uint)foundIndex <= (uint)index) + { + left = middle; + } + else + { + right = middle; + } + + if (right <= left + 1) + { + break; + } + } + + rank0Index = left; + } + else + { + rank0Index = 0; + } + + int lengthInWords = (length + BitsPerWord - 1) / BitsPerWord; + int rank1WordsCount = rank0Index == (length / BitsPerRank0Entry) && (lengthInWords % Rank1Entries) != 0 + ? lengthInWords % Rank1Entries + : Rank1Entries; + + int baseIndex = (int)_rank0[rank0Index] + rank0Index * -BitsPerRank0Entry + index; + int plainIndex; + int count; + int remainingBits; + uint membershipBits; + + for (plainIndex = rank0Index * Rank1Entries - 1, count = 0; count < rank1WordsCount; plainIndex++, count++) + { + int currentIndex = baseIndex + count * -BitsPerWord; + + if (_rank1[plainIndex + 1] + currentIndex < 0) + { + remainingBits = _rank1[plainIndex] + currentIndex + BitsPerWord; + membershipBits = ~membershipBitmap[plainIndex]; + + return plainIndex * BitsPerWord + SbvSelect.SelectPos(membershipBits, remainingBits); + } + } + + remainingBits = _rank1[plainIndex] + baseIndex + (rank1WordsCount - 1) * -BitsPerWord; + membershipBits = ~membershipBitmap[plainIndex]; + + return plainIndex * BitsPerWord + SbvSelect.SelectPos(membershipBits, remainingBits); + } + + private static int CalculateRank0Length(int setCapacity) + { + return (setCapacity / (BitsPerWord * Rank1Entries)) + 1; + } + + private static int CalculateRank1Length(int setCapacity) + { + return (setCapacity / BitsPerWord) + 1; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SbvSelect.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SbvSelect.cs new file mode 100644 index 00000000..54c3f8b0 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SbvSelect.cs @@ -0,0 +1,156 @@ +using System; +using System.Numerics; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class SbvSelect + { + private uint[] _array; + private BitVector32 _bv1; + private BitVector32 _bv2; + private SbvRank _sbvRank1; + private SbvRank _sbvRank2; + + public bool Import(ref BinaryReader reader) + { + if (!reader.Read(out int arrayLength) || + reader.AllocateAndReadArray(ref _array, arrayLength) != arrayLength) + { + return false; + } + + _bv1 = new(); + _bv2 = new(); + _sbvRank1 = new(); + _sbvRank2 = new(); + + return _bv1.Import(ref reader) && + _bv2.Import(ref reader) && + _sbvRank1.Import(ref reader, _bv1.BitLength) && + _sbvRank2.Import(ref reader, _bv2.BitLength); + } + + public void Build(ReadOnlySpan<uint> bitmap, int length) + { + int lengthInWords = (length + Set.BitsPerWord - 1) / Set.BitsPerWord; + + int rank0Length = 0; + int rank1Length = 0; + + if (lengthInWords != 0) + { + for (int index = 0; index < bitmap.Length; index++) + { + uint value = bitmap[index]; + + if (value != 0) + { + rank0Length++; + rank1Length += BitOperations.PopCount(value); + } + } + } + + _bv1 = new(rank0Length); + _bv2 = new(rank1Length); + _array = new uint[rank0Length]; + + bool setSequence = false; + int arrayIndex = 0; + uint unsetCount = 0; + rank0Length = 0; + rank1Length = 0; + + if (lengthInWords != 0) + { + for (int index = 0; index < bitmap.Length; index++) + { + uint value = bitmap[index]; + + if (value != 0) + { + if (!setSequence) + { + _bv1.TurnOn(rank0Length); + _array[arrayIndex++] = unsetCount; + setSequence = true; + } + + _bv2.TurnOn(rank1Length); + + rank0Length++; + rank1Length += BitOperations.PopCount(value); + } + else + { + unsetCount++; + setSequence = false; + } + } + } + + _sbvRank1 = new(_bv1.Array, _bv1.BitLength); + _sbvRank2 = new(_bv2.Array, _bv2.BitLength); + } + + public int Select(Set set, int index) + { + if (index < _bv2.BitLength) + { + int rank1PlainIndex = _sbvRank2.CalcRank1(index, _bv2.Array); + int rank0PlainIndex = _sbvRank1.CalcRank1(rank1PlainIndex - 1, _bv1.Array); + + int value = (int)_array[rank0PlainIndex - 1] + (rank1PlainIndex - 1); + + int baseBitIndex = 0; + + if (value != 0) + { + baseBitIndex = value * 32; + + int setBvLength = set.BitVector.BitLength; + int bitIndexBounded = baseBitIndex - 1; + + if (bitIndexBounded >= setBvLength) + { + bitIndexBounded = setBvLength - 1; + } + + index -= set.SbvRank.CalcRank1(bitIndexBounded, set.BitVector.Array); + } + + return SelectPos(set.BitVector.Array[value], index) + baseBitIndex; + } + + return -1; + } + + public static int SelectPos(uint membershipBits, int bitIndex) + { + // Skips "bitIndex" set bits, and returns the bit index of the next set bit. + // If there is no set bit after skipping the specified amount, returns 32. + + int bit; + int bitCount = bitIndex; + + for (bit = 0; bit < sizeof(uint) * 8;) + { + if (((membershipBits >> bit) & 1) != 0) + { + if (bitCount-- == 0) + { + break; + } + + bit++; + } + else + { + bit += BitOperations.TrailingZeroCount(membershipBits >> bit); + } + } + + return bit; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Set.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Set.cs new file mode 100644 index 00000000..559b7851 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Set.cs @@ -0,0 +1,73 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class Set + { + public const int BitsPerWord = 32; + + private readonly BitVector32 _bitVector; + private readonly SbvRank _sbvRank; + + public BitVector32 BitVector => _bitVector; + public SbvRank SbvRank => _sbvRank; + + public Set() + { + _bitVector = new(); + _sbvRank = new(); + } + + public Set(int length) + { + _bitVector = new(length); + _sbvRank = new(); + } + + public void Build() + { + _sbvRank.Build(_bitVector.Array, _bitVector.BitLength); + } + + public bool Import(ref BinaryReader reader) + { + return _bitVector.Import(ref reader) && _sbvRank.Import(ref reader, _bitVector.BitLength); + } + + public bool Has(int index) + { + return _bitVector.Has(index); + } + + public bool TurnOn(int index, int count) + { + return _bitVector.TurnOn(index, count); + } + + public bool TurnOn(int index) + { + return _bitVector.TurnOn(index); + } + + public int Rank1(int index) + { + if ((uint)index >= (uint)_bitVector.BitLength) + { + index = _bitVector.BitLength - 1; + } + + return _sbvRank.CalcRank1(index, _bitVector.Array); + } + + public int Select0(int index) + { + int length = _bitVector.BitLength; + int rankIndex = _sbvRank.CalcRank1(length - 1, _bitVector.Array); + + if ((uint)index < (uint)(length - rankIndex)) + { + return _sbvRank.CalcSelect0(index, length, _bitVector.Array); + } + + return -1; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SimilarFormTable.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SimilarFormTable.cs new file mode 100644 index 00000000..7999e6ca --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SimilarFormTable.cs @@ -0,0 +1,132 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class SimilarFormTable + { + private int _similarTableStringLength; + private int _canonicalTableStringLength; + private int _count; + private byte[][] _similarTable; + private byte[][] _canonicalTable; + + public bool Import(ref BinaryReader reader) + { + if (!reader.Read(out _similarTableStringLength) || + !reader.Read(out _canonicalTableStringLength) || + !reader.Read(out _count)) + { + return false; + } + + _similarTable = new byte[_count][]; + _canonicalTable = new byte[_count][]; + + if (_count < 1) + { + return true; + } + + for (int tableIndex = 0; tableIndex < _count; tableIndex++) + { + if (reader.AllocateAndReadArray(ref _similarTable[tableIndex], _similarTableStringLength) != _similarTableStringLength || + reader.AllocateAndReadArray(ref _canonicalTable[tableIndex], _canonicalTableStringLength) != _canonicalTableStringLength) + { + return false; + } + } + + return true; + } + + public ReadOnlySpan<byte> FindCanonicalString(ReadOnlySpan<byte> similarFormString) + { + int lowerBound = 0; + int upperBound = _count; + + for (int charIndex = 0; charIndex < similarFormString.Length; charIndex++) + { + byte character = similarFormString[charIndex]; + + int newLowerBound = GetLowerBound(character, charIndex, lowerBound - 1, upperBound - 1); + if (newLowerBound < 0 || _similarTable[newLowerBound][charIndex] != character) + { + return ReadOnlySpan<byte>.Empty; + } + + int newUpperBound = GetUpperBound(character, charIndex, lowerBound - 1, upperBound - 1); + if (newUpperBound < 0) + { + newUpperBound = upperBound; + } + + lowerBound = newLowerBound; + upperBound = newUpperBound; + } + + return _canonicalTable[lowerBound]; + } + + private int GetLowerBound(byte character, int charIndex, int left, int right) + { + while (right - left > 1) + { + int range = right + left; + + if (range < 0) + { + range++; + } + + int middle = range / 2; + + if (character <= _similarTable[middle][charIndex]) + { + right = middle; + } + else + { + left = middle; + } + } + + if (_similarTable[right][charIndex] < character) + { + return -1; + } + + return right; + } + + private int GetUpperBound(byte character, int charIndex, int left, int right) + { + while (right - left > 1) + { + int range = right + left; + + if (range < 0) + { + range++; + } + + int middle = range / 2; + + if (_similarTable[middle][charIndex] <= character) + { + left = middle; + } + else + { + right = middle; + } + } + + if (_similarTable[right][charIndex] <= character) + { + return -1; + } + + return right; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SparseSet.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SparseSet.cs new file mode 100644 index 00000000..6690203d --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/SparseSet.cs @@ -0,0 +1,125 @@ +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + class SparseSet + { + private const int BitsPerWord = Set.BitsPerWord; + + private ulong _rangeValuesCount; + private ulong _rangeStartValue; + private ulong _rangeEndValue; + private uint _count; + private uint _bitfieldLength; + private uint[] _bitfields; + private readonly Sbv _sbv = new(); + + public ulong RangeValuesCount => _rangeValuesCount; + public ulong RangeEndValue => _rangeEndValue; + + public bool Import(ref BinaryReader reader) + { + if (!reader.Read(out _rangeValuesCount) || + !reader.Read(out _rangeStartValue) || + !reader.Read(out _rangeEndValue) || + !reader.Read(out _count) || + !reader.Read(out _bitfieldLength) || + !reader.Read(out int arrayLength) || + reader.AllocateAndReadArray(ref _bitfields, arrayLength) != arrayLength) + { + return false; + } + + return _sbv.Import(ref reader); + } + + public bool Has(long index) + { + int plainIndex = Rank1(index); + + return plainIndex != 0 && Select1Ex(plainIndex - 1) == index; + } + + public int Rank1(long index) + { + uint count = _count; + + if ((ulong)index < _rangeStartValue || count == 0) + { + return 0; + } + + if (_rangeStartValue == (ulong)index || count < 3) + { + return 1; + } + + if (_rangeEndValue <= (ulong)index) + { + return (int)count; + } + + int left = 0; + int right = (int)count - 1; + + while (true) + { + int range = right - left; + if (range < 0) + { + range++; + } + + int middle = left + (range / 2); + + long foundIndex = Select1Ex(middle); + + if ((ulong)foundIndex <= (ulong)index) + { + left = middle; + } + else + { + right = middle; + } + + if (right <= left + 1) + { + break; + } + } + + return left + 1; + } + + public int Select1(int index) + { + return (int)Select1Ex(index); + } + + public long Select1Ex(int index) + { + if ((uint)index >= _count) + { + return -1L; + } + + int indexOffset = _sbv.SbvSelect.Select(_sbv.Set, index); + int bitfieldLength = (int)_bitfieldLength; + + int currentBitIndex = index * bitfieldLength; + int wordIndex = currentBitIndex / BitsPerWord; + int wordBitOffset = currentBitIndex % BitsPerWord; + + ulong value = _bitfields[wordIndex]; + + if (wordBitOffset + bitfieldLength > BitsPerWord) + { + value |= (ulong)_bitfields[wordIndex + 1] << 32; + } + + value >>= wordBitOffset; + value &= uint.MaxValue >> (BitsPerWord - bitfieldLength); + + return ((indexOffset - (uint)index) << bitfieldLength) + (int)value; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8ParseResult.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8ParseResult.cs new file mode 100644 index 00000000..bf065f86 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8ParseResult.cs @@ -0,0 +1,27 @@ +using Ryujinx.Horizon.Common; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + enum Utf8ParseResult + { + Success = 0, + InvalidCharacter = 2, + InvalidPointer = 0x16, + InvalidSize = 0x22, + InvalidString = 0x54, + } + + static class Utf8ParseResultExtensions + { + public static Result ToHorizonResult(this Utf8ParseResult result) + { + return result switch + { + Utf8ParseResult.Success => Result.Success, + Utf8ParseResult.InvalidSize => NgcResult.InvalidSize, + Utf8ParseResult.InvalidString => NgcResult.InvalidUtf8Encoding, + _ => NgcResult.InvalidPointer, + }; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8Text.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8Text.cs new file mode 100644 index 00000000..47f78049 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8Text.cs @@ -0,0 +1,104 @@ +using System; +using System.Text; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + readonly struct Utf8Text + { + private readonly byte[] _text; + private readonly int[] _charOffsets; + + public int CharacterCount => _charOffsets.Length - 1; + + public Utf8Text() + { + _text = Array.Empty<byte>(); + _charOffsets = Array.Empty<int>(); + } + + public Utf8Text(byte[] text) + { + _text = text; + + UTF8Encoding encoding = new(encoderShouldEmitUTF8Identifier: false, throwOnInvalidBytes: true); + + string str = encoding.GetString(text); + + _charOffsets = new int[str.Length + 1]; + + int offset = 0; + + for (int index = 0; index < str.Length; index++) + { + _charOffsets[index] = offset; + offset += encoding.GetByteCount(str.AsSpan().Slice(index, 1)); + } + + _charOffsets[str.Length] = offset; + } + + public Utf8Text(ReadOnlySpan<byte> text) : this(text.ToArray()) + { + } + + public static Utf8ParseResult Create(out Utf8Text utf8Text, ReadOnlySpan<byte> text) + { + try + { + utf8Text = new(text); + } + catch (ArgumentException) + { + utf8Text = default; + + return Utf8ParseResult.InvalidCharacter; + } + + return Utf8ParseResult.Success; + } + + public ReadOnlySpan<byte> AsSubstring(int startCharIndex, int endCharIndex) + { + int startOffset = _charOffsets[startCharIndex]; + int endOffset = _charOffsets[endCharIndex]; + + return _text.AsSpan()[startOffset..endOffset]; + } + + public Utf8Text AppendNullTerminated(ReadOnlySpan<byte> toAppend) + { + int length = toAppend.IndexOf((byte)0); + if (length >= 0) + { + toAppend = toAppend[..length]; + } + + return Append(toAppend); + } + + public Utf8Text Append(ReadOnlySpan<byte> toAppend) + { + byte[] combined = new byte[_text.Length + toAppend.Length]; + + _text.AsSpan().CopyTo(combined.AsSpan()[.._text.Length]); + toAppend.CopyTo(combined.AsSpan()[_text.Length..]); + + return new(combined); + } + + public void CopyTo(Span<byte> destination) + { + _text.CopyTo(destination[.._text.Length]); + + if (destination.Length > _text.Length) + { + destination[_text.Length] = 0; + } + } + + public ReadOnlySpan<byte> AsSpan() + { + return _text; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8Util.cs b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8Util.cs new file mode 100644 index 00000000..1bb543ba --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/Detail/Utf8Util.cs @@ -0,0 +1,41 @@ +using System; +using System.Text; + +namespace Ryujinx.Horizon.Sdk.Ngc.Detail +{ + static class Utf8Util + { + public static Utf8ParseResult NormalizeFormKC(Span<byte> output, ReadOnlySpan<byte> input) + { + int length = input.IndexOf((byte)0); + if (length >= 0) + { + input = input[..length]; + } + + UTF8Encoding encoding = new(encoderShouldEmitUTF8Identifier: false, throwOnInvalidBytes: true); + + string text; + + try + { + text = encoding.GetString(input); + } + catch (ArgumentException) + { + return Utf8ParseResult.InvalidCharacter; + } + + string normalizedText = text.Normalize(NormalizationForm.FormKC); + + int outputIndex = Encoding.UTF8.GetBytes(normalizedText, output); + + if (outputIndex < output.Length) + { + output[outputIndex] = 0; + } + + return Utf8ParseResult.Success; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/INgcService.cs b/src/Ryujinx.Horizon/Sdk/Ngc/INgcService.cs new file mode 100644 index 00000000..90f07822 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/INgcService.cs @@ -0,0 +1,14 @@ +using Ryujinx.Horizon.Common; +using Ryujinx.Horizon.Sdk.Sf; +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc +{ + interface INgcService : IServiceObject + { + Result GetContentVersion(out uint version); + Result Check(out uint checkMask, ReadOnlySpan<byte> text, uint regionMask, ProfanityFilterOption option); + Result Mask(out int maskedWordsCount, Span<byte> filteredText, ReadOnlySpan<byte> text, uint regionMask, ProfanityFilterOption option); + Result Reload(); + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/MaskMode.cs b/src/Ryujinx.Horizon/Sdk/Ngc/MaskMode.cs new file mode 100644 index 00000000..da0a4e6f --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/MaskMode.cs @@ -0,0 +1,8 @@ +namespace Ryujinx.Horizon.Sdk.Ngc +{ + enum MaskMode + { + Overwrite = 0, + ReplaceByOneCharacter = 1, + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/NgcResult.cs b/src/Ryujinx.Horizon/Sdk/Ngc/NgcResult.cs new file mode 100644 index 00000000..c53687fe --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/NgcResult.cs @@ -0,0 +1,16 @@ +using Ryujinx.Horizon.Common; + +namespace Ryujinx.Horizon.Sdk.Ngc +{ + static class NgcResult + { + private const int ModuleId = 146; + + public static Result InvalidPointer => new(ModuleId, 3); + public static Result InvalidSize => new(ModuleId, 4); + public static Result InvalidUtf8Encoding => new(ModuleId, 5); + public static Result AllocationFailed => new(ModuleId, 101); + public static Result DataAccessError => new(ModuleId, 102); + public static Result GenericUtf8Error => new(ModuleId, 103); + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/ProfanityFilterFlags.cs b/src/Ryujinx.Horizon/Sdk/Ngc/ProfanityFilterFlags.cs new file mode 100644 index 00000000..19542c00 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/ProfanityFilterFlags.cs @@ -0,0 +1,12 @@ +using System; + +namespace Ryujinx.Horizon.Sdk.Ngc +{ + [Flags] + enum ProfanityFilterFlags + { + None = 0, + MatchNormalizedFormKC = 1 << 0, + MatchSimilarForm = 1 << 1, + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/ProfanityFilterOption.cs b/src/Ryujinx.Horizon/Sdk/Ngc/ProfanityFilterOption.cs new file mode 100644 index 00000000..4a2ab715 --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/ProfanityFilterOption.cs @@ -0,0 +1,23 @@ +using System.Runtime.InteropServices; + +namespace Ryujinx.Horizon.Sdk.Ngc +{ + [StructLayout(LayoutKind.Sequential, Size = 0x14, Pack = 0x4)] + readonly struct ProfanityFilterOption + { + public readonly SkipMode SkipAtSignCheck; + public readonly MaskMode MaskMode; + public readonly ProfanityFilterFlags Flags; + public readonly uint SystemRegionMask; + public readonly uint Reserved; + + public ProfanityFilterOption(SkipMode skipAtSignCheck, MaskMode maskMode, ProfanityFilterFlags flags, uint systemRegionMask) + { + SkipAtSignCheck = skipAtSignCheck; + MaskMode = maskMode; + Flags = flags; + SystemRegionMask = systemRegionMask; + Reserved = 0; + } + } +} diff --git a/src/Ryujinx.Horizon/Sdk/Ngc/SkipMode.cs b/src/Ryujinx.Horizon/Sdk/Ngc/SkipMode.cs new file mode 100644 index 00000000..69ab48eb --- /dev/null +++ b/src/Ryujinx.Horizon/Sdk/Ngc/SkipMode.cs @@ -0,0 +1,8 @@ +namespace Ryujinx.Horizon.Sdk.Ngc +{ + enum SkipMode + { + DoNotSkip, + SkipAtSignCheck, + } +} diff --git a/src/Ryujinx.Horizon/ServiceTable.cs b/src/Ryujinx.Horizon/ServiceTable.cs index fd423aa2..41da222a 100644 --- a/src/Ryujinx.Horizon/ServiceTable.cs +++ b/src/Ryujinx.Horizon/ServiceTable.cs @@ -2,6 +2,7 @@ using Ryujinx.Horizon.Bcat; using Ryujinx.Horizon.Lbl; using Ryujinx.Horizon.LogManager; using Ryujinx.Horizon.MmNv; +using Ryujinx.Horizon.Ngc; using Ryujinx.Horizon.Prepo; using Ryujinx.Horizon.Wlan; using System.Collections.Generic; @@ -31,6 +32,7 @@ namespace Ryujinx.Horizon RegisterService<MmNvMain>(); RegisterService<PrepoMain>(); RegisterService<WlanMain>(); + RegisterService<NgcMain>(); _totalServices = entries.Count; |