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