comparison utils.c @ 437:50bae308f71e libavformat

moving nearly identical binary search code from nut/mpeg/asf to utils.c

436:dd042d607ec9

        }
    }
    return a;
}

static int av_seek_frame_generic(AVFormatContext *s, 
                                 int stream_index, int64_t timestamp)
{
    int index;
    AVStream *st;

    else
        ret = -1;
    if (ret >= 0) {
        return 0;
    }
    
    return av_seek_frame_generic(s, stream_index, timestamp);
}

/*******************************************************/

/* return TRUE if the stream has accurate timings for at least one component */

437:50bae308f71e

        }
    }
    return a;
}

#define DEBUG_SEEK

int av_seek_frame_binary(AVFormatContext *s, int stream_index, int64_t target_ts){
    AVInputFormat *avif= s->iformat;
    int64_t pos_min, pos_max, pos, pos_limit;
    int64_t ts_min, ts_max, ts;
    int64_t start_pos;
    int index, no_change;
    AVStream *st;

    if (stream_index < 0) {
        stream_index = av_find_default_stream_index(s);
        if (stream_index < 0)
            return -1;
    }

#ifdef DEBUG_SEEK
    av_log(s, AV_LOG_DEBUG, "read_seek: %d %lld\n", stream_index, target_ts);
#endif

    ts_max=
    ts_min= AV_NOPTS_VALUE;
    pos_limit= -1; //gcc falsely says it may be uninitalized

    st= s->streams[stream_index];
    if(st->index_entries){
        AVIndexEntry *e;

        index= av_index_search_timestamp(st, target_ts);
        e= &st->index_entries[index];

        if(e->timestamp <= target_ts || e->pos == e->min_distance){
            pos_min= e->pos;
            ts_min= e->timestamp;
#ifdef DEBUG_SEEK
        av_log(s, AV_LOG_DEBUG, "unsing cached pos_min=0x%llx dts_min=%lld\n", 
               pos_min,ts_min);
#endif
        }else{
            assert(index==0);
        }
        index++;
        if(index < st->nb_index_entries){
            e= &st->index_entries[index];
            assert(e->timestamp >= target_ts);
            pos_max= e->pos;
            ts_max= e->timestamp;
            pos_limit= pos_max - e->min_distance;
#ifdef DEBUG_SEEK
        av_log(s, AV_LOG_DEBUG, "unsing cached pos_max=0x%llx pos_limit=0x%llx dts_max=%lld\n", 
               pos_max,pos_limit, ts_max);
#endif
        }
    }

    if(ts_min == AV_NOPTS_VALUE){
        pos_min = s->data_offset;
        ts_min = avif->read_timestamp(s, stream_index, &pos_min, INT64_MAX);
        if (ts_min == AV_NOPTS_VALUE)
            return -1;
    }

    if(ts_max == AV_NOPTS_VALUE){
        int step= 1024;
        pos_max = url_filesize(url_fileno(&s->pb)) - 1;
        do{
            pos_max -= step;
            ts_max = avif->read_timestamp(s, stream_index, &pos_max, pos_max + step);
            step += step;
        }while(ts_max == AV_NOPTS_VALUE && pos_max >= step);
        if (ts_max == AV_NOPTS_VALUE)
            return -1;
        
        for(;;){
            int64_t tmp_pos= pos_max + 1;
            int64_t tmp_ts= avif->read_timestamp(s, stream_index, &tmp_pos, INT64_MAX);
            if(tmp_ts == AV_NOPTS_VALUE)
                break;
            ts_max= tmp_ts;
            pos_max= tmp_pos;
        }
        pos_limit= pos_max;
    }

    no_change=0;
    while (pos_min < pos_limit) {
#ifdef DEBUG_SEEK
        av_log(s, AV_LOG_DEBUG, "pos_min=0x%llx pos_max=0x%llx dts_min=%lld dts_max=%lld\n", 
               pos_min, pos_max,
               ts_min, ts_max);
#endif
        assert(pos_limit <= pos_max);

        if(no_change==0){
            int64_t approximate_keyframe_distance= pos_max - pos_limit;
            // interpolate position (better than dichotomy)
            pos = (int64_t)((double)(pos_max - pos_min) *
                            (double)(target_ts - ts_min) /
                            (double)(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 keframes 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 = avif->read_timestamp(s, stream_index, &pos, INT64_MAX); //may pass pos_limit instead of -1
        if(pos == pos_max)
            no_change++;
        else
            no_change=0;
#ifdef DEBUG_SEEK
av_log(s, AV_LOG_DEBUG, "%Ld %Ld %Ld / %Ld %Ld %Ld target:%Ld limit:%Ld start:%Ld noc:%d\n", pos_min, pos, pos_max, ts_min, ts, ts_max, target_ts, pos_limit, start_pos, no_change);
#endif
        assert(ts != AV_NOPTS_VALUE);
        if (target_ts < ts) {
            pos_limit = start_pos - 1;
            pos_max = pos;
            ts_max = ts;
        } else {
            pos_min = pos;
            ts_min = ts;
            /* check if we are lucky */
            if (target_ts == ts)
                break;
        }
    }
    
    pos = pos_min;
#ifdef DEBUG_SEEK
    pos_min = pos;
    ts_min = avif->read_timestamp(s, stream_index, &pos_min, INT64_MAX);
    pos_min++;
    ts_max = avif->read_timestamp(s, stream_index, &pos_min, INT64_MAX);
    av_log(s, AV_LOG_DEBUG, "pos=0x%llx %lld<=%lld<=%lld\n", 
           pos, ts_min, target_ts, ts_max);
#endif
    /* do the seek */
    url_fseek(&s->pb, pos, SEEK_SET);
    st->cur_dts = ts_min;

    return 0;
}

static int av_seek_frame_generic(AVFormatContext *s, 
                                 int stream_index, int64_t timestamp)
{
    int index;
    AVStream *st;

    else
        ret = -1;
    if (ret >= 0) {
        return 0;
    }

    if(s->iformat->read_timestamp)
        return av_seek_frame_binary(s, stream_index, timestamp);
    else
        return av_seek_frame_generic(s, stream_index, timestamp);
}

/*******************************************************/

/* return TRUE if the stream has accurate timings for at least one component */