int64_t ff_gen_search(AVFormatContext *s, int stream_index, int64_t target_ts, int64_t pos_min, int64_t pos_max, int64_t pos_limit, int64_t ts_min, int64_t ts_max, int flags, int64_t *ts_ret, int64_t (*read_timestamp)(struct AVFormatContext *, int , int64_t *, int64_t )) { int64_t pos, ts; int64_t start_pos, filesize; int no_change; av_dlog(s, "gen_seek: %d %s\n", stream_index, av_ts2str(target_ts)); if(ts_min == AV_NOPTS_VALUE){ pos_min = s->data_offset; ts_min = ff_read_timestamp(s, stream_index, &pos_min, INT64_MAX, read_timestamp); if (ts_min == AV_NOPTS_VALUE) return -1; } if(ts_min >= target_ts){ *ts_ret= ts_min; return pos_min; } if(ts_max == AV_NOPTS_VALUE){ int step= 1024; filesize = avio_size(s->pb); pos_max = filesize - 1; do{ pos_max = FFMAX(0, pos_max - step); ts_max = ff_read_timestamp(s, stream_index, &pos_max, pos_max + step, read_timestamp); step += step; }while(ts_max == AV_NOPTS_VALUE && pos_max > 0); if (ts_max == AV_NOPTS_VALUE) return -1; for(;;){ int64_t tmp_pos= pos_max + 1; int64_t tmp_ts= ff_read_timestamp(s, stream_index, &tmp_pos, INT64_MAX, read_timestamp); if(tmp_ts == AV_NOPTS_VALUE) break; ts_max= tmp_ts; pos_max= tmp_pos; if(tmp_pos >= filesize) break; } pos_limit= pos_max; } if(ts_max <= target_ts){ *ts_ret= ts_max; return pos_max; } if(ts_min > ts_max){ return -1; }else if(ts_min == ts_max){ pos_limit= pos_min; } no_change=0; while (pos_min < pos_limit) { av_dlog(s, "pos_min=0x%"PRIx64" pos_max=0x%"PRIx64" dts_min=%s dts_max=%s\n", pos_min, pos_max, av_ts2str(ts_min), av_ts2str(ts_max)); assert(pos_limit <= pos_max); if(no_change==0){ int64_t approximate_keyframe_distance= pos_max - pos_limit; // interpolate position (better than dichotomy) pos = av_rescale(target_ts - ts_min, pos_max - pos_min, ts_max - ts_min) + pos_min - approximate_keyframe_distance; }else if(no_change==1){ // bisection, if interpolation failed to change min or max pos last time pos = (pos_min + pos_limit)>>1; }else{ /* linear search if bisection failed, can only happen if there are very few or no keyframes between min/max */ pos=pos_min; } if(pos <= pos_min) pos= pos_min + 1; else if(pos > pos_limit) pos= pos_limit; start_pos= pos; ts = ff_read_timestamp(s, stream_index, &pos, INT64_MAX, read_timestamp); //may pass pos_limit instead of -1 if(pos == pos_max) no_change++; else no_change=0; av_dlog(s, "%"PRId64" %"PRId64" %"PRId64" / %s %s %s target:%s limit:%"PRId64" start:%"PRId64" noc:%d\n", pos_min, pos, pos_max, av_ts2str(ts_min), av_ts2str(ts), av_ts2str(ts_max), av_ts2str(target_ts), pos_limit, start_pos, no_change); if(ts == AV_NOPTS_VALUE){ av_log(s, AV_LOG_ERROR, "read_timestamp() failed in the middle\n"); return -1; } assert(ts != AV_NOPTS_VALUE); if (target_ts <= ts) { pos_limit = start_pos - 1; pos_max = pos; ts_max = ts; } if (target_ts >= ts) { pos_min = pos; ts_min = ts; } } pos = (flags & AVSEEK_FLAG_BACKWARD) ? pos_min : pos_max; ts = (flags & AVSEEK_FLAG_BACKWARD) ? ts_min : ts_max; #if 0 pos_min = pos; ts_min = ff_read_timestamp(s, stream_index, &pos_min, INT64_MAX, read_timestamp); pos_min++; ts_max = ff_read_timestamp(s, stream_index, &pos_min, INT64_MAX, read_timestamp); av_dlog(s, "pos=0x%"PRIx64" %s<=%s<=%s\n", pos, av_ts2str(ts_min), av_ts2str(target_ts), av_ts2str(ts_max)); #endif *ts_ret= ts; return pos; }