rough sketch of a possible algorithm/implementation

in playstate:

1. store a counter per row per channel, initialized with the loop count of the loop command, invalid if none. (i.e. store [order,row,chn,loopcount] for all loop/backwardpositionjump

commands (position jumps have implicit loop count 1, unless song has repeat-forever set, in which case they have infinite loop count), sorted in a vector for space and lookup efficiency,

memory should be pre-allocated when loading the file (or when editing in the tracker))

2. reset loop counts for patternloops on pattern change if not position jumping
3. when looping, decrease that counter and reset all counters that are jumped-over-backwards to their original loop count value.
4. done. this implements a proper (implicit) stack for all loopcounters. song will terminate, always. getlength does not need to estimate loops anymore but can calculate them precisely.

the algorithm guarantees termination by the following principle: the loop count for the latest (latest in song order-list + row ordering) backwards loop/jump is always strictly

monotonically descreasing, and earlier loop counts are only ever reset to their original (thus maximum) value. ordering loop counts in this order from song end to song start, interpreting

every loopcount as a digit and interpreting the concatenated number as an integer ALWAYS decreases the integer towards zero on every backward loop/jump. when it reaches 0, no further

backward loop/jump will ever be exectuted. termination is guaranteed by construction.

assumptions:

• algorithm is compatible with weird format quirks (i do not see why it shouldnt be, though)
• a backwards position jump in a particular order/row position always targets the same row in the jumped-to pattern (which as far as i can see is true, even for FT2). things will not

violate invariants even if this assumption does not hold. the worst case outcome is too short playback in truely extremely weird situations (because the loop count is decreased even if in

theory it might be possible that the target on the next occasion might be something entirely different, which would be desirable to execute).

in default libopenmpt playback mode (i.e. not allowing any infinite loops at all), this algorithm must be followed without exceptions. in repeat-song-n-times mode, backwardpositionjump

commands are initialized with n+1.

memory requirements:

• rowvisior: O(num_orders * max(rows_per_pattern) * sizeof(bool))
• loopcountstacks: O(num_orders * max(num_loopjumpcommands_per_pattern) * sizeof(int))

runtime complexity:

• rowvisitor: O(num_looped_rows) per loop, amortized O(1)
• loopcountstacks: O(max(num_loopjumpcommands_per_pattern)+log(num_loops_per_song)) per loop, amortized O(log(num_loops_per_song))

it can even support a mode with current infinite loop behaviour:

• on loop, reset not only the jumped-over loop counts, but instead reset all but the one currently executing, even the ones later in the pattern.

i think we can even completely remove all traces of rowvisitor.

https://forum.openmpt.org/index.php?topic=6367.0

Here's an initial implementation following the existing RowVisitor approach. It's far from optimal with regards to memory allocations, it's just a first try to check the feasibility of this idea.

The advantage of this approach is that it is completely independent of any pattern break / jump / loop handling and can thus be agnostic of those events and as a consequence of any compatibility quicks.

This implementation avoids memory allocations for every row on which no pattern loop is played by using variant<bool, set>: bool=false equals empty set, bool=true equals set with one trivial entry: all loop counts are zero.

This means that in the most common case (no pattern loops in module), there won't be any extra allocations, but as this uses a std::variant we still pay the space of a std::set on each row.

The next step could be to further optimize the common case from "variant<bool, set> inside vector inside vector" to "variant<bitset, set inside vector> inside vector". This would allow for the most common case (no pattern loops in a pattern) to consume much less memory and not even require an extra allocation outside of the order vector, for each pattern where the bitset is large enough (e.g. 256 entries would be enough for most modules).
Given a 64-bit build, any pattern without loops that is smaller than 256 rows would consume only 36 bytes in total instead of 32 bytes per row. For a module like Beyond The Network this would mean the memory usage is around 25KB instead of 800KB.

New tweaked version that is allocation-free during playback for most modules - unanticipated pattern loop quirks may still force some memory allocation, but that was the case with the original RowVisitor too.

Note that all new implementations have one common issue: While the accurate estimation of pattern loops is very desirable, it also opens an easy Denial of Service possibility: Even a sub-kilobyte IT file may contain nested pattern loops that would cause 16^64 pattern loop executions, which is obviously an infinity. libopenmpt will by default scan the length of all modules for subsong detection, so it will effectively lock up that thread forever.

I think it is required to put some arbitrary (maybe even configurable) limit on pattern loop evaluation in the context of length calculation. For example, this limit could be a number of rows since the player has been inside any sort of pattern loop. The limit should be a couple thousand of rows to be sure that no real-world module will ever be hit by this. If the limit is hit, libopenmpt could return infinity for song duration.

Proposed workaround and some evil files that are disproportionally long compared to their byte size due to nested loops.

More tweaking and optimizations; now the RowVisitor also handles the ProTracker Row Delay + Pattern Break quirk consistently for both regular playback and GetLength.

Previous patch accidentally inverted a min/max, breaking pre-allocation

While a variant closer to what is described in the first comment might be possible, I think it comes with a set of disadvantages that RowVisitor doesn have:

• It would require knowledge about pattern break and pattern loop handling (such as per-format command precedence etc.) to be duplicated into yet another place (the pre-allocation step)
• Other format quirks might also have to be added
• Pattern loops can actually be carried on between patterns in some tricky situations

On the other hand, extending RowVisitor with the loop state logic makes integration in the existing code very easy, and it can also be reasoned similarly easily that it will always terminate.

This is the state against current trunk with some minor updates here and there. I think this is now in a pretty much optimal state and I suggest to apply it as soon as possible to give it some thorough testing. For modules that have no pattern loops at all, memory consumption and allocation behaviour will be pretty much identical (in fact, a bit less memory will be consumed because the list of last visited rows no longer exists). For "normal" pattern loops as they will be found in most modules (trivial nesting that doesn't exploit any quirks), the code is allocation-free during playback. Only for complex modules that really try to exploit pattern loops (such as Black Queen) there will be some allocations during playback, but that was already the case with the old implementation, so this is not a new issue.

While some of those allocations could be avoided, it would make the implementation much more complex and error-prone because format-specific playback logic would have to be added to the pre-allocation code. The same would be true for an implementation that only looks at the jumps themselves, with the difference that it wouldn't work at all without this format-specific knowledge.

Updated against current trunk and minor refactoring (consolidating more code between GetLength() and ProcessRow() to avoid duplicate logic - in fact, some logic between the two functions was not identical, leading to incorrect time calculation for a loop-related S3M quirk)

Compile fixes for libopenmpt

The new code is active as of r14021. There may be some further tweaks happening before the 1.30 release, I have a few more ideas, but the feature itself doesn't have to wait for those.