comparison utils.c @ 437:50bae308f71e libavformat

moving nearly identical binary search code from nut/mpeg/asf to utils.c
author michael
date Mon, 12 Apr 2004 16:50:03 +0000
parents 24545aa514e8
children a699cf5c703d
comparison
equal deleted inserted replaced
436:dd042d607ec9 437:50bae308f71e
995 } 995 }
996 } 996 }
997 return a; 997 return a;
998 } 998 }
999 999
1000 #define DEBUG_SEEK
1001
1002 int av_seek_frame_binary(AVFormatContext *s, int stream_index, int64_t target_ts){
1003 AVInputFormat *avif= s->iformat;
1004 int64_t pos_min, pos_max, pos, pos_limit;
1005 int64_t ts_min, ts_max, ts;
1006 int64_t start_pos;
1007 int index, no_change;
1008 AVStream *st;
1009
1010 if (stream_index < 0) {
1011 stream_index = av_find_default_stream_index(s);
1012 if (stream_index < 0)
1013 return -1;
1014 }
1015
1016 #ifdef DEBUG_SEEK
1017 av_log(s, AV_LOG_DEBUG, "read_seek: %d %lld\n", stream_index, target_ts);
1018 #endif
1019
1020 ts_max=
1021 ts_min= AV_NOPTS_VALUE;
1022 pos_limit= -1; //gcc falsely says it may be uninitalized
1023
1024 st= s->streams[stream_index];
1025 if(st->index_entries){
1026 AVIndexEntry *e;
1027
1028 index= av_index_search_timestamp(st, target_ts);
1029 e= &st->index_entries[index];
1030
1031 if(e->timestamp <= target_ts || e->pos == e->min_distance){
1032 pos_min= e->pos;
1033 ts_min= e->timestamp;
1034 #ifdef DEBUG_SEEK
1035 av_log(s, AV_LOG_DEBUG, "unsing cached pos_min=0x%llx dts_min=%lld\n",
1036 pos_min,ts_min);
1037 #endif
1038 }else{
1039 assert(index==0);
1040 }
1041 index++;
1042 if(index < st->nb_index_entries){
1043 e= &st->index_entries[index];
1044 assert(e->timestamp >= target_ts);
1045 pos_max= e->pos;
1046 ts_max= e->timestamp;
1047 pos_limit= pos_max - e->min_distance;
1048 #ifdef DEBUG_SEEK
1049 av_log(s, AV_LOG_DEBUG, "unsing cached pos_max=0x%llx pos_limit=0x%llx dts_max=%lld\n",
1050 pos_max,pos_limit, ts_max);
1051 #endif
1052 }
1053 }
1054
1055 if(ts_min == AV_NOPTS_VALUE){
1056 pos_min = s->data_offset;
1057 ts_min = avif->read_timestamp(s, stream_index, &pos_min, INT64_MAX);
1058 if (ts_min == AV_NOPTS_VALUE)
1059 return -1;
1060 }
1061
1062 if(ts_max == AV_NOPTS_VALUE){
1063 int step= 1024;
1064 pos_max = url_filesize(url_fileno(&s->pb)) - 1;
1065 do{
1066 pos_max -= step;
1067 ts_max = avif->read_timestamp(s, stream_index, &pos_max, pos_max + step);
1068 step += step;
1069 }while(ts_max == AV_NOPTS_VALUE && pos_max >= step);
1070 if (ts_max == AV_NOPTS_VALUE)
1071 return -1;
1072
1073 for(;;){
1074 int64_t tmp_pos= pos_max + 1;
1075 int64_t tmp_ts= avif->read_timestamp(s, stream_index, &tmp_pos, INT64_MAX);
1076 if(tmp_ts == AV_NOPTS_VALUE)
1077 break;
1078 ts_max= tmp_ts;
1079 pos_max= tmp_pos;
1080 }
1081 pos_limit= pos_max;
1082 }
1083
1084 no_change=0;
1085 while (pos_min < pos_limit) {
1086 #ifdef DEBUG_SEEK
1087 av_log(s, AV_LOG_DEBUG, "pos_min=0x%llx pos_max=0x%llx dts_min=%lld dts_max=%lld\n",
1088 pos_min, pos_max,
1089 ts_min, ts_max);
1090 #endif
1091 assert(pos_limit <= pos_max);
1092
1093 if(no_change==0){
1094 int64_t approximate_keyframe_distance= pos_max - pos_limit;
1095 // interpolate position (better than dichotomy)
1096 pos = (int64_t)((double)(pos_max - pos_min) *
1097 (double)(target_ts - ts_min) /
1098 (double)(ts_max - ts_min)) + pos_min - approximate_keyframe_distance;
1099 }else if(no_change==1){
1100 // bisection, if interpolation failed to change min or max pos last time
1101 pos = (pos_min + pos_limit)>>1;
1102 }else{
1103 // linear search if bisection failed, can only happen if there are very few or no keframes between min/max
1104 pos=pos_min;
1105 }
1106 if(pos <= pos_min)
1107 pos= pos_min + 1;
1108 else if(pos > pos_limit)
1109 pos= pos_limit;
1110 start_pos= pos;
1111
1112 ts = avif->read_timestamp(s, stream_index, &pos, INT64_MAX); //may pass pos_limit instead of -1
1113 if(pos == pos_max)
1114 no_change++;
1115 else
1116 no_change=0;
1117 #ifdef DEBUG_SEEK
1118 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);
1119 #endif
1120 assert(ts != AV_NOPTS_VALUE);
1121 if (target_ts < ts) {
1122 pos_limit = start_pos - 1;
1123 pos_max = pos;
1124 ts_max = ts;
1125 } else {
1126 pos_min = pos;
1127 ts_min = ts;
1128 /* check if we are lucky */
1129 if (target_ts == ts)
1130 break;
1131 }
1132 }
1133
1134 pos = pos_min;
1135 #ifdef DEBUG_SEEK
1136 pos_min = pos;
1137 ts_min = avif->read_timestamp(s, stream_index, &pos_min, INT64_MAX);
1138 pos_min++;
1139 ts_max = avif->read_timestamp(s, stream_index, &pos_min, INT64_MAX);
1140 av_log(s, AV_LOG_DEBUG, "pos=0x%llx %lld<=%lld<=%lld\n",
1141 pos, ts_min, target_ts, ts_max);
1142 #endif
1143 /* do the seek */
1144 url_fseek(&s->pb, pos, SEEK_SET);
1145 st->cur_dts = ts_min;
1146
1147 return 0;
1148 }
1149
1000 static int av_seek_frame_generic(AVFormatContext *s, 1150 static int av_seek_frame_generic(AVFormatContext *s,
1001 int stream_index, int64_t timestamp) 1151 int stream_index, int64_t timestamp)
1002 { 1152 {
1003 int index; 1153 int index;
1004 AVStream *st; 1154 AVStream *st;
1045 else 1195 else
1046 ret = -1; 1196 ret = -1;
1047 if (ret >= 0) { 1197 if (ret >= 0) {
1048 return 0; 1198 return 0;
1049 } 1199 }
1050 1200
1051 return av_seek_frame_generic(s, stream_index, timestamp); 1201 if(s->iformat->read_timestamp)
1202 return av_seek_frame_binary(s, stream_index, timestamp);
1203 else
1204 return av_seek_frame_generic(s, stream_index, timestamp);
1052 } 1205 }
1053 1206
1054 /*******************************************************/ 1207 /*******************************************************/
1055 1208
1056 /* return TRUE if the stream has accurate timings for at least one component */ 1209 /* return TRUE if the stream has accurate timings for at least one component */