1 files changed, 96 insertions, 0 deletions
diff --git a/src/Ryujinx.Cpu/LightningJit/Table/InstTableLevel.cs b/src/Ryujinx.Cpu/LightningJit/Table/InstTableLevel.cs
new file mode 100644
index 00000000..6567efee
--- /dev/null
+++ b/src/Ryujinx.Cpu/LightningJit/Table/InstTableLevel.cs
@@ -0,0 +1,96 @@
+using System.Collections.Generic;
+using System.Numerics;
+
+namespace Ryujinx.Cpu.LightningJit.Table
+{
+    class InstTableLevel<T> where T : IInstInfo
+    {
+        private readonly int _shift;
+        private readonly uint _mask;
+        private readonly InstTableLevel<T>[] _childs;
+        private readonly List<T> _insts;
+
+        private InstTableLevel(List<T> insts, uint baseMask)
+        {
+            uint commonEncodingMask = baseMask;
+
+            foreach (T info in insts)
+            {
+                commonEncodingMask &= info.EncodingMask;
+            }
+
+            if (commonEncodingMask != 0)
+            {
+                _shift = BitOperations.TrailingZeroCount(commonEncodingMask);
+                int bits = BitOperations.TrailingZeroCount(~(commonEncodingMask >> _shift));
+                int count = 1 << bits;
+                _mask = uint.MaxValue >> (32 - bits);
+
+                _childs = new InstTableLevel<T>[count];
+
+                List<T>[] splitList = new List<T>[count];
+
+                for (int index = 0; index < insts.Count; index++)
+                {
+                    int splitIndex = (int)((insts[index].Encoding >> _shift) & _mask);
+
+                    (splitList[splitIndex] ??= new()).Add(insts[index]);
+                }
+
+                for (int index = 0; index < count; index++)
+                {
+                    if (splitList[index] == null)
+                    {
+                        continue;
+                    }
+
+                    _childs[index] = new InstTableLevel<T>(splitList[index], baseMask & ~commonEncodingMask);
+                }
+            }
+            else
+            {
+                _insts = insts;
+            }
+        }
+
+        public InstTableLevel(List<T> insts) : this(insts, uint.MaxValue)
+        {
+        }
+
+        public bool TryFind(uint encoding, IsaVersion version, IsaFeature features, out T value)
+        {
+            if (_childs != null)
+            {
+                int index = (int)((encoding >> _shift) & _mask);
+
+                if (_childs[index] == null)
+                {
+                    value = default;
+
+                    return false;
+                }
+
+                return _childs[index].TryFind(encoding, version, features, out value);
+            }
+            else
+            {
+                foreach (T info in _insts)
+                {
+                    if ((encoding & info.EncodingMask) == info.Encoding &&
+                        !info.IsConstrained(encoding) &&
+                        info.Version <= version &&
+                        (info.Feature & features) == info.Feature)
+                    {
+                        value = info;
+
+                        return true;
+                    }
+                }
+
+                value = default;
+
+                return false;
+            }
+        }
+    }
+}