2 * seek utility functions for use within format handlers
4 * Copyright (c) 2009 Ivan Schreter
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26 #include "libavutil/mathematics.h"
27 #include "libavutil/mem.h"
30 // NOTE: implementation should be moved here in another patch, to keep patches
34 * helper structure describing keyframe search state of one stream
37 int64_t pos_lo; ///< position of the frame with low timestamp in file or INT64_MAX if not found (yet)
38 int64_t ts_lo; ///< frame presentation timestamp or same as pos_lo for byte seeking
40 int64_t pos_hi; ///< position of the frame with high timestamp in file or INT64_MAX if not found (yet)
41 int64_t ts_hi; ///< frame presentation timestamp or same as pos_hi for byte seeking
43 int64_t last_pos; ///< last known position of a frame, for multi-frame packets
45 int64_t term_ts; ///< termination timestamp (which TS we already read)
46 AVRational term_ts_tb; ///< timebase for term_ts
47 int64_t first_ts; ///< first packet timestamp in this iteration (to fill term_ts later)
48 AVRational first_ts_tb; ///< timebase for first_ts
50 int terminated; ///< termination flag for the current iteration
54 * Compute a distance between timestamps.
56 * Distances are only comparable, if same time bases are used for computing
59 * @param ts_hi high timestamp
60 * @param tb_hi high timestamp time base
61 * @param ts_lo low timestamp
62 * @param tb_lo low timestamp time base
63 * @return representation of distance between high and low timestamps
65 static int64_t ts_distance(int64_t ts_hi,
72 hi = ts_hi * tb_hi.num * tb_lo.den;
73 lo = ts_lo * tb_lo.num * tb_hi.den;
79 * Partial search for keyframes in multiple streams.
81 * This routine searches in each stream for the next lower and the next higher
82 * timestamp compared to the given target timestamp. The search starts at the current
83 * file position and ends at the file position, where all streams have already been
84 * examined (or when all higher key frames are found in the first iteration).
86 * This routine is called iteratively with an exponential backoff to find the lower
89 * @param s format context
90 * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE)
91 * @param timebase time base for timestamps
92 * @param flags seeking flags
93 * @param sync array with information per stream
94 * @param keyframes_to_find count of keyframes to find in total
95 * @param found_lo ptr to the count of already found low timestamp keyframes
96 * @param found_hi ptr to the count of already found high timestamp keyframes
97 * @param first_iter flag for first iteration
99 static void search_hi_lo_keyframes(AVFormatContext *s,
104 int keyframes_to_find,
114 int terminated_count = 0;
116 int64_t pts, dts; // PTS/DTS from stream
117 int64_t ts; // PTS in stream-local time base or position for byte seeking
118 AVRational ts_tb; // Time base of the stream or 1:1 for byte seeking
121 if (av_read_frame(s, &pkt) < 0) {
122 // EOF or error, make sure high flags are set
123 for (idx = 0; idx < s->nb_streams; ++idx) {
124 if (s->streams[idx]->discard < AVDISCARD_ALL) {
126 if (sp->pos_hi == INT64_MAX) {
127 // no high frame exists for this stream
129 sp->ts_hi = INT64_MAX;
130 sp->pos_hi = INT64_MAX - 1;
137 idx = pkt.stream_index;
138 st = s->streams[idx];
139 if (st->discard >= AVDISCARD_ALL)
140 // this stream is not active, skip packet
149 if (pts == AV_NOPTS_VALUE)
150 // some formats don't provide PTS, only DTS
153 av_free_packet(&pkt);
155 // Multi-frame packets only return position for the very first frame.
156 // Other frames are read with position == -1. Therefore, we note down
157 // last known position of a frame and use it if a frame without
158 // position arrives. In this way, it's possible to seek to proper
159 // position. Additionally, for parsers not providing position at all,
160 // an approximation will be used (starting position of this iteration).
166 // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set).
167 if (pts != AV_NOPTS_VALUE &&
168 ((flg & AV_PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) {
169 if (flags & AVSEEK_FLAG_BYTE) {
170 // for byte seeking, use position as timestamp
175 // otherwise, get stream time_base
177 ts_tb = st->time_base;
180 if (sp->first_ts == AV_NOPTS_VALUE) {
181 // Note down termination timestamp for the next iteration - when
182 // we encounter a packet with the same timestamp, we will ignore
183 // any further packets for this stream in next iteration (as they
184 // are already evaluated).
186 sp->first_ts_tb = ts_tb;
189 if (sp->term_ts != AV_NOPTS_VALUE &&
190 av_compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) {
191 // past the end position from last iteration, ignore packet
192 if (!sp->terminated) {
195 if (sp->pos_hi == INT64_MAX) {
196 // no high frame exists for this stream
198 sp->ts_hi = INT64_MAX;
199 sp->pos_hi = INT64_MAX - 1;
201 if (terminated_count == keyframes_to_find)
202 break; // all terminated, iteration done
207 if (av_compare_ts(ts, ts_tb, timestamp, timebase) <= 0) {
208 // keyframe found before target timestamp
209 if (sp->pos_lo == INT64_MAX) {
210 // found first keyframe lower than target timestamp
214 } else if (sp->ts_lo < ts) {
215 // found a better match (closer to target timestamp)
220 if (av_compare_ts(ts, ts_tb, timestamp, timebase) >= 0) {
221 // keyframe found after target timestamp
222 if (sp->pos_hi == INT64_MAX) {
223 // found first keyframe higher than target timestamp
227 if (*found_hi >= keyframes_to_find && first_iter) {
228 // We found high frame for all. They may get updated
229 // to TS closer to target TS in later iterations (which
230 // will stop at start position of previous iteration).
233 } else if (sp->ts_hi > ts) {
234 // found a better match (actually, shouldn't happen)
242 // Clean up the parser.
243 ff_read_frame_flush(s);
246 int64_t ff_gen_syncpoint_search(AVFormatContext *s,
254 AVSyncPoint *sync, *sp;
257 int keyframes_to_find = 0;
260 int found_lo = 0, found_hi = 0;
261 int64_t min_distance, distance;
264 AVRational time_base;
266 if (flags & AVSEEK_FLAG_BYTE) {
267 // for byte seeking, we have exact 1:1 "timestamps" - positions
271 if (stream_index >= 0) {
272 // we have a reference stream, which time base we use
273 st = s->streams[stream_index];
274 time_base = st->time_base;
276 // no reference stream, use AV_TIME_BASE as reference time base
278 time_base.den = AV_TIME_BASE;
282 // Initialize syncpoint structures for each stream.
283 sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint));
285 // cannot allocate helper structure
288 for (i = 0; i < s->nb_streams; ++i) {
292 sp->pos_lo = INT64_MAX;
293 sp->ts_lo = INT64_MAX;
294 sp->pos_hi = INT64_MAX;
295 sp->ts_hi = INT64_MAX;
297 sp->first_ts = AV_NOPTS_VALUE;
298 sp->term_ts = ts_max;
299 sp->term_ts_tb = time_base;
302 st->cur_dts = AV_NOPTS_VALUE;
304 if (st->discard < AVDISCARD_ALL)
308 if (!keyframes_to_find) {
309 // no stream active, error
314 // Find keyframes in all active streams with timestamp/position just before
315 // and just after requested timestamp/position.
316 step = s->pb->buffer_size;
317 curpos = FFMAX(pos - step / 2, 0);
319 avio_seek(s->pb, curpos, SEEK_SET);
320 search_hi_lo_keyframes(s,
325 &found_lo, &found_hi,
327 if (found_lo == keyframes_to_find && found_hi == keyframes_to_find)
328 break; // have all keyframes we wanted
330 break; // cannot go back anymore
337 // switch termination positions
338 for (i = 0; i < s->nb_streams; ++i) {
340 st->cur_dts = AV_NOPTS_VALUE;
343 if (sp->first_ts != AV_NOPTS_VALUE) {
344 sp->term_ts = sp->first_ts;
345 sp->term_ts_tb = sp->first_ts_tb;
346 sp->first_ts = AV_NOPTS_VALUE;
349 sp->last_pos = curpos;
354 // Find actual position to start decoding so that decoder synchronizes
355 // closest to ts and between ts_min and ts_max.
358 for (i = 0; i < s->nb_streams; ++i) {
360 if (st->discard < AVDISCARD_ALL) {
362 min_distance = INT64_MAX;
363 // Find timestamp closest to requested timestamp within min/max limits.
364 if (sp->pos_lo != INT64_MAX
365 && av_compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0
366 && av_compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) {
367 // low timestamp is in range
368 min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base);
369 min_pos = sp->pos_lo;
371 if (sp->pos_hi != INT64_MAX
372 && av_compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0
373 && av_compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) {
374 // high timestamp is in range, check distance
375 distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base);
376 if (distance < min_distance) {
377 min_distance = distance;
378 min_pos = sp->pos_hi;
381 if (min_distance == INT64_MAX) {
382 // no timestamp is in range, cannot seek
391 avio_seek(s->pb, pos, SEEK_SET);
396 AVParserState *ff_store_parser_state(AVFormatContext *s)
400 AVParserStreamState *ss;
401 AVParserState *state = av_malloc(sizeof(AVParserState));
405 state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams);
406 if (!state->stream_states) {
411 state->fpos = avio_tell(s->pb);
413 // copy context structures
414 state->packet_buffer = s->packet_buffer;
415 state->parse_queue = s->parse_queue;
416 state->raw_packet_buffer = s->raw_packet_buffer;
417 state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size;
419 s->packet_buffer = NULL;
420 s->parse_queue = NULL;
421 s->raw_packet_buffer = NULL;
422 s->raw_packet_buffer_remaining_size = RAW_PACKET_BUFFER_SIZE;
424 // copy stream structures
425 state->nb_streams = s->nb_streams;
426 for (i = 0; i < s->nb_streams; i++) {
428 ss = &state->stream_states[i];
430 ss->parser = st->parser;
431 ss->last_IP_pts = st->last_IP_pts;
432 ss->cur_dts = st->cur_dts;
433 ss->probe_packets = st->probe_packets;
436 st->last_IP_pts = AV_NOPTS_VALUE;
437 st->cur_dts = AV_NOPTS_VALUE;
438 st->probe_packets = MAX_PROBE_PACKETS;
444 void ff_restore_parser_state(AVFormatContext *s, AVParserState *state)
448 AVParserStreamState *ss;
449 ff_read_frame_flush(s);
454 avio_seek(s->pb, state->fpos, SEEK_SET);
456 // copy context structures
457 s->packet_buffer = state->packet_buffer;
458 s->parse_queue = state->parse_queue;
459 s->raw_packet_buffer = state->raw_packet_buffer;
460 s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size;
462 // copy stream structures
463 for (i = 0; i < state->nb_streams; i++) {
465 ss = &state->stream_states[i];
467 st->parser = ss->parser;
468 st->last_IP_pts = ss->last_IP_pts;
469 st->cur_dts = ss->cur_dts;
470 st->probe_packets = ss->probe_packets;
473 av_free(state->stream_states);
477 static void free_packet_list(AVPacketList *pktl)
483 av_free_packet(&cur->pkt);
488 void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
491 AVParserStreamState *ss;
496 for (i = 0; i < state->nb_streams; i++) {
497 ss = &state->stream_states[i];
499 av_parser_close(ss->parser);
502 free_packet_list(state->packet_buffer);
503 free_packet_list(state->parse_queue);
504 free_packet_list(state->raw_packet_buffer);
506 av_free(state->stream_states);