demux: change backward-overlap to keyframe ranges instead of packets

This seems more useful in general. This change also happens to fix a
miscounting of preroll packets when some of them were "rounded" away,
and which could make it stuck.

Also a simple intra-refresh encode with x264 (and muxed to mkv by it)
seems to work now. I guess I misinterpreted earlier results.

2 files changed, 41 insertions, 39 deletions

diff --git a/DOCS/man/options.rst b/DOCS/man/options.rst
index 99bb8cad8d..0631fd6a12 100644
--- a/DOCS/man/options.rst
+++ b/DOCS/man/options.rst
@@ -543,7 +543,8 @@ Playback Control
     accept suffixes such as ``KiB`` and ``MiB``.
 
 ``--video-backward-overlap=<auto|number>``, ``--audio-backward-overlap=<auto|number>``
-    Number of overlapping packets to use for backward decoding (default: auto).
+    Number of overlapping keyframe ranges to use for backward decoding (default:
+    auto) ("keyframe" to be understood as in the mpv/ffmpeg specific meaning).
     Backward decoding works by forward decoding in small steps. Some codecs
     cannot restart decoding from any packet (even if it's marked as seek point),
     which becomes noticeable with backward decoding (in theory this is a problem
@@ -554,10 +555,9 @@ Playback Control
     discard the output. This option controls how many packets to feed. The
     ``auto`` choice is currently hardcoded to 1 for audio, and 0 for video.
 
-    ``--video-backward-overlap`` was intended to handle intra-refresh video, but
-    which does not work since libavcodec silently drops frames even with
-    ``--vd-lavc-show-all``, and it's too messy to accurately guess which frames
-    have been dropped.
+    ``--video-backward-overlap`` can potentially handle intra-refresh video,
+    depending on the exact conditions. You may have to use the
+    ``--vd-lavc-show-all`` option as well.
 
 ``--demuxer-backward-playback-step=<seconds>``
     Number of seconds the demuxer should seek back to get new packets during
diff --git a/demux/demux.c b/demux/demux.c
index 5130b8ee25..c9792a3024 100644
--- a/demux/demux.c
+++ b/demux/demux.c
@@ -1329,31 +1329,46 @@ static void find_backward_restart_pos(struct demux_stream *ds)
     // Find where to restart demuxing. It's usually the last keyframe packet
     // before restart_pos, but might be up to back_preroll packets earlier.
 
-    struct demux_packet *last_keyframe = NULL;
-    struct demux_packet *target = NULL;
-
-    // Keep this packet at back_preroll packets before last_keyframe.
-    struct demux_packet *pre_packet = ds->reader_head;
-    int pre_packet_offset = ds->back_preroll;
+    struct demux_packet *last_keyframe = NULL; // keyframe before back_restart
 
     // (Normally, we'd just iterate backwards, but no back links.)
-    for (struct demux_packet *cur = ds->reader_head;
-         cur != back_restart;
-         cur = cur->next)
-    {
-        if (cur->keyframe) {
-            last_keyframe = cur;
-            target = pre_packet;
-        }
-
-        if (pre_packet_offset) {
-            pre_packet_offset--;
-        } else {
-            pre_packet = pre_packet->next;
+    int num_kf = 0;
+    struct demux_packet *pre_1 = NULL; // idiotic "optimization" for preroll=1
+    for (struct demux_packet *dp = first; dp != back_restart; dp = dp->next) {
+        if (dp->keyframe) {
+            num_kf++;
+            pre_1 = last_keyframe; // 1 keyframe before final last_keyframe
+            last_keyframe = dp;
+        }
+    }
+
+    struct demux_packet *target = NULL; // resume pos
+    int got_preroll = 0; // nr. of keyframes, incl. target, excl. last_keyframe
+
+    if (ds->back_preroll == 0) {
+        target = last_keyframe;
+    } else if (ds->back_preroll == 1) {
+        target = pre_1;
+        if (!target && ds->queue->is_bof)
+            target = last_keyframe;
+        got_preroll = target == pre_1 ? 1 : 0;
+    } else if (num_kf > ds->back_preroll || ds->queue->is_bof) {
+        got_preroll = ds->back_preroll;
+        if (num_kf <= ds->back_preroll && ds->queue->is_bof)
+            got_preroll = MPMAX(0, num_kf - 1);
+        int cur_kf = 0;
+        for (struct demux_packet *dp = first; dp != back_restart; dp = dp->next) {
+            if (dp->keyframe) {
+                cur_kf++;
+                if (num_kf - cur_kf == got_preroll) {
+                    target = dp;
+                    break;
+                }
+            }
         }
     }
 
-    if (!last_keyframe) {
+    if (!target) {
         // Note: assume this holds true. You could think of various reasons why
         // this might break.
         if (ds->queue->is_bof) {
@@ -1368,19 +1383,6 @@ static void find_backward_restart_pos(struct demux_stream *ds)
         goto resume_earlier;
     }
 
-    int got_preroll = 0;
-    for (struct demux_packet *cur = target;
-         cur != last_keyframe;
-         cur = cur->next)
-         got_preroll++;
-
-    if (got_preroll < ds->back_preroll && !ds->queue->is_bof)
-        goto resume_earlier;
-
-    // (Round preroll down to 0 in the worst case.)
-    while (!target->keyframe)
-        target = target->next;
-
     // Skip reader_head from previous keyframe to current one.
     // Or if preroll is involved, the first preroll packet.
     while (ds->reader_head != target) {
@@ -2299,7 +2301,7 @@ static int dequeue_packet(struct demux_stream *ds, struct demux_packet **res)
     pkt->next = NULL;
 
     if (ds->in->back_demuxing) {
-        if (ds->back_range_min)
+        if (ds->back_range_min && pkt->keyframe)
             ds->back_range_min -= 1;
         if (ds->back_range_min) {
             pkt->back_preroll = true;