1 /* 2 * RowVisitor.h 3 * ------------ 4 * Purpose: Class for recording which rows of a song has already been visited, used for detecting when a module starts to loop. 5 * Notes : See implementation file. 6 * Authors: OpenMPT Devs 7 * The OpenMPT source code is released under the BSD license. Read LICENSE for more details. 8 */ 9 10 11 #pragma once 12 13 #include "openmpt/all/BuildSettings.hpp" 14 15 #include "mpt/base/span.hpp" 16 #include "Snd_defs.h" 17 18 #include <map> 19 20 OPENMPT_NAMESPACE_BEGIN 21 22 #if defined(MPT_BUILD_DEBUG) || defined(MPT_BUILD_FUZZER) 23 #define MPT_VERIFY_ROWVISITOR_LOOPSTATE 24 #endif // MPT_BUILD_DEBUG || MPT_BUILD_FUZZER 25 26 class CSoundFile; 27 class ModSequence; 28 struct ModChannel; 29 30 class RowVisitor 31 { 32 protected: 33 using ChannelStates = mpt::span<const ModChannel>; 34 35 class LoopState 36 { 37 static constexpr uint64 FNV1a_BASIS = 14695981039346656037ull; 38 static constexpr uint64 FNV1a_PRIME = 1099511628211ull; 39 uint64 m_hash = FNV1a_BASIS; 40 #ifdef MPT_VERIFY_ROWVISITOR_LOOPSTATE 41 std::vector<std::pair<uint8, uint8>> m_counts; // Actual loop counts to verify equality of hash-based implementation 42 #endif 43 44 public: 45 LoopState() = default; 46 LoopState(const ChannelStates &chnState, const bool ignoreRow); 47 LoopState(const LoopState &) = default; 48 LoopState(LoopState&&) = default; 49 LoopState &operator=(const LoopState &) = default; 50 LoopState &operator=(LoopState&&) = default; 51 52 [[nodiscard]] bool operator==(const LoopState &other) const noexcept 53 { 54 #ifdef MPT_VERIFY_ROWVISITOR_LOOPSTATE 55 if((m_counts == other.m_counts) != (m_hash == other.m_hash)) 56 std::abort(); 57 #endif 58 return m_hash == other.m_hash; 59 } 60 HasLoops()61 [[nodiscard]] bool HasLoops() const noexcept 62 { 63 #ifdef MPT_VERIFY_ROWVISITOR_LOOPSTATE 64 if(m_counts.empty() != (m_hash == FNV1a_BASIS)) 65 std::abort(); 66 #endif 67 return m_hash != FNV1a_BASIS; 68 } 69 }; 70 71 using LoopStateSet = std::vector<LoopState>; 72 73 // Stores for every (order, row) combination in the sequence if it has been visited or not. 74 std::vector<std::vector<bool>> m_visitedRows; 75 // Map for each row that's part of a pattern loop which loop states have been visited. Held in a separate data structure because it is sparse data in typical modules. 76 std::map<std::pair<ORDERINDEX, ROWINDEX>, LoopStateSet> m_visitedLoopStates; 77 78 const CSoundFile &m_sndFile; 79 ROWINDEX m_rowsSpentInLoops = 0; 80 const SEQUENCEINDEX m_sequence; 81 82 public: 83 RowVisitor(const CSoundFile &sndFile, SEQUENCEINDEX sequence = SEQUENCEINDEX_INVALID); 84 85 void MoveVisitedRowsFrom(RowVisitor &other) noexcept; 86 87 // Resize / Clear the row vector. 88 // If reset is true, the vector is not only resized to the required dimensions, but also completely cleared (i.e. all visited rows are unset). 89 void Initialize(bool reset); 90 91 // Mark an order/row combination as visited and returns true if it was visited before. 92 bool Visit(ORDERINDEX ord, ROWINDEX row, const ChannelStates &chnState, bool ignoreRow); 93 94 // Find the first row that has not been played yet. 95 // The order and row is stored in the order and row variables on success, on failure they contain invalid values. 96 // If onlyUnplayedPatterns is true (default), only completely unplayed patterns are considered, otherwise a song can start anywhere. 97 // Function returns true on success. 98 [[nodiscard]] bool GetFirstUnvisitedRow(ORDERINDEX &order, ROWINDEX &row, bool onlyUnplayedPatterns) const; 99 100 // Pattern loops can stack up exponentially, which can cause an effectively infinite amount of time to be spent on evaluating them. 101 // If this function returns true, module evaluation should be aborted because the pattern loops appear to be too complex. ModuleTooComplex(ROWINDEX threshold)102 [[nodiscard]] bool ModuleTooComplex(ROWINDEX threshold) const noexcept { return m_rowsSpentInLoops >= threshold; } ResetComplexity()103 void ResetComplexity() { m_rowsSpentInLoops = 0; } 104 105 protected: 106 // Get the needed vector size for a given pattern. 107 [[nodiscard]] ROWINDEX VisitedRowsVectorSize(PATTERNINDEX pattern) const noexcept; 108 109 [[nodiscard]] const ModSequence &Order() const; 110 }; 111 112 OPENMPT_NAMESPACE_END 113