libavformat/seek.c

   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
  26 // NOTE: implementation should be moved here in another patch, to keep patches
  27 // separated.
  28 extern void av_read_frame_flush(AVFormatContext *s);
  29
  30 /**
  31  * helper structure describing keyframe search state of one stream
  32  */
  33 typedef 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  * Compare two timestamps exactly, taking their respective time bases into account.
  52  *
  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
  58  */
  59 static int compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b)
  60 {
  61     int64_t a, b, res;
  62
  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;
  71
  72     a = ts_a * tb_a.num * tb_b.den;
  73     b = ts_b * tb_b.num * tb_a.den;
  74
  75     res = a - b;
  76     if (!res)
  77         return 0;
  78     else
  79         return (res >> 63) | 1;
  80 }
  81
  82 /**
  83  * Compute a distance between timestamps.
  84  *
  85  * Distances are only comparable, if same time bases are used for computing
  86  * distances.
  87  *
  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
  93  */
  94 static int64_t ts_distance(int64_t ts_hi,
  95                            AVRational tb_hi,
  96                            int64_t ts_lo,
  97                            AVRational tb_lo)
  98 {
  99     int64_t hi, lo;
 100
 101     hi = ts_hi * tb_hi.num * tb_lo.den;
 102     lo = ts_lo * tb_lo.num * tb_hi.den;
 103
 104     return hi - lo;
 105 }
 106
 107 /**
 108  * Partial search for keyframes in multiple streams.
 109  *
 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).
 114  *
 115  * This routine is called iteratively with an exponential backoff to find the lower
 116  * timestamp.
 117  *
 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
 127  */
 128 static void search_hi_lo_keyframes(AVFormatContext *s,
 129                                    int64_t timestamp,
 130                                    AVRational timebase,
 131                                    int flags,
 132                                    AVSyncPoint *sync,
 133                                    int keyframes_to_find,
 134                                    int *found_lo,
 135                                    int *found_hi,
 136                                    int first_iter)
 137 {
 138     AVPacket pkt;
 139     AVSyncPoint *sp;
 140     AVStream *st;
 141     int idx;
 142     int flg;
 143     int terminated_count = 0;
 144     int64_t pos;
 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
 148
 149     for (;;) {
 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) {
 154                     sp = &sync[idx];
 155                     if (sp->pos_hi == INT64_MAX) {
 156                         // no high frame exists for this stream
 157                         (*found_hi)++;
 158                         sp->ts_hi  = INT64_MAX;
 159                         sp->pos_hi = INT64_MAX - 1;
 160                     }
 161                 }
 162             }
 163             break;
 164         }
 165
 166         idx = pkt.stream_index;
 167         st = s->streams[idx];
 168         if (st->discard >= AVDISCARD_ALL)
 169             // this stream is not active, skip packet
 170             continue;
 171
 172         sp = &sync[idx];
 173
 174         flg = pkt.flags;
 175         pos = pkt.pos;
 176         pts = pkt.pts;
 177         dts = pkt.dts;
 178         if (pts == AV_NOPTS_VALUE)
 179             // some formats don't provide PTS, only DTS
 180             pts = dts;
 181
 182         av_free_packet(&pkt);
 183
 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).
 190         if (pos < 0)
 191             pos = sp->last_pos;
 192         else
 193             sp->last_pos = pos;
 194
 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
 200                 ts        = pos;
 201                 ts_tb.num = 1;
 202                 ts_tb.den = 1;
 203             } else {
 204                 // otherwise, get stream time_base
 205                 ts    = pts;
 206                 ts_tb = st->time_base;
 207             }
 208
 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).
 214                 sp->first_ts    = ts;
 215                 sp->first_ts_tb = ts_tb;
 216             }
 217
 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) {
 222                     sp->terminated = 1;
 223                     ++terminated_count;
 224                     if (sp->pos_hi == INT64_MAX) {
 225                         // no high frame exists for this stream
 226                         (*found_hi)++;
 227                         sp->ts_hi  = INT64_MAX;
 228                         sp->pos_hi = INT64_MAX - 1;
 229                     }
 230                     if (terminated_count == keyframes_to_find)
 231                         break;  // all terminated, iteration done
 232                 }
 233                 continue;
 234             }
 235
 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
 240                     (*found_lo)++;
 241                     sp->ts_lo  = ts;
 242                     sp->pos_lo = pos;
 243                 } else if (sp->ts_lo < ts) {
 244                     // found a better match (closer to target timestamp)
 245                     sp->ts_lo  = ts;
 246                     sp->pos_lo = pos;
 247                 }
 248             }
 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
 253                     (*found_hi)++;
 254                     sp->ts_hi  = ts;
 255                     sp->pos_hi = pos;
 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).
 260                         break;
 261                     }
 262                 } else if (sp->ts_hi > ts) {
 263                     // found a better match (actually, shouldn't happen)
 264                     sp->ts_hi  = ts;
 265                     sp->pos_hi = pos;
 266                 }
 267             }
 268         }
 269     }
 270
 271     // Clean up the parser.
 272     av_read_frame_flush(s);
 273 }
 274
 275 int64_t ff_gen_syncpoint_search(AVFormatContext *s,
 276                                 int stream_index,
 277                                 int64_t pos,
 278                                 int64_t ts_min,
 279                                 int64_t ts,
 280                                 int64_t ts_max,
 281                                 int flags)
 282 {
 283     AVSyncPoint *sync, *sp;
 284     AVStream *st;
 285     int i;
 286     int keyframes_to_find = 0;
 287     int64_t curpos;
 288     int64_t step;
 289     int found_lo = 0, found_hi = 0;
 290     int64_t min_distance, distance;
 291     int64_t min_pos = 0;
 292     int first_iter = 1;
 293     AVRational time_base;
 294
 295     if (flags & AVSEEK_FLAG_BYTE) {
 296         // for byte seeking, we have exact 1:1 "timestamps" - positions
 297         time_base.num = 1;
 298         time_base.den = 1;
 299     } else {
 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;
 304         } else {
 305             // no reference stream, use AV_TIME_BASE as reference time base
 306             time_base.num = 1;
 307             time_base.den = AV_TIME_BASE;
 308         }
 309     }
 310
 311     // Initialize syncpoint structures for each stream.
 312     sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint));
 313     if (!sync)
 314         // cannot allocate helper structure
 315         return -1;
 316
 317     for (i = 0; i < s->nb_streams; ++i) {
 318         st = s->streams[i];
 319         sp = &sync[i];
 320
 321         sp->pos_lo     = INT64_MAX;
 322         sp->ts_lo      = INT64_MAX;
 323         sp->pos_hi     = INT64_MAX;
 324         sp->ts_hi      = INT64_MAX;
 325         sp->terminated = 0;
 326         sp->first_ts   = AV_NOPTS_VALUE;
 327         sp->term_ts    = ts_max;
 328         sp->term_ts_tb = time_base;
 329         sp->last_pos   = pos;
 330
 331         st->cur_dts    = AV_NOPTS_VALUE;
 332
 333         if (st->discard < AVDISCARD_ALL)
 334             ++keyframes_to_find;
 335     }
 336
 337     if (!keyframes_to_find) {
 338         // no stream active, error
 339         av_free(sync);
 340         return -1;
 341     }
 342
 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);
 347     for (;;) {
 348         url_fseek(s->pb, curpos, SEEK_SET);
 349         search_hi_lo_keyframes(s,
 350                                ts, time_base,
 351                                flags,
 352                                sync,
 353                                keyframes_to_find,
 354                                &found_lo, &found_hi,
 355                                first_iter);
 356         if (found_lo == keyframes_to_find && found_hi == keyframes_to_find)
 357             break;  // have all keyframes we wanted
 358         if (!curpos)
 359             break;  // cannot go back anymore
 360
 361         curpos = pos - step;
 362         if (curpos < 0)
 363             curpos = 0;
 364         step *= 2;
 365
 366         // switch termination positions
 367         for (i = 0; i < s->nb_streams; ++i) {
 368             st = s->streams[i];
 369             st->cur_dts = AV_NOPTS_VALUE;
 370
 371             sp = &sync[i];
 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;
 376             }
 377             sp->terminated = 0;
 378             sp->last_pos = curpos;
 379         }
 380         first_iter = 0;
 381     }
 382
 383     // Find actual position to start decoding so that decoder synchronizes
 384     // closest to ts and between ts_min and ts_max.
 385     pos = INT64_MAX;
 386
 387     for (i = 0; i < s->nb_streams; ++i) {
 388         st = s->streams[i];
 389         if (st->discard < AVDISCARD_ALL) {
 390             sp = &sync[i];
 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;
 399             }
 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;
 408                 }
 409             }
 410             if (min_distance == INT64_MAX) {
 411                 // no timestamp is in range, cannot seek
 412                 av_free(sync);
 413                 return -1;
 414             }
 415             if (min_pos < pos)
 416                 pos = min_pos;
 417         }
 418     }
 419
 420     url_fseek(s->pb, pos, SEEK_SET);
 421     av_free(sync);
 422     return pos;
 423 }
 424
 425 AVParserState *ff_store_parser_state(AVFormatContext *s)
 426 {
 427     int i;
 428     AVStream *st;
 429     AVParserStreamState *ss;
 430     AVParserState *state = av_malloc(sizeof(AVParserState));
 431     if (!state)
 432         return NULL;
 433
 434     state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams);
 435     if (!state->stream_states) {
 436         av_free(state);
 437         return NULL;
 438     }
 439
 440     state->fpos = url_ftell(s->pb);
 441
 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;
 447
 448     s->cur_st                               = NULL;
 449     s->packet_buffer                        = NULL;
 450     s->raw_packet_buffer                    = NULL;
 451     s->raw_packet_buffer_remaining_size     = RAW_PACKET_BUFFER_SIZE;
 452
 453     // copy stream structures
 454     state->nb_streams = s->nb_streams;
 455     for (i = 0; i < s->nb_streams; i++) {
 456         st = s->streams[i];
 457         ss = &state->stream_states[i];
 458
 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;
 467
 468         st->parser        = NULL;
 469         st->last_IP_pts   = AV_NOPTS_VALUE;
 470         st->cur_dts       = AV_NOPTS_VALUE;
 471         st->reference_dts = AV_NOPTS_VALUE;
 472         st->cur_ptr       = NULL;
 473         st->cur_len       = 0;
 474         st->probe_packets = MAX_PROBE_PACKETS;
 475         av_init_packet(&st->cur_pkt);
 476     }
 477
 478     return state;
 479 }
 480
 481 void ff_restore_parser_state(AVFormatContext *s, AVParserState *state)
 482 {
 483     int i;
 484     AVStream *st;
 485     AVParserStreamState *ss;
 486     av_read_frame_flush(s);
 487
 488     if (!state)
 489         return;
 490
 491     url_fseek(s->pb, state->fpos, SEEK_SET);
 492
 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;
 498
 499     // copy stream structures
 500     for (i = 0; i < state->nb_streams; i++) {
 501         st = s->streams[i];
 502         ss = &state->stream_states[i];
 503
 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;
 512     }
 513
 514     av_free(state->stream_states);
 515     av_free(state);
 516 }
 517
 518 static void free_packet_list(AVPacketList *pktl)
 519 {
 520     AVPacketList *cur;
 521     while (pktl) {
 522         cur = pktl;
 523         pktl = cur->next;
 524         av_free_packet(&cur->pkt);
 525         av_free(cur);
 526     }
 527 }
 528
 529 void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
 530 {
 531     int i;
 532     AVParserStreamState *ss;
 533
 534     if (!state)
 535         return;
 536
 537     for (i = 0; i < state->nb_streams; i++) {
 538         ss = &state->stream_states[i];
 539         if (ss->parser)
 540             av_parser_close(ss->parser);
 541         av_free_packet(&ss->cur_pkt);
 542     }
 543
 544     free_packet_list(state->packet_buffer);
 545     free_packet_list(state->raw_packet_buffer);
 546
 547     av_free(state->stream_states);
 548     av_free(state);
 549 }
 550