5 files changed, 481 insertions, 0 deletions

diff --git a/src/audio_core/renderer/nodes/bit_array.h b/src/audio_core/renderer/nodes/bit_array.h
new file mode 100644
index 000000000..b0d53cd51
--- /dev/null
+++ b/src/audio_core/renderer/nodes/bit_array.h
@@ -0,0 +1,25 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <vector>
+
+#include "common/common_types.h"
+
+namespace AudioCore::AudioRenderer {
+/**
+ * Represents an array of bits used for nodes and edges for the mixing graph.
+ */
+struct BitArray {
+    void reset() {
+        buffer.assign(buffer.size(), false);
+    }
+
+    /// Bits
+    std::vector<bool> buffer{};
+    /// Size of the buffer
+    u32 size{};
+};
+
+} // namespace AudioCore::AudioRenderer
diff --git a/src/audio_core/renderer/nodes/edge_matrix.cpp b/src/audio_core/renderer/nodes/edge_matrix.cpp
new file mode 100644
index 000000000..5573f33b9
--- /dev/null
+++ b/src/audio_core/renderer/nodes/edge_matrix.cpp
@@ -0,0 +1,38 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include "audio_core/renderer/nodes/edge_matrix.h"
+
+namespace AudioCore::AudioRenderer {
+
+void EdgeMatrix::Initialize([[maybe_unused]] std::span<u8> buffer,
+                            [[maybe_unused]] const u64 node_buffer_size, const u32 count_) {
+    count = count_;
+    edges.buffer.resize(count_ * count_);
+    edges.size = count_ * count_;
+    edges.reset();
+}
+
+bool EdgeMatrix::Connected(const u32 id, const u32 destination_id) const {
+    return edges.buffer[count * id + destination_id];
+}
+
+void EdgeMatrix::Connect(const u32 id, const u32 destination_id) {
+    edges.buffer[count * id + destination_id] = true;
+}
+
+void EdgeMatrix::Disconnect(const u32 id, const u32 destination_id) {
+    edges.buffer[count * id + destination_id] = false;
+}
+
+void EdgeMatrix::RemoveEdges(const u32 id) {
+    for (u32 dest = 0; dest < count; dest++) {
+        Disconnect(id, dest);
+    }
+}
+
+u32 EdgeMatrix::GetNodeCount() const {
+    return count;
+}
+
+} // namespace AudioCore::AudioRenderer
diff --git a/src/audio_core/renderer/nodes/edge_matrix.h b/src/audio_core/renderer/nodes/edge_matrix.h
new file mode 100644
index 000000000..27a20e43e
--- /dev/null
+++ b/src/audio_core/renderer/nodes/edge_matrix.h
@@ -0,0 +1,82 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <span>
+
+#include "audio_core/renderer/nodes/bit_array.h"
+#include "common/alignment.h"
+#include "common/common_types.h"
+
+namespace AudioCore::AudioRenderer {
+/**
+ * An edge matrix, holding the connections for each node to every other node in the graph.
+ */
+class EdgeMatrix {
+public:
+    /**
+     * Calculate the size required for its workbuffer.
+     *
+     * @param count - The number of nodes in the graph.
+     * @return The required workbuffer size.
+     */
+    static u64 GetWorkBufferSize(u32 count) {
+        return Common::AlignUp(count * count, 0x40) / sizeof(u64);
+    }
+
+    /**
+     * Initialize this edge matrix.
+     *
+     * @param buffer           - The workbuffer to use. Unused.
+     * @param node_buffer_size - The size of the workbuffer. Unused.
+     * @param count            - The number of nodes in the graph.
+     */
+    void Initialize(std::span<u8> buffer, u64 node_buffer_size, u32 count);
+
+    /**
+     * Check if a node is connected to another.
+     *
+     * @param id             - The node id to check.
+     * @param destination_id - Node id to check connection with.
+     */
+    bool Connected(u32 id, u32 destination_id) const;
+
+    /**
+     * Connect a node to another.
+     *
+     * @param id             - The node id to connect.
+     * @param destination_id - Destination to connect it to.
+     */
+    void Connect(u32 id, u32 destination_id);
+
+    /**
+     * Disconnect a node from another.
+     *
+     * @param id             - The node id to disconnect.
+     * @param destination_id - Destination to disconnect it from.
+     */
+    void Disconnect(u32 id, u32 destination_id);
+
+    /**
+     * Remove all connections for a given node.
+     *
+     * @param id - The node id to disconnect.
+     */
+    void RemoveEdges(u32 id);
+
+    /**
+     * Get the number of nodes in the graph.
+     *
+     * @return Number of nodes.
+     */
+    u32 GetNodeCount() const;
+
+private:
+    /// Edges for the current graph
+    BitArray edges;
+    /// Number of nodes (not edges) in the graph
+    u32 count;
+};
+
+} // namespace AudioCore::AudioRenderer
diff --git a/src/audio_core/renderer/nodes/node_states.cpp b/src/audio_core/renderer/nodes/node_states.cpp
new file mode 100644
index 000000000..1821a51e6
--- /dev/null
+++ b/src/audio_core/renderer/nodes/node_states.cpp
@@ -0,0 +1,141 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include "audio_core/renderer/nodes/node_states.h"
+#include "common/logging/log.h"
+
+namespace AudioCore::AudioRenderer {
+
+void NodeStates::Initialize(std::span<u8> buffer_, [[maybe_unused]] const u64 node_buffer_size,
+                            const u32 count) {
+    u64 num_blocks{Common::AlignUp(count, 0x40) / sizeof(u64)};
+    u64 offset{0};
+
+    node_count = count;
+
+    nodes_found.buffer.resize(count);
+    nodes_found.size = count;
+    nodes_found.reset();
+
+    offset += num_blocks;
+
+    nodes_complete.buffer.resize(count);
+    nodes_complete.size = count;
+    nodes_complete.reset();
+
+    offset += num_blocks;
+
+    results = {reinterpret_cast<u32*>(&buffer_[offset]), count};
+
+    offset += count * sizeof(u32);
+
+    stack.stack = {reinterpret_cast<u32*>(&buffer_[offset]), count * count};
+    stack.size = count * count;
+    stack.unk_10 = count * count;
+
+    offset += count * count * sizeof(u32);
+}
+
+bool NodeStates::Tsort(const EdgeMatrix& edge_matrix) {
+    return DepthFirstSearch(edge_matrix, stack);
+}
+
+bool NodeStates::DepthFirstSearch(const EdgeMatrix& edge_matrix, Stack& stack_) {
+    ResetState();
+
+    for (u32 node_id = 0; node_id < node_count; node_id++) {
+        if (GetState(node_id) == SearchState::Unknown) {
+            stack_.push(node_id);
+        }
+
+        while (stack_.Count() > 0) {
+            auto current_node{stack_.top()};
+            switch (GetState(current_node)) {
+            case SearchState::Unknown:
+                SetState(current_node, SearchState::Found);
+                break;
+            case SearchState::Found:
+                SetState(current_node, SearchState::Complete);
+                PushTsortResult(current_node);
+                stack_.pop();
+                continue;
+            case SearchState::Complete:
+                stack_.pop();
+                continue;
+            }
+
+            const auto edge_count{edge_matrix.GetNodeCount()};
+            for (u32 edge_id = 0; edge_id < edge_count; edge_id++) {
+                if (!edge_matrix.Connected(current_node, edge_id)) {
+                    continue;
+                }
+
+                switch (GetState(edge_id)) {
+                case SearchState::Unknown:
+                    stack_.push(edge_id);
+                    break;
+                case SearchState::Found:
+                    LOG_ERROR(Service_Audio,
+                              "Cycle detected in the node graph, graph is not a DAG! "
+                              "Bailing to avoid an infinite loop");
+                    ResetState();
+                    return false;
+                case SearchState::Complete:
+                    break;
+                }
+            }
+        }
+    }
+
+    return true;
+}
+
+NodeStates::SearchState NodeStates::GetState(const u32 id) const {
+    if (nodes_found.buffer[id]) {
+        return SearchState::Found;
+    } else if (nodes_complete.buffer[id]) {
+        return SearchState::Complete;
+    }
+    return SearchState::Unknown;
+}
+
+void NodeStates::PushTsortResult(const u32 id) {
+    results[result_pos++] = id;
+}
+
+void NodeStates::SetState(const u32 id, const SearchState state) {
+    switch (state) {
+    case SearchState::Complete:
+        nodes_found.buffer[id] = false;
+        nodes_complete.buffer[id] = true;
+        break;
+    case SearchState::Found:
+        nodes_found.buffer[id] = true;
+        nodes_complete.buffer[id] = false;
+        break;
+    case SearchState::Unknown:
+        nodes_found.buffer[id] = false;
+        nodes_complete.buffer[id] = false;
+        break;
+    default:
+        LOG_ERROR(Service_Audio, "Unknown node SearchState {}", static_cast<u32>(state));
+        break;
+    }
+}
+
+void NodeStates::ResetState() {
+    nodes_found.reset();
+    nodes_complete.reset();
+    std::fill(results.begin(), results.end(), -1);
+    result_pos = 0;
+}
+
+u32 NodeStates::GetNodeCount() const {
+    return node_count;
+}
+
+std::vector<s32> NodeStates::GetSortedResuls() const {
+    return {results.rbegin(), results.rbegin() + result_pos};
+}
+
+} // namespace AudioCore::AudioRenderer
diff --git a/src/audio_core/renderer/nodes/node_states.h b/src/audio_core/renderer/nodes/node_states.h
new file mode 100644
index 000000000..a1e0958a2
--- /dev/null
+++ b/src/audio_core/renderer/nodes/node_states.h
@@ -0,0 +1,195 @@
+// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <span>
+#include <vector>
+
+#include "audio_core/renderer/nodes/edge_matrix.h"
+#include "common/alignment.h"
+#include "common/common_types.h"
+
+namespace AudioCore::AudioRenderer {
+/**
+ * Graph utility functions for sorting and getting results from the DAG.
+ */
+class NodeStates {
+    /**
+     * State of a node in the depth first search.
+     */
+    enum class SearchState {
+        Unknown,
+        Found,
+        Complete,
+    };
+
+    /**
+     * Stack used for a depth first search.
+     */
+    struct Stack {
+        /**
+         * Calculate the workbuffer size required for this stack.
+         *
+         * @param count - Maximum number of nodes for the stack.
+         * @return Required buffer size.
+         */
+        static u32 CalcBufferSize(u32 count) {
+            return count * sizeof(u32);
+        }
+
+        /**
+         * Reset the stack back to default.
+         *
+         * @param buffer_ - The new buffer to use.
+         * @param size_   - The size of the new buffer.
+         */
+        void Reset(u32* buffer_, u32 size_) {
+            stack = {buffer_, size_};
+            size = size_;
+            pos = 0;
+            unk_10 = size_;
+        }
+
+        /**
+         * Get the current stack position.
+         *
+         * @return The current stack position.
+         */
+        u32 Count() {
+            return pos;
+        }
+
+        /**
+         * Push a new node to the stack.
+         *
+         * @param data - The node to push.
+         */
+        void push(u32 data) {
+            stack[pos++] = data;
+        }
+
+        /**
+         * Pop a node from the stack.
+         *
+         * @return The node on the top of the stack.
+         */
+        u32 pop() {
+            return stack[--pos];
+        }
+
+        /**
+         * Get the top of the stack without popping.
+         *
+         * @return The node on the top of the stack.
+         */
+        u32 top() {
+            return stack[pos - 1];
+        }
+
+        /// Buffer for the stack
+        std::span<u32> stack{};
+        /// Size of the stack buffer
+        u32 size{};
+        /// Current stack position
+        u32 pos{};
+        /// Unknown
+        u32 unk_10{};
+    };
+
+public:
+    /**
+     * Calculate the workbuffer size required for the node states.
+     *
+     * @param count - The number of nodes.
+     * @return The required workbuffer size.
+     */
+    static u64 GetWorkBufferSize(u32 count) {
+        return (Common::AlignUp(count, 0x40) / sizeof(u64)) * 2 + count * sizeof(BitArray) +
+               count * Stack::CalcBufferSize(count);
+    }
+
+    /**
+     * Initialize the node states.
+     *
+     * @param buffer           - The workbuffer to use. Unused.
+     * @param node_buffer_size - The size of the workbuffer. Unused.
+     * @param count            - The number of nodes in the graph.
+     */
+    void Initialize(std::span<u8> nodes, u64 node_buffer_size, u32 count);
+
+    /**
+     * Sort the graph. Only calls DepthFirstSearch.
+     *
+     * @param edge_matrix - The edge matrix used to hold the connections between nodes.
+     * @return True if the sort was successful, otherwise false.
+     */
+    bool Tsort(const EdgeMatrix& edge_matrix);
+
+    /**
+     * Sort the graph via depth first search.
+     *
+     * @param edge_matrix - The edge matrix used to hold the connections between nodes.
+     * @param stack       - The stack used for pushing and popping nodes.
+     * @return True if the sort was successful, otherwise false.
+     */
+    bool DepthFirstSearch(const EdgeMatrix& edge_matrix, Stack& stack);
+
+    /**
+     * Get the search state of a given node.
+     *
+     * @param id - The node id to check.
+     * @return The node's search state. See SearchState
+     */
+    SearchState GetState(u32 id) const;
+
+    /**
+     * Push a node id to the results buffer when found in the DFS.
+     *
+     * @param id - The node id to push.
+     */
+    void PushTsortResult(u32 id);
+
+    /**
+     * Set the state of a node.
+     *
+     * @param id - The node id to alter.
+     * @param state - The new search state.
+     */
+    void SetState(u32 id, SearchState state);
+
+    /**
+     * Reset the nodes found, complete and the results.
+     */
+    void ResetState();
+
+    /**
+     * Get the number of nodes in the graph.
+     *
+     * @return The number of nodes.
+     */
+    u32 GetNodeCount() const;
+
+    /**
+     * Get the sorted results from the DFS.
+     *
+     * @return Vector of nodes in reverse order.
+     */
+    std::vector<s32> GetSortedResuls() const;
+
+private:
+    /// Number of nodes in the graph
+    u32 node_count{};
+    /// Position in results buffer
+    u32 result_pos{};
+    /// List of nodes found
+    BitArray nodes_found{};
+    /// List of nodes completed
+    BitArray nodes_complete{};
+    /// List of results from the depth first search
+    std::span<u32> results{};
+    /// Stack used during the depth first search
+    Stack stack{};
+};
+
+} // namespace AudioCore::AudioRenderer