gst-libs/ext/ffmpeg/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 #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  */
  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  * 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  */
  62 static 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  */
  96 static 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
 243 int64_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
 393 AVParserState *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
 449 void 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
 486 static 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
 497 void 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