• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

libavformat/seek.c

Go to the documentation of this file.
00001 /*
00002  * seek utility functions for use within format handlers
00003  *
00004  * Copyright (c) 2009 Ivan Schreter
00005  *
00006  * This file is part of FFmpeg.
00007  *
00008  * FFmpeg is free software; you can redistribute it and/or
00009  * modify it under the terms of the GNU Lesser General Public
00010  * License as published by the Free Software Foundation; either
00011  * version 2.1 of the License, or (at your option) any later version.
00012  *
00013  * FFmpeg is distributed in the hope that it will be useful,
00014  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00016  * Lesser General Public License for more details.
00017  *
00018  * You should have received a copy of the GNU Lesser General Public
00019  * License along with FFmpeg; if not, write to the Free Software
00020  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00021  */
00022 
00023 #include "seek.h"
00024 #include "libavutil/mem.h"
00025 #include "internal.h"
00026 
00027 // NOTE: implementation should be moved here in another patch, to keep patches
00028 // separated.
00029 
00033 typedef struct {
00034     int64_t     pos_lo;      
00035     int64_t     ts_lo;       
00036 
00037     int64_t     pos_hi;      
00038     int64_t     ts_hi;       
00039 
00040     int64_t     last_pos;    
00041 
00042     int64_t     term_ts;     
00043     AVRational  term_ts_tb;  
00044     int64_t     first_ts;    
00045     AVRational  first_ts_tb; 
00046 
00047     int         terminated;  
00048 } AVSyncPoint;
00049 
00062 static int64_t ts_distance(int64_t ts_hi,
00063                            AVRational tb_hi,
00064                            int64_t ts_lo,
00065                            AVRational tb_lo)
00066 {
00067     int64_t hi, lo;
00068 
00069     hi = ts_hi * tb_hi.num * tb_lo.den;
00070     lo = ts_lo * tb_lo.num * tb_hi.den;
00071 
00072     return hi - lo;
00073 }
00074 
00096 static void search_hi_lo_keyframes(AVFormatContext *s,
00097                                    int64_t timestamp,
00098                                    AVRational timebase,
00099                                    int flags,
00100                                    AVSyncPoint *sync,
00101                                    int keyframes_to_find,
00102                                    int *found_lo,
00103                                    int *found_hi,
00104                                    int first_iter)
00105 {
00106     AVPacket pkt;
00107     AVSyncPoint *sp;
00108     AVStream *st;
00109     int idx;
00110     int flg;
00111     int terminated_count = 0;
00112     int64_t pos;
00113     int64_t pts, dts;   // PTS/DTS from stream
00114     int64_t ts;         // PTS in stream-local time base or position for byte seeking
00115     AVRational ts_tb;   // Time base of the stream or 1:1 for byte seeking
00116 
00117     for (;;) {
00118         if (av_read_frame(s, &pkt) < 0) {
00119             // EOF or error, make sure high flags are set
00120             for (idx = 0; idx < s->nb_streams; ++idx) {
00121                 if (s->streams[idx]->discard < AVDISCARD_ALL) {
00122                     sp = &sync[idx];
00123                     if (sp->pos_hi == INT64_MAX) {
00124                         // no high frame exists for this stream
00125                         (*found_hi)++;
00126                         sp->ts_hi  = INT64_MAX;
00127                         sp->pos_hi = INT64_MAX - 1;
00128                     }
00129                 }
00130             }
00131             break;
00132         }
00133 
00134         idx = pkt.stream_index;
00135         st = s->streams[idx];
00136         if (st->discard >= AVDISCARD_ALL)
00137             // this stream is not active, skip packet
00138             continue;
00139 
00140         sp = &sync[idx];
00141 
00142         flg = pkt.flags;
00143         pos = pkt.pos;
00144         pts = pkt.pts;
00145         dts = pkt.dts;
00146         if (pts == AV_NOPTS_VALUE)
00147             // some formats don't provide PTS, only DTS
00148             pts = dts;
00149 
00150         av_free_packet(&pkt);
00151 
00152         // Multi-frame packets only return position for the very first frame.
00153         // Other frames are read with position == -1. Therefore, we note down
00154         // last known position of a frame and use it if a frame without
00155         // position arrives. In this way, it's possible to seek to proper
00156         // position. Additionally, for parsers not providing position at all,
00157         // an approximation will be used (starting position of this iteration).
00158         if (pos < 0)
00159             pos = sp->last_pos;
00160         else
00161             sp->last_pos = pos;
00162 
00163         // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set).
00164         if (pts != AV_NOPTS_VALUE &&
00165             ((flg & AV_PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) {
00166             if (flags & AVSEEK_FLAG_BYTE) {
00167                 // for byte seeking, use position as timestamp
00168                 ts        = pos;
00169                 ts_tb.num = 1;
00170                 ts_tb.den = 1;
00171             } else {
00172                 // otherwise, get stream time_base
00173                 ts    = pts;
00174                 ts_tb = st->time_base;
00175             }
00176 
00177             if (sp->first_ts == AV_NOPTS_VALUE) {
00178                 // Note down termination timestamp for the next iteration - when
00179                 // we encounter a packet with the same timestamp, we will ignore
00180                 // any further packets for this stream in next iteration (as they
00181                 // are already evaluated).
00182                 sp->first_ts    = ts;
00183                 sp->first_ts_tb = ts_tb;
00184             }
00185 
00186             if (sp->term_ts != AV_NOPTS_VALUE &&
00187                 av_compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) {
00188                 // past the end position from last iteration, ignore packet
00189                 if (!sp->terminated) {
00190                     sp->terminated = 1;
00191                     ++terminated_count;
00192                     if (sp->pos_hi == INT64_MAX) {
00193                         // no high frame exists for this stream
00194                         (*found_hi)++;
00195                         sp->ts_hi  = INT64_MAX;
00196                         sp->pos_hi = INT64_MAX - 1;
00197                     }
00198                     if (terminated_count == keyframes_to_find)
00199                         break;  // all terminated, iteration done
00200                 }
00201                 continue;
00202             }
00203 
00204             if (av_compare_ts(ts, ts_tb, timestamp, timebase) <= 0) {
00205                 // keyframe found before target timestamp
00206                 if (sp->pos_lo == INT64_MAX) {
00207                     // found first keyframe lower than target timestamp
00208                     (*found_lo)++;
00209                     sp->ts_lo  = ts;
00210                     sp->pos_lo = pos;
00211                 } else if (sp->ts_lo < ts) {
00212                     // found a better match (closer to target timestamp)
00213                     sp->ts_lo  = ts;
00214                     sp->pos_lo = pos;
00215                 }
00216             }
00217             if (av_compare_ts(ts, ts_tb, timestamp, timebase) >= 0) {
00218                 // keyframe found after target timestamp
00219                 if (sp->pos_hi == INT64_MAX) {
00220                     // found first keyframe higher than target timestamp
00221                     (*found_hi)++;
00222                     sp->ts_hi  = ts;
00223                     sp->pos_hi = pos;
00224                     if (*found_hi >= keyframes_to_find && first_iter) {
00225                         // We found high frame for all. They may get updated
00226                         // to TS closer to target TS in later iterations (which
00227                         // will stop at start position of previous iteration).
00228                         break;
00229                     }
00230                 } else if (sp->ts_hi > ts) {
00231                     // found a better match (actually, shouldn't happen)
00232                     sp->ts_hi  = ts;
00233                     sp->pos_hi = pos;
00234                 }
00235             }
00236         }
00237     }
00238 
00239     // Clean up the parser.
00240     ff_read_frame_flush(s);
00241 }
00242 
00243 int64_t ff_gen_syncpoint_search(AVFormatContext *s,
00244                                 int stream_index,
00245                                 int64_t pos,
00246                                 int64_t ts_min,
00247                                 int64_t ts,
00248                                 int64_t ts_max,
00249                                 int flags)
00250 {
00251     AVSyncPoint *sync, *sp;
00252     AVStream *st;
00253     int i;
00254     int keyframes_to_find = 0;
00255     int64_t curpos;
00256     int64_t step;
00257     int found_lo = 0, found_hi = 0;
00258     int64_t min_distance, distance;
00259     int64_t min_pos = 0;
00260     int first_iter = 1;
00261     AVRational time_base;
00262 
00263     if (flags & AVSEEK_FLAG_BYTE) {
00264         // for byte seeking, we have exact 1:1 "timestamps" - positions
00265         time_base.num = 1;
00266         time_base.den = 1;
00267     } else {
00268         if (stream_index >= 0) {
00269             // we have a reference stream, which time base we use
00270             st = s->streams[stream_index];
00271             time_base = st->time_base;
00272         } else {
00273             // no reference stream, use AV_TIME_BASE as reference time base
00274             time_base.num = 1;
00275             time_base.den = AV_TIME_BASE;
00276         }
00277     }
00278 
00279     // Initialize syncpoint structures for each stream.
00280     sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint));
00281     if (!sync)
00282         // cannot allocate helper structure
00283         return -1;
00284 
00285     for (i = 0; i < s->nb_streams; ++i) {
00286         st = s->streams[i];
00287         sp = &sync[i];
00288 
00289         sp->pos_lo     = INT64_MAX;
00290         sp->ts_lo      = INT64_MAX;
00291         sp->pos_hi     = INT64_MAX;
00292         sp->ts_hi      = INT64_MAX;
00293         sp->terminated = 0;
00294         sp->first_ts   = AV_NOPTS_VALUE;
00295         sp->term_ts    = ts_max;
00296         sp->term_ts_tb = time_base;
00297         sp->last_pos   = pos;
00298 
00299         st->cur_dts    = AV_NOPTS_VALUE;
00300 
00301         if (st->discard < AVDISCARD_ALL)
00302             ++keyframes_to_find;
00303     }
00304 
00305     if (!keyframes_to_find) {
00306         // no stream active, error
00307         av_free(sync);
00308         return -1;
00309     }
00310 
00311     // Find keyframes in all active streams with timestamp/position just before
00312     // and just after requested timestamp/position.
00313     step = s->pb->buffer_size;
00314     curpos = FFMAX(pos - step / 2, 0);
00315     for (;;) {
00316         url_fseek(s->pb, curpos, SEEK_SET);
00317         search_hi_lo_keyframes(s,
00318                                ts, time_base,
00319                                flags,
00320                                sync,
00321                                keyframes_to_find,
00322                                &found_lo, &found_hi,
00323                                first_iter);
00324         if (found_lo == keyframes_to_find && found_hi == keyframes_to_find)
00325             break;  // have all keyframes we wanted
00326         if (!curpos)
00327             break;  // cannot go back anymore
00328 
00329         curpos = pos - step;
00330         if (curpos < 0)
00331             curpos = 0;
00332         step *= 2;
00333 
00334         // switch termination positions
00335         for (i = 0; i < s->nb_streams; ++i) {
00336             st = s->streams[i];
00337             st->cur_dts = AV_NOPTS_VALUE;
00338 
00339             sp = &sync[i];
00340             if (sp->first_ts != AV_NOPTS_VALUE) {
00341                 sp->term_ts    = sp->first_ts;
00342                 sp->term_ts_tb = sp->first_ts_tb;
00343                 sp->first_ts   = AV_NOPTS_VALUE;
00344             }
00345             sp->terminated = 0;
00346             sp->last_pos = curpos;
00347         }
00348         first_iter = 0;
00349     }
00350 
00351     // Find actual position to start decoding so that decoder synchronizes
00352     // closest to ts and between ts_min and ts_max.
00353     pos = INT64_MAX;
00354 
00355     for (i = 0; i < s->nb_streams; ++i) {
00356         st = s->streams[i];
00357         if (st->discard < AVDISCARD_ALL) {
00358             sp = &sync[i];
00359             min_distance = INT64_MAX;
00360             // Find timestamp closest to requested timestamp within min/max limits.
00361             if (sp->pos_lo != INT64_MAX
00362                 && av_compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0
00363                 && av_compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) {
00364                 // low timestamp is in range
00365                 min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base);
00366                 min_pos = sp->pos_lo;
00367             }
00368             if (sp->pos_hi != INT64_MAX
00369                 && av_compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0
00370                 && av_compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) {
00371                 // high timestamp is in range, check distance
00372                 distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base);
00373                 if (distance < min_distance) {
00374                     min_distance = distance;
00375                     min_pos = sp->pos_hi;
00376                 }
00377             }
00378             if (min_distance == INT64_MAX) {
00379                 // no timestamp is in range, cannot seek
00380                 av_free(sync);
00381                 return -1;
00382             }
00383             if (min_pos < pos)
00384                 pos = min_pos;
00385         }
00386     }
00387 
00388     url_fseek(s->pb, pos, SEEK_SET);
00389     av_free(sync);
00390     return pos;
00391 }
00392 
00393 AVParserState *ff_store_parser_state(AVFormatContext *s)
00394 {
00395     int i;
00396     AVStream *st;
00397     AVParserStreamState *ss;
00398     AVParserState *state = av_malloc(sizeof(AVParserState));
00399     if (!state)
00400         return NULL;
00401 
00402     state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams);
00403     if (!state->stream_states) {
00404         av_free(state);
00405         return NULL;
00406     }
00407 
00408     state->fpos = url_ftell(s->pb);
00409 
00410     // copy context structures
00411     state->cur_st                           = s->cur_st;
00412     state->packet_buffer                    = s->packet_buffer;
00413     state->raw_packet_buffer                = s->raw_packet_buffer;
00414     state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size;
00415 
00416     s->cur_st                               = NULL;
00417     s->packet_buffer                        = NULL;
00418     s->raw_packet_buffer                    = NULL;
00419     s->raw_packet_buffer_remaining_size     = RAW_PACKET_BUFFER_SIZE;
00420 
00421     // copy stream structures
00422     state->nb_streams = s->nb_streams;
00423     for (i = 0; i < s->nb_streams; i++) {
00424         st = s->streams[i];
00425         ss = &state->stream_states[i];
00426 
00427         ss->parser        = st->parser;
00428         ss->last_IP_pts   = st->last_IP_pts;
00429         ss->cur_dts       = st->cur_dts;
00430         ss->reference_dts = st->reference_dts;
00431         ss->cur_ptr       = st->cur_ptr;
00432         ss->cur_len       = st->cur_len;
00433         ss->probe_packets = st->probe_packets;
00434         ss->cur_pkt       = st->cur_pkt;
00435 
00436         st->parser        = NULL;
00437         st->last_IP_pts   = AV_NOPTS_VALUE;
00438         st->cur_dts       = AV_NOPTS_VALUE;
00439         st->reference_dts = AV_NOPTS_VALUE;
00440         st->cur_ptr       = NULL;
00441         st->cur_len       = 0;
00442         st->probe_packets = MAX_PROBE_PACKETS;
00443         av_init_packet(&st->cur_pkt);
00444     }
00445 
00446     return state;
00447 }
00448 
00449 void ff_restore_parser_state(AVFormatContext *s, AVParserState *state)
00450 {
00451     int i;
00452     AVStream *st;
00453     AVParserStreamState *ss;
00454     ff_read_frame_flush(s);
00455 
00456     if (!state)
00457         return;
00458 
00459     url_fseek(s->pb, state->fpos, SEEK_SET);
00460 
00461     // copy context structures
00462     s->cur_st                           = state->cur_st;
00463     s->packet_buffer                    = state->packet_buffer;
00464     s->raw_packet_buffer                = state->raw_packet_buffer;
00465     s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size;
00466 
00467     // copy stream structures
00468     for (i = 0; i < state->nb_streams; i++) {
00469         st = s->streams[i];
00470         ss = &state->stream_states[i];
00471 
00472         st->parser        = ss->parser;
00473         st->last_IP_pts   = ss->last_IP_pts;
00474         st->cur_dts       = ss->cur_dts;
00475         st->reference_dts = ss->reference_dts;
00476         st->cur_ptr       = ss->cur_ptr;
00477         st->cur_len       = ss->cur_len;
00478         st->probe_packets = ss->probe_packets;
00479         st->cur_pkt       = ss->cur_pkt;
00480     }
00481 
00482     av_free(state->stream_states);
00483     av_free(state);
00484 }
00485 
00486 static void free_packet_list(AVPacketList *pktl)
00487 {
00488     AVPacketList *cur;
00489     while (pktl) {
00490         cur = pktl;
00491         pktl = cur->next;
00492         av_free_packet(&cur->pkt);
00493         av_free(cur);
00494     }
00495 }
00496 
00497 void ff_free_parser_state(AVFormatContext *s, AVParserState *state)
00498 {
00499     int i;
00500     AVParserStreamState *ss;
00501 
00502     if (!state)
00503         return;
00504 
00505     for (i = 0; i < state->nb_streams; i++) {
00506         ss = &state->stream_states[i];
00507         if (ss->parser)
00508             av_parser_close(ss->parser);
00509         av_free_packet(&ss->cur_pkt);
00510     }
00511 
00512     free_packet_list(state->packet_buffer);
00513     free_packet_list(state->raw_packet_buffer);
00514 
00515     av_free(state->stream_states);
00516     av_free(state);
00517 }
00518 

Generated on Fri Sep 16 2011 17:17:51 for FFmpeg by  doxygen 1.7.1