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