View Issue Details

IDProjectCategoryView StatusLast Update
0001146OpenMPT[All Projects] Playback Compatibilitypublic2019-03-01 14:12
ReportermanxAssigned To 
PriorityurgentSeverityblockReproducibilityalways
Status newResolutionopen 
Product VersionOpenMPT 1.28.00.* (old testing) 
Target VersionOpenMPT 1.29 / libopenmpt 0.5 (goals)Fixed in Version 
Summary0001146: Handle infinite loops
Description

libopenmpt, by default, should never enter an infinite playback loop, even if the module itself contains an infinite loop using pattern loops or pattern position jumps and pattern break to row.

TagsNo tags attached.
Has the bug occurred in previous versions?
Tested code revision (in case you know it)

Relationships

related to 0001206 new Odd behavior when seeking through this module in libopenmpt 

Activities

manx

manx

2019-01-24 12:07

administrator   ~0003825

Last edited: 2019-03-01 14:12

View 2 revisions

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))

  1. reset loop counts for patternloops on pattern change if not position jumping
  2. when looping, decrease that counter and reset all counters that are jumped-over-backwards to their original loop count value.
  3. 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.

Issue History

Date Modified Username Field Change
2018-09-22 06:28 manx New Issue
2018-09-23 09:56 manx Priority normal => urgent
2018-09-23 09:56 manx Severity major => block
2018-09-23 09:56 manx Target Version OpenMPT 1.29 / libopenmpt 0.5 (goals) => libopenmpt 0.4 (goals)
2018-09-24 11:25 manx Target Version libopenmpt 0.4 (goals) => OpenMPT 1.29 / libopenmpt 0.5 (goals)
2019-01-24 12:07 manx Note Added: 0003825
2019-02-28 20:40 Saga Musix Relationship added related to 0001206
2019-03-01 14:12 manx Note Edited: 0003825 View Revisions