PR #25556 opened by Alexkane URL: https://code.ffmpeg.org/FFmpeg/FFmpeg/pulls/25556 Patch URL: https://code.ffmpeg.org/FFmpeg/FFmpeg/pulls/25556.patch
ff_gen_search() narrows a byte range around the target timestamp on the assumption that timestamps increase with the position in the file. MPEG-TS recordings break that assumption whenever the clock is reset: a regional splice, a PCR reset, two captures written back to back. In the sample of issue 25009 the timestamps run 0-40 s, jump to 41371-41411 s, and return to 80-120 s. Seeking to 100 s first finds the right packets, then a bisection probe lands in the middle segment and reads a timestamp far above the one at the end of the file. The search treated that as "the target is earlier", moved the upper bound onto the probe, discarded the final segment and converged on the first jump, so every seek beyond 80 s returned the frame at 40 s. A probe whose timestamp exceeds ts_max is impossible in a monotonic stream and proves a discontinuity between the probe and pos_max. The target, which is below ts_max, can only be met again after that jump, so the search now drops the range before the probe instead of the range after it; ts_min is kept only as a placeholder and the next step bisects, since interpolating from a timestamp that was read on the other side of the jump is meaningless. If that pass does not end between two read timestamps that enclose the target, the target either precedes the jump or falls in a gap of the timeline, and the search is redone the historical way from the bracket as it stood at the jump. That recovers the old answer in both cases, so a file without discontinuities is searched with exactly the probes it was before. On the sample, seeks to 20, 38, 42, 82, 100 and 115 s now return the frames at those positions (42 s used to be one frame late); 60 and 78 s, which fall between the two timelines, still return the frame at 40 s as before. The new fate-seek-ts-discont test builds a 540 KB stream from three clock-shifted MPEG-TS segments with the tools FATE already uses, so it needs no sample; two of its seeks land after the jump with this change and on the jump without it. Reported by bernhardberger with the generator for the sample. Fixes #25009 >From f01b962fd7ce69414201f10e87c34f70f050f6b4 Mon Sep 17 00:00:00 2001 From: Alexkane <[email protected]> Date: Wed, 28 Oct 2026 00:07:06 -0400 Subject: [PATCH] avformat/seek: look past a timestamp discontinuity for the seek target ff_gen_search() narrows a byte range around the target timestamp on the assumption that timestamps increase with the position in the file. MPEG-TS recordings break that assumption whenever the clock is reset: a regional splice, a PCR reset, two captures written back to back. In the sample of issue 25009 the timestamps run 0-40 s, jump to 41371-41411 s, and return to 80-120 s. Seeking to 100 s first finds the right packets, then a bisection probe lands in the middle segment and reads a timestamp far above the one at the end of the file. The search treated that as "the target is earlier", moved the upper bound onto the probe, discarded the final segment and converged on the first jump, so every seek beyond 80 s returned the frame at 40 s. A probe whose timestamp exceeds ts_max is impossible in a monotonic stream and proves a discontinuity between the probe and pos_max. The target, which is below ts_max, can only be met again after that jump, so the search now drops the range before the probe instead of the range after it; ts_min is kept only as a placeholder and the next step bisects, since interpolating from a timestamp that was read on the other side of the jump is meaningless. If that pass does not end between two read timestamps that enclose the target, the target either precedes the jump or falls in a gap of the timeline, and the search is redone the historical way from the bracket as it stood at the jump. That recovers the old answer in both cases, so a file without discontinuities is searched with exactly the probes it was before. On the sample, seeks to 20, 38, 42, 82, 100 and 115 s now return the frames at those positions (42 s used to be one frame late); 60 and 78 s, which fall between the two timelines, still return the frame at 40 s as before. The new fate-seek-ts-discont test builds a 540 KB stream from three clock-shifted MPEG-TS segments with the tools FATE already uses, so it needs no sample; two of its seeks land after the jump with this change and on the jump without it. Reported by bernhardberger with the generator for the sample. Fixes #25009 --- libavformat/seek.c | 212 ++++++++++++++++++++++++++++---------- tests/fate/seek.mak | 23 +++++ tests/ref/seek/ts-discont | 53 ++++++++++ 3 files changed, 236 insertions(+), 52 deletions(-) create mode 100644 tests/ref/seek/ts-discont diff --git a/libavformat/seek.c b/libavformat/seek.c index 4a09d013353..31df3ec2e0d 100644 --- a/libavformat/seek.c +++ b/libavformat/seek.c @@ -395,6 +395,140 @@ int ff_find_last_ts(AVFormatContext *s, int stream_index, int64_t *ts, int64_t * return 0; } +/** + * State of a binary search for target_ts: pos_min and pos_max enclose the + * target, ts_min < target_ts <= ts_max are the timestamps read there, and + * pos_limit is the highest position still worth probing below pos_max. + * + * ts_min_valid / ts_max_valid record whether the timestamp was really read at + * that position. A bound that was moved onto a probe lying across a timestamp + * discontinuity keeps the previous timestamp, which from then on is only a + * placeholder that preserves the loop invariant ts_min < ts_max; the + * interpolation step must not rely on it and the result must not be + * reported as a timestamp the stream contains. + */ +typedef struct SearchBracket { + int64_t pos_min, pos_max, pos_limit; + int64_t ts_min, ts_max; + int ts_min_valid, ts_max_valid; +} SearchBracket; + +/** + * Narrow a bracket until pos_min and pos_max are neighbouring packets. + * + * The search assumes timestamps increase with the position in the file. A + * probe that reads a timestamp above ts_max proves that they do not: the + * stream jumps back somewhere between the probe and pos_max, as MPEG-TS does + * when the clock is reset at a splice (broadcast recordings, concatenated + * captures, ticket 25009). Such a probe cannot be ordered against the target, + * so the caller chooses which half of the bracket to keep: + * + * - keep_right: drop [pos_min, probe). The target, which is below ts_max, can + * only be reached again after the jump. ts_min is kept as a placeholder. + * - otherwise: drop (probe, pos_max], the historical behaviour. If the target + * lies beyond the jump this converges on the jump itself, where timestamps + * skip over the target, rather than on the packets that carry it. + * + * When jump is non-NULL and such a probe is seen, *jump receives the bracket + * as it stood after that probe under the second policy, so the caller can + * resume from exactly the point where the two policies part. + * + * @return 0 if no discontinuity was crossed, 1 if one was, <0 on a read error + */ +static int gen_search_bracket(AVFormatContext *s, int stream_index, + int64_t target_ts, SearchBracket *b, + int keep_right, SearchBracket *jump, + int64_t (*read_ts)(struct AVFormatContext *, int, + int64_t *, int64_t)) +{ + int64_t pos, ts; + int64_t start_pos; + int no_change = 0; + int jumped = 0; + + while (b->pos_min < b->pos_limit) { + av_log(s, AV_LOG_TRACE, "pos_min=0x%"PRIx64" pos_max=0x%"PRIx64 + " dts_min=%s dts_max=%s\n", b->pos_min, b->pos_max, + av_ts2str(b->ts_min), av_ts2str(b->ts_max)); + av_assert0(b->pos_limit <= b->pos_max); + + if (no_change == 0) { + int64_t approximate_keyframe_distance = b->pos_max - b->pos_limit; + // interpolate position (better than dichotomy) + pos = av_rescale(target_ts - b->ts_min, b->pos_max - b->pos_min, + b->ts_max - b->ts_min) + + b->pos_min - approximate_keyframe_distance; + } else if (no_change == 1) { + // bisection if interpolation did not change min / max pos last time + pos = (b->pos_min + b->pos_limit) >> 1; + } else { + /* linear search if bisection failed, can only happen if there + * are very few or no keyframes between min/max */ + pos = b->pos_min; + } + if (pos <= b->pos_min) + pos = b->pos_min + 1; + else if (pos > b->pos_limit) + pos = b->pos_limit; + start_pos = pos; + + // May pass pos_limit instead of -1. + ts = read_timestamp(s, stream_index, &pos, INT64_MAX, read_ts); + if (pos == b->pos_max) + no_change++; + else + no_change = 0; + av_log(s, AV_LOG_TRACE, "%"PRId64" %"PRId64" %"PRId64" / %s %s %s" + " target:%s limit:%"PRId64" start:%"PRId64" noc:%d\n", + b->pos_min, pos, b->pos_max, av_ts2str(b->ts_min), + av_ts2str(ts), av_ts2str(b->ts_max), av_ts2str(target_ts), + b->pos_limit, start_pos, no_change); + if (ts == AV_NOPTS_VALUE) { + av_log(s, AV_LOG_ERROR, "read_timestamp() failed in the middle\n"); + return -1; + } + if (ts > b->ts_max) { + av_log(s, AV_LOG_TRACE, "dts %s at 0x%"PRIx64" is above dts_max: " + "timestamp discontinuity before 0x%"PRIx64"\n", + av_ts2str(ts), pos, b->pos_max); + if (jump && !jumped) { + *jump = *b; + jump->pos_limit = start_pos - 1; + jump->pos_max = pos; + jump->ts_max = ts; + jump->ts_max_valid = 0; + } + jumped = 1; + if (keep_right) { + b->pos_min = pos; + b->ts_min_valid = 0; + /* ts_min is now a placeholder, so the interpolation step has + * nothing real to work from: bisect the remaining range. */ + no_change = 1; + } else { + b->pos_limit = start_pos - 1; + b->pos_max = pos; + b->ts_max = ts; + b->ts_max_valid = 0; + } + continue; + } + if (target_ts <= ts) { + b->pos_limit = start_pos - 1; + b->pos_max = pos; + b->ts_max = ts; + b->ts_max_valid = 1; + } + if (target_ts >= ts) { + b->pos_min = pos; + b->ts_min = ts; + b->ts_min_valid = 1; + } + } + + return jumped; +} + int64_t ff_gen_search(AVFormatContext *s, int stream_index, int64_t target_ts, int64_t pos_min, int64_t pos_max, int64_t pos_limit, int64_t ts_min, int64_t ts_max, @@ -403,9 +537,8 @@ int64_t ff_gen_search(AVFormatContext *s, int stream_index, int64_t target_ts, int, int64_t *, int64_t)) { FFFormatContext *const si = ffformatcontext(s); + SearchBracket b, jump = { 0 }; int64_t pos, ts; - int64_t start_pos; - int no_change; int ret; av_log(s, AV_LOG_TRACE, "gen_seek: %d %s\n", stream_index, av_ts2str(target_ts)); @@ -435,61 +568,36 @@ int64_t ff_gen_search(AVFormatContext *s, int stream_index, int64_t target_ts, av_assert0(ts_min < ts_max); - no_change = 0; - while (pos_min < pos_limit) { - av_log(s, AV_LOG_TRACE, - "pos_min=0x%"PRIx64" pos_max=0x%"PRIx64" dts_min=%s dts_max=%s\n", - pos_min, pos_max, av_ts2str(ts_min), av_ts2str(ts_max)); - av_assert0(pos_limit <= pos_max); + b = (SearchBracket){ pos_min, pos_max, pos_limit, ts_min, ts_max, 1, 1 }; - if (no_change == 0) { - int64_t approximate_keyframe_distance = pos_max - pos_limit; - // interpolate position (better than dichotomy) - pos = av_rescale(target_ts - ts_min, pos_max - pos_min, - ts_max - ts_min) + - pos_min - approximate_keyframe_distance; - } else if (no_change == 1) { - // bisection if interpolation did not change min / max pos last time - pos = (pos_min + pos_limit) >> 1; - } else { - /* linear search if bisection failed, can only happen if there - * are very few or no keyframes between min/max */ - pos = pos_min; - } - if (pos <= pos_min) - pos = pos_min + 1; - else if (pos > pos_limit) - pos = pos_limit; - start_pos = pos; + /* First try the half after a discontinuity, since a target beyond the + * jump is the common case (seeking into a recording after its clock was + * reset): on a monotonic stream this runs exactly the historical search. */ + ret = gen_search_bracket(s, stream_index, target_ts, &b, 1, &jump, + read_timestamp_func); + if (ret < 0) + return -1; - // May pass pos_limit instead of -1. - ts = read_timestamp(s, stream_index, &pos, INT64_MAX, read_timestamp_func); - if (pos == pos_max) - no_change++; - else - no_change = 0; - av_log(s, AV_LOG_TRACE, "%"PRId64" %"PRId64" %"PRId64" / %s %s %s" - " target:%s limit:%"PRId64" start:%"PRId64" noc:%d\n", - pos_min, pos, pos_max, - av_ts2str(ts_min), av_ts2str(ts), av_ts2str(ts_max), av_ts2str(target_ts), - pos_limit, start_pos, no_change); - if (ts == AV_NOPTS_VALUE) { - av_log(s, AV_LOG_ERROR, "read_timestamp() failed in the middle\n"); + if (ret > 0 && !(b.ts_min_valid && b.ts_max_valid)) { + /* A discontinuity was crossed and the search did not end between two + * read timestamps enclosing the target, so the part after the jump + * does not contain it: either it precedes the jump, or no packet has + * it at all (the target falls in a gap of the timeline). Redo the + * search the historical way from the bracket as it stood at the + * jump. That finds the target when it precedes the jump, and + * otherwise returns what every earlier version returned, the position + * of the jump itself. */ + av_log(s, AV_LOG_TRACE, "no timestamps enclosing the target after the " + "discontinuity, searching before it\n"); + ret = gen_search_bracket(s, stream_index, target_ts, &jump, 0, NULL, + read_timestamp_func); + if (ret < 0) return -1; - } - if (target_ts <= ts) { - pos_limit = start_pos - 1; - pos_max = pos; - ts_max = ts; - } - if (target_ts >= ts) { - pos_min = pos; - ts_min = ts; - } + b = jump; } - pos = (flags & AVSEEK_FLAG_BACKWARD) ? pos_min : pos_max; - ts = (flags & AVSEEK_FLAG_BACKWARD) ? ts_min : ts_max; + pos = (flags & AVSEEK_FLAG_BACKWARD) ? b.pos_min : b.pos_max; + ts = (flags & AVSEEK_FLAG_BACKWARD) ? b.ts_min : b.ts_max; #if 0 pos_min = pos; ts_min = read_timestamp(s, stream_index, &pos_min, INT64_MAX, read_timestamp_func); diff --git a/tests/fate/seek.mak b/tests/fate/seek.mak index d33cef4d928..d0c761e3047 100644 --- a/tests/fate/seek.mak +++ b/tests/fate/seek.mak @@ -212,6 +212,29 @@ tests/data/hls-seek.m3u8: ffmpeg$(PROGSSUF)$(EXESUF) | tests/data FATE_SEEK_EXTRA += $(FATE_SEEK_EXTRA-yes) +# Three MPEG-TS segments of one programme written back to back with a clock +# jump between them: 0-2 s, then 40000-40002 s, then 4-6 s of the original +# timeline. This is what a broadcast recording looks like after a PCR reset +# or a regional splice, and what made the timestamp search discard the final +# segment (ticket 25009): a probe landing in the middle segment reads a +# timestamp above the one at the end of the file. +SEEK_TS_DISCONT_ENC = -map 0:v -map 1:a -c:v mpeg2video -threads:v 1 -bf 2 -g 15 \ + -dct int -idct int -flags +bitexact -c:a mp2fixed -f mpegts +tests/data/seek-ts-discont.ts: ffmpeg$(PROGSSUF)$(EXESUF) | tests/data + $(M)$(TARGET_EXEC) $(TARGET_PATH)/$< -nostdin -y \ + -f lavfi -i "testsrc2=size=128x72:rate=10:d=6" \ + -f lavfi -i "aevalsrc=cos(2*PI*t)*sin(2*PI*(440+4*t)*t):d=6" \ + -t 2 $(SEEK_TS_DISCONT_ENC) $(TARGET_PATH)/tests/data/seek-ts-discont-0.ts \ + -ss 2 -t 2 -output_ts_offset 40000 $(SEEK_TS_DISCONT_ENC) $(TARGET_PATH)/tests/data/seek-ts-discont-1.ts \ + -ss 4 -t 2 -output_ts_offset 4 $(SEEK_TS_DISCONT_ENC) $(TARGET_PATH)/tests/data/seek-ts-discont-2.ts 2>/dev/null + $(Q)cat tests/data/seek-ts-discont-0.ts tests/data/seek-ts-discont-1.ts tests/data/seek-ts-discont-2.ts > $@ + +# -duration 9 makes the pseudo-random targets reach the final segment (5.3-7.2 s +# with the muxer's delay), which is where seeking used to land on the jump. +FATE_SEEK_FFMPEG-$(call ALLYES, TESTSRC2_FILTER AEVALSRC_FILTER ARESAMPLE_FILTER LAVFI_INDEV MPEG2VIDEO_ENCODER MP2FIXED_ENCODER MPEGTS_MUXER MPEGTS_DEMUXER FILE_PROTOCOL) += fate-seek-ts-discont +fate-seek-ts-discont: tests/data/seek-ts-discont.ts +fate-seek-ts-discont: CMD = run libavformat/tests/seek$(EXESUF) $(TARGET_PATH)/tests/data/seek-ts-discont.ts -duration 9 + FATE_SEEK_FFMPEG-$(call ALLYES, TESTSRC2_FILTER AEVALSRC_FILTER ARESAMPLE_FILTER LAVFI_INDEV MPEG2VIDEO_ENCODER MP2FIXED_ENCODER HLS_MUXER MPEGTS_MUXER HLS_DEMUXER MPEGTS_DEMUXER FILE_PROTOCOL) += fate-seek-hls fate-seek-hls: tests/data/hls-seek.m3u8 fate-seek-hls: CMD = run libavformat/tests/seek$(EXESUF) $(TARGET_PATH)/tests/data/hls-seek.m3u8 -duration 6 diff --git a/tests/ref/seek/ts-discont b/tests/ref/seek/ts-discont new file mode 100644 index 00000000000..97b0ff028a2 --- /dev/null +++ b/tests/ref/seek/ts-discont @@ -0,0 +1,53 @@ +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st:-1 flags:0 ts:-1.000000 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st:-1 flags:1 ts: 2.894167 +ret: 0 st: 1 flags:1 dts: 2.795211 pts: 2.795211 pos: 122576 size: 1254 +ret: 0 st: 0 flags:0 ts: 6.788333 +ret: 0 st: 1 flags:1 dts: 6.799700 pts: 6.799700 pos: 495380 size: 1254 +ret: 0 st: 0 flags:1 ts: 1.682500 +ret: 0 st: 1 flags:1 dts: 1.593578 pts: 1.593578 pos: 17296 size: 1254 +ret: 0 st: 1 flags:0 ts: 5.576667 +ret: 0 st: 1 flags:1 dts: 5.598078 pts: 5.598078 pos: 382956 size: 1253 +ret: 0 st: 1 flags:1 ts: 0.470833 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st:-1 flags:0 ts: 4.365002 +ret: 0 st: 1 flags:1 dts: 40001.389089 pts: 40001.389089 pos: 188564 size: 1253 +ret: 0 st:-1 flags:1 ts:-0.740831 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st: 0 flags:0 ts: 3.153333 +ret: 0 st: 1 flags:1 dts: 3.160933 pts: 3.160933 pos: 155664 size: 1254 +ret: 0 st: 0 flags:1 ts: 7.047500 +ret: 0 st: 1 flags:1 dts: 6.956444 pts: 6.956444 pos: 512112 size: 1254 +ret: 0 st: 1 flags:0 ts: 1.941667 +ret: 0 st: 1 flags:1 dts: 1.959300 pts: 1.959300 pos: 47752 size: 1254 +ret: 0 st: 1 flags:1 ts: 5.835833 +ret: 0 st: 1 flags:1 dts: 5.807056 pts: 5.807056 pos: 402132 size: 1253 +ret: 0 st:-1 flags:0 ts: 0.730004 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st:-1 flags:1 ts: 4.624171 +ret: 0 st: 1 flags:1 dts: 3.265422 pts: 3.265422 pos: 165252 size: 1254 +ret: 0 st: 0 flags:0 ts:-0.481667 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st: 0 flags:1 ts: 3.412500 +ret: 0 st: 1 flags:1 dts: 3.265422 pts: 3.265422 pos: 165252 size: 1254 +ret: 0 st: 1 flags:0 ts: 7.306667 +ret: 0 st: 1 flags:1 dts: 7.322156 pts: 7.322156 pos: 538620 size: 1254 +ret: 0 st: 1 flags:1 ts: 2.200844 +ret: 0 st: 1 flags:1 dts: 2.168278 pts: 2.168278 pos: 66552 size: 1254 +ret: 0 st:-1 flags:0 ts: 6.095006 +ret: 0 st: 1 flags:1 dts: 6.068278 pts: 6.068278 pos: 427888 size: 1254 +ret: 0 st:-1 flags:1 ts: 0.989173 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st: 0 flags:0 ts: 4.883344 +ret: 0 st: 1 flags:1 dts: 40001.389089 pts: 40001.389089 pos: 188564 size: 1253 +ret: 0 st: 0 flags:1 ts:-0.222489 +ret: 0 st: 1 flags:1 dts: 1.489089 pts: 1.489089 pos: 9212 size: 1253 +ret: 0 st: 1 flags:0 ts: 3.671678 +ret: 0 st: 1 flags:1 dts: 40001.389089 pts: 40001.389089 pos: 188564 size: 1253 +ret: 0 st: 1 flags:1 ts: 7.565844 +ret: 0 st: 1 flags:1 dts: 7.374400 pts: 7.374400 pos: 541252 size: 1254 +ret: 0 st:-1 flags:0 ts: 2.460008 +ret: 0 st: 1 flags:1 dts: 2.481744 pts: 2.481744 pos: 94940 size: 1254 +ret: 0 st:-1 flags:1 ts: 6.354175 +ret: 0 st: 1 flags:1 dts: 6.277256 pts: 6.277256 pos: 448756 size: 1254 -- 2.54.0 _______________________________________________ ffmpeg-devel mailing list -- [email protected] To unsubscribe send an email to [email protected]
