comparison nut.c @ 437:50bae308f71e libavformat

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

436:dd042d607ec9

    if(flags & FLAG_PTS){
        if(flags & FLAG_FULL_PTS){
            pts= get_v(bc);
            if(frame_type && key_frame){
                av_add_index_entry(
                    s->streams[stream_id], 
                    frame_start, 
                    pts, 
                    frame_start - nut->stream[stream_id].last_sync_pos,
                    AVINDEX_KEYFRAME);
                nut->stream[stream_id].last_sync_pos= frame_start;
                assert(nut->packet_start == frame_start);
            }

            nut->written_packet_size= -1;
        }
    }
}

static int64_t read_timestamp(AVFormatContext *s, int stream_index, int64_t *pos_arg, int64_t pos_limit){
    NUTContext *nut = s->priv_data;
    ByteIOContext *bc = &s->pb;
    int64_t pos, pts;
    uint64_t code;
    int frame_code,step, flags, stream_id, i;
av_log(s, AV_LOG_DEBUG, "read_timestamp(X,%d,%lld,%lld)\n", stream_index, *pos_arg, pos_limit);

            if(stream_id==-1)
                stream_id= get_v(bc);
            if(stream_id >= s->nb_streams)
                goto resync;
                
            pts= get_v(bc);
    
            if(flags & FLAG_KEY_FRAME){
                av_add_index_entry(
                    s->streams[stream_id], 
                    pos, 

        }
    }
    return AV_NOPTS_VALUE;
}

#define DEBUG_SEEK
static int nut_read_seek(AVFormatContext *s, int stream_index, int64_t target_ts){
    NUTContext *nut = s->priv_data;
    StreamContext *stream;
    int64_t pos_min, pos_max, pos, pos_limit;
    int64_t ts_min, ts_max, ts;
    int64_t start_pos;
    int index, no_change,i;
    AVStream *st;

    if (stream_index < 0) {
        stream_index = av_find_default_stream_index(s);
        if (stream_index < 0)
            return -1;
    }
    stream= &nut->stream[stream_index];
    target_ts= (av_rescale(target_ts, stream->rate_num, stream->rate_den) + AV_TIME_BASE/2) / AV_TIME_BASE;

#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 = 0;
        ts_min = 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 = 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= 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 = 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 = read_timestamp(s, stream_index, &pos_min, INT64_MAX);
    pos_min++;
    ts_max = 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);

    nut->written_packet_size= -1;
    for(i=0; i<s->nb_streams; i++)
        nut->stream[i].last_sync_pos= pos;

    return 0;
}

    nut_probe,
    nut_read_header,
    nut_read_packet,
    nut_read_close,
    nut_read_seek,
    .extensions = "nut",
};

#ifdef CONFIG_ENCODERS
static AVOutputFormat nut_oformat = {

437:50bae308f71e

    if(flags & FLAG_PTS){
        if(flags & FLAG_FULL_PTS){
            pts= get_v(bc);
            if(frame_type && key_frame){
                int64_t av_pts= pts * AV_TIME_BASE * stream->rate_den / stream->rate_num;
                av_add_index_entry(
                    s->streams[stream_id], 
                    frame_start, 
                    av_pts, 
                    frame_start - nut->stream[stream_id].last_sync_pos,
                    AVINDEX_KEYFRAME);
                nut->stream[stream_id].last_sync_pos= frame_start;
                assert(nut->packet_start == frame_start);
            }

            nut->written_packet_size= -1;
        }
    }
}

static int64_t nut_read_timestamp(AVFormatContext *s, int stream_index, int64_t *pos_arg, int64_t pos_limit){
    NUTContext *nut = s->priv_data;
    StreamContext *stream;
    ByteIOContext *bc = &s->pb;
    int64_t pos, pts;
    uint64_t code;
    int frame_code,step, flags, stream_id, i;
av_log(s, AV_LOG_DEBUG, "read_timestamp(X,%d,%lld,%lld)\n", stream_index, *pos_arg, pos_limit);

            if(stream_id==-1)
                stream_id= get_v(bc);
            if(stream_id >= s->nb_streams)
                goto resync;
                
            stream= &nut->stream[stream_id];
            pts= get_v(bc) * AV_TIME_BASE * stream->rate_den / stream->rate_num;
    
            if(flags & FLAG_KEY_FRAME){
                av_add_index_entry(
                    s->streams[stream_id], 
                    pos, 

        }
    }
    return AV_NOPTS_VALUE;
}

static int nut_read_seek(AVFormatContext *s, int stream_index, int64_t target_ts){
    NUTContext *nut = s->priv_data;
    int64_t pos;
    int i;

    if(av_seek_frame_binary(s, stream_index, target_ts) < 0)
        return -1;

    nut->written_packet_size= -1;
    pos= url_ftell(&s->pb);
    for(i=0; i<s->nb_streams; i++)
        nut->stream[i].last_sync_pos= pos;

    return 0;
}

    nut_probe,
    nut_read_header,
    nut_read_packet,
    nut_read_close,
    nut_read_seek,
    nut_read_timestamp,
    .extensions = "nut",
};

#ifdef CONFIG_ENCODERS
static AVOutputFormat nut_oformat = {