From 458da8a94877677f086f06cdeecf959ec4283a33 Mon Sep 17 00:00:00 2001 From: Kelebek1 Date: Sat, 16 Jul 2022 23:48:45 +0100 Subject: Project Andio --- src/audio_core/renderer/nodes/bit_array.h | 25 ++++ src/audio_core/renderer/nodes/edge_matrix.cpp | 38 +++++ src/audio_core/renderer/nodes/edge_matrix.h | 82 +++++++++++ src/audio_core/renderer/nodes/node_states.cpp | 141 +++++++++++++++++++ src/audio_core/renderer/nodes/node_states.h | 195 ++++++++++++++++++++++++++ 5 files changed, 481 insertions(+) create mode 100644 src/audio_core/renderer/nodes/bit_array.h create mode 100644 src/audio_core/renderer/nodes/edge_matrix.cpp create mode 100644 src/audio_core/renderer/nodes/edge_matrix.h create mode 100644 src/audio_core/renderer/nodes/node_states.cpp create mode 100644 src/audio_core/renderer/nodes/node_states.h (limited to 'src/audio_core/renderer/nodes') 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 + +#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 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 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 + +#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 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 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(&buffer_[offset]), count}; + + offset += count * sizeof(u32); + + stack.stack = {reinterpret_cast(&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(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 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 +#include + +#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 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 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 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 results{}; + /// Stack used during the depth first search + Stack stack{}; +}; + +} // namespace AudioCore::AudioRenderer -- cgit v1.2.3