1/* 2 * seek utility functions for use within format handlers 3 * 4 * Copyright (c) 2009 Ivan Schreter 5 * 6 * This file is part of FFmpeg. 7 * 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. 12 * 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. 17 * 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 21 */ 22 23#include "seek.h" 24#include "libavutil/mem.h" 25#include "internal.h" 26 27// NOTE: implementation should be moved here in another patch, to keep patches 28// separated. 29 30/** 31 * helper structure describing keyframe search state of one stream 32 */ 33typedef struct { 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 36 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 39 40 int64_t last_pos; ///< last known position of a frame, for multi-frame packets 41 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 46 47 int terminated; ///< termination flag for the current iteration 48} AVSyncPoint; 49 50/** 51 * Compute a distance between timestamps. 52 * 53 * Distances are only comparable, if same time bases are used for computing 54 * distances. 55 * 56 * @param ts_hi high timestamp 57 * @param tb_hi high timestamp time base 58 * @param ts_lo low timestamp 59 * @param tb_lo low timestamp time base 60 * @return representation of distance between high and low timestamps 61 */ 62static int64_t ts_distance(int64_t ts_hi, 63 AVRational tb_hi, 64 int64_t ts_lo, 65 AVRational tb_lo) 66{ 67 int64_t hi, lo; 68 69 hi = ts_hi * tb_hi.num * tb_lo.den; 70 lo = ts_lo * tb_lo.num * tb_hi.den; 71 72 return hi - lo; 73} 74 75/** 76 * Partial search for keyframes in multiple streams. 77 * 78 * This routine searches in each stream for the next lower and the next higher 79 * timestamp compared to the given target timestamp. The search starts at the current 80 * file position and ends at the file position, where all streams have already been 81 * examined (or when all higher key frames are found in the first iteration). 82 * 83 * This routine is called iteratively with an exponential backoff to find the lower 84 * timestamp. 85 * 86 * @param s format context 87 * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE) 88 * @param timebase time base for timestamps 89 * @param flags seeking flags 90 * @param sync array with information per stream 91 * @param keyframes_to_find count of keyframes to find in total 92 * @param found_lo ptr to the count of already found low timestamp keyframes 93 * @param found_hi ptr to the count of already found high timestamp keyframes 94 * @param first_iter flag for first iteration 95 */ 96static void search_hi_lo_keyframes(AVFormatContext *s, 97 int64_t timestamp, 98 AVRational timebase, 99 int flags, 100 AVSyncPoint *sync, 101 int keyframes_to_find, 102 int *found_lo, 103 int *found_hi, 104 int first_iter) 105{ 106 AVPacket pkt; 107 AVSyncPoint *sp; 108 AVStream *st; 109 int idx; 110 int flg; 111 int terminated_count = 0; 112 int64_t pos; 113 int64_t pts, dts; // PTS/DTS from stream 114 int64_t ts; // PTS in stream-local time base or position for byte seeking 115 AVRational ts_tb; // Time base of the stream or 1:1 for byte seeking 116 117 for (;;) { 118 if (av_read_frame(s, &pkt) < 0) { 119 // EOF or error, make sure high flags are set 120 for (idx = 0; idx < s->nb_streams; ++idx) { 121 if (s->streams[idx]->discard < AVDISCARD_ALL) { 122 sp = &sync[idx]; 123 if (sp->pos_hi == INT64_MAX) { 124 // no high frame exists for this stream 125 (*found_hi)++; 126 sp->ts_hi = INT64_MAX; 127 sp->pos_hi = INT64_MAX - 1; 128 } 129 } 130 } 131 break; 132 } 133 134 idx = pkt.stream_index; 135 st = s->streams[idx]; 136 if (st->discard >= AVDISCARD_ALL) 137 // this stream is not active, skip packet 138 continue; 139 140 sp = &sync[idx]; 141 142 flg = pkt.flags; 143 pos = pkt.pos; 144 pts = pkt.pts; 145 dts = pkt.dts; 146 if (pts == AV_NOPTS_VALUE) 147 // some formats don't provide PTS, only DTS 148 pts = dts; 149 150 av_free_packet(&pkt); 151 152 // Multi-frame packets only return position for the very first frame. 153 // Other frames are read with position == -1. Therefore, we note down 154 // last known position of a frame and use it if a frame without 155 // position arrives. In this way, it's possible to seek to proper 156 // position. Additionally, for parsers not providing position at all, 157 // an approximation will be used (starting position of this iteration). 158 if (pos < 0) 159 pos = sp->last_pos; 160 else 161 sp->last_pos = pos; 162 163 // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set). 164 if (pts != AV_NOPTS_VALUE && 165 ((flg & AV_PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) { 166 if (flags & AVSEEK_FLAG_BYTE) { 167 // for byte seeking, use position as timestamp 168 ts = pos; 169 ts_tb.num = 1; 170 ts_tb.den = 1; 171 } else { 172 // otherwise, get stream time_base 173 ts = pts; 174 ts_tb = st->time_base; 175 } 176 177 if (sp->first_ts == AV_NOPTS_VALUE) { 178 // Note down termination timestamp for the next iteration - when 179 // we encounter a packet with the same timestamp, we will ignore 180 // any further packets for this stream in next iteration (as they 181 // are already evaluated). 182 sp->first_ts = ts; 183 sp->first_ts_tb = ts_tb; 184 } 185 186 if (sp->term_ts != AV_NOPTS_VALUE && 187 av_compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) { 188 // past the end position from last iteration, ignore packet 189 if (!sp->terminated) { 190 sp->terminated = 1; 191 ++terminated_count; 192 if (sp->pos_hi == INT64_MAX) { 193 // no high frame exists for this stream 194 (*found_hi)++; 195 sp->ts_hi = INT64_MAX; 196 sp->pos_hi = INT64_MAX - 1; 197 } 198 if (terminated_count == keyframes_to_find) 199 break; // all terminated, iteration done 200 } 201 continue; 202 } 203 204 if (av_compare_ts(ts, ts_tb, timestamp, timebase) <= 0) { 205 // keyframe found before target timestamp 206 if (sp->pos_lo == INT64_MAX) { 207 // found first keyframe lower than target timestamp 208 (*found_lo)++; 209 sp->ts_lo = ts; 210 sp->pos_lo = pos; 211 } else if (sp->ts_lo < ts) { 212 // found a better match (closer to target timestamp) 213 sp->ts_lo = ts; 214 sp->pos_lo = pos; 215 } 216 } 217 if (av_compare_ts(ts, ts_tb, timestamp, timebase) >= 0) { 218 // keyframe found after target timestamp 219 if (sp->pos_hi == INT64_MAX) { 220 // found first keyframe higher than target timestamp 221 (*found_hi)++; 222 sp->ts_hi = ts; 223 sp->pos_hi = pos; 224 if (*found_hi >= keyframes_to_find && first_iter) { 225 // We found high frame for all. They may get updated 226 // to TS closer to target TS in later iterations (which 227 // will stop at start position of previous iteration). 228 break; 229 } 230 } else if (sp->ts_hi > ts) { 231 // found a better match (actually, shouldn't happen) 232 sp->ts_hi = ts; 233 sp->pos_hi = pos; 234 } 235 } 236 } 237 } 238 239 // Clean up the parser. 240 ff_read_frame_flush(s); 241} 242 243int64_t ff_gen_syncpoint_search(AVFormatContext *s, 244 int stream_index, 245 int64_t pos, 246 int64_t ts_min, 247 int64_t ts, 248 int64_t ts_max, 249 int flags) 250{ 251 AVSyncPoint *sync, *sp; 252 AVStream *st; 253 int i; 254 int keyframes_to_find = 0; 255 int64_t curpos; 256 int64_t step; 257 int found_lo = 0, found_hi = 0; 258 int64_t min_distance, distance; 259 int64_t min_pos = 0; 260 int first_iter = 1; 261 AVRational time_base; 262 263 if (flags & AVSEEK_FLAG_BYTE) { 264 // for byte seeking, we have exact 1:1 "timestamps" - positions 265 time_base.num = 1; 266 time_base.den = 1; 267 } else { 268 if (stream_index >= 0) { 269 // we have a reference stream, which time base we use 270 st = s->streams[stream_index]; 271 time_base = st->time_base; 272 } else { 273 // no reference stream, use AV_TIME_BASE as reference time base 274 time_base.num = 1; 275 time_base.den = AV_TIME_BASE; 276 } 277 } 278 279 // Initialize syncpoint structures for each stream. 280 sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint)); 281 if (!sync) 282 // cannot allocate helper structure 283 return -1; 284 285 for (i = 0; i < s->nb_streams; ++i) { 286 st = s->streams[i]; 287 sp = &sync[i]; 288 289 sp->pos_lo = INT64_MAX; 290 sp->ts_lo = INT64_MAX; 291 sp->pos_hi = INT64_MAX; 292 sp->ts_hi = INT64_MAX; 293 sp->terminated = 0; 294 sp->first_ts = AV_NOPTS_VALUE; 295 sp->term_ts = ts_max; 296 sp->term_ts_tb = time_base; 297 sp->last_pos = pos; 298 299 st->cur_dts = AV_NOPTS_VALUE; 300 301 if (st->discard < AVDISCARD_ALL) 302 ++keyframes_to_find; 303 } 304 305 if (!keyframes_to_find) { 306 // no stream active, error 307 av_free(sync); 308 return -1; 309 } 310 311 // Find keyframes in all active streams with timestamp/position just before 312 // and just after requested timestamp/position. 313 step = s->pb->buffer_size; 314 curpos = FFMAX(pos - step / 2, 0); 315 for (;;) { 316 url_fseek(s->pb, curpos, SEEK_SET); 317 search_hi_lo_keyframes(s, 318 ts, time_base, 319 flags, 320 sync, 321 keyframes_to_find, 322 &found_lo, &found_hi, 323 first_iter); 324 if (found_lo == keyframes_to_find && found_hi == keyframes_to_find) 325 break; // have all keyframes we wanted 326 if (!curpos) 327 break; // cannot go back anymore 328 329 curpos = pos - step; 330 if (curpos < 0) 331 curpos = 0; 332 step *= 2; 333 334 // switch termination positions 335 for (i = 0; i < s->nb_streams; ++i) { 336 st = s->streams[i]; 337 st->cur_dts = AV_NOPTS_VALUE; 338 339 sp = &sync[i]; 340 if (sp->first_ts != AV_NOPTS_VALUE) { 341 sp->term_ts = sp->first_ts; 342 sp->term_ts_tb = sp->first_ts_tb; 343 sp->first_ts = AV_NOPTS_VALUE; 344 } 345 sp->terminated = 0; 346 sp->last_pos = curpos; 347 } 348 first_iter = 0; 349 } 350 351 // Find actual position to start decoding so that decoder synchronizes 352 // closest to ts and between ts_min and ts_max. 353 pos = INT64_MAX; 354 355 for (i = 0; i < s->nb_streams; ++i) { 356 st = s->streams[i]; 357 if (st->discard < AVDISCARD_ALL) { 358 sp = &sync[i]; 359 min_distance = INT64_MAX; 360 // Find timestamp closest to requested timestamp within min/max limits. 361 if (sp->pos_lo != INT64_MAX 362 && av_compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0 363 && av_compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) { 364 // low timestamp is in range 365 min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base); 366 min_pos = sp->pos_lo; 367 } 368 if (sp->pos_hi != INT64_MAX 369 && av_compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0 370 && av_compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) { 371 // high timestamp is in range, check distance 372 distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base); 373 if (distance < min_distance) { 374 min_distance = distance; 375 min_pos = sp->pos_hi; 376 } 377 } 378 if (min_distance == INT64_MAX) { 379 // no timestamp is in range, cannot seek 380 av_free(sync); 381 return -1; 382 } 383 if (min_pos < pos) 384 pos = min_pos; 385 } 386 } 387 388 url_fseek(s->pb, pos, SEEK_SET); 389 av_free(sync); 390 return pos; 391} 392 393AVParserState *ff_store_parser_state(AVFormatContext *s) 394{ 395 int i; 396 AVStream *st; 397 AVParserStreamState *ss; 398 AVParserState *state = av_malloc(sizeof(AVParserState)); 399 if (!state) 400 return NULL; 401 402 state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams); 403 if (!state->stream_states) { 404 av_free(state); 405 return NULL; 406 } 407 408 state->fpos = url_ftell(s->pb); 409 410 // copy context structures 411 state->cur_st = s->cur_st; 412 state->packet_buffer = s->packet_buffer; 413 state->raw_packet_buffer = s->raw_packet_buffer; 414 state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size; 415 416 s->cur_st = NULL; 417 s->packet_buffer = NULL; 418 s->raw_packet_buffer = NULL; 419 s->raw_packet_buffer_remaining_size = RAW_PACKET_BUFFER_SIZE; 420 421 // copy stream structures 422 state->nb_streams = s->nb_streams; 423 for (i = 0; i < s->nb_streams; i++) { 424 st = s->streams[i]; 425 ss = &state->stream_states[i]; 426 427 ss->parser = st->parser; 428 ss->last_IP_pts = st->last_IP_pts; 429 ss->cur_dts = st->cur_dts; 430 ss->reference_dts = st->reference_dts; 431 ss->cur_ptr = st->cur_ptr; 432 ss->cur_len = st->cur_len; 433 ss->probe_packets = st->probe_packets; 434 ss->cur_pkt = st->cur_pkt; 435 436 st->parser = NULL; 437 st->last_IP_pts = AV_NOPTS_VALUE; 438 st->cur_dts = AV_NOPTS_VALUE; 439 st->reference_dts = AV_NOPTS_VALUE; 440 st->cur_ptr = NULL; 441 st->cur_len = 0; 442 st->probe_packets = MAX_PROBE_PACKETS; 443 av_init_packet(&st->cur_pkt); 444 } 445 446 return state; 447} 448 449void ff_restore_parser_state(AVFormatContext *s, AVParserState *state) 450{ 451 int i; 452 AVStream *st; 453 AVParserStreamState *ss; 454 ff_read_frame_flush(s); 455 456 if (!state) 457 return; 458 459 url_fseek(s->pb, state->fpos, SEEK_SET); 460 461 // copy context structures 462 s->cur_st = state->cur_st; 463 s->packet_buffer = state->packet_buffer; 464 s->raw_packet_buffer = state->raw_packet_buffer; 465 s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size; 466 467 // copy stream structures 468 for (i = 0; i < state->nb_streams; i++) { 469 st = s->streams[i]; 470 ss = &state->stream_states[i]; 471 472 st->parser = ss->parser; 473 st->last_IP_pts = ss->last_IP_pts; 474 st->cur_dts = ss->cur_dts; 475 st->reference_dts = ss->reference_dts; 476 st->cur_ptr = ss->cur_ptr; 477 st->cur_len = ss->cur_len; 478 st->probe_packets = ss->probe_packets; 479 st->cur_pkt = ss->cur_pkt; 480 } 481 482 av_free(state->stream_states); 483 av_free(state); 484} 485 486static void free_packet_list(AVPacketList *pktl) 487{ 488 AVPacketList *cur; 489 while (pktl) { 490 cur = pktl; 491 pktl = cur->next; 492 av_free_packet(&cur->pkt); 493 av_free(cur); 494 } 495} 496 497void ff_free_parser_state(AVFormatContext *s, AVParserState *state) 498{ 499 int i; 500 AVParserStreamState *ss; 501 502 if (!state) 503 return; 504 505 for (i = 0; i < state->nb_streams; i++) { 506 ss = &state->stream_states[i]; 507 if (ss->parser) 508 av_parser_close(ss->parser); 509 av_free_packet(&ss->cur_pkt); 510 } 511 512 free_packet_list(state->packet_buffer); 513 free_packet_list(state->raw_packet_buffer); 514 515 av_free(state->stream_states); 516 av_free(state); 517} 518 519