| /* |
| * seek utility functions for use within format handlers |
| * |
| * Copyright (c) 2009 Ivan Schreter |
| * |
| * This file is part of FFmpeg. |
| * |
| * FFmpeg is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * FFmpeg is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public |
| * License along with FFmpeg; if not, write to the Free Software |
| * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
| */ |
| |
| #include "seek.h" |
| #include "libavutil/mathematics.h" |
| #include "libavutil/mem.h" |
| #include "internal.h" |
| |
| // NOTE: implementation should be moved here in another patch, to keep patches |
| // separated. |
| |
| /** |
| * helper structure describing keyframe search state of one stream |
| */ |
| typedef struct { |
| int64_t pos_lo; ///< position of the frame with low timestamp in file or INT64_MAX if not found (yet) |
| int64_t ts_lo; ///< frame presentation timestamp or same as pos_lo for byte seeking |
| |
| int64_t pos_hi; ///< position of the frame with high timestamp in file or INT64_MAX if not found (yet) |
| int64_t ts_hi; ///< frame presentation timestamp or same as pos_hi for byte seeking |
| |
| int64_t last_pos; ///< last known position of a frame, for multi-frame packets |
| |
| int64_t term_ts; ///< termination timestamp (which TS we already read) |
| AVRational term_ts_tb; ///< timebase for term_ts |
| int64_t first_ts; ///< first packet timestamp in this iteration (to fill term_ts later) |
| AVRational first_ts_tb; ///< timebase for first_ts |
| |
| int terminated; ///< termination flag for the current iteration |
| } AVSyncPoint; |
| |
| /** |
| * Compute a distance between timestamps. |
| * |
| * Distances are only comparable, if same time bases are used for computing |
| * distances. |
| * |
| * @param ts_hi high timestamp |
| * @param tb_hi high timestamp time base |
| * @param ts_lo low timestamp |
| * @param tb_lo low timestamp time base |
| * @return representation of distance between high and low timestamps |
| */ |
| static int64_t ts_distance(int64_t ts_hi, |
| AVRational tb_hi, |
| int64_t ts_lo, |
| AVRational tb_lo) |
| { |
| int64_t hi, lo; |
| |
| hi = ts_hi * tb_hi.num * tb_lo.den; |
| lo = ts_lo * tb_lo.num * tb_hi.den; |
| |
| return hi - lo; |
| } |
| |
| /** |
| * Partial search for keyframes in multiple streams. |
| * |
| * This routine searches in each stream for the next lower and the next higher |
| * timestamp compared to the given target timestamp. The search starts at the current |
| * file position and ends at the file position, where all streams have already been |
| * examined (or when all higher key frames are found in the first iteration). |
| * |
| * This routine is called iteratively with an exponential backoff to find the lower |
| * timestamp. |
| * |
| * @param s format context |
| * @param timestamp target timestamp (or position, if AVSEEK_FLAG_BYTE) |
| * @param timebase time base for timestamps |
| * @param flags seeking flags |
| * @param sync array with information per stream |
| * @param keyframes_to_find count of keyframes to find in total |
| * @param found_lo ptr to the count of already found low timestamp keyframes |
| * @param found_hi ptr to the count of already found high timestamp keyframes |
| * @param first_iter flag for first iteration |
| */ |
| static void search_hi_lo_keyframes(AVFormatContext *s, |
| int64_t timestamp, |
| AVRational timebase, |
| int flags, |
| AVSyncPoint *sync, |
| int keyframes_to_find, |
| int *found_lo, |
| int *found_hi, |
| int first_iter) |
| { |
| AVPacket pkt; |
| AVSyncPoint *sp; |
| AVStream *st; |
| int idx; |
| int flg; |
| int terminated_count = 0; |
| int64_t pos; |
| int64_t pts, dts; // PTS/DTS from stream |
| int64_t ts; // PTS in stream-local time base or position for byte seeking |
| AVRational ts_tb; // Time base of the stream or 1:1 for byte seeking |
| |
| for (;;) { |
| if (av_read_frame(s, &pkt) < 0) { |
| // EOF or error, make sure high flags are set |
| for (idx = 0; idx < s->nb_streams; ++idx) { |
| if (s->streams[idx]->discard < AVDISCARD_ALL) { |
| sp = &sync[idx]; |
| if (sp->pos_hi == INT64_MAX) { |
| // no high frame exists for this stream |
| (*found_hi)++; |
| sp->ts_hi = INT64_MAX; |
| sp->pos_hi = INT64_MAX - 1; |
| } |
| } |
| } |
| break; |
| } |
| |
| idx = pkt.stream_index; |
| st = s->streams[idx]; |
| if (st->discard >= AVDISCARD_ALL) |
| // this stream is not active, skip packet |
| continue; |
| |
| sp = &sync[idx]; |
| |
| flg = pkt.flags; |
| pos = pkt.pos; |
| pts = pkt.pts; |
| dts = pkt.dts; |
| if (pts == AV_NOPTS_VALUE) |
| // some formats don't provide PTS, only DTS |
| pts = dts; |
| |
| av_free_packet(&pkt); |
| |
| // Multi-frame packets only return position for the very first frame. |
| // Other frames are read with position == -1. Therefore, we note down |
| // last known position of a frame and use it if a frame without |
| // position arrives. In this way, it's possible to seek to proper |
| // position. Additionally, for parsers not providing position at all, |
| // an approximation will be used (starting position of this iteration). |
| if (pos < 0) |
| pos = sp->last_pos; |
| else |
| sp->last_pos = pos; |
| |
| // Evaluate key frames with known TS (or any frames, if AVSEEK_FLAG_ANY set). |
| if (pts != AV_NOPTS_VALUE && |
| ((flg & AV_PKT_FLAG_KEY) || (flags & AVSEEK_FLAG_ANY))) { |
| if (flags & AVSEEK_FLAG_BYTE) { |
| // for byte seeking, use position as timestamp |
| ts = pos; |
| ts_tb.num = 1; |
| ts_tb.den = 1; |
| } else { |
| // otherwise, get stream time_base |
| ts = pts; |
| ts_tb = st->time_base; |
| } |
| |
| if (sp->first_ts == AV_NOPTS_VALUE) { |
| // Note down termination timestamp for the next iteration - when |
| // we encounter a packet with the same timestamp, we will ignore |
| // any further packets for this stream in next iteration (as they |
| // are already evaluated). |
| sp->first_ts = ts; |
| sp->first_ts_tb = ts_tb; |
| } |
| |
| if (sp->term_ts != AV_NOPTS_VALUE && |
| av_compare_ts(ts, ts_tb, sp->term_ts, sp->term_ts_tb) > 0) { |
| // past the end position from last iteration, ignore packet |
| if (!sp->terminated) { |
| sp->terminated = 1; |
| ++terminated_count; |
| if (sp->pos_hi == INT64_MAX) { |
| // no high frame exists for this stream |
| (*found_hi)++; |
| sp->ts_hi = INT64_MAX; |
| sp->pos_hi = INT64_MAX - 1; |
| } |
| if (terminated_count == keyframes_to_find) |
| break; // all terminated, iteration done |
| } |
| continue; |
| } |
| |
| if (av_compare_ts(ts, ts_tb, timestamp, timebase) <= 0) { |
| // keyframe found before target timestamp |
| if (sp->pos_lo == INT64_MAX) { |
| // found first keyframe lower than target timestamp |
| (*found_lo)++; |
| sp->ts_lo = ts; |
| sp->pos_lo = pos; |
| } else if (sp->ts_lo < ts) { |
| // found a better match (closer to target timestamp) |
| sp->ts_lo = ts; |
| sp->pos_lo = pos; |
| } |
| } |
| if (av_compare_ts(ts, ts_tb, timestamp, timebase) >= 0) { |
| // keyframe found after target timestamp |
| if (sp->pos_hi == INT64_MAX) { |
| // found first keyframe higher than target timestamp |
| (*found_hi)++; |
| sp->ts_hi = ts; |
| sp->pos_hi = pos; |
| if (*found_hi >= keyframes_to_find && first_iter) { |
| // We found high frame for all. They may get updated |
| // to TS closer to target TS in later iterations (which |
| // will stop at start position of previous iteration). |
| break; |
| } |
| } else if (sp->ts_hi > ts) { |
| // found a better match (actually, shouldn't happen) |
| sp->ts_hi = ts; |
| sp->pos_hi = pos; |
| } |
| } |
| } |
| } |
| |
| // Clean up the parser. |
| ff_read_frame_flush(s); |
| } |
| |
| int64_t ff_gen_syncpoint_search(AVFormatContext *s, |
| int stream_index, |
| int64_t pos, |
| int64_t ts_min, |
| int64_t ts, |
| int64_t ts_max, |
| int flags) |
| { |
| AVSyncPoint *sync, *sp; |
| AVStream *st; |
| int i; |
| int keyframes_to_find = 0; |
| int64_t curpos; |
| int64_t step; |
| int found_lo = 0, found_hi = 0; |
| int64_t min_distance, distance; |
| int64_t min_pos = 0; |
| int first_iter = 1; |
| AVRational time_base; |
| |
| if (flags & AVSEEK_FLAG_BYTE) { |
| // for byte seeking, we have exact 1:1 "timestamps" - positions |
| time_base.num = 1; |
| time_base.den = 1; |
| } else { |
| if (stream_index >= 0) { |
| // we have a reference stream, which time base we use |
| st = s->streams[stream_index]; |
| time_base = st->time_base; |
| } else { |
| // no reference stream, use AV_TIME_BASE as reference time base |
| time_base.num = 1; |
| time_base.den = AV_TIME_BASE; |
| } |
| } |
| |
| // Initialize syncpoint structures for each stream. |
| sync = av_malloc(s->nb_streams * sizeof(AVSyncPoint)); |
| if (!sync) |
| // cannot allocate helper structure |
| return -1; |
| |
| for (i = 0; i < s->nb_streams; ++i) { |
| st = s->streams[i]; |
| sp = &sync[i]; |
| |
| sp->pos_lo = INT64_MAX; |
| sp->ts_lo = INT64_MAX; |
| sp->pos_hi = INT64_MAX; |
| sp->ts_hi = INT64_MAX; |
| sp->terminated = 0; |
| sp->first_ts = AV_NOPTS_VALUE; |
| sp->term_ts = ts_max; |
| sp->term_ts_tb = time_base; |
| sp->last_pos = pos; |
| |
| st->cur_dts = AV_NOPTS_VALUE; |
| |
| if (st->discard < AVDISCARD_ALL) |
| ++keyframes_to_find; |
| } |
| |
| if (!keyframes_to_find) { |
| // no stream active, error |
| av_free(sync); |
| return -1; |
| } |
| |
| // Find keyframes in all active streams with timestamp/position just before |
| // and just after requested timestamp/position. |
| step = s->pb->buffer_size; |
| curpos = FFMAX(pos - step / 2, 0); |
| for (;;) { |
| avio_seek(s->pb, curpos, SEEK_SET); |
| search_hi_lo_keyframes(s, |
| ts, time_base, |
| flags, |
| sync, |
| keyframes_to_find, |
| &found_lo, &found_hi, |
| first_iter); |
| if (found_lo == keyframes_to_find && found_hi == keyframes_to_find) |
| break; // have all keyframes we wanted |
| if (!curpos) |
| break; // cannot go back anymore |
| |
| curpos = pos - step; |
| if (curpos < 0) |
| curpos = 0; |
| step *= 2; |
| |
| // switch termination positions |
| for (i = 0; i < s->nb_streams; ++i) { |
| st = s->streams[i]; |
| st->cur_dts = AV_NOPTS_VALUE; |
| |
| sp = &sync[i]; |
| if (sp->first_ts != AV_NOPTS_VALUE) { |
| sp->term_ts = sp->first_ts; |
| sp->term_ts_tb = sp->first_ts_tb; |
| sp->first_ts = AV_NOPTS_VALUE; |
| } |
| sp->terminated = 0; |
| sp->last_pos = curpos; |
| } |
| first_iter = 0; |
| } |
| |
| // Find actual position to start decoding so that decoder synchronizes |
| // closest to ts and between ts_min and ts_max. |
| pos = INT64_MAX; |
| |
| for (i = 0; i < s->nb_streams; ++i) { |
| st = s->streams[i]; |
| if (st->discard < AVDISCARD_ALL) { |
| sp = &sync[i]; |
| min_distance = INT64_MAX; |
| // Find timestamp closest to requested timestamp within min/max limits. |
| if (sp->pos_lo != INT64_MAX |
| && av_compare_ts(ts_min, time_base, sp->ts_lo, st->time_base) <= 0 |
| && av_compare_ts(sp->ts_lo, st->time_base, ts_max, time_base) <= 0) { |
| // low timestamp is in range |
| min_distance = ts_distance(ts, time_base, sp->ts_lo, st->time_base); |
| min_pos = sp->pos_lo; |
| } |
| if (sp->pos_hi != INT64_MAX |
| && av_compare_ts(ts_min, time_base, sp->ts_hi, st->time_base) <= 0 |
| && av_compare_ts(sp->ts_hi, st->time_base, ts_max, time_base) <= 0) { |
| // high timestamp is in range, check distance |
| distance = ts_distance(sp->ts_hi, st->time_base, ts, time_base); |
| if (distance < min_distance) { |
| min_distance = distance; |
| min_pos = sp->pos_hi; |
| } |
| } |
| if (min_distance == INT64_MAX) { |
| // no timestamp is in range, cannot seek |
| av_free(sync); |
| return -1; |
| } |
| if (min_pos < pos) |
| pos = min_pos; |
| } |
| } |
| |
| avio_seek(s->pb, pos, SEEK_SET); |
| av_free(sync); |
| return pos; |
| } |
| |
| AVParserState *ff_store_parser_state(AVFormatContext *s) |
| { |
| int i; |
| AVStream *st; |
| AVParserStreamState *ss; |
| AVParserState *state = av_malloc(sizeof(AVParserState)); |
| if (!state) |
| return NULL; |
| |
| state->stream_states = av_malloc(sizeof(AVParserStreamState) * s->nb_streams); |
| if (!state->stream_states) { |
| av_free(state); |
| return NULL; |
| } |
| |
| state->fpos = avio_tell(s->pb); |
| |
| // copy context structures |
| state->cur_st = s->cur_st; |
| state->packet_buffer = s->packet_buffer; |
| state->raw_packet_buffer = s->raw_packet_buffer; |
| state->raw_packet_buffer_remaining_size = s->raw_packet_buffer_remaining_size; |
| |
| s->cur_st = NULL; |
| s->packet_buffer = NULL; |
| s->raw_packet_buffer = NULL; |
| s->raw_packet_buffer_remaining_size = RAW_PACKET_BUFFER_SIZE; |
| |
| // copy stream structures |
| state->nb_streams = s->nb_streams; |
| for (i = 0; i < s->nb_streams; i++) { |
| st = s->streams[i]; |
| ss = &state->stream_states[i]; |
| |
| ss->parser = st->parser; |
| ss->last_IP_pts = st->last_IP_pts; |
| ss->cur_dts = st->cur_dts; |
| ss->reference_dts = st->reference_dts; |
| ss->cur_ptr = st->cur_ptr; |
| ss->cur_len = st->cur_len; |
| ss->probe_packets = st->probe_packets; |
| ss->cur_pkt = st->cur_pkt; |
| |
| st->parser = NULL; |
| st->last_IP_pts = AV_NOPTS_VALUE; |
| st->cur_dts = AV_NOPTS_VALUE; |
| st->reference_dts = AV_NOPTS_VALUE; |
| st->cur_ptr = NULL; |
| st->cur_len = 0; |
| st->probe_packets = MAX_PROBE_PACKETS; |
| av_init_packet(&st->cur_pkt); |
| } |
| |
| return state; |
| } |
| |
| void ff_restore_parser_state(AVFormatContext *s, AVParserState *state) |
| { |
| int i; |
| AVStream *st; |
| AVParserStreamState *ss; |
| ff_read_frame_flush(s); |
| |
| if (!state) |
| return; |
| |
| avio_seek(s->pb, state->fpos, SEEK_SET); |
| |
| // copy context structures |
| s->cur_st = state->cur_st; |
| s->packet_buffer = state->packet_buffer; |
| s->raw_packet_buffer = state->raw_packet_buffer; |
| s->raw_packet_buffer_remaining_size = state->raw_packet_buffer_remaining_size; |
| |
| // copy stream structures |
| for (i = 0; i < state->nb_streams; i++) { |
| st = s->streams[i]; |
| ss = &state->stream_states[i]; |
| |
| st->parser = ss->parser; |
| st->last_IP_pts = ss->last_IP_pts; |
| st->cur_dts = ss->cur_dts; |
| st->reference_dts = ss->reference_dts; |
| st->cur_ptr = ss->cur_ptr; |
| st->cur_len = ss->cur_len; |
| st->probe_packets = ss->probe_packets; |
| st->cur_pkt = ss->cur_pkt; |
| } |
| |
| av_free(state->stream_states); |
| av_free(state); |
| } |
| |
| static void free_packet_list(AVPacketList *pktl) |
| { |
| AVPacketList *cur; |
| while (pktl) { |
| cur = pktl; |
| pktl = cur->next; |
| av_free_packet(&cur->pkt); |
| av_free(cur); |
| } |
| } |
| |
| void ff_free_parser_state(AVFormatContext *s, AVParserState *state) |
| { |
| int i; |
| AVParserStreamState *ss; |
| |
| if (!state) |
| return; |
| |
| for (i = 0; i < state->nb_streams; i++) { |
| ss = &state->stream_states[i]; |
| if (ss->parser) |
| av_parser_close(ss->parser); |
| av_free_packet(&ss->cur_pkt); |
| } |
| |
| free_packet_list(state->packet_buffer); |
| free_packet_list(state->raw_packet_buffer); |
| |
| av_free(state->stream_states); |
| av_free(state); |
| } |
| |
