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
24 #include "libavutil/mem.h"
26 // NOTE: implementation should be moved here in another patch, to keep patches
28 extern void av_read_frame_flush(AVFormatContext *s);
31 * helper structure describing keyframe search state of one stream
34 int64_t pos_lo; ///< position of the frame with low timestamp in file or INT64_MAX if not found (yet)
35 int64_t ts_lo; ///< frame presentation timestamp or same as pos_lo for byte seeking
37 int64_t pos_hi; ///< position of the frame with high timestamp in file or INT64_MAX if not found (yet)
38 int64_t ts_hi; ///< frame presentation timestamp or same as pos_hi for byte seeking
40 int64_t last_pos; ///< last known position of a frame, for multi-frame packets
42 int64_t term_ts; ///< termination timestamp (which TS we already read)
43 AVRational term_ts_tb; ///< timebase for term_ts
44 int64_t first_ts; ///< first packet timestamp in this iteration (to fill term_ts later)
45 AVRational first_ts_tb; ///< timebase for first_ts
47 int terminated; ///< termination flag for the current iteration
51 * Compare two timestamps exactly, taking their respective time bases into account.
53 * @param ts_a timestamp A
54 * @param tb_a time base for timestamp A
55 * @param ts_b timestamp B
56 * @param tb_b time base for timestamp A
57 * @return -1, 0 or 1 if timestamp A is less than, equal or greater than timestamp B
59 static int compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b)
63 if (ts_a == INT64_MIN)
64 return ts_a < ts_b ? -1 : 0;
65 if (ts_a == INT64_MAX)
66 return ts_a > ts_b ? 1 : 0;
67 if (ts_b == INT64_MIN)
68 return ts_a > ts_b ? 1 : 0;
69 if (ts_b == INT64_MAX)
70 return ts_a < ts_b ? -1 : 0;
72 a = ts_a * tb_a.num * tb_b.den;
73 b = ts_b * tb_b.num * tb_a.den;
79 return (res >> 63) | 1;
83 * Compute a distance between timestamps.
85 * Distances are only comparable, if same time bases are used for computing
88 * @param ts_hi high timestamp
89 * @param tb_hi high timestamp time base
90 * @param ts_lo low timestamp
91 * @param tb_lo low timestamp time base
92 * @return representation of distance between high and low timestamps
94 static int64_t ts_distance(int64_t ts_hi,
101 hi = ts_hi * tb_hi.num * tb_lo.den;
102 lo = ts_lo * tb_lo.num * tb_hi.den;
108 * Partial search for keyframes in multiple streams.
110 * This routine searches in each stream for the next lower and the next higher
111 * timestamp compared to the given target timestamp. The search starts at the current
112 * file position and ends at the file position, where all streams have already been
113 * examined (or when all higher key frames are found in the first iteration).
115 * This routine is called iteratively with an exponential backoff to find the lower
118 * @param s format context
119 * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE)
120 * @param timebase time base for timestamps
121 * @param flags seeking flags
122 * @param sync array with information per stream
123 * @param keyframes_to_find count of keyframes to find in total
124 * @param found_lo ptr to the count of already found low timestamp keyframes
125 * @param found_hi ptr to the count of already found high timestamp keyframes
126 * @param first_iter flag for first iteration
128 static void search_hi_lo_keyframes(AVFormatContext *s,
133 int keyframes_to_find,
143 int terminated_count = 0;
145 int64_t pts, dts; // PTS/DTS from stream
146 int64_t ts; // PTS in stream-local time base or position for byte seeking
147 AVRational ts_tb; // Time base of the stream or 1:1 for byte seeking
150 if (av_read_frame(s, &pkt) < 0) {
151 // EOF or error, make sure high flags are set
152 for (idx = 0; idx < s->nb_streams; ++idx) {
153 if (s->streams[idx]->discard < AVDISCARD_ALL) {
155 if (sp->pos_hi == INT64_MAX) {
156 // no high frame exists for this stream
158 sp->ts_hi = INT64_MAX;
159 sp->pos_hi = INT64_MAX - 1;
166 idx = pkt.stream_index;
167 st = s->streams[idx];
168 if (st->discard >= AVDISCARD_ALL)
169 // this stream is not active, skip packet
178 if (pts == AV_NOPTS_VALUE)
179 // some formats don't provide PTS, only DTS
182 av_free_packet(&pkt);
184 // Multi-frame packets only return position for the very first frame.
185 // Other frames are read with position == -1. Therefore, we note down
186 // last known position of a frame and use it if a frame without
187 // position arrives. In this way, it's possible to seek to proper
188 // position. Additionally, for parsers not providing position at all,
189 // an approximation will be used (starting position of this iteration).
195 // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set).
196 if (pts != AV_NOPTS_VALUE &&
197 ((flg & PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) {
198 if (flags & AVSEEK_FLAG_BYTE) {
199 // for byte seeking, use position as timestamp
204 // otherwise, get stream time_base
206 ts_tb = st->time_base;
209 if (sp->first_ts == AV_NOPTS_VALUE) {
210 // Note down termination timestamp for the next iteration - when
211 // we encounter a packet with the same timestamp, we will ignore
212 // any further packets for this stream in next iteration (as they
213 // are already evaluated).
215 sp->first_ts_tb = ts_tb;
218 if (sp->term_ts != AV_NOPTS_VALUE &&
219 compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) {
220 // past the end position from last iteration, ignore packet
221 if (!sp->terminated) {
224 if (sp->pos_hi == INT64_MAX) {
225 // no high frame exists for this stream
227 sp->ts_hi = INT64_MAX;
228 sp->pos_hi = INT64_MAX - 1;
230 if (terminated_count == keyframes_to_find)
231 break; // all terminated, iteration done
236 if (compare_ts(ts, ts_tb, timestamp, timebase) <= 0) {
237 // keyframe found before target timestamp
238 if (sp->pos_lo == INT64_MAX) {
239 // found first keyframe lower than target timestamp
243 } else if (sp->ts_lo < ts) {
244 // found a better match (closer to target timestamp)
249 if (compare_ts(ts, ts_tb, timestamp, timebase) >= 0) {
250 // keyframe found after target timestamp
251 if (sp->pos_hi == INT64_MAX) {
252 // found first keyframe higher than target timestamp
256 if (*found_hi >= keyframes_to_find && first_iter) {
257 // We found high frame for all. They may get updated
258 // to TS closer to target TS in later iterations (which
259 // will stop at start position of previous iteration).
262 } else if (sp->ts_hi > ts) {
263 // found a better match (actually, shouldn't happen)
271 // Clean up the parser.
272 av_read_frame_flush(s);
275 int64_t ff_gen_syncpoint_search(AVFormatContext *s,
283 AVSyncPoint *sync, *sp;
286 int keyframes_to_find = 0;
289 int found_lo = 0, found_hi = 0;
290 int64_t min_distance, distance;
293 AVRational time_base;
295 if (flags & AVSEEK_FLAG_BYTE) {
296 // for byte seeking, we have exact 1:1 "timestamps" - positions
300 if (stream_index >= 0) {
301 // we have a reference stream, which time base we use
302 st = s->streams[stream_index];
303 time_base = st->time_base;
305 // no reference stream, use AV_TIME_BASE as reference time base
307 time_base.den = AV_TIME_BASE;
311 // Initialize syncpoint structures for each stream.
312 sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint));
314 // cannot allocate helper structure
317 for (i = 0; i < s->nb_streams; ++i) {
321 sp->pos_lo = INT64_MAX;
322 sp->ts_lo = INT64_MAX;
323 sp->pos_hi = INT64_MAX;
324 sp->ts_hi = INT64_MAX;
326 sp->first_ts = AV_NOPTS_VALUE;
327 sp->term_ts = ts_max;
328 sp->term_ts_tb = time_base;
331 st->cur_dts = AV_NOPTS_VALUE;
333 if (st->discard < AVDISCARD_ALL)
337 if (!keyframes_to_find) {
338 // no stream active, error
343 // Find keyframes in all active streams with timestamp/position just before
344 // and just after requested timestamp/position.
345 step = s->pb->buffer_size;
346 curpos = FFMAX(pos - step / 2, 0);
348 url_fseek(s->pb, curpos, SEEK_SET);
349 search_hi_lo_keyframes(s,
354 &found_lo, &found_hi,
356 if (found_lo == keyframes_to_find && found_hi == keyframes_to_find)
357 break; // have all keyframes we wanted
359 break; // cannot go back anymore
366 // switch termination positions
367 for (i = 0; i < s->nb_streams; ++i) {
369 st->cur_dts = AV_NOPTS_VALUE;
372 if (sp->first_ts != AV_NOPTS_VALUE) {
373 sp->term_ts = sp->first_ts;
374 sp->term_ts_tb = sp->first_ts_tb;
375 sp->first_ts = AV_NOPTS_VALUE;
378 sp->last_pos = curpos;
383 // Find actual position to start decoding so that decoder synchronizes
384 // closest to ts and between ts_min and ts_max.
387 for (i = 0; i < s->nb_streams; ++i) {
389 if (st->discard < AVDISCARD_ALL) {
391 min_distance = INT64_MAX;
392 // Find timestamp closest to requested timestamp within min/max limits.
393 if (sp->pos_lo != INT64_MAX
394 && compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0
395 && compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) {
396 // low timestamp is in range
397 min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base);
398 min_pos = sp->pos_lo;
400 if (sp->pos_hi != INT64_MAX
401 && compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0
402 && compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) {
403 // high timestamp is in range, check distance
404 distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base);
405 if (distance < min_distance) {
406 min_distance = distance;
407 min_pos = sp->pos_hi;
410 if (min_distance == INT64_MAX) {
411 // no timestamp is in range, cannot seek
420 url_fseek(s->pb, pos, SEEK_SET);
425 AVParserState *ff_store_parser_state(AVFormatContext *s)
429 AVParserStreamState *ss;
430 AVParserState *state = av_malloc(sizeof(AVParserState));
434 state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams);
435 if (!state->stream_states) {
440 state->fpos = url_ftell(s->pb);
442 // copy context structures
443 state->cur_st = s->cur_st;
444 state->packet_buffer = s->packet_buffer;
445 state->raw_packet_buffer = s->raw_packet_buffer;
446 state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size;
449 s->packet_buffer = NULL;
450 s->raw_packet_buffer = NULL;
451 s->raw_packet_buffer_remaining_size = RAW_PACKET_BUFFER_SIZE;
453 // copy stream structures
454 state->nb_streams = s->nb_streams;
455 for (i = 0; i < s->nb_streams; i++) {
457 ss = &state->stream_states[i];
459 ss->parser = st->parser;
460 ss->last_IP_pts = st->last_IP_pts;
461 ss->cur_dts = st->cur_dts;
462 ss->reference_dts = st->reference_dts;
463 ss->cur_ptr = st->cur_ptr;
464 ss->cur_len = st->cur_len;
465 ss->probe_packets = st->probe_packets;
466 ss->cur_pkt = st->cur_pkt;
469 st->last_IP_pts = AV_NOPTS_VALUE;
470 st->cur_dts = AV_NOPTS_VALUE;
471 st->reference_dts = AV_NOPTS_VALUE;
474 st->probe_packets = MAX_PROBE_PACKETS;
475 av_init_packet(&st->cur_pkt);
481 void ff_restore_parser_state(AVFormatContext *s, AVParserState *state)
485 AVParserStreamState *ss;
486 av_read_frame_flush(s);
491 url_fseek(s->pb, state->fpos, SEEK_SET);
493 // copy context structures
494 s->cur_st = state->cur_st;
495 s->packet_buffer = state->packet_buffer;
496 s->raw_packet_buffer = state->raw_packet_buffer;
497 s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size;
499 // copy stream structures
500 for (i = 0; i < state->nb_streams; i++) {
502 ss = &state->stream_states[i];
504 st->parser = ss->parser;
505 st->last_IP_pts = ss->last_IP_pts;
506 st->cur_dts = ss->cur_dts;
507 st->reference_dts = ss->reference_dts;
508 st->cur_ptr = ss->cur_ptr;
509 st->cur_len = ss->cur_len;
510 st->probe_packets = ss->probe_packets;
511 st->cur_pkt = ss->cur_pkt;
514 av_free(state->stream_states);
518 static void free_packet_list(AVPacketList *pktl)
524 av_free_packet(&cur->pkt);
529 void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
532 AVParserStreamState *ss;
537 for (i = 0; i < state->nb_streams; i++) {
538 ss = &state->stream_states[i];
540 av_parser_close(ss->parser);
541 av_free_packet(&ss->cur_pkt);
544 free_packet_list(state->packet_buffer);
545 free_packet_list(state->raw_packet_buffer);
547 av_free(state->stream_states);