diff options
Diffstat (limited to '')
-rw-r--r-- | src/audio_core/renderer/nodes/node_states.cpp | 141 |
1 files changed, 141 insertions, 0 deletions
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 |