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