1 /*
2 * RowVisitor.cpp
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 : The class keeps track of rows that have been visited by the player before.
6 * This way, we can tell when the module starts to loop, i.e. we can determine the song length,
7 * or find out that a given point of the module can never be reached.
8 *
9 * In some module formats, infinite loops can be achieved through pattern loops (e.g. E60 / E61 / E61 in one channel of a ProTracker MOD).
10 * To detect such loops, we store a set of loop counts across all channels encountered for each row.
11 * As soon as a set of loop counts is encountered twice for a specific row, we know that the track ends up in an infinite loop.
12 * As a result of this design, it is safe to evaluate pattern loops in CSoundFile::GetLength.
13 * Authors: OpenMPT Devs
14 * The OpenMPT source code is released under the BSD license. Read LICENSE for more details.
15 */
16
17
18 #include "stdafx.h"
19 #include "RowVisitor.h"
20 #include "Sndfile.h"
21
22 OPENMPT_NAMESPACE_BEGIN
23
LoopState(const ChannelStates & chnState,const bool ignoreRow)24 RowVisitor::LoopState::LoopState(const ChannelStates &chnState, const bool ignoreRow)
25 {
26 // Rather than storing the exact loop count vector, we compute a FNV-1a 64-bit hash of it.
27 // This means we can store the loop state in a small and fixed amount of memory.
28 // In theory there is the possibility of hash collisions for different loop states, but in practice,
29 // the relevant inputs for the hashing algorithm are extremely unlikely to produce collisions.
30 // There may be better hashing algorithms, but many of them are much more complex and cannot be applied easily in an incremental way.
31 uint64 hash = FNV1a_BASIS;
32 if(ignoreRow)
33 {
34 hash = (hash ^ 0xFFu) * FNV1a_PRIME;
35 #ifdef MPT_VERIFY_ROWVISITOR_LOOPSTATE
36 m_counts.emplace_back(uint8(0xFF), uint8(0xFF));
37 #endif
38 }
39
40 for(size_t chn = 0; chn < chnState.size(); chn++)
41 {
42 if(chnState[chn].nPatternLoopCount)
43 {
44 static_assert(MAX_BASECHANNELS <= 256, "Channel index cannot be used as byte input for hash generator");
45 static_assert(sizeof(chnState[0].nPatternLoopCount) <= sizeof(uint8), "Loop count cannot be used as byte input for hash generator");
46 hash = (hash ^ chn) * FNV1a_PRIME;
47 hash = (hash ^ chnState[chn].nPatternLoopCount) * FNV1a_PRIME;
48 #ifdef MPT_VERIFY_ROWVISITOR_LOOPSTATE
49 m_counts.emplace_back(static_cast<uint8>(chn), chnState[chn].nPatternLoopCount);
50 #endif
51 }
52 }
53 m_hash = hash;
54 }
55
56
RowVisitor(const CSoundFile & sndFile,SEQUENCEINDEX sequence)57 RowVisitor::RowVisitor(const CSoundFile &sndFile, SEQUENCEINDEX sequence)
58 : m_sndFile(sndFile)
59 , m_sequence(sequence)
60 {
61 Initialize(true);
62 }
63
64
MoveVisitedRowsFrom(RowVisitor & other)65 void RowVisitor::MoveVisitedRowsFrom(RowVisitor &other) noexcept
66 {
67 m_visitedRows = std::move(other.m_visitedRows);
68 m_visitedLoopStates = std::move(other.m_visitedLoopStates);
69 }
70
71
Order() const72 const ModSequence &RowVisitor::Order() const
73 {
74 if(m_sequence >= m_sndFile.Order.GetNumSequences())
75 return m_sndFile.Order();
76 else
77 return m_sndFile.Order(m_sequence);
78 }
79
80
81 // Resize / clear the row vector.
82 // If reset is true, the vector is not only resized to the required dimensions, but also completely cleared (i.e. all visited rows are reset).
Initialize(bool reset)83 void RowVisitor::Initialize(bool reset)
84 {
85 auto &order = Order();
86 const ORDERINDEX endOrder = order.GetLengthTailTrimmed();
87 m_visitedRows.resize(endOrder);
88 if(reset)
89 {
90 m_visitedLoopStates.clear();
91 m_rowsSpentInLoops = 0;
92 }
93
94 std::vector<uint8> loopCount;
95 std::vector<ORDERINDEX> visitedPatterns(m_sndFile.Patterns.GetNumPatterns(), ORDERINDEX_INVALID);
96 for(ORDERINDEX ord = 0; ord < endOrder; ord++)
97 {
98 const PATTERNINDEX pat = order[ord];
99 const ROWINDEX numRows = VisitedRowsVectorSize(pat);
100 auto &visitedRows = m_visitedRows[ord];
101
102 if(reset)
103 visitedRows.assign(numRows, false);
104 else
105 visitedRows.resize(numRows, false);
106
107 if(!order.IsValidPat(ord))
108 continue;
109
110 const ROWINDEX startRow = std::min(static_cast<ROWINDEX>(reset ? 0 : visitedRows.size()), numRows);
111 auto insertionHint = m_visitedLoopStates.end();
112
113 if(visitedPatterns[pat] != ORDERINDEX_INVALID)
114 {
115 // We visited this pattern before, copy over the results
116 const auto begin = m_visitedLoopStates.lower_bound({visitedPatterns[pat], startRow});
117 const auto end = (begin != m_visitedLoopStates.end()) ? m_visitedLoopStates.lower_bound({visitedPatterns[pat], numRows}) : m_visitedLoopStates.end();
118 for(auto pos = begin; pos != end; ++pos)
119 {
120 LoopStateSet loopStates;
121 loopStates.reserve(pos->second.capacity());
122 insertionHint = ++m_visitedLoopStates.insert_or_assign(insertionHint, {ord, pos->first.second}, std::move(loopStates));
123 }
124 continue;
125 }
126
127 // Pre-allocate loop count state
128 const auto &pattern = m_sndFile.Patterns[pat];
129 loopCount.assign(pattern.GetNumChannels(), 0);
130 for(ROWINDEX i = numRows; i != startRow; i--)
131 {
132 const ROWINDEX row = i - 1;
133 uint32 maxLoopStates = 1;
134 auto m = pattern.GetRow(row);
135 // Break condition: If it's more than 16, it's probably wrong :) exact loop count depends on how loops overlap.
136 for(CHANNELINDEX chn = 0; chn < pattern.GetNumChannels() && maxLoopStates < 16; chn++, m++)
137 {
138 auto count = loopCount[chn];
139 if((m->command == CMD_S3MCMDEX && (m->param & 0xF0) == 0xB0) || (m->command == CMD_MODCMDEX && (m->param & 0xF0) == 0x60))
140 {
141 loopCount[chn] = (m->param & 0x0F);
142 if(loopCount[chn])
143 count = loopCount[chn];
144 }
145 if(count)
146 maxLoopStates *= (count + 1);
147 }
148 if(maxLoopStates > 1)
149 {
150 LoopStateSet loopStates;
151 loopStates.reserve(maxLoopStates);
152 insertionHint = m_visitedLoopStates.insert_or_assign(insertionHint, {ord, row}, std::move(loopStates));
153 }
154 }
155 // Only use this order as a blueprint for other orders using the same pattern if we fully parsed the pattern.
156 if(startRow == 0)
157 visitedPatterns[pat] = ord;
158 }
159 }
160
161
162 // Mark an order/row combination as visited and returns true if it was visited before.
Visit(ORDERINDEX ord,ROWINDEX row,const ChannelStates & chnState,bool ignoreRow)163 bool RowVisitor::Visit(ORDERINDEX ord, ROWINDEX row, const ChannelStates &chnState, bool ignoreRow)
164 {
165 auto &order = Order();
166 if(ord >= order.size() || row >= VisitedRowsVectorSize(order[ord]))
167 return false;
168
169 // The module might have been edited in the meantime - so we have to extend this a bit.
170 if(ord >= m_visitedRows.size() || row >= m_visitedRows[ord].size())
171 {
172 Initialize(false);
173 // If it's still past the end of the vector, this means that ord >= order.GetLengthTailTrimmed(), i.e. we are trying to play an empty order.
174 if(ord >= m_visitedRows.size())
175 return false;
176 }
177
178 MPT_ASSERT(chnState.size() >= m_sndFile.GetNumChannels());
179 LoopState newState{chnState.first(m_sndFile.GetNumChannels()), ignoreRow};
180 const auto rowLoopState = m_visitedLoopStates.find({ord, row});
181 const bool oldHadLoops = (rowLoopState != m_visitedLoopStates.end() && !rowLoopState->second.empty());
182 const bool newHasLoops = newState.HasLoops();
183 const bool wasVisited = m_visitedRows[ord][row];
184
185 // Check if new state is part of row state already. If so, we visited this row already and thus the module must be looping
186 if(!oldHadLoops && !newHasLoops && wasVisited)
187 return true;
188 if(oldHadLoops && mpt::contains(rowLoopState->second, newState))
189 return true;
190
191 if(newHasLoops)
192 m_rowsSpentInLoops++;
193
194 if(oldHadLoops || newHasLoops)
195 {
196 // Convert to set representation if it isn't already
197 if(!oldHadLoops && wasVisited)
198 m_visitedLoopStates[{ord, row}].emplace_back();
199 m_visitedLoopStates[{ord, row}].emplace_back(std::move(newState));
200 }
201 m_visitedRows[ord][row] = true;
202 return false;
203 }
204
205
206 // Get the needed vector size for a given pattern.
VisitedRowsVectorSize(PATTERNINDEX pattern) const207 ROWINDEX RowVisitor::VisitedRowsVectorSize(PATTERNINDEX pattern) const noexcept
208 {
209 if(m_sndFile.Patterns.IsValidPat(pattern))
210 return m_sndFile.Patterns[pattern].GetNumRows();
211 else
212 return 1; // Non-existing patterns consist of a "fake" row.
213 }
214
215
216 // Find the first row that has not been played yet.
217 // The order and row is stored in the order and row variables on success, on failure they contain invalid values.
218 // If onlyUnplayedPatterns is true (default), only completely unplayed patterns are considered, otherwise a song can start on any unplayed row.
219 // Function returns true on success.
GetFirstUnvisitedRow(ORDERINDEX & ord,ROWINDEX & row,bool onlyUnplayedPatterns) const220 bool RowVisitor::GetFirstUnvisitedRow(ORDERINDEX &ord, ROWINDEX &row, bool onlyUnplayedPatterns) const
221 {
222 const auto &order = Order();
223 const ORDERINDEX endOrder = order.GetLengthTailTrimmed();
224 for(ord = 0; ord < endOrder; ord++)
225 {
226 if(!order.IsValidPat(ord))
227 continue;
228
229 if(ord >= m_visitedRows.size())
230 {
231 // Not yet initialized => unvisited
232 row = 0;
233 return true;
234 }
235
236 const auto &visitedRows = m_visitedRows[ord];
237 const auto firstUnplayedRow = std::find(visitedRows.begin(), visitedRows.end(), onlyUnplayedPatterns);
238 if(onlyUnplayedPatterns && firstUnplayedRow == visitedRows.end())
239 {
240 // No row of this pattern has been played yet.
241 row = 0;
242 return true;
243 } else if(!onlyUnplayedPatterns)
244 {
245 // Return the first unplayed row in this pattern
246 if(firstUnplayedRow != visitedRows.end())
247 {
248 row = static_cast<ROWINDEX>(std::distance(visitedRows.begin(), firstUnplayedRow));
249 return true;
250 }
251 if(visitedRows.size() < m_sndFile.Patterns[order[ord]].GetNumRows())
252 {
253 // History is not fully initialized
254 row = static_cast<ROWINDEX>(visitedRows.size());
255 return true;
256 }
257 }
258 }
259
260 // Didn't find anything :(
261 ord = ORDERINDEX_INVALID;
262 row = ROWINDEX_INVALID;
263 return false;
264 }
265
266
267 OPENMPT_NAMESPACE_END
268