1 files changed, 417 insertions, 0 deletions
diff --git a/src/core/file_sys/fssystem/fssystem_bucket_tree.h b/src/core/file_sys/fssystem/fssystem_bucket_tree.h
new file mode 100644
index 000000000..74a2f7583
--- /dev/null
+++ b/src/core/file_sys/fssystem/fssystem_bucket_tree.h
@@ -0,0 +1,417 @@
+// SPDX-FileCopyrightText: Copyright 2023 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <mutex>
+
+#include "common/alignment.h"
+#include "common/common_funcs.h"
+#include "common/common_types.h"
+#include "common/literals.h"
+
+#include "core/file_sys/vfs.h"
+#include "core/hle/result.h"
+
+namespace FileSys {
+
+using namespace Common::Literals;
+
+class BucketTree {
+    YUZU_NON_COPYABLE(BucketTree);
+    YUZU_NON_MOVEABLE(BucketTree);
+
+public:
+    static constexpr u32 Magic = Common::MakeMagic('B', 'K', 'T', 'R');
+    static constexpr u32 Version = 1;
+
+    static constexpr size_t NodeSizeMin = 1_KiB;
+    static constexpr size_t NodeSizeMax = 512_KiB;
+
+public:
+    class Visitor;
+
+    struct Header {
+        u32 magic;
+        u32 version;
+        s32 entry_count;
+        s32 reserved;
+
+        void Format(s32 entry_count);
+        Result Verify() const;
+    };
+    static_assert(std::is_trivial_v<Header>);
+    static_assert(sizeof(Header) == 0x10);
+
+    struct NodeHeader {
+        s32 index;
+        s32 count;
+        s64 offset;
+
+        Result Verify(s32 node_index, size_t node_size, size_t entry_size) const;
+    };
+    static_assert(std::is_trivial_v<NodeHeader>);
+    static_assert(sizeof(NodeHeader) == 0x10);
+
+    struct Offsets {
+        s64 start_offset;
+        s64 end_offset;
+
+        constexpr bool IsInclude(s64 offset) const {
+            return this->start_offset <= offset && offset < this->end_offset;
+        }
+
+        constexpr bool IsInclude(s64 offset, s64 size) const {
+            return size > 0 && this->start_offset <= offset && size <= (this->end_offset - offset);
+        }
+    };
+    static_assert(std::is_trivial_v<Offsets>);
+    static_assert(sizeof(Offsets) == 0x10);
+
+    struct OffsetCache {
+        Offsets offsets;
+        std::mutex mutex;
+        bool is_initialized;
+
+        OffsetCache() : offsets{-1, -1}, mutex(), is_initialized(false) {}
+    };
+
+    class ContinuousReadingInfo {
+    private:
+        size_t m_read_size;
+        s32 m_skip_count;
+        bool m_done;
+
+    public:
+        constexpr ContinuousReadingInfo() : m_read_size(), m_skip_count(), m_done() {}
+
+        constexpr void Reset() {
+            m_read_size = 0;
+            m_skip_count = 0;
+            m_done = false;
+        }
+
+        constexpr void SetSkipCount(s32 count) {
+            ASSERT(count >= 0);
+            m_skip_count = count;
+        }
+        constexpr s32 GetSkipCount() const {
+            return m_skip_count;
+        }
+        constexpr bool CheckNeedScan() {
+            return (--m_skip_count) <= 0;
+        }
+
+        constexpr void Done() {
+            m_read_size = 0;
+            m_done = true;
+        }
+        constexpr bool IsDone() const {
+            return m_done;
+        }
+
+        constexpr void SetReadSize(size_t size) {
+            m_read_size = size;
+        }
+        constexpr size_t GetReadSize() const {
+            return m_read_size;
+        }
+        constexpr bool CanDo() const {
+            return m_read_size > 0;
+        }
+    };
+
+private:
+    class NodeBuffer {
+        YUZU_NON_COPYABLE(NodeBuffer);
+
+    private:
+        void* m_header;
+
+    public:
+        NodeBuffer() : m_header() {}
+
+        ~NodeBuffer() {
+            ASSERT(m_header == nullptr);
+        }
+
+        NodeBuffer(NodeBuffer&& rhs) : m_header(rhs.m_header) {
+            rhs.m_header = nullptr;
+        }
+
+        NodeBuffer& operator=(NodeBuffer&& rhs) {
+            if (this != std::addressof(rhs)) {
+                ASSERT(m_header == nullptr);
+
+                m_header = rhs.m_header;
+
+                rhs.m_header = nullptr;
+            }
+            return *this;
+        }
+
+        bool Allocate(size_t node_size) {
+            ASSERT(m_header == nullptr);
+
+            m_header = ::operator new(node_size, std::align_val_t{sizeof(s64)});
+
+            // ASSERT(Common::IsAligned(m_header, sizeof(s64)));
+
+            return m_header != nullptr;
+        }
+
+        void Free(size_t node_size) {
+            if (m_header) {
+                ::operator delete(m_header, std::align_val_t{sizeof(s64)});
+                m_header = nullptr;
+            }
+        }
+
+        void FillZero(size_t node_size) const {
+            if (m_header) {
+                std::memset(m_header, 0, node_size);
+            }
+        }
+
+        NodeHeader* Get() const {
+            return reinterpret_cast<NodeHeader*>(m_header);
+        }
+
+        NodeHeader* operator->() const {
+            return this->Get();
+        }
+
+        template <typename T>
+        T* Get() const {
+            static_assert(std::is_trivial_v<T>);
+            static_assert(sizeof(T) == sizeof(NodeHeader));
+            return reinterpret_cast<T*>(m_header);
+        }
+    };
+
+private:
+    static constexpr s32 GetEntryCount(size_t node_size, size_t entry_size) {
+        return static_cast<s32>((node_size - sizeof(NodeHeader)) / entry_size);
+    }
+
+    static constexpr s32 GetOffsetCount(size_t node_size) {
+        return static_cast<s32>((node_size - sizeof(NodeHeader)) / sizeof(s64));
+    }
+
+    static constexpr s32 GetEntrySetCount(size_t node_size, size_t entry_size, s32 entry_count) {
+        const s32 entry_count_per_node = GetEntryCount(node_size, entry_size);
+        return Common::DivideUp(entry_count, entry_count_per_node);
+    }
+
+    static constexpr s32 GetNodeL2Count(size_t node_size, size_t entry_size, s32 entry_count) {
+        const s32 offset_count_per_node = GetOffsetCount(node_size);
+        const s32 entry_set_count = GetEntrySetCount(node_size, entry_size, entry_count);
+
+        if (entry_set_count <= offset_count_per_node) {
+            return 0;
+        }
+
+        const s32 node_l2_count = Common::DivideUp(entry_set_count, offset_count_per_node);
+        ASSERT(node_l2_count <= offset_count_per_node);
+
+        return Common::DivideUp(entry_set_count - (offset_count_per_node - (node_l2_count - 1)),
+                                offset_count_per_node);
+    }
+
+public:
+    static constexpr s64 QueryHeaderStorageSize() {
+        return sizeof(Header);
+    }
+
+    static constexpr s64 QueryNodeStorageSize(size_t node_size, size_t entry_size,
+                                              s32 entry_count) {
+        ASSERT(entry_size >= sizeof(s64));
+        ASSERT(node_size >= entry_size + sizeof(NodeHeader));
+        ASSERT(NodeSizeMin <= node_size && node_size <= NodeSizeMax);
+        ASSERT(Common::IsPowerOfTwo(node_size));
+        ASSERT(entry_count >= 0);
+
+        if (entry_count <= 0) {
+            return 0;
+        }
+        return (1 + GetNodeL2Count(node_size, entry_size, entry_count)) *
+               static_cast<s64>(node_size);
+    }
+
+    static constexpr s64 QueryEntryStorageSize(size_t node_size, size_t entry_size,
+                                               s32 entry_count) {
+        ASSERT(entry_size >= sizeof(s64));
+        ASSERT(node_size >= entry_size + sizeof(NodeHeader));
+        ASSERT(NodeSizeMin <= node_size && node_size <= NodeSizeMax);
+        ASSERT(Common::IsPowerOfTwo(node_size));
+        ASSERT(entry_count >= 0);
+
+        if (entry_count <= 0) {
+            return 0;
+        }
+        return GetEntrySetCount(node_size, entry_size, entry_count) * static_cast<s64>(node_size);
+    }
+
+private:
+    mutable VirtualFile m_node_storage;
+    mutable VirtualFile m_entry_storage;
+    NodeBuffer m_node_l1;
+    size_t m_node_size;
+    size_t m_entry_size;
+    s32 m_entry_count;
+    s32 m_offset_count;
+    s32 m_entry_set_count;
+    OffsetCache m_offset_cache;
+
+public:
+    BucketTree()
+        : m_node_storage(), m_entry_storage(), m_node_l1(), m_node_size(), m_entry_size(),
+          m_entry_count(), m_offset_count(), m_entry_set_count(), m_offset_cache() {}
+    ~BucketTree() {
+        this->Finalize();
+    }
+
+    Result Initialize(VirtualFile node_storage, VirtualFile entry_storage, size_t node_size,
+                      size_t entry_size, s32 entry_count);
+    void Initialize(size_t node_size, s64 end_offset);
+    void Finalize();
+
+    bool IsInitialized() const {
+        return m_node_size > 0;
+    }
+    bool IsEmpty() const {
+        return m_entry_size == 0;
+    }
+
+    Result Find(Visitor* visitor, s64 virtual_address);
+    Result InvalidateCache();
+
+    s32 GetEntryCount() const {
+        return m_entry_count;
+    }
+
+    Result GetOffsets(Offsets* out) {
+        // Ensure we have an offset cache.
+        R_TRY(this->EnsureOffsetCache());
+
+        // Set the output.
+        *out = m_offset_cache.offsets;
+        R_SUCCEED();
+    }
+
+private:
+    template <typename EntryType>
+    struct ContinuousReadingParam {
+        s64 offset;
+        size_t size;
+        NodeHeader entry_set;
+        s32 entry_index;
+        Offsets offsets;
+        EntryType entry;
+    };
+
+private:
+    template <typename EntryType>
+    Result ScanContinuousReading(ContinuousReadingInfo* out_info,
+                                 const ContinuousReadingParam<EntryType>& param) const;
+
+    bool IsExistL2() const {
+        return m_offset_count < m_entry_set_count;
+    }
+    bool IsExistOffsetL2OnL1() const {
+        return this->IsExistL2() && m_node_l1->count < m_offset_count;
+    }
+
+    s64 GetEntrySetIndex(s32 node_index, s32 offset_index) const {
+        return (m_offset_count - m_node_l1->count) + (m_offset_count * node_index) + offset_index;
+    }
+
+    Result EnsureOffsetCache();
+};
+
+class BucketTree::Visitor {
+    YUZU_NON_COPYABLE(Visitor);
+    YUZU_NON_MOVEABLE(Visitor);
+
+private:
+    friend class BucketTree;
+
+    union EntrySetHeader {
+        NodeHeader header;
+        struct Info {
+            s32 index;
+            s32 count;
+            s64 end;
+            s64 start;
+        } info;
+        static_assert(std::is_trivial_v<Info>);
+    };
+    static_assert(std::is_trivial_v<EntrySetHeader>);
+
+private:
+    const BucketTree* m_tree;
+    BucketTree::Offsets m_offsets;
+    void* m_entry;
+    s32 m_entry_index;
+    s32 m_entry_set_count;
+    EntrySetHeader m_entry_set;
+
+public:
+    constexpr Visitor()
+        : m_tree(), m_entry(), m_entry_index(-1), m_entry_set_count(), m_entry_set{} {}
+    ~Visitor() {
+        if (m_entry != nullptr) {
+            ::operator delete(m_entry, m_tree->m_entry_size);
+            m_tree = nullptr;
+            m_entry = nullptr;
+        }
+    }
+
+    bool IsValid() const {
+        return m_entry_index >= 0;
+    }
+    bool CanMoveNext() const {
+        return this->IsValid() && (m_entry_index + 1 < m_entry_set.info.count ||
+                                   m_entry_set.info.index + 1 < m_entry_set_count);
+    }
+    bool CanMovePrevious() const {
+        return this->IsValid() && (m_entry_index > 0 || m_entry_set.info.index > 0);
+    }
+
+    Result MoveNext();
+    Result MovePrevious();
+
+    template <typename EntryType>
+    Result ScanContinuousReading(ContinuousReadingInfo* out_info, s64 offset, size_t size) const;
+
+    const void* Get() const {
+        ASSERT(this->IsValid());
+        return m_entry;
+    }
+
+    template <typename T>
+    const T* Get() const {
+        ASSERT(this->IsValid());
+        return reinterpret_cast<const T*>(m_entry);
+    }
+
+    const BucketTree* GetTree() const {
+        return m_tree;
+    }
+
+private:
+    Result Initialize(const BucketTree* tree, const BucketTree::Offsets& offsets);
+
+    Result Find(s64 virtual_address);
+
+    Result FindEntrySet(s32* out_index, s64 virtual_address, s32 node_index);
+    Result FindEntrySetWithBuffer(s32* out_index, s64 virtual_address, s32 node_index,
+                                  char* buffer);
+    Result FindEntrySetWithoutBuffer(s32* out_index, s64 virtual_address, s32 node_index);
+
+    Result FindEntry(s64 virtual_address, s32 entry_set_index);
+    Result FindEntryWithBuffer(s64 virtual_address, s32 entry_set_index, char* buffer);
+    Result FindEntryWithoutBuffer(s64 virtual_address, s32 entry_set_index);
+};
+
+} // namespace FileSys